freshlybakedca.ke
Git fork
1#define USE_THE_REPOSITORY_VARIABLE
2#define DISABLE_SIGN_COMPARE_WARNINGS
3
4#include "git-compat-util.h"
5#include "pseudo-merge.h"
6#include "date.h"
7#include "oid-array.h"
8#include "strbuf.h"
9#include "config.h"
10#include "string-list.h"
11#include "refs.h"
12#include "pack-bitmap.h"
13#include "commit.h"
14#include "alloc.h"
15#include "progress.h"
16#include "hex.h"
17
18#define DEFAULT_PSEUDO_MERGE_DECAY 1.0
19#define DEFAULT_PSEUDO_MERGE_MAX_MERGES 64
20#define DEFAULT_PSEUDO_MERGE_SAMPLE_RATE 1
21#define DEFAULT_PSEUDO_MERGE_THRESHOLD approxidate("1.week.ago")
22#define DEFAULT_PSEUDO_MERGE_STABLE_THRESHOLD approxidate("1.month.ago")
23#define DEFAULT_PSEUDO_MERGE_STABLE_SIZE 512
24
25static double gitexp(double base, int exp)
26{
27 double result = 1;
28 while (1) {
29 if (exp % 2)
30 result *= base;
31 exp >>= 1;
32 if (!exp)
33 break;
34 base *= base;
35 }
36 return result;
37}
38
39static uint32_t pseudo_merge_group_size(const struct pseudo_merge_group *group,
40 const struct pseudo_merge_matches *matches,
41 uint32_t i)
42{
43 double C = 0.0f;
44 uint32_t n;
45
46 /*
47 * The size of pseudo-merge groups decays according to a power series,
48 * which looks like:
49 *
50 * f(n) = C * n^-k
51 *
52 * , where 'n' is the n-th pseudo-merge group, 'f(n)' is its size, 'k'
53 * is the decay rate, and 'C' is a scaling value.
54 *
55 * The value of C depends on the number of groups, decay rate, and total
56 * number of commits. It is computed such that if there are M and N
57 * total groups and commits, respectively, that:
58 *
59 * N = f(0) + f(1) + ... f(M-1)
60 *
61 * Rearranging to isolate C, we get:
62 *
63 * N = \sum_{n=1}^M C / n^k
64 *
65 * N / C = \sum_{n=1}^M n^-k
66 *
67 * C = N / \sum_{n=1}^M n^-k
68 *
69 * For example, if we have a decay rate of 'k' being equal to 1.5, 'N'
70 * total commits equal to 10,000, and 'M' being equal to 6 groups, then
71 * the (rounded) group sizes are:
72 *
73 * { 5469, 1934, 1053, 684, 489, 372 }
74 *
75 * increasing the number of total groups, say to 10, scales the group
76 * sizes appropriately:
77 *
78 * { 5012, 1772, 964, 626, 448, 341, 271, 221, 186, 158 }
79 */
80 for (n = 0; n < group->max_merges; n++)
81 C += 1.0 / gitexp(n + 1, group->decay);
82 C = matches->unstable_nr / C;
83
84 return (uint32_t)((C / gitexp(i + 1, group->decay)) + 0.5);
85}
86
87static void pseudo_merge_group_init(struct pseudo_merge_group *group)
88{
89 memset(group, 0, sizeof(struct pseudo_merge_group));
90
91 strmap_init_with_options(&group->matches, NULL, 1);
92
93 group->decay = DEFAULT_PSEUDO_MERGE_DECAY;
94 group->max_merges = DEFAULT_PSEUDO_MERGE_MAX_MERGES;
95 group->sample_rate = DEFAULT_PSEUDO_MERGE_SAMPLE_RATE;
96 group->threshold = DEFAULT_PSEUDO_MERGE_THRESHOLD;
97 group->stable_threshold = DEFAULT_PSEUDO_MERGE_STABLE_THRESHOLD;
98 group->stable_size = DEFAULT_PSEUDO_MERGE_STABLE_SIZE;
99}
100
101void pseudo_merge_group_release(struct pseudo_merge_group *group)
102{
103 struct hashmap_iter iter;
104 struct strmap_entry *e;
105
106 regfree(group->pattern);
107 free(group->pattern);
108
109 strmap_for_each_entry(&group->matches, &iter, e) {
110 struct pseudo_merge_matches *matches = e->value;
111 free(matches->stable);
112 free(matches->unstable);
113 free(matches);
114 }
115 strmap_clear(&group->matches, 0);
116
117 free(group->merges);
118}
119
120static int pseudo_merge_config(const char *var, const char *value,
121 const struct config_context *ctx,
122 void *cb_data)
123{
124 struct string_list *list = cb_data;
125 struct string_list_item *item;
126 struct pseudo_merge_group *group;
127 struct strbuf buf = STRBUF_INIT;
128 const char *sub, *key;
129 size_t sub_len;
130 int ret = 0;
131
132 if (parse_config_key(var, "bitmappseudomerge", &sub, &sub_len, &key))
133 goto done;
134
135 if (!sub_len)
136 goto done;
137
138 strbuf_add(&buf, sub, sub_len);
139
140 item = string_list_lookup(list, buf.buf);
141 if (!item) {
142 item = string_list_insert(list, buf.buf);
143
144 item->util = xmalloc(sizeof(struct pseudo_merge_group));
145 pseudo_merge_group_init(item->util);
146 }
147
148 group = item->util;
149
150 if (!strcmp(key, "pattern")) {
151 struct strbuf re = STRBUF_INIT;
152
153 free(group->pattern);
154 if (*value != '^')
155 strbuf_addch(&re, '^');
156 strbuf_addstr(&re, value);
157
158 group->pattern = xcalloc(1, sizeof(regex_t));
159 if (regcomp(group->pattern, re.buf, REG_EXTENDED))
160 die(_("failed to load pseudo-merge regex for %s: '%s'"),
161 sub, re.buf);
162
163 strbuf_release(&re);
164 } else if (!strcmp(key, "decay")) {
165 group->decay = git_config_double(var, value, ctx->kvi);
166 if (group->decay < 0) {
167 warning(_("%s must be non-negative, using default"), var);
168 group->decay = DEFAULT_PSEUDO_MERGE_DECAY;
169 }
170 } else if (!strcmp(key, "samplerate")) {
171 group->sample_rate = git_config_double(var, value, ctx->kvi);
172 if (!(0 <= group->sample_rate && group->sample_rate <= 1)) {
173 warning(_("%s must be between 0 and 1, using default"), var);
174 group->sample_rate = DEFAULT_PSEUDO_MERGE_SAMPLE_RATE;
175 }
176 } else if (!strcmp(key, "threshold")) {
177 if (git_config_expiry_date(&group->threshold, var, value)) {
178 ret = -1;
179 goto done;
180 }
181 } else if (!strcmp(key, "maxmerges")) {
182 group->max_merges = git_config_int(var, value, ctx->kvi);
183 if (group->max_merges < 0) {
184 warning(_("%s must be non-negative, using default"), var);
185 group->max_merges = DEFAULT_PSEUDO_MERGE_MAX_MERGES;
186 }
187 } else if (!strcmp(key, "stablethreshold")) {
188 if (git_config_expiry_date(&group->stable_threshold, var, value)) {
189 ret = -1;
190 goto done;
191 }
192 } else if (!strcmp(key, "stablesize")) {
193 group->stable_size = git_config_int(var, value, ctx->kvi);
194 if (group->stable_size <= 0) {
195 warning(_("%s must be positive, using default"), var);
196 group->stable_size = DEFAULT_PSEUDO_MERGE_STABLE_SIZE;
197 }
198 }
199
200done:
201 strbuf_release(&buf);
202
203 return ret;
204}
205
206void load_pseudo_merges_from_config(struct repository *r,
207 struct string_list *list)
208{
209 struct string_list_item *item;
210
211 repo_config(r, pseudo_merge_config, list);
212
213 for_each_string_list_item(item, list) {
214 struct pseudo_merge_group *group = item->util;
215 if (!group->pattern)
216 die(_("pseudo-merge group '%s' missing required pattern"),
217 item->string);
218 if (group->threshold < group->stable_threshold)
219 die(_("pseudo-merge group '%s' has unstable threshold "
220 "before stable one"), item->string);
221 }
222}
223
224static int find_pseudo_merge_group_for_ref(const char *refname,
225 const char *referent UNUSED,
226 const struct object_id *oid,
227 int flags UNUSED,
228 void *_data)
229{
230 struct bitmap_writer *writer = _data;
231 struct object_id peeled;
232 struct commit *c;
233 uint32_t i;
234 int has_bitmap;
235
236 if (!peel_iterated_oid(the_repository, oid, &peeled))
237 oid = &peeled;
238
239 c = lookup_commit(the_repository, oid);
240 if (!c)
241 return 0;
242 if (!packlist_find(writer->to_pack, oid))
243 return 0;
244
245 has_bitmap = bitmap_writer_has_bitmapped_object_id(writer, oid);
246
247 for (i = 0; i < writer->pseudo_merge_groups.nr; i++) {
248 struct pseudo_merge_group *group;
249 struct pseudo_merge_matches *matches;
250 struct strbuf group_name = STRBUF_INIT;
251 regmatch_t captures[16];
252 size_t j;
253
254 group = writer->pseudo_merge_groups.items[i].util;
255 if (regexec(group->pattern, refname, ARRAY_SIZE(captures),
256 captures, 0))
257 continue;
258
259 if (captures[ARRAY_SIZE(captures) - 1].rm_so != -1)
260 warning(_("pseudo-merge regex from config has too many capture "
261 "groups (max=%"PRIuMAX")"),
262 (uintmax_t)ARRAY_SIZE(captures) - 2);
263
264 for (j = !!group->pattern->re_nsub; j < ARRAY_SIZE(captures); j++) {
265 regmatch_t *match = &captures[j];
266 if (match->rm_so == -1)
267 continue;
268
269 if (group_name.len)
270 strbuf_addch(&group_name, '-');
271
272 strbuf_add(&group_name, refname + match->rm_so,
273 match->rm_eo - match->rm_so);
274 }
275
276 matches = strmap_get(&group->matches, group_name.buf);
277 if (!matches) {
278 matches = xcalloc(1, sizeof(*matches));
279 strmap_put(&group->matches, group_name.buf,
280 matches);
281 }
282
283 if (c->date <= group->stable_threshold) {
284 ALLOC_GROW(matches->stable, matches->stable_nr + 1,
285 matches->stable_alloc);
286 matches->stable[matches->stable_nr++] = c;
287 } else if (c->date <= group->threshold && !has_bitmap) {
288 ALLOC_GROW(matches->unstable, matches->unstable_nr + 1,
289 matches->unstable_alloc);
290 matches->unstable[matches->unstable_nr++] = c;
291 }
292
293 strbuf_release(&group_name);
294 }
295
296 return 0;
297}
298
299static struct commit *push_pseudo_merge(struct pseudo_merge_group *group)
300{
301 struct commit *merge;
302
303 ALLOC_GROW(group->merges, group->merges_nr + 1, group->merges_alloc);
304
305 merge = alloc_commit_node(the_repository);
306 merge->object.parsed = 1;
307 merge->object.flags |= BITMAP_PSEUDO_MERGE;
308
309 group->merges[group->merges_nr++] = merge;
310
311 return merge;
312}
313
314static struct pseudo_merge_commit_idx *pseudo_merge_idx(kh_oid_map_t *pseudo_merge_commits,
315 const struct object_id *oid)
316
317{
318 struct pseudo_merge_commit_idx *pmc;
319 int hash_ret;
320 khiter_t hash_pos = kh_put_oid_map(pseudo_merge_commits, *oid,
321 &hash_ret);
322
323 if (hash_ret) {
324 CALLOC_ARRAY(pmc, 1);
325 kh_value(pseudo_merge_commits, hash_pos) = pmc;
326 } else {
327 pmc = kh_value(pseudo_merge_commits, hash_pos);
328 }
329
330 return pmc;
331}
332
333#define MIN_PSEUDO_MERGE_SIZE 8
334
335static void select_pseudo_merges_1(struct bitmap_writer *writer,
336 struct pseudo_merge_group *group,
337 struct pseudo_merge_matches *matches)
338{
339 uint32_t i, j;
340 uint32_t stable_merges_nr;
341
342 if (!matches->stable_nr && !matches->unstable_nr)
343 return; /* all tips in this group already have bitmaps */
344
345 stable_merges_nr = matches->stable_nr / group->stable_size;
346 if (matches->stable_nr % group->stable_size)
347 stable_merges_nr++;
348
349 /* make stable_merges_nr pseudo merges for stable commits */
350 for (i = 0, j = 0; i < stable_merges_nr; i++) {
351 struct commit *merge;
352 struct commit_list **p;
353
354 merge = push_pseudo_merge(group);
355 p = &merge->parents;
356
357 /*
358 * For each pseudo-merge created above, add parents to the
359 * allocated commit node from the stable set of commits
360 * (un-bitmapped, newer than the stable threshold).
361 */
362 do {
363 struct commit *c;
364 struct pseudo_merge_commit_idx *pmc;
365
366 if (j >= matches->stable_nr)
367 break;
368
369 c = matches->stable[j++];
370 /*
371 * Here and below, make sure that we keep our mapping of
372 * commits -> pseudo-merge(s) which include the key'd
373 * commit up-to-date.
374 */
375 pmc = pseudo_merge_idx(writer->pseudo_merge_commits,
376 &c->object.oid);
377
378 ALLOC_GROW(pmc->pseudo_merge, pmc->nr + 1, pmc->alloc);
379
380 pmc->pseudo_merge[pmc->nr++] = writer->pseudo_merges_nr;
381 p = commit_list_append(c, p);
382 } while (j % group->stable_size);
383
384 if (merge->parents) {
385 bitmap_writer_push_commit(writer, merge, 1);
386 writer->pseudo_merges_nr++;
387 }
388 }
389
390 /* make up to group->max_merges pseudo merges for unstable commits */
391 for (i = 0, j = 0; i < group->max_merges; i++) {
392 struct commit *merge;
393 struct commit_list **p;
394 uint32_t size, end;
395
396 merge = push_pseudo_merge(group);
397 p = &merge->parents;
398
399 size = pseudo_merge_group_size(group, matches, i);
400 end = size < MIN_PSEUDO_MERGE_SIZE ? matches->unstable_nr : j + size;
401
402 /*
403 * For each pseudo-merge commit created above, add parents to
404 * the allocated commit node from the unstable set of commits
405 * (newer than the stable threshold).
406 *
407 * Account for the sample rate, since not every candidate from
408 * the set of stable commits will be included as a pseudo-merge
409 * parent.
410 */
411 for (; j < end && j < matches->unstable_nr; j++) {
412 struct commit *c = matches->unstable[j];
413 struct pseudo_merge_commit_idx *pmc;
414
415 if (j % (uint32_t)(1.0 / group->sample_rate))
416 continue;
417
418 pmc = pseudo_merge_idx(writer->pseudo_merge_commits,
419 &c->object.oid);
420
421 ALLOC_GROW(pmc->pseudo_merge, pmc->nr + 1, pmc->alloc);
422
423 pmc->pseudo_merge[pmc->nr++] = writer->pseudo_merges_nr;
424 p = commit_list_append(c, p);
425 }
426
427 if (merge->parents) {
428 bitmap_writer_push_commit(writer, merge, 1);
429 writer->pseudo_merges_nr++; }
430 if (end >= matches->unstable_nr)
431 break;
432 }
433}
434
435static int commit_date_cmp(const void *va, const void *vb)
436{
437 timestamp_t a = (*(const struct commit **)va)->date;
438 timestamp_t b = (*(const struct commit **)vb)->date;
439
440 if (a < b)
441 return -1;
442 else if (a > b)
443 return 1;
444 return 0;
445}
446
447static void sort_pseudo_merge_matches(struct pseudo_merge_matches *matches)
448{
449 QSORT(matches->stable, matches->stable_nr, commit_date_cmp);
450 QSORT(matches->unstable, matches->unstable_nr, commit_date_cmp);
451}
452
453void select_pseudo_merges(struct bitmap_writer *writer)
454{
455 struct progress *progress = NULL;
456 uint32_t i;
457
458 if (!writer->pseudo_merge_groups.nr)
459 return;
460
461 if (writer->show_progress)
462 progress = start_progress(the_repository,
463 "Selecting pseudo-merge commits",
464 writer->pseudo_merge_groups.nr);
465
466 refs_for_each_ref(get_main_ref_store(the_repository),
467 find_pseudo_merge_group_for_ref, writer);
468
469 for (i = 0; i < writer->pseudo_merge_groups.nr; i++) {
470 struct pseudo_merge_group *group;
471 struct hashmap_iter iter;
472 struct strmap_entry *e;
473
474 group = writer->pseudo_merge_groups.items[i].util;
475 strmap_for_each_entry(&group->matches, &iter, e) {
476 struct pseudo_merge_matches *matches = e->value;
477
478 sort_pseudo_merge_matches(matches);
479
480 select_pseudo_merges_1(writer, group, matches);
481 }
482
483 display_progress(progress, i + 1);
484 }
485
486 stop_progress(&progress);
487}
488
489void free_pseudo_merge_map(struct pseudo_merge_map *pm)
490{
491 uint32_t i;
492 for (i = 0; i < pm->nr; i++) {
493 ewah_pool_free(pm->v[i].commits);
494 ewah_pool_free(pm->v[i].bitmap);
495 }
496 free(pm->v);
497}
498
499struct pseudo_merge_commit_ext {
500 uint32_t nr;
501 const unsigned char *ptr;
502};
503
504static int pseudo_merge_ext_at(const struct pseudo_merge_map *pm,
505 struct pseudo_merge_commit_ext *ext, size_t at)
506{
507 if (at >= pm->map_size)
508 return error(_("extended pseudo-merge read out-of-bounds "
509 "(%"PRIuMAX" >= %"PRIuMAX")"),
510 (uintmax_t)at, (uintmax_t)pm->map_size);
511 if (at + 4 >= pm->map_size)
512 return error(_("extended pseudo-merge entry is too short "
513 "(%"PRIuMAX" >= %"PRIuMAX")"),
514 (uintmax_t)(at + 4), (uintmax_t)pm->map_size);
515
516 ext->nr = get_be32(pm->map + at);
517 ext->ptr = pm->map + at + sizeof(uint32_t);
518
519 return 0;
520}
521
522struct ewah_bitmap *pseudo_merge_bitmap(const struct pseudo_merge_map *pm,
523 struct pseudo_merge *merge)
524{
525 if (!merge->loaded_commits)
526 BUG("cannot use unloaded pseudo-merge bitmap");
527
528 if (!merge->loaded_bitmap) {
529 size_t at = merge->bitmap_at;
530
531 merge->bitmap = read_bitmap(pm->map, pm->map_size, &at);
532 merge->loaded_bitmap = 1;
533 }
534
535 return merge->bitmap;
536}
537
538struct pseudo_merge *use_pseudo_merge(const struct pseudo_merge_map *pm,
539 struct pseudo_merge *merge)
540{
541 if (!merge->loaded_commits) {
542 size_t pos = merge->at;
543
544 merge->commits = read_bitmap(pm->map, pm->map_size, &pos);
545 merge->bitmap_at = pos;
546 merge->loaded_commits = 1;
547 }
548 return merge;
549}
550
551static struct pseudo_merge *pseudo_merge_at(const struct pseudo_merge_map *pm,
552 struct object_id *oid,
553 size_t want)
554{
555 size_t lo = 0;
556 size_t hi = pm->nr;
557
558 while (lo < hi) {
559 size_t mi = lo + (hi - lo) / 2;
560 size_t got = pm->v[mi].at;
561
562 if (got == want)
563 return use_pseudo_merge(pm, &pm->v[mi]);
564 else if (got < want)
565 hi = mi;
566 else
567 lo = mi + 1;
568 }
569
570 warning(_("could not find pseudo-merge for commit %s at offset %"PRIuMAX),
571 oid_to_hex(oid), (uintmax_t)want);
572
573 return NULL;
574}
575
576struct pseudo_merge_commit {
577 uint32_t commit_pos;
578 uint64_t pseudo_merge_ofs;
579};
580
581#define PSEUDO_MERGE_COMMIT_RAWSZ (sizeof(uint32_t)+sizeof(uint64_t))
582
583static void read_pseudo_merge_commit_at(struct pseudo_merge_commit *merge,
584 const unsigned char *at)
585{
586 merge->commit_pos = get_be32(at);
587 merge->pseudo_merge_ofs = get_be64(at + sizeof(uint32_t));
588}
589
590static int nth_pseudo_merge_ext(const struct pseudo_merge_map *pm,
591 struct pseudo_merge_commit_ext *ext,
592 struct pseudo_merge_commit *merge,
593 uint32_t n)
594{
595 size_t ofs;
596
597 if (n >= ext->nr)
598 return error(_("extended pseudo-merge lookup out-of-bounds "
599 "(%"PRIu32" >= %"PRIu32")"), n, ext->nr);
600
601 ofs = get_be64(ext->ptr + st_mult(n, sizeof(uint64_t)));
602 if (ofs >= pm->map_size)
603 return error(_("out-of-bounds read: (%"PRIuMAX" >= %"PRIuMAX")"),
604 (uintmax_t)ofs, (uintmax_t)pm->map_size);
605
606 read_pseudo_merge_commit_at(merge, pm->map + ofs);
607
608 return 0;
609}
610
611static unsigned apply_pseudo_merge(const struct pseudo_merge_map *pm,
612 struct pseudo_merge *merge,
613 struct bitmap *result,
614 struct bitmap *roots)
615{
616 if (merge->satisfied)
617 return 0;
618
619 if (!ewah_bitmap_is_subset(merge->commits, roots ? roots : result))
620 return 0;
621
622 bitmap_or_ewah(result, pseudo_merge_bitmap(pm, merge));
623 if (roots)
624 bitmap_or_ewah(roots, pseudo_merge_bitmap(pm, merge));
625 merge->satisfied = 1;
626
627 return 1;
628}
629
630static int pseudo_merge_commit_cmp(const void *va, const void *vb)
631{
632 struct pseudo_merge_commit merge;
633 uint32_t key = *(uint32_t*)va;
634
635 read_pseudo_merge_commit_at(&merge, vb);
636
637 if (key < merge.commit_pos)
638 return -1;
639 if (key > merge.commit_pos)
640 return 1;
641 return 0;
642}
643
644static struct pseudo_merge_commit *find_pseudo_merge(const struct pseudo_merge_map *pm,
645 uint32_t pos)
646{
647 if (!pm->commits_nr)
648 return NULL;
649
650 return bsearch(&pos, pm->commits, pm->commits_nr,
651 PSEUDO_MERGE_COMMIT_RAWSZ, pseudo_merge_commit_cmp);
652}
653
654int apply_pseudo_merges_for_commit(const struct pseudo_merge_map *pm,
655 struct bitmap *result,
656 struct commit *commit, uint32_t commit_pos)
657{
658 struct pseudo_merge *merge;
659 struct pseudo_merge_commit *merge_commit;
660 int ret = 0;
661
662 merge_commit = find_pseudo_merge(pm, commit_pos);
663 if (!merge_commit)
664 return 0;
665
666 if (merge_commit->pseudo_merge_ofs & ((uint64_t)1<<63)) {
667 struct pseudo_merge_commit_ext ext = { 0 };
668 off_t ofs = merge_commit->pseudo_merge_ofs & ~((uint64_t)1<<63);
669 uint32_t i;
670
671 if (pseudo_merge_ext_at(pm, &ext, ofs) < -1) {
672 warning(_("could not read extended pseudo-merge table "
673 "for commit %s"),
674 oid_to_hex(&commit->object.oid));
675 return ret;
676 }
677
678 for (i = 0; i < ext.nr; i++) {
679 if (nth_pseudo_merge_ext(pm, &ext, merge_commit, i) < 0)
680 return ret;
681
682 merge = pseudo_merge_at(pm, &commit->object.oid,
683 merge_commit->pseudo_merge_ofs);
684
685 if (!merge)
686 return ret;
687
688 if (apply_pseudo_merge(pm, merge, result, NULL))
689 ret++;
690 }
691 } else {
692 merge = pseudo_merge_at(pm, &commit->object.oid,
693 merge_commit->pseudo_merge_ofs);
694
695 if (!merge)
696 return ret;
697
698 if (apply_pseudo_merge(pm, merge, result, NULL))
699 ret++;
700 }
701
702 if (ret)
703 cascade_pseudo_merges(pm, result, NULL);
704
705 return ret;
706}
707
708int cascade_pseudo_merges(const struct pseudo_merge_map *pm,
709 struct bitmap *result,
710 struct bitmap *roots)
711{
712 unsigned any_satisfied;
713 int ret = 0;
714
715 do {
716 struct pseudo_merge *merge;
717 uint32_t i;
718
719 any_satisfied = 0;
720
721 for (i = 0; i < pm->nr; i++) {
722 merge = use_pseudo_merge(pm, &pm->v[i]);
723 if (apply_pseudo_merge(pm, merge, result, roots)) {
724 any_satisfied |= 1;
725 ret++;
726 }
727 }
728 } while (any_satisfied);
729
730 return ret;
731}
732
733struct pseudo_merge *pseudo_merge_for_parents(const struct pseudo_merge_map *pm,
734 struct bitmap *parents)
735{
736 struct pseudo_merge *match = NULL;
737 size_t i;
738
739 if (!pm->nr)
740 return NULL;
741
742 /*
743 * NOTE: this loop is quadratic in the worst-case (where no
744 * matching pseudo-merge bitmaps are found), but in practice
745 * this is OK for a few reasons:
746 *
747 * - Rejecting pseudo-merge bitmaps that do not match the
748 * given commit is done quickly (i.e. `bitmap_equals_ewah()`
749 * returns early when we know the two bitmaps aren't equal.
750 *
751 * - Already matched pseudo-merge bitmaps (which we track with
752 * the `->satisfied` bit here) are skipped as potential
753 * candidates.
754 *
755 * - The number of pseudo-merges should be small (in the
756 * hundreds for most repositories).
757 *
758 * If in the future this semi-quadratic behavior does become a
759 * problem, another approach would be to keep track of which
760 * pseudo-merges are still "viable" after enumerating the
761 * pseudo-merge commit's parents:
762 *
763 * - A pseudo-merge bitmap becomes non-viable when the bit(s)
764 * corresponding to one or more parent(s) of the given
765 * commit are not set in a candidate pseudo-merge's commits
766 * bitmap.
767 *
768 * - After processing all bits, enumerate the remaining set of
769 * viable pseudo-merge bitmaps, and check that their
770 * popcount() matches the number of parents in the given
771 * commit.
772 */
773 for (i = 0; i < pm->nr; i++) {
774 struct pseudo_merge *candidate = use_pseudo_merge(pm, &pm->v[i]);
775 if (!candidate || candidate->satisfied)
776 continue;
777 if (!bitmap_equals_ewah(parents, candidate->commits))
778 continue;
779
780 match = candidate;
781 match->satisfied = 1;
782 break;
783 }
784
785 return match;
786}