[RFC PATCH 12/13] commit-reach: use is_descendant_of for ref_newer

[Derrick Stolee <dstolee@microsoft.com>]

The ref_newer method is used by 'git push' to detect if a force-push is
requried. This method does not use any kind of cutoff when walking, so
in the case of a force-push will walk all reachable commits.

The is_descendant_of method already uses paint_down_to_common along with
cutoffs. By translating the ref_newer arguments into the commit and
commit_list required by is_descendant_of, we can have one fewer commit
walk and also improve our performance!

For a copy of the Linux repository, 'test-tool reach ref_newer' presents
the following improvements with the specified input.

Input
-----
A:v4.9
B:v3.19

Before: 0.11 s
 After: 0.10 s

To test the negative case, add a new commit with parent v3.19,
regenerate the commit-graph, and then run with B pointing at that
commit.

Before: 0.52 s
 After: 0.12 s

Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
 commit-reach.c | 17 ++++-------------
 commit.c       |  7 +++++--
 commit.h       |  6 +++++-
 fetch-pack.c   |  3 ++-
 sha1-name.c    |  3 ++-
 walker.c       |  3 ++-
 6 files changed, 20 insertions(+), 19 deletions(-)

diff --git a/commit-reach.c b/commit-reach.c
index 8e24455d9f..249e9a4fac 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -376,7 +376,7 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
 {
 	struct object *o;
 	struct commit *old_commit, *new_commit;
-	struct commit_list *list, *used;
+	struct commit_list *list = NULL;
 	int found = 0;
 
 	/*
@@ -396,18 +396,9 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
 	if (parse_commit(new_commit) < 0)
 		return 0;
 
-	used = list = NULL;
-	commit_list_insert(new_commit, &list);
-	while (list) {
-		new_commit = pop_most_recent_commit(&list, TMP_MARK);
-		commit_list_insert(new_commit, &used);
-		if (new_commit == old_commit) {
-			found = 1;
-			break;
-		}
-	}
-	unmark_and_free(list, TMP_MARK);
-	unmark_and_free(used, TMP_MARK);
+	commit_list_insert(old_commit, &list);
+	found = is_descendant_of(new_commit, list);
+	free_commit_list(list);
 	return found;
 }
 
diff --git a/commit.c b/commit.c
index d4ddaf4879..9870682673 100644
--- a/commit.c
+++ b/commit.c
@@ -556,7 +556,8 @@ void commit_list_sort_by_date(struct commit_list **list)
 }
 
 struct commit *pop_most_recent_commit(struct commit_list **list,
-				      unsigned int mark)
+				      unsigned int mark,
+				      uint32_t min_generation)
 {
 	struct commit *ret = pop_commit(list);
 	struct commit_list *parents = ret->parents;
@@ -565,7 +566,9 @@ struct commit *pop_most_recent_commit(struct commit_list **list,
 		struct commit *commit = parents->item;
 		if (!parse_commit(commit) && !(commit->object.flags & mark)) {
 			commit->object.flags |= mark;
-			commit_list_insert_by_date(commit, list);
+
+			if (commit->generation >= min_generation)
+				commit_list_insert_by_date(commit, list);
 		}
 		parents = parents->next;
 	}
diff --git a/commit.h b/commit.h
index 7e0f273720..5eaeded5e2 100644
--- a/commit.h
+++ b/commit.h
@@ -159,9 +159,13 @@ extern const char *skip_blank_lines(const char *msg);
 
 /** Removes the first commit from a list sorted by date, and adds all
  * of its parents.
+ *
+ * The parents are not added if their generation number is strictly
+ * lower than min_generation.
  **/
 struct commit *pop_most_recent_commit(struct commit_list **list,
-				      unsigned int mark);
+				      unsigned int mark,
+				      uint32_t min_generation);
 
 struct commit *pop_commit(struct commit_list **stack);
 
diff --git a/fetch-pack.c b/fetch-pack.c
index a320ce9872..351e3d4bcd 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -600,7 +600,8 @@ static void mark_recent_complete_commits(struct fetch_pack_args *args,
 	while (complete && cutoff <= complete->item->date) {
 		print_verbose(args, _("Marking %s as complete"),
 			      oid_to_hex(&complete->item->object.oid));
-		pop_most_recent_commit(&complete, COMPLETE);
+		pop_most_recent_commit(&complete, COMPLETE,
+				       GENERATION_NUMBER_ZERO);
 	}
 }
 
diff --git a/sha1-name.c b/sha1-name.c
index 60d9ef3c7e..471a54464d 100644
--- a/sha1-name.c
+++ b/sha1-name.c
@@ -1141,7 +1141,8 @@ static int get_oid_oneline(const char *prefix, struct object_id *oid,
 		struct commit *commit;
 		int matches;
 
-		commit = pop_most_recent_commit(&list, ONELINE_SEEN);
+		commit = pop_most_recent_commit(&list, ONELINE_SEEN,
+						GENERATION_NUMBER_ZERO);
 		if (!parse_object(&commit->object.oid))
 			continue;
 		buf = get_commit_buffer(commit, NULL);
diff --git a/walker.c b/walker.c
index 0b162a09b9..e243fc8768 100644
--- a/walker.c
+++ b/walker.c
@@ -78,7 +78,8 @@ static int process_commit(struct walker *walker, struct commit *commit)
 		return -1;
 
 	while (complete && complete->item->date >= commit->date) {
-		pop_most_recent_commit(&complete, COMPLETE);
+		pop_most_recent_commit(&complete, COMPLETE,
+				       GENERATION_NUMBER_ZERO);
 	}
 
 	if (commit->object.flags & COMPLETE)
-- 
2.18.0.118.gd4f65b8d14