[PATCH v5 00/10] commit-reach: terminate merge-base walk when one side is exhausted

["Kristofer Karlsson via GitGitGadget" <gitgitgadget@gmail.com>]

Optimize paint_down_to_common() for merge-base queries that hit large
one-sided histories.

When the walk from one side reaches a commit with a very low generation
number that the other side never paints, the walk is forced to drain most of
the graph. A common trigger is a repository import that grafts a separate
history with its own root, but any merge that introduces a low-generation
commit never painted by the other side has the same effect.

A new merge-base candidate can only be discovered when exclusive PARENT1 and
PARENT2 paint meet. This series teaches paint_down_to_common() to stop as
soon as one side has no exclusive commits left in the queue; once one side
is exhausted, no further candidates can appear.

origin/HEAD  o   o  PR HEAD
             |   |
   (import)  o   :
            / \ /
           |   o  merge-base
           |   |
           :   :  (~2.5M commits)
           |   |
import root   main root


In the RFC thread [1], Derrick Stolee provided a criss-cross counterexample
that sharpened the halt condition, and Elijah Newren independently
discovered the same optimization and shared an implementation in PR #2150
[2]. Patch 3 incorporates test cases from Elijah's branch.

This series implements the optimization only after the walk enters the
finite-generation region, where generation ordering guarantees that paint on
visited commits is final.

Patch 2 adds a test_trace2_data_singular helper to test-lib-functions.sh
that reports expected/actual values on assertion failure instead of a silent
grep exit. This was invaluable during development for iterating on step
counts across the series, and should be valuable for repairing tests after
future algorithmic changes. Happy to drop it if it is considered unnecessary
infrastructure.

The final patch removes the commit-date ordering fallback introduced by
091f4cf3 (commit: don't use generation numbers if not needed, 2018-08-30).
With side-exhaustion in place, the fallback is no longer needed for
performance, and removing it ensures the queue is always generation-ordered
regardless of graph version, so every termination condition can rely on a
single ordering invariant. This patch can be dropped if the scope is too
broad for this series.

NOTE: If the final patch is kept, the separate "commit-reach: fix !FIND_ALL
early exit with v1 commit graph" topic becomes unnecessary. Either way, the
two topics conflict trivially and I am happy to reroll whichever lands
second.

Benchmarks

Trace2 step counts are deterministic (measured via trace2_data_intmax added
in patch 5). Wall-clock times are best-of-11 runs.

2.6M-commit monorepo with commit-graph:

                                      steps              wall-clock
merge-base --all  (across import)  2143438 ->      3     3.67s ->    5ms
merge-base --all  (1000 apart)     2692915 ->   1035     4.41s ->    7ms
merge-base --all  (5000 apart)     2692915 ->   6401     4.45s ->   13ms
merge-base --all  (HEAD vs import) 2698872 ->  45960     4.50s ->   79ms
merge-tree        (across import)  2143438 ->      3     4.42s ->   11ms


git.git (88k commits, commit-graph):

                                      steps              wall-clock
merge-base --all v2.0.0 v2.55.0-rc1 72264 ->  44589      110ms ->   68ms
merge-base --all HEAD HEAD~1000      9891 ->   3828       18ms ->   10ms
merge-base --all HEAD HEAD~10000    72303 ->  41487      101ms ->   50ms


CC: Derrick Stolee stolee@gmail.com CC: Elijah Newren newren@gmail.com

[1]
https://lore.kernel.org/git/CAL71e4Ps-2_0+uuZu43N9pFnXBemoAohPs_eyRJf8taXHJPAXQ@mail.gmail.com/T/#u
[2] https://github.com/gitgitgadget/git/pull/2150

Changes since v4:

 * New patch 2/10: added test_trace2_data_singular helper to
   test-lib-functions.sh. Shows expected/actual values on assertion failure
   instead of a silent grep failure. Makes iterating on step counts much
   easier.

 * New patch 6/10: added clock-skew topologies (se-, se2-) that expose
   side-exhaustion bugs when the commit-date ordering fallback fires with a
   v1 commit graph. All topologies use a shared skew_commit helper. Includes
   step count assertions for edge-case tests from patch 3.

 * Folded the nonstale_queue dedup wrapper removal (previously separate
   patch 6/8) into the paint_state introduction in patch 7/10.

 * New patch 10/10: remove the commit-date ordering fallback in
   paint_down_to_common(). The fallback (091cf18e) was a performance
   optimization for v1 commit graphs, but it breaks the generation ordering
   invariant that both the side-exhaustion and single-result optimizations
   depend on. With side-exhaustion in place, the fallback is no longer
   needed. If kept, this supersedes the separate "commit-reach: fix
   !FIND_ALL early exit with v1 commit graph" topic.

Changes since v3:

 * Fixed BUG assertion that was accidentally made unconditional in v3:
   restored the min_generation guard so it only fires when generation-based
   ordering is active.

 * Moved generation cutoff and single-result termination conditions into the
   documentation in patch 1, since they describe existing behavior.

 * Renamed paint_state counter fields for clarity: p1_count ->
   parent1_count, p2_count -> parent2_count, pending_merge_bases ->
   mb_candidate_count. Changed counter types from int to size_t. (Suggested
   by Rene Scharfe.)

Changes since v2:

 * New patch 9/10 (was 8/8): moved the min_generation termination check and
   the last_gen monotonicity assertion into paint_queue_get(), consolidating
   halt conditions. commit_graph_generation() is now called once per
   dequeued commit and shared across all checks.

 * Moved all halt conditions inside paint_queue_get() with the "pop first"
   form: pop, check, then decrement counters. This keeps the optimization
   commit's diff minimal (just inserting the new checks between pop and
   decrement).

 * Shortened the doc comment on paint_queue_get() to describe what it does
   rather than how. Inline comments on each return NULL explain the specific
   halt condition.

 * Replaced the manual commit-graph setup in the step-count test with
   run_all_modes, which now sets GIT_TRACE2_EVENT per mode and produces
   trace-mode-{none,full,half,no-gdat}.txt files.

 * Added a test_paint_down_steps helper for concise 4-mode step assertions
   with diagnostic output on mismatch (prints "expected X, got Y" instead of
   a silent grep failure).

 * Added step-count assertions to the single-walk edge-case tests:
   in_merge_bases_many:self, pending-stale, infinity-both-sides,
   mixed-finite-infinity.

 * Included step counts alongside wall-clock times in the benchmark tables.

Changes since v1:

 * Reordered patches: documentation first (describing the existing
   algorithm), tests before code changes, so they demonstrate passing with
   old logic first.

 * Dropped the ahead_behind decoupling patch. paint_state is now a NEW
   struct alongside nonstale_queue instead of replacing it. ahead_behind()
   is completely untouched.

 * Removed nonstale_queue_put_dedup() and nonstale_queue_get_dedup() (dead
   code after the conversion) in a separate commit.

 * Renamed: struct paint_queue -> paint_state, field pq -> queue,
   paint_count_add/remove -> paint_count_update (single function with signed
   delta parameter).

 * Split the old paint_count_transition (which handled both old and new
   flags in one call) into separate remove/add calls with a signed delta.
   This eliminates the need for the case 0 handler (which tracked "not in
   the queue") and allows an exhaustive switch on (PARENT1 | PARENT2 |
   STALE) that documents all valid flag combinations, with BUG() in default.

 * Added trace2_data_intmax() instrumentation to report the number of
   commits visited per paint walk (separate commit), with step-count
   assertions in tests for deterministic regression detection.

Elijah Newren (1):
  t6600: add test cases for side-exhaustion edge cases

Kristofer Karlsson (9):
  Documentation/technical: add paint-down-to-common doc
  test-lib-functions: improve diagnostic output for trace2 data
    assertions
  t6099, t6600: add side-exhaustion regression tests
  commit-reach: add trace2 instrumentation to paint_down_to_common()
  t6600: add clock-skew topologies and step counts for edge cases
  commit-reach: introduce struct paint_state with per-side counters
  commit-reach: terminate merge-base walk when one paint side is
    exhausted
  commit-reach: move min_generation check into paint_queue_get()
  commit-reach: remove commit-date ordering fallback

 Documentation/Makefile                        |   1 +
 Documentation/technical/meson.build           |   1 +
 .../technical/paint-down-to-common.adoc       | 151 +++++++++
 commit-graph.c                                |  11 -
 commit-graph.h                                |   6 -
 commit-reach.c                                | 152 ++++++---
 t/meson.build                                 |   1 +
 t/t6099-merge-base-side-exhaustion.sh         |  82 +++++
 t/t6600-test-reach.sh                         | 289 +++++++++++++++++-
 t/test-lib-functions.sh                       |  36 +++
 10 files changed, 663 insertions(+), 67 deletions(-)
 create mode 100644 Documentation/technical/paint-down-to-common.adoc
 create mode 100755 t/t6099-merge-base-side-exhaustion.sh


base-commit: e9019fcafe0040228b8631c30f97ae1adb61bcdc
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2149%2Fspkrka%2Fside-exhaust-pr-v5
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2149/spkrka/side-exhaust-pr-v5
Pull-Request: https://github.com/gitgitgadget/git/pull/2149

Range-diff vs v4:

  1:  3efb095b03 !  1:  be00f5aaa1 Documentation/technical: add paint-down-to-common doc
     @@ Documentation/technical/paint-down-to-common.adoc (new)
      +  - PARENT1: reachable from `one`
      +  - PARENT2: reachable from any commit in `twos[]`
      +
     -+The walk uses a priority queue ordered by generation number (falling
     -+back to commit date when generation numbers are unavailable). Each
     -+step dequeues the highest-priority commit (this is when we say a
     -+commit is "visited") and propagates its paint flags to its parents,
     -+enqueuing them if they gained new flags. When a commit receives
     -+both PARENT1 and PARENT2, it is a merge-base candidate. A candidate
     -+gains the STALE flag so its ancestors propagate staleness -- any
     -+deeper common ancestor is necessarily redundant.
     -+
     ++The walk uses a priority queue ordered by generation number
     ++(highest first), breaking ties by commit date. Each step dequeues
     ++the highest-priority commit (this is when we say a commit is
     ++"visited") and propagates its paint flags to its parents, enqueuing
     ++them if they gained new flags. When a commit receives both PARENT1
     ++and PARENT2, it is a merge-base candidate. A candidate gains the
     ++STALE flag so its ancestors propagate staleness -- any deeper common
     ++ancestor is necessarily redundant.
     ++
     ++NOTE: When the commit-graph uses only topological levels (generation
     ++number v1) and the caller passes `min_generation = 0`, a legacy
     ++fallback replaces the generation-ordered comparator with a pure
     ++commit-date comparator. This breaks the ordering invariants
     ++described below -- see <<date-ordering-fallback>>.
     ++
     ++[[generation-regions]]
      +INFINITY and finite generation regions
      +--------------------------------------
      +
     ++The properties in this section assume generation-number ordering (the
     ++default comparator). They do NOT hold when the date-ordering fallback
     ++is active -- see <<date-ordering-fallback>>.
     ++
      +The commit-graph stores a generation number for each commit. Commits
      +not in the commit-graph have generation `GENERATION_NUMBER_INFINITY`. The
      +graph is closed under reachability: if a commit is in the graph, all
     @@ Documentation/technical/paint-down-to-common.adoc (new)
      +
      +Single result
      +~~~~~~~~~~~~~
     -+When only one merge base is needed and the walk is in the
     -+finite-generation region, the first candidate found is necessarily
     -+the highest-generation common ancestor. No remaining commit in the
     -+queue can be a descendant of this candidate (generation ordering
     -+guarantees children are visited first), so it cannot be redundant
     -+and the walk can stop immediately.
     ++When only one merge base is needed, the walk is in the
     ++finite-generation region, and the queue uses generation ordering,
     ++the first candidate found is necessarily the highest-generation
     ++common ancestor. No remaining commit in the queue can be a
     ++descendant of this candidate (generation ordering guarantees
     ++children are visited first), so it cannot be redundant and the walk
     ++can stop immediately.
     ++
     ++This optimization is NOT safe when the date-ordering fallback is
     ++active, because commit-date order can visit a deeper ancestor
     ++before a shallower one -- see <<date-ordering-fallback>>.
     ++
     ++[[date-ordering-fallback]]
     ++Date-ordering fallback
     ++----------------------
     ++
     ++When `min_generation` is zero and the commit-graph does not contain
     ++corrected commit dates (generation number v1, which stores only
     ++topological levels), `paint_down_to_common()` replaces the default
     ++generation-ordered comparator with `compare_commits_by_commit_date`.
     ++
     ++This was introduced as a performance heuristic: topological levels
     ++are coarser than commit dates, so date ordering can reach merge
     ++bases in fewer steps when timestamps are well-behaved. However,
     ++commit dates are not required to be monotonic -- a parent can have
     ++a later date than its child (clock skew, rebases, etc.) -- so the
     ++queue may visit commits out of topological order.
     ++
     ++This disables optimizations that depend on generation ordering:
     ++
     ++  1. *Single result*: the first merge-base candidate found may not
     ++     be the shallowest, because a deeper ancestor with a higher
     ++     commit date can be dequeued first.
     ++
     ++  2. *Side-exhaustion* (see subsequent commits): one paint side can
     ++     appear to drain from the queue while commits from that side are
     ++     still waiting with lower dates, causing premature termination.
      +
      +Related documentation
      +---------------------
  -:  ---------- >  2:  143f5e0cc1 test-lib-functions: improve diagnostic output for trace2 data assertions
  2:  1a0154b406 !  3:  eec4a9d926 t6600: add test cases for side-exhaustion edge cases
     @@ t/t6600-test-reach.sh: test_expect_success 'setup' '
      +	pi_x="$(cat pi-X-oid)" &&
      +	git branch -f pi-X-br "$pi_x" &&
      +	git tag pi-X "$pi_x" &&
     -+
       	git commit-graph write --reachable &&
       	mv .git/objects/info/commit-graph commit-graph-full &&
       	chmod u+w commit-graph-full &&
  3:  017bf156c5 !  4:  7f0efe6c73 t6099, t6600: add side-exhaustion regression tests
     @@ t/t6099-merge-base-side-exhaustion.sh (new)
      +'
      +
      +test_done
     -
     - ## t/t6600-test-reach.sh ##
     -@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:infinity-both-sides' '
     - 	test_all_modes get_merge_bases_many
     - '
     - 
     -+test_expect_success 'setup mixed finite/INFINITY topology' '
     -+	# Create a commit outside all saved commit-graph files so it always
     -+	# has INFINITY generation, while its parent (ps-X) is in the graph
     -+	# with a finite generation. Use the ps-* orphan topology so we do
     -+	# not pollute the grid-based rev-list tests.
     -+	git checkout ps-X &&
     -+	test_env GIT_TEST_COMMIT_GRAPH= test_commit pm-INF
     -+'
     -+
     -+test_expect_success 'get_merge_bases_many:mixed-finite-infinity' '
     -+	# One tip (pm-INF) is outside the commit-graph with INFINITY
     -+	# generation; the other (ps-B) is in the graph with finite
     -+	# generation. The walk starts in the INFINITY region and crosses
     -+	# into the finite region where side-exhaustion can fire.
     -+	cat >input <<-\EOF &&
     -+	A:pm-INF
     -+	X:ps-B
     -+	EOF
     -+	{
     -+		echo "get_merge_bases_many(A,X):" &&
     -+		git rev-parse ps-X
     -+	} >expect &&
     -+	test_all_modes get_merge_bases_many
     -+'
     -+
     - test_expect_success 'reduce_heads' '
     - 	cat >input <<-\EOF &&
     - 	X:commit-1-10
  4:  df3b090a2b !  5:  b9fb8bfe26 commit-reach: add trace2 instrumentation to paint_down_to_common()
     @@ t/t6600-test-reach.sh: test_expect_success 'setup' '
      +test_paint_down_steps () {
      +	for mode in none full half no-gdat
      +	do
     -+		test_trace2_data paint_down_to_common steps "$1" \
     -+			<"trace-mode-${mode}.txt" || return 1
     ++		test_trace2_data_singular paint_down_to_common steps "$1" \
     ++			"mode=$mode" <"trace-mode-${mode}.txt" || return 1
      +		shift
      +	done
      +}
     @@ t/t6600-test-reach.sh: test_expect_success 'in_merge_bases_many:self' '
       '
       
       test_expect_success 'is_descendant_of:hit' '
     -@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:pending-stale' '
     - 		echo "get_merge_bases_many(A,X):" &&
     - 		git rev-parse ps-B
     - 	} >expect &&
     --	test_all_modes get_merge_bases_many
     -+	test_all_modes get_merge_bases_many &&
     -+	test_paint_down_steps 6 6 6 6
     - '
     - 
     - test_expect_success 'get_merge_bases_many:infinity-both-sides' '
      @@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:infinity-both-sides' '
     - 		echo "get_merge_bases_many(A,X):" &&
     - 		git rev-parse pi-B
     - 	} >expect &&
     --	test_all_modes get_merge_bases_many
     -+	test_all_modes get_merge_bases_many &&
     -+	test_paint_down_steps 5 5 5 5
     + 	test_all_modes get_merge_bases_many
       '
       
     - test_expect_success 'setup mixed finite/INFINITY topology' '
     -@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:mixed-finite-infinity' '
     - 		echo "get_merge_bases_many(A,X):" &&
     - 		git rev-parse ps-X
     - 	} >expect &&
     --	test_all_modes get_merge_bases_many
     -+	test_all_modes get_merge_bases_many &&
     -+	test_paint_down_steps 3 3 3 3
     -+'
     -+
      +test_expect_success 'merge-base --all commit-walk steps' '
      +	>input &&
      +	git rev-parse commit-9-1 >expect &&
      +	run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
      +	test_paint_down_steps 81 80 81 81
     - '
     - 
     ++'
     ++
       test_expect_success 'reduce_heads' '
     + 	cat >input <<-\EOF &&
     + 	X:commit-1-10
  -:  ---------- >  6:  c6e3cc13f7 t6600: add clock-skew topologies and step counts for edge cases
  5:  fed9f2c368 !  7:  42a75899f2 commit-reach: introduce struct paint_state with per-side counters
     @@ Commit message
          earlier than the old code in some topologies (the popped stale
          commit is never processed), so a few step counts drop by one.
      
     -    The existing nonstale_queue is left in place for ahead_behind().
     +    The existing nonstale_queue is left in place for ahead_behind(),
     +    though nonstale_queue_put_dedup() and nonstale_queue_get_dedup()
     +    became unused and are removed.
      
          Signed-off-by: Kristofer Karlsson <krka@spotify.com>
      
     @@ Documentation/technical/paint-down-to-common.adoc: re-enqueued is bounded by the
         4. Single result: the caller only needs one merge base, one has
      
       ## commit-reach.c ##
     -@@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
     - 	return commit;
     +@@ commit-reach.c: static void clear_nonstale_queue(struct nonstale_queue *queue)
     + 	queue->max_nonstale = NULL;
       }
       
     +-static void nonstale_queue_put_dedup(struct nonstale_queue *queue,
     +-				     struct commit *c)
      +/*
      + * Priority queue with per-side commit counters for paint_down_to_common().
      + * Each non-stale queued commit occupies exactly one bucket: PARENT1-only,
     @@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_q
      +	size_t parent1_count;
      +	size_t parent2_count;
      +	size_t mb_candidate_count;
     ++	int gen_ordered;
      +};
      +
      +static void paint_count_update(struct paint_state *state,
      +			       unsigned flags, int delta)
     -+{
     + {
     +-	if (c->object.flags & ENQUEUED)
     +-		return;
     +-	c->object.flags |= ENQUEUED;
     +-	nonstale_queue_put(queue, c);
      +	switch (flags & (PARENT1 | PARENT2 | STALE)) {
      +	case PARENT1:
      +		state->parent1_count += delta;
     @@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_q
      +	default:
      +		BUG("unexpected paint state");
      +	}
     -+}
     -+
     + }
     + 
     +-static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
      +static void paint_queue_put(struct paint_state *state,
      +			    struct commit *c, unsigned add_flags)
     -+{
     + {
     +-	struct commit *commit = nonstale_queue_get(queue);
      +	unsigned old_flags = c->object.flags;
      +	c->object.flags |= add_flags;
      +
     @@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_q
      +		paint_count_update(state, c->object.flags, 1);
      +	}
      +}
     -+
     + 
     +-	if (commit)
     +-		commit->object.flags &= ~ENQUEUED;
      +static struct commit *paint_queue_get(struct paint_state *state)
      +{
      +	struct commit *commit = prio_queue_get(&state->queue);
     @@ commit-reach.c: static struct commit *nonstale_queue_get_dedup(struct nonstale_q
      +		return NULL;
      +
      +	paint_count_update(state, commit->object.flags, -1);
     -+	return commit;
     -+}
     -+
     - /*
     -  * See Documentation/technical/paint-down-to-common.adoc
     -  *
     + 	return commit;
     + }
     + 
      @@ commit-reach.c: static int paint_down_to_common(struct repository *r,
       				enum merge_base_flags mb_flags,
       				struct commit_list **result)
     @@ commit-reach.c: static int paint_down_to_common(struct repository *r,
      -	struct nonstale_queue queue = {
      -		{ compare_commits_by_gen_then_commit_date }
      +	struct paint_state state = {
     -+		.queue = { compare_commits_by_gen_then_commit_date }
     ++		.queue = { compare_commits_by_gen_then_commit_date },
     ++		.gen_ordered = 1,
       	};
      +	struct commit *commit;
       	int i;
     @@ commit-reach.c: static int paint_down_to_common(struct repository *r,
       	timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
       	struct commit_list **tail = result;
       
     - 	if (!min_generation && !corrected_commit_dates_enabled(r))
     +-	if (!min_generation && !corrected_commit_dates_enabled(r))
      -		queue.pq.compare = compare_commits_by_commit_date;
     ++	if (!min_generation && !corrected_commit_dates_enabled(r)) {
      +		state.queue.compare = compare_commits_by_commit_date;
     ++		state.gen_ordered = 0;
     ++	}
       
       	one->object.flags |= PARENT1;
       	if (!n) {
     @@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:infinity-both-s
       '
       
       test_expect_success 'setup mixed finite/INFINITY topology' '
     +@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all with clock skew returns wrong merge base (
     + 	>input &&
     + 	git rev-parse se2-MB1 >expect &&
     + 	run_all_modes git merge-base --all se2-A se2-B &&
     +-	test_paint_down_steps 8 7 8 8
     ++	test_paint_down_steps 8 6 8 8
     + '
     + 
     + test_expect_success 'reduce_heads' '
  6:  4db485b48a <  -:  ---------- commit-reach: remove unused nonstale_queue dedup wrappers
  7:  4506780649 !  8:  f8f00b7bcc commit-reach: terminate merge-base walk when one paint side is exhausted
     @@ commit-reach.c: static struct commit *paint_queue_get(struct paint_state *state)
      +
      +		/* one side is exhausted */
      +		if ((!state->parent1_count || !state->parent2_count) &&
     ++		    state->gen_ordered &&
      +		    commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
      +			return NULL;
      +	}
     @@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all commit-walk steps'
       	git rev-parse commit-9-1 >expect &&
       	run_all_modes git merge-base --all commit-9-9 commit-9-1 &&
      -	test_paint_down_steps 81 80 81 81
     -+	test_paint_down_steps 81 9 57 10
     ++	test_paint_down_steps 81 9 57 81
       '
       
     - test_expect_success 'reduce_heads' '
     + test_expect_success 'merge-base --all with clock skew and v1 commit-graph (side-exhaustion)' '
  8:  8dd15d44e6 !  9:  b45c302caa commit-reach: move min_generation check into paint_queue_get()
     @@ Commit message
      
       ## commit-reach.c ##
      @@ commit-reach.c: struct paint_state {
     - 	size_t parent1_count;
       	size_t parent2_count;
       	size_t mb_candidate_count;
     + 	int gen_ordered;
      +	timestamp_t min_generation;
      +	timestamp_t last_gen;
       };
     @@ commit-reach.c: static void paint_queue_put(struct paint_state *state,
       	if (!state->mb_candidate_count) {
       		/* only stale entries remain */
      @@ commit-reach.c: static struct commit *paint_queue_get(struct paint_state *state)
     - 
       		/* one side is exhausted */
       		if ((!state->parent1_count || !state->parent2_count) &&
     + 		    state->gen_ordered &&
      -		    commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
      +		    generation < GENERATION_NUMBER_INFINITY)
       			return NULL;
     @@ commit-reach.c: static int paint_down_to_common(struct repository *r,
       
      +	state.min_generation = min_generation;
      +	state.last_gen = GENERATION_NUMBER_INFINITY;
     - 	if (!min_generation && !corrected_commit_dates_enabled(r))
     + 	if (!min_generation && !corrected_commit_dates_enabled(r)) {
       		state.queue.compare = compare_commits_by_commit_date;
     - 
     + 		state.gen_ordered = 0;
      @@ commit-reach.c: static int paint_down_to_common(struct repository *r,
       	while ((commit = paint_queue_get(&state))) {
       		struct commit_list *parents;
  -:  ---------- > 10:  d68972b1d7 commit-reach: remove commit-date ordering fallback

-- 
gitgitgadget