git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[RFC/PATCH 3/3] simplify-merges: drop merge from irrelevant side branch

From
Kevin Bracey <kevin@bracey.fi>
Date
Apr 26, 2013, 19:31 UTC
Message-ID
<1367004718-30048-3-git-send-email-kevin@bracey.fi>
In-Reply-To
<1367004718-30048-1-git-send-email-kevin@bracey.fi>

Reimplement commit 4b7f53da on top of the new simplify-merges infrastructure, tightening the condition to only consider root parents; the original version incorrectly dropped parents that were TREESAME to anything.

Original log message follows.

The merge simplification rule stated in 6546b59 (revision traversal: show full history with merge simplification, 2008-07-31) still treated merge commits too specially. Namely, in a history with this shape:

	---o---o---M
	          /
         x---x---x

where three 'x' were on a history completely unrelated to the main history 'o' and do not touch any of the paths we are following, we still said that after simplifying all of the parents of M, 'x' (which is the leftmost 'x' that rightmost 'x simplifies down to) and 'o' (which would be the last commit on the main history that touches the paths we are following) are independent from each other, and both need to be kept.

That is incorrect; when the side branch 'x' never touches the paths, it should be removed to allow M to simplify down to the last commit on the main history that touches the paths.

Suggested-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Kevin Bracey <kevin@bracey.fi>
---
 Documentation/rev-list-options.txt | 35 ++++++++++++++++++++++-------------
 revision.c                         | 26 +++++++++++++++++++++++++-
 t/t6012-rev-list-simplify.sh       |  2 +-
 3 files changed, 48 insertions(+), 15 deletions(-)
diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt
index 0832004..db45401 100644
--- a/Documentation/rev-list-options.txt
+++ b/Documentation/rev-list-options.txt
@@ -342,13 +342,13 @@ In the following, we will always refer to the same example history to
 illustrate the differences between simplification settings.  We assume
 that you are filtering for a file `foo` in this commit graph:
 -----------------------------------------------------------------------
-	  .-A---M---N---O---P
-	 /     /   /   /   /
-	I     B   C   D   E
-	 \   /   /   /   /
-	  `-------------'
+	  .-A---M---N---O---P---Q
+	 /     /   /   /   /   /
+	I     B   C   D   E   Y
+	 \   /   /   /   /   /
+	  `-------------'   X
 -----------------------------------------------------------------------
-The horizontal line of history A---P is taken to be the first parent of
+The horizontal line of history A---Q is taken to be the first parent of
 each merge.  The commits are:
 
 * `I` is the initial commit, in which `foo` exists with contents
@@ -370,6 +370,10 @@ each merge.  The commits are:
   strings to "quux xyzzy".  Despite appearing interesting, `P` is
   TREESAME to all parents.
 
+* `X` is an indpendent root commit that added a new file `side`, and `Y`
+  modified it. `Y` is TREESAME to `X`. Its merge `Q` added `side` to `P`, and
+  `Q` is TREESAME to all parents.
+
 'rev-list' walks backwards through history, including or excluding
 commits based on whether '\--full-history' and/or parent rewriting
 (via '\--parents' or '\--children') are used.  The following settings
@@ -413,7 +417,7 @@ parent lines.
 	I  A  B  N  D  O
 -----------------------------------------------------------------------
 +
-`P` and `M` were excluded because they are TREESAME to both parents.  `E`,
+`Q`, `P` and `M` were excluded because they are TREESAME to both parents.  `E`,
 `C` and `B` were all walked, but only `B` was !TREESAME, so the others
 do not appear.
 +
@@ -431,7 +435,7 @@ Along each parent, prune away commits that are not included
 themselves.  This results in
 +
 -----------------------------------------------------------------------
-	  .-A---M---N---O---P
+	  .-A---M---N---O---P---Q
 	 /     /   /   /   /
 	I     B   /   D   /
 	 \   /   /   /   /
@@ -441,7 +445,8 @@ themselves.  This results in
 Compare to '\--full-history' without rewriting above.  Note that `E`
 was pruned away because it is TREESAME, but the parent list of P was
 rewritten to contain `E`'s parent `I`.  The same happened for `C` and
-`N`.  Note also that `P` was included despite being TREESAME.
+`N`, and `X`, `Y` and `Q`.  Note also that `P` and `Q` were included despite
+being TREESAME.
 
 In addition to the above settings, you can change whether TREESAME
 affects inclusion:
@@ -471,9 +476,9 @@ history according to the following rules:
 * Set `C'` to `C`.
 +
 * Replace each parent `P` of `C'` with its simplification `P'`.  In
-  the process, drop parents that are ancestors of other parents, and
-  remove duplicates, but take care to never drop all parents that
-  we are TREESAME to.
+  the process, drop parents that are ancestors of other parents or that are
+  root commits TREESAME to an empty tree, and remove duplicates, but take care
+  to never drop all parents that we are TREESAME to.
 +
 * If after this parent rewriting, `C'` is a root or merge commit (has
   zero or >1 parents), a boundary commit, or !TREESAME, it remains.
@@ -491,7 +496,7 @@ The effect of this is best shown by way of comparing to
 	  `---------'
 -----------------------------------------------------------------------
 +
-Note the major differences in `N` and `P` over '--full-history':
+Note the major differences in `N`, `P` and `Q` over '--full-history':
 +
 --
 * `N`'s parent list had `I` removed, because it is an ancestor of the
@@ -499,6 +504,10 @@ Note the major differences in `N` and `P` over '--full-history':
 +
 * `P`'s parent list similarly had `I` removed.  `P` was then
   removed completely, because it had one parent and is TREESAME.
++
+* `Q`'s parent list had `Y` simplified to `X`. `X` was then removed, because it
+  was a TREESAME root. `Q` was then removed completely, because it had one
+  parent and is TREESAME.
 --
 
 Finally, there is a fifth simplification mode available:
diff --git a/revision.c b/revision.c
index 4e27c9a..67608e0 100644
--- a/revision.c
+++ b/revision.c
@@ -2102,6 +2102,22 @@ static int mark_redundant_parents(struct rev_info *revs, struct commit *commit)
 	return marked;
 }
 
+static int mark_treesame_root_parents(struct rev_info *revs, struct commit *commit)
+{
+	struct commit_list *p;
+	int marked = 0;
+
+	for (p = commit->parents; p; p = p->next) {
+		struct commit *parent = p->item;
+		if (!parent->parents && (parent->object.flags & TREESAME)) {
+			parent->object.flags |= TMP_MARK;
+			marked++;
+		}
+	}
+
+	return marked;
+}
+
 static int remove_marked_parents(struct rev_info *revs, struct commit *commit)
 {
 	struct treesame_state *ts = lookup_decoration(&revs->treesame, &commit->object);
@@ -2224,10 +2240,18 @@ static struct commit_list **simplify_one(struct rev_info *revs, struct commit *c
 	 *     /    /		o: a commit that touches the paths;
 	 * ---o----'
 	 *
-	 * Detect and simplify this case.
+	 * Further, a merge of an independent branch that doesn't
+	 * touch the path will reduce to a treesame root parent:
+	 *
+	 *  ----o----X		X: the commit we are looking at;
+	 *          /		o: a commit that touches the paths;
+	 *         r		r: a root commit not touching the paths
+	 *
+	 * Detect and simplify both cases.
 	 */
 	if (1 < cnt) {
 		int marked = mark_redundant_parents(revs, commit);
+		marked += mark_treesame_root_parents(revs, commit);
 		if (marked)
 			remove_marked_parents(revs, commit);
 	}
diff --git a/t/t6012-rev-list-simplify.sh b/t/t6012-rev-list-simplify.sh
index 4e55872..57ce239 100755
--- a/t/t6012-rev-list-simplify.sh
+++ b/t/t6012-rev-list-simplify.sh
@@ -110,7 +110,7 @@ check_result 'L K J I H G F E D C B A' --full-history
 check_result 'K I H E C B A' --full-history -- file
 check_result 'K I H E C B A' --full-history --topo-order -- file
 check_result 'K I H E C B A' --full-history --date-order -- file
-check_outcome failure 'I E C B A' --simplify-merges -- file
+check_result 'I E C B A' --simplify-merges -- file
 check_result 'I B A' -- file
 check_result 'I B A' --topo-order -- file
 check_result 'H' --first-parent -- another-file

-- 
1.8.2.1.632.gd2b1879
Previous: Junio C HamanoNext: Junio C Hamano
Message 19 of 25 in “Locating merge that dropped a change”
  1. Kevin BraceyApr 9, 2013
  2. Kevin BraceyApr 11, 2013
  3. Junio C HamanoApr 11, 2013
  4. Make --full-history consider more mergesKevin Bracey, Apr 22, 2013
  5. Junio C HamanoApr 22, 2013
  6. Kevin BraceyApr 23, 2013
  7. Junio C HamanoApr 24, 2013
  8. Junio C HamanoApr 25, 2013
  9. Kevin BraceyApr 25, 2013
  10. Junio C HamanoApr 25, 2013
  11. Kevin BraceyApr 25, 2013
  12. Junio C HamanoApr 25, 2013
  13. Kevin BraceyApr 26, 2013
  14. 1/3 revision.c: tighten up TREESAME handling of mergesKevin Bracey, Apr 26, 2013
  15. 2/3 simplify-merges: never remove all TREESAME parentsKevin Bracey, Apr 26, 2013
  16. Junio C HamanoApr 27, 2013
  17. Kevin BraceyApr 28, 2013
  18. Junio C HamanoApr 28, 2013
  19. 3/3 simplify-merges: drop merge from irrelevant side branchKevin Bracey, Apr 26, 2013
  20. Junio C HamanoApr 27, 2013
  21. David AguilarApr 27, 2013
  22. Kevin BraceyApr 28, 2013
  23. Junio C HamanoApr 28, 2013
  24. Kevin BraceyApr 29, 2013
  25. Junio C HamanoApr 29, 2013

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.