* [GSoC Patch v6 2/4] rev-parse: use append_formatted_path() for path formatting
From: K Jayatheerth @ 2026-06-20 3:16 UTC (permalink / raw)
To: git
Cc: jltobler, lucasseikioshiro, gitster, phillip.wood, sandals,
kumarayushjha123, a3205153416, kristofferhaugsbakk, K Jayatheerth
In-Reply-To: <20260620031644.353772-1-jayatheerthkulkarni2005@gmail.com>
Now that the core path-formatting algorithm lives in
append_formatted_path(), print_path() doesn't need to duplicate it.
Replace the body of print_path() with a small mapping from rev-parse's
existing format_type/default_type pair to the shared path_format enum,
then delegate to append_formatted_path(). The two local enums, and
every call site that uses them throughout cmd_rev_parse(), are left
untouched.
Mentored-by: Justin Tobler <jltobler@gmail.com>
Mentored-by: Lucas Seiki Oshiro <lucasseikioshiro@gmail.com>
Signed-off-by: K Jayatheerth <jayatheerthkulkarni2005@gmail.com>
---
builtin/rev-parse.c | 73 ++++++++++++++++++---------------------------
1 file changed, 29 insertions(+), 44 deletions(-)
diff --git a/builtin/rev-parse.c b/builtin/rev-parse.c
index bb882678fe..6de01466db 100644
--- a/builtin/rev-parse.c
+++ b/builtin/rev-parse.c
@@ -653,53 +653,38 @@ enum default_type {
DEFAULT_UNMODIFIED,
};
-static void print_path(const char *path, const char *prefix, enum format_type format, enum default_type def)
+static void print_path(const char *path, const char *prefix,
+ enum format_type format, enum default_type def)
{
- char *cwd = NULL;
- /*
- * We don't ever produce a relative path if prefix is NULL, so set the
- * prefix to the current directory so that we can produce a relative
- * path whenever possible. If we're using RELATIVE_IF_SHARED mode, then
- * we want an absolute path unless the two share a common prefix, so don't
- * set it in that case, since doing so causes a relative path to always
- * be produced if possible.
- */
- if (!prefix && (format != FORMAT_DEFAULT || def != DEFAULT_RELATIVE_IF_SHARED))
- prefix = cwd = xgetcwd();
- if (format == FORMAT_DEFAULT && def == DEFAULT_UNMODIFIED) {
- puts(path);
- } else if (format == FORMAT_RELATIVE ||
- (format == FORMAT_DEFAULT && def == DEFAULT_RELATIVE)) {
- /*
- * In order for relative_path to work as expected, we need to
- * make sure that both paths are absolute paths. If we don't,
- * we can end up with an unexpected absolute path that the user
- * didn't want.
- */
- struct strbuf buf = STRBUF_INIT, realbuf = STRBUF_INIT, prefixbuf = STRBUF_INIT;
- if (!is_absolute_path(path)) {
- strbuf_realpath_forgiving(&realbuf, path, 1);
- path = realbuf.buf;
- }
- if (!is_absolute_path(prefix)) {
- strbuf_realpath_forgiving(&prefixbuf, prefix, 1);
- prefix = prefixbuf.buf;
+ struct strbuf sb = STRBUF_INIT;
+ enum path_format fmt;
+
+ if (format == FORMAT_RELATIVE) {
+ fmt = PATH_FORMAT_RELATIVE;
+ } else if (format == FORMAT_CANONICAL) {
+ fmt = PATH_FORMAT_CANONICAL;
+ } else /* FORMAT_DEFAULT */ {
+ switch (def) {
+ case DEFAULT_RELATIVE:
+ fmt = PATH_FORMAT_RELATIVE;
+ break;
+ case DEFAULT_RELATIVE_IF_SHARED:
+ fmt = PATH_FORMAT_RELATIVE_IF_SHARED;
+ break;
+ case DEFAULT_CANONICAL:
+ fmt = PATH_FORMAT_CANONICAL;
+ break;
+ case DEFAULT_UNMODIFIED:
+ default:
+ fmt = PATH_FORMAT_UNMODIFIED;
+ break;
}
- puts(relative_path(path, prefix, &buf));
- strbuf_release(&buf);
- strbuf_release(&realbuf);
- strbuf_release(&prefixbuf);
- } else if (format == FORMAT_DEFAULT && def == DEFAULT_RELATIVE_IF_SHARED) {
- struct strbuf buf = STRBUF_INIT;
- puts(relative_path(path, prefix, &buf));
- strbuf_release(&buf);
- } else {
- struct strbuf buf = STRBUF_INIT;
- strbuf_realpath_forgiving(&buf, path, 1);
- puts(buf.buf);
- strbuf_release(&buf);
}
- free(cwd);
+
+ append_formatted_path(&sb, path, prefix, fmt);
+ puts(sb.buf);
+
+ strbuf_release(&sb);
}
int cmd_rev_parse(int argc,
--
2.54.0
^ permalink raw reply related
* [GSoC Patch v6 3/4] repo: add path.commondir with absolute and relative suffix formatting
From: K Jayatheerth @ 2026-06-20 3:16 UTC (permalink / raw)
To: git
Cc: jltobler, lucasseikioshiro, gitster, phillip.wood, sandals,
kumarayushjha123, a3205153416, kristofferhaugsbakk, K Jayatheerth
In-Reply-To: <20260620031644.353772-1-jayatheerthkulkarni2005@gmail.com>
Scripts working with worktree setups need a reliable way to discover
the common directory, which diverges from the git directory when
multiple worktrees are in use. There is no way to retrieve this path
from git repo info today.
Introduce path.commondir.absolute and path.commondir.relative keys.
Exposing explicit format variants rather than a single key with a
default avoids ambiguity for scripts that require predictable output.
Mentored-by: Justin Tobler <jltobler@gmail.com>
Mentored-by: Lucas Seiki Oshiro <lucasseikioshiro@gmail.com>
Signed-off-by: K Jayatheerth <jayatheerthkulkarni2005@gmail.com>
---
Documentation/git-repo.adoc | 9 +++++++
builtin/repo.c | 26 +++++++++++++++++++
t/t1900-repo-info.sh | 52 +++++++++++++++++++++++++++++++++++++
3 files changed, 87 insertions(+)
diff --git a/Documentation/git-repo.adoc b/Documentation/git-repo.adoc
index 42262c1983..890c34051d 100644
--- a/Documentation/git-repo.adoc
+++ b/Documentation/git-repo.adoc
@@ -104,6 +104,15 @@ values that they return:
`object.format`::
The object format (hash algorithm) used in the repository.
+`path.commondir.absolute`::
+ The canonical absolute path to the Git repository's common
+ directory (the shared `.git` directory containing objects,
+ refs, and global configuration).
+
+`path.commondir.relative`::
+ The path to the Git repository's common directory relative to
+ the current working directory.
+
`references.format`::
The reference storage format. The valid values are:
+
diff --git a/builtin/repo.c b/builtin/repo.c
index 71a5c1c29c..c4cc3bf3fc 100644
--- a/builtin/repo.c
+++ b/builtin/repo.c
@@ -7,12 +7,14 @@
#include "hex.h"
#include "odb.h"
#include "parse-options.h"
+#include "path.h"
#include "path-walk.h"
#include "progress.h"
#include "quote.h"
#include "ref-filter.h"
#include "refs.h"
#include "revision.h"
+#include "setup.h"
#include "strbuf.h"
#include "string-list.h"
#include "shallow.h"
@@ -75,6 +77,28 @@ static int get_object_format(struct repository *repo, struct strbuf *buf)
return 0;
}
+static int get_path_commondir_absolute(struct repository *repo, struct strbuf *buf)
+{
+ const char *common_dir = repo_get_common_dir(repo);
+
+ if (!common_dir)
+ return error(_("unable to get common directory"));
+
+ append_formatted_path(buf, common_dir, startup_info->prefix, PATH_FORMAT_CANONICAL);
+ return 0;
+}
+
+static int get_path_commondir_relative(struct repository *repo, struct strbuf *buf)
+{
+ const char *common_dir = repo_get_common_dir(repo);
+
+ if (!common_dir)
+ return error(_("unable to get common directory"));
+
+ append_formatted_path(buf, common_dir, startup_info->prefix, PATH_FORMAT_RELATIVE);
+ return 0;
+}
+
static int get_references_format(struct repository *repo, struct strbuf *buf)
{
strbuf_addstr(buf,
@@ -87,6 +111,8 @@ static const struct repo_info_field repo_info_field[] = {
{ "layout.bare", get_layout_bare },
{ "layout.shallow", get_layout_shallow },
{ "object.format", get_object_format },
+ { "path.commondir.absolute", get_path_commondir_absolute },
+ { "path.commondir.relative", get_path_commondir_relative },
{ "references.format", get_references_format },
};
diff --git a/t/t1900-repo-info.sh b/t/t1900-repo-info.sh
index 39bb77dda0..09158d29f9 100755
--- a/t/t1900-repo-info.sh
+++ b/t/t1900-repo-info.sh
@@ -155,4 +155,56 @@ test_expect_success 'git repo info -h shows only repo info usage' '
test_grep ! "git repo structure" actual
'
+# Helper function to test path keys in both absolute and relative formats.
+# $1: label for the test
+# $2: field_name (e.g., commondir)
+# $3: expected_dir (the directory name, e.g., .git or custom-common)
+# $4: init_command (extra setup like exporting env vars)
+test_repo_info_path () {
+ label=$1
+ field_name=$2
+ expected_dir=$3
+ init_command=$4
+
+ test_expect_success "absolute: $label" '
+ test_when_finished "rm -rf repo" &&
+ git init repo &&
+ (
+ mkdir -p repo/sub &&
+ cd repo/sub &&
+ ROOT="$(test-tool path-utils real_path ..)" && export ROOT &&
+ eval "$init_command" &&
+ echo "path.$field_name.absolute=$ROOT/$expected_dir" >expect &&
+ git repo info "path.$field_name.absolute" >actual &&
+ test_cmp expect actual
+ )
+ '
+
+ test_expect_success "relative: $label" '
+ test_when_finished "rm -rf repo" &&
+ git init repo &&
+ (
+ mkdir -p repo/sub &&
+ cd repo/sub &&
+ ROOT="$(test-tool path-utils real_path ..)" && export ROOT &&
+ eval "$init_command" &&
+ echo "path.$field_name.relative=../$expected_dir" >expect &&
+ git repo info "path.$field_name.relative" >actual &&
+ test_cmp expect actual
+ )
+ '
+}
+
+test_repo_info_path 'commondir standard' 'commondir' '.git'
+
+test_repo_info_path 'commondir with GIT_COMMON_DIR and GIT_DIR' 'commondir' \
+ 'custom-common' \
+ 'GIT_COMMON_DIR="$ROOT/custom-common" && export GIT_COMMON_DIR &&
+ GIT_DIR="../.git" && export GIT_DIR &&
+ git init --bare "$ROOT/custom-common"'
+
+test_repo_info_path 'commondir with only GIT_DIR' 'commondir' \
+ '.git' \
+ 'GIT_DIR="../.git" && export GIT_DIR'
+
test_done
--
2.54.0
^ permalink raw reply related
* [GSoC Patch v6 4/4] repo: add path.gitdir with absolute and relative suffix formatting
From: K Jayatheerth @ 2026-06-20 3:16 UTC (permalink / raw)
To: git
Cc: jltobler, lucasseikioshiro, gitster, phillip.wood, sandals,
kumarayushjha123, a3205153416, kristofferhaugsbakk, K Jayatheerth
In-Reply-To: <20260620031644.353772-1-jayatheerthkulkarni2005@gmail.com>
Scripts need a stable way to locate the git directory without
parsing rev-parse output or relying on its flag-driven path format
selection. There is no way to retrieve this path from git repo info
today.
Introduce path.gitdir.absolute and path.gitdir.relative keys,
consistent with the path.commondir keys added in the previous patch.
Reuse the test_repo_info_path helper introduced there to validate
both variants.
Mentored-by: Justin Tobler <jltobler@gmail.com>
Mentored-by: Lucas Seiki Oshiro <lucasseikioshiro@gmail.com>
Signed-off-by: K Jayatheerth <jayatheerthkulkarni2005@gmail.com>
---
Documentation/git-repo.adoc | 6 ++++++
builtin/repo.c | 24 ++++++++++++++++++++++++
t/t1900-repo-info.sh | 6 ++++++
3 files changed, 36 insertions(+)
diff --git a/Documentation/git-repo.adoc b/Documentation/git-repo.adoc
index 890c34051d..ed7d80c690 100644
--- a/Documentation/git-repo.adoc
+++ b/Documentation/git-repo.adoc
@@ -113,6 +113,12 @@ values that they return:
The path to the Git repository's common directory relative to
the current working directory.
+`path.gitdir.absolute`::
+ The canonical absolute path to the Git repository directory (the `.git` directory).
+
+`path.gitdir.relative`::
+ The path to the Git repository directory relative to the current working directory.
+
`references.format`::
The reference storage format. The valid values are:
+
diff --git a/builtin/repo.c b/builtin/repo.c
index c4cc3bf3fc..9a312d127a 100644
--- a/builtin/repo.c
+++ b/builtin/repo.c
@@ -99,6 +99,28 @@ static int get_path_commondir_relative(struct repository *repo, struct strbuf *b
return 0;
}
+static int get_path_gitdir_absolute(struct repository *repo, struct strbuf *buf)
+{
+ const char *git_dir = repo_get_git_dir(repo);
+
+ if (!git_dir)
+ return error(_("unable to get git directory"));
+
+ append_formatted_path(buf, git_dir, startup_info->prefix, PATH_FORMAT_CANONICAL);
+ return 0;
+}
+
+static int get_path_gitdir_relative(struct repository *repo, struct strbuf *buf)
+{
+ const char *git_dir = repo_get_git_dir(repo);
+
+ if (!git_dir)
+ return error(_("unable to get git directory"));
+
+ append_formatted_path(buf, git_dir, startup_info->prefix, PATH_FORMAT_RELATIVE);
+ return 0;
+}
+
static int get_references_format(struct repository *repo, struct strbuf *buf)
{
strbuf_addstr(buf,
@@ -113,6 +135,8 @@ static const struct repo_info_field repo_info_field[] = {
{ "object.format", get_object_format },
{ "path.commondir.absolute", get_path_commondir_absolute },
{ "path.commondir.relative", get_path_commondir_relative },
+ { "path.gitdir.absolute", get_path_gitdir_absolute },
+ { "path.gitdir.relative", get_path_gitdir_relative },
{ "references.format", get_references_format },
};
diff --git a/t/t1900-repo-info.sh b/t/t1900-repo-info.sh
index 09158d29f9..ae8c22c817 100755
--- a/t/t1900-repo-info.sh
+++ b/t/t1900-repo-info.sh
@@ -207,4 +207,10 @@ test_repo_info_path 'commondir with only GIT_DIR' 'commondir' \
'.git' \
'GIT_DIR="../.git" && export GIT_DIR'
+test_repo_info_path 'gitdir standard' 'gitdir' '.git'
+
+test_repo_info_path 'gitdir with explicit GIT_DIR' 'gitdir' \
+ '.git' \
+ 'GIT_DIR="../.git" && export GIT_DIR'
+
test_done
--
2.54.0
^ permalink raw reply related
* Re: [PATCH v14 4/6] branch: add --prune-merged <branch>
From: Harald Nordgren @ 2026-06-20 9:04 UTC (permalink / raw)
To: Junio C Hamano
Cc: Phillip Wood, Harald Nordgren via GitGitGadget, git,
Kristoffer Haugsbakk, Johannes Sixt
In-Reply-To: <xmqq33yimsdp.fsf@gitster.g>
> - Move the @{upstream} of feature2 to the branch that "merged"
> feature1 and caused its removal. Asking feature2@{upstream}
> would answer origin/master, which feature1 was removed after
> getting merged.
I think this is a strong option.
As a side note: I was annoyed before when GitHub didn't re-assign base
automatically when doing stacked PR's, so merging in the first branch
caused developers to merge in the second PR into essentially a dead
feature branch instead of master, if they forgot to manually change
it. But I think GitHub has fixed this now so the second PR gets its
base changed to default branch.
Two caveats:
- How to handle recursion: b1 has b2 as upstream and b2 has b3 as
upstream, and both b2 and b3 have been merged? Not good if it's just
luck which order the branches get walked, but also we don't want to
have to do many passes, two passes is not even guaranteed to be
enough.
- What about when b3 has itself as upstream? I guess then we can just
remove the upstream of b2. Overall, I don't think it's a huge problem
when a branch gets no upstream, so maybe just warn about it.
Harald
^ permalink raw reply
* [PATCH v6 0/3] graph: indent visual roots in graph
From: Pablo Sabater @ 2026-06-20 10:11 UTC (permalink / raw)
To: git
Cc: krka, ayu.chandekar, chandrapratap3519, christian.couder, gitster,
jltobler, karthik.188, pabloosabaterr, peff, phillip.wood,
siddharthasthana31
In-Reply-To: <20260613-ps-pre-commit-indent-v5-0-8d308efea63d@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.
There are two main limitations to predict if the next commit will be a
visual root candidate:
1. The peek only gives us the next entry reliably, we cannot see past it
reliably in order.
2. Even if we could peek past in order, its parents might not have been
simplified yet, so a future commit that will become a visual root is
not detected as a visual root in peek-time.
This causes the cascading to not be set and result in a extra
indentation. For example:
Given:
* A unrelated (visual root)
* B child of C
* C visual root WILL BE FILTERED OUT
* D unrelated (visual root)
The actual output is:
* A
* B
* D
But we wanted:
* A
* B
* D
A test has been added to t4218 and a NEEDSWORK to the lookahead function
to document this edge case but I'm not that familiar with revision.c.
Maybe there's a better way to make the lookahead more reliable.
[1]: https://lore.kernel.org/git/xmqqwnwajbuj.fsf@gitster.c.googlers.com/
V5 DIFF:
- Added new commit with lookahead functions to abstract the commit
traverse to the graph. Changed the lookahead function from graph to
call this new functions.
- Added new test with two unrelated branches with merges.
- Fixed test_expect_failure to have the correct expected output.
- Simplified the NEEDSWORK.
Signed-off-by: Pablo Sabater <pabloosabaterr@gmail.com>
---
Pablo Sabater (3):
lib-log-graph: move check_graph function
revision: add peek functions for lookahead
graph: indent visual root in graph
graph.c | 271 +++++++++++++++++
revision.c | 38 +++
revision.h | 10 +
t/lib-log-graph.sh | 5 +
t/meson.build | 1 +
t/t4215-log-skewed-merges.sh | 33 +-
t/t4218-log-graph-indentation.sh | 468 +++++++++++++++++++++++++++++
t/t6016-rev-list-graph-simplify-history.sh | 25 +-
8 files changed, 817 insertions(+), 34 deletions(-)
---
base-commit: 95e20213faefeb95df29277c58ac1980ab68f701
change-id: 20260612-ps-pre-commit-indent-39ca72816382
Best regards,
--
Pablo Sabater <pabloosabaterr@gmail.com>
^ permalink raw reply
* [PATCH v6 1/3] lib-log-graph: move check_graph function
From: Pablo Sabater @ 2026-06-20 10:11 UTC (permalink / raw)
To: git
Cc: krka, ayu.chandekar, chandrapratap3519, christian.couder, gitster,
jltobler, karthik.188, pabloosabaterr, peff, phillip.wood,
siddharthasthana31
In-Reply-To: <20260620-ps-pre-commit-indent-v6-0-cdc6d8fd5fbc@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 v6 2/3] revision: add peek functions for lookahead
From: Pablo Sabater @ 2026-06-20 10:11 UTC (permalink / raw)
To: git
Cc: krka, ayu.chandekar, chandrapratap3519, christian.couder, gitster,
jltobler, karthik.188, pabloosabaterr, peff, phillip.wood,
siddharthasthana31, Kristofer Karlsson
In-Reply-To: <20260620-ps-pre-commit-indent-v6-0-cdc6d8fd5fbc@gmail.com>
The graph code in a subsequent commit needs to be able to look ahead in
order to set indentation-related flags.
Using revs->commits is brittle and the data structure that holds the
pending commits might change in the future.
Add two functions that abstract this for the graph.
Helped-by: Kristofer Karlsson <stoansen@gmail.com>
Signed-off-by: Pablo Sabater <pabloosabaterr@gmail.com>
---
revision.c | 38 ++++++++++++++++++++++++++++++++++++++
revision.h | 10 ++++++++++
2 files changed, 48 insertions(+)
diff --git a/revision.c b/revision.c
index e91d7e1f11..a472a28853 100644
--- a/revision.c
+++ b/revision.c
@@ -3708,6 +3708,44 @@ static unsigned int count_explore_walked;
static unsigned int count_indegree_walked;
static unsigned int count_topo_walked;
+struct commit *revision_peek_next_commit (struct rev_info *revs)
+{
+ struct topo_walk_info *info = revs->topo_walk_info;
+
+ if (info)
+ return prio_queue_peek(&info->topo_queue);
+ if (revs->commits)
+ return revs->commits->item;
+
+ return NULL;
+}
+
+int revision_has_commits_after (struct rev_info *revs, int n)
+{
+ struct topo_walk_info *info = revs->topo_walk_info;
+
+ if (info) {
+ int visible = 0;
+ for (size_t i = 0; i < info->topo_queue.nr && visible < n; i++) {
+ struct commit *c = info->topo_queue.array[i].data;
+ if (get_commit_action(revs, c) == commit_show)
+ visible++;
+ }
+ return visible > n-1;
+ }
+ if (revs->commits) {
+ struct commit_list *cl;
+ int visible = 0;
+ for (cl = revs->commits; cl && visible < n; cl = cl->next) {
+ if (get_commit_action(revs, cl->item) == commit_show)
+ visible++;
+ }
+ return visible > n-1;
+ }
+
+ return 0;
+}
+
static void trace2_topo_walk_statistics_atexit(void)
{
struct json_writer jw = JSON_WRITER_INIT;
diff --git a/revision.h b/revision.h
index 00c392be37..a10c6b0940 100644
--- a/revision.h
+++ b/revision.h
@@ -572,4 +572,14 @@ int rewrite_parents(struct rev_info *revs,
*/
struct commit_list *get_saved_parents(struct rev_info *revs, const struct commit *commit);
+/*
+ * Peek into revision's next commit without consuming it.
+ */
+struct commit *revision_peek_next_commit(struct rev_info *revs);
+
+/*
+ * Check if there are n more commits to be shown yet.
+ */
+int revision_has_commits_after(struct rev_info *revs, int n);
+
#endif
--
2.54.0
^ permalink raw reply related
* [PATCH v6 3/3] graph: indent visual root in graph
From: Pablo Sabater @ 2026-06-20 10:11 UTC (permalink / raw)
To: git
Cc: krka, ayu.chandekar, chandrapratap3519, christian.couder, gitster,
jltobler, karthik.188, pabloosabaterr, peff, phillip.wood,
siddharthasthana31
In-Reply-To: <20260620-ps-pre-commit-indent-v6-0-cdc6d8fd5fbc@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.
There are two main limitations to predict if the next commit will be a
visual root candidate:
1. The peek only gives us the next entry reliably, we cannot see past it
reliably in order.
2. Even if we could peek past in order, its parents might not have been
simplified yet, so a future commit that will become a visual root is
not detected as a visual root in peek-time.
This causes the cascading to not be set and result in a extra
indentation. For example:
Given:
* A unrelated (visual root)
* B child of C
* C visual root WILL BE FILTERED OUT
* D unrelated (visual root)
The actual output is:
* A
* B
* D
But we wanted:
* A
* B
* D
The output isn't broken as unrelated commits are successfully separated
by indentation, but an indent level should have been avoided.
Create a new test file for graph indentations test called
't4218-log-graph-indentation.sh'.
The filtered parents edge case is documented as a NEEDSWORK on the
lookahead function and it has its own 'test_expect_failure' at 't4218'.
[1]: https://lore.kernel.org/git/xmqqwnwajbuj.fsf@gitster.c.googlers.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 | 271 +++++++++++++++++++++++
t/meson.build | 1 +
t/t4218-log-graph-indentation.sh | 468 +++++++++++++++++++++++++++++++++++++++
3 files changed, 740 insertions(+)
diff --git a/graph.c b/graph.c
index 842282685f..7263aa6283 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 is_merge_parent:1;
};
enum graph_state {
GRAPH_PADDING,
GRAPH_SKIP,
GRAPH_PRE_COMMIT,
+ GRAPH_PRE_ROOT,
GRAPH_COMMIT,
GRAPH_POST_MERGE,
GRAPH_COLLAPSING
@@ -315,6 +326,48 @@ struct git_graph {
* diff_output_prefix_callback().
*/
struct strbuf prefix_buf;
+
+ /*
+ * If a commit is a visual root, we need to indent it to prevent
+ * unrelated commits from being vertically adjacent to it.
+ */
+ unsigned 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 visual_root_cascade:1;
+
+ /*
+ * Set when the current commit was already present in graph->columns
+ * before being processed.
+ */
+ unsigned 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)
@@ -388,6 +441,8 @@ struct git_graph *graph_init(struct rev_info *opt)
graph->num_columns = 0;
graph->num_new_columns = 0;
graph->mapping_size = 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.
@@ -561,6 +616,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;
@@ -572,6 +632,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) {
@@ -610,6 +671,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)
@@ -701,10 +768,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
*/
@@ -763,9 +840,144 @@ static int graph_needs_pre_commit_line(struct git_graph *graph)
graph->expansion_row < graph_num_expansion_rows(graph);
}
+/*
+ * 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.
+ *
+ * - 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)
+{
+ return c->parents == NULL && !(c->object.flags & BOUNDARY);
+}
+
+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->commit_in_columns &&
+ graph->columns[graph->commit_index].is_merge_parent) &&
+ flags->is_next_visible &&
+ (!flags->next_has_column || graph->visual_root_depth > 0);
+}
+
+/*
+ * Iterates the commits queue searching for the next visible commit, once found
+ * sets visibleness and visual-root flags.
+ * Knowing if the next commit is also a visual root avoids redundant indentations
+ *
+ * NEEDSWORK: There are two main limitations to predict if the next commit will be
+ * a visual root candidate:
+ *
+ * 1. The peek only gives us the next entry reliably, we cannot see past it
+ * reliably in order.
+ *
+ * 2. Even if we could peek past in order, its parents might not have been
+ * simplified yet, so a future commit that will become a visual root is
+ * not detected as a visual root in peek-time.
+ *
+ * This results in a redundant indentation.
+ *
+ * See 'test_expect_failure' at t4218-log-graph-indentation.sh.
+ */
+static void graph_peek_next_visible(struct git_graph *graph,
+ struct graph_lookahead_flags *flags)
+{
+ struct commit *next;
+
+ flags->is_next_visible = 0;
+ flags->is_next_visual_root = 0;
+ flags->next_has_column = 0;
+
+ next = revision_peek_next_commit(graph->revs);
+ if (!next)
+ return;
+
+ if (get_commit_action(graph->revs, next) != commit_show) {
+ /*
+ * next commit won't be shown but there could be a visible
+ * commit still.
+ */
+ if (revision_has_commits_after(graph->revs, 1))
+ flags->is_next_visible = 1;
+ return;
+ }
+
+ flags->is_next_visible = 1;
+ flags->next_has_column = graph_find_new_column_by_commit(graph, next) >= 0;
+
+ if (!graph_is_visual_root_candidate(next))
+ return;
+ /*
+ * Next commit is a visual root candidate but we don't want the last
+ * commit to get indented, check if its not the last visible commit
+ *
+ * We do not need graph->commit_in_columns or is_merge_parent,
+ * because we only need to know whether the next one might be a
+ * visual root, affecting the current commit where the cascade
+ * would have to be set and the first visual root not indented.
+ *
+ * It will set next_is_visual_root to true for merge parents that
+ * graph_is_visual_root() would return false, but if the next is
+ * a merge parent, the current commit is the child and cannot
+ * be a visual root and therefore having no effect.
+ */
+ if (revision_has_commits_after(graph->revs, 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
@@ -796,6 +1008,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;
/*
@@ -813,11 +1042,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
@@ -1065,6 +1299,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)) {
@@ -1436,6 +1681,29 @@ 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 should only be called on a
+ * visual root.
+ */
+ assert(graph->is_visual_root);
+
+ for (size_t 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;
@@ -1461,6 +1729,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 3219264fe7..6093ff469b 100644
--- a/t/meson.build
+++ b/t/meson.build
@@ -576,6 +576,7 @@ integration_tests = [
't4215-log-skewed-merges.sh',
't4216-log-bloom.sh',
't4217-log-limit.sh',
+ 't4218-log-graph-indentation.sh',
't4252-am-options.sh',
't4253-am-keep-cr-dos.sh',
't4254-am-corrupt.sh',
diff --git a/t/t4218-log-graph-indentation.sh b/t/t4218-log-graph-indentation.sh
new file mode 100755
index 0000000000..005ad7c30c
--- /dev/null
+++ b/t/t4218-log-graph-indentation.sh
@@ -0,0 +1,468 @@
+#!/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" &&
+ { git rm -rf . || true; }
+}
+
+# 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
+'
+
+# When a commit's parent will be filtered, the lookahead cannot reliably predict
+# if the next commit will be shown because the filtering has not happened yet at
+# peek-time. This makes cascade to not be set causing an extra indentation.
+#
+# Expected:
+#
+# A
+# B
+# D
+#
+# Output:
+#
+# A
+# B
+# D
+#
+# This will happen for any case where we find ourselves with the next commit
+# being a unrelated child of a parent that will be filtered.
+#
+# instead of the expected:
+test_expect_failure 'filtered parent cascading edge case' '
+ create_orphan _25 &&
+ echo test >other.txt &&
+ git add other.txt &&
+ git commit -m "C-filtered" &&
+
+ echo test >foo.txt &&
+ git add foo.txt &&
+ git commit -m "B (child of filtered)" &&
+
+ create_orphan _26 &&
+ echo test >foo.txt &&
+ git add foo.txt &&
+ git commit -m "A (visual root)" &&
+
+ create_orphan _27 &&
+ echo test >foo.txt &&
+ git add foo.txt &&
+ git commit -m "D (last)" &&
+
+ lib_test_check_graph _25 _26 _27 -- foo.txt <<-\EOF
+ * B (child of filtered)
+ * A (visual root)
+ * D (last)
+ EOF
+'
+
+test_expect_failure '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
+'
+
+# This 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 childs' '
+ (
+ 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_done
--
2.54.0
^ permalink raw reply related
* Re: [PATCH v6 2/3] revision: add peek functions for lookahead
From: Pablo Sabater @ 2026-06-20 10:18 UTC (permalink / raw)
To: git
Cc: krka, ayu.chandekar, chandrapratap3519, christian.couder, gitster,
jltobler, karthik.188, peff, phillip.wood, siddharthasthana31,
Kristofer Karlsson
In-Reply-To: <20260620-ps-pre-commit-indent-v6-2-cdc6d8fd5fbc@gmail.com>
El sáb, 20 jun 2026 a las 12:12, Pablo Sabater
(<pabloosabaterr@gmail.com>) escribió:
>
> The graph code in a subsequent commit needs to be able to look ahead in
> order to set indentation-related flags.
>
> Using revs->commits is brittle and the data structure that holds the
> pending commits might change in the future.
>
> Add two functions that abstract this for the graph.
>
> Helped-by: Kristofer Karlsson <stoansen@gmail.com>
> Signed-off-by: Pablo Sabater <pabloosabaterr@gmail.com>
The email on the trailer is wrong, sorry Kristofer, I'll fix it in the
next version.
Regards,
Pablo
^ permalink raw reply
* [PATCH/RFC 0/6] commit-reach: terminate merge-base walk when one side is exhausted
From: Kristofer Karlsson via GitGitGadget @ 2026-06-20 10:36 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson
Hi,
This follows up on my RFC [1] with a concrete proposal. I expect the design
to still be scrutinized, but that may be easier with actual code to look at.
I tried to make this easier to review by splitting into atomic patches. The
first two patches are the meatiest parts, though they are pure refactoring.
The behavior change is in patch 3 and is in itself quite small. The last
patch adds technical documentation to support future development.
----------------------------------------------------------------------------
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 4 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 layout:
1/6 commit-reach: decouple ahead_behind from nonstale_queue 2/6
commit-reach: introduce paint_queue and per-side counters 3/6 commit-reach:
stop the walk when one side is exhausted 4/6 t6600: add side-exhaustion
edge-case tests 5/6 t6099, t6600: add side-exhaustion regression tests 6/6
Documentation/technical: document paint_down_to_common()
Benchmarks
Measured on a 2.6M-commit monorepo with commit-graph (baseline v2.55-rc1):
merge-base --all (across import) 4.293s -> 8ms (537x)
merge-tree (across import) 5.345s -> 13ms (411x)
merge-base --all (1000 commits apart) 5.404s -> 7ms (772x)
No regression on linux.git (1.4M commits, commit-graph):
merge-base HEAD HEAD~1000 38ms -> 40ms
merge-base --all HEAD HEAD~1000 87ms -> 36ms
merge-base --is-ancestor HEAD~1000 HEAD 11ms -> 11ms
merge-base --all HEAD HEAD~10000 626ms -> 428ms
[1]
https://lore.kernel.org/git/CAL71e4Ps-2_0+uuZu43N9pFnXBemoAohPs_eyRJf8taXHJPAXQ@mail.gmail.com/T/#u
[2] https://github.com/gitgitgadget/git/pull/2150
Elijah Newren (1):
t6600: add test cases for side-exhaustion edge cases
Kristofer Karlsson (5):
commit-reach: decouple ahead_behind from nonstale_queue
commit-reach: introduce struct paint_queue with per-side counters
commit-reach: terminate merge-base walk when one paint side is
exhausted
t6099, t6600: add side-exhaustion regression tests
Documentation/technical: add paint-down-to-common doc
Documentation/Makefile | 1 +
Documentation/technical/meson.build | 1 +
.../technical/paint-down-to-common.adoc | 130 ++++++++++++++
commit-reach.c | 159 +++++++++++-------
t/meson.build | 1 +
t/t6099-merge-base-side-exhaustion.sh | 82 +++++++++
t/t6600-test-reach.sh | 136 +++++++++++++++
7 files changed, 451 insertions(+), 59 deletions(-)
create mode 100644 Documentation/technical/paint-down-to-common.adoc
create mode 100755 t/t6099-merge-base-side-exhaustion.sh
base-commit: 8d96f09e9245ddf80c1981476fcbac8c4bb4125f
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-2149%2Fspkrka%2Fside-exhaust-pr-v1
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-2149/spkrka/side-exhaust-pr-v1
Pull-Request: https://github.com/gitgitgadget/git/pull/2149
--
gitgitgadget
^ permalink raw reply
* [PATCH/RFC 1/6] commit-reach: decouple ahead_behind from nonstale_queue
From: Kristofer Karlsson via GitGitGadget @ 2026-06-20 10:36 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.git.1781951820.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Move ahead_behind() off the shared nonstale_queue abstraction to use
a plain prio_queue with a local max_nonstale pointer. The nonstale
tracking is inlined into insert_no_dup().
This prepares for replacing nonstale_queue with a paint_queue struct
that tracks per-side commit counts, which ahead_behind() does not
need. No behavior change.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
commit-reach.c | 32 +++++++++++++++++++++-----------
1 file changed, 21 insertions(+), 11 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c
index 5df471a313..377a5cc42a 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -1089,12 +1089,18 @@ struct commit_list *get_reachable_subset(struct commit **from, size_t nr_from,
define_commit_slab(bit_arrays, struct bitmap *);
static struct bit_arrays bit_arrays;
-static void insert_no_dup(struct nonstale_queue *queue, struct commit *c)
+static void insert_no_dup(struct prio_queue *queue,
+ struct commit **max_nonstale,
+ struct commit *c)
{
if (c->object.flags & PARENT2)
return;
- nonstale_queue_put(queue, c);
c->object.flags |= PARENT2;
+ prio_queue_put(queue, c);
+ if (!(c->object.flags & STALE) &&
+ (!*max_nonstale ||
+ queue->compare(*max_nonstale, c, queue->cb_data) <= 0))
+ *max_nonstale = c;
}
static struct bitmap *get_bit_array(struct commit *c, int width)
@@ -1118,9 +1124,10 @@ void ahead_behind(struct repository *r,
struct commit **commits, size_t commits_nr,
struct ahead_behind_count *counts, size_t counts_nr)
{
- struct nonstale_queue queue = {
- { .compare = compare_commits_by_gen_then_commit_date }
+ struct prio_queue queue = {
+ .compare = compare_commits_by_gen_then_commit_date
};
+ struct commit *max_nonstale = NULL;
size_t width = DIV_ROUND_UP(commits_nr, BITS_IN_EWORD);
if (!commits_nr || !counts_nr)
@@ -1140,14 +1147,17 @@ void ahead_behind(struct repository *r,
struct bitmap *bitmap = get_bit_array(c, width);
bitmap_set(bitmap, i);
- insert_no_dup(&queue, c);
+ insert_no_dup(&queue, &max_nonstale, c);
}
- while (queue.max_nonstale) {
- struct commit *c = nonstale_queue_get(&queue);
+ while (max_nonstale) {
+ struct commit *c = prio_queue_get(&queue);
struct commit_list *p;
struct bitmap *bitmap_c = get_bit_array(c, width);
+ if (c == max_nonstale)
+ max_nonstale = NULL;
+
for (size_t i = 0; i < counts_nr; i++) {
int reach_from_tip = !!bitmap_get(bitmap_c, counts[i].tip_index);
int reach_from_base = !!bitmap_get(bitmap_c, counts[i].base_index);
@@ -1178,7 +1188,7 @@ void ahead_behind(struct repository *r,
if (bitmap_popcount(bitmap_p) == commits_nr)
p->item->object.flags |= STALE;
- insert_no_dup(&queue, p->item);
+ insert_no_dup(&queue, &max_nonstale, p->item);
}
free_bit_array(c);
@@ -1186,10 +1196,10 @@ void ahead_behind(struct repository *r,
/* STALE is used here, PARENT2 is used by insert_no_dup(). */
repo_clear_commit_marks(r, PARENT2 | STALE);
- for (size_t i = 0; i < queue.pq.nr; i++)
- free_bit_array(queue.pq.array[i].data);
+ for (size_t i = 0; i < queue.nr; i++)
+ free_bit_array(queue.array[i].data);
clear_bit_arrays(&bit_arrays);
- clear_nonstale_queue(&queue);
+ clear_prio_queue(&queue);
}
struct commit_and_index {
--
gitgitgadget
^ permalink raw reply related
* [PATCH/RFC 2/6] commit-reach: introduce struct paint_queue with per-side counters
From: Kristofer Karlsson via GitGitGadget @ 2026-06-20 10:36 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.git.1781951820.gitgitgadget@gmail.com>
From: Kristofer Karlsson <krka@spotify.com>
Replace the nonstale_queue abstraction in paint_down_to_common() with
a new paint_queue struct that tracks per-side commit counts. 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_transition() which handles
all flag changes as bucket transfers: remove from the old bucket, add
to the new one. Either step is a no-op when the respective state has
no bucket (stale or zero).
The loop now drains the queue via paint_queue_get() and breaks when
all counters reach zero, replacing the old pointer-based termination
(max_nonstale). This is equivalent behavior.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
commit-reach.c | 114 ++++++++++++++++++++++++++++---------------------
1 file changed, 66 insertions(+), 48 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c
index 377a5cc42a..ba1e896f0f 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -41,58 +41,75 @@ static int compare_commits_by_gen(const void *_a, const void *_b)
}
/*
- * A prio_queue with O(1) termination check. 'max_nonstale' tracks
- * the lowest-priority non-stale commit enqueued so far; once it is
- * popped, every remaining entry is known to be STALE.
+ * 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 nonstale_queue {
+struct paint_queue {
struct prio_queue pq;
- struct commit *max_nonstale;
+ int p1_count;
+ int p2_count;
+ int pending_merge_bases;
};
-static void nonstale_queue_put(struct nonstale_queue *queue,
- struct commit *c)
+/*
+ * Adjust per-side counters for a paint-state transition. Non-stale
+ * commits are counted in one of three counters: PARENT1-only,
+ * PARENT2-only, or both. Zero means "not in the queue" (used on
+ * enqueue/dequeue); stale commits are not counted at all.
+ */
+static void paint_count_transition(struct paint_queue *queue,
+ unsigned old_flags, unsigned new_flags)
{
- struct commit *old = queue->max_nonstale;
+ unsigned old_paint = old_flags & (PARENT1 | PARENT2 | STALE);
+ unsigned new_paint = new_flags & (PARENT1 | PARENT2 | STALE);
- prio_queue_put(&queue->pq, c);
- if (c->object.flags & STALE)
+ if (old_paint == new_paint)
return;
- if (!old || queue->pq.compare(old, c, queue->pq.cb_data) <= 0)
- queue->max_nonstale = c;
-}
-
-static struct commit *nonstale_queue_get(struct nonstale_queue *queue)
-{
- struct commit *commit = prio_queue_get(&queue->pq);
- if (commit == queue->max_nonstale)
- queue->max_nonstale = NULL;
-
- return commit;
+ if (!(old_paint & STALE)) {
+ switch (old_paint & (PARENT1 | PARENT2)) {
+ case 0: break;
+ case PARENT1: queue->p1_count--; break;
+ case PARENT2: queue->p2_count--; break;
+ case PARENT1 | PARENT2: queue->pending_merge_bases--; break;
+ default: BUG("unexpected paint state");
+ }
+ }
+ if (!(new_paint & STALE)) {
+ switch (new_paint & (PARENT1 | PARENT2)) {
+ case 0: break;
+ case PARENT1: queue->p1_count++; break;
+ case PARENT2: queue->p2_count++; break;
+ case PARENT1 | PARENT2: queue->pending_merge_bases++; break;
+ default: BUG("unexpected paint state");
+ }
+ }
}
-static void clear_nonstale_queue(struct nonstale_queue *queue)
+static void paint_queue_put(struct paint_queue *queue,
+ struct commit *c, unsigned add_flags)
{
- clear_prio_queue(&queue->pq);
- queue->max_nonstale = NULL;
-}
+ unsigned old_flags = c->object.flags;
+ c->object.flags |= add_flags;
-static void nonstale_queue_put_dedup(struct nonstale_queue *queue,
- struct commit *c)
-{
- if (c->object.flags & ENQUEUED)
- return;
- c->object.flags |= ENQUEUED;
- nonstale_queue_put(queue, c);
+ if (old_flags & ENQUEUED) {
+ paint_count_transition(queue, old_flags, c->object.flags);
+ } else {
+ c->object.flags |= ENQUEUED;
+ prio_queue_put(&queue->pq, c);
+ paint_count_transition(queue, 0, c->object.flags);
+ }
}
-static struct commit *nonstale_queue_get_dedup(struct nonstale_queue *queue)
+static struct commit *paint_queue_get(struct paint_queue *queue)
{
- struct commit *commit = nonstale_queue_get(queue);
+ struct commit *commit = prio_queue_get(&queue->pq);
- if (commit)
+ if (commit) {
commit->object.flags &= ~ENQUEUED;
+ paint_count_transition(queue, commit->object.flags, 0);
+ }
return commit;
}
@@ -104,9 +121,10 @@ 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_queue queue = {
+ .pq = { compare_commits_by_gen_then_commit_date }
};
+ struct commit *commit;
int i;
timestamp_t last_gen = GENERATION_NUMBER_INFINITY;
struct commit_list **tail = result;
@@ -119,15 +137,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(&queue, 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(&queue, twos[i], PARENT2);
- while (queue.max_nonstale) {
- struct commit *commit = nonstale_queue_get_dedup(&queue);
+ while ((commit = paint_queue_get(&queue))) {
struct commit_list *parents;
int flags;
timestamp_t generation = commit_graph_generation(commit);
@@ -165,7 +180,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(&queue.pq);
commit_list_free(*result);
*result = NULL;
/*
@@ -180,12 +195,15 @@ 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(&queue, p, flags);
}
+
+ if (queue.p1_count + queue.p2_count +
+ queue.pending_merge_bases == 0)
+ break;
}
- clear_nonstale_queue(&queue);
+ clear_prio_queue(&queue.pq);
commit_list_sort_by_date(result);
return 0;
}
--
gitgitgadget
^ permalink raw reply related
* [PATCH/RFC 3/6] commit-reach: terminate merge-base walk when one paint side is exhausted
From: Kristofer Karlsson via GitGitGadget @ 2026-06-20 10:36 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.git.1781951820.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 in the previous commit. 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 popped 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.
On large repositories with commit-graph, this yields 100-1000x
speedups for merge-base queries where one side (e.g. a PR branch) is
much smaller than the other.
Helped-by: Derrick Stolee <stolee@gmail.com>
Helped-by: Elijah Newren <newren@gmail.com>
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
commit-reach.c | 13 +++++++++++++
1 file changed, 13 insertions(+)
diff --git a/commit-reach.c b/commit-reach.c
index ba1e896f0f..fcd1ad0167 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -201,6 +201,19 @@ static int paint_down_to_common(struct repository *r,
if (queue.p1_count + queue.p2_count +
queue.pending_merge_bases == 0)
break;
+
+ /*
+ * Side exhaustion: a new merge-base can only form
+ * when both PARENT1-only and PARENT2-only commits
+ * remain in the queue. In the finite-generation
+ * region the queue is ordered topologically, so
+ * no future step can add paint to visited commits
+ * and an exhausted side cannot reappear.
+ */
+ if (generation < GENERATION_NUMBER_INFINITY &&
+ queue.pending_merge_bases == 0 &&
+ (queue.p1_count == 0 || queue.p2_count == 0))
+ break;
}
clear_prio_queue(&queue.pq);
--
gitgitgadget
^ permalink raw reply related
* [PATCH/RFC 4/6] t6600: add test cases for side-exhaustion edge cases
From: Elijah Newren via GitGitGadget @ 2026-06-20 10:36 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson, Elijah Newren
In-Reply-To: <pull.2149.git.1781951820.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 | 111 ++++++++++++++++++++++++++++++++++++++++++
1 file changed, 111 insertions(+)
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index b5b314e570..775c077c87 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -49,6 +49,62 @@ test_expect_success 'setup' '
git tag -a -m "$x-$i" tag-$x-$i commit-$x-$i || return 1
done
done &&
+
+ # 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 &&
@@ -146,6 +202,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
@@ -183,6 +249,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/RFC 5/6] t6099, t6600: add side-exhaustion regression tests
From: Kristofer Karlsson via GitGitGadget @ 2026-06-20 10:36 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.git.1781951820.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 +++++++++++++++++++++++++++
t/t6600-test-reach.sh | 25 ++++++++
3 files changed, 108 insertions(+)
create mode 100755 t/t6099-merge-base-side-exhaustion.sh
diff --git a/t/meson.build b/t/meson.build
index 3219264fe7..ee6ebdffb9 100644
--- a/t/meson.build
+++ b/t/meson.build
@@ -786,6 +786,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..bae3ea7f83
--- /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
diff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh
index 775c077c87..f5560b0c1c 100755
--- a/t/t6600-test-reach.sh
+++ b/t/t6600-test-reach.sh
@@ -294,6 +294,31 @@ test_expect_success 'get_merge_bases_many:infinity-both-sides' '
test_all_modes get_merge_bases_many
'
+test_expect_success 'setup mixed finite/INFINITY topology' '
+ # Create a commit outside all saved commit-graph files so it always
+ # has INFINITY generation, while its parent (ps-X) is in the graph
+ # with a finite generation. Use the ps-* orphan topology so we do
+ # not pollute the grid-based rev-list tests.
+ git checkout ps-X &&
+ test_env GIT_TEST_COMMIT_GRAPH= test_commit pm-INF
+'
+
+test_expect_success 'get_merge_bases_many:mixed-finite-infinity' '
+ # One tip (pm-INF) is outside the commit-graph with INFINITY
+ # generation; the other (ps-B) is in the graph with finite
+ # generation. The walk starts in the INFINITY region and crosses
+ # into the finite region where side-exhaustion can fire.
+ cat >input <<-\EOF &&
+ A:pm-INF
+ X:ps-B
+ EOF
+ {
+ echo "get_merge_bases_many(A,X):" &&
+ git rev-parse ps-X
+ } >expect &&
+ test_all_modes get_merge_bases_many
+'
+
test_expect_success 'reduce_heads' '
cat >input <<-\EOF &&
X:commit-1-10
--
gitgitgadget
^ permalink raw reply related
* [PATCH/RFC 6/6] Documentation/technical: add paint-down-to-common doc
From: Kristofer Karlsson via GitGitGadget @ 2026-06-20 10:36 UTC (permalink / raw)
To: git; +Cc: Derrick Stolee, Elijah Newren, Kristofer Karlsson,
Kristofer Karlsson
In-Reply-To: <pull.2149.git.1781951820.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.
Signed-off-by: Kristofer Karlsson <krka@spotify.com>
---
Documentation/Makefile | 1 +
Documentation/technical/meson.build | 1 +
.../technical/paint-down-to-common.adoc | 130 ++++++++++++++++++
3 files changed, 132 insertions(+)
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..e677cce84d
--- /dev/null
+++ b/Documentation/technical/paint-down-to-common.adoc
@@ -0,0 +1,130 @@
+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 (falling
+back to commit date when generation numbers are unavailable). Each
+step dequeues the highest-priority commit (this is when we say a
+commit is "visited") and propagates its paint flags to its parents,
+enqueuing them if they gained new flags. When a commit receives
+both PARENT1 and PARENT2, it is a merge-base candidate. A candidate
+gains the STALE flag so its ancestors propagate staleness -- any
+deeper common ancestor is necessarily redundant.
+
+INFINITY and finite generation 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:
+
+....
+ +---------------------------------------+
+ | 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
+-----------
+
+Termination happens when we can prove that no extra progress is
+possible. We are done with the main loop when one of the following
+conditions holds:
+
+ 1. The queue is empty.
+ 2. The queue only contains STALE entries.
+ 3. Side-exhaustion: the walk has reached the finite region and one
+ of the sides is fully exhausted.
+
+The loop waits for all pending merge-base candidates to be popped
+and recorded before any early exit fires, so no separate drain phase
+is needed after termination.
+
+Stale entry condition
+~~~~~~~~~~~~~~~~~~~~~
+If all entries are stale we cannot find any new merge bases since
+that requires at least one enqueued side node meeting the other side.
+However, we could still invalidate merge bases (if there are more
+than one). This is unnecessary since `remove_redundant()` will clean
+that up as a post-process step.
+
+Side-exhaustion
+~~~~~~~~~~~~~~~
+A commit is *exclusive* to one side if it carries that side's paint
+but not the other (e.g. PARENT1 without PARENT2).
+
+If we have reached the finite region of the graph, no future
+traversal step can add paint to an already-visited commit. Thus if
+there are no exclusive PARENT2 commits in the queue, no additional
+PARENT2 paint can be introduced into the walk. Even if exclusive
+PARENT1 commits remain, no new merge-base candidates can be
+discovered. The same holds symmetrically for PARENT1.
+
+This invariant is only valid in the finite region of the graph.
+
+Related documentation
+---------------------
+
+ - `Documentation/technical/commit-graph.adoc` -- generation numbers
+ and the reachability closure property.
--
gitgitgadget
^ permalink raw reply related
* Re: [PATCH v4 0/1] environment: move protect_hfs and protect_ntfs into repo_config_values
From: Tian Yuchen @ 2026-06-20 13:38 UTC (permalink / raw)
To: Junio C Hamano
Cc: git, Christian Couder, Ayush Chandekar, Olamide Caleb Bello
In-Reply-To: <xmqqjyrujvco.fsf@gitster.g>
On 6/20/26 01:25, Junio C Hamano wrote:
> Junio C Hamano <gitster@pobox.com> writes:
>
>> diff --git c/environment.h w/environment.h
>> index fdd9775900..b1ae4a70de 100644
>> --- c/environment.h
>> +++ w/environment.h
>> @@ -127,8 +127,8 @@ int git_default_core_config(const char *var, const char *value,
>>
>> /*
>> * Getters for the `protect_hfs` and `protect_ntfs` fields of `struct repo_config_values`.
>> - * They check `repo->gitdir` to prevent calling repo_config_values()
>> - * before the configuration is loaded or in bare environments.
>> + * They check `repo->initialized` to prevent calling `repo_config_values()`
>> + * before the repository setup is fully complete or in non-git environments.
>> */
>> int repo_protect_hfs(struct repository *repo);
>> int repo_protect_ntfs(struct repository *repo);
>
> Another thing we should remember (but should *NOT* do while these
> topics are still in flight) to do is to consolidate these comments
> into one. The hfs and htfs getters are covered by the same single
> comment, but ignorecase and trustexecutable bit getters have their
> own comments, only because they came in different topics. We should
> conslidate them into a single comment block once all of these have
> landed in 'master', which may happen soon after 2.55 final gets
> tagged.
>
I understand. I’ll send the hfs/ntfs fix patch right away, and will
clean up the comments once all of the associated patches (there will be
more in the next few weeks) have been merged into master. ;)
Thanks, yuchen
^ permalink raw reply
* Re: [PATCH v3] SubmittingPatches: address design critiques
From: Junio C Hamano @ 2026-06-20 14:09 UTC (permalink / raw)
To: Michael Montalbo; +Cc: code, git
In-Reply-To: <CAC2Qwm+WcGkd9pAV5=JL1hfCDRisGQRFmdfOsMTrMWyx7aa65A@mail.gmail.com>
Michael Montalbo <mmontalbo@gmail.com> writes:
> Slight reflow suggestions:
>
> Defend your design decisions on the list first; work with reviewers and
> other members to improve the design before revising the implementation.
> This will avoid wasting effort on an implementation before its design is
> solid.
Yeah, making the last part a separate sentence does make it much
easier to follow. Will use.
Thanks.
^ permalink raw reply
* [PATCH] environment: use 'repo->initialized' for repo_protect_hfs() and repo_protect_ntfs()
From: Tian Yuchen @ 2026-06-20 14:09 UTC (permalink / raw)
To: git; +Cc: Tian Yuchen, Christian Couder, Ayush Chandekar,
Olamide Caleb Bello
In-Reply-To: <xmqqo6h6jvuk.fsf@gitster.g>
To match how we refrain from calling repo_config_values() on an
uninitialized instance of a repository object in other two topics
that deal with ignore_case and trust_executable_bit, check the
repo->initialized bit instead of the repo->gitdir member.
Base commit: 43192e7977f5f05138abcdb3212a3f87ab513bef
Mentored-by: Christian Couder <christian.couder@gmail.com>
Mentored-by: Ayush Chandekar <ayu.chandekar@gmail.com>
Mentored-by: Olamide Caleb Bello <belkid98@gmail.com>
Signed-off-by: Tian Yuchen <cat@malon.dev>
---
environment.c | 4 ++--
environment.h | 4 ++--
2 files changed, 4 insertions(+), 4 deletions(-)
diff --git a/environment.c b/environment.c
index 6ee11e9fc8..8f0c1c4f25 100644
--- a/environment.c
+++ b/environment.c
@@ -130,14 +130,14 @@ int is_bare_repository(struct repository *repo)
int repo_protect_ntfs(struct repository *repo)
{
- return repo->gitdir ?
+ return (repo && repo->initialized) ?
repo_config_values(repo)->protect_ntfs :
PROTECT_NTFS_DEFAULT;
}
int repo_protect_hfs(struct repository *repo)
{
- return repo->gitdir ?
+ return (repo && repo->initialized) ?
repo_config_values(repo)->protect_hfs :
PROTECT_HFS_DEFAULT;
}
diff --git a/environment.h b/environment.h
index d188955f5b..8aaedcfea3 100644
--- a/environment.h
+++ b/environment.h
@@ -137,8 +137,8 @@ int git_default_core_config(const char *var, const char *value,
/*
* Getters for the `protect_hfs` and `protect_ntfs` fields of `struct repo_config_values`.
- * They check `repo->gitdir` to prevent calling repo_config_values()
- * before the configuration is loaded or in bare environments.
+ * They check `repo->initialized` to prevent calling `repo_config_values()`
+ * before the repository setup is fully complete or in non-git environments.
*/
int repo_protect_hfs(struct repository *repo);
int repo_protect_ntfs(struct repository *repo);
--
2.43.0
^ permalink raw reply related
* Re: [GSoC Patch v6 1/4] path: introduce append_formatted_path() for shared path formatting
From: Junio C Hamano @ 2026-06-20 14:27 UTC (permalink / raw)
To: K Jayatheerth
Cc: git, jltobler, lucasseikioshiro, phillip.wood, sandals,
kumarayushjha123, a3205153416, kristofferhaugsbakk
In-Reply-To: <20260620031644.353772-2-jayatheerthkulkarni2005@gmail.com>
K Jayatheerth <jayatheerthkulkarni2005@gmail.com> writes:
> The path-formatting logic in builtin/rev-parse.c is tightly coupled
> to that command and writes directly to stdout, making it impossible
> for other builtins to reuse.
>
> Extract the core algorithm into append_formatted_path() in path.c
> and expose a path_format enum in path.h so that any builtin can
> format paths consistently without duplicating logic.
>
> Mentored-by: Justin Tobler <jltobler@gmail.com>
> Mentored-by: Lucas Seiki Oshiro <lucasseikioshiro@gmail.com>
> Signed-off-by: K Jayatheerth <jayatheerthkulkarni2005@gmail.com>
> ---
> path.c | 69 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
> path.h | 30 +++++++++++++++++++++++++
> 2 files changed, 99 insertions(+)
It often, even though not always, is a sign of a bad topic structure
to have an insertion-only patch without any removal of existing
code, that adds totally unused code.
If the step is to "extract the core algorithm", shouldn't it be able
to replace existing code already?
We may want to add new features to this helper function near the end
of the topic, but wouldn't it make sense for the topic to first
consolidate various path formatting logic already present in the
existing code into a single helper for ease of extending it (which
means replacing open-coded logic in existing code paths with a call
to the new helper, which would have a code that may look very
similar to the original code that was replaced with a single call to
the helper function), and then expose the helper for use by new
callers, and finally further add new features that existing code
paths wouldn't have needed but the new callers would want?
How else can we make sure this new implementation added by the first
step in the series is (1) capable enough to reproduce what we
already have in different parts of the system, (2) does not bring in
what the current codebase does not need, and (3) bug-to-bug
compatible with the existing code paths?
> diff --git a/path.c b/path.c
> index d7e17bf174..6d8e892ada 100644
> --- a/path.c
> +++ b/path.c
> @@ -1579,6 +1579,75 @@ char *xdg_cache_home(const char *filename)
> return NULL;
> }
>
> +void append_formatted_path(struct strbuf *dest, const char *path,
> + const char *prefix, enum path_format format)
> +{
> + switch (format) {
> + case PATH_FORMAT_UNMODIFIED:
> + strbuf_addstr(dest, path);
> + break;
> +
> + case PATH_FORMAT_RELATIVE: {
> + struct strbuf relative_buf = STRBUF_INIT;
> + struct strbuf real_path = STRBUF_INIT;
> + struct strbuf real_prefix = STRBUF_INIT;
> + char *cwd = NULL;
> +
> + /*
> + * We don't ever produce a relative path if prefix is NULL,
> + * so set the prefix to the current directory so that we can
> + * produce a relative path whenever possible.
> + */
> + if (!prefix)
> + prefix = cwd = xgetcwd();
> +
> + if (!is_absolute_path(path)) {
> + strbuf_realpath_forgiving(&real_path, path, 1);
> + path = real_path.buf;
> + }
> + if (!is_absolute_path(prefix)) {
> + strbuf_realpath_forgiving(&real_prefix, prefix, 1);
> + prefix = real_prefix.buf;
> + }
> +
> + strbuf_addstr(dest, relative_path(path, prefix, &relative_buf));
> +
> + strbuf_release(&relative_buf);
> + strbuf_release(&real_path);
> + strbuf_release(&real_prefix);
> + free(cwd);
> + break;
> + }
> +
> + case PATH_FORMAT_RELATIVE_IF_SHARED: {
> + struct strbuf relative_buf = STRBUF_INIT;
> +
> + /*
> + * If we're using RELATIVE_IF_SHARED mode, then we want an
> + * absolute path unless the two share a common prefix, so don't
> + * default the prefix to the current working directory. Doing so
> + * would cause a relative path to always be produced if possible.
> + */
> + strbuf_addstr(dest, relative_path(path, prefix, &relative_buf));
> + strbuf_release(&relative_buf);
> + break;
> + }
> +
> + case PATH_FORMAT_CANONICAL: {
> + struct strbuf canonical_buf = STRBUF_INIT;
> +
> + strbuf_realpath_forgiving(&canonical_buf, path, 1);
> + strbuf_addbuf(dest, &canonical_buf);
> +
> + strbuf_release(&canonical_buf);
> + break;
> + }
> +
> + default:
> + BUG("unknown path_format value %d", format);
> + }
> +}
> +
> REPO_GIT_PATH_FUNC(squash_msg, "SQUASH_MSG")
> REPO_GIT_PATH_FUNC(merge_msg, "MERGE_MSG")
> REPO_GIT_PATH_FUNC(merge_rr, "MERGE_RR")
> diff --git a/path.h b/path.h
> index 4c2958a903..4d982a2c8e 100644
> --- a/path.h
> +++ b/path.h
> @@ -262,6 +262,36 @@ enum scld_error safe_create_leading_directories_no_share(char *path);
> int safe_create_file_with_leading_directories(struct repository *repo,
> const char *path);
>
> +/**
> + * The formatting strategy to apply when writing a path into a buffer.
> + */
> +enum path_format {
> + /* Output the path exactly as-is without any modifications. */
> + PATH_FORMAT_UNMODIFIED,
> +
> + /* Output a path relative to the provided directory prefix. */
> + PATH_FORMAT_RELATIVE,
> +
> + /* Output a relative path only if the path shares a root with the prefix. */
> + PATH_FORMAT_RELATIVE_IF_SHARED,
> +
> + /* Output a fully resolved, absolute canonical path. */
> + PATH_FORMAT_CANONICAL
> +};
> +
> +/**
> + * Format a path according to the specified formatting strategy and append
> + * the result to the given strbuf.
> + *
> + * `dest` : The string buffer to append the formatted path to.
> + * `path` : The path string that needs to be formatted.
> + * `prefix` : The directory prefix to calculate relative offsets against.
> + * Pass NULL to default to the current working directory where applicable.
> + * `format` : The formatting behavior rule to execute.
> + */
> +void append_formatted_path(struct strbuf *dest, const char *path,
> + const char *prefix, enum path_format format);
> +
> # ifdef USE_THE_REPOSITORY_VARIABLE
> # include "strbuf.h"
> # include "repository.h"
^ permalink raw reply
* Re: [PATCH v6 2/3] revision: add peek functions for lookahead
From: Junio C Hamano @ 2026-06-20 14:56 UTC (permalink / raw)
To: Pablo Sabater
Cc: git, krka, ayu.chandekar, chandrapratap3519, christian.couder,
jltobler, karthik.188, peff, phillip.wood, siddharthasthana31,
Kristofer Karlsson
In-Reply-To: <20260620-ps-pre-commit-indent-v6-2-cdc6d8fd5fbc@gmail.com>
Pablo Sabater <pabloosabaterr@gmail.com> writes:
> The graph code in a subsequent commit needs to be able to look ahead in
> order to set indentation-related flags.
>
> Using revs->commits is brittle and the data structure that holds the
> pending commits might change in the future.
>
> Add two functions that abstract this for the graph.
>
> Helped-by: Kristofer Karlsson <stoansen@gmail.com>
> Signed-off-by: Pablo Sabater <pabloosabaterr@gmail.com>
> ---
> revision.c | 38 ++++++++++++++++++++++++++++++++++++++
> revision.h | 10 ++++++++++
> 2 files changed, 48 insertions(+)
>
> diff --git a/revision.c b/revision.c
> index e91d7e1f11..a472a28853 100644
> --- a/revision.c
> +++ b/revision.c
> @@ -3708,6 +3708,44 @@ static unsigned int count_explore_walked;
> static unsigned int count_indegree_walked;
> static unsigned int count_topo_walked;
>
> +struct commit *revision_peek_next_commit (struct rev_info *revs)
> +{
> + struct topo_walk_info *info = revs->topo_walk_info;
> +
> + if (info)
> + return prio_queue_peek(&info->topo_queue);
> + if (revs->commits)
> + return revs->commits->item;
> +
> + return NULL;
> +}
OK. "If we are doing topo_walk, topo_queue is the priority queue to
peek into, otherwise revs->commits list is being used" is a bit too
intimate implementation detail I am not comfortable to depend on,
but as long as it is contained inside revision.c it should be OK.
Lose the space between the function name and its (parameter list)
from this and the next function.
> +int revision_has_commits_after (struct rev_info *revs, int n)
> +{
> + struct topo_walk_info *info = revs->topo_walk_info;
> +
> + if (info) {
> + int visible = 0;
> + for (size_t i = 0; i < info->topo_queue.nr && visible < n; i++) {
> + struct commit *c = info->topo_queue.array[i].data;
> + if (get_commit_action(revs, c) == commit_show)
> + visible++;
> + }
> + return visible > n-1;
> + }
> + if (revs->commits) {
> + struct commit_list *cl;
> + int visible = 0;
> + for (cl = revs->commits; cl && visible < n; cl = cl->next) {
> + if (get_commit_action(revs, cl->item) == commit_show)
> + visible++;
> + }
> + return visible > n-1;
> + }
> +
> + return 0;
> +}
Regarding the use of get_commit_action() here, I wondered if this is
safe, because usually get_commit_action() is called only once per
commit during history traversal from simplify_commit(), but this
patch adds calls to it for all of the remaining commits being
processed without consuming them (so get_commit_action() will be
called on these commits again later as the history traversal
progresses).
If get_commit_action() a pure function without any side effects,
this may be safe, but line-log has something with side effect in the
function.
I _think_ this is OK, as "--graph" sets .rewrite_parents bit (as
well as .topo_order bit) on, which makes want_ancestry() to return
true. Which in turn means even if -L is in effect, we will not call
line_log_process_ranges_arbitrary_commit() that is the only source
of side effect in this function. Somebody needs to sanity check
this, but we may want to leave an in-code comment to warn future
developers not to call get_commit_action() on random commits outside
of the normal history traversal under what condition (namely, -L
without rewrite_parents).
Even better, perhaps add
if (revs->line_level_traverse && !want_ancestry(revs))
BUG("do not call this");
at the beginning of revision_has_commits_after() function, and
describe why in the header file comment for this function below?
> diff --git a/revision.h b/revision.h
> index 00c392be37..a10c6b0940 100644
> --- a/revision.h
> +++ b/revision.h
> @@ -572,4 +572,14 @@ int rewrite_parents(struct rev_info *revs,
> */
> struct commit_list *get_saved_parents(struct rev_info *revs, const struct commit *commit);
>
> +/*
> + * Peek into revision's next commit without consuming it.
> + */
> +struct commit *revision_peek_next_commit(struct rev_info *revs);
> +
> +/*
> + * Check if there are n more commits to be shown yet.
> + */
> +int revision_has_commits_after(struct rev_info *revs, int n);
> +
> #endif
^ permalink raw reply
* Re: [PATCH v6 2/3] revision: add peek functions for lookahead
From: Junio C Hamano @ 2026-06-20 15:15 UTC (permalink / raw)
To: Pablo Sabater
Cc: git, SZEDER Gábor, Michael Montalbo, krka, ayu.chandekar,
chandrapratap3519, christian.couder, jltobler, karthik.188, peff,
phillip.wood, siddharthasthana31, Kristofer Karlsson
In-Reply-To: <xmqqzf0pfefp.fsf@gitster.g>
Junio C Hamano <gitster@pobox.com> writes:
> I _think_ this is OK, as "--graph" sets .rewrite_parents bit (as
> well as .topo_order bit) on, which makes want_ancestry() to return
> true. Which in turn means even if -L is in effect, we will not call
> line_log_process_ranges_arbitrary_commit() that is the only source
> of side effect in this function. Somebody needs to sanity check
> this, but we may want to leave an in-code comment to warn future
> developers not to call get_commit_action() on random commits outside
> of the normal history traversal under what condition (namely, -L
> without rewrite_parents).
>
> Even better, perhaps add
>
> if (revs->line_level_traverse && !want_ancestry(revs))
> BUG("do not call this");
>
> at the beginning of revision_has_commits_after() function, and
> describe why in the header file comment for this function below?
Having said all that, in the longer term we might be better off if
we fix the line-log code so that get_commit_action() becomes a pure
function again.
It might be a very simple change to move the "if we are doing -L and
!want_ancestry(), call the line_log_process_ranges_arbitrary_commit()"
to simplify_commit() before it calls get_commit_action(), but I
haven't thought things through.
[jc: Michael Cc'ed as there are a few topics on line-log recently
from him; SZEDER Cc'ed as his 3cb9d2b6 (line-log: more responsive,
incremental 'git log -L', 2020-05-11) introduced this side effect
there.]
In any case, this is a remote tangent that does not affect how we
want to proceed with this series ;-).
^ permalink raw reply
* Re: [PATCH] environment: use 'repo->initialized' for repo_protect_hfs() and repo_protect_ntfs()
From: Junio C Hamano @ 2026-06-20 15:18 UTC (permalink / raw)
To: Tian Yuchen; +Cc: git, Christian Couder, Ayush Chandekar, Olamide Caleb Bello
In-Reply-To: <20260620140957.667820-1-cat@malon.dev>
Tian Yuchen <cat@malon.dev> writes:
> To match how we refrain from calling repo_config_values() on an
> uninitialized instance of a repository object in other two topics
> that deal with ignore_case and trust_executable_bit, check the
> repo->initialized bit instead of the repo->gitdir member.
OK.
> Base commit: 43192e7977f5f05138abcdb3212a3f87ab513bef
This line does not belong here. Besides, you do not build directly
on top of 'next', ever.
> Mentored-by: Christian Couder <christian.couder@gmail.com>
> Mentored-by: Ayush Chandekar <ayu.chandekar@gmail.com>
> Mentored-by: Olamide Caleb Bello <belkid98@gmail.com>
> Signed-off-by: Tian Yuchen <cat@malon.dev>
> ---
> environment.c | 4 ++--
> environment.h | 4 ++--
> 2 files changed, 4 insertions(+), 4 deletions(-)
I'll queue the change directly on top of ty/move-protect-hfs-ntfs
topic, which will be merged to 'next'.
Thanks.
> diff --git a/environment.c b/environment.c
> index 6ee11e9fc8..8f0c1c4f25 100644
> --- a/environment.c
> +++ b/environment.c
> @@ -130,14 +130,14 @@ int is_bare_repository(struct repository *repo)
>
> int repo_protect_ntfs(struct repository *repo)
> {
> - return repo->gitdir ?
> + return (repo && repo->initialized) ?
> repo_config_values(repo)->protect_ntfs :
> PROTECT_NTFS_DEFAULT;
> }
>
> int repo_protect_hfs(struct repository *repo)
> {
> - return repo->gitdir ?
> + return (repo && repo->initialized) ?
> repo_config_values(repo)->protect_hfs :
> PROTECT_HFS_DEFAULT;
> }
> diff --git a/environment.h b/environment.h
> index d188955f5b..8aaedcfea3 100644
> --- a/environment.h
> +++ b/environment.h
> @@ -137,8 +137,8 @@ int git_default_core_config(const char *var, const char *value,
>
> /*
> * Getters for the `protect_hfs` and `protect_ntfs` fields of `struct repo_config_values`.
> - * They check `repo->gitdir` to prevent calling repo_config_values()
> - * before the configuration is loaded or in bare environments.
> + * They check `repo->initialized` to prevent calling `repo_config_values()`
> + * before the repository setup is fully complete or in non-git environments.
> */
> int repo_protect_hfs(struct repository *repo);
> int repo_protect_ntfs(struct repository *repo);
^ permalink raw reply
* Re: [RFH] Why do osx CI jobs so unreliable?
From: Michael Montalbo @ 2026-06-20 15:33 UTC (permalink / raw)
To: Patrick Steinhardt; +Cc: git, Junio C Hamano
Patrick Steinhardt <ps@pks.im> writes:
> So I strongly suspect that it most be one of the t555* tests.
> [...]
> Maybe this is something that's specific to GitHub's environment...
I think you're right it's t5551/t5559. The runs Junio linked:
osx-clang cancelled 360min
osx-gcc cancelled 360min
osx-reftable success 35min
osx-meson success 61min
All four run the same t5551/t5559 under EXPENSIVE. The two that
finished differ in just two ways, which look like the levers:
osx-reftable generates the 100k-ref advertisement in ~24ms vs ~1.2s
for loose refs on macOS (so much less time mid-response), and
osx-meson runs tests at nproc while the prove jobs hardcode --jobs=10
on a 3-core runner (over recent master/next the prove jobs hang ~40%,
meson ~10%).
When it is wedged the whole chain sits at 0% CPU. upload-pack is
blocked in write() on the ls-refs advertisement, curl blocked in
select(). So it looks like an HTTP/2 flow-control stall on the
response side. The same stall resets itself after ~60-85s on my Linux
box and on a bare-metal Mac, but not on the GitHub runner; I haven't
pinned down why yet.
On the chance those two levers are the fix, a branch off master:
https://github.com/mmontalbo/git/tree/mm/macos-ci-hang-fix
- pack the refs in t5551's enormous-ref-negotiation test (doesn't
change what it checks on the wire, just avoids re-reading 100k loose
files to advertise them, like reftable already does)
- use the core count for $JOBS on the GitHub macOS path, matching the
GitLab branch in the same ci/lib.sh and what meson does
I ran the two macOS jobs under EXPENSIVE about eight times with these
and they all finished in ~30-44min instead of hanging. Happy to send
out a patch if it's helpful.
^ permalink raw reply
* Re: git-diff in a worktree is an order of magnitude slower?
From: D. Ben Knoble @ 2026-06-20 15:57 UTC (permalink / raw)
To: Jeff King; +Cc: Git
In-Reply-To: <20260611085526.GL2191159@coredump.intra.peff.net>
Coming back to index refreshing…
On Thu, Jun 11, 2026 at 4:55 AM Jeff King <peff@peff.net> wrote:
>
> On Tue, Jun 09, 2026 at 01:15:11PM -0400, D. Ben Knoble wrote:
>
> > > Which implies that the entries are stat dirty. And indeed, if I run:
> > >
> > > git -C linux update-index --refresh
> > >
> > > now they both take ~20ms.
> >
> > Ah, TIL about --refresh. I suppose it could be nice if "git diff"
> > updated the index in this way, but that sounds like a band-aid. Maybe
> > creating a fresh worktree should do the equivalent to make sure it's
> > considered "fresh"?
>
> I think "git diff" _does_ refresh the index internally (that's what
> takes so long!). I thought we then wrote out the result, but maybe we
> don't notice that it needs an update for some reason?
>
> I'm pretty sure "git status" does something similar, though running it
> in a slow working tree _does_ seem to make things faster. Maybe it's
> more aggressive about doing the update.
Thanks for the status pointer:
- cmd_status calls refresh_index and repo_updated_index_if_able
- those same calls are wrapped in refresh_index_quietly in builtin/diff.c
But the refresh_index_quietly call is guarded by (effectively; the
actual code uses rev.diffopt.skip_stat_unmatch)
1 < !!diff_auto_refresh_index
which dates to aecbf914c4 (git-diff: resurrect the traditional empty
"diff --git" behaviour, 2007-08-31). On my system that comparison is
false because the double-negation produces 1
(diff_auto_refresh_index=1 or the result of git_config_bool). Or at
least, I don't see it get written to elsewhere (maybe that's supposed
to happen in diff.c:diffcore_skip_stat_unmatch in this case and isn't?
Idk. (Even dirtying the worktree as a hypothesis that only when a diff
is found does the counter get bumped doesn't seem to work.)
So… has that conditional been quietly dead all this time? I can't
imagine that's right, but…
> > > I'd have thought USE_NSEC was the default these days, but looks like it
> > > isn't? Try building with that and I'll bet it goes away entirely.
> >
> > Thanks, I'll take a look.
> >
> > I can see on my Macbook that at least Meson does automatically set
> > either USE_ST_TIMESPEC or NO_NSEC automatically, but has no option to
> > enabled USE_NSEC and try that. I can probably write that patch (which
> > I'll do to test), and I can send it along with the "worktree add
> > should refresh the index" if you think that's an appropriate thing to
> > do.
>
> I think NO_NSEC is about not looking at the nsec fields of stat structs
> (since they might not exist). But we don't actually use them for stat
> matching unless USE_NSEC is set.
>
> I guess the distinction goes back to c06ff4908b (Record ns-timestamps if
> possible, but do not use it without USE_NSEC, 2009-03-04), which details
> some reasons you might not want USE_NSEC. Feels like it ought to be a
> run-time config, though, and maybe even something that gets auto-probed
> by git-init.
>
> Definitely not an area I have looked at much, though, nor thought hard
> about. So there might be gotchas. :)
>
> -Peff
Looks like adding USE_NSEC to my build did make the issue go away (the
patch is short, and I'll send it anyway for folks to have the knob),
but that now seems like a band-aid to me based on my confusion above.
--
D. Ben Knoble
^ 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