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