pseudo-merge.h

   1 #ifndef PSEUDO_MERGE_H
   2 #define PSEUDO_MERGE_H
   3
   4 #include "git-compat-util.h"
   5 #include "strmap.h"
   6 #include "khash.h"
   7 #include "ewah/ewok.h"
   8
   9 struct commit;
  10 struct string_list;
  11 struct bitmap_index;
  12 struct bitmap_writer;
  13 struct repository;
  14
  15 /*
  16  * A pseudo-merge group tracks the set of non-bitmapped reference tips
  17  * that match the given pattern.
  18  *
  19  * Within those matches, they are further segmented by separating
  20  * consecutive capture groups with '-' dash character capture groups
  21  * with '-' dash characters.
  22  *
  23  * Those groups are then ordered by committer date and partitioned
  24  * into individual pseudo-merge(s) according to the decay, max_merges,
  25  * sample_rate, and threshold parameters.
  26  */
  27 struct pseudo_merge_group {
  28         regex_t *pattern;
  29
  30         /* capture group(s) -> struct pseudo_merge_matches */
  31         struct strmap matches;
  32
  33         /*
  34          * The individual pseudo-merge(s) that are generated from the
  35          * above array of matches, partitioned according to the below
  36          * parameters.
  37          */
  38         struct commit **merges;
  39         size_t merges_nr;
  40         size_t merges_alloc;
  41
  42         /*
  43          * Pseudo-merge grouping parameters. See git-config(1) for
  44          * more information.
  45          */
  46         double decay;
  47         int max_merges;
  48         double sample_rate;
  49         int stable_size;
  50         timestamp_t threshold;
  51         timestamp_t stable_threshold;
  52 };
  53
  54 void pseudo_merge_group_release(struct pseudo_merge_group *group);
  55
  56 struct pseudo_merge_matches {
  57         struct commit **stable;
  58         struct commit **unstable;
  59         size_t stable_nr, stable_alloc;
  60         size_t unstable_nr, unstable_alloc;
  61 };
  62
  63 /*
  64  * Read the repository's configuration:
  65  *
  66  *   - bitmapPseudoMerge.<name>.pattern
  67  *   - bitmapPseudoMerge.<name>.decay
  68  *   - bitmapPseudoMerge.<name>.sampleRate
  69  *   - bitmapPseudoMerge.<name>.threshold
  70  *   - bitmapPseudoMerge.<name>.maxMerges
  71  *   - bitmapPseudoMerge.<name>.stableThreshold
  72  *   - bitmapPseudoMerge.<name>.stableSize
  73  *
  74  * and populates the given `list` with pseudo-merge groups. String
  75  * entry keys are the pseudo-merge group names, and the values are
  76  * pointers to the pseudo_merge_group structure itself.
  77  */
  78 void load_pseudo_merges_from_config(struct repository *r, struct string_list *list);
  79
  80 /*
  81  * A pseudo-merge commit index (pseudo_merge_commit_idx) maps a
  82  * particular (non-pseudo-merge) commit to the list of pseudo-merge(s)
  83  * it appears in.
  84  */
  85 struct pseudo_merge_commit_idx {
  86         uint32_t *pseudo_merge;
  87         size_t nr, alloc;
  88 };
  89
  90 /*
  91  * Selects pseudo-merges from a list of commits, populating the given
  92  * string_list of pseudo-merge groups.
  93  *
  94  * Populates the pseudo_merge_commits map with a commit_idx
  95  * corresponding to each commit in the list. Counts the total number
  96  * of pseudo-merges generated.
  97  *
  98  * Optionally shows a progress meter.
  99  */
 100 void select_pseudo_merges(struct bitmap_writer *writer);
 101
 102 /*
 103  * Represents a serialized view of a file containing pseudo-merge(s)
 104  * (see Documentation/technical/bitmap-format.txt for a specification
 105  * of the format).
 106  */
 107 struct pseudo_merge_map {
 108         /*
 109          * An array of pseudo-merge(s), lazily loaded from the .bitmap
 110          * file.
 111          */
 112         struct pseudo_merge *v;
 113         size_t nr;
 114         size_t commits_nr;
 115
 116         /*
 117          * Pointers into a memory-mapped view of the .bitmap file:
 118          *
 119          *   - map: the beginning of the .bitmap file
 120          *   - commits: the beginning of the pseudo-merge commit index
 121          *   - map_size: the size of the .bitmap file
 122          */
 123         const unsigned char *map;
 124         const unsigned char *commits;
 125
 126         size_t map_size;
 127 };
 128
 129 /*
 130  * An individual pseudo-merge, storing a pair of lazily-loaded
 131  * bitmaps:
 132  *
 133  *  - commits: the set of commit(s) that are part of the pseudo-merge
 134  *  - bitmap: the set of object(s) reachable from the above set of
 135  *    commits.
 136  *
 137  * The `at` and `bitmap_at` fields are used to store the locations of
 138  * each of the above bitmaps in the .bitmap file.
 139  */
 140 struct pseudo_merge {
 141         struct ewah_bitmap *commits;
 142         struct ewah_bitmap *bitmap;
 143
 144         off_t at;
 145         off_t bitmap_at;
 146
 147         /*
 148          * `satisfied` indicates whether the given pseudo-merge has been
 149          * used.
 150          *
 151          * `loaded_commits` and `loaded_bitmap` indicate whether the
 152          * respective bitmaps have been loaded and read from the
 153          * .bitmap file.
 154          */
 155         unsigned satisfied : 1,
 156                  loaded_commits : 1,
 157                  loaded_bitmap : 1;
 158 };
 159
 160 /*
 161  * Frees the given pseudo-merge map, releasing any memory held by (a)
 162  * parsed EWAH bitmaps, or (b) the array of pseudo-merges itself. Does
 163  * not free the memory-mapped view of the .bitmap file.
 164  */
 165 void free_pseudo_merge_map(struct pseudo_merge_map *pm);
 166
 167 /*
 168  * Loads the bitmap corresponding to the given pseudo-merge from the
 169  * map, if it has not already been loaded.
 170  */
 171 struct ewah_bitmap *pseudo_merge_bitmap(const struct pseudo_merge_map *pm,
 172                                         struct pseudo_merge *merge);
 173
 174 /*
 175  * Loads the pseudo-merge and its commits bitmap from the given
 176  * pseudo-merge map, if it has not already been loaded.
 177  */
 178 struct pseudo_merge *use_pseudo_merge(const struct pseudo_merge_map *pm,
 179                                       struct pseudo_merge *merge);
 180
 181 /*
 182  * Applies pseudo-merge(s) containing the given commit to the bitmap
 183  * "result".
 184  *
 185  * If any pseudo-merge(s) were satisfied, returns the number
 186  * satisfied, otherwise returns 0. If any were satisfied, the
 187  * remaining unsatisfied pseudo-merges are cascaded (see below).
 188  */
 189 int apply_pseudo_merges_for_commit(const struct pseudo_merge_map *pm,
 190                                    struct bitmap *result,
 191                                    struct commit *commit, uint32_t commit_pos);
 192
 193 /*
 194  * Applies pseudo-merge(s) which are satisfied according to the
 195  * current bitmap in result (or roots, see below). If any
 196  * pseudo-merges were satisfied, repeat the process over unsatisfied
 197  * pseudo-merge commits until no more pseudo-merges are satisfied.
 198  *
 199  * Result is the bitmap to which the pseudo-merge(s) are applied.
 200  * Roots (if given) is a bitmap of the traversal tip(s) for either
 201  * side of a reachability traversal.
 202  *
 203  * Roots may given instead of a populated results bitmap at the
 204  * beginning of a traversal on either side where the reachability
 205  * closure over tips is not yet known.
 206  */
 207 int cascade_pseudo_merges(const struct pseudo_merge_map *pm,
 208                           struct bitmap *result,
 209                           struct bitmap *roots);
 210
 211 /*
 212  * Returns a pseudo-merge which contains the exact set of commits
 213  * listed in the "parents" bitamp, or NULL if none could be found.
 214  */
 215 struct pseudo_merge *pseudo_merge_for_parents(const struct pseudo_merge_map *pm,
 216                                               struct bitmap *parents);
 217
 218 #endif