[PATCH v9 0/4] graph: indent visual roots in graph

[Pablo Sabater <pabloosabaterr@gmail.com>]

When rendering a graph, if the history contains multiple "visual roots",
actual roots or commits that look like roots (i.e. have their parents
filtered out) can end up being vertically adjacent to unrelated commits,
falsely appearing to be related.

A fix for this issue was already attempted [1] a while ago.

This series adds indentation to the visual root commits, so they cannot be
vertically adjacent anymore making it easier to identify them.

Before indentation:

	* A
	* B1
	* B2
	* C1
	* C2

After indentation:

	  * A
	* B1
	 \
	  * B2
	* C1
	* C2

Indents the visual root commits that have still commits to show after
them, and if they have children it connects them with an edge at a new
row.

If there are multiple visual roots adjacent in history, the indentation
starts with the second one, avoiding redundant indentation of the first
one and cascades after the second.

	* A
	  * B
	    * C
	* D1
	* D2

This series first commit is a cleanup that brings a common function
from t4215 and t6016 to a graph functions file which they both use, so
the new test file for indentation, t4218, can use it as well.

GitHub CI: https://github.com/pabloosabaterr/git/actions/runs/29154333559

[1]: https://lore.kernel.org/git/xmqqwnwajbuj.fsf@gitster.c.googlers.com/

V8 DIFF:

- Checking if the parents of a commit are NULL is not enough to know if
  the commit is a visual root due to options that filter the commit
  parents but they do not remove them (--author, --grep, etc).
  At graph_is_visual_root_candidate(), iterate the parents and call
  graph_is_interesting() for each of them to know whether they will be
  shown or not.
- Add a --author and a --grep test.

Signed-off-by: Pablo Sabater <pabloosabaterr@gmail.com>

---
Pablo Sabater (4):
      lib-log-graph: move check_graph function
      revision: add next_commit_to_show()
      graph: add a 2 commit buffer for lookahead
      graph: indent visual root in graph

 graph.c                                    | 295 +++++++++++++++++
 graph.h                                    |  17 +
 revision.c                                 |  48 ++-
 t/lib-log-graph.sh                         |   5 +
 t/meson.build                              |   1 +
 t/t4215-log-skewed-merges.sh               |  33 +-
 t/t4218-log-graph-indentation.sh           | 514 +++++++++++++++++++++++++++++
 t/t6016-rev-list-graph-simplify-history.sh |  25 +-
 8 files changed, 893 insertions(+), 45 deletions(-)

Range-diff versus v8:

1:  ce4f6419c2 = 1:  22ab444372 lib-log-graph: move check_graph function
2:  8c7326745e = 2:  ebb88c8b29 revision: add next_commit_to_show()
3:  f2e895c72b = 3:  0705ee321e graph: add a 2 commit buffer for lookahead
4:  90d5d22344 ! 4:  fa2e60fb3f graph: indent visual root in graph
    @@ graph.c: void graph_push_lookahead(struct git_graph *graph, struct commit *c)
     + * - It has parents but they are all filtered out and
     + *   commit->parents arrives NULL.
     + *
    ++ * - Its parents are uninteresting.
    ++ *
     + * - It is not a boundary commit. Boundary commits also have no visible
     + *   parents, but they are not selected as visual roots because they cannot
     + *   cause the ambiguity of being vertically adjacent because:
    @@ graph.c: void graph_push_lookahead(struct git_graph *graph, struct commit *c)
     + *      ancestor of the boundary it would be excluded and not rendered.
     + *      Boundaries therefore always sink to the bottom.
     + */
    -+static int graph_is_visual_root_candidate(struct commit *c)
    ++static int graph_is_visual_root_candidate(struct commit *c, struct git_graph *graph)
     +{
    -+	return c->parents == NULL && !(c->object.flags & BOUNDARY);
    ++	struct commit_list *p;
    ++
    ++	if (c->object.flags & BOUNDARY)
    ++		return 0;
    ++	for (p = c->parents; p; p = p->next)
    ++		if (graph_is_interesting(graph, p->item))
    ++			return 0;
    ++	return 1;
     +}
     +
     +static int graph_is_visual_root(struct git_graph *graph,
    @@ graph.c: void graph_push_lookahead(struct git_graph *graph, struct commit *c)
     +	 * current commit has to act as the last commit and omit
     +	 * indentation.
     +	 */
    -+	return graph_is_visual_root_candidate(graph->commit) &&
    ++	return graph_is_visual_root_candidate(graph->commit, graph) &&
     +	       !(graph->commit_in_columns &&
     +		 graph->columns[graph->commit_index].is_merge_parent) &&
     +	       flags->is_next_visible &&
    @@ graph.c: void graph_push_lookahead(struct git_graph *graph, struct commit *c)
     +	flags->next_has_column =
     +		graph_find_new_column_by_commit(graph, graph->lookahead[0]) >= 0;
     +
    -+	if (!graph_is_visual_root_candidate(graph->lookahead[0]))
    ++	if (!graph_is_visual_root_candidate(graph->lookahead[0], graph))
     +		return;
     +
     +	if (graph->lookahead_nr >= 2)
    @@ t/t4218-log-graph-indentation.sh (new)
     +	EOF
     +'
     +
    ++# when the graph commits are filtered with regex options like --author, the
    ++# commit parents do not come NULL so it is needed to check if the parents are
    ++# interesting.
    ++test_expect_success '--author skipped parent makes a visual root' '
    ++	create_orphan _55 &&
    ++	test_tick &&
    ++	git commit --allow-empty -m 55_A &&
    ++	create_orphan _54 &&
    ++	test_tick &&
    ++	git commit --allow-empty --author="Other <other@example.com>" -m 54_A &&
    ++	test_tick &&
    ++	git commit --allow-empty -m 54_B &&
    ++	test_tick &&
    ++	git commit --allow-empty -m 54_C &&
    ++	lib_test_check_graph --author="A U Thor" _54 _55 <<-\EOF
    ++	* 54_C
    ++	 \
    ++	  * 54_B
    ++	* 55_A
    ++	EOF
    ++'
    ++
    ++test_expect_success '--grep skipped parent makes a visual root' '
    ++	create_orphan _57 &&
    ++	test_tick &&
    ++	git commit --allow-empty -m 57_keep_A &&
    ++	create_orphan _56 &&
    ++	test_tick &&
    ++	git commit --allow-empty -m 56_skip &&
    ++	test_tick &&
    ++	git commit --allow-empty -m 56_keep_A &&
    ++	test_tick &&
    ++	git commit --allow-empty -m 56_keep_B &&
    ++	lib_test_check_graph --grep=keep _56 _57 <<-\EOF
    ++	* 56_keep_B
    ++	 \
    ++	  * 56_keep_A
    ++	* 57_keep_A
    ++	EOF
    ++'
    ++
     +test_done

---
base-commit: f85a7e662054a7b0d9070e432508831afa214b47