Merge branch 'bc/hash-independent-tests'
[gitweb.git] / ref-filter.c
index 0bccfceff2ae31200019838d9f2b67e13e32ef6f..e1bcb4ca8a1977e97b26da47962dfcd3781a021e 100644 (file)
@@ -19,6 +19,7 @@
 #include "wt-status.h"
 #include "commit-slab.h"
 #include "commit-graph.h"
+#include "commit-reach.h"
 
 static struct ref_msg {
        const char *gone;
@@ -263,6 +264,8 @@ static int trailers_atom_parser(const struct ref_format *format, struct used_ato
        struct string_list params = STRING_LIST_INIT_DUP;
        int i;
 
+       atom->u.contents.trailer_opts.no_divider = 1;
+
        if (arg) {
                string_list_split(&params, arg, ',', -1);
                for (i = 0; i < params.nr; i++) {
@@ -1673,144 +1676,6 @@ static int get_ref_atom_value(struct ref_array_item *ref, int atom,
        return 0;
 }
 
-/*
- * Unknown has to be "0" here, because that's the default value for
- * contains_cache slab entries that have not yet been assigned.
- */
-enum contains_result {
-       CONTAINS_UNKNOWN = 0,
-       CONTAINS_NO,
-       CONTAINS_YES
-};
-
-define_commit_slab(contains_cache, enum contains_result);
-
-struct ref_filter_cbdata {
-       struct ref_array *array;
-       struct ref_filter *filter;
-       struct contains_cache contains_cache;
-       struct contains_cache no_contains_cache;
-};
-
-/*
- * Mimicking the real stack, this stack lives on the heap, avoiding stack
- * overflows.
- *
- * At each recursion step, the stack items points to the commits whose
- * ancestors are to be inspected.
- */
-struct contains_stack {
-       int nr, alloc;
-       struct contains_stack_entry {
-               struct commit *commit;
-               struct commit_list *parents;
-       } *contains_stack;
-};
-
-static int in_commit_list(const struct commit_list *want, struct commit *c)
-{
-       for (; want; want = want->next)
-               if (!oidcmp(&want->item->object.oid, &c->object.oid))
-                       return 1;
-       return 0;
-}
-
-/*
- * Test whether the candidate is contained in the list.
- * Do not recurse to find out, though, but return -1 if inconclusive.
- */
-static enum contains_result contains_test(struct commit *candidate,
-                                         const struct commit_list *want,
-                                         struct contains_cache *cache,
-                                         uint32_t cutoff)
-{
-       enum contains_result *cached = contains_cache_at(cache, candidate);
-
-       /* If we already have the answer cached, return that. */
-       if (*cached)
-               return *cached;
-
-       /* or are we it? */
-       if (in_commit_list(want, candidate)) {
-               *cached = CONTAINS_YES;
-               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;
-}
-
-static void push_to_contains_stack(struct commit *candidate, struct contains_stack *contains_stack)
-{
-       ALLOC_GROW(contains_stack->contains_stack, contains_stack->nr + 1, contains_stack->alloc);
-       contains_stack->contains_stack[contains_stack->nr].commit = candidate;
-       contains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;
-}
-
-static enum contains_result contains_tag_algo(struct commit *candidate,
-                                             const struct commit_list *want,
-                                             struct contains_cache *cache)
-{
-       struct contains_stack contains_stack = { 0, 0, NULL };
-       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;
-               load_commit_graph_info(the_repository, c);
-               if (c->generation < cutoff)
-                       cutoff = c->generation;
-       }
-
-       result = contains_test(candidate, want, cache, cutoff);
-       if (result != CONTAINS_UNKNOWN)
-               return result;
-
-       push_to_contains_stack(candidate, &contains_stack);
-       while (contains_stack.nr) {
-               struct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];
-               struct commit *commit = entry->commit;
-               struct commit_list *parents = entry->parents;
-
-               if (!parents) {
-                       *contains_cache_at(cache, commit) = CONTAINS_NO;
-                       contains_stack.nr--;
-               }
-               /*
-                * 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, cutoff)) {
-               case CONTAINS_YES:
-                       *contains_cache_at(cache, commit) = CONTAINS_YES;
-                       contains_stack.nr--;
-                       break;
-               case CONTAINS_NO:
-                       entry->parents = parents->next;
-                       break;
-               case CONTAINS_UNKNOWN:
-                       push_to_contains_stack(parents->item, &contains_stack);
-                       break;
-               }
-       }
-       free(contains_stack.contains_stack);
-       return contains_test(candidate, want, cache, cutoff);
-}
-
-static int commit_contains(struct ref_filter *filter, struct commit *commit,
-                          struct commit_list *list, struct contains_cache *cache)
-{
-       if (filter->with_commit_tag_algo)
-               return contains_tag_algo(commit, list, cache) == CONTAINS_YES;
-       return is_descendant_of(commit, list);
-}
-
 /*
  * Return 1 if the refname matches one of the patterns, otherwise 0.
  * A pattern can be a literal prefix (e.g. a refname "refs/heads/master"
@@ -2046,6 +1911,13 @@ static int filter_ref_kind(struct ref_filter *filter, const char *refname)
        return ref_kind_from_refname(refname);
 }
 
+struct ref_filter_cbdata {
+       struct ref_array *array;
+       struct ref_filter *filter;
+       struct contains_cache contains_cache;
+       struct contains_cache no_contains_cache;
+};
+
 /*
  * A call-back given to for_each_ref().  Filter refs and keep them for
  * later object processing.