* [PATCH v2 0/2] t9811: reformat and modernize tests
From: Marcelo Machado Lage @ 2026-07-11 16:04 UTC (permalink / raw)
To: git; +Cc: Marcelo Machado Lage
In-Reply-To: <20260702140704.65805-1-marcelomlage@usp.br>
This patch series reformats and modernizes the t9811 tests.
Changes since v1:
- Break long && chains into multiple lines according to how git tests are
written nowadays. This was suggested by Patrick Steinhardt.
- Replace 'test -f' calls by more useful 'test_path_*' helpers as the
second commit in the series.
Marcelo Machado Lage (2):
t9811: break long && chains into multiple lines
t9811: replace 'test -f' and '! test -f' with 'test_path_*'
t/t9811-git-p4-label-import.sh | 34 ++++++++++++++++++++++------------
1 file changed, 22 insertions(+), 12 deletions(-)
Range-diff against v1:
-: ---------- > 1: 0f03c913eb t9811: break long && chains into multiple lines
1: f319f2e6e7 ! 2: 3e590881c3 t9811: replace 'test -f' and '! test -f' with 'test_path_*'
@@ Commit message
Replace the basic shell commands 'test -f', with more modern test
helpers 'test_path_is_file' and 'test_path_is_missing'.
+ These modern helpers emit useful information when the corresponding
+ tests fail, unlike 'test -f' and '! test -f'.
+
+ The occurrences of '! test -f filename' were replaced by
+ 'file_path_is_missing filename', a stronger guarantee equivalent to
+ '! test -e filename'.
+
+ Co-authored-by: Vinicius Lira de Freitas <vinilira@usp.br>
+ Signed-off-by: Vinicius Lira de Freitas <vinilira@usp.br>
+ Signed-off-by: Marcelo Machado Lage <marcelomlage@usp.br>
## t/t9811-git-p4-label-import.sh ##
@@ t/t9811-git-p4-label-import.sh: test_expect_success 'basic p4 labels' '
@@ t/t9811-git-p4-label-import.sh: test_expect_success 'basic p4 labels' '
- ! test -f f2 &&
+ test_path_is_missing f2 &&
git checkout TAG_WITH\$_SHELL_CHAR &&
-- test -f f1 && test -f f2 && test -f file_with_\$metachar &&
-+ test_path_is_file f1 && test_path_is_file f2 && test_path_is_file file_with_\$metachar &&
+- test -f f1 &&
+- test -f f2 &&
+- test -f file_with_\$metachar &&
++ test_path_is_file f1 &&
++ test_path_is_file f2 &&
++ test_path_is_file file_with_\$metachar &&
git show TAG_LONG_LABEL | grep -q "A Label second line"
)
--
2.34.1
^ permalink raw reply
* Re: [PATCH v9 0/4] graph: indent visual roots in graph
From: Pablo Sabater @ 2026-07-11 15:41 UTC (permalink / raw)
To: Mirko Faina, Pablo Sabater
Cc: git, ayu.chandekar, chandrapratap3519, christian.couder, gitster,
jltobler, karthik.188, krka, peff, phillip.wood,
siddharthasthana31
In-Reply-To: <alJOgYmAfGg37hsB@exploit>
On Sat Jul 11, 2026 at 4:15 PM CEST, Mirko Faina wrote:
> On Sat, Jul 11, 2026 at 03:37:49PM +0200, Pablo Sabater wrote:
>> When rendering a graph, if the history contains multiple "visual roots",
>> actual roots or commits that look like roots (i.e. have their parents
>> filtered out) can end up being vertically adjacent to unrelated commits,
>> falsely appearing to be related.
>>
>> A fix for this issue was already attempted [1] a while ago.
>>
>> This series adds indentation to the visual root commits, so they cannot be
>> vertically adjacent anymore making it easier to identify them.
[snip]
>
> Sorry, I know I'm a bit late to the discussion regarding the design,
> but, could we maybe have two different code paths for printing graphs?
> Having the old one as a default and this new one only when we're using
> --oneline (well, --format=reference would benefit too)? As it is now if
> I have multiple one-patch series in sequence the entries are
> unnecessarily indented.
>
> Thanks
No worries :)
Well, I thought that it could become annoying given the scenario of
having too many visual roots one after the other. But I didn't have a
clear way of having that scenario without forcing it.
I think that this solves an ambiguity so it should be the default option
and someone who doesn't want the indentation has to explicitly unset it
maybe with something like '--no-graph-indent'.
Apart from having an option to disable indentation.
We could have the cascading to have a limit or make it zig-zag:
instead of:
A
B
C
D
We could do:
A
B
C
D
This would have its own edge cases like:
A
B
C <- if we zig-zag here C and D become ambiguous, currently we are
D indenting only the last commits (visual roots) here we would have
D to chose between continuing cascading or indenting the first of D.
I'm not so sure if I like the zig-zag solution because we need to think again
if it causes an ambiguity, but I wanted to mention it.
I think we need some more opinions about the design.
Thanks,
Pablo
^ permalink raw reply
* Re: [PATCH v9 0/9] migrate more variables into repo_config_values
From: Pablo Sabater @ 2026-07-11 15:24 UTC (permalink / raw)
To: Tian Yuchen, git; +Cc: cirnovskyv, szeder.dev
In-Reply-To: <20260709161145.13349-1-cat@malon.dev>
On Thu Jul 9, 2026 at 6:11 PM CEST, Tian Yuchen wrote:
> Hi everyone,
>
> This patch series continues the ongoing libification effort by migrating
> a batch of global configuration variables into struct repo_config_values.
>
> What does this series do:
>
> infrastructure & strings (commits 1-6):
> Introduce 'repo_config_values_clear()' to manage the lifecycle
> of heap-allocated configuration strings. This infrastructure is utilized
> to migrate string variables, including 'excludes_file', 'apply' whitespace
> configs, and external programs including 'editor', 'pager', 'askpass'.
>
> enums (commits 7-9):
> Migrate enumerations 'push_default', 'autorebase', and
> 'object_creation_mode'. Care was taken to make these types available
> to the configuration structure without triggering circular header
> dependencies.
>
> RFC:
>
> Commit 3~5. Is it really necessary to migrate _program variables?
> https://lore.kernel.org/git/8e657184-ee0b-453a-9f2d-a98080d3582e@gmail.com/
>
> Commit 6~9. Previous related discussions on 'git_branch_track'.
> https://lore.kernel.org/git/CAD=f0L-mPX+KECUjXk-WBzEbTP7wCa8sB56GySQT0yh9mfUOWw@mail.gmail.com/
>
> Note:
>
> Since a new getter 'repo_excludes_file()' is introduced, as previously
> promised, once it is finally merged into 'master', there will be a patch to
> update and squash the comments.
>
> Similarly, I've noticed that the classification and sorting of variables in
> 'repo_config_values' don't seem to be correct. There will also be a patch
> to fix this, and I think it will form a commit series along with the comment
> patch?
>
> Change since v8:
>
> Fixed a memory leak in pager.c.
>
> Thanks!
>
> Tian Yuchen (9):
> repository: introduce repo_config_values_clear()
> environment: move excludes_file into repo_config_values
> environment: move editor_program into repo_config_values
> environment: move pager_program into repo_config_values
> environment: move askpass_program into repo_config_values
> environment: migrate apply_default_whitespace and
> apply_default_ignorewhitespace
> environment: move push_default into repo_config_values
> environment: move autorebase into repo_config_values
> environment: move object_creation_mode into repo_config_values
>
> apply.c | 20 +++++++-----
> branch.c | 2 +-
> builtin/push.c | 8 ++---
> dir.c | 4 +--
> editor.c | 4 +--
> environment.c | 87 +++++++++++++++++++++++++++++++++++---------------
> environment.h | 75 +++++++++++++++++++++++++++----------------
> object-file.c | 2 +-
> pager.c | 26 +++++++++------
> prompt.c | 3 +-
> remote.c | 2 +-
> repository.c | 1 +
> 12 files changed, 152 insertions(+), 82 deletions(-)
Hi!
I missed a base-commit to easily apply this locally, could we
add one?
Thanks!
Pablo
^ permalink raw reply
* Re: [PATCH v9 0/4] graph: indent visual roots in graph
From: Mirko Faina @ 2026-07-11 14:15 UTC (permalink / raw)
To: Pablo Sabater
Cc: git, ayu.chandekar, chandrapratap3519, christian.couder, gitster,
jltobler, karthik.188, krka, peff, phillip.wood,
siddharthasthana31, Mirko Faina
In-Reply-To: <20260711-ps-pre-commit-indent-v9-0-eab6676e82f7@gmail.com>
On Sat, Jul 11, 2026 at 03:37:49PM +0200, Pablo Sabater wrote:
> When rendering a graph, if the history contains multiple "visual roots",
> actual roots or commits that look like roots (i.e. have their parents
> filtered out) can end up being vertically adjacent to unrelated commits,
> falsely appearing to be related.
>
> A fix for this issue was already attempted [1] a while ago.
>
> This series adds indentation to the visual root commits, so they cannot be
> vertically adjacent anymore making it easier to identify them.
>
> Before indentation:
>
> * A
> * B1
> * B2
> * C1
> * C2
>
> After indentation:
>
> * A
> * B1
> \
> * B2
> * C1
> * C2
>
> Indents the visual root commits that have still commits to show after
> them, and if they have children it connects them with an edge at a new
> row.
>
> If there are multiple visual roots adjacent in history, the indentation
> starts with the second one, avoiding redundant indentation of the first
> one and cascades after the second.
>
> * A
> * B
> * C
> * D1
> * D2
>
> This series first commit is a cleanup that brings a common function
> from t4215 and t6016 to a graph functions file which they both use, so
> the new test file for indentation, t4218, can use it as well.
>
> GitHub CI: https://github.com/pabloosabaterr/git/actions/runs/29154333559
>
> [1]: https://lore.kernel.org/git/xmqqwnwajbuj.fsf@gitster.c.googlers.com/
>
> V8 DIFF:
>
> - Checking if the parents of a commit are NULL is not enough to know if
> the commit is a visual root due to options that filter the commit
> parents but they do not remove them (--author, --grep, etc).
> At graph_is_visual_root_candidate(), iterate the parents and call
> graph_is_interesting() for each of them to know whether they will be
> shown or not.
> - Add a --author and a --grep test.
>
> Signed-off-by: Pablo Sabater <pabloosabaterr@gmail.com>
>
> ---
> Pablo Sabater (4):
> lib-log-graph: move check_graph function
> revision: add next_commit_to_show()
> graph: add a 2 commit buffer for lookahead
> graph: indent visual root in graph
>
> graph.c | 295 +++++++++++++++++
> graph.h | 17 +
> revision.c | 48 ++-
> t/lib-log-graph.sh | 5 +
> t/meson.build | 1 +
> t/t4215-log-skewed-merges.sh | 33 +-
> t/t4218-log-graph-indentation.sh | 514 +++++++++++++++++++++++++++++
> t/t6016-rev-list-graph-simplify-history.sh | 25 +-
> 8 files changed, 893 insertions(+), 45 deletions(-)
Sorry, I know I'm a bit late to the discussion regarding the design,
but, could we maybe have two different code paths for printing graphs?
Having the old one as a default and this new one only when we're using
--oneline (well, --format=reference would benefit too)? As it is now if
I have multiple one-patch series in sequence the entries are
unnecessarily indented.
Thanks
^ permalink raw reply
* Re: [PATCH 1/2] git-subtree: Bail out if we find output from Rust rewrite [and 1 more messages]
From: D. Ben Knoble @ 2026-07-11 13:41 UTC (permalink / raw)
To: Ian Jackson; +Cc: Colin Stagner, git, Johannes Schindelin
In-Reply-To: <27215.27575.968985.583226@chiark.greenend.org.uk>
Hi Ian,
On Thu, Jul 9, 2026 at 5:48 AM Ian Jackson
<ijackson@chiark.greenend.org.uk> wrote:
[snip]
> > On 7/6/26 06:58, Ian Jackson wrote:
> > > Another, bigger, reason is that current git-subtree generates unmarked
> > > subtree merges (ie, without any git-subtree trailers)
> >
> > Subtree merges can be performed without git-subtree, via the `-X
> > subtree` merge strategy option. While the design of RIIR git-subtree is
> > outside the scope of this patch series, this may be worth thinking about
> > in your rewrite.
>
> This is what I'm calling an "unmarked subtree merge". My rewrite is
> not going to support this user behaviour. The problem is that it is
> not possible to reliably determine whetheer something is an unmarked
> subtree merge.
>
> It is possible to guess based on tree similarity, but that's a
> heuristic. It's also possible to guess based on root commits.
> Both of these approaches can go wrong in some cases. I prefer to
> write reliable software, which doesn't guess.
>
> I'll advise against this practice in the documentation, but I'm
> reasonably confident that if a user does this anyway the results won't
> be terrible. The upstream input to an unmarked subtree merge in a
> downstream that has already used my rewrite, will be treated as if it
> were a downstream branch that predates the subtree addition. The
> effect on split (in most cases) is a missing parent relationship,
> which is undesirable but not catastrophic.I've made a note to add a
> test case for this scenario.
>
> Combining manual -X subtree merges with git-subtree --squash merges
> could easily produce quite weird and wrong results in the tree (even
> before anyone tries split, or something). I don't think I can even
> reliably detect this situation after the user has done it, and of
> course since that user is using plain git, I certainly can't prevent
> it. This is another reason why manual use of -X subtree should be
> discouraged.
Just to make sure I understand you (I regularly use -X subtree with
one project): the Rust rewrite won't support -X subtree merges, but we
don't intend to discourage folks from using -X subtree merges in toto,
right? Merely not support a mix of the 2?
^ permalink raw reply
* [PATCH v9 4/4] graph: indent visual root in graph
From: Pablo Sabater @ 2026-07-11 13:37 UTC (permalink / raw)
To: git
Cc: pabloosabaterr, ayu.chandekar, chandrapratap3519,
christian.couder, gitster, jltobler, karthik.188, krka, mroik,
peff, phillip.wood, siddharthasthana31
In-Reply-To: <20260711-ps-pre-commit-indent-v9-0-eab6676e82f7@gmail.com>
When rendering a graph, if the history contains multiple "visual roots",
actual roots or commits that look like roots (i.e. have their parents
filtered out) can end up being vertically adjacent to unrelated commits,
falsely appearing to be related.
A fix for this issue was already attempted [1] a while ago.
This happens because the commits fill the space from left to right and
when a visual root ends, its column becomes free for the following
commit even if they are not related. Once this happens the unrelated
commit is rendered below the visual root. Because there is no special
character or way to identify when a visual root is rendered making the
graph confusing.
By indenting the visual roots when there are still commits to show the
vertical adjacency can be avoided.
Add is_visual_root flag to git_graph making it visible in all graph states,
give graph_update() a new function, graph_is_visual_root() to know if the
current commit is a visual root and set is_visual_root.
The different handled cases are:
- If a visual root has children: similar to GRAPH_PRE_COMMIT state when
octopus merges need space, an edge row needs to be printed to connect
the child with the indented visual root. A new state GRAPH_PRE_ROOT is
needed to connect the child with the visual root:
* child of the visual root
\ GRAPH_PRE_ROOT
* visual root indented
- If a visual root is child-less we can skip GRAPH_PRE_ROOT state and
render the indented commit directly.
* visual root indented
* unrelated commit
- If two or more visual roots are adjacent: by having a lookahead to the
next commit that will be rendered, if the next commit is also a visual
root and we are on a visual root, meaning two visual root adjacent in
the history, the top one can omit the indent, making the one below to
indent only once, if there are more adjacent visual commits, the
indentation will increase for each adjacent one, cascading.
* visual root
* visual root
* visual root
* last commit
Even if the last commit is a root, because there is nothing that will be
rendered below we can omit the indentation on purpose.
[1]: https://lore.kernel.org/git/xmqqwnwajbuj.fsf@gitster.c.googlers.com/
Helped-by: Kristofer Karlsson <krka@spotify.com>
Mentored-by: Karthik Nayak <karthik.188@gmail.com>
Mentored-by: Chandra Pratap <chandrapratap3519@gmail.com>
Signed-off-by: Pablo Sabater <pabloosabaterr@gmail.com>
---
graph.c | 244 +++++++++++++++++++
t/meson.build | 1 +
t/t4218-log-graph-indentation.sh | 514 +++++++++++++++++++++++++++++++++++++++
3 files changed, 759 insertions(+)
diff --git a/graph.c b/graph.c
index 89ebcf7540..087094189f 100644
--- a/graph.c
+++ b/graph.c
@@ -60,12 +60,23 @@ struct column {
* index into column_colors.
*/
unsigned short color;
+ /*
+ * Marks if a commit is a non-first parent of a merge. These columns are
+ * already visually connected to the merge commit and do not need
+ * indentation.
+ *
+ * The first parent is the one that inherits the column and it can need
+ * indentation if turns out to be a visual root and there's still
+ * commits to render.
+ */
+ unsigned int is_merge_parent:1;
};
enum graph_state {
GRAPH_PADDING,
GRAPH_SKIP,
GRAPH_PRE_COMMIT,
+ GRAPH_PRE_ROOT,
GRAPH_COMMIT,
GRAPH_POST_MERGE,
GRAPH_COLLAPSING
@@ -323,6 +334,51 @@ struct git_graph {
*/
struct commit *lookahead[2];
int lookahead_nr;
+
+ /*
+ * If a commit is a visual root, we need to indent it to prevent
+ * unrelated commits from being vertically adjacent to it.
+ */
+ unsigned int is_visual_root:1;
+
+ /*
+ * Indentation increases for each visual root adjacent to another visual
+ * root, making visual root commits indentation cascade.
+ */
+ unsigned int visual_root_depth;
+
+ /*
+ * When a visual root is adjacent to other visual roots, the first one
+ * can avoid indentation and the rest cascades, increasing the indentation
+ * for each one.
+ */
+ unsigned int visual_root_cascade:1;
+
+ /*
+ * Set when the current commit was already present in graph->columns
+ * before being processed.
+ */
+ unsigned int commit_in_columns:1;
+};
+
+struct graph_lookahead_flags {
+
+ /*
+ * Set when there will be a commit after the current one that will be
+ * rendered.
+ */
+ unsigned int is_next_visible:1;
+
+ /*
+ * Set when the next visible commit is candidate to be a visual root.
+ */
+ unsigned int is_next_visual_root:1;
+
+ /*
+ * Set when the next visible commit will be rendered under the current
+ * commit.
+ */
+ unsigned int next_has_column:1;
};
static inline int graph_needs_truncation(struct git_graph *graph, int lane)
@@ -399,6 +455,8 @@ struct git_graph *graph_init(struct rev_info *opt)
graph->lookahead[0] = NULL;
graph->lookahead[1] = NULL;
graph->lookahead_nr = 0;
+ graph->visual_root_depth = 0;
+ graph->visual_root_cascade = 0;
/*
* Start the column color at the maximum value, since we'll
* always increment it for the first commit we output.
@@ -581,6 +639,11 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
struct commit *commit,
int idx)
{
+ /*
+ * Get the initial merge_layout before it's modified to know if this
+ * is a merge.
+ */
+ int initial_merge_layout = graph->merge_layout;
int i = graph_find_new_column_by_commit(graph, commit);
int mapping_idx;
@@ -592,6 +655,7 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
i = graph->num_new_columns++;
graph->new_columns[i].commit = commit;
graph->new_columns[i].color = graph_find_commit_color(graph, commit);
+ graph->new_columns[i].is_merge_parent = 0;
}
if (graph->num_parents > 1 && idx > -1 && graph->merge_layout == -1) {
@@ -630,6 +694,12 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
}
graph->mapping[mapping_idx] = i;
+
+ /*
+ * Mark non-first parents of a merge.
+ */
+ if (graph->num_parents > 1 && initial_merge_layout >= 0 && idx > -1)
+ graph->new_columns[i].is_merge_parent = 1;
}
static void graph_update_columns(struct git_graph *graph)
@@ -721,10 +791,20 @@ static void graph_update_columns(struct git_graph *graph)
if (graph->num_parents == 0)
graph->width += 2;
} else {
+ int j;
graph_insert_into_new_columns(graph, col_commit, -1);
+ /*
+ * This column is not the current commit, but we need to
+ * propagate the flag until the commit is processed.
+ */
+ j = graph_find_new_column_by_commit(graph, col_commit);
+ if (j >= 0 && graph->columns[i].is_merge_parent)
+ graph->new_columns[j].is_merge_parent = 1;
}
}
+ graph->commit_in_columns = is_commit_in_columns;
+
/*
* If graph_max_lanes is set, cap the width
*/
@@ -814,9 +894,113 @@ void graph_push_lookahead(struct git_graph *graph, struct commit *c)
graph->lookahead[graph->lookahead_nr++] = c;
}
+/*
+ * A commit can be a visual root when:
+ *
+ * - It has no parents.
+ *
+ * - It has parents but they are all filtered out and
+ * commit->parents arrives NULL.
+ *
+ * - Its parents are uninteresting.
+ *
+ * - It is not a boundary commit. Boundary commits also have no visible
+ * parents, but they are not selected as visual roots because they cannot
+ * cause the ambiguity of being vertically adjacent because:
+ *
+ * 1. A boundary only appears because an included commit is its child.
+ * Children are always above, and the renderer draws an edge down to
+ * the boundary from that child. Rather than starting a column like a
+ * visual root would do, it inherits its child column.
+ *
+ * 2. Included commits cannot appear below a boundary. Boundaries are
+ * ancestors of the exclusion point; if an included commit were an
+ * ancestor of the boundary it would be excluded and not rendered.
+ * Boundaries therefore always sink to the bottom.
+ */
+static int graph_is_visual_root_candidate(struct commit *c, struct git_graph *graph)
+{
+ struct commit_list *p;
+
+ if (c->object.flags & BOUNDARY)
+ return 0;
+ for (p = c->parents; p; p = p->next)
+ if (graph_is_interesting(graph, p->item))
+ return 0;
+ return 1;
+}
+
+static int graph_is_visual_root(struct git_graph *graph,
+ struct graph_lookahead_flags *flags)
+{
+ /*
+ * This must be only called for the current commit as graph contains
+ * the state for the current commit only.
+ *
+ * To check if a commit is a visual root, call graph_is_visual_root_candidate()
+ * but we won't know if it is really a visual root until we get to the
+ * next commit state.
+ *
+ * The current commit is an actual visual root if it is a candidate and
+ * the commit is not a non-first parent of a merge.
+ *
+ * *
+ * |\
+ * | * <- it is a visual root candidate but it shouldn't be indented
+ * * because it is already connected by an edge.
+ * ^ if commit_in_columns && is_merge_parent means the commit
+ * | was put by a merge and is connected.
+ * |
+ * `-------- if !is_next_visible means we're on the last commit, avoid
+ * indentation unless the one before is a visual root, then
+ * we need to differentiate from the one above.
+ *
+ * If next_has_columns means that the next commit has
+ * already a column, so it will not be rendered below, the
+ * current commit has to act as the last commit and omit
+ * indentation.
+ */
+ return graph_is_visual_root_candidate(graph->commit, graph) &&
+ !(graph->commit_in_columns &&
+ graph->columns[graph->commit_index].is_merge_parent) &&
+ flags->is_next_visible &&
+ (!flags->next_has_column || graph->visual_root_depth > 0);
+}
+
+/*
+ * Peeks the next commits via the lookahead buffer and sets the lookahead flags.
+ */
+static void graph_peek_next_visible(struct git_graph *graph,
+ struct graph_lookahead_flags *flags)
+{
+ flags->is_next_visible = 0;
+ flags->is_next_visual_root = 0;
+ flags->next_has_column = 0;
+
+ if (!graph->lookahead_nr)
+ return;
+
+ flags->is_next_visible = 1;
+ flags->next_has_column =
+ graph_find_new_column_by_commit(graph, graph->lookahead[0]) >= 0;
+
+ if (!graph_is_visual_root_candidate(graph->lookahead[0], graph))
+ return;
+
+ if (graph->lookahead_nr >= 2)
+ flags->is_next_visual_root = 1;
+}
+
+static int graph_needs_pre_root_line(struct git_graph *graph)
+{
+ return graph->commit_in_columns && graph->is_visual_root &&
+ graph->num_columns > 0 && !graph->visual_root_cascade;
+}
+
void graph_update(struct git_graph *graph, struct commit *commit)
{
struct commit_list *parent;
+ struct graph_lookahead_flags flags;
/*
* Set the new commit
@@ -847,6 +1031,23 @@ void graph_update(struct git_graph *graph, struct commit *commit)
*/
graph_update_columns(graph);
+ graph_peek_next_visible(graph, &flags);
+
+ graph->is_visual_root = graph_is_visual_root(graph, &flags);
+
+ if (graph->is_visual_root) {
+ /*
+ * If next is a visual root we can omit the indent for the first
+ * visual root and start cascading.
+ */
+ if (!graph->visual_root_depth && flags.is_next_visual_root)
+ graph->visual_root_cascade = 1;
+ graph->visual_root_depth++;
+ } else {
+ graph->visual_root_depth = 0;
+ graph->visual_root_cascade = 0;
+ }
+
graph->expansion_row = 0;
/*
@@ -864,11 +1065,16 @@ void graph_update(struct git_graph *graph, struct commit *commit)
* room for it. We need to do this only if there is a branch row
* (or more) to the right of this commit.
*
+ * If it is a visual root, we need to print an extra row to
+ * connect the indentation.
+ *
* If there are less than 3 parents, we can immediately print the
* commit line.
*/
if (graph->state != GRAPH_PADDING)
graph->state = GRAPH_SKIP;
+ else if (graph_needs_pre_root_line(graph))
+ graph->state = GRAPH_PRE_ROOT;
else if (graph_needs_pre_commit_line(graph))
graph->state = GRAPH_PRE_COMMIT;
else
@@ -1116,6 +1322,17 @@ static void graph_output_commit_line(struct git_graph *graph, struct graph_line
if (col_commit == graph->commit) {
seen_this = 1;
+ if (graph->is_visual_root) {
+ int depth = graph->visual_root_depth;
+ /*
+ * Each visual column is 2 characters wide.
+ * Omit the indentation for the first visual
+ * root in cascade mode.
+ */
+ int padding = (depth - graph->visual_root_cascade) * 2;
+ graph_line_addchars(line, ' ', padding);
+ graph->width += padding;
+ }
graph_output_commit_char(graph, line);
if (graph_needs_truncation(graph, i)) {
@@ -1487,6 +1704,30 @@ static void graph_output_collapsing_line(struct git_graph *graph, struct graph_l
graph_update_state(graph, GRAPH_PADDING);
}
+static void graph_output_pre_root_line(struct git_graph *graph, struct graph_line *line)
+{
+ /*
+ * This function adds a row before a visual root, to connect the
+ * branch to the indented commit. It must only be called on a
+ * visual root.
+ */
+ if (!graph->is_visual_root)
+ BUG("commit must be a visual root to call pre_root_line");
+
+ for (int i = 0; i < graph->num_columns; i++) {
+ struct column *col = &graph->columns[i];
+ if (col->commit == graph->commit) {
+ graph_line_addch(line, ' ');
+ graph_line_write_column(line, col, '\\');
+ } else {
+ graph_line_write_column(line, col, '|');
+ }
+ graph_line_addch(line, ' ');
+ }
+
+ graph_update_state(graph, GRAPH_COMMIT);
+}
+
int graph_next_line(struct git_graph *graph, struct strbuf *sb)
{
int shown_commit_line = 0;
@@ -1512,6 +1753,9 @@ int graph_next_line(struct git_graph *graph, struct strbuf *sb)
case GRAPH_PRE_COMMIT:
graph_output_pre_commit_line(graph, &line);
break;
+ case GRAPH_PRE_ROOT:
+ graph_output_pre_root_line(graph, &line);
+ break;
case GRAPH_COMMIT:
graph_output_commit_line(graph, &line);
shown_commit_line = 1;
diff --git a/t/meson.build b/t/meson.build
index 7c3c070426..cce5ba71f9 100644
--- a/t/meson.build
+++ b/t/meson.build
@@ -577,6 +577,7 @@ integration_tests = [
't4215-log-skewed-merges.sh',
't4216-log-bloom.sh',
't4217-log-limit.sh',
+ 't4218-log-graph-indentation.sh',
't4219-log-follow-merge.sh',
't4252-am-options.sh',
't4253-am-keep-cr-dos.sh',
diff --git a/t/t4218-log-graph-indentation.sh b/t/t4218-log-graph-indentation.sh
new file mode 100755
index 0000000000..60c7d84af7
--- /dev/null
+++ b/t/t4218-log-graph-indentation.sh
@@ -0,0 +1,514 @@
+#!/bin/sh
+
+test_description='git log --graph visual root indentations'
+
+. ./test-lib.sh
+. "$TEST_DIRECTORY"/lib-log-graph.sh
+
+check_graph_with_description () {
+ cat >expect &&
+ lib_test_cmp_graph --format="%s%ndescription%nsecond-line" "$@"
+}
+
+create_orphan () {
+ git checkout --orphan "$1" &&
+ test_might_fail git rm -rf .
+}
+
+# disable commit-graph topo order to have the graph to render in different
+# ways (used in --first-parent tests to have multiple visual roots while a
+# column is active at the same time).
+unset_commit_graph () {
+ sane_unset GIT_TEST_COMMIT_GRAPH &&
+ rm -f .git/objects/info/commit-graph &&
+ rm -rf .git/objects/info/commit-graphs
+}
+
+test_expect_success 'single root commit is not indented' '
+ create_orphan _1 && test_commit 1_A &&
+ lib_test_check_graph _1 <<-\EOF
+ * 1_A
+ EOF
+'
+
+test_expect_success 'visual root indented before unrelated branch' '
+ create_orphan _2 && test_commit 2_A && test_commit 2_B &&
+ create_orphan _3 && test_commit 3_A &&
+ lib_test_check_graph _2 _3 <<-\EOF
+ * 3_A
+ * 2_B
+ * 2_A
+ EOF
+'
+
+test_expect_success 'visual root indentation with --left-right' '
+ lib_test_check_graph --left-right _2..._3 <<-\EOF
+ > 3_A
+ < 2_B
+ < 2_A
+ EOF
+'
+
+# A better case of why indentation is still needed with '--left-right' flag is
+# that unrelated branches can be on the same side, so it's needed to
+# differentiate visual roots on the same side.
+test_expect_success 'visual root indentation with --left-right having unrelated commits on the same side' '
+ lib_test_check_graph --left-right _2..._3 _1 <<-\EOF
+ > 3_A
+ < 2_B
+ \
+ < 2_A
+ > 1_A
+ EOF
+'
+
+test_expect_success 'visual root indents the description also' '
+ check_graph_with_description _2 _3 <<-\EOF
+ * 3_A
+ description
+ second-line
+ * 2_B
+ | description
+ | second-line
+ * 2_A
+ description
+ second-line
+ EOF
+'
+
+test_expect_success 'indented visual root parent gets connected to its child' '
+ create_orphan _4 && test_commit 4_A && test_commit 4_B &&
+ create_orphan _5 && test_commit 5_A && test_commit 5_B &&
+ lib_test_check_graph _4 _5 <<-\EOF
+ * 5_B
+ \
+ * 5_A
+ * 4_B
+ * 4_A
+ EOF
+'
+
+test_expect_success 'indented visual root parent gets connected to its child with description' '
+ check_graph_with_description _4 _5 <<-\EOF
+ * 5_B
+ | description
+ | second-line
+ \
+ * 5_A
+ description
+ second-line
+ * 4_B
+ | description
+ | second-line
+ * 4_A
+ description
+ second-line
+ EOF
+'
+
+test_expect_success 'visual roots cascade and last root does not' '
+ create_orphan _7 && test_commit 7_A && test_commit 7_B &&
+ create_orphan _8 && test_commit 8_A &&
+ create_orphan _9 && test_commit 9_A &&
+ create_orphan _10 && test_commit 10_A &&
+ lib_test_check_graph _7 _8 _9 _10 <<-\EOF
+ * 10_A
+ * 9_A
+ * 8_A
+ * 7_B
+ * 7_A
+ EOF
+'
+
+test_expect_success 'last root does not cascade' '
+ lib_test_check_graph _8 _9 _10 <<-\EOF
+ * 10_A
+ * 9_A
+ * 8_A
+ EOF
+'
+
+test_expect_success 'merge parents are roots between them but they do not indent' '
+ create_orphan _11 && test_commit 11_A &&
+ create_orphan _12 && test_commit 12_A &&
+ create_orphan _13 && test_commit 13_A &&
+ git checkout _11 &&
+ TREE=$(git write-tree) &&
+ MERGE=$(git commit-tree $TREE -p _11 -p _12 -p _13 -m 11_octopus) &&
+ git reset --hard $MERGE &&
+ lib_test_check_graph _11 <<-\EOF
+ *-. 11_octopus
+ |\ \
+ | | * 13_A
+ | * 12_A
+ * 11_A
+ EOF
+'
+
+# The last parent of a merge can be indented if nothing related to it needs to
+# be rendered after, if it's another visual root, merge parent must not get
+# indented but rather activate cascading.
+test_expect_success 'merge then unrelated visual root and unrelated branch' '
+ create_orphan _16 && test_commit 16_A && test_commit 16_B &&
+ create_orphan _17 && test_commit 17_A &&
+ create_orphan _18 && test_commit 18_A &&
+ create_orphan _19 && test_commit 19_A &&
+ create_orphan _20 && test_commit 20_A &&
+ git checkout _18 &&
+ TREE=$(git write-tree) &&
+ MERGE=$(git commit-tree $TREE -p _18 -p _19 -p _20 -m 18_octopus) &&
+ git reset --hard $MERGE &&
+ lib_test_check_graph _18 _17 _16 <<-\EOF
+ *-. 18_octopus
+ |\ \
+ | | * 20_A
+ | * 19_A
+ * 18_A
+ * 17_A
+ * 16_B
+ * 16_A
+ EOF
+'
+
+# The last commit root does not get indented, if the next thing after the root
+# merge parent is the last commit, indent the merge parent.
+test_expect_success 'merge then unrelated root indents merge parent' '
+ lib_test_check_graph _18 _17 <<-\EOF
+ *-. 18_octopus
+ |\ \
+ | | * 20_A
+ | * 19_A
+ \
+ * 18_A
+ * 17_A
+ EOF
+'
+
+test_expect_success 'merge then unrelated branch indents merge parent' '
+ lib_test_check_graph _18 _16 <<-\EOF
+ *-. 18_octopus
+ |\ \
+ | | * 20_A
+ | * 19_A
+ \
+ * 18_A
+ * 16_B
+ * 16_A
+ EOF
+'
+
+test_expect_success 'two-parent merge of orphans' '
+ create_orphan _21 && test_commit 21_A &&
+ create_orphan _22 && test_commit 22_A &&
+ git checkout _21 &&
+ TREE=$(git write-tree) &&
+ MERGE=$(git commit-tree $TREE -p _21 -p _22 -m 21_merge) &&
+ git reset --hard $MERGE &&
+ lib_test_check_graph _21 <<-\EOF
+ * 21_merge
+ |\
+ | * 22_A
+ * 21_A
+ EOF
+'
+
+test_expect_success 'commit with filtered parent becomes a visual root' '
+ create_orphan _23 &&
+ echo test >other.txt &&
+ git add other.txt &&
+ git commit -m "23_A" &&
+ echo test >foo.txt &&
+ git add foo.txt &&
+ git commit -m "23_B" &&
+ create_orphan _24 &&
+ echo test >foo.txt &&
+ git add foo.txt &&
+ git commit -m "24_A" &&
+ lib_test_check_graph _23 _24 -- foo.txt <<-\EOF
+ * 23_B
+ * 24_A
+ EOF
+'
+
+test_expect_success 'filtered parent cascading edge case' '
+ create_orphan _27 &&
+ echo test >foo.txt &&
+ git add foo.txt &&
+ test_tick &&
+ git commit -m "D (last)" &&
+
+ create_orphan _25 &&
+ echo test >other.txt &&
+ git add other.txt &&
+ test_tick &&
+ git commit -m "C-filtered" &&
+
+ echo test >foo.txt &&
+ git add foo.txt &&
+ test_tick &&
+ git commit -m "B (child of filtered)" &&
+
+ create_orphan _26 &&
+ echo test >foo.txt &&
+ git add foo.txt &&
+ test_tick &&
+ git commit -m "A (visual root)" &&
+
+ lib_test_check_graph _25 _26 _27 -- foo.txt <<-\EOF
+ * A (visual root)
+ * B (child of filtered)
+ * D (last)
+ EOF
+'
+
+test_expect_success 'multiple filtered parents in sequence' '
+ create_orphan _44 &&
+ echo a >other.txt && git add other.txt && git commit -m "44_F" &&
+ echo b >foo.txt && git add foo.txt && git commit -m "44_C" &&
+
+ create_orphan _45 &&
+ echo c >other.txt && git add other.txt && git commit -m "45_F" &&
+ echo d >foo.txt && git add foo.txt && git commit -m "45_C" &&
+
+ create_orphan _46 &&
+ echo e >foo.txt && git add foo.txt && git commit -m "46_A" &&
+
+ lib_test_check_graph _44 _45 _46 -- foo.txt <<-\EOF
+ * 44_C
+ * 45_C
+ * 46_A
+ EOF
+'
+
+# These tests prove why there is no need to have indentation for boundary
+# commits.
+#
+# Boundary commits rather than starting a column they 'inherit' the one of
+# its child so there will always be an edge that connects it removing the
+# ambiguity.
+test_expect_success 'unrelated boundaries are not ambiguous' '
+ create_orphan _28 && test_commit 28_A && test_commit 28_B &&
+ test_commit 28_C &&
+ create_orphan _29 && test_commit 29_A && test_commit 29_B &&
+ lib_test_check_graph --boundary 28_A.._28 29_A.._29 <<-\EOF
+ * 29_B
+ | * 28_C
+ | * 28_B
+ | o 28_A
+ o 29_A
+ EOF
+'
+
+# Same structure as t6016
+test_expect_success 'boundary commits big test' '
+ # 3 commits on branch _30
+ create_orphan _30 &&
+ test_commit 30_A &&
+ test_commit 30_B &&
+ test_commit 30_C &&
+
+ # 2 commits on branch _31, started from 30_A
+ git checkout -b _31 30_A &&
+ test_commit 31_A &&
+ test_commit 31_B &&
+
+ # 2 commits on branch _32, started from 30_B
+ git checkout -b _32 30_B &&
+ test_commit 32_A &&
+ test_commit 32_B &&
+
+ # Octopus merge _31 and _32 into -30
+ git checkout _30 &&
+ git merge _31 _32 -m 30_D &&
+ git tag 30_D &&
+ test_commit 30_E &&
+
+ # More commits on _32, then merge _32 into _30
+ git checkout _32 &&
+ test_commit 32_C &&
+ test_commit 32_D &&
+ git checkout _30 &&
+ git merge -s ours _32 -m 30_F &&
+ git tag 30_F &&
+ test_commit 30_G &&
+ lib_test_check_graph --boundary _30 _31 _32 ^32_C <<-\EOF
+ * 30_G
+ * 30_F
+ |\
+ | * 32_D
+ * | 30_E
+ | |
+ | \
+ *-. \ 30_D
+ |\ \ \
+ | * | | 31_B
+ | * | | 31_A
+ * | | | 30_C
+ o | | | 30_B
+ |/ / /
+ o / / 30_A
+ / /
+ | o 32_C
+ |/
+ o 32_B
+ EOF
+'
+
+# Filter by --first-parent and then forcing the filtered parents to be shown.
+test_expect_success '--first-parent flag with the filtered parents' '
+ (
+ unset_commit_graph &&
+ create_orphan _35 && test_commit 35_A && test_commit 35_B &&
+ create_orphan _36 && test_commit 36_A &&
+ create_orphan _37 && test_commit 37_A &&
+ git checkout _35 &&
+ TREE=$(git write-tree) &&
+ MERGE=$(git commit-tree $TREE -p _35 -p _36 -p _37 -m 35_octopus) &&
+ git reset --hard $MERGE &&
+ lib_test_check_graph --first-parent _35 _36 _37 <<-\EOF
+ * 35_octopus
+ | * 37_A
+ | * 36_A
+ * 35_B
+ * 35_A
+ EOF
+ )
+'
+
+test_expect_success '--first-parent with filtered parents but one has a child' '
+ (
+ unset_commit_graph &&
+ create_orphan _38 && test_commit 38_A && test_commit 38_B &&
+ create_orphan _39 && test_commit 39_A &&
+ create_orphan _40 && test_commit 40_A && test_commit 40_B &&
+ git checkout _38 &&
+ TREE=$(git write-tree) &&
+ MERGE=$(git commit-tree $TREE -p _38 -p _39 -p _40 -m 38_octopus) &&
+ git reset --hard $MERGE &&
+ lib_test_check_graph --first-parent _38 _39 _40 <<-\EOF
+ * 38_octopus
+ | * 40_B
+ | * 40_A
+ | * 39_A
+ * 38_B
+ * 38_A
+ EOF
+ )
+'
+
+test_expect_success '--first-parent with filtered parents but both have children' '
+ (
+ unset_commit_graph &&
+ create_orphan _41 && test_commit 41_A && test_commit 41_B &&
+ create_orphan _42 && test_commit 42_A && test_commit 42_B &&
+ create_orphan _43 && test_commit 43_A && test_commit 43_B &&
+ git checkout _41 &&
+ TREE=$(git write-tree) &&
+ MERGE=$(git commit-tree $TREE -p _41 -p _42 -p _43 -m 41_octopus) &&
+ git reset --hard $MERGE &&
+ lib_test_check_graph --first-parent _41 _42 _43 <<-\EOF
+ * 41_octopus
+ | * 43_B
+ | \
+ | * 43_A
+ | * 42_B
+ | * 42_A
+ * 41_B
+ * 41_A
+ EOF
+ )
+'
+
+test_expect_success 'two unrelated merges' '
+ create_orphan _50 && test_commit 50_A &&
+ git checkout -b _51 &&
+ test_commit 51_A && test_commit 51_B &&
+ git checkout _50 &&
+ git merge --no-ff _51 -m 50_B &&
+
+ create_orphan _52 && test_commit 52_A &&
+ git checkout -b _53 &&
+ test_commit 53_A && test_commit 53_B &&
+ git checkout _52 &&
+ git merge --no-ff _53 -m 52_B &&
+
+ lib_test_check_graph _52 _50 <<-\EOF
+ * 52_B
+ |\
+ | * 53_B
+ | * 53_A
+ |/
+ \
+ * 52_A
+ * 50_B
+ |\
+ | * 51_B
+ | * 51_A
+ |/
+ * 50_A
+ EOF
+'
+
+test_expect_success '--max-count treats the last visible commit as the last commit' '
+ lib_test_check_graph --max-count=2 _8 _9 _10 <<-\EOF
+ * 10_A
+ * 9_A
+ EOF
+'
+
+test_expect_success '--max-count=1 shows a single root without indentation' '
+ lib_test_check_graph --max-count=1 _8 _9 _10 <<-\EOF
+ * 10_A
+ EOF
+'
+
+test_expect_success '--max-count-oldest indents visual roots' '
+ lib_test_check_graph --max-count-oldest=3 _8 _9 _10 <<-\EOF
+ * 10_A
+ * 9_A
+ * 8_A
+ EOF
+'
+
+# when the graph commits are filtered with regex options like --author, the
+# commit parents do not come NULL so it is needed to check if the parents are
+# interesting.
+test_expect_success '--author skipped parent makes a visual root' '
+ create_orphan _55 &&
+ test_tick &&
+ git commit --allow-empty -m 55_A &&
+ create_orphan _54 &&
+ test_tick &&
+ git commit --allow-empty --author="Other <other@example.com>" -m 54_A &&
+ test_tick &&
+ git commit --allow-empty -m 54_B &&
+ test_tick &&
+ git commit --allow-empty -m 54_C &&
+ lib_test_check_graph --author="A U Thor" _54 _55 <<-\EOF
+ * 54_C
+ \
+ * 54_B
+ * 55_A
+ EOF
+'
+
+test_expect_success '--grep skipped parent makes a visual root' '
+ create_orphan _57 &&
+ test_tick &&
+ git commit --allow-empty -m 57_keep_A &&
+ create_orphan _56 &&
+ test_tick &&
+ git commit --allow-empty -m 56_skip &&
+ test_tick &&
+ git commit --allow-empty -m 56_keep_A &&
+ test_tick &&
+ git commit --allow-empty -m 56_keep_B &&
+ lib_test_check_graph --grep=keep _56 _57 <<-\EOF
+ * 56_keep_B
+ \
+ * 56_keep_A
+ * 57_keep_A
+ EOF
+'
+
+test_done
--
2.54.0
^ permalink raw reply related
* [PATCH v9 3/4] graph: add a 2 commit buffer for lookahead
From: Pablo Sabater @ 2026-07-11 13:37 UTC (permalink / raw)
To: git
Cc: pabloosabaterr, ayu.chandekar, chandrapratap3519,
christian.couder, gitster, jltobler, karthik.188, krka, mroik,
peff, phillip.wood, siddharthasthana31
In-Reply-To: <20260711-ps-pre-commit-indent-v9-0-eab6676e82f7@gmail.com>
In a subsequent commit the graph renderer needs to know if the next
commit is a visual root or if it is the last commit to be shown. This
requires peeking 2 commits ahead.
Commits are pre-fetched in get_revision() through next_commit_to_show()
where they are also marked as SHOWN, regardless the source they come
from.
Update graph_is_interesting() so it considers commits inside the
lookahead buffer as interesting as well.
Helped-by: Kristofer Karlsson <krka@spotify.com>
Signed-off-by: Pablo Sabater <pabloosabaterr@gmail.com>
---
graph.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++
graph.h | 17 +++++++++++++++++
revision.c | 18 ++++++++++++++++--
3 files changed, 84 insertions(+), 2 deletions(-)
diff --git a/graph.c b/graph.c
index 842282685f..89ebcf7540 100644
--- a/graph.c
+++ b/graph.c
@@ -315,6 +315,14 @@ struct git_graph {
* diff_output_prefix_callback().
*/
struct strbuf prefix_buf;
+
+ /*
+ * Lookahead buffer: up to 2 pre-fetched commits that will be shown.
+ * Populated by get_revision() so graph_peek_next_visible() can use
+ * actual walk results instead of peeking at rev_info internals.
+ */
+ struct commit *lookahead[2];
+ int lookahead_nr;
};
static inline int graph_needs_truncation(struct git_graph *graph, int lane)
@@ -388,6 +396,9 @@ struct git_graph *graph_init(struct rev_info *opt)
graph->num_columns = 0;
graph->num_new_columns = 0;
graph->mapping_size = 0;
+ graph->lookahead[0] = NULL;
+ graph->lookahead[1] = NULL;
+ graph->lookahead_nr = 0;
/*
* Start the column color at the maximum value, since we'll
* always increment it for the first commit we output.
@@ -456,6 +467,15 @@ static void graph_ensure_capacity(struct git_graph *graph, int num_columns)
*/
static int graph_is_interesting(struct git_graph *graph, struct commit *commit)
{
+ /*
+ * Commits in the lookahead buffer have been pre-fetched by
+ * get_revision() and will be shown in the future. They already have
+ * the SHOWN flag set when they were pre-fetched but the graph still
+ * needs to treat them as interesting parents.
+ */
+ for (int i = 0; i < graph->lookahead_nr; i++)
+ if (graph->lookahead[i] == commit)
+ return 1;
/*
* If revs->boundary is set, commits whose children have
* been shown are always interesting, even if they have the
@@ -763,6 +783,37 @@ static int graph_needs_pre_commit_line(struct git_graph *graph)
graph->expansion_row < graph_num_expansion_rows(graph);
}
+struct commit *graph_pop_lookahead(struct git_graph *graph)
+{
+ struct commit *c;
+
+ if (!graph->lookahead_nr)
+ return NULL;
+
+ c = graph->lookahead[0];
+ if (!c)
+ BUG("lookahead buffer has %d entries but the first one is NULL",
+ graph->lookahead_nr);
+
+ graph->lookahead[0] = graph->lookahead[1];
+ graph->lookahead[1] = NULL;
+ graph->lookahead_nr--;
+ return c;
+}
+
+int graph_get_lookahead_room(struct git_graph *graph)
+{
+ return (int)ARRAY_SIZE(graph->lookahead) - graph->lookahead_nr;
+}
+
+void graph_push_lookahead(struct git_graph *graph, struct commit *c)
+{
+ if (!graph_get_lookahead_room(graph))
+ BUG("pushing into lookahead buffer when it is already full");
+
+ graph->lookahead[graph->lookahead_nr++] = c;
+}
+
void graph_update(struct git_graph *graph, struct commit *commit)
{
struct commit_list *parent;
diff --git a/graph.h b/graph.h
index 3fd1dcb2e9..1193711fb8 100644
--- a/graph.h
+++ b/graph.h
@@ -262,4 +262,21 @@ void graph_show_commit_msg(struct git_graph *graph,
FILE *file,
struct strbuf const *sb);
+/*
+ * Pop the first commit from the graph's lookahead buffer.
+ * Returns NULL if the buffer is empty.
+ */
+struct commit *graph_pop_lookahead(struct git_graph *graph);
+
+/*
+ * Returns how many more commits can be added to the lookahead buffer.
+ */
+int graph_get_lookahead_room(struct git_graph *graph);
+
+/*
+ * Push a commit into the lookahead buffer. Must only be called when
+ * graph_get_lookahead_room() returns > 0.
+ */
+void graph_push_lookahead(struct git_graph *graph, struct commit *c);
+
#endif /* GRAPH_H */
diff --git a/revision.c b/revision.c
index 288935943f..258c3cf782 100644
--- a/revision.c
+++ b/revision.c
@@ -4715,10 +4715,24 @@ struct commit *get_revision(struct rev_info *revs)
return c;
}
- c = next_commit_to_show(revs);
+ if (revs->graph) {
+ c = graph_pop_lookahead(revs->graph);
+ if (!c)
+ c = next_commit_to_show(revs);
+ } else {
+ c = next_commit_to_show(revs);
+ }
- if (c && revs->graph)
+ if (c && revs->graph) {
+ while (graph_get_lookahead_room(revs->graph)) {
+ struct commit *next = next_commit_to_show(revs);
+ if (!next)
+ break;
+ graph_push_lookahead(revs->graph, next);
+ }
graph_update(revs->graph, c);
+ }
+
if (!c) {
free_saved_parents(revs);
commit_list_free(revs->previous_parents);
--
2.54.0
^ permalink raw reply related
* [PATCH v9 2/4] revision: add next_commit_to_show()
From: Pablo Sabater @ 2026-07-11 13:37 UTC (permalink / raw)
To: git
Cc: pabloosabaterr, ayu.chandekar, chandrapratap3519,
christian.couder, gitster, jltobler, karthik.188, krka, mroik,
peff, phillip.wood, siddharthasthana31
In-Reply-To: <20260711-ps-pre-commit-indent-v9-0-eab6676e82f7@gmail.com>
get_revision() gets its commits from two sources depending on the mode:
1. Normally it gets the commits from get_revision_internal().
2. --max-count-oldest which was introduced at bb4ce23284 (revision.c:
implement --max-count-oldest, 2026-05-19) gets the commits by popping
from a saved list at revs->commits marking SHOWN and CHILD_SHOWN on
each popped commit.
Extract the choice logic into a helper, next_commit_to_show(), which
returns the next commit regardless of the source it comes from.
This has no change in behavior. The helper is needed in a subsequent
commit that pre-fetches two commits into a buffer for lookahead purposes
and needs to pre-fetch from the same source.
The --reverse branch keeps its own pop loop. Using the helper for
--reverse would additionally set SHOWN and CHILD_SHOWN which is not
desired and a behavior change.
Signed-off-by: Pablo Sabater <pabloosabaterr@gmail.com>
---
revision.c | 36 ++++++++++++++++++++++++------------
1 file changed, 24 insertions(+), 12 deletions(-)
diff --git a/revision.c b/revision.c
index 0c95edef59..288935943f 100644
--- a/revision.c
+++ b/revision.c
@@ -4658,12 +4658,34 @@ static void retrieve_oldest_commits(struct rev_info *revs,
commit_list_insert(c, queue);
}
+/*
+ * Returns the next commit that will be shown, regardless of whether it comes
+ * directly from the revision walk or from the list saved by the staged output
+ * of --max-count-oldest.
+ */
+static struct commit *next_commit_to_show(struct rev_info *revs)
+{
+ struct commit *c;
+ struct commit_list *p;
+
+ if (!revs->max_count_stage)
+ return get_revision_internal(revs);
+
+ c = pop_commit(&revs->commits);
+ if (c) {
+ c->object.flags |= SHOWN;
+ if (!(c->object.flags & BOUNDARY))
+ for (p = c->parents; p; p = p->next)
+ p->item->object.flags |= CHILD_SHOWN;
+ }
+ return c;
+}
+
struct commit *get_revision(struct rev_info *revs)
{
struct commit *c;
struct commit_list *reversed;
struct commit_list *queue = NULL;
- struct commit_list *p;
if (revs->max_count_type == 1 && !revs->max_count_stage) {
retrieve_oldest_commits(revs, &queue);
@@ -4693,17 +4715,7 @@ struct commit *get_revision(struct rev_info *revs)
return c;
}
- if (revs->max_count_stage) {
- c = pop_commit(&revs->commits);
- if (c) {
- c->object.flags |= SHOWN;
- if (!(c->object.flags & BOUNDARY))
- for (p = c->parents; p; p = p->next)
- p->item->object.flags |= CHILD_SHOWN;
- }
- } else {
- c = get_revision_internal(revs);
- }
+ c = next_commit_to_show(revs);
if (c && revs->graph)
graph_update(revs->graph, c);
--
2.54.0
^ permalink raw reply related
* [PATCH v9 1/4] lib-log-graph: move check_graph function
From: Pablo Sabater @ 2026-07-11 13:37 UTC (permalink / raw)
To: git
Cc: pabloosabaterr, ayu.chandekar, chandrapratap3519,
christian.couder, gitster, jltobler, karthik.188, krka, mroik,
peff, phillip.wood, siddharthasthana31
In-Reply-To: <20260711-ps-pre-commit-indent-v9-0-eab6676e82f7@gmail.com>
check_graph is a function shared in the test files t4215 and t6016 used
to format the output graph, but instead of being in a file called by
both test, the function code is repeated in each file.
Move check_graph to lib-log-graph.sh file which both tests already
import graph functions from, renaming it to lib_test_check_graph.
This function is needed for the following commit which includes graph
tests in a new file and requires check_graph.
Mentored-by: Karthik Nayak <karthik.188@gmail.com>
Mentored-by: Chandra Pratap <chandrapratap3519@gmail.com>
Signed-off-by: Pablo Sabater <pabloosabaterr@gmail.com>
---
t/lib-log-graph.sh | 5 +++++
t/t4215-log-skewed-merges.sh | 33 +++++++++++++-----------------
t/t6016-rev-list-graph-simplify-history.sh | 25 +++++++++-------------
3 files changed, 29 insertions(+), 34 deletions(-)
diff --git a/t/lib-log-graph.sh b/t/lib-log-graph.sh
index bf952ef920..1eae8f60c2 100644
--- a/t/lib-log-graph.sh
+++ b/t/lib-log-graph.sh
@@ -26,3 +26,8 @@ lib_test_cmp_colored_graph () {
test_decode_color <output.colors.raw | sed "s/ *\$//" >output.colors &&
test_cmp expect.colors output.colors
}
+
+lib_test_check_graph () {
+ cat >expect &&
+ lib_test_cmp_graph --format=%s "$@"
+}
diff --git a/t/t4215-log-skewed-merges.sh b/t/t4215-log-skewed-merges.sh
index 1612f05f1b..eebab71039 100755
--- a/t/t4215-log-skewed-merges.sh
+++ b/t/t4215-log-skewed-merges.sh
@@ -5,11 +5,6 @@ test_description='git log --graph of skewed merges'
. ./test-lib.sh
. "$TEST_DIRECTORY"/lib-log-graph.sh
-check_graph () {
- cat >expect &&
- lib_test_cmp_graph --format=%s "$@"
-}
-
test_expect_success 'log --graph with merge fusing with its left and right neighbors' '
git checkout --orphan _p &&
test_commit A &&
@@ -21,7 +16,7 @@ test_expect_success 'log --graph with merge fusing with its left and right neigh
git checkout _p && git merge --no-ff _r -m G &&
git checkout @^^ && git merge --no-ff _p -m H &&
- check_graph <<-\EOF
+ lib_test_check_graph <<-\EOF
* H
|\
| * G
@@ -49,7 +44,7 @@ test_expect_success 'log --graph with left-skewed merge' '
git checkout 0_p && git merge --no-ff 0_s -m 0_G &&
git checkout @^ && git merge --no-ff 0_q 0_r 0_t 0_p -m 0_H &&
- check_graph <<-\EOF
+ lib_test_check_graph <<-\EOF
*-----. 0_H
|\ \ \ \
| | | | * 0_G
@@ -83,7 +78,7 @@ test_expect_success 'log --graph with nested left-skewed merge' '
git checkout 1_p && git merge --no-ff 1_r -m 1_G &&
git checkout @^^ && git merge --no-ff 1_p -m 1_H &&
- check_graph <<-\EOF
+ lib_test_check_graph <<-\EOF
* 1_H
|\
| * 1_G
@@ -115,7 +110,7 @@ test_expect_success 'log --graph with nested left-skewed merge following normal
git checkout -b 2_s @^^ && git merge --no-ff 2_q -m 2_J &&
git checkout 2_p && git merge --no-ff 2_s -m 2_K &&
- check_graph <<-\EOF
+ lib_test_check_graph <<-\EOF
* 2_K
|\
| * 2_J
@@ -151,7 +146,7 @@ test_expect_success 'log --graph with nested right-skewed merge following left-s
git checkout 3_p && git merge --no-ff 3_r -m 3_H &&
git checkout @^^ && git merge --no-ff 3_p -m 3_J &&
- check_graph <<-\EOF
+ lib_test_check_graph <<-\EOF
* 3_J
|\
| * 3_H
@@ -182,7 +177,7 @@ test_expect_success 'log --graph with right-skewed merge following a left-skewed
git merge --no-ff 4_p -m 4_G &&
git checkout @^^ && git merge --no-ff 4_s -m 4_H &&
- check_graph --date-order <<-\EOF
+ lib_test_check_graph --date-order <<-\EOF
* 4_H
|\
| * 4_G
@@ -218,7 +213,7 @@ test_expect_success 'log --graph with octopus merge with column joining its penu
git checkout 5_r &&
git merge --no-ff 5_s -m 5_H &&
- check_graph <<-\EOF
+ lib_test_check_graph <<-\EOF
* 5_H
|\
| *-. 5_G
@@ -257,7 +252,7 @@ test_expect_success 'log --graph with multiple tips' '
git checkout 6_1 &&
git merge --no-ff 6_2 -m 6_I &&
- check_graph 6_1 6_3 6_5 <<-\EOF
+ lib_test_check_graph 6_1 6_3 6_5 <<-\EOF
* 6_I
|\
| | * 6_H
@@ -334,7 +329,7 @@ test_expect_success 'log --graph with multiple tips' '
git checkout -b M_7 7_1 &&
git merge --no-ff 7_2 7_3 -m 7_M4 &&
- check_graph M_1 M_3 M_5 M_7 <<-\EOF
+ lib_test_check_graph M_1 M_3 M_5 M_7 <<-\EOF
* 7_M1
|\
| | * 7_M2
@@ -371,7 +366,7 @@ test_expect_success 'log --graph with multiple tips' '
'
test_expect_success 'log --graph --graph-lane-limit=2 limited to two lanes' '
- check_graph --graph-lane-limit=2 M_7 <<-\EOF
+ lib_test_check_graph --graph-lane-limit=2 M_7 <<-\EOF
*-. 7_M4
|\ \
| | * 7_G
@@ -388,7 +383,7 @@ test_expect_success 'log --graph --graph-lane-limit=2 limited to two lanes' '
'
test_expect_success 'log --graph --graph-lane-limit=1 truncate mid octopus merge' '
- check_graph --graph-lane-limit=1 M_7 <<-\EOF
+ lib_test_check_graph --graph-lane-limit=1 M_7 <<-\EOF
*-~ 7_M4
|\~
| ~ 7_G
@@ -405,7 +400,7 @@ test_expect_success 'log --graph --graph-lane-limit=1 truncate mid octopus merge
'
test_expect_success 'log --graph --graph-lane-limit=3 limited to three lanes' '
- check_graph --graph-lane-limit=3 M_1 M_3 M_5 M_7 <<-\EOF
+ lib_test_check_graph --graph-lane-limit=3 M_1 M_3 M_5 M_7 <<-\EOF
* 7_M1
|\
| | * 7_M2
@@ -441,7 +436,7 @@ test_expect_success 'log --graph --graph-lane-limit=3 limited to three lanes' '
'
test_expect_success 'log --graph --graph-lane-limit=6 check if it only shows first of 3 parent merge' '
- check_graph --graph-lane-limit=6 M_1 M_3 M_5 M_7 <<-\EOF
+ lib_test_check_graph --graph-lane-limit=6 M_1 M_3 M_5 M_7 <<-\EOF
* 7_M1
|\
| | * 7_M2
@@ -478,7 +473,7 @@ test_expect_success 'log --graph --graph-lane-limit=6 check if it only shows fir
'
test_expect_success 'log --graph --graph-lane-limit=7 check if it shows all 3 parent merge' '
- check_graph --graph-lane-limit=7 M_1 M_3 M_5 M_7 <<-\EOF
+ lib_test_check_graph --graph-lane-limit=7 M_1 M_3 M_5 M_7 <<-\EOF
* 7_M1
|\
| | * 7_M2
diff --git a/t/t6016-rev-list-graph-simplify-history.sh b/t/t6016-rev-list-graph-simplify-history.sh
index 54b0a6f5f8..e0d9c3c1ac 100755
--- a/t/t6016-rev-list-graph-simplify-history.sh
+++ b/t/t6016-rev-list-graph-simplify-history.sh
@@ -13,11 +13,6 @@ export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME
. ./test-lib.sh
. "$TEST_DIRECTORY"/lib-log-graph.sh
-check_graph () {
- cat >expect &&
- lib_test_cmp_graph --format=%s "$@"
-}
-
test_expect_success 'set up rev-list --graph test' '
# 3 commits on branch A
test_commit A1 foo.txt &&
@@ -54,7 +49,7 @@ test_expect_success 'set up rev-list --graph test' '
'
test_expect_success '--graph --all' '
- check_graph --all <<-\EOF
+ lib_test_check_graph --all <<-\EOF
* A7
* A6
|\
@@ -82,7 +77,7 @@ test_expect_success '--graph --all' '
# that undecorated merges are interesting, even with --simplify-by-decoration
test_expect_success '--graph --simplify-by-decoration' '
git tag -d A4 &&
- check_graph --all --simplify-by-decoration <<-\EOF
+ lib_test_check_graph --all --simplify-by-decoration <<-\EOF
* A7
* A6
|\
@@ -114,7 +109,7 @@ test_expect_success 'setup: get rid of decorations on B' '
# Graph with branch B simplified away
test_expect_success '--graph --simplify-by-decoration prune branch B' '
- check_graph --simplify-by-decoration --all <<-\EOF
+ lib_test_check_graph --simplify-by-decoration --all <<-\EOF
* A7
* A6
|\
@@ -133,7 +128,7 @@ test_expect_success '--graph --simplify-by-decoration prune branch B' '
'
test_expect_success '--graph --full-history -- bar.txt' '
- check_graph --full-history --all -- bar.txt <<-\EOF
+ lib_test_check_graph --full-history --all -- bar.txt <<-\EOF
* A7
* A6
|\
@@ -148,7 +143,7 @@ test_expect_success '--graph --full-history -- bar.txt' '
'
test_expect_success '--graph --full-history --simplify-merges -- bar.txt' '
- check_graph --full-history --simplify-merges --all -- bar.txt <<-\EOF
+ lib_test_check_graph --full-history --simplify-merges --all -- bar.txt <<-\EOF
* A7
* A6
|\
@@ -161,7 +156,7 @@ test_expect_success '--graph --full-history --simplify-merges -- bar.txt' '
'
test_expect_success '--graph -- bar.txt' '
- check_graph --all -- bar.txt <<-\EOF
+ lib_test_check_graph --all -- bar.txt <<-\EOF
* A7
* A5
* A3
@@ -172,7 +167,7 @@ test_expect_success '--graph -- bar.txt' '
'
test_expect_success '--graph --sparse -- bar.txt' '
- check_graph --sparse --all -- bar.txt <<-\EOF
+ lib_test_check_graph --sparse --all -- bar.txt <<-\EOF
* A7
* A6
* A5
@@ -189,7 +184,7 @@ test_expect_success '--graph --sparse -- bar.txt' '
'
test_expect_success '--graph ^C4' '
- check_graph --all ^C4 <<-\EOF
+ lib_test_check_graph --all ^C4 <<-\EOF
* A7
* A6
* A5
@@ -202,7 +197,7 @@ test_expect_success '--graph ^C4' '
'
test_expect_success '--graph ^C3' '
- check_graph --all ^C3 <<-\EOF
+ lib_test_check_graph --all ^C3 <<-\EOF
* A7
* A6
|\
@@ -220,7 +215,7 @@ test_expect_success '--graph ^C3' '
# that important, but this test depends on it. If the ordering ever changes
# in the code, we'll need to update this test.
test_expect_success '--graph --boundary ^C3' '
- check_graph --boundary --all ^C3 <<-\EOF
+ lib_test_check_graph --boundary --all ^C3 <<-\EOF
* A7
* A6
|\
--
2.54.0
^ permalink raw reply related
* [PATCH v9 0/4] graph: indent visual roots in graph
From: Pablo Sabater @ 2026-07-11 13:37 UTC (permalink / raw)
To: git
Cc: pabloosabaterr, ayu.chandekar, chandrapratap3519,
christian.couder, gitster, jltobler, karthik.188, krka, mroik,
peff, phillip.wood, siddharthasthana31
In-Reply-To: <20260710-ps-pre-commit-indent-v8-0-d3b636463bf4@gmail.com>
When rendering a graph, if the history contains multiple "visual roots",
actual roots or commits that look like roots (i.e. have their parents
filtered out) can end up being vertically adjacent to unrelated commits,
falsely appearing to be related.
A fix for this issue was already attempted [1] a while ago.
This series adds indentation to the visual root commits, so they cannot be
vertically adjacent anymore making it easier to identify them.
Before indentation:
* A
* B1
* B2
* C1
* C2
After indentation:
* A
* B1
\
* B2
* C1
* C2
Indents the visual root commits that have still commits to show after
them, and if they have children it connects them with an edge at a new
row.
If there are multiple visual roots adjacent in history, the indentation
starts with the second one, avoiding redundant indentation of the first
one and cascades after the second.
* A
* B
* C
* D1
* D2
This series first commit is a cleanup that brings a common function
from t4215 and t6016 to a graph functions file which they both use, so
the new test file for indentation, t4218, can use it as well.
GitHub CI: https://github.com/pabloosabaterr/git/actions/runs/29154333559
[1]: https://lore.kernel.org/git/xmqqwnwajbuj.fsf@gitster.c.googlers.com/
V8 DIFF:
- Checking if the parents of a commit are NULL is not enough to know if
the commit is a visual root due to options that filter the commit
parents but they do not remove them (--author, --grep, etc).
At graph_is_visual_root_candidate(), iterate the parents and call
graph_is_interesting() for each of them to know whether they will be
shown or not.
- Add a --author and a --grep test.
Signed-off-by: Pablo Sabater <pabloosabaterr@gmail.com>
---
Pablo Sabater (4):
lib-log-graph: move check_graph function
revision: add next_commit_to_show()
graph: add a 2 commit buffer for lookahead
graph: indent visual root in graph
graph.c | 295 +++++++++++++++++
graph.h | 17 +
revision.c | 48 ++-
t/lib-log-graph.sh | 5 +
t/meson.build | 1 +
t/t4215-log-skewed-merges.sh | 33 +-
t/t4218-log-graph-indentation.sh | 514 +++++++++++++++++++++++++++++
t/t6016-rev-list-graph-simplify-history.sh | 25 +-
8 files changed, 893 insertions(+), 45 deletions(-)
Range-diff versus v8:
1: ce4f6419c2 = 1: 22ab444372 lib-log-graph: move check_graph function
2: 8c7326745e = 2: ebb88c8b29 revision: add next_commit_to_show()
3: f2e895c72b = 3: 0705ee321e graph: add a 2 commit buffer for lookahead
4: 90d5d22344 ! 4: fa2e60fb3f graph: indent visual root in graph
@@ graph.c: void graph_push_lookahead(struct git_graph *graph, struct commit *c)
+ * - It has parents but they are all filtered out and
+ * commit->parents arrives NULL.
+ *
++ * - Its parents are uninteresting.
++ *
+ * - It is not a boundary commit. Boundary commits also have no visible
+ * parents, but they are not selected as visual roots because they cannot
+ * cause the ambiguity of being vertically adjacent because:
@@ graph.c: void graph_push_lookahead(struct git_graph *graph, struct commit *c)
+ * ancestor of the boundary it would be excluded and not rendered.
+ * Boundaries therefore always sink to the bottom.
+ */
-+static int graph_is_visual_root_candidate(struct commit *c)
++static int graph_is_visual_root_candidate(struct commit *c, struct git_graph *graph)
+{
-+ return c->parents == NULL && !(c->object.flags & BOUNDARY);
++ struct commit_list *p;
++
++ if (c->object.flags & BOUNDARY)
++ return 0;
++ for (p = c->parents; p; p = p->next)
++ if (graph_is_interesting(graph, p->item))
++ return 0;
++ return 1;
+}
+
+static int graph_is_visual_root(struct git_graph *graph,
@@ graph.c: void graph_push_lookahead(struct git_graph *graph, struct commit *c)
+ * current commit has to act as the last commit and omit
+ * indentation.
+ */
-+ return graph_is_visual_root_candidate(graph->commit) &&
++ return graph_is_visual_root_candidate(graph->commit, graph) &&
+ !(graph->commit_in_columns &&
+ graph->columns[graph->commit_index].is_merge_parent) &&
+ flags->is_next_visible &&
@@ graph.c: void graph_push_lookahead(struct git_graph *graph, struct commit *c)
+ flags->next_has_column =
+ graph_find_new_column_by_commit(graph, graph->lookahead[0]) >= 0;
+
-+ if (!graph_is_visual_root_candidate(graph->lookahead[0]))
++ if (!graph_is_visual_root_candidate(graph->lookahead[0], graph))
+ return;
+
+ if (graph->lookahead_nr >= 2)
@@ t/t4218-log-graph-indentation.sh (new)
+ EOF
+'
+
++# when the graph commits are filtered with regex options like --author, the
++# commit parents do not come NULL so it is needed to check if the parents are
++# interesting.
++test_expect_success '--author skipped parent makes a visual root' '
++ create_orphan _55 &&
++ test_tick &&
++ git commit --allow-empty -m 55_A &&
++ create_orphan _54 &&
++ test_tick &&
++ git commit --allow-empty --author="Other <other@example.com>" -m 54_A &&
++ test_tick &&
++ git commit --allow-empty -m 54_B &&
++ test_tick &&
++ git commit --allow-empty -m 54_C &&
++ lib_test_check_graph --author="A U Thor" _54 _55 <<-\EOF
++ * 54_C
++ \
++ * 54_B
++ * 55_A
++ EOF
++'
++
++test_expect_success '--grep skipped parent makes a visual root' '
++ create_orphan _57 &&
++ test_tick &&
++ git commit --allow-empty -m 57_keep_A &&
++ create_orphan _56 &&
++ test_tick &&
++ git commit --allow-empty -m 56_skip &&
++ test_tick &&
++ git commit --allow-empty -m 56_keep_A &&
++ test_tick &&
++ git commit --allow-empty -m 56_keep_B &&
++ lib_test_check_graph --grep=keep _56 _57 <<-\EOF
++ * 56_keep_B
++ \
++ * 56_keep_A
++ * 57_keep_A
++ EOF
++'
++
+test_done
---
base-commit: f85a7e662054a7b0d9070e432508831afa214b47
^ permalink raw reply
* [PATCH v6 10/10] commit-reach: remove commit-date ordering fallback
From: Kristofer Karlsson via GitGitGadget @ 2026-07-11 13:27 UTC (permalink / raw)
To: git
Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
René Scharfe, SZEDER Gábor, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v6.git.1783776466.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Remove the fallback that switched paint_down_to_common() from
generation ordering to commit-date ordering when the commit-graph
lacks corrected commit dates (v1 graph with topo levels only).
The fallback was added in 091f4cf3 (commit: don't use generation
numbers if not needed, 2018-08-30) to avoid a performance
regression on the Linux kernel repo where v1 topo levels caused
"git merge-base v4.8 v4.9" to walk 636k commits instead of 167k.
A side branch with a low topo level stayed in the queue behind a
long chain, preventing early STALE propagation.
Side-exhaustion (added in the previous commits) solves this
differently by terminating the walk as soon as one paint side
empties from the queue, preventing the deep walk regardless of
queue ordering. Benchmarks of "git merge-base --all v4.8 v4.9"
on the Linux kernel repo show that side-exhaustion reduces the
step count far below what the date-ordering fallback achieved:
steps time
no graph, baseline: 167,413 3.25 s
v1 graph, baseline: 167,413 0.25 s
v2 graph, baseline: 167,441 0.29 s
v1 graph, this series: 5,725 0.02 s
v2 graph, this series: 3,887 0.01 s
With generation ordering always active, the existing min_generation
check in paint_queue_get() correctly identifies when the walk has
reached the finite generation region. The date ordering fallback
broke this invariant: a commit could have a finite topo level
while the queue was date-ordered, causing the early exit to fire
before all merge bases were found.
Also remove corrected_commit_dates_enabled() from commit-graph.c
which has no remaining callers.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
.../technical/paint-down-to-common.adoc | 51 +++----------------
commit-graph.c | 11 ----
commit-graph.h | 6 ---
commit-reach.c | 15 +++---
t/t6600-test-reach.sh | 23 ++++-----
5 files changed, 21 insertions(+), 85 deletions(-)
diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc
index 7ae9b11529..f9978ff9f0 100644
--- a/Documentation/technical/paint-down-to-common.adoc
+++ b/Documentation/technical/paint-down-to-common.adoc
@@ -44,10 +44,6 @@ ancestor is necessarily redundant.
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
@@ -82,10 +78,12 @@ traversal: children are always visited before their parents. This
means that paint on already-visited commits is final -- no future
traversal step can add paint to them.
-In the INFINITY region, commit-date ordering can violate this: a
-parent with a later date can be visited before a child with an earlier
-date. Paint flags are therefore NOT final at visit time, and a
-commit visited with only one side's paint may later gain the other.
+In the INFINITY region, all commits share the same generation
+value, so the queue breaks ties by commit date. This can violate
+topological ordering: a parent with a later date can be visited
+before a child with an earlier date. Paint flags are therefore
+NOT final at visit time, and a commit visited with only one
+side's paint may later gain the other.
Paint flags are only added, never removed. Since each flag can be set
at most once per commit, the number of times a commit can be
@@ -149,43 +147,6 @@ 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 the commit-graph has generation numbers v1 and no
-generation floor is specified, topological ordering
-(via generation numbers) is disabled. Topological levels are
-correct but unbalanced -- ordering by such generation numbers
-can sometimes cause the walk to detour too far before finding
-merge bases. Commit-date ordering typically reaches them in
-fewer steps -- see this change for more details:
-
- 091f4cf3 (commit: don't use generation numbers if not needed,
- 2018-08-30)
-
-With generation number v2 (corrected commit dates) we have the best
-of both worlds and do not need this fallback.
-
-For v1, `paint_down_to_common()` falls back to pure commit-date
-ordering via `compare_commits_by_commit_date`. Because commit
-dates are not monotonic (clock skew, rebases, etc.), the queue
-may visit commits out of topological order.
-
-This disables the optimizations that depend on generation ordering:
-
- - *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.
-
- - *Side exhaustion*: 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
---------------------
diff --git a/commit-graph.c b/commit-graph.c
index 9dc8bd5eee..10c2cf9023 100644
--- a/commit-graph.c
+++ b/commit-graph.c
@@ -793,17 +793,6 @@ int generation_numbers_enabled(struct repository *r)
return !!first_generation;
}
-int corrected_commit_dates_enabled(struct repository *r)
-{
- struct commit_graph *g;
-
- g = prepare_commit_graph(r);
- if (!g || !g->num_commits)
- return 0;
-
- return g->read_generation_data;
-}
-
struct bloom_filter_settings *get_bloom_filter_settings(struct repository *r)
{
struct commit_graph *g;
diff --git a/commit-graph.h b/commit-graph.h
index 13ca4ff010..d96147a07c 100644
--- a/commit-graph.h
+++ b/commit-graph.h
@@ -136,12 +136,6 @@ struct commit_graph *parse_commit_graph(struct repository *r,
*/
int generation_numbers_enabled(struct repository *r);
-/*
- * Return 1 if and only if the repository has a commit-graph
- * file and generation data chunk has been written for the file.
- */
-int corrected_commit_dates_enabled(struct repository *r);
-
struct bloom_filter_settings *get_bloom_filter_settings(struct repository *r);
enum commit_graph_write_flags {
diff --git a/commit-reach.c b/commit-reach.c
index 8f6c810e4f..9e491a97fd 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -89,7 +89,6 @@ 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;
};
@@ -166,7 +165,6 @@ static struct commit *paint_queue_get(struct paint_state *state)
/* one side is exhausted */
if ((!state->parent1_count || !state->parent2_count) &&
- state->gen_ordered &&
generation < GENERATION_NUMBER_INFINITY)
return NULL;
}
@@ -187,9 +185,13 @@ static int paint_down_to_common(struct repository *r,
enum merge_base_flags mb_flags,
struct commit_list **result)
{
+ /*
+ * Generation ordering is required for the side-exhaustion and
+ * single-result early exits, which rely on topological traversal
+ * order (children visited before parents) in the finite region.
+ */
struct paint_state state = {
- .queue = { compare_commits_by_gen_then_commit_date },
- .gen_ordered = 1,
+ .queue = { compare_commits_by_gen_then_commit_date }
};
struct commit *commit;
int i;
@@ -198,10 +200,6 @@ 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)) {
- state.queue.compare = compare_commits_by_commit_date;
- state.gen_ordered = 0;
- }
one->object.flags |= PARENT1;
if (!n) {
@@ -229,7 +227,6 @@ static int paint_down_to_common(struct repository *r,
* descendant of this one.
*/
if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
- state.gen_ordered &&
state.last_gen < GENERATION_NUMBER_INFINITY)
break;
}
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 6bf17cb7b6..445449a458 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -381,7 +381,7 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
git rev-parse pi-B
} >expect &&
test_all_modes get_merge_bases_many &&
- test_paint_down_steps 5 4 5 5
+ test_paint_down_steps 5 4 5 4
'
test_expect_success 'setup mixed finite/INFINITY topology' '
@@ -414,31 +414,26 @@ 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 9 57 81
+ test_paint_down_steps 81 9 57 37
'
test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '
- # Verify correct merge base under clock skew. se-D (the
- # merge base) has a higher date than its child se-C.
- # Generation ordering ensures se-C is visited before se-D,
- # so P1 paint propagates correctly and se-D is found.
+ # Verify that the merge base is computed correctly even
+ # when commits have non-monotonic commit dates.
>input &&
git rev-parse se-D >expect &&
run_all_modes git merge-base --all se-A se-B &&
- test_paint_down_steps 6 4 6 6
+ test_paint_down_steps 6 4 6 4
'
test_expect_success 'merge-base --all with clock skew and redundant ancestor (side-exhaustion)' '
- # Verify correct merge base when clock skew could cause a
- # too-deep result. MB1 is the correct merge base; MB2 is
- # its ancestor. A reaches MB2 via E (high date) and MB1
- # via C (low date). Generation ordering ensures C is
- # visited before side-exhaustion fires, so MB1 is found
- # and remove_redundant correctly discards MB2.
+ # Verify that the correct merge base is found even when
+ # non-monotonic commit dates could cause a redundant
+ # ancestor to be visited first.
>input &&
git rev-parse se2-MB1 >expect &&
run_all_modes git merge-base --all se2-A se2-B &&
- test_paint_down_steps 8 6 8 8
+ test_paint_down_steps 8 6 8 6
'
test_expect_success 'reduce_heads' '
--
gitgitgadget
^ permalink raw reply related
* [PATCH v6 09/10] commit-reach: move min_generation check into paint_queue_get()
From: Kristofer Karlsson via GitGitGadget @ 2026-07-11 13:27 UTC (permalink / raw)
To: git
Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
René Scharfe, SZEDER Gábor, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v6.git.1783776466.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Consolidate the min_generation termination condition into
paint_queue_get(), alongside the existing stale-entry and
side-exhaustion checks.
Move last_gen into struct paint_state so that
commit_graph_generation() is called exactly once per dequeued commit
and the result is shared across all termination checks and the
monotonicity BUG assertion.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
commit-reach.c | 31 ++++++++++++++++++-------------
1 file changed, 18 insertions(+), 13 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c
index eabd689e52..8f6c810e4f 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -90,6 +90,8 @@ struct paint_state {
size_t parent2_count;
size_t mb_candidate_count;
int gen_ordered;
+ timestamp_t min_generation;
+ timestamp_t last_gen;
};
static void paint_count_update(struct paint_state *state,
@@ -139,11 +141,23 @@ static void paint_queue_put(struct paint_state *state,
static struct commit *paint_queue_get(struct paint_state *state)
{
struct commit *commit = prio_queue_get(&state->queue);
+ timestamp_t generation;
if (!commit)
return NULL;
commit->object.flags &= ~ENQUEUED;
+ generation = commit_graph_generation(commit);
+
+ if (state->min_generation && generation > state->last_gen)
+ BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
+ generation, state->last_gen,
+ oid_to_hex(&commit->object.oid));
+ state->last_gen = generation;
+
+ /* generation cutoff */
+ if (generation < state->min_generation)
+ return NULL;
if (!state->mb_candidate_count) {
/* only stale entries remain */
@@ -153,7 +167,7 @@ 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;
}
@@ -180,9 +194,10 @@ static int paint_down_to_common(struct repository *r,
struct commit *commit;
int i;
int steps = 0;
- timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
struct commit_list **tail = result;
+ state.min_generation = min_generation;
+ state.last_gen = GENERATION_NUMBER_INFINITY;
if (!min_generation && !corrected_commit_dates_enabled(r)) {
state.queue.compare = compare_commits_by_commit_date;
state.gen_ordered = 0;
@@ -201,18 +216,8 @@ static int paint_down_to_common(struct repository *r,
while ((commit = paint_queue_get(&state))) {
struct commit_list *parents;
int flags;
- timestamp_t generation = commit_graph_generation(commit);
steps++;
- if (min_generation && generation > last_gen)
- BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
- generation, last_gen,
- oid_to_hex(&commit->object.oid));
- last_gen = generation;
-
- if (generation < min_generation)
- break;
-
flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
if (flags == (PARENT1 | PARENT2)) {
if (!(commit->object.flags & RESULT)) {
@@ -225,7 +230,7 @@ static int paint_down_to_common(struct repository *r,
*/
if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
state.gen_ordered &&
- generation < GENERATION_NUMBER_INFINITY)
+ state.last_gen < GENERATION_NUMBER_INFINITY)
break;
}
/* Mark parents of a found merge stale */
--
gitgitgadget
^ permalink raw reply related
* [PATCH v6 08/10] commit-reach: terminate merge-base walk when one paint side is exhausted
From: Kristofer Karlsson via GitGitGadget @ 2026-07-11 13:27 UTC (permalink / raw)
To: git
Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
René Scharfe, SZEDER Gábor, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v6.git.1783776466.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add an early termination check to paint_down_to_common() using the
per-side counters introduced earlier. Once the walk enters the
finite-generation region, terminate early when one side's exclusive
count drops to zero -- no new merge-base can form without both paint
sides meeting.
The check also waits for pending_merge_bases to reach zero, ensuring
all merge-base candidates have been dequeued and recorded before
exiting.
The INFINITY gate ensures correctness: commits without a commit-graph
entry have GENERATION_NUMBER_INFINITY and are ordered by commit date,
which is not topologically reliable. The optimization only fires
once the walk enters the finite-generation region where ordering
guarantees hold.
Step counts measured with trace2 on git.git with commit-graph:
merge-base --all v2.0.0 v2.55.0-rc1:
before: 72264 steps after: 44589 steps
merge-base --all v2.55.0-rc1 v2.55.0-rc1~5:
before: 110 steps after: 7 steps
Helped-by: Derrick Stolee <stolee@gmail.com>
Helped-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
.../technical/paint-down-to-common.adoc | 23 ++++++++++++++++++-
commit-reach.c | 18 ++++++++++++---
t/t6600-test-reach.sh | 4 ++--
3 files changed, 39 insertions(+), 6 deletions(-)
diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc
index 3b3f7ac8af..7ae9b11529 100644
--- a/Documentation/technical/paint-down-to-common.adoc
+++ b/Documentation/technical/paint-down-to-common.adoc
@@ -105,6 +105,9 @@ ends when one of the following conditions holds:
4. Single result: the caller only needs one merge base, one has
been found, and the walk has entered the finite-generation
region.
+ 5. Side exhaustion: no pure PARENT1 or pure PARENT2 commits
+ remain in the queue, no pending merge-base candidates exist,
+ and the walk has entered the finite-generation region.
Stale entry condition
~~~~~~~~~~~~~~~~~~~~~
@@ -115,6 +118,20 @@ existing candidates by proving one is an ancestor of another, but
`remove_redundant()` handles that as a post-processing step, so it
is safe to exit early.
+Side-exhaustion condition
+~~~~~~~~~~~~~~~~~~~~~~~~~
+A new merge-base requires commits from both sides to meet. When one
+side's exclusive counter reaches zero and there are no pending
+merge-base candidates, no future traversal step can produce a new
+candidate.
+
+This optimization only activates in the finite-generation region
+where topological ordering holds. In that region, children are
+always visited before parents, so paint flags are final at visit
+time and an exhausted side cannot reappear. In the INFINITY region,
+commit-date ordering can violate this guarantee, so the check is
+skipped.
+
Generation cutoff
~~~~~~~~~~~~~~~~~
Some callers (notably `remove_redundant()`) supply a `min_generation`
@@ -159,12 +176,16 @@ ordering via `compare_commits_by_commit_date`. Because commit
dates are not monotonic (clock skew, rebases, etc.), the queue
may visit commits out of topological order.
-This disables the optimization that depends on generation ordering:
+This disables the optimizations that depend on generation ordering:
- *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.
+ - *Side exhaustion*: 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
---------------------
diff --git a/commit-reach.c b/commit-reach.c
index ed5e935efd..eabd689e52 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -132,6 +132,10 @@ static void paint_queue_put(struct paint_state *state,
}
}
+/*
+ * Dequeue the next commit for the paint walk, or return NULL when
+ * no more merge bases can be discovered.
+ */
static struct commit *paint_queue_get(struct paint_state *state)
{
struct commit *commit = prio_queue_get(&state->queue);
@@ -141,9 +145,17 @@ static struct commit *paint_queue_get(struct paint_state *state)
commit->object.flags &= ~ENQUEUED;
- if (!state->parent1_count && !state->parent2_count &&
- !state->mb_candidate_count)
- return NULL;
+ if (!state->mb_candidate_count) {
+ /* only stale entries remain */
+ if (!state->parent1_count && !state->parent2_count)
+ return NULL;
+
+ /* one side is exhausted */
+ if ((!state->parent1_count || !state->parent2_count) &&
+ state->gen_ordered &&
+ commit_graph_generation(commit) < GENERATION_NUMBER_INFINITY)
+ return NULL;
+ }
paint_count_update(state, commit->object.flags, -1);
return commit;
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index f9895f5fd7..6bf17cb7b6 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -297,7 +297,7 @@ test_expect_success 'in_merge_bases_many:self' '
EOF
echo "in_merge_bases_many(A,X):1" >expect &&
test_all_modes in_merge_bases_many &&
- test_paint_down_steps 45 2 25 3
+ test_paint_down_steps 45 1 25 1
'
test_expect_success 'is_descendant_of:hit' '
@@ -414,7 +414,7 @@ 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_paint_down_steps 81 9 57 81
'
test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '
--
gitgitgadget
^ permalink raw reply related
* [PATCH v6 07/10] commit-reach: introduce struct paint_state with per-side counters
From: Kristofer Karlsson via GitGitGadget @ 2026-07-11 13:27 UTC (permalink / raw)
To: git
Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
René Scharfe, SZEDER Gábor, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v6.git.1783776466.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add a paint_state struct for use by paint_down_to_common() that
wraps a prio_queue with per-side commit counters. Each non-stale
queued commit occupies exactly one counter bucket based on its
paint flags: PARENT1-only, PARENT2-only, or both sides (a pending
merge-base candidate).
The counters are maintained by paint_count_update() which adjusts
the appropriate bucket by a signed delta. An exhaustive switch on
the paint+stale bits documents all valid flag combinations in one
place.
Convert paint_down_to_common() to use paint_state. The loop now
drains the queue via paint_queue_get() which returns NULL when all
counters reach zero, replacing the old pointer-based termination
(max_nonstale). This is equivalent behavior -- both conditions
detect that no non-stale entries remain.
paint_queue_get() uses a "pop first" form: it dequeues a commit,
then checks the counters. This means the loop exits one iteration
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(),
though nonstale_queue_put_dedup() and nonstale_queue_get_dedup()
became unused and are removed.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
.../technical/paint-down-to-common.adoc | 9 +-
commit-reach.c | 103 +++++++++++++-----
t/t6600-test-reach.sh | 6 +-
3 files changed, 82 insertions(+), 36 deletions(-)
diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc
index c203f14455..3b3f7ac8af 100644
--- a/Documentation/technical/paint-down-to-common.adoc
+++ b/Documentation/technical/paint-down-to-common.adoc
@@ -94,15 +94,12 @@ re-enqueued is bounded by the number of flag transitions.
Termination
-----------
-The walk uses a `nonstale_queue` wrapper around `prio_queue` that
-tracks `max_nonstale`: the lowest-priority non-stale commit enqueued
-so far. Once that commit is dequeued, every remaining entry is known
-to be STALE and the loop terminates. Specifically, the main loop
+The walk tracks the number of commits of each type in the queue
+(PARENT1-only, PARENT2-only, pending merge-base). The main loop
ends when one of the following conditions holds:
1. The queue is empty.
- 2. `max_nonstale` has been dequeued, meaning the queue only contains
- STALE entries.
+ 2. The queue contains only stale entries.
3. Generation cutoff: the dequeued commit's generation is below
a caller-supplied `min_generation` threshold.
4. Single result: the caller only needs one merge base, one has
diff --git a/commit-reach.c b/commit-reach.c
index ee1632d724..ed5e935efd 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -79,21 +79,73 @@ 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,
+ * PARENT2-only, or both (a pending merge-base candidate).
+ */
+struct paint_state {
+ struct prio_queue queue;
+ 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;
+ break;
+
+ case PARENT2:
+ state->parent2_count += delta;
+ break;
+
+ case PARENT1 | PARENT2:
+ state->mb_candidate_count += delta;
+ break;
+
+ case PARENT1 | PARENT2 | STALE:
+ break;
+
+ default:
+ BUG("unexpected paint state");
+ }
+}
+
+static void paint_queue_put(struct paint_state *state,
+ struct commit *c, unsigned add_flags)
+{
+ unsigned old_flags = c->object.flags;
+ c->object.flags |= add_flags;
+
+ if (old_flags & ENQUEUED) {
+ paint_count_update(state, old_flags, -1);
+ paint_count_update(state, c->object.flags, 1);
+ } else {
+ c->object.flags |= ENQUEUED;
+ prio_queue_put(&state->queue, c);
+ paint_count_update(state, c->object.flags, 1);
+ }
}
-static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
+static struct commit *paint_queue_get(struct paint_state *state)
{
- struct commit *commit = nonstale_queue_get(queue);
+ struct commit *commit = prio_queue_get(&state->queue);
+
+ if (!commit)
+ return NULL;
+
+ commit->object.flags &= ~ENQUEUED;
+
+ if (!state->parent1_count && !state->parent2_count &&
+ !state->mb_candidate_count)
+ return NULL;
- if (commit)
- commit->object.flags &= ~ENQUEUED;
+ paint_count_update(state, commit->object.flags, -1);
return commit;
}
@@ -109,18 +161,19 @@ static int paint_down_to_common(struct repository *r,
enum merge_base_flags mb_flags,
struct commit_list **result)
{
- struct nonstale_queue queue = {
- { compare_commits_by_gen_then_commit_date }
+ struct paint_state state = {
+ .queue = { compare_commits_by_gen_then_commit_date },
+ .gen_ordered = 1,
};
+ struct commit *commit;
int i;
- int gen_ordered = 1;
int steps = 0;
timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
struct commit_list **tail = result;
if (!min_generation && !corrected_commit_dates_enabled(r)) {
- queue.pq.compare = compare_commits_by_commit_date;
- gen_ordered = 0;
+ state.queue.compare = compare_commits_by_commit_date;
+ state.gen_ordered = 0;
}
one->object.flags |= PARENT1;
@@ -128,15 +181,12 @@ static int paint_down_to_common(struct repository *r,
commit_list_append(one, result);
return 0;
}
- nonstale_queue_put_dedup(&queue, one);
+ paint_queue_put(&state, one, 0);
- for (i = 0; i < n; i++) {
- twos[i]->object.flags |= PARENT2;
- nonstale_queue_put_dedup(&queue, twos[i]);
- }
+ for (i = 0; i < n; i++)
+ paint_queue_put(&state, twos[i], PARENT2);
- while (queue.max_nonstale) {
- struct commit *commit = nonstale_queue_get_dedup(&queue);
+ while ((commit = paint_queue_get(&state))) {
struct commit_list *parents;
int flags;
timestamp_t generation = commit_graph_generation(commit);
@@ -162,7 +212,7 @@ static int paint_down_to_common(struct repository *r,
* descendant of this one.
*/
if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
- gen_ordered &&
+ state.gen_ordered &&
generation < GENERATION_NUMBER_INFINITY)
break;
}
@@ -176,7 +226,7 @@ static int paint_down_to_common(struct repository *r,
if ((p->object.flags & flags) == flags)
continue;
if (repo_parse_commit(r, p)) {
- clear_nonstale_queue(&queue);
+ clear_prio_queue(&state.queue);
commit_list_free(*result);
*result = NULL;
/*
@@ -191,12 +241,11 @@ static int paint_down_to_common(struct repository *r,
return error(_("could not parse commit %s"),
oid_to_hex(&p->object.oid));
}
- p->object.flags |= flags;
- nonstale_queue_put_dedup(&queue, p);
+ paint_queue_put(&state, p, flags);
}
}
- clear_nonstale_queue(&queue);
+ clear_prio_queue(&state.queue);
trace2_data_intmax("paint_down_to_common", r,
"steps", steps);
commit_list_sort_by_date(result);
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 55aa220bb3..f9895f5fd7 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -366,7 +366,7 @@ test_expect_success 'get_merge_bases_many:pending-stale' '
git rev-parse ps-B
} >expect &&
test_all_modes get_merge_bases_many &&
- test_paint_down_steps 6 6 6 6
+ test_paint_down_steps 5 5 5 5
'
test_expect_success 'get_merge_bases_many:infinity-both-sides' '
@@ -381,7 +381,7 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
git rev-parse pi-B
} >expect &&
test_all_modes get_merge_bases_many &&
- test_paint_down_steps 5 5 5 5
+ test_paint_down_steps 5 4 5 5
'
test_expect_success 'setup mixed finite/INFINITY topology' '
@@ -438,7 +438,7 @@ test_expect_success 'merge-base --all with clock skew and redundant ancestor (si
>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' '
--
gitgitgadget
^ permalink raw reply related
* [PATCH v6 06/10] t6600: add clock-skew topologies and step counts for edge cases
From: Kristofer Karlsson via GitGitGadget @ 2026-07-11 13:27 UTC (permalink / raw)
To: git
Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
René Scharfe, SZEDER Gábor, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v6.git.1783776466.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add topologies and tests exercising paint_down_to_common() under
clock skew, where commit-date ordering (v1 commit-graph without
corrected commit dates) violates the topological invariant that
children are dequeued before parents:
- se-*: side-exhaustion fires too early when one paint side fully
drains from the queue while a low-date ancestor on the other
side is still queued
- se2-*: side-exhaustion returns a too-deep merge base because
the correct (closer) base never receives both paint sides
Also add step counts to the edge-case tests from the previous
commit, a mixed finite/INFINITY generation topology exercising
the transition from INFINITY-generation commits to graph-backed
commits, and step counts for the grid-based merge-base test.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
t/t6600-test-reach.sh | 98 ++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 96 insertions(+), 2 deletions(-)
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 45aa26cd44..55aa220bb3 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -140,6 +140,48 @@ test_expect_success 'setup' '
git branch -f pi-X-br "$pi_x" &&
git tag pi-X "$pi_x" &&
+ # Clock-skew topology for side-exhaustion testing.
+ # D is the correct merge base but has a higher committer date
+ # than C (its child). With date ordering, D would be dequeued
+ # before C, causing side-exhaustion to fire too early.
+ # Generation ordering prevents this by visiting children
+ # before parents regardless of dates.
+ #
+ # se-A (date 7000) --> se-C (date 3000) --> se-D (date 5000) --> se-root (date 4000)
+ # se-B (date 6000) --> se-D
+ #
+ se_root=$(skew_commit 4000 se-root) &&
+ se_D=$(skew_commit 5000 se-D -p "$se_root") &&
+ se_C=$(skew_commit 3000 se-C -p "$se_D") &&
+ se_A=$(skew_commit 7000 se-A -p "$se_C") &&
+ se_B=$(skew_commit 6000 se-B -p "$se_D") &&
+ git branch -f se-A "$se_A" &&
+ git branch -f se-B "$se_B" &&
+ git tag se-D "$se_D" &&
+
+ # Clock-skew topology with redundant ancestor for
+ # side-exhaustion testing. MB1 is the correct merge base;
+ # MB2 is its parent. A reaches MB2 via E (high date) and
+ # MB1 via C (low date). B reaches MB1 via D. With date
+ # ordering, side-exhaustion would fire before C is dequeued,
+ # missing MB1. Generation ordering ensures both are found.
+ #
+ # se2-A (date 8000) --> se2-C (date 2000) --> se2-MB1 (date 5000) --> se2-MB2 (date 4000) --> se2-root (date 1000)
+ # se2-A --> se2-E (date 6500) --> se2-MB2
+ # se2-B (date 7000) --> se2-D (date 6000) --> se2-MB1
+ #
+ se2_root=$(skew_commit 1000 se2-root) &&
+ se2_MB2=$(skew_commit 4000 se2-MB2 -p "$se2_root") &&
+ se2_MB1=$(skew_commit 5000 se2-MB1 -p "$se2_MB2") &&
+ se2_C=$(skew_commit 2000 se2-C -p "$se2_MB1") &&
+ se2_D=$(skew_commit 6000 se2-D -p "$se2_MB1") &&
+ se2_E=$(skew_commit 6500 se2-E -p "$se2_MB2") &&
+ se2_A=$(skew_commit 8000 se2-A -p "$se2_C" -p "$se2_E") &&
+ se2_B=$(skew_commit 7000 se2-B -p "$se2_D") &&
+ git branch -f se2-A "$se2_A" &&
+ git branch -f se2-B "$se2_B" &&
+ git tag se2-MB1 "$se2_MB1" &&
+
git commit-graph write --reachable &&
mv .git/objects/info/commit-graph commit-graph-full &&
chmod u+w commit-graph-full &&
@@ -323,7 +365,8 @@ 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' '
@@ -337,7 +380,34 @@ 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_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_paint_down_steps 3 3 3 3
'
test_expect_success 'merge-base --all commit-walk steps' '
@@ -347,6 +417,30 @@ test_expect_success 'merge-base --all commit-walk steps' '
test_paint_down_steps 81 80 81 81
'
+test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '
+ # Verify correct merge base under clock skew. se-D (the
+ # merge base) has a higher date than its child se-C.
+ # Generation ordering ensures se-C is visited before se-D,
+ # so P1 paint propagates correctly and se-D is found.
+ >input &&
+ git rev-parse se-D >expect &&
+ run_all_modes git merge-base --all se-A se-B &&
+ test_paint_down_steps 6 4 6 6
+'
+
+test_expect_success 'merge-base --all with clock skew and redundant ancestor (side-exhaustion)' '
+ # Verify correct merge base when clock skew could cause a
+ # too-deep result. MB1 is the correct merge base; MB2 is
+ # its ancestor. A reaches MB2 via E (high date) and MB1
+ # via C (low date). Generation ordering ensures C is
+ # visited before side-exhaustion fires, so MB1 is found
+ # and remove_redundant correctly discards MB2.
+ >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_expect_success 'reduce_heads' '
cat >input <<-\EOF &&
X:commit-1-10
--
gitgitgadget
^ permalink raw reply related
* [PATCH v6 05/10] commit-reach: add trace2 instrumentation to paint_down_to_common()
From: Kristofer Karlsson via GitGitGadget @ 2026-07-11 13:27 UTC (permalink / raw)
To: git
Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
René Scharfe, SZEDER Gábor, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v6.git.1783776466.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add a step counter and trace2_data_intmax() call so that the number
of commits visited during the paint walk is observable via
GIT_TRACE2_EVENT. This provides a way to measure the impact of
future optimizations without relying on wall-clock benchmarks alone.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
commit-reach.c | 5 +++++
t/t6600-test-reach.sh | 44 ++++++++++++++++++++++++++++++-------------
2 files changed, 36 insertions(+), 13 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c
index 778e11f5d3..ee1632d724 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -11,6 +11,7 @@
#include "tag.h"
#include "commit-reach.h"
#include "ewah/ewok.h"
+#include "trace2.h"
/* Remember to update object flag allocation in object.h */
#define PARENT1 (1u<<16)
@@ -113,6 +114,7 @@ static int paint_down_to_common(struct repository *r,
};
int i;
int gen_ordered = 1;
+ int steps = 0;
timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
struct commit_list **tail = result;
@@ -138,6 +140,7 @@ static int paint_down_to_common(struct repository *r,
struct commit_list *parents;
int flags;
timestamp_t generation = commit_graph_generation(commit);
+ steps++;
if (min_generation && generation > last_gen)
BUG("bad generation skip %"PRItime" > %"PRItime" at %s",
@@ -194,6 +197,8 @@ static int paint_down_to_common(struct repository *r,
}
clear_nonstale_queue(&queue);
+ trace2_data_intmax("paint_down_to_common", r,
+ "steps", steps);
commit_list_sort_by_date(result);
return 0;
}
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 698b831a6e..45aa26cd44 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -153,24 +153,34 @@ test_expect_success 'setup' '
'
run_all_modes () {
- test_when_finished rm -rf .git/objects/info/commit-graph &&
- "$@" <input >actual &&
- test_cmp expect actual &&
- cp commit-graph-full .git/objects/info/commit-graph &&
- "$@" <input >actual &&
- test_cmp expect actual &&
- cp commit-graph-half .git/objects/info/commit-graph &&
- "$@" <input >actual &&
- test_cmp expect actual &&
- cp commit-graph-no-gdat .git/objects/info/commit-graph &&
- "$@" <input >actual &&
- test_cmp expect actual
+ graph=.git/objects/info/commit-graph &&
+ test_when_finished rm -rf "$graph" "${graph}s" &&
+ rm -f trace-mode-*.txt &&
+
+ for mode in none full half no-gdat
+ do
+ rm -rf "$graph" "${graph}s" &&
+ cp "commit-graph-${mode}" "$graph" 2>/dev/null ||
+ true &&
+ GIT_TRACE2_EVENT="$(pwd)/trace-mode-${mode}.txt" \
+ "$@" <input >actual &&
+ test_cmp expect actual || return 1
+ done
}
test_all_modes () {
run_all_modes test-tool reach "$@"
}
+test_paint_down_steps () {
+ for mode in none full half no-gdat
+ do
+ test_trace2_data_singular paint_down_to_common steps "$1" \
+ "mode=$mode" <"trace-mode-${mode}.txt" || return 1
+ shift
+ done
+}
+
test_expect_success 'ref_newer:miss' '
cat >input <<-\EOF &&
A:commit-5-7
@@ -244,7 +254,8 @@ test_expect_success 'in_merge_bases_many:self' '
X:commit-6-8
EOF
echo "in_merge_bases_many(A,X):1" >expect &&
- test_all_modes in_merge_bases_many
+ test_all_modes in_merge_bases_many &&
+ test_paint_down_steps 45 2 25 3
'
test_expect_success 'is_descendant_of:hit' '
@@ -329,6 +340,13 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
test_all_modes get_merge_bases_many
'
+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
--
gitgitgadget
^ permalink raw reply related
* [PATCH v6 04/10] t6099, t6600: add side-exhaustion regression tests
From: Kristofer Karlsson via GitGitGadget @ 2026-07-11 13:27 UTC (permalink / raw)
To: git
Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
René Scharfe, SZEDER Gábor, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v6.git.1783776466.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add t6099 to test the case where multiple merge-base candidates exist
and one is an ancestor of another. This exercises the side-exhaustion
optimization in paint_down_to_common together with the
remove_redundant safety net in get_merge_bases_many_0.
Add a mixed finite/INFINITY test to t6600 where one tip is outside
the commit-graph (INFINITY generation) and the other is inside.
This exercises the region transition: the walk starts in the
INFINITY region where side-exhaustion is disabled, then crosses
into the finite region where it can fire.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
t/meson.build | 1 +
t/t6099-merge-base-side-exhaustion.sh | 82 +++++++++++++++++++++++++++
2 files changed, 83 insertions(+)
create mode 100755 t/t6099-merge-base-side-exhaustion.sh
diff --git a/t/meson.build b/t/meson.build
index 8ae6ab6c5f..1b58a49fa3 100644
--- a/t/meson.build
+++ b/t/meson.build
@@ -793,6 +793,7 @@ integration_tests = [
't6041-bisect-submodule.sh',
't6050-replace.sh',
't6060-merge-index.sh',
+ 't6099-merge-base-side-exhaustion.sh',
't6100-rev-list-in-order.sh',
't6101-rev-parse-parents.sh',
't6102-rev-list-unexpected-objects.sh',
diff --git a/t/t6099-merge-base-side-exhaustion.sh b/t/t6099-merge-base-side-exhaustion.sh
new file mode 100755
index 0000000000..4f1e0d50ef
--- /dev/null
+++ b/t/t6099-merge-base-side-exhaustion.sh
@@ -0,0 +1,82 @@
+#!/bin/sh
+
+test_description='merge-base with ancestor among merge-base candidates
+
+Test that merge-base --all correctly handles cases where
+multiple merge-base candidates exist and one is an ancestor
+of another. The side-exhaustion optimization in
+paint_down_to_common may exit before STALE propagation
+removes the ancestor, but remove_redundant catches it.
+
+Graph shape (parents are below children):
+
+ A ----------- X
+ |\ /|
+ | B---------/ |
+ | | |
+ e2 \ f2
+ | | |
+ e1 d1 f1
+ \ | /
+ \ | /
+ \| /
+ C
+
+A and X are the two tips.
+B and C are both reachable from A and X.
+B reaches C through d1.
+Only B should appear in merge-base --all output.
+'
+
+GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME=main
+export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME
+
+TEST_PASSES_SANITIZE_LEAK=true
+. ./test-lib.sh
+
+test_expect_success 'setup ancestor merge-base candidate' '
+ test_commit C &&
+
+ git checkout -b d-chain HEAD &&
+ test_commit d1 &&
+ test_commit B &&
+
+ git checkout -b e-path C &&
+ test_commit e1 &&
+ test_commit e2 &&
+
+ git checkout -b f-path C &&
+ test_commit f1 &&
+ test_commit f2 &&
+
+ git checkout -b branch-A e-path &&
+ test_merge A B &&
+
+ git checkout -b branch-X f-path &&
+ test_merge X B &&
+
+ git commit-graph write --reachable
+'
+
+test_expect_success 'merge-base --all excludes ancestor candidate' '
+ git rev-parse B >expected &&
+ git merge-base --all A X >actual &&
+ test_cmp expected actual
+'
+
+test_expect_success 'merge-base (single) finds shallowest' '
+ git rev-parse B >expected &&
+ git merge-base A X >actual &&
+ test_cmp expected actual
+'
+
+# Without commit-graph: generation numbers are INFINITY,
+# side-exhaustion optimization does not fire.
+test_expect_success 'merge-base --all without commit-graph' '
+ rm -f .git/objects/info/commit-graph &&
+ git rev-parse B >expected &&
+ git merge-base --all A X >actual &&
+ test_cmp expected actual
+'
+
+test_done
--
gitgitgadget
^ permalink raw reply related
* [PATCH v6 03/10] t6600: add test cases for side-exhaustion edge cases
From: Elijah Newren via GitGitGadget @ 2026-07-11 13:27 UTC (permalink / raw)
To: git
Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
René Scharfe, SZEDER Gábor, Kristofer Karlsson,
Elijah Newren
In-Reply-To: <pull.2149.v6.git.1783776466.gitgitgadget@gmail.com>
From: Elijah Newren <newren@gmail.com>
Add test cases to t6600-test-reach.sh that exercise edge cases in the
side-exhaustion optimization for paint_down_to_common():
- in_merge_bases_many:self: commit is both A and one of the X inputs
- get_merge_bases_many:duplicate-twos: duplicate entries in X list
- get_merge_bases_many:pending-stale: STALE transition on an
already-painted commit (ps-* diamond topology)
- get_merge_bases_many:infinity-both-sides: both tips outside the
commit-graph with non-monotonic dates (pi-* topology)
Signed-off-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
t/t6600-test-reach.sh | 110 ++++++++++++++++++++++++++++++++++++++++++
1 file changed, 110 insertions(+)
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 019fed9f5e..698b831a6e 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -85,6 +85,61 @@ test_expect_success 'setup' '
git branch -f skew-P2 "$skew_P2" &&
git tag skew-M2 "$skew_M2" &&
+ # Build a small side topology to exercise the (PARENT1|PARENT2) ->
+ # (PARENT1|PARENT2|STALE) transition in paint_down_to_common(); the
+ # 10x10 grid above does not exercise it because no merge-base candidate
+ # there is a descendant of another, so STALE never reaches a
+ # still-pending candidate.
+ #
+ # ps-X
+ # /|\
+ # / | \
+ # ps-Z ps-B ps-W
+ # | / \ |
+ # | / \ |
+ # |/ \|
+ # ps-T1 ps-T2
+ #
+ # where ps-T1=merge(ps-Z,ps-B), ps-T2=merge(ps-W,ps-B), so
+ # merge-base(ps-T1,ps-T2) = ps-B. During the walk, ps-X transitions
+ # to (PARENT1|PARENT2) via ps-Z and ps-W before ps-B is dequeued;
+ # then the STALE-walk from ps-B transitions ps-X to
+ # (PARENT1|PARENT2|STALE).
+ git checkout --orphan ps-orphan &&
+ test_commit ps-X &&
+ git checkout -b ps-B-br ps-X && test_commit ps-B &&
+ git checkout -b ps-Z-br ps-X && test_commit ps-Z &&
+ git checkout -b ps-W-br ps-X && test_commit ps-W &&
+ git checkout -b ps-T1 ps-Z &&
+ git merge --no-ff -m ps-T1 ps-B &&
+ git checkout -b ps-T2 ps-W &&
+ git merge --no-ff -m ps-T2 ps-B &&
+
+ # Build a side topology that lives entirely outside the half
+ # commit-graph and has non-monotonic commit dates, to exercise the
+ # INFINITY-gate in paint_down_to_common. With both tips outside
+ # the graph, generation is INFINITY and the queue falls back to
+ # commit-date order, which here is non-monotonic.
+ #
+ # pi-X (date 500, PARENT1 tip) --> pi-P, pi-D
+ # pi-D (date 480) --> pi-C
+ # pi-C (date 200) --> pi-B
+ # pi-B (date 100, PARENT2 tip) --> pi-P
+ # pi-P (date 450, root)
+ #
+ # merge-base(pi-X, pi-B) = pi-B (it is an ancestor of pi-X and is
+ # itself one of the queried tips).
+ git checkout --orphan pi-orphan &&
+ test_commit --date "@450 +0000" pi-P &&
+ test_commit --date "@100 +0000" pi-B &&
+ test_commit --date "@200 +0000" pi-C &&
+ test_commit --date "@480 +0000" pi-D &&
+ GIT_AUTHOR_DATE="@500 +0000" GIT_COMMITTER_DATE="@500 +0000" \
+ git commit-tree -p pi-D -p pi-P -m pi-X pi-D^{tree} >pi-X-oid &&
+ 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 &&
@@ -182,6 +237,16 @@ test_expect_success 'in_merge_bases_many:miss-heuristic' '
test_all_modes in_merge_bases_many
'
+test_expect_success 'in_merge_bases_many:self' '
+ cat >input <<-\EOF &&
+ A:commit-6-8
+ X:commit-5-9
+ X:commit-6-8
+ EOF
+ echo "in_merge_bases_many(A,X):1" >expect &&
+ test_all_modes in_merge_bases_many
+'
+
test_expect_success 'is_descendant_of:hit' '
cat >input <<-\EOF &&
A:commit-5-7
@@ -219,6 +284,51 @@ test_expect_success 'get_merge_bases_many' '
test_all_modes get_merge_bases_many
'
+test_expect_success 'get_merge_bases_many:duplicate-twos' '
+ cat >input <<-\EOF &&
+ A:commit-5-7
+ X:commit-4-8
+ X:commit-4-8
+ X:commit-6-6
+ X:commit-6-6
+ X:commit-8-3
+ EOF
+ {
+ echo "get_merge_bases_many(A,X):" &&
+ git rev-parse commit-5-6 \
+ commit-4-7 | sort
+ } >expect &&
+ test_all_modes get_merge_bases_many
+'
+
+test_expect_success 'get_merge_bases_many:pending-stale' '
+ # Exercises the (PARENT1|PARENT2) -> (...|STALE) transition path in
+ # paint_down_to_common(). See the topology comment in the setup test.
+ cat >input <<-\EOF &&
+ A:ps-T1
+ X:ps-T2
+ EOF
+ {
+ echo "get_merge_bases_many(A,X):" &&
+ git rev-parse ps-B
+ } >expect &&
+ test_all_modes get_merge_bases_many
+'
+
+test_expect_success 'get_merge_bases_many:infinity-both-sides' '
+ # Exercises the push-time INFINITY-gate in paint_down_to_common(). See
+ # the pi-* topology comment in the setup test.
+ cat >input <<-\EOF &&
+ A:pi-X
+ X:pi-B
+ EOF
+ {
+ echo "get_merge_bases_many(A,X):" &&
+ git rev-parse pi-B
+ } >expect &&
+ test_all_modes get_merge_bases_many
+'
+
test_expect_success 'reduce_heads' '
cat >input <<-\EOF &&
X:commit-1-10
--
gitgitgadget
^ permalink raw reply related
* [PATCH v6 02/10] test-lib-functions: improve diagnostic output for trace2 data assertions
From: Kristofer Karlsson via GitGitGadget @ 2026-07-11 13:27 UTC (permalink / raw)
To: git
Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
René Scharfe, SZEDER Gábor, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v6.git.1783776466.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
test_trace2_data is a bare grep that silently exits on failure.
Add a more informative variant that verifies the event appears
exactly once and reports what went wrong: key not found, multiple
entries, or value mismatch. Diagnostics go to FD 4 like test_grep.
Before (value mismatch):
$ test_trace2_data status count/changed 999 <trace2.txt
$ echo $?
1
(no output)
After:
$ test_trace2_data_singular status count/changed 999 <trace2.txt
error: trace2 data 'status/count/changed'
expected: 999
actual: 0
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
t/test-lib-functions.sh | 36 ++++++++++++++++++++++++++++++++++++
1 file changed, 36 insertions(+)
diff --git a/t/test-lib-functions.sh b/t/test-lib-functions.sh
index 809c662124..3521efe5d7 100644
--- a/t/test-lib-functions.sh
+++ b/t/test-lib-functions.sh
@@ -1996,6 +1996,42 @@ test_trace2_data () {
grep -e '"category":"'"$1"'","key":"'"$2"'","value":"'"$3"'"'
}
+# Check that the given trace2 data event has the expected value and
+# appears exactly once. Produces a diagnostic on failure.
+#
+# test_trace2_data_singular <category> <key> <value> [<label>]
+test_trace2_data_singular () {
+ local category="$1" key="$2" expect_val="$3"
+ local label_suffix="${4:+ [$4]}"
+ local kv_pattern='"category":"'"$category"'","key":"'"$key"'","value":"\([^"]*\)"'
+ local actual
+
+ actual=$(sed -n "s|.*${kv_pattern}.*|\1|p") &&
+
+ if test -z "$actual"
+ then
+ echo >&4 "error: trace2 data '$category/$key'$label_suffix not found"
+ return 1
+ fi &&
+
+ case "$actual" in
+ *"
+"*)
+ echo >&4 "error: trace2 data '$category/$key'$label_suffix has multiple entries, expected 1"
+ printf '%s\n' "$actual" | sed 's/^/ actual: /' >&4
+ return 1
+ ;;
+ esac &&
+
+ if test "$actual" != "$expect_val"
+ then
+ echo >&4 "error: trace2 data '$category/$key'$label_suffix"
+ echo >&4 " expected: $expect_val"
+ echo >&4 " actual: $actual"
+ return 1
+ fi
+}
+
# Given a GIT_TRACE2_EVENT log over stdin, writes to stdout a list of URLs
# sent to git-remote-https child processes.
test_remote_https_urls() {
--
gitgitgadget
^ permalink raw reply related
* [PATCH v6 01/10] Documentation/technical: add paint-down-to-common doc
From: Kristofer Karlsson via GitGitGadget @ 2026-07-11 13:27 UTC (permalink / raw)
To: git
Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
René Scharfe, SZEDER Gábor, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.v6.git.1783776466.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Add a technical document describing the paint_down_to_common()
algorithm used for merge-base computation, covering the paint
walk, generation number regions, and termination conditions.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
Documentation/Makefile | 1 +
Documentation/technical/meson.build | 1 +
.../technical/paint-down-to-common.adoc | 175 ++++++++++++++++++
commit-reach.c | 6 +-
4 files changed, 182 insertions(+), 1 deletion(-)
create mode 100644 Documentation/technical/paint-down-to-common.adoc
diff --git a/Documentation/Makefile b/Documentation/Makefile
index 2699f0b24a..f8dea4b395 100644
--- a/Documentation/Makefile
+++ b/Documentation/Makefile
@@ -129,6 +129,7 @@ TECH_DOCS += technical/long-running-process-protocol
TECH_DOCS += technical/multi-pack-index
TECH_DOCS += technical/packfile-uri
TECH_DOCS += technical/pack-heuristics
+TECH_DOCS += technical/paint-down-to-common
TECH_DOCS += technical/parallel-checkout
TECH_DOCS += technical/partial-clone
TECH_DOCS += technical/platform-support
diff --git a/Documentation/technical/meson.build b/Documentation/technical/meson.build
index ec07088c57..9ce11d5e48 100644
--- a/Documentation/technical/meson.build
+++ b/Documentation/technical/meson.build
@@ -18,6 +18,7 @@ articles = [
'multi-pack-index.adoc',
'packfile-uri.adoc',
'pack-heuristics.adoc',
+ 'paint-down-to-common.adoc',
'parallel-checkout.adoc',
'partial-clone.adoc',
'platform-support.adoc',
diff --git a/Documentation/technical/paint-down-to-common.adoc b/Documentation/technical/paint-down-to-common.adoc
new file mode 100644
index 0000000000..c203f14455
--- /dev/null
+++ b/Documentation/technical/paint-down-to-common.adoc
@@ -0,0 +1,175 @@
+Merge-Base Computation and paint_down_to_common()
+==================================================
+
+The function `paint_down_to_common()` in `commit-reach.c` computes merge
+bases by walking the commit graph backwards from two sets of tips and
+finding where their ancestry meets.
+
+Use cases
+---------
+
+Computing merge bases is used in two different ways:
+
+ 1. *Finding all merge bases* (`merge-base --all`, `merge-tree`,
+ `merge`, `rebase`). A merge base is a common ancestor that is
+ not itself an ancestor of another common ancestor.
+
+ 2. *Ancestry checks* (`in_merge_bases`, used by `merge-base
+ --is-ancestor`, `branch -d`, `fetch`). These ask: "is commit A
+ an ancestor of commit B?" If a common ancestor equals one of the
+ inputs, that input is necessarily the only merge base -- no other
+ common ancestor can be both as recent and not an ancestor of it.
+
+Both use cases share the same algorithm and implementation.
+
+Algorithm
+---------
+
+Given a commit `one` and a set of commits `twos[]`, the walk paints
+commits with two colors:
+
+ - PARENT1: reachable from `one`
+ - PARENT2: reachable from any commit in `twos[]`
+
+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.
+
+[[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 its ancestors are
+too. This partitions the commit graph into two regions:
+
+....
+ +---------------------------------------+
+ | INFINITY region |
+ | generation = INFINITY |
+ | queue order: heuristic (commit date) |
+ +---------------------------------------+
+ |
+ v
+ +---------------------------------------+
+ | Finite region |
+ | generation = finite |
+ | queue order: topological |
+ +---------------------------------------+
+....
+
+When the commit-graph is enabled, the INFINITY region is typically
+very small -- it only contains commits added since the last
+commit-graph refresh.
+
+All reachable INFINITY-generation commits are visited before any
+finite-generation commit, because INFINITY is larger than any finite
+value. Once the walk crosses into the finite region, it stays there.
+
+In the finite region, generation ordering guarantees topological
+traversal: children are always visited before their parents. This
+means that paint on already-visited commits is final -- no future
+traversal step can add paint to them.
+
+In the INFINITY region, commit-date ordering can violate this: a
+parent with a later date can be visited before a child with an earlier
+date. Paint flags are therefore NOT final at visit time, and a
+commit visited with only one side's paint may later gain the other.
+
+Paint flags are only added, never removed. Since each flag can be set
+at most once per commit, the number of times a commit can be
+re-enqueued is bounded by the number of flag transitions.
+
+Termination
+-----------
+
+The walk uses a `nonstale_queue` wrapper around `prio_queue` that
+tracks `max_nonstale`: the lowest-priority non-stale commit enqueued
+so far. Once that commit is dequeued, every remaining entry is known
+to be STALE and the loop terminates. Specifically, the main loop
+ends when one of the following conditions holds:
+
+ 1. The queue is empty.
+ 2. `max_nonstale` has been dequeued, meaning the queue only contains
+ STALE entries.
+ 3. Generation cutoff: the dequeued commit's generation is below
+ a caller-supplied `min_generation` threshold.
+ 4. Single result: the caller only needs one merge base, one has
+ been found, and the walk has entered the finite-generation
+ region.
+
+Stale entry condition
+~~~~~~~~~~~~~~~~~~~~~
+Once all queued entries are stale, no new merge-base candidates can
+be discovered -- that requires at least one non-stale commit from
+each side meeting. Continuing the walk could still invalidate
+existing candidates by proving one is an ancestor of another, but
+`remove_redundant()` handles that as a post-processing step, so it
+is safe to exit early.
+
+Generation cutoff
+~~~~~~~~~~~~~~~~~
+Some callers (notably `remove_redundant()`) supply a `min_generation`
+threshold -- the minimum generation of the input commits. No merge
+base can have a generation below this threshold, so the walk
+terminates as soon as it dequeues such a commit.
+
+Single result
+~~~~~~~~~~~~~
+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 the commit-graph has generation numbers v1 and no
+generation floor is specified, topological ordering
+(via generation numbers) is disabled. Topological levels are
+correct but unbalanced -- ordering by such generation numbers
+can sometimes cause the walk to detour too far before finding
+merge bases. Commit-date ordering typically reaches them in
+fewer steps -- see this change for more details:
+
+ 091f4cf3 (commit: don't use generation numbers if not needed,
+ 2018-08-30)
+
+With generation number v2 (corrected commit dates) we have the best
+of both worlds and do not need this fallback.
+
+For v1, `paint_down_to_common()` falls back to pure commit-date
+ordering via `compare_commits_by_commit_date`. Because commit
+dates are not monotonic (clock skew, rebases, etc.), the queue
+may visit commits out of topological order.
+
+This disables the optimization that depends on generation ordering:
+
+ - *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.
+
+Related documentation
+---------------------
+
+ - `Documentation/technical/commit-graph.adoc` -- generation numbers
+ and the reachability closure property.
diff --git a/commit-reach.c b/commit-reach.c
index d7221fe389..778e11f5d3 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -96,7 +96,11 @@ static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
return commit;
}
-/* all input commits in one and twos[] must have been parsed! */
+/*
+ * See Documentation/technical/paint-down-to-common.adoc
+ *
+ * All input commits in one and twos[] must have been parsed!
+ */
static int paint_down_to_common(struct repository *r,
struct commit *one, int n,
struct commit **twos,
--
gitgitgadget
^ permalink raw reply related
* [PATCH v6 00/10] commit-reach: terminate merge-base walk when one side is exhausted
From: Kristofer Karlsson via GitGitGadget @ 2026-07-11 13:27 UTC (permalink / raw)
To: git
Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
René Scharfe, SZEDER Gábor, Kristofer Karlsson
In-Reply-To: <pull.2149.v5.git.1782923832.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.
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
This series is based on next (depends on kk/commit-reach-find-all-fix and
kk/commit-reach-optim) but is expected to merge cleanly once
kk/commit-reach-find-all-fix graduates to master.
[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 v5:
* Rebased on next, which now contains kk/commit-reach-find-all-fix. The
gen_ordered guard from that topic is carried through patches 7-9 via
state.gen_ordered, then removed in patch 10 along with the date-ordering
fallback.
* Minor documentation and test comment improvements.
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 | 154 +++++++++++
commit-graph.c | 11 -
commit-graph.h | 6 -
commit-reach.c | 156 +++++++++---
t/meson.build | 1 +
t/t6099-merge-base-side-exhaustion.sh | 82 ++++++
t/t6600-test-reach.sh | 241 +++++++++++++++++-
t/test-lib-functions.sh | 36 +++
10 files changed, 618 insertions(+), 71 deletions(-)
create mode 100644 Documentation/technical/paint-down-to-common.adoc
create mode 100755 t/t6099-merge-base-side-exhaustion.sh
base-commit: d0cf55ea5485acc255740c5208673122e812dfa4
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2149%2Fspkrka%2Fside-exhaust-pr-v6
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2149/spkrka/side-exhaust-pr-v6
Pull-Request: https://github.com/gitgitgadget/git/pull/2149
Range-diff vs v5:
1: be00f5aaa1 ! 1: 5ef4f08105 Documentation/technical: add paint-down-to-common doc
@@ Documentation/technical/paint-down-to-common.adoc (new)
+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
+--------------------------------------
@@ Documentation/technical/paint-down-to-common.adoc (new)
+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
-+its ancestors are too. This partitions the commit graph into two regions:
++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 its ancestors are
++too. This partitions the commit graph into two regions:
+
+....
+ +---------------------------------------+
@@ Documentation/technical/paint-down-to-common.adoc (new)
+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`.
++When the commit-graph has generation numbers v1 and no
++generation floor is specified, topological ordering
++(via generation numbers) is disabled. Topological levels are
++correct but unbalanced -- ordering by such generation numbers
++can sometimes cause the walk to detour too far before finding
++merge bases. Commit-date ordering typically reaches them in
++fewer steps -- see this change for more details:
++
++ 091f4cf3 (commit: don't use generation numbers if not needed,
++ 2018-08-30)
+
-+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.
++With generation number v2 (corrected commit dates) we have the best
++of both worlds and do not need this fallback.
+
-+This disables optimizations that depend on generation ordering:
++For v1, `paint_down_to_common()` falls back to pure commit-date
++ordering via `compare_commits_by_commit_date`. Because commit
++dates are not monotonic (clock skew, rebases, etc.), the queue
++may visit commits out of topological order.
+
-+ 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.
++This disables the optimization that depends on generation ordering:
+
-+ 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.
++ - *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.
+
+Related documentation
+---------------------
2: 143f5e0cc1 ! 2: d0ee6d062e test-lib-functions: improve diagnostic output for trace2 data assertions
@@ Commit message
test_trace2_data is a bare grep that silently exits on failure.
Add a more informative variant that verifies the event appears
exactly once and reports what went wrong: key not found, multiple
- entries, or value mismatch. Diagnostics go to FD 4 like test_grep.
+ entries, or value mismatch. Diagnostics go to FD 4 like test_grep.
Before (value mismatch):
3: eec4a9d926 ! 3: 21ecf6dc34 t6600: add test cases for side-exhaustion edge cases
@@ Commit message
## t/t6600-test-reach.sh ##
@@ t/t6600-test-reach.sh: test_expect_success 'setup' '
- git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i || return 1
- done
- done &&
-+
+ git branch -f skew-P2 "$skew_P2" &&
+ git tag skew-M2 "$skew_M2" &&
+
+ # Build a small side topology to exercise the (PARENT1|PARENT2) ->
+ # (PARENT1|PARENT2|STALE) transition in paint_down_to_common(); the
+ # 10x10 grid above does not exercise it because no merge-base candidate
@@ 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 &&
4: 7f0efe6c73 = 4: d4ecf4b698 t6099, t6600: add side-exhaustion regression tests
5: b9fb8bfe26 ! 5: 9e76f5fb62 commit-reach: add trace2 instrumentation to paint_down_to_common()
@@ commit-reach.c
/* Remember to update object flag allocation in object.h */
#define PARENT1 (1u<<16)
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
- { compare_commits_by_gen_then_commit_date }
};
int i;
+ int gen_ordered = 1;
+ int steps = 0;
timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
struct commit_list **tail = result;
6: c6e3cc13f7 ! 6: 171b3cd3ae t6600: add clock-skew topologies and step counts for edge cases
@@ Commit message
## t/t6600-test-reach.sh ##
@@ 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" &&
-+
-+ # Build a topology with clock skew to test the !FIND_ALL early
-+ # exit in paint_down_to_common(). M2 is the correct merge base
-+ # of P1 and P2, but its ancestor M1 has a higher committer date
-+ # due to clock skew. With date-only ordering (v1 commit graph
-+ # without corrected commit dates), M1 pops from the queue first,
-+ # gets both paint sides, and the early exit fires before M2 is
-+ # ever visited.
-+ #
-+ # P1 P2 @7000
-+ # | / \
-+ # A B D @6000
-+ # / \ | |
-+ # | M2--+ | @2000 (correct merge base)
-+ # \ | |
-+ # M1--------+ @5000 (clock skew: date > M2)
-+ # |
-+ # root @1000
-+ #
-+ git checkout --orphan skew-orphan &&
-+ skew_tree=$(git mktree </dev/null) &&
-+ skew_commit () {
-+ GIT_COMMITTER_DATE="@$1 +0000" GIT_AUTHOR_DATE="@$1 +0000" \
-+ git commit-tree -m "$2" "$skew_tree" $3 $4 $5 $6
-+ } &&
-+ skew_root=$(skew_commit 1000 root) &&
-+ skew_M1=$(skew_commit 5000 M1 -p "$skew_root") &&
-+ skew_M2=$(skew_commit 2000 M2 -p "$skew_M1") &&
-+ skew_A=$(skew_commit 6000 A -p "$skew_M1" -p "$skew_M2") &&
-+ skew_B=$(skew_commit 6000 B -p "$skew_M2") &&
-+ skew_D=$(skew_commit 6000 D -p "$skew_M1") &&
-+ skew_P1=$(skew_commit 7000 P1 -p "$skew_A") &&
-+ skew_P2=$(skew_commit 7000 P2 -p "$skew_B" -p "$skew_D") &&
-+ git branch -f skew-P1 "$skew_P1" &&
-+ git branch -f skew-P2 "$skew_P2" &&
-+ git tag skew-M2 "$skew_M2" &&
-+
-+ # Build a topology where clock skew causes the side-exhaustion
-+ # optimization to fire too early with date ordering (v1 graph).
+
++ # Clock-skew topology for side-exhaustion testing.
+ # D is the correct merge base but has a higher committer date
-+ # than C (its child), so D is dequeued before C. The P2 side
-+ # (B -> D -> root) fully drains while C (P1-only) is still
-+ # queued. Side-exhaustion fires, missing D as a merge base.
++ # than C (its child). With date ordering, D would be dequeued
++ # before C, causing side-exhaustion to fire too early.
++ # Generation ordering prevents this by visiting children
++ # before parents regardless of dates.
+ #
+ # se-A (date 7000) --> se-C (date 3000) --> se-D (date 5000) --> se-root (date 4000)
+ # se-B (date 6000) --> se-D
@@ t/t6600-test-reach.sh: test_expect_success 'setup' '
+ git branch -f se-B "$se_B" &&
+ git tag se-D "$se_D" &&
+
-+ # Build a topology where side-exhaustion with date ordering
-+ # returns a wrong (too-deep) merge base. MB1 is the correct
-+ # merge base; MB2 is its parent and should be filtered as
-+ # redundant. A reaches MB2 via E (high date) and MB1 via C
-+ # (low date). B reaches MB1 via D. With date ordering, the
-+ # P2 side drains after MB2 is found but before C is dequeued,
-+ # so MB1 never receives P1 paint. Result: MB2 (wrong).
++ # Clock-skew topology with redundant ancestor for
++ # side-exhaustion testing. MB1 is the correct merge base;
++ # MB2 is its parent. A reaches MB2 via E (high date) and
++ # MB1 via C (low date). B reaches MB1 via D. With date
++ # ordering, side-exhaustion would fire before C is dequeued,
++ # missing MB1. Generation ordering ensures both are found.
+ #
+ # se2-A (date 8000) --> se2-C (date 2000) --> se2-MB1 (date 5000) --> se2-MB2 (date 4000) --> se2-root (date 1000)
+ # se2-A --> se2-E (date 6500) --> se2-MB2
@@ t/t6600-test-reach.sh: test_expect_success 'setup' '
+ git branch -f se2-A "$se2_A" &&
+ git branch -f se2-B "$se2_B" &&
+ git tag se2-MB1 "$se2_MB1" &&
++
git commit-graph write --reachable &&
mv .git/objects/info/commit-graph commit-graph-full &&
chmod u+w commit-graph-full &&
@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all commit-walk steps'
test_paint_down_steps 81 80 81 81
'
-+test_expect_success 'merge-base --all with clock skew and v1 commit-graph (side-exhaustion)' '
-+ # With date ordering (v1 graph), the side-exhaustion
-+ # optimization can fire too early. In this topology, the P2
-+ # side (se-B -> se-D -> se-root) fully drains from the queue
-+ # while se-C (P1-only, low date) is still queued. With
-+ # generation ordering, se-C would be dequeued before se-D
-+ # (child before parent), propagating P1 to se-D and
-+ # discovering the merge base. Date ordering violates this.
++test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '
++ # Verify correct merge base under clock skew. se-D (the
++ # merge base) has a higher date than its child se-C.
++ # Generation ordering ensures se-C is visited before se-D,
++ # so P1 paint propagates correctly and se-D is found.
+ >input &&
+ git rev-parse se-D >expect &&
+ run_all_modes git merge-base --all se-A se-B &&
+ test_paint_down_steps 6 4 6 6
+'
+
-+test_expect_success 'merge-base --all with clock skew returns wrong merge base (side-exhaustion)' '
-+ # With date ordering (v1 graph), side-exhaustion causes
-+ # merge-base --all to return MB2 (too deep) instead of MB1
-+ # (the correct closest merge base). P1 paint reaches MB2
-+ # via E (high date) before it reaches MB1 via C (low date).
-+ # After MB2 is found as P1|P2, the P2 side drains and
-+ # side-exhaustion fires while C is still in the queue.
-+ # MB1 never receives P1 paint, so it is never identified
-+ # as a merge base. remove_redundant cannot discard MB2
-+ # because MB1 was never found.
++test_expect_success 'merge-base --all with clock skew and redundant ancestor (side-exhaustion)' '
++ # Verify correct merge base when clock skew could cause a
++ # too-deep result. MB1 is the correct merge base; MB2 is
++ # its ancestor. A reaches MB2 via E (high date) and MB1
++ # via C (low date). Generation ordering ensures C is
++ # visited before side-exhaustion fires, so MB1 is found
++ # and remove_redundant correctly discards MB2.
+ >input &&
+ git rev-parse se2-MB1 >expect &&
+ run_all_modes git merge-base --all se2-A se2-B &&
7: 42a75899f2 ! 7: 92a327a94c commit-reach: introduce struct paint_state with per-side counters
@@ commit-reach.c: static void clear_nonstale_queue(struct nonstale_queue *queue)
+ 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 void clear_nonstale_queue(struct nonstale_queue *queue)
+ prio_queue_put(&state->queue, c);
+ paint_count_update(state, c->object.flags, 1);
+ }
-+}
+ }
-- if (commit)
-- commit->object.flags &= ~ENQUEUED;
+-static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
+static struct commit *paint_queue_get(struct paint_state *state)
-+{
+ {
+- struct commit *commit = nonstale_queue_get(queue);
+ struct commit *commit = prio_queue_get(&state->queue);
+
+ if (!commit)
@@ commit-reach.c: static void clear_nonstale_queue(struct nonstale_queue *queue)
+ if (!state->parent1_count && !state->parent2_count &&
+ !state->mb_candidate_count)
+ return NULL;
-+
+
+- if (commit)
+- commit->object.flags &= ~ENQUEUED;
+ paint_count_update(state, commit->object.flags, -1);
return commit;
}
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
};
+ struct commit *commit;
int i;
+- int gen_ordered = 1;
int steps = 0;
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)) {
+- gen_ordered = 0;
+ state.queue.compare = compare_commits_by_commit_date;
+ state.gen_ordered = 0;
-+ }
+ }
one->object.flags |= PARENT1;
- if (!n) {
+@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
commit_list_append(one, result);
return 0;
}
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
struct commit_list *parents;
int flags;
timestamp_t generation = commit_graph_generation(commit);
+@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
+ * descendant of this one.
+ */
+ if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
+- gen_ordered &&
++ state.gen_ordered &&
+ generation < GENERATION_NUMBER_INFINITY)
+ break;
+ }
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
if ((p->object.flags & flags) == flags)
continue;
@@ 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 (
+@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all with clock skew and redundant ancestor (si
>input &&
git rev-parse se2-MB1 >expect &&
run_all_modes git merge-base --all se2-A se2-B &&
8: f8f00b7bcc ! 8: 0d552869be commit-reach: terminate merge-base walk when one paint side is exhausted
@@ Commit message
commit-reach: terminate merge-base walk when one paint side is exhausted
Add an early termination check to paint_down_to_common() using the
- per-side counters introduced earlier. Once the walk enters the
+ per-side counters introduced earlier. Once the walk enters the
finite-generation region, terminate early when one side's exclusive
count drops to zero -- no new merge-base can form without both paint
sides meeting.
@@ Commit message
The INFINITY gate ensures correctness: commits without a commit-graph
entry have GENERATION_NUMBER_INFINITY and are ordered by commit date,
- which is not topologically reliable. The optimization only fires
+ which is not topologically reliable. The optimization only fires
once the walk enters the finite-generation region where ordering
guarantees hold.
@@ Documentation/technical/paint-down-to-common.adoc: existing candidates by provin
Generation cutoff
~~~~~~~~~~~~~~~~~
Some callers (notably `remove_redundant()`) supply a `min_generation`
+@@ Documentation/technical/paint-down-to-common.adoc: ordering via `compare_commits_by_commit_date`. Because commit
+ dates are not monotonic (clock skew, rebases, etc.), the queue
+ may visit commits out of topological order.
+
+-This disables the optimization that depends on generation ordering:
++This disables the optimizations that depend on generation ordering:
+
+ - *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.
+
++ - *Side exhaustion*: 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
+ ---------------------
+
## commit-reach.c ##
@@ commit-reach.c: static void paint_queue_put(struct paint_state *state,
@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all commit-walk steps'
+ test_paint_down_steps 81 9 57 81
'
- test_expect_success 'merge-base --all with clock skew and v1 commit-graph (side-exhaustion)' '
+ test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '
9: b45c302caa ! 9: 598a963375 commit-reach: move min_generation check into paint_queue_get()
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
if (flags == (PARENT1 | PARENT2)) {
if (!(commit->object.flags & RESULT)) {
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
- * descendant of this one.
*/
if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
+ state.gen_ordered &&
- generation < GENERATION_NUMBER_INFINITY)
+ state.last_gen < GENERATION_NUMBER_INFINITY)
break;
10: d68972b1d7 ! 10: 6d617da1f7 commit-reach: remove commit-date ordering fallback
@@ Commit message
Side-exhaustion (added in the previous commits) solves this
differently by terminating the walk as soon as one paint side
empties from the queue, preventing the deep walk regardless of
- queue ordering. Benchmarks of "git merge-base --all v4.8 v4.9"
+ queue ordering. Benchmarks of "git merge-base --all v4.8 v4.9"
on the Linux kernel repo show that side-exhaustion reduces the
step count far below what the date-ordering fallback achieved:
@@ Commit message
With generation ordering always active, the existing min_generation
check in paint_queue_get() correctly identifies when the walk has
- reached the finite generation region. The date ordering fallback
+ reached the finite generation region. The date ordering fallback
broke this invariant: a commit could have a finite topo level
while the queue was date-ordered, causing the early exit to fire
before all merge bases were found.
@@ Commit message
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
## Documentation/technical/paint-down-to-common.adoc ##
-@@ Documentation/technical/paint-down-to-common.adoc: 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]]
+@@ Documentation/technical/paint-down-to-common.adoc: ancestor is necessarily redundant.
INFINITY and finite generation regions
--------------------------------------
@@ Documentation/technical/paint-down-to-common.adoc: and PARENT2, it is a merge-ba
-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
+ 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
+@@ Documentation/technical/paint-down-to-common.adoc: traversal: children are always visited before their parents. This
+ means that paint on already-visited commits is final -- no future
+ traversal step can add paint to them.
+
+-In the INFINITY region, commit-date ordering can violate this: a
+-parent with a later date can be visited before a child with an earlier
+-date. Paint flags are therefore NOT final at visit time, and a
+-commit visited with only one side's paint may later gain the other.
++In the INFINITY region, all commits share the same generation
++value, so the queue breaks ties by commit date. This can violate
++topological ordering: a parent with a later date can be visited
++before a child with an earlier date. Paint flags are therefore
++NOT final at visit time, and a commit visited with only one
++side's paint may later gain the other.
+
+ Paint flags are only added, never removed. Since each flag can be set
+ at most once per commit, the number of times a commit can be
@@ Documentation/technical/paint-down-to-common.adoc: descendant of this candidate (generation ordering guarantees
children are visited first), so it cannot be redundant and the walk
can stop immediately.
@@ Documentation/technical/paint-down-to-common.adoc: descendant of this candidate
-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`.
+-When the commit-graph has generation numbers v1 and no
+-generation floor is specified, topological ordering
+-(via generation numbers) is disabled. Topological levels are
+-correct but unbalanced -- ordering by such generation numbers
+-can sometimes cause the walk to detour too far before finding
+-merge bases. Commit-date ordering typically reaches them in
+-fewer steps -- see this change for more details:
-
--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.
+- 091f4cf3 (commit: don't use generation numbers if not needed,
+- 2018-08-30)
-
--This disables optimizations that depend on generation ordering:
+-With generation number v2 (corrected commit dates) we have the best
+-of both worlds and do not need this fallback.
-
-- 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.
+-For v1, `paint_down_to_common()` falls back to pure commit-date
+-ordering via `compare_commits_by_commit_date`. Because commit
+-dates are not monotonic (clock skew, rebases, etc.), the queue
+-may visit commits out of topological order.
-
-- 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.
+-This disables the optimizations that depend on generation ordering:
+-
+- - *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.
+-
+- - *Side exhaustion*: 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
---------------------
@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
one->object.flags |= PARENT1;
if (!n) {
+@@ commit-reach.c: static int paint_down_to_common(struct repository *r,
+ * descendant of this one.
+ */
+ if (!(mb_flags & MERGE_BASE_FIND_ALL) &&
+- state.gen_ordered &&
+ state.last_gen < GENERATION_NUMBER_INFINITY)
+ break;
+ }
## t/t6600-test-reach.sh ##
@@ t/t6600-test-reach.sh: test_expect_success 'get_merge_bases_many:infinity-both-sides' '
@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all commit-walk steps'
+ test_paint_down_steps 81 9 57 37
'
- test_expect_success 'merge-base --all with clock skew and v1 commit-graph (side-exhaustion)' '
-@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all with clock skew and v1 commit-graph (side-
+ test_expect_success 'merge-base --all with clock skew (side-exhaustion)' '
+- # Verify correct merge base under clock skew. se-D (the
+- # merge base) has a higher date than its child se-C.
+- # Generation ordering ensures se-C is visited before se-D,
+- # so P1 paint propagates correctly and se-D is found.
++ # Verify that the merge base is computed correctly even
++ # when commits have non-monotonic commit dates.
>input &&
git rev-parse se-D >expect &&
run_all_modes git merge-base --all se-A se-B &&
@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all with clock skew and
+ test_paint_down_steps 6 4 6 4
'
- test_expect_success 'merge-base --all with clock skew returns wrong merge base (side-exhaustion)' '
-@@ t/t6600-test-reach.sh: test_expect_success 'merge-base --all with clock skew returns wrong merge base (
+ test_expect_success 'merge-base --all with clock skew and redundant ancestor (side-exhaustion)' '
+- # Verify correct merge base when clock skew could cause a
+- # too-deep result. MB1 is the correct merge base; MB2 is
+- # its ancestor. A reaches MB2 via E (high date) and MB1
+- # via C (low date). Generation ordering ensures C is
+- # visited before side-exhaustion fires, so MB1 is found
+- # and remove_redundant correctly discards MB2.
++ # Verify that the correct merge base is found even when
++ # non-monotonic commit dates could cause a redundant
++ # ancestor to be visited first.
>input &&
git rev-parse se2-MB1 >expect &&
run_all_modes git merge-base --all se2-A se2-B &&
--
gitgitgadget
^ permalink raw reply
* [PATCH] fixup! fetch: add fetch.submoduleErrors to make submodule fetch errors non-fatal
From: Ramsay Jones @ 2026-07-11 13:22 UTC (permalink / raw)
To: Junio C Hamano; +Cc: GIT Mailing-list
Signed-off-by: Ramsay Jones <ramsay@ramsayjones.plus.com>
---
Hi Junio,
You have probably already noticed, but just in case, I had to fixup commit df9481e6d6
("fetch: add fetch.submoduleErrors to make submodule fetch errors non-fatal", 2026-07-10)
in order to get a clean test-suite run on the 'seen' branch (@a77a48500d) this afternoon.
[this is part of the 'pz/fetch-submodule-errors-config' branch].
Thanks.
ATB,
Ramsay Jones
t/t5526-fetch-submodules.sh | 18 +++++++++---------
1 file changed, 9 insertions(+), 9 deletions(-)
diff --git a/t/t5526-fetch-submodules.sh b/t/t5526-fetch-submodules.sh
index 7ccc80048b..4bb6d483be 100755
--- a/t/t5526-fetch-submodules.sh
+++ b/t/t5526-fetch-submodules.sh
@@ -1312,7 +1312,7 @@ test_expect_success 'fetch --recurse-submodules fails when submodule commit is u
create_err_env env_default &&
push_unreachable_commit env_default &&
test_must_fail git -C env_default/clone fetch --recurse-submodules 2>err &&
- grep "Errors during submodule fetch" err
+ test_grep "Errors during submodule fetch" err
'
test_expect_success 'fetch.submoduleErrors=warn: unreachable submodule commit is non-fatal' '
@@ -1321,7 +1321,7 @@ test_expect_success 'fetch.submoduleErrors=warn: unreachable submodule commit is
push_unreachable_commit env_warn_cfg &&
git -C env_warn_cfg/clone -c fetch.submoduleErrors=warn \
fetch --recurse-submodules 2>err &&
- grep "Errors during submodule fetch" err
+ test_grep "Errors during submodule fetch" err
'
test_expect_success '--submodule-errors=warn: unreachable submodule commit is non-fatal' '
@@ -1330,7 +1330,7 @@ test_expect_success '--submodule-errors=warn: unreachable submodule commit is no
push_unreachable_commit env_warn_cli &&
git -C env_warn_cli/clone fetch --recurse-submodules \
--submodule-errors=warn 2>err &&
- grep "Errors during submodule fetch" err
+ test_grep "Errors during submodule fetch" err
'
test_expect_success '--submodule-errors=fail: unreachable submodule commit is fatal' '
@@ -1339,7 +1339,7 @@ test_expect_success '--submodule-errors=fail: unreachable submodule commit is fa
push_unreachable_commit env_fail_cli &&
test_must_fail git -C env_fail_cli/clone fetch --recurse-submodules \
--submodule-errors=fail 2>err &&
- grep "Errors during submodule fetch" err
+ test_grep "Errors during submodule fetch" err
'
test_expect_success 'fetch.submoduleErrors=warn does not suppress successful fetch' '
@@ -1355,7 +1355,7 @@ test_expect_success 'fetch.submoduleErrors=warn does not suppress successful fet
git -C env_ok/super_work push &&
git -C env_ok/clone -c fetch.submoduleErrors=warn \
fetch --recurse-submodules 2>err &&
- ! grep "Errors during submodule fetch" err
+ test_grep ! "Errors during submodule fetch" err
'
test_expect_success 'failed submodule fetch is fatal even when its commits are present locally' '
@@ -1382,7 +1382,7 @@ test_expect_success 'failed submodule fetch is fatal even when its commits are p
git -C env_phase1/super_work push &&
git -C env_phase1/clone/sub remote set-url origin "$pwd/env_phase1/missing" &&
test_must_fail git -C env_phase1/clone fetch --recurse-submodules 2>err &&
- grep "Errors during submodule fetch" err
+ test_grep "Errors during submodule fetch" err
'
test_expect_success '--submodule-errors=warn is honored by fetch --all' '
@@ -1395,7 +1395,7 @@ test_expect_success '--submodule-errors=warn is honored by fetch --all' '
git -C env_all/clone remote add second "$pwd/env_all/super_bare" &&
git -C env_all/clone fetch --all --recurse-submodules \
--submodule-errors=warn 2>err &&
- grep "Errors during submodule fetch" err
+ test_grep "Errors during submodule fetch" err
'
test_expect_success 'fetch.submoduleErrors=warn: inaccessible submodule is non-fatal' '
@@ -1405,9 +1405,9 @@ test_expect_success 'fetch.submoduleErrors=warn: inaccessible submodule is non-f
rm -r env_access/clone/.git/modules/sub &&
git -C env_access/clone -c fetch.submoduleErrors=warn \
fetch --recurse-submodules 2>err &&
- grep "Could not access submodule" err &&
+ test_grep "Could not access submodule" err &&
test_must_fail git -C env_access/clone fetch --recurse-submodules 2>err &&
- grep "Could not access submodule" err
+ test_grep "Could not access submodule" err
'
test_done
--
2.55.0
^ permalink raw reply related
* Re: [PATCH v18 5/7] branch: add --delete-merged <branch>
From: Harald Nordgren @ 2026-07-11 13:08 UTC (permalink / raw)
To: phillip.wood
Cc: Harald Nordgren via GitGitGadget, git, Kristoffer Haugsbakk,
Johannes Sixt, Phillip Wood
In-Reply-To: <e35f1268-2518-4a44-9c7c-28ba13ca7b7b@gmail.com>
> > git branch --delete-merged <branch>...
>
> This design means that unlike --forked there is no way to limit the
> branches considered for deletion. I wonder if we'd be better to have
> --delete-merged take an argument like --forked so that the user can
> limit the branches that might be deleted without resorting to the config
> setting added in the next patch.
Makes sense, I updated it now and it seems to work fine.
> > diff --git a/t/t3200-branch.sh b/t/t3200-branch.sh
> > index 3104c555f6..047ba54778 100755
> > --- a/t/t3200-branch.sh
> > +++ b/t/t3200-branch.sh
> > @@ -1839,4 +1839,189 @@ test_expect_success '--forked narrows a <pattern> argument' '
> > test_cmp expect actual
> > '
> >
> > +test_expect_success '--delete-merged: setup' '
> > + git init -b main upstream &&
> > + (
> > + cd upstream &&
> > + test_commit base &&
> > + git checkout -b next &&
> > + test_commit next-work &&
> > + git checkout main
> > + ) &&
> > + git init -b main other &&
> > + test_commit -C other other-base &&
> > + git init -b main fork
> > +'
> > +
> > +setup_repo_for_delete_merged () {
> > + rm -rf repo &&
> > + git clone upstream repo &&
> > + (
> > + cd repo &&
> > + git remote add fork ../fork &&
> > + git remote add other ../other &&
> > + git config remote.pushDefault fork &&
> > + git config push.default current &&
> > + git fetch other
> > + )
> > +}
> > +
> > +merged_branch () {
>
> A comment would have helped to explain what this helper does. Also
> calling it create_merged_branch() would be clearer too I think.
I want to avoid comments because of the maintenance burden they
introduce, I think 'create_merged_branch' will be a very clear name.
Thanks for that suggestion!
> > + (
> > + cd repo &&
> > + git checkout -b "$1" "$2" &&
>
> If we add '--track' we can avoid having to run "git branch
> --set-upstream-to" below. The same goes for many if not all of the
> branches created by "git checkout -b" and "git branch" in these tests.
That's a very good point. I wanted to keep it "vanilla" since I worked
a lot on upstreams and tracking branches in my other topics and didn't
want it to bleed over, but yes it's much nicer.
> > + git commit --allow-empty -m "$1 work" &&
> > + git push origin "$1:next" &&
>
> We let the caller specify the upstream branch, but then always push to
> origin/next - should be be using 'git push ${2%%/*} "$1:${2#*/}"', or if
> we don't need that flexibility hard coding the upstream branch?
I'll hardcode for now.
> > + git fetch origin &&
>
> We've just pushed, what are we fetching here?
>
> > + git branch --set-upstream-to="$2" "$1"
> > + )
> > +}
> > +
> > +test_expect_success '--delete-merged deletes merged branches and spares the rest' '
> > + test_when_finished "rm -rf repo" &&
>
> The first thing setup_repo_for_delete does is delete repo so do we need
> this as well?
Nope, let's rip it out.
> > + git branch --set-upstream-to=origin/next unmerged &&
> > + git checkout -b tracks-other other/main &&
> > + git branch --set-upstream-to=other/main tracks-other &&
> > + git checkout --detach
>
> I assume this is to ensure we don't spare a branch because it is checked
> out?
Yes, but it's also a pattern that I copy-pasted a few too many times,
see my other comment where some of these can be removed.
> > + ) &&
> > + sha=$(git -C repo rev-parse --short merged) &&
> > +
> > + git -C repo branch --delete-merged origin/next >actual 2>&1 &&
> > +
> > + echo "Deleted branch merged (was $sha)." >expect &&
>
> There doesn't seem to be any reason for these command or the ones below
> to be outside the subshell - they're all running commands in "repo".
> That seems to be a common pattern in these tests.
Agreed, but other reviewers were against subshells before. I updated
it now and looks much cleaner.
> > + (
> > + cd repo &&
> > + git checkout -b mainline main &&
> > + git checkout -b on-local mainline &&
> > + git branch --set-upstream-to=mainline on-local &&
>
> Why do we need on-local to track mainline rather than main? I'm a bit
> confused what the point of mainline is.
It's to have an indirection of a branch that is the same as main but
will be protected. I tried to delete it now and replace it with just
main, but then main was deleted and subsequent tests failed.
> > + git update-ref refs/remotes/origin/topic refs/remotes/origin/next &&
> > + git branch --set-upstream-to=origin/topic upstream-gone &&
> > + git update-ref -d refs/remotes/origin/topic &&
>
> These three lines can be replaced by
>
> git config branch.gone.merge does-not-exist
>
> > + git branch --set-upstream-to=origin/main main &&
> > + git config branch.main.pushRemote origin &&
>
> What does this do? Isn't its pushRemote already origin?
Deleted.
> > + git checkout -b tracks-other other/main &&
> > + git branch --set-upstream-to=other/main tracks-other &&
> > + git checkout checked-out
> > + ) &&
> > +
> > + git -C repo branch --delete-merged origin/next mainline &&
>
> Do we want to use "origin/*" here instead so that we check that main is
> not deleted because its push destination matches its upstream?
That's a good point and a good regression test later on.
> > +
> > + git -C repo for-each-ref --format="%(refname:short)" refs/heads/ >actual &&
> > + cat >expect <<-\EOF &&
> > + checked-out
> > + main
> > + mainline
> > + tracks-other
> > + upstream-gone
> > + EOF
> > + test_cmp expect actual
>
> This checks we delete on-local - good. I wonder if we should add a
> comment about the expected outcome so it is clear to the casual reader
> what is happening.
I'll rename to 'local-to-delete' to clarify and to avoid the comment.
> > +'
> > +
> > +test_expect_success '--delete-merged requires at least one <branch>' '
> > + test_must_fail git -C forked branch --delete-merged 2>err &&
> > + test_grep "requires at least one <branch>" err
> > +'
> > +
> > +test_expect_success '--delete-merged keeps a branch that is an upstream' '
> > + test_when_finished "rm -rf repo" &&
> > + setup_repo_for_delete_merged &&
> > + merged_branch feature origin/next &&
> > + (
> > + cd repo &&
> > + git checkout -b topic feature &&
> > + git commit --allow-empty -m "topic work" &&
> > + git branch --set-upstream-to=feature topic &&
> > + git checkout --detach
> > + ) &&
> > +
> > + git -C repo branch --dry-run --delete-merged origin/next >out &&
>
> This belongs in a later patch and shows that the patches in this series
> have not been individually tested (c.f. my previous mail about running
> "git rebase --keep-base --exec")
Yup, should be fixed now. And I usually run "git rebase --keep-base
--exec" a lot!
> > + git -C repo rev-parse --verify refs/heads/feature &&
> > + git -C repo rev-parse --verify refs/heads/topic &&
>
> I preferred the way this as checked in the previous tests with
> for-each-ref and test_cmp as that shows everything that was kept.
Yes, it's better.
> > + echo origin/next >expect &&
> > + git -C repo rev-parse --abbrev-ref feature@{upstream} >actual &&
> > + test_cmp expect actual &&
> > + echo feature >expect &&
> > + git -C repo rev-parse --abbrev-ref topic@{upstream} >actual &&
> > + test_cmp expect actual
>
> This is a bit of a faff. Perhaps
>
> git config --local --get-regexp
> "branch.(feature|topic).(merge|remote)" >actual
>
> followed by test_cmp would be more concise and more clearly show that
> we're interested in checking that the config settings still exist.
Nice.
> > +'
> > +
> > +test_expect_success '--delete-merged keeps a chain of upstreams of a kept branch' '
> > + test_when_finished "rm -rf repo" &&
> > + setup_repo_for_delete_merged &&
> > + (
> > + cd repo &&
> > + git branch b3 origin/next &&
> > + git branch --set-upstream-to=origin/next b3 &&
> > + git branch b2 origin/next &&
> > + git branch --set-upstream-to=b3 b2 &&
> > + git checkout -b b1 b2 &&
> > + git commit --allow-empty -m "b1 work" &&
> > + git branch --set-upstream-to=b2 b1 &&
> > + git checkout --detach
> > + ) &&
>
> I'd find this easier to follow if the base branch which is created
> first was numbered 1, rather than the tip of the stack.
>
>
> > + git -C repo branch --delete-merged origin/next &&
>
> b3 is merged but cannot be deleted because it is the upstream for b2
> which although it is merged into b3 isn't a candidate for deletion
> because its upstream is b3.
>
> I'm not quite sure what this test demonstrates that the next one does not.
Deleting this one, which also removes the question of b1, b2 and b3 naming.
> > +
> > + git -C repo for-each-ref --format="%(refname:short)" refs/heads/ >actual &&
> > + cat >expect <<-\EOF &&
> > + b1
> > + b2
> > + b3
> > + main
> > + EOF
> > + test_cmp expect actual
> > +'
> > +
> > +test_expect_success '--delete-merged clears the upstream of a kept base whose own base is deleted' '
> > + test_when_finished "rm -rf repo" &&
> > + setup_repo_for_delete_merged &&
> > + (
> > + cd repo &&
> > + git branch lower origin/next &&
> > + git branch --set-upstream-to=origin/next lower &&
> > + git branch mid origin/next &&
> > + git branch --set-upstream-to=lower mid &&
> > + git checkout -b tip mid &&
> > + git commit --allow-empty -m "tip work" &&
> > + git branch --set-upstream-to=mid tip &&
> > + git checkout --detach
> > + ) &&
> > +
> > + git -C repo branch --delete-merged origin/next lower &&
>
> We expect lower to be deleted, but not mid because although it is merged
> it is the upstream of an unmerged branch. Again it would be nice to
> check that with for-each-ref (maybe that is a common enough pattern to
> justify a helper that takes the expected output on stdin
>
> check_branches <<-\EOF
> main
> mid
> tip
> EOF
Very good idea! Created the helper!
> > + test_must_fail git -C repo rev-parse --verify refs/heads/lower &&
> > + git -C repo rev-parse --verify refs/heads/mid &&
> > + test_must_fail git -C repo rev-parse mid@{upstream} &&
> > + echo mid >expect &&
> > + git -C repo rev-parse --abbrev-ref tip@{upstream} >actual &&
> > + test_cmp expect actual
>
> I'd check the config settings here as suggested for the test above. The
> test coverage looks good, there are just a few places where a comment
> would help explain what's going on and some places where we can save a
> few commands.
Will update! Thanks again!
Harald
^ permalink raw reply
* Re: [PATCH v18 1/7] branch: add --forked filter for --list mode
From: Harald Nordgren @ 2026-07-11 12:30 UTC (permalink / raw)
To: phillip.wood
Cc: Harald Nordgren via GitGitGadget, git, Kristoffer Haugsbakk,
Johannes Sixt
In-Reply-To: <8ee46e33-4eb8-4e01-800a-82cc7cefa3f9@gmail.com>
> The implementation looks good, I've left a couple of small comments on
> the tests.
Thanks for all the help so far! Much appreciated!
> One thought I had was whether we want a mode which recurses
> so that if the upstream of topic2 is topic1 which has an upstream of
> origin/main --forked=recurse origin/main would list topic1 and topic2.
> So long as we don't think that is a sensible default we can add it in
> the future if we want.
I don't understand this one, but if we safely do it later then that
sounds good considering we will soon be on v19.
> > + git branch local-base &&
> > + git branch --track local-one origin/one &&
> > + git branch --track local-two origin/two &&
> > + git branch --track local-foreign other/foreign &&
> > + git branch --track local-onbase local-base &&
> > +
> > + git checkout local-one &&
> > + test_commit --no-tag local-one-work local-one.t &&
> > + git checkout local-foreign &&
> > + test_commit --no-tag local-foreign-work local-foreign.t &&
> > + git checkout --detach
>
> Why do we need a detached HEAD?
The '--delete-merged honours branch.<name>.deleteMerged=false' ' and
"branch -d still deletes a deleteMerged=false branch" ' tests need it,
but it's not necessary here, deleting.
> > + git -C forked branch --forked "origin/*" --no-merged origin/one \
> > + --format="%(refname:short)" >actual &&
> > + echo local-one >expect &&
> > + test_cmp expect actual
> > +'
> > +
> > +test_expect_success '--forked rejects unknown branch/pattern' '
> > + test_must_fail git -C forked branch --forked nope 2>err &&
> > + test_grep "not a valid branch or pattern" err
> > +'
> > +
> > +test_expect_success '--forked requires a value' '
> > + test_must_fail git -C forked branch --forked 2>err &&
> > + test_grep "requires a value" err
> > +'
>
> It is a bit odd to have these two tests in the middle of the ones that
> check the functionality works.
Good point, reordering.
Harald
^ permalink raw reply
* Re: Understanding why Git defaults to show author date and not committer date
From: Jeff King @ 2026-07-11 8:03 UTC (permalink / raw)
To: Omri Sarig; +Cc: git
In-Reply-To: <CAP9es6tyaGwfTguz5zgBmE5xN7MLDN3-rxRfo_JJBf79RCNzgg@mail.gmail.com>
On Fri, Jul 10, 2026 at 05:08:11PM +0200, Omri Sarig wrote:
> I understand the distinction between the 2 formats, and I can see the utility of
> both. I'm curious about the decision to show the author date and not the
> committer date as default one in Git commands.
> Are there some workflows where the author date is more relevant, or is that
> mostly a legacy decision?
>
> I'd be interested in hearing about workflows where the author date is the more
> useful one, as I use the committer date almost always.
In a workflow based on mailing patches, the committer date is usually
much less interesting. It is "when the maintainer happened to pick up
your patch", as opposed to when you wrote it. Likewise, we show the
author's name by default, not the committer's.
-Peff
^ permalink raw reply
page: next (older) | prev (newer) | latest
- recent:[subjects (threaded)|topics (new)|topics (active)]
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox