[PATCH 1/5] trailer: Implement a helper to reverse-map trailer xrefs

[Tejun Heo <tj@kernel.org>]

From: Tejun Heo <htejun@fb.com>

Some trailers refer to other commits.  Let's call them xrefs
(cross-references).  For example, a cherry pick trailer points to the
source commit.  It is sometimes useful to build a reverse map of these
xrefs - ie. source -> cherry-pick instead of cherry-pick -> source.

This patch implements trailer helpers to enable such reverse maps.

The helpers can process arbitrary trailers and once the xrefs are
recorded, the reverse-mapping can be iterated per source commit using
trailer_rev_xrefs_for_each().

Signed-off-by: Tejun Heo <htejun@fb.com>
---
 trailer.c | 105 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 trailer.h |  38 ++++++++++++++++++++
 2 files changed, 143 insertions(+)

diff --git a/trailer.c b/trailer.c
index 0796f326b..15744600b 100644
--- a/trailer.c
+++ b/trailer.c
@@ -2,6 +2,7 @@
 #include "config.h"
 #include "string-list.h"
 #include "run-command.h"
+#include "object-store.h"
 #include "commit.h"
 #include "tempfile.h"
 #include "trailer.h"
@@ -1170,3 +1171,107 @@ void format_trailers_from_commit(struct strbuf *out, const char *msg,
 	format_trailer_info(out, &info, opts);
 	trailer_info_release(&info);
 }
+
+implement_static_commit_slab(trailer_rxrefs_slab, struct object_array *);
+
+static struct object_array *get_trailer_rxrefs(
+			struct trailer_rev_xrefs *rxrefs, struct commit *commit)
+{
+	struct object_array **slot =
+		trailer_rxrefs_slab_peek(&rxrefs->slab, commit);
+
+	return slot ? *slot : NULL;
+}
+
+static struct object_array *get_create_trailer_rxrefs(
+			struct trailer_rev_xrefs *rxrefs, struct commit *commit)
+{
+	struct object_array **slot =
+		trailer_rxrefs_slab_at(&rxrefs->slab, commit);
+
+	if (*slot)
+		return *slot;
+
+	add_object_array(&commit->object, oid_to_hex(&commit->object.oid),
+			 &rxrefs->dst_commits);
+	*slot = xmalloc(sizeof(struct object_array));
+	**slot = (struct object_array)OBJECT_ARRAY_INIT;
+	return *slot;
+}
+
+void trailer_rev_xrefs_init(struct trailer_rev_xrefs *rxrefs,
+			    const char *trailer_prefix)
+{
+	rxrefs->trailer_prefix = xstrdup(trailer_prefix);
+	rxrefs->trailer_prefix_len = strlen(trailer_prefix);
+	init_trailer_rxrefs_slab(&rxrefs->slab);
+	rxrefs->dst_commits = (struct object_array)OBJECT_ARRAY_INIT;
+}
+
+/* record the reverse mapping of @commit's xref trailer */
+void trailer_rev_xrefs_record(struct trailer_rev_xrefs *rxrefs,
+			      struct commit *commit)
+{
+	struct process_trailer_options opts = PROCESS_TRAILER_OPTIONS_INIT;
+	enum object_type type;
+	unsigned long size;
+	void *buffer;
+	struct trailer_info info;
+	int i;
+
+	buffer = read_object_file(&commit->object.oid, &type, &size);
+	trailer_info_get(&info, buffer, &opts);
+
+	/* when nested, the last trailer describes the latest cherry-pick */
+	for (i = info.trailer_nr - 1; i >= 0; i--) {
+		char *line = info.trailers[i];
+
+		if (starts_with(line, rxrefs->trailer_prefix)) {
+			struct object_id dst_oid;
+			struct object *dst_object;
+			struct commit *dst_commit;
+			struct object_array *src_objs;
+			char cherry_hex[GIT_MAX_HEXSZ + 1];
+
+			if (get_oid_hex(line + rxrefs->trailer_prefix_len,
+					&dst_oid))
+				continue;
+
+			dst_object = parse_object(the_repository, &dst_oid);
+			if (!dst_object || dst_object->type != OBJ_COMMIT)
+				continue;
+
+			dst_commit = (struct commit *)dst_object;
+			src_objs = get_create_trailer_rxrefs(rxrefs, dst_commit);
+
+			oid_to_hex_r(cherry_hex, &commit->object.oid);
+			add_object_array(&commit->object, cherry_hex, src_objs);
+			break;
+		}
+	}
+
+	free(buffer);
+}
+
+void trailer_rev_xrefs_release(struct trailer_rev_xrefs *rxrefs)
+{
+	clear_trailer_rxrefs_slab(&rxrefs->slab);
+	object_array_clear(&rxrefs->dst_commits);
+	free(rxrefs->trailer_prefix);
+}
+
+void trailer_rev_xrefs_next(struct trailer_rev_xrefs *rxrefs, int *idx_p,
+			    struct commit **dst_commit_p,
+			    struct object_array **src_objs_p)
+{
+	if (*idx_p >= rxrefs->dst_commits.nr) {
+		*dst_commit_p = NULL;
+		*src_objs_p = NULL;
+		return;
+	}
+
+	*dst_commit_p = (struct commit *)
+		rxrefs->dst_commits.objects[*idx_p].item;
+	*src_objs_p = get_trailer_rxrefs(rxrefs, *dst_commit_p);
+	(*idx_p)++;
+}
diff --git a/trailer.h b/trailer.h
index b99773964..07090a11f 100644
--- a/trailer.h
+++ b/trailer.h
@@ -2,6 +2,8 @@
 #define TRAILER_H
 
 #include "list.h"
+#include "object.h"
+#include "commit-slab.h"
 
 struct strbuf;
 
@@ -99,4 +101,40 @@ void trailer_info_release(struct trailer_info *info);
 void format_trailers_from_commit(struct strbuf *out, const char *msg,
 				 const struct process_trailer_options *opts);
 
+/*
+ * Helpers to reverse trailers referencing to other commits.
+ *
+ * Some trailers, e.g. "(cherry picked from...)", references other commits.
+ * The following helpers can be used to reverse map those references.  See
+ * builtin/reverse-trailer-xrefs.c for a usage example.
+ */
+declare_commit_slab(trailer_rxrefs_slab, struct object_array *);
+
+struct trailer_rev_xrefs {
+	char *trailer_prefix;
+	int trailer_prefix_len;
+	struct trailer_rxrefs_slab slab;
+	struct object_array dst_commits;
+};
+
+void trailer_rev_xrefs_init(struct trailer_rev_xrefs *rxrefs,
+			    const char *trailer_prefix);
+void trailer_rev_xrefs_record(struct trailer_rev_xrefs *rxrefs,
+			      struct commit *commit);
+void trailer_rev_xrefs_release(struct trailer_rev_xrefs *rxrefs);
+
+void trailer_rev_xrefs_next(struct trailer_rev_xrefs *rxrefs,
+			    int *idx_p, struct commit **dst_commit_p,
+			    struct object_array **src_objs_p);
+
+/*
+ * Iterate the recorded reverse mappings - @dst_commit was pointed to by
+ * commits in @src_objs.
+ */
+#define trailer_rev_xrefs_for_each(rxrefs, idx, dst_commit, src_objs)		\
+	for ((idx) = 0,								\
+	     trailer_rev_xrefs_next(rxrefs, &(idx), &(dst_commit), &(src_objs));\
+	     (dst_commit);							\
+	     trailer_rev_xrefs_next(rxrefs, &(idx), &(dst_commit), &(src_objs)))
+
 #endif /* TRAILER_H */
-- 
2.17.1