Re: [PATCH 01/16] commit-reach: move walk methods from commit.c

2018-07-16 Thread Jonathan Tan 
> +/* Remember to update object flag allocation in object.h */
> +#define PARENT1  (1u<<16)
> +#define PARENT2  (1u<<17)
> +#define STALE(1u<<18)
> +#define RESULT   (1u<<19)

Update object.h to point to commit-reach.c instead of commit.c also.

> diff --git a/commit-reach.h b/commit-reach.h
> new file mode 100644
> index 0..244f48c5f
> --- /dev/null
> +++ b/commit-reach.h
> @@ -0,0 +1,41 @@
> +#ifndef __COMMIT_REACH_H__
> +#define __COMMIT_REACH_H__
> +
> +#include "commit.h"
> +
> +struct commit_list *get_merge_bases_many(struct commit *one,
> +  int n,
> +  struct commit **twos);



Should the declarations in commit.h be deleted also?

Thanks for copying it over verbatim - it makes it much easier to see
what's going on with --color-moved.

Re: [PATCH 01/16] commit-reach: move walk methods from commit.c

2018-07-16 Thread Stefan Beller 
On Mon, Jul 16, 2018 at 6:00 AM Derrick Stolee via GitGitGadget
 wrote:
>
> From: Derrick Stolee 
>
> Signed-off-by: Derrick Stolee 

This looks good, apart from nits below.

Thanks,
Stefan

> diff --git a/commit-reach.c b/commit-reach.c
> new file mode 100644
> index 0..f2e2f7461
> --- /dev/null
> +++ b/commit-reach.c
> @@ -0,0 +1,359 @@
> +#include "cache.h"
> +#include "prio-queue.h"
> +#include "commit-reach.h"

and commit.h (see discussion below) ?

> diff --git a/commit-reach.h b/commit-reach.h
> new file mode 100644
> index 0..244f48c5f
> --- /dev/null
> +++ b/commit-reach.h
> @@ -0,0 +1,41 @@
> +#ifndef __COMMIT_REACH_H__
> +#define __COMMIT_REACH_H__
> +
> +#include "commit.h"

Do we really need to include the header file in another header file?
I'd think forward declarations would work fine here?
(The benefit of forward declaring the structs commits, commit_list
is purely for the poor saps of developers that we are, as then touching
commit.h would not trigger a compilation of files that only include this
header but not commit.h. That are not many in this particular case,
but I consider it good practice that we should follow)

> +
> +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);
> +
> +
> +/*
> + * 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.
> + */
> +struct commit_list *reduce_heads(struct commit_list *heads);
> +
> +/*
> + * 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);

Thanks for the docs! Bonus points for also documenting the
other functions (is_descendant_of etc. For example is
is_descendant_of destroying some bit state?)

> +#endif
> diff --git a/commit.c b/commit.c
> index 39b80bd21..32d1234bd 100644
> --- a/commit.c
> +++ b/commit.c
> @@ -843,364 +843,6 @@ void sort_in_topological_order(struct commit_list 
> **list, enum rev_sort_order so
> clear_author_date_slab(_date);
>  }
>
> -/* merge-base stuff */

This is the only line that did not make it to the other file. :-)
I don't think it is needed in commit-reach.c

[PATCH 01/16] commit-reach: move walk methods from commit.c

2018-07-16 Thread Derrick Stolee via GitGitGadget 
From: Derrick Stolee 

Signed-off-by: Derrick Stolee 
---
 Makefile   |   1 +
 commit-reach.c | 359 +
 commit-reach.h |  41 ++
 commit.c   | 358 
 4 files changed, 401 insertions(+), 358 deletions(-)
 create mode 100644 commit-reach.c
 create mode 100644 commit-reach.h

diff --git a/Makefile b/Makefile
index bb8bd6720..59781f4bc 100644
--- a/Makefile
+++ b/Makefile
@@ -829,6 +829,7 @@ LIB_OBJS += column.o
 LIB_OBJS += combine-diff.o
 LIB_OBJS += commit.o
 LIB_OBJS += commit-graph.o
+LIB_OBJS += commit-reach.o
 LIB_OBJS += compat/obstack.o
 LIB_OBJS += compat/terminal.o
 LIB_OBJS += config.o
diff --git a/commit-reach.c b/commit-reach.c
new file mode 100644
index 0..f2e2f7461
--- /dev/null
+++ b/commit-reach.c
@@ -0,0 +1,359 @@
+#include "cache.h"
+#include "prio-queue.h"
+#include "commit-reach.h"
+
+/* Remember to update object flag allocation in object.h */
+#define PARENT1(1u<<16)
+#define PARENT2(1u<<17)
+#define STALE  (1u<<18)
+#define RESULT (1u<<19)
+
+static const unsigned all_flags = (PARENT1 | PARENT2 | STALE | RESULT);
+
+static int queue_has_nonstale(struct prio_queue *queue)
+{
+   int i;
+   for (i = 0; i < queue->nr; i++) {
+   struct commit *commit = queue->array[i].data;
+   if (!(commit->object.flags & STALE))
+   return 1;
+   }
+   return 0;
+}
+
+/* all input commits in one and twos[] must have been parsed! */
+static struct commit_list *paint_down_to_common(struct commit *one, int n,
+   struct commit **twos,
+   int min_generation)
+{
+   struct prio_queue queue = { compare_commits_by_gen_then_commit_date };
+   struct commit_list *result = NULL;
+   int i;
+   uint32_t last_gen = GENERATION_NUMBER_INFINITY;
+
+   one->object.flags |= PARENT1;
+   if (!n) {
+   commit_list_append(one, );
+   return result;
+   }
+   prio_queue_put(, one);
+
+   for (i = 0; i < n; i++) {
+   twos[i]->object.flags |= PARENT2;
+   prio_queue_put(, twos[i]);
+   }
+
+   while (queue_has_nonstale()) {
+   struct commit *commit = prio_queue_get();
+   struct commit_list *parents;
+   int flags;
+
+   if (commit->generation > last_gen)
+   BUG("bad generation skip %8x > %8x at %s",
+   commit->generation, last_gen,
+   oid_to_hex(>object.oid));
+   last_gen = commit->generation;
+
+   if (commit->generation < min_generation)
+   break;
+
+   flags = commit->object.flags & (PARENT1 | PARENT2 | STALE);
+   if (flags == (PARENT1 | PARENT2)) {
+   if (!(commit->object.flags & RESULT)) {
+   commit->object.flags |= RESULT;
+   commit_list_insert_by_date(commit, );
+   }
+   /* Mark parents of a found merge stale */
+   flags |= STALE;
+   }
+   parents = commit->parents;
+   while (parents) {
+   struct commit *p = parents->item;
+   parents = parents->next;
+   if ((p->object.flags & flags) == flags)
+   continue;
+   if (parse_commit(p))
+   return NULL;
+   p->object.flags |= flags;
+   prio_queue_put(, p);
+   }
+   }
+
+   clear_prio_queue();
+   return result;
+}
+
+static struct commit_list *merge_bases_many(struct commit *one, int n, struct 
commit **twos)
+{
+   struct commit_list *list = NULL;
+   struct commit_list *result = NULL;
+   int i;
+
+   for (i = 0; i < n; i++) {
+   if (one == twos[i])
+   /*
+* We do not mark this even with RESULT so we do not
+* have to clean it up.
+*/
+   return commit_list_insert(one, );
+   }
+
+   if (parse_commit(one))
+   return NULL;
+   for (i = 0; i < n; i++) {
+   if (parse_commit(twos[i]))
+   return NULL;
+   }
+
+   list = paint_down_to_common(one, n, twos, 0);
+
+   while (list) {
+   struct commit *commit = pop_commit();
+   if (!(commit->object.flags & STALE))
+   commit_list_insert_by_date(commit, );
+   }
+   return result;
+}
+
+struct commit_list *get_octopus_merge_bases(struct commit_list *in)
+{
+   struct commit_list *i, *j, *k, *ret = NULL;
+
+