[PATCH 1/2] git-log --cherry-pick

[Junio C Hamano <junkio@cox.net>]

This is meant to be a saner replacement for "git-cherry".

When used with "A...B", this filters out commits whose patch
text has the same patch-id as a commit on the other side.

Signed-off-by: Junio C Hamano <junkio@cox.net>
---

  Junio C Hamano <junkio@cox.net> writes:

  > Funny.
  >
  > Last night I was thinking about git-cherry, as it is one of the
  > few commands that have "funny parameter semantics that do not
  > mesh well with git-log family" (others are format-patch and
  > rebase).
  >
  > I think we should be able to use --left-right and ... operator
  > to express what the above cherry does with something like:
  >
  >     $ git log --left-right --ignore-common-patch cvs-upstream...my-branch
  >
  > The --ignore-common-patch option does not exist yet, but the
  > basic code to implement it should already be accessible from the
  > log family, as that is what format-patch needs to do.

 revision.c |  141 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 revision.h |    1 +
 2 files changed, 142 insertions(+), 0 deletions(-)

diff --git a/revision.c b/revision.c
index 486393c..0903f19 100644
--- a/revision.c
+++ b/revision.c
@@ -422,6 +422,139 @@ static void add_parents_to_list(struct rev_info *revs, struct commit *commit, st
 	}
 }
 
+/*
+ * This needs to be moved from builtin-log -- its get_patch_ids() implementation
+ * is horrible -- it pollutes the object array with non objects!
+ */
+static int get_patch_id(struct commit *commit, struct diff_options *options,
+		unsigned char *sha1)
+{
+	if (commit->parents)
+		diff_tree_sha1(commit->parents->item->object.sha1,
+		               commit->object.sha1, "", options);
+	else
+		diff_root_tree_sha1(commit->object.sha1, "", options);
+	diffcore_std(options);
+	return diff_flush_patch_id(options, sha1);
+}
+
+struct patch_id_ent {
+	unsigned char patch_id[20];
+	char seen;
+};
+
+static int compare_patch_id(const void *a_, const void *b_)
+{
+	struct patch_id_ent *a = *((struct patch_id_ent **)a_);
+	struct patch_id_ent *b = *((struct patch_id_ent **)b_);
+	return hashcmp(a->patch_id, b->patch_id);
+}
+
+static void cherry_pick_list(struct commit_list *list)
+{
+	struct commit_list *p;
+	int left_count = 0, right_count = 0, nr;
+	struct patch_id_ent *patches, **table;
+	int left_first, table_size;
+	struct diff_options opts;
+
+	/* First count the commits on the left and on the right */
+	for (p = list; p; p = p->next) {
+		struct commit *commit = p->item;
+		unsigned flags = commit->object.flags;
+		if (flags & BOUNDARY)
+			;
+		else if (flags & SYMMETRIC_LEFT)
+			left_count++;
+		else
+			right_count++;
+	}
+
+	left_first = left_count < right_count;
+	table_size = left_first ? left_count : right_count;
+
+	/* Allocate a look-up table to help matching up */
+	patches = xcalloc(table_size, sizeof(struct patch_id_ent));
+	table = xcalloc(table_size, sizeof(struct patch_id_ent *));
+	nr = 0;
+
+	diff_setup(&opts);
+	opts.recursive = 1;
+	if (diff_setup_done(&opts) < 0)
+		die("diff_setup_done failed");
+
+	/* Compute patch-ids for one side */
+	for (p = list; p; p = p->next) {
+		struct commit *commit = p->item;
+		unsigned flags = commit->object.flags;
+
+		if (flags & BOUNDARY)
+			continue;
+		/*
+		 * If we have fewer left, left_first is set and we omit
+		 * commits on the right branch in this loop.  If we have
+		 * fewer right, we skip the left ones.
+		 */
+		if (left_first != !!(flags & SYMMETRIC_LEFT))
+			continue;
+		if (get_patch_id(commit, &opts, patches[nr].patch_id))
+			continue;
+		/*
+		 * FIXME: this does not really work if the side
+		 * we are dealing with have two commits with the same
+		 * patch id, as we end up having two entries in the
+		 * patch table.
+		 */
+		table[nr] = &(patches[nr]);
+		commit->util = table[nr];
+		nr++;
+	}
+	qsort(table, nr, sizeof(table[0]), compare_patch_id);
+
+	/* Check the other side */
+	for (p = list; p; p = p->next) {
+		struct commit *commit = p->item;
+		unsigned flags = commit->object.flags;
+		struct patch_id_ent ent, *entp = &ent, **found;
+
+		if (flags & BOUNDARY)
+			continue;
+		/*
+		 * If we have fewer left, left_first is set and we omit
+		 * commits on the left branch in this loop.
+		 */
+		if (left_first == !!(flags & SYMMETRIC_LEFT))
+			continue;
+		if (get_patch_id(commit, &opts, ent.patch_id))
+			continue;
+		/*
+		 * Have we seen the same patch id?
+		 */
+		found = bsearch(&entp, table, nr, sizeof(table[0]),
+				compare_patch_id);
+		if (!found)
+			continue;
+		(*found)->seen = 1;
+		commit->object.flags |= SHOWN; /* exclude this from the output set */
+	}
+
+	/* Now check the original side for seen ones */
+	for (p = list; p; p = p->next) {
+		struct commit *commit = p->item;
+		struct patch_id_ent *ent;
+
+		ent = commit->util;
+		if (!ent)
+			continue;
+		if (ent->seen)
+			commit->object.flags |= SHOWN;
+		commit->util = NULL;
+	}
+
+	free(table);
+	free(patches);
+}
+
 static void limit_list(struct rev_info *revs)
 {
 	struct commit_list *list = revs->commits;
@@ -449,6 +582,9 @@ static void limit_list(struct rev_info *revs)
 			continue;
 		p = &commit_list_insert(commit, p)->next;
 	}
+	if (revs->cherry_pick)
+		cherry_pick_list(newlist);
+
 	revs->commits = newlist;
 }
 
@@ -913,6 +1049,11 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch
 				revs->left_right = 1;
 				continue;
 			}
+			if (!strcmp(arg, "--cherry-pick")) {
+				revs->cherry_pick = 1;
+				revs->left_right = 1;
+				continue;
+			}
 			if (!strcmp(arg, "--objects")) {
 				revs->tag_objects = 1;
 				revs->tree_objects = 1;
diff --git a/revision.h b/revision.h
index 55e6b53..b69624a 100644
--- a/revision.h
+++ b/revision.h
@@ -47,6 +47,7 @@ struct rev_info {
 			left_right:1,
 			parents:1,
 			reverse:1,
+			cherry_pick:1,
 			first_parent_only:1;
 
 	/* Diff flags */