[PATCH v10 3.4/3.7] fixup! history: add squash subcommand to fold a range

From: Phillip Wood <[email protected]>

Reject ranges with more than one tip

Given

          C
         /
    A - B - D

then

   git history squash ^A C D

should fail because the way we squash commits assumes the range has
a single tip. While we might want to support multiple tips in the
future lets not complicate things now.

To check for multiple tips mark each commit we see as a tip and
increment a tip counter, then, iterate over the parents of each commit,
removing the mark and decrementing the counter if the mark was set. As
we have to iterate over the parents anyway, stop using "--boundary"
and check that we've seen each parent before which allows us to
produce a better error message.

Note: I'm not sure what our policy is with respect to adding new
users of object flags. If that's a problem, we could use a commit
slab instead.

Signed-off-by: Phillip Wood <[email protected]>
---
 builtin/history.c         | 80 ++++++++++++++++++++++++---------------
 object.h                  |  1 +
 t/t3455-history-squash.sh | 19 ++++++++--
 3 files changed, 65 insertions(+), 35 deletions(-)

diff --git a/builtin/history.c b/builtin/history.c
index 4dcfdb109d..bb4a74ec1a 100644
--- a/builtin/history.c
+++ b/builtin/history.c
@@ -1006,6 +1006,10 @@ static int cmd_history_split(int argc,
 	release_revisions(&revs);
 	return ret;
 }
+
+/*Remember to update object flag allocation in object.h */
+#define SQUASH_SEEN (1u << 11)
+#define SQUASH_TIP (1u << 12)
 
 /*
  * Resolve a "<base>..<tip>" revision range into the base commit just outside
@@ -1023,16 +1027,14 @@ static int resolve_squash_range(struct repository *repo,
 {
 	struct rev_info revs;
 	struct commit *commit, *base = NULL, *oldest = NULL, *tip = NULL;
-	struct commit_list *boundaries = NULL, *b;
 	size_t i;
-	int ret;
+	int ret, tip_count = 0;
 
 	repo_init_revisions(repo, &revs, NULL);
 	revs.reverse = 1;
 	revs.topo_order = 1;
 	revs.sort_order = REV_SORT_IN_GRAPH_ORDER;
 	revs.simplify_history = 0;
-	revs.boundary = 1;
 	revs.ancestry_path = 1;
 	revs.limited = 1;
 	revs.ancestry_path_implicit_bottoms = 1;
@@ -1045,7 +1047,7 @@ static int resolve_squash_range(struct repository *repo,
 
 	if (revs.reverse != 1 || revs.topo_order != 1 ||
 	    revs.sort_order != REV_SORT_IN_GRAPH_ORDER ||
-	    revs.simplify_history != 0 || revs.boundary != 1 ||
+	    revs.simplify_history != 0 || revs.boundary == 1 ||
 	    revs.ancestry_path != 1 || revs.limited != 1 ||
 	    revs.ancestry_path_implicit_bottoms != 1) {
 		warning(_("ignoring rev-list options that would change how the "
@@ -1054,7 +1056,7 @@ static int resolve_squash_range(struct repository *repo,
 		revs.topo_order = 1;
 		revs.sort_order = REV_SORT_IN_GRAPH_ORDER;
 		revs.simplify_history = 0;
-		revs.boundary = 1;
+		revs.boundary = 0;
 		revs.ancestry_path = 1;
 		revs.limited = 1;
 		revs.ancestry_path_implicit_bottoms = 1;
@@ -1077,59 +1079,75 @@ static int resolve_squash_range(struct repository *repo,
 		ret = error(_("error preparing revisions"));
 		goto out;
 	}
-
-	/*
-	 * Set boundary commits aside for the base check below, and put every
-	 * in-range commit but the tip into the interior set. A ref pointing
-	 * at an interior commit would dangle once the range is folded away.
-	 */
 	while ((commit = get_revision(&revs))) {
-		if (commit->object.flags & BOUNDARY) {
-			commit_list_insert(commit, &boundaries);
-			continue;
-		}
+		struct commit_list *p;
+
 		if (!commit->parents) {
 			ret = error(_("cannot squash down to root commit"));
 			goto out;
+		}
+		for (p = commit->parents; oldest && p; p = p->next) {
+			struct commit_list *q;
+			struct object *o;
+			bool seen;
+
+			if (repo_parse_commit(repo, p->item)) {
+				ret = error(_("cannot parse commit"));
+				goto out;
+			}
+			o = &p->item->object;
+			seen = o->flags & SQUASH_SEEN;
+			/*
+			 * Allow parents that match the parents of the
+			 * squashed commit.
+			 */
+			for (q = oldest->parents; !seen && q; q = q->next)
+				seen = p->item == q->item;
+			if (!seen) {
+				ret = error(_("parent %s of commit %s is "
+					      "outside the revision range"),
+					    repo_find_unique_abbrev(repo, &o->oid,
+								    DEFAULT_ABBREV),
+					    repo_find_unique_abbrev(repo, &commit->object.oid,
+								    DEFAULT_ABBREV));
+				goto out;
+			}
+			if (o->flags & SQUASH_TIP) {
+				tip_count--;
+				o->flags &= ~SQUASH_TIP;
+			}
 		}
 		if (!oldest)
 			oldest = commit;
 		if (tip)
 			oidset_insert(interior_out, &tip->object.oid);
 		tip = commit;
+		tip->object.flags |= SQUASH_SEEN | SQUASH_TIP;
+		tip_count++;
 	}
-
-	if (!oldest) {
+	if (!tip_count) {
 		ret = error(_("the revision range is empty"));
 		goto out;
-	} else if (oldest == tip) {
+	} else if (tip_count != 1) {
+		  ret = error(_("the revision range contains more than one tip "
+				"commit"));
+		  goto out;
+	  } else if (oldest == tip) {
 		ret = error(_("the revision range holds a single commit; "
 			      "nothing to squash"));
 		goto out;
 	} else if (!oldest->parents) {
 		BUG("an in-range commit must have a parent");
 	}
 	base = oldest->parents->item;
-
-	/*
-	 * A boundary other than the base is an in-range commit reaching a
-	 * commit outside the range, so the range has more than one base.
-	 */
-	for (b = boundaries; b; b = b->next) {
-		if (b->item != base) {
-			ret = error(_("the revision range has more than one base; "
-				      "cannot squash"));
-			goto out;
-		}
-	}
 
 	*base_out = base;
 	*oldest_out = oldest;
 	*tip_out = tip;
 	ret = 0;
 
 out:
-	commit_list_free(boundaries);
+	clear_object_flags(repo, SQUASH_SEEN | SQUASH_TIP);
 	reset_revision_walk();
 	release_revisions(&revs);
 	return ret;
diff --git a/object.h b/object.h
index 8fb03ff90a..ad18ffcc55 100644
--- a/object.h
+++ b/object.h
@@ -74,6 +74,7 @@ void object_array_init(struct object_array *array);
  * bisect.c:                                        16
  * bundle.c:                                        16
  * http-push.c:                          11-----14
+ * builtin/history.c:                    11-12
  * commit-graph.c:                                15
  * commit-reach.c:                                  16-------20
  * builtin/last-modified.c:                         1617
diff --git a/t/t3455-history-squash.sh b/t/t3455-history-squash.sh
index b181f93892..ba826df592 100755
--- a/t/t3455-history-squash.sh
+++ b/t/t3455-history-squash.sh
@@ -33,8 +33,7 @@ check_log_messages () {
 }
 
 test_expect_success 'setup linear history touching two files' '
-	test_commit base file a &&
-	git tag start &&
+	test_commit base file a start &&
 	test_commit --no-tag one other x &&
 	test_commit --no-tag two file c &&
 	test_commit three file d
@@ -76,6 +75,18 @@ test_expect_success 'rejects root commit' '
 	test_must_fail git history squash --ancestry-path=start $oid..three 2>err &&
 	echo "error: cannot squash down to root commit" >expect &&
 	test_cmp expect err
+'
+
+test_expect_success 'rejects multiple tips' '
+	oid=$(git commit-tree -m tip -p start^0 three^{tree}) &&
+	test_must_fail git history squash ^start $oid three~1 2>err &&
+	echo "error: the revision range contains more than one tip commit" >expect &&
+	test_cmp expect err &&
+
+	git reset --hard three &&
+	git history squash ^start three~1 three &&
+	test_cmp_rev HEAD~1 start^0 &&
+	test_cmp_rev HEAD^{tree} three^{tree}
 '
 
 test_expect_success 'accepts multiple revision arguments with an exclusion' '
@@ -404,7 +415,7 @@ test_expect_success 'refuses a merge whose other parent is outside the range' '
 	merged=$(git rev-parse HEAD) &&
 
 	test_must_fail git history squash "$base.." 2>err &&
-	test_grep "more than one base" err &&
+	test_grep "parent .* of commit .* is outside the revision range" err &&
 	test_cmp_rev "$merged" HEAD
 '
 
@@ -533,7 +544,7 @@ test_expect_success 'refuses an octopus merge with an arm forked before the base
 	git branch -D octo-pre octo-within &&
 
 	test_must_fail git history squash "$octo_base.." 2>err &&
-	test_grep "more than one base" err &&
+	test_grep "parent .* of commit .* is outside the revision range" err &&
 	test_cmp_rev "$merged" HEAD
 '
 
-- 
2.54.0.200.gfd8d68259e3