[RFC PATCH 03/13] commit-reach: move commit_contains from ref-filter
Signed-off-by: Derrick Stolee <dstolee@microsoft.com>
---
commit-reach.c | 119 +++++++++++++++++++++++++++++++++++++++
commit-reach.h | 44 +++++----------
fast-import.c | 1 +
ref-filter.c | 147 +++----------------------------------------------
4 files changed, 141 insertions(+), 170 deletions(-)
diff --git a/commit-reach.c b/commit-reach.c
index 80cdb738f6..6cfd7379ce 100644
--- a/commit-reach.c
+++ b/commit-reach.c
@@ -409,3 +409,122 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
unmark_and_free(used, TMP_MARK);
return found;
}
+
+/*
+ * 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(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);
+}
+
+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);
+}
diff --git a/commit-reach.h b/commit-reach.h
index 35ec9f0ddb..986fb388d5 100644
--- a/commit-reach.h
+++ b/commit-reach.h
@@ -2,42 +2,24 @@
#define __COMMIT_REACH_H__
#include "commit.h"
+#include "commit-slab.h"
+#include "ref-filter.h"
-struct commit_list *get_merge_bases_many(struct commit *one,
- int n,
- struct commit **twos);
-struct commit_list *get_merge_bases_many_dirty(struct commit *one,
- int n,
- struct commit **twos);
-struct commit_list *get_merge_bases(struct commit *one, struct commit *two);
-struct commit_list *get_octopus_merge_bases(struct commit_list *in);
-
-/* To be used only when object flags after this call no longer matter */
-struct commit_list *get_merge_bases_many_dirty(struct commit *one, int n, struct commit **twos);
-
-int is_descendant_of(struct commit *commit, struct commit_list *with_commit);
-int in_merge_bases_many(struct commit *commit, int nr_reference, struct commit **reference);
-int in_merge_bases(struct commit *commit, struct commit *reference);
-
+int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);
/*
- * Takes a list of commits and returns a new list where those
- * have been removed that can be reached from other commits in
- * the list. It is useful for, e.g., reducing the commits
- * randomly thrown at the git-merge command and removing
- * redundant commits that the user shouldn't have given to it.
- *
- * This function destroys the STALE bit of the commit objects'
- * flags.
+ * Unknown has to be "0" here, because that's the default value for
+ * contains_cache slab entries that have not yet been assigned.
*/
-struct commit_list *reduce_heads(struct commit_list *heads);
+enum contains_result {
+ CONTAINS_UNKNOWN = 0,
+ CONTAINS_NO,
+ CONTAINS_YES
+};
-/*
- * Like `reduce_heads()`, except it replaces the list. Use this
- * instead of `foo = reduce_heads(foo);` to avoid memory leaks.
- */
-void reduce_heads_replace(struct commit_list **heads);
+define_commit_slab(contains_cache, enum contains_result);
-int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid);
+int commit_contains(struct ref_filter *filter, struct commit *commit,
+ struct commit_list *list, struct contains_cache *cache);
#endif
diff --git a/fast-import.c b/fast-import.c
index 4d55910ab9..49ce8e8426 100644
--- a/fast-import.c
+++ b/fast-import.c
@@ -171,6 +171,7 @@ Format of STDIN stream:
#include "packfile.h"
#include "object-store.h"
#include "mem-pool.h"
+#include "commit-reach.h"
#define PACK_ID_BITS 16
#define MAX_PACK_ID ((1<<PACK_ID_BITS)-1)
diff --git a/ref-filter.c b/ref-filter.c
index fa3685d91f..f4f71728ae 100644
--- a/ref-filter.c
+++ b/ref-filter.c
@@ -16,7 +16,7 @@
#include "trailer.h"
#include "wt-status.h"
#include "commit-slab.h"
-#include "commit-graph.h"
+#include "commit-reach.h"
static struct ref_msg {
const char *gone;
@@ -1620,144 +1620,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(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"
@@ -1984,6 +1846,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.
--
2.18.0.118.gd4f65b8d14
Derrick Stolee <dstolee@microsoft.com>