merge(3p/git): Merge git subtree at v2.29.2 r/1890

This also bumps the stable nixpkgs to 20.09 as of 2020-11-21, because
there is some breakage in the git build related to the netrc
credentials helper which someone has taken care of in nixpkgs.

The stable channel is not used for anything other than git, so this
should be fine.

Change-Id: I3575a19dab09e1e9556cf8231d717de9890484fb

1 files changed, 205 insertions, 86 deletions

diff --git a/third_party/git/builtin/name-rev.c b/third_party/git/builtin/name-rev.c
index c785fe16bade..725dd0451913 100644
--- a/third_party/git/builtin/name-rev.c
+++ b/third_party/git/builtin/name-rev.c
@@ -6,20 +6,25 @@
 #include "tag.h"
 #include "refs.h"
 #include "parse-options.h"
+#include "prio-queue.h"
 #include "sha1-lookup.h"
 #include "commit-slab.h"
 
-#define CUTOFF_DATE_SLOP 86400 /* one day */
+/*
+ * One day.  See the 'name a rev shortly after epoch' test in t6120 when
+ * changing this value
+ */
+#define CUTOFF_DATE_SLOP 86400
 
-typedef struct rev_name {
-	const char *tip_name;
+struct rev_name {
+	char *tip_name;
 	timestamp_t taggerdate;
 	int generation;
 	int distance;
 	int from_tag;
-} rev_name;
+};
 
-define_commit_slab(commit_rev_name, struct rev_name *);
+define_commit_slab(commit_rev_name, struct rev_name);
 
 static timestamp_t cutoff = TIME_MAX;
 static struct commit_rev_name rev_names;
@@ -27,16 +32,16 @@ static struct commit_rev_name rev_names;
 /* How many generations are maximally preferred over _one_ merge traversal? */
 #define MERGE_TRAVERSAL_WEIGHT 65535
 
-static struct rev_name *get_commit_rev_name(struct commit *commit)
+static int is_valid_rev_name(const struct rev_name *name)
 {
-	struct rev_name **slot = commit_rev_name_peek(&rev_names, commit);
-
-	return slot ? *slot : NULL;
+	return name && (name->generation || name->tip_name);
 }
 
-static void set_commit_rev_name(struct commit *commit, struct rev_name *name)
+static struct rev_name *get_commit_rev_name(const struct commit *commit)
 {
-	*commit_rev_name_at(&rev_names, commit) = name;
+	struct rev_name *name = commit_rev_name_peek(&rev_names, commit);
+
+	return is_valid_rev_name(name) ? name : NULL;
 }
 
 static int is_better_name(struct rev_name *name,
@@ -75,68 +80,135 @@ static int is_better_name(struct rev_name *name,
 	return 0;
 }
 
-static void name_rev(struct commit *commit,
-		const char *tip_name, timestamp_t taggerdate,
-		int generation, int distance, int from_tag,
-		int deref)
+static struct rev_name *create_or_update_name(struct commit *commit,
+					      timestamp_t taggerdate,
+					      int generation, int distance,
+					      int from_tag)
 {
-	struct rev_name *name = get_commit_rev_name(commit);
-	struct commit_list *parents;
-	int parent_number = 1;
-	char *to_free = NULL;
-
-	parse_commit(commit);
+	struct rev_name *name = commit_rev_name_at(&rev_names, commit);
+
+	if (is_valid_rev_name(name)) {
+		if (!is_better_name(name, taggerdate, distance, from_tag))
+			return NULL;
+
+		/*
+		 * This string might still be shared with ancestors
+		 * (generation > 0).  We can release it here regardless,
+		 * because the new name that has just won will be better
+		 * for them as well, so name_rev() will replace these
+		 * stale pointers when it processes the parents.
+		 */
+		if (!name->generation)
+			free(name->tip_name);
+	}
 
-	if (commit->date < cutoff)
-		return;
+	name->taggerdate = taggerdate;
+	name->generation = generation;
+	name->distance = distance;
+	name->from_tag = from_tag;
 
-	if (deref) {
-		tip_name = to_free = xstrfmt("%s^0", tip_name);
+	return name;
+}
 
-		if (generation)
-			die("generation: %d, but deref?", generation);
+static char *get_parent_name(const struct rev_name *name, int parent_number)
+{
+	struct strbuf sb = STRBUF_INIT;
+	size_t len;
+
+	strip_suffix(name->tip_name, "^0", &len);
+	if (name->generation > 0) {
+		strbuf_grow(&sb, len +
+			    1 + decimal_width(name->generation) +
+			    1 + decimal_width(parent_number));
+		strbuf_addf(&sb, "%.*s~%d^%d", (int)len, name->tip_name,
+			    name->generation, parent_number);
+	} else {
+		strbuf_grow(&sb, len +
+			    1 + decimal_width(parent_number));
+		strbuf_addf(&sb, "%.*s^%d", (int)len, name->tip_name,
+			    parent_number);
 	}
+	return strbuf_detach(&sb, NULL);
+}
 
-	if (name == NULL) {
-		name = xmalloc(sizeof(rev_name));
-		set_commit_rev_name(commit, name);
-		goto copy_data;
-	} else if (is_better_name(name, taggerdate, distance, from_tag)) {
-copy_data:
-		name->tip_name = tip_name;
-		name->taggerdate = taggerdate;
-		name->generation = generation;
-		name->distance = distance;
-		name->from_tag = from_tag;
-	} else {
-		free(to_free);
+static void name_rev(struct commit *start_commit,
+		const char *tip_name, timestamp_t taggerdate,
+		int from_tag, int deref)
+{
+	struct prio_queue queue;
+	struct commit *commit;
+	struct commit **parents_to_queue = NULL;
+	size_t parents_to_queue_nr, parents_to_queue_alloc = 0;
+	struct rev_name *start_name;
+
+	parse_commit(start_commit);
+	if (start_commit->date < cutoff)
 		return;
-	}
 
-	for (parents = commit->parents;
-			parents;
-			parents = parents->next, parent_number++) {
-		if (parent_number > 1) {
-			size_t len;
-			char *new_name;
-
-			strip_suffix(tip_name, "^0", &len);
-			if (generation > 0)
-				new_name = xstrfmt("%.*s~%d^%d", (int)len, tip_name,
-						   generation, parent_number);
-			else
-				new_name = xstrfmt("%.*s^%d", (int)len, tip_name,
-						   parent_number);
-
-			name_rev(parents->item, new_name, taggerdate, 0,
-				 distance + MERGE_TRAVERSAL_WEIGHT,
-				 from_tag, 0);
-		} else {
-			name_rev(parents->item, tip_name, taggerdate,
-				 generation + 1, distance + 1,
-				 from_tag, 0);
+	start_name = create_or_update_name(start_commit, taggerdate, 0, 0,
+					   from_tag);
+	if (!start_name)
+		return;
+	if (deref)
+		start_name->tip_name = xstrfmt("%s^0", tip_name);
+	else
+		start_name->tip_name = xstrdup(tip_name);
+
+	memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */
+	prio_queue_put(&queue, start_commit);
+
+	while ((commit = prio_queue_get(&queue))) {
+		struct rev_name *name = get_commit_rev_name(commit);
+		struct commit_list *parents;
+		int parent_number = 1;
+
+		parents_to_queue_nr = 0;
+
+		for (parents = commit->parents;
+				parents;
+				parents = parents->next, parent_number++) {
+			struct commit *parent = parents->item;
+			struct rev_name *parent_name;
+			int generation, distance;
+
+			parse_commit(parent);
+			if (parent->date < cutoff)
+				continue;
+
+			if (parent_number > 1) {
+				generation = 0;
+				distance = name->distance + MERGE_TRAVERSAL_WEIGHT;
+			} else {
+				generation = name->generation + 1;
+				distance = name->distance + 1;
+			}
+
+			parent_name = create_or_update_name(parent, taggerdate,
+							    generation,
+							    distance, from_tag);
+			if (parent_name) {
+				if (parent_number > 1)
+					parent_name->tip_name =
+						get_parent_name(name,
+								parent_number);
+				else
+					parent_name->tip_name = name->tip_name;
+				ALLOC_GROW(parents_to_queue,
+					   parents_to_queue_nr + 1,
+					   parents_to_queue_alloc);
+				parents_to_queue[parents_to_queue_nr] = parent;
+				parents_to_queue_nr++;
+			}
 		}
+
+		/* The first parent must come out first from the prio_queue */
+		while (parents_to_queue_nr)
+			prio_queue_put(&queue,
+				       parents_to_queue[--parents_to_queue_nr]);
 	}
+
+	clear_prio_queue(&queue);
+	free(parents_to_queue);
 }
 
 static int subpath_matches(const char *path, const char *filter)
@@ -157,10 +229,10 @@ static const char *name_ref_abbrev(const char *refname, int shorten_unambiguous)
 {
 	if (shorten_unambiguous)
 		refname = shorten_unambiguous_ref(refname, 0);
-	else if (starts_with(refname, "refs/heads/"))
-		refname = refname + 11;
-	else if (starts_with(refname, "refs/"))
-		refname = refname + 5;
+	else if (skip_prefix(refname, "refs/heads/", &refname))
+		; /* refname already advanced */
+	else
+		skip_prefix(refname, "refs/", &refname);
 	return refname;
 }
 
@@ -175,6 +247,10 @@ static struct tip_table {
 	struct tip_table_entry {
 		struct object_id oid;
 		const char *refname;
+		struct commit *commit;
+		timestamp_t taggerdate;
+		unsigned int from_tag:1;
+		unsigned int deref:1;
 	} *table;
 	int nr;
 	int alloc;
@@ -182,13 +258,18 @@ static struct tip_table {
 } tip_table;
 
 static void add_to_tip_table(const struct object_id *oid, const char *refname,
-			     int shorten_unambiguous)
+			     int shorten_unambiguous, struct commit *commit,
+			     timestamp_t taggerdate, int from_tag, int deref)
 {
 	refname = name_ref_abbrev(refname, shorten_unambiguous);
 
 	ALLOC_GROW(tip_table.table, tip_table.nr + 1, tip_table.alloc);
 	oidcpy(&tip_table.table[tip_table.nr].oid, oid);
 	tip_table.table[tip_table.nr].refname = xstrdup(refname);
+	tip_table.table[tip_table.nr].commit = commit;
+	tip_table.table[tip_table.nr].taggerdate = taggerdate;
+	tip_table.table[tip_table.nr].from_tag = from_tag;
+	tip_table.table[tip_table.nr].deref = deref;
 	tip_table.nr++;
 	tip_table.sorted = 0;
 }
@@ -199,12 +280,30 @@ static int tipcmp(const void *a_, const void *b_)
 	return oidcmp(&a->oid, &b->oid);
 }
 
+static int cmp_by_tag_and_age(const void *a_, const void *b_)
+{
+	const struct tip_table_entry *a = a_, *b = b_;
+	int cmp;
+
+	/* Prefer tags. */
+	cmp = b->from_tag - a->from_tag;
+	if (cmp)
+		return cmp;
+
+	/* Older is better. */
+	if (a->taggerdate < b->taggerdate)
+		return -1;
+	return a->taggerdate != b->taggerdate;
+}
+
 static int name_ref(const char *path, const struct object_id *oid, int flags, void *cb_data)
 {
 	struct object *o = parse_object(the_repository, oid);
 	struct name_ref_data *data = cb_data;
 	int can_abbreviate_output = data->tags_only && data->name_only;
 	int deref = 0;
+	int from_tag = 0;
+	struct commit *commit = NULL;
 	timestamp_t taggerdate = TIME_MAX;
 
 	if (data->tags_only && !starts_with(path, "refs/tags/"))
@@ -253,8 +352,6 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
 			return 0;
 	}
 
-	add_to_tip_table(oid, path, can_abbreviate_output);
-
 	while (o && o->type == OBJ_TAG) {
 		struct tag *t = (struct tag *) o;
 		if (!t->tagged)
@@ -264,18 +361,35 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
 		taggerdate = t->date;
 	}
 	if (o && o->type == OBJ_COMMIT) {
-		struct commit *commit = (struct commit *)o;
-		int from_tag = starts_with(path, "refs/tags/");
-
+		commit = (struct commit *)o;
+		from_tag = starts_with(path, "refs/tags/");
 		if (taggerdate == TIME_MAX)
-			taggerdate = ((struct commit *)o)->date;
-		path = name_ref_abbrev(path, can_abbreviate_output);
-		name_rev(commit, xstrdup(path), taggerdate, 0, 0,
-			 from_tag, deref);
+			taggerdate = commit->date;
 	}
+
+	add_to_tip_table(oid, path, can_abbreviate_output, commit, taggerdate,
+			 from_tag, deref);
 	return 0;
 }
 
+static void name_tips(void)
+{
+	int i;
+
+	/*
+	 * Try to set better names first, so that worse ones spread
+	 * less.
+	 */
+	QSORT(tip_table.table, tip_table.nr, cmp_by_tag_and_age);
+	for (i = 0; i < tip_table.nr; i++) {
+		struct tip_table_entry *e = &tip_table.table[i];
+		if (e->commit) {
+			name_rev(e->commit, e->refname, e->taggerdate,
+				 e->from_tag, e->deref);
+		}
+	}
+}
+
 static const unsigned char *nth_tip_table_ent(size_t ix, void *table_)
 {
 	struct tip_table_entry *table = table_;
@@ -305,11 +419,11 @@ static const char *get_exact_ref_match(const struct object *o)
 static const char *get_rev_name(const struct object *o, struct strbuf *buf)
 {
 	struct rev_name *n;
-	struct commit *c;
+	const struct commit *c;
 
 	if (o->type != OBJ_COMMIT)
 		return get_exact_ref_match(o);
-	c = (struct commit *) o;
+	c = (const struct commit *) o;
 	n = get_commit_rev_name(c);
 	if (!n)
 		return NULL;
@@ -317,11 +431,10 @@ static const char *get_rev_name(const struct object *o, struct strbuf *buf)
 	if (!n->generation)
 		return n->tip_name;
 	else {
-		int len = strlen(n->tip_name);
-		if (len > 2 && !strcmp(n->tip_name + len - 2, "^0"))
-			len -= 2;
 		strbuf_reset(buf);
-		strbuf_addf(buf, "%.*s~%d", len, n->tip_name, n->generation);
+		strbuf_addstr(buf, n->tip_name);
+		strbuf_strip_suffix(buf, "^0");
+		strbuf_addf(buf, "~%d", n->generation);
 		return buf->buf;
 	}
 }
@@ -408,7 +521,7 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 	int all = 0, transform_stdin = 0, allow_undefined = 1, always = 0, peel_tag = 0;
 	struct name_ref_data data = { 0, 0, STRING_LIST_INIT_NODUP, STRING_LIST_INIT_NODUP };
 	struct option opts[] = {
-		OPT_BOOL(0, "name-only", &data.name_only, N_("print only names (no SHA-1)")),
+		OPT_BOOL(0, "name-only", &data.name_only, N_("print only ref-based names (no object names)")),
 		OPT_BOOL(0, "tags", &data.tags_only, N_("only use tags to name the commits")),
 		OPT_STRING_LIST(0, "refs", &data.ref_filters, N_("pattern"),
 				   N_("only use refs matching <pattern>")),
@@ -481,9 +594,15 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
 		add_object_array(object, *argv, &revs);
 	}
 
-	if (cutoff)
-		cutoff = cutoff - CUTOFF_DATE_SLOP;
+	if (cutoff) {
+		/* check for undeflow */
+		if (cutoff > TIME_MIN + CUTOFF_DATE_SLOP)
+			cutoff = cutoff - CUTOFF_DATE_SLOP;
+		else
+			cutoff = TIME_MIN;
+	}
 	for_each_ref(name_ref, &data);
+	name_tips();
 
 	if (transform_stdin) {
 		char buffer[2048];