[PATCH v2 08/10] ref-filter: use generation number for --contains

[Derrick Stolee]

A commit A can reach a commit B only if the generation number of A
is strictly larger than the generation number of B. This condition
allows significantly short-circuiting commit-graph walks.

Use generation number for '--contains' type queries.

On a copy of the Linux repository where HEAD is containd in v4.13
but no earlier tag, the command 'git tag --contains HEAD' had the
following peformance improvement:

Before: 0.81s
After:  0.04s
Rel %:  -95%

Helped-by: Jeff King <p...@peff.net>
Signed-off-by: Derrick Stolee <dsto...@microsoft.com>
---
 ref-filter.c | 24 +++++++++++++++++++-----
 1 file changed, 19 insertions(+), 5 deletions(-)

diff --git a/ref-filter.c b/ref-filter.c
index 45fc56216a..2f5e79b5de 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -1584,7 +1584,8 @@ static int in_commit_list(const struct commit_list *want, 
struct commit *c)
  */
 static enum contains_result contains_test(struct commit *candidate,
                                          const struct commit_list *want,
-                                         struct contains_cache *cache)
+                                         struct contains_cache *cache,
+                                         uint32_t cutoff)
 {
        enum contains_result *cached = contains_cache_at(cache, candidate);
 
@@ -1598,8 +1599,11 @@ static enum contains_result contains_test(struct commit 
*candidate,
                return CONTAINS_YES;
        }
 
-       /* Otherwise, we don't know; prepare to recurse */
        parse_commit_or_die(candidate);
+
+       if (candidate->generation < cutoff)
+               return CONTAINS_NO;
+
        return CONTAINS_UNKNOWN;
 }
 
@@ -1615,8 +1619,18 @@ static enum contains_result contains_tag_algo(struct 
commit *candidate,
                                              struct contains_cache *cache)
 {
        struct contains_stack contains_stack = { 0, 0, NULL };
-       enum contains_result result = contains_test(candidate, want, cache);
+       enum contains_result result;
+       uint32_t cutoff = GENERATION_NUMBER_INFINITY;
+       const struct commit_list *p;
+
+       for (p = want; p; p = p->next) {
+               struct commit *c = p->item;
+               parse_commit_or_die(c);
+               if (c->generation < cutoff)
+                       cutoff = c->generation;
+       }
 
+       result = contains_test(candidate, want, cache, cutoff);
        if (result != CONTAINS_UNKNOWN)
                return result;
 
@@ -1634,7 +1648,7 @@ static enum contains_result contains_tag_algo(struct 
commit *candidate,
                 * If we just popped the stack, parents->item has been marked,
                 * therefore contains_test will return a meaningful yes/no.
                 */
-               else switch (contains_test(parents->item, want, cache)) {
+               else switch (contains_test(parents->item, want, cache, cutoff)) 
{
                case CONTAINS_YES:
                        *contains_cache_at(cache, commit) = CONTAINS_YES;
                        contains_stack.nr--;
@@ -1648,7 +1662,7 @@ static enum contains_result contains_tag_algo(struct 
commit *candidate,
                }
        }
        free(contains_stack.contains_stack);
-       return contains_test(candidate, want, cache);
+       return contains_test(candidate, want, cache, cutoff);
 }
 
 static int commit_contains(struct ref_filter *filter, struct commit *commit,
-- 
2.17.0