[PATCH RFC] graph: implement git-log(1) --untangle

[PATCH RFC] graph: implement git-log(1) --untangle

[Toon Claes]

The output of `git log --graph` can be cluttered when dealing with
long-living branches or octopus merges.

For example consider this graph:

    * left
    | *-.   octopus-merge
    |/|\ \
    | | | * 4
    | | * | 3
    | | |/
    | * / 2
    | |/
    * / 1
    |/
    * initial

The reason this looks messy, is because for each merged branch there is
a line back to the source branch. But in most cases, the user doesn't
care when merged branches are branched of.

To simplify the graph, implement option `--untangle`.

    * left
    | *-.   octopus-merge
    |/|\ \
    | | | * 4
    | | * 3
    | * 2
    * 1
    * initial

As you can see, this untangles the arms of the octopus.

To implement this feature, merge commits are treated a differently. For
each parent commit (except the first one) of a merge, the merge-base
with the first parent is found. That merge-base is saved in the column
for that branch and when the next commit for the column would be that
merge-base, no lines are drawn no more.

Signed-off-by: Toon Claes <toon@iotcl.com>
---
I was at FOSDEM this weekend, and there someone spoke[1] about merge
strategies. Now you can argue whether merge commits are good or not, but
one argument is less likely to argue about: it can make
`git log --graph --oneline` look really cluttered. For example take this
fragment of the graph of 'master' in the git.git project:

    * | | | | | | | | | | | | | |   d627023d80 Merge branch 'ps/packfile-store-in-odb-source'
    |\ \ \ \ \ \ \ \ \ \ \ \ \ \ \
    | * | | | | | | | | | | | | | | a282a8f163 packfile: move MIDX into packfile store
    | * | | | | | | | | | | | | | | a593373b09 packfile: refactor `find_pack_entry()` to work on the packfile store
    | * | | | | | | | | | | | | | | 6acefa0d2c packfile: inline `find_kept_pack_entry()`
    | * | | | | | | | | | | | | | | 8384cbcb4c packfile: only prepare owning store in `packfile_store_prepare()`
    | * | | | | | | | | | | | | | | 7b330a11de packfile: only prepare owning store in `packfile_store_get_packs()`
    | * | | | | | | | | | | | | | | 84f0e60b28 packfile: move packfile store into object source
    | * | | | | | | | | | | | | | | eb9ec52d95 packfile: refactor misleading code when unusing pack windows
    | * | | | | | | | | | | | | | | 085de91b95 packfile: refactor kept-pack cache to work with packfile stores
    | * | | | | | | | | | | | | | | 0316c63ca4 packfile: pass source to `prepare_pack()`
    | * | | | | | | | | | | | | | | 480336a9ce packfile: create store via its owning source
    | * | | | | | | | | | | | | | |   f1ec43d4d2 Merge branch 'ps/odb-misc-fixes' into ps/packfile-store-in-odb-source
    | |\ \ \ \ \ \ \ \ \ \ \ \ \ \ \
    | * \ \ \ \ \ \ \ \ \ \ \ \ \ \ \   f1799202ea Merge branch 'ps/object-read-stream' into ps/packfile-store-in-odb-source
    | |\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
    * | \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \   ab72d23880 Merge branch 'kt/http-backend-errors'
    |\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
    | * | | | | | | | | | | | | | | | | | a8227ae8d5 http-backend: write newlines to stderr when responding with errors
    | | |_|_|_|_|_|_|_|/ / / / / / / / /
    | |/| | | | | | | | | | | | | | | |
    * | | | | | | | | | | | | | | | | |   e01178bb1a Merge branch 'ps/t1410-cleanup'

This graph can grow wide very quickly.

I would argue the problem here are not the merge commits, but it's the
way this is displayed.

So that got me thinking. `git log --graph` shows lines from child
commits to each of their parents. This is very useful for branches to
see which of the parent commits they include. But it's less useful for
merged branches. In most cases for a branch that was merged, nobody
cares from which commit that branch was branched of, because that merge
comit contains all changes from the history of all parents of that merge
commit.

That's why I've created this experiment. In this patch I'm adding a new
option `--untangle` to git-log(1). This option, as I like to call it,
"untangles the octopus".

There are still some bugs in this implementation. And a bunch of memory
leaks. Also am I not sold on the name `--untangle`. It sounds catchy,
but it's name isn't very meaningful for most users. I've been thinking
about `--ignore-merge-base` or `disconnect-merge-base`, but I'm open to
better suggestions. That's why I'm submitting this as a RFC. Before I
continue work on this, I'm curious if the project is open to such
contribution? And if so, which direction it should go?

[1]: https://fosdem.org/2026/schedule/event/3VNNBK-efficient-git-for-high-stakes/
---
 graph.c                      | 107 ++++++++++++++++++++++++++++++++++++++++---
 graph.h                      |   8 ++++
 revision.c                   |   6 +++
 t/t4214-log-graph-octopus.sh | 104 +++++++++++++++++++++++++++++++++++++++++
 4 files changed, 218 insertions(+), 7 deletions(-)

diff --git a/graph.c b/graph.c
index 26f6fbf000..2657990054 100644
--- a/graph.c
+++ b/graph.c
@@ -8,6 +8,7 @@
 #include "graph.h"
 #include "revision.h"
 #include "strvec.h"
+#include "commit-reach.h"
 
 /* Internal API */
 
@@ -51,6 +52,11 @@ static void graph_show_strbuf(struct git_graph *graph,
  */
 
 struct column {
+	/*
+	 * When only_first_merge_base is set this column might be ignoring it's
+         * merge-base, store it here.
+	 */
+	struct commit_list *ignored_merge_bases;
 	/*
 	 * The parent commit of this column.
 	 */
@@ -315,6 +321,14 @@ struct git_graph {
 	 * diff_output_prefix_callback().
 	 */
 	struct strbuf prefix_buf;
+
+	/*
+	 * For merge commits, determine the merge-base for the parent commits.
+	 * With only_first_merge_base set, only the first parent is connected
+	 * back to the merge-base. This simplifies the graph and makes the
+	 * merged branches appear like they originate from another root commit.
+	 */
+	bool only_first_merge_base;
 };
 
 static const char *diff_output_prefix_callback(struct diff_options *opt, void *data)
@@ -391,8 +405,8 @@ struct git_graph *graph_init(struct rev_info *opt)
 	 * We'll automatically grow columns later if we need more room.
 	 */
 	graph->column_capacity = 30;
-	ALLOC_ARRAY(graph->columns, graph->column_capacity);
-	ALLOC_ARRAY(graph->new_columns, graph->column_capacity);
+	CALLOC_ARRAY(graph->columns, graph->column_capacity);
+	CALLOC_ARRAY(graph->new_columns, graph->column_capacity);
 	ALLOC_ARRAY(graph->mapping, 2 * graph->column_capacity);
 	ALLOC_ARRAY(graph->old_mapping, 2 * graph->column_capacity);
 
@@ -404,6 +418,8 @@ struct git_graph *graph_init(struct rev_info *opt)
 	opt->diffopt.output_prefix = diff_output_prefix_callback;
 	opt->diffopt.output_prefix_data = graph;
 
+	graph->only_first_merge_base = false;
+
 	return graph;
 }
 
@@ -412,6 +428,13 @@ void graph_clear(struct git_graph *graph)
 	if (!graph)
 		return;
 
+	for (size_t i = 0; i < graph->num_columns; i++) {
+		free_commit_list(graph->columns[i].ignored_merge_bases);
+	}
+	for (size_t i = 0; i < graph->num_new_columns; i++) {
+		free_commit_list(graph->new_columns[i].ignored_merge_bases);
+	}
+
 	free(graph->columns);
 	free(graph->new_columns);
 	free(graph->mapping);
@@ -420,6 +443,12 @@ void graph_clear(struct git_graph *graph)
 	free(graph);
 }
 
+void graph_set_only_first_merge_base(struct git_graph *graph, bool skip)
+{
+	if (graph)
+		graph->only_first_merge_base = skip;
+}
+
 static void graph_update_state(struct git_graph *graph, enum graph_state s)
 {
 	graph->prev_state = graph->state;
@@ -550,7 +579,8 @@ static int graph_find_new_column_by_commit(struct git_graph *graph,
 
 static void graph_insert_into_new_columns(struct git_graph *graph,
 					  struct commit *commit,
-					  int idx)
+					  int idx,
+					  struct commit_list *merge_bases)
 {
 	int i = graph_find_new_column_by_commit(graph, commit);
 	int mapping_idx;
@@ -563,6 +593,9 @@ 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);
+
+		//free_commit_list(graph->new_columns[i].ignored_merge_bases);
+		graph->new_columns[i].ignored_merge_bases = merge_bases;
 	}
 
 	if (graph->num_parents > 1 && idx > -1 && graph->merge_layout == -1) {
@@ -605,7 +638,7 @@ static void graph_insert_into_new_columns(struct git_graph *graph,
 
 static void graph_update_columns(struct git_graph *graph)
 {
-	struct commit_list *parent;
+	struct commit_list *parent, *first_parent, *ignored_parent, *ignored_merge_bases;
 	int max_new_columns;
 	int i, seen_this, is_commit_in_columns;
 
@@ -667,11 +700,45 @@ static void graph_update_columns(struct git_graph *graph)
 
 		if (col_commit == graph->commit) {
 			seen_this = 1;
+			first_parent = NULL;
+			ignored_merge_bases = graph->columns[i].ignored_merge_bases;
 			graph->commit_index = i;
 			graph->merge_layout = -1;
+
+			/*
+			 * Find the parent that should be ignored, if any?
+			 */
+			ignored_parent = NULL;
+			for (parent = first_interesting_parent(graph);
+			     parent;
+			     parent = next_interesting_parent(graph, parent)) {
+				if (commit_list_contains(parent->item, ignored_merge_bases)) {
+					/*
+					 * Note: We only get in this codepath
+					 * when graph->only_first_merge_base is
+					 * set, because otherwise
+					 * ignored_merge_bases would be NULL.
+					 */
+					ignored_parent = parent;
+
+					/*
+					 * Whoops, fix miscalculated parent count.
+					 * TODO is this really needed?
+					 */
+					graph->num_parents -= 1;
+					break;
+				}
+			}
+
 			for (parent = first_interesting_parent(graph);
 			     parent;
 			     parent = next_interesting_parent(graph, parent)) {
+				/*
+				 * Skip the ignored parent
+				 */
+				if (ignored_parent && ignored_parent->item == parent->item)
+					continue;
+
 				/*
 				 * If this is a merge, or the start of a new
 				 * childless column, increment the current
@@ -681,7 +748,30 @@ static void graph_update_columns(struct git_graph *graph)
 				    !is_commit_in_columns) {
 					graph_increment_column_color(graph);
 				}
-				graph_insert_into_new_columns(graph, parent->item, i);
+
+				if (!first_parent) {
+					first_parent = parent;
+
+					if (ignored_parent) {
+						/*
+						 * One of the parents was ignored,
+						 * the new ignored merge-base can be found
+						 * against that parent.
+						 */
+						if (repo_get_merge_bases(graph->revs->repo, ignored_parent->item, parent->item, &ignored_merge_bases) < 0) {
+							free_commit_list(ignored_merge_bases);
+							ignored_merge_bases = NULL;
+						}
+					}
+				} else if (graph->only_first_merge_base) {
+					if (repo_get_merge_bases(graph->revs->repo, first_parent->item, parent->item, &ignored_merge_bases) < 0) {
+						free_commit_list(ignored_merge_bases);
+						ignored_merge_bases = NULL;
+					}
+				}
+
+				graph_insert_into_new_columns(graph, parent->item, i,
+							      ignored_merge_bases);
 			}
 			/*
 			 * We always need to increment graph->width by at
@@ -692,7 +782,7 @@ static void graph_update_columns(struct git_graph *graph)
 			if (graph->num_parents == 0)
 				graph->width += 2;
 		} else {
-			graph_insert_into_new_columns(graph, col_commit, -1);
+			graph_insert_into_new_columns(graph, col_commit, -1, graph->columns[i].ignored_merge_bases);
 		}
 	}
 
@@ -1112,6 +1202,9 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct graph_l
 			seen_this = 1;
 
 			for (j = 0; j < graph->num_parents; j++) {
+				if (!parents)
+					break;
+
 				par_column = graph_find_new_column_by_commit(graph, parents->item);
 				assert(par_column >= 0);
 
@@ -1145,7 +1238,7 @@ static void graph_output_post_merge_line(struct git_graph *graph, struct graph_l
 			}
 		}
 
-		if (col_commit == first_parent->item)
+		if (first_parent && col_commit == first_parent->item)
 			parent_col = col;
 	}
 
diff --git a/graph.h b/graph.h
index 3fd1dcb2e9..e2568ae803 100644
--- a/graph.h
+++ b/graph.h
@@ -144,6 +144,14 @@ struct git_graph *graph_init(struct rev_info *opt);
  */
 void graph_clear(struct git_graph *graph);
 
+/*
+ * Enable skip-merge-base mode for the graph.
+ * When enabled, non-first-parent branches from merge commits will not
+ * show history beyond the merge-base, making the graph simpler by
+ * showing branches as if they have separate roots.
+ */
+void graph_set_only_first_merge_base(struct git_graph *graph, bool skip);
+
 /*
  * Update a git_graph with a new commit.
  * This will cause the graph to begin outputting lines for the new commit
diff --git a/revision.c b/revision.c
index 9b131670f7..71a2a4ed57 100644
--- a/revision.c
+++ b/revision.c
@@ -2602,6 +2602,12 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg
 	} else if (!strcmp(arg, "--no-graph")) {
 		graph_clear(revs->graph);
 		revs->graph = NULL;
+	} else if (!strcmp(arg, "--untangle")) {
+		if (!revs->graph)
+			revs->graph = graph_init(revs);
+		graph_set_only_first_merge_base(revs->graph, true);
+	} else if (!strcmp(arg, "--no-untangle")) {
+		graph_set_only_first_merge_base(revs->graph, 0);
 	} else if (!strcmp(arg, "--encode-email-headers")) {
 		revs->encode_email_headers = 1;
 	} else if (!strcmp(arg, "--no-encode-email-headers")) {
diff --git a/t/t4214-log-graph-octopus.sh b/t/t4214-log-graph-octopus.sh
index f70c46bbbf..181bce074b 100755
--- a/t/t4214-log-graph-octopus.sh
+++ b/t/t4214-log-graph-octopus.sh
@@ -347,4 +347,108 @@ test_expect_success 'log --graph with unrelated commit and octopus child with co
 	test_cmp_colored_graph after-initial after-merge
 '
 
+test_expect_success 'log --graph --untangle with tricky octopus merge, no color' '
+	test_cmp_graph --untangle left octopus-merge <<-\EOF
+	* left
+	| *-.   octopus-merge
+	|/|\ \
+	| | | * 4
+	| | * 3
+	| * 2
+	* 1
+	* initial
+	EOF
+'
+
+test_expect_success 'log --graph --untangle with branch from merged branch, no color' '
+	test_when_finished rm -rf repo &&
+	git init repo &&
+	(
+		cd repo &&
+		test_commit initial &&
+		test_commit a &&
+		git checkout initial -b feat-1 &&
+		test_commit b &&
+		git checkout main &&
+		test_merge feat-1-merge feat-1 &&
+		test_commit c &&
+		git checkout b -b feat-2 &&
+		test_commit d &&
+		git checkout main &&
+		test_merge feat-2-merge feat-2 &&
+		test_cmp_graph main --untangle <<-\EOF
+		*   feat-2-merge
+		|\
+		| * d
+		* c
+		*   feat-1-merge
+		|\
+		| * b
+		* a
+		* initial
+		EOF
+	)
+'
+
+test_expect_success 'log --graph --untangle with intermediate merge of source branch, no color' '
+	test_when_finished rm -rf repo &&
+	git init repo &&
+	(
+		cd repo &&
+		test_commit initial &&
+		test_commit a &&
+		test_commit b &&
+		git checkout initial -b feat-1 &&
+		test_commit c &&
+		test_merge merge-a a &&
+		test_commit d &&
+		git checkout main &&
+		test_merge feat-1-merge feat-1 &&
+		test_cmp_graph main --untangle <<-\EOF
+		*   feat-1-merge
+		|\
+		| * d
+		| * merge-a
+		| * c
+		* b
+		* a
+		* initial
+		EOF
+	)
+'
+
+test_expect_success 'log --graph with merging branch from other root commit, no color' '
+	test_when_finished rm -rf repo &&
+	git init repo &&
+	(
+		cd repo &&
+		test_commit initial &&
+		test_commit a &&
+		test_commit b &&
+		git checkout --orphan orphan &&
+		test_commit I &&
+		test_commit II &&
+		git checkout main &&
+		test_merge merge-orphan --allow-unrelated-histories orphan &&
+		test_commit c &&
+		git checkout a -b feat &&
+		test_commit d &&
+		git checkout main &&
+		test_merge merge-feat feat &&
+		test_cmp_graph main --untangle <<-\EOF
+		*   merge-feat
+		|\
+		| * d
+		* c
+		*   merge-orphan
+		|\
+		| * II
+		| * I
+		* b
+		* a
+		* initial
+		EOF
+	)
+'
+
 test_done

---
base-commit: 22584464849815268419fd9d2eba307362360db1
change-id: 20260202-toon-log-graph-no-merge-base-775255ebd74a

Re: [PATCH RFC] graph: implement git-log(1) --untangle

[Junio C Hamano]

Toon Claes <toon@iotcl.com> writes:

> I would argue the problem here are not the merge commits, but it's the
> way this is displayed.

I am curious, as anybody else who has read this message up to this
point, how your --untangle option improves the same section of the
history you drew above (which I did not include).

> There are still some bugs in this implementation. And a bunch of memory
> leaks. Also am I not sold on the name `--untangle`. It sounds catchy,
> but it's name isn't very meaningful for most users. I've been thinking
> about `--ignore-merge-base` or `disconnect-merge-base`, but I'm open to
> better suggestions. That's why I'm submitting this as a RFC. Before I
> continue work on this, I'm curious if the project is open to such
> contribution? And if so, which direction it should go?

In any case, I am very happy to see another person who is not afraid
of our C codebase to have looked at this part of the system (I have
a long-standing pet peeve, unrelated to this issue, in this area).

>  struct column {
> +	/*
> +	 * When only_first_merge_base is set this column might be ignoring it's
> +         * merge-base, store it here.
> +	 */
> +	struct commit_list *ignored_merge_bases;
>  	/*
>  	 * The parent commit of this column.
>  	 */

Re: [PATCH RFC] graph: implement git-log(1) --untangle

[Toon Claes]

Junio C Hamano <gitster@pobox.com> writes:

> Toon Claes <toon@iotcl.com> writes:
>
>> I would argue the problem here are not the merge commits, but it's the
>> way this is displayed.
>
> I am curious, as anybody else who has read this message up to this
> point, how your --untangle option improves the same section of the
> history you drew above (which I did not include).

I didn't want to clutter my email with a lot of examples, I would rather
have people give it a try. But since you asked.

Without --untangle:

    * 67ad42147a (tag: v2.53.0, origin/master, origin/maint, origin/HEAD, master) Git 2.53
    *   6f328bc9e3 Merge tag 'l10n-2.53.0-v1' of https://github.com/git-l10n/git-po
    |\
    | *   532543fa46 Merge branch 'jx/zh_CN' of github.com:jiangxin/git
    | |\
    | | * eb816ef79e l10n: zh_CN: standardize glossary terms
    | | * 3065daed59 l10n: zh_CN: updated translation for 2.53
    | | * eb3cfc6b2f l10n: zh_CN: fix inconsistent use of standard vs. wide colons
    | * |   5a83d800f3 Merge branch 'l10n/zh-TW/git-2-53' of github.com:l10n-tw/git-po
    | |\ \
    | | * | b47610d61d l10n: zh_TW.po: update Git 2.53 translation
    | * | |   e996719801 Merge branch 'po-id' of github.com:bagasme/git-po
    | |\ \ \
    | | * | | 6ef4d11472 l10n: po-id for 2.53
    | | |/ /
    | * | |   8ef65d7efd Merge branch 'l10n-ga-2.53' of github.com:aindriu80/git-po
    | |\ \ \
    | | * | | d534a373e7 l10n: ga.po: Fix git-po-helper warnings
    | | * | | 0c19f7f950 l10n: ga.po: Update Irish translation for Git 2.53
    | * | | |   b386b3aea7 Merge branch 'master' of github.com:alshopov/git-po
    | |\ \ \ \
    | | * | | | 06045e3984 l10n: bg.po: Updated Bulgarian translation (6091t)
    | * | | | |   af1a298e2c Merge branch 'fr_2.53' of github.com:jnavila/git
    | |\ \ \ \ \
    | | * | | | | 72dd507505 l10n: fr: v2.53
    | | | |_|/ /
    | | |/| | |
    | * | | | |   6f75c474d7 Merge branch 'tr-l10n' of github.com:bitigchi/git-po
    | |\ \ \ \ \
    | | * | | | | d63adbbbd5 l10n: tr: Update Turkish translations
    | | |/ / / /
    | * | | | |   3eaaa7fea4 Merge branch 'master' of github.com:nafmo/git-l10n-sv
    | |\ \ \ \ \
    | | |_|_|_|/
    | |/| | | |
    | | * | | | cba7353aed l10n: sv.po: Update Swedish translation
    * | | | | | 239b7f686c RelNotes: fully spell negation
    * | | | | | 2258446484 RelNotes: correct "fast-import" option name
    |/ / / / /
    * | | | | ea717645d1 RelNotes: a few spelling fixes
    * | | | | ab380cb80b (tag: v2.53.0-rc2) Git 2.53-rc2
    | |/ / /
    |/| | |
    * | | | ab689ea7f9 Revert "Merge branch 'cs/rebased-subtree-split'"
    * | | |   6959eee16e Merge branch 'master' of https://github.com/j6t/git-gui

With --untangle:

    * 67ad42147a (tag: v2.53.0, origin/master, origin/maint, origin/HEAD, master) Git 2.53
    *   6f328bc9e3 Merge tag 'l10n-2.53.0-v1' of https://github.com/git-l10n/git-po
    |\
    | *   532543fa46 Merge branch 'jx/zh_CN' of github.com:jiangxin/git
    | |\
    | | * eb816ef79e l10n: zh_CN: standardize glossary terms
    | | * 3065daed59 l10n: zh_CN: updated translation for 2.53
    | | * eb3cfc6b2f l10n: zh_CN: fix inconsistent use of standard vs. wide colons
    | *   5a83d800f3 Merge branch 'l10n/zh-TW/git-2-53' of github.com:l10n-tw/git-po
    | |\
    | | * b47610d61d l10n: zh_TW.po: update Git 2.53 translation
    | *   e996719801 Merge branch 'po-id' of github.com:bagasme/git-po
    | |\
    | | * 6ef4d11472 l10n: po-id for 2.53
    | *   8ef65d7efd Merge branch 'l10n-ga-2.53' of github.com:aindriu80/git-po
    | |\
    | | * d534a373e7 l10n: ga.po: Fix git-po-helper warnings
    | | * 0c19f7f950 l10n: ga.po: Update Irish translation for Git 2.53
    | *   b386b3aea7 Merge branch 'master' of github.com:alshopov/git-po
    | |\
    | | * 06045e3984 l10n: bg.po: Updated Bulgarian translation (6091t)
    | *   af1a298e2c Merge branch 'fr_2.53' of github.com:jnavila/git
    | |\
    | | * 72dd507505 l10n: fr: v2.53
    | *   6f75c474d7 Merge branch 'tr-l10n' of github.com:bitigchi/git-po
    | |\
    | | * d63adbbbd5 l10n: tr: Update Turkish translations
    | * 3eaaa7fea4 Merge branch 'master' of github.com:nafmo/git-l10n-sv
    | * cba7353aed l10n: sv.po: Update Swedish translation
    * 239b7f686c RelNotes: fully spell negation
    * 2258446484 RelNotes: correct "fast-import" option name
    * ea717645d1 RelNotes: a few spelling fixes
    * ab380cb80b (tag: v2.53.0-rc2) Git 2.53-rc2
    * ab689ea7f9 Revert "Merge branch 'cs/rebased-subtree-split'"
    *   6959eee16e Merge branch 'master' of https://github.com/j6t/git-gui

>> There are still some bugs in this implementation. And a bunch of memory
>> leaks. Also am I not sold on the name `--untangle`. It sounds catchy,
>> but it's name isn't very meaningful for most users. I've been thinking
>> about `--ignore-merge-base` or `disconnect-merge-base`, but I'm open to
>> better suggestions. That's why I'm submitting this as a RFC. Before I
>> continue work on this, I'm curious if the project is open to such
>> contribution? And if so, which direction it should go?
>
> In any case, I am very happy to see another person who is not afraid
> of our C codebase to have looked at this part of the system (I have
> a long-standing pet peeve, unrelated to this issue, in this area).

I'm happy to learn more about those pet peeves. git-log(1) --graph could
definetily use some love.

-- 
Cheers,
Toon

Re: [PATCH RFC] graph: implement git-log(1) --untangle

[Johannes Sixt]

Am 06.02.26 um 19:49 schrieb Toon Claes:
> The output of `git log --graph` can be cluttered when dealing with
> long-living branches or octopus merges.
> 
> For example consider this graph:
> 
>     * left
>     | *-.   octopus-merge
>     |/|\ \
>     | | | * 4
>     | | * | 3
>     | | |/
>     | * / 2
>     | |/
>     * / 1
>     |/
>     * initial
> 
> The reason this looks messy, is because for each merged branch there is
> a line back to the source branch. But in most cases, the user doesn't
> care when merged branches are branched of.
> 
> To simplify the graph, implement option `--untangle`.
> 
>     * left
>     | *-.   octopus-merge
>     |/|\ \
>     | | | * 4
>     | | * 3
>     | * 2
>     * 1
>     * initial

IMNSHO, we need a better way to show where links to parents were
truncated. Otherwise, I must consider this chart an incorrect
representation of the history above.

> As you can see, this untangles the arms of the octopus.

This example is too small to show any real improvement. But I think I
understood what the goal is.

> To implement this feature, merge commits are treated a differently. For
> each parent commit (except the first one) of a merge, the merge-base
> with the first parent is found. That merge-base is saved in the column
> for that branch and when the next commit for the column would be that
> merge-base, no lines are drawn no more.

So, the option's effect is to untangle visual representation of the
history. It is achieved by truncating links between merge-bases and
commits that appear in non-first parent links.

How does this work with criss-cross merges?

  Z
 / \
o   o
|\ /|
| x |
|/ \|
o   o
 \ /
  A

(not sure how --graph would represent this...)

How does this work with backward merges?

* main
|\
* | C
| * sync with main
|/|
* | B
| * A
|/
* initial

How does this interact with --boundary?

Speaking of which, boundary commits are listed last. Since they need to
be linked to the commits for which they are the boundary, a whole lot of
these "unnecessary" lines accumulate the longer the list of commits is.
If only there were a way to show boundary commits as soon as possible,
then this accumulation would not happen.

-- Hannes

Re: [PATCH RFC] graph: implement git-log(1) --untangle

[Toon Claes]

Johannes Sixt <j6t@kdbg.org> writes:

> IMNSHO, we need a better way to show where links to parents were
> truncated. Otherwise, I must consider this chart an incorrect
> representation of the history above.

The only alternative I can come up is showing as if the branch was made
from the parent commit of the merge commit. Like so:

Real:

    *
    |\
    | *
    | *
    *  \
    |\  |
    * * |
    |/ /
    * /
    *

My current implementation:

    *
    |\
    | *
    | *
    *
    |\
    * *
    |/
    *
    *

The suggestion:

    *
    |\
    | *
    | *
    |/
    *
    |\
    * *
    |/
    *
    *

But either way, what it shown it wrong. And that's in my opinion a
tradeoff of this feature.

I've been thinking about something else. Display in some way part of the
history is missing, maybe by showing a '.' in the graph:

    *
    |\
    | *
    | *
    | .
    *
    |\
    * *
    |/
    *
    *

This indicates a piece of the history is truncated. I'm still on the
fence about this

>
>> As you can see, this untangles the arms of the octopus.
>
> This example is too small to show any real improvement. But I think I
> understood what the goal is.

I would like to invite anyone here to try the feature on some of your
repositories you have. I feel it's impossible to really demonstrate it's
power through some examples over email.

> So, the option's effect is to untangle visual representation of the
> history. It is achieved by truncating links between merge-bases and
> commits that appear in non-first parent links.

Yes, that's the idea.

> How does this work with criss-cross merges?
>
>   Z
>  / \
> o   o
> |\ /|
> | x |
> |/ \|
> o   o
>  \ /
>   A

I haven't tried it yet.

>
> (not sure how --graph would represent this...)
>
> How does this work with backward merges?
>
> * main
> |\
> * | C
> | * sync with main
> |/|
> * | B
> | * A
> |/
> * initial

I've been trying in this first version to address that, but I haven't
been fully able to make it work.

I assume you and other readers know, but your example is a
simplification of:

    * main
    |\
    * | C
    | * sync with main
    | |\
    | |/
    |/|
    * | B
    | * A
    |/
    * initial

So here there merge-base isn't the first parent, so things get a little
more complicated. Also when 'B' is ignored as merge-base, the merge-base
needs to be recalculated to be 'initial'.

Anyhow, the idea is to show it like this:

    * main
    |\
    * | C
    | * sync with main
    * | B
    | * A
    * initial

If you don't like my proposal of being fully disconnected from the
merge-base, we could consider using a different symbol for "truncated"
history:

    * main
    |\
    * | C
    | + sync with main
    * | B
    | + A
    * initial

The commits with a '+' have more parents but they are not shown.

> How does this interact with --boundary?

Haven't tried it yet.

> Speaking of which, boundary commits are listed last. Since they need to
> be linked to the commits for which they are the boundary, a whole lot of
> these "unnecessary" lines accumulate the longer the list of commits is.

That's good to know, when I continue work on this feature.

> If only there were a way to show boundary commits as soon as possible,
> then this accumulation would not happen.

I'll need to dive deeper into this to understand what you're saying
here.

-- 
Cheers,
Toon

Re: [PATCH RFC] graph: implement git-log(1) --untangle

[Johannes Sixt]

Am 09.02.26 um 07:38 schrieb Toon Claes:
> ... Display in some way part of the
> history is missing, maybe by showing a '.' in the graph:
> 
>     *
>     |\
>     | *
>     | *
>     | .
>     *
>     |\
>     * *
>     |/
>     *
>     *
> 
> This indicates a piece of the history is truncated. I'm still on the
> fence about this

I like this. The line with the fullstop can then show a hint where the
graph continues, perhaps "(see 123abc456 below)" or something.

>     * main
>     |\
>     * | C
>     | * sync with main
>     | |\
>     | |/
>     |/|
>     * | B
>     | * A
>     |/
>     * initial
> 
> So here there merge-base isn't the first parent, so things get a little
> more complicated. Also when 'B' is ignored as merge-base, the merge-base
> needs to be recalculated to be 'initial'.
> 
> Anyhow, the idea is to show it like this:
> 
>     * main
>     |\
>     * | C
>     | * sync with main
>     * | B
>     | * A
>     * initial

If only the history leading up to 'sync with maint' is shown, it would
look like this:

    * sync with main
    |\
    | * B
    | .
    * A
    * initial

I would expect this sub-graph to occur when the full history is
displayed. IMO it's wrong to treat 'sync with main' differently just
because it is an ancestor of a another merge commit, as you suggested.

But, of course, the truncated connection between 'initial' and B
contradicts what would be expected for the full history (no truncation).
So, I don't know...

-- Hannes

Re: [PATCH RFC] graph: implement git-log(1) --untangle

[Junio C Hamano]

Toon Claes <toon@iotcl.com> writes:

> I've been thinking about something else. Display in some way part of the
> history is missing, maybe by showing a '.' in the graph:
>
>     *
>     |\
>     | *
>     | *
>     | .
>     *
>     |\
>     * *
>     |/
>     *
>     *
>
> This indicates a piece of the history is truncated. I'm still on the
> fence about this

It has been quite a while since I used gitk the last time, but I
recall it did something similar.  Instead of saying "I removed line
from here so you do not know where the other end of it is", it drew
a little down arrow and there was some way to find the matching up
arrow further down in the graph (either being in the same color or
perhaps clicking on one end jumped you to the other one, taking
advantage of being interactive program, I do not recall the
details).  I wnder if we can "label" your "." above with something
like (a)..(z)(aa)..(az).. or something?