Merge branch 'jk/reflog-walk' into maint

Numerous bugs in walking of reflogs via "log -g" and friends have
been fixed.

* jk/reflog-walk:
  reflog-walk: apply --since/--until to reflog dates
  reflog-walk: stop using fake parents
  rev-list: check reflog_info before showing usage
  get_revision_1(): replace do-while with an early return
  log: do not free parents when walking reflog
  log: clarify comment about reflog cycles
  revision: disallow reflog walking with revs->limited
  t1414: document some reflog-walk oddities

8 files changed, 253 insertions, 123 deletions

diff --git a/builtin/log.c b/builtin/log.c
index c6362cf92e..5ffc380bd7 100644
--- a/builtin/log.c
+++ b/builtin/log.c
@@ -372,11 +372,14 @@ static int cmd_log_walk(struct rev_info *rev)
 			 */
 			rev->max_count++;
 		if (!rev->reflog_info) {
-			/* we allow cycles in reflog ancestry */
+			/*
+			 * We may show a given commit multiple times when
+			 * walking the reflogs.
+			 */
 			free_commit_buffer(commit);
+			free_commit_list(commit->parents);
+			commit->parents = NULL;
 		}
-		free_commit_list(commit->parents);
-		commit->parents = NULL;
 		if (saved_nrl < rev->diffopt.needed_rename_limit)
 			saved_nrl = rev->diffopt.needed_rename_limit;
 		if (rev->diffopt.degraded_cc_to_c)
diff --git a/builtin/rev-list.c b/builtin/rev-list.c
index fee10d8567..e8f5048903 100644
--- a/builtin/rev-list.c
+++ b/builtin/rev-list.c
@@ -11,6 +11,7 @@
 #include "graph.h"
 #include "bisect.h"
 #include "progress.h"
+#include "reflog-walk.h"
 
 static const char rev_list_usage[] =
 "git rev-list [OPTION] <commit-id>... [ -- paths... ]\n"
@@ -349,7 +350,7 @@ int cmd_rev_list(int argc, const char **argv, const char *prefix)
 		/* Only --header was specified */
 		revs.commit_format = CMIT_FMT_RAW;
 
-	if ((!revs.commits &&
+	if ((!revs.commits && reflog_walk_empty(revs.reflog_info) &&
 	     (!(revs.tag_objects || revs.tree_objects || revs.blob_objects) &&
 	      !revs.pending.nr)) ||
 	    revs.diff)
diff --git a/reflog-walk.c b/reflog-walk.c
index 081f89b70d..74ebe5148f 100644
--- a/reflog-walk.c
+++ b/reflog-walk.c
@@ -94,45 +94,6 @@ static int get_reflog_recno_by_time(struct complete_reflogs *array,
 	return -1;
 }
 
-struct commit_info_lifo {
-	struct commit_info {
-		struct commit *commit;
-		void *util;
-	} *items;
-	int nr, alloc;
-};
-
-static struct commit_info *get_commit_info(struct commit *commit,
-		struct commit_info_lifo *lifo, int pop)
-{
-	int i;
-	for (i = 0; i < lifo->nr; i++)
-		if (lifo->items[i].commit == commit) {
-			struct commit_info *result = &lifo->items[i];
-			if (pop) {
-				if (i + 1 < lifo->nr)
-					memmove(lifo->items + i,
-						lifo->items + i + 1,
-						(lifo->nr - i) *
-						sizeof(struct commit_info));
-				lifo->nr--;
-			}
-			return result;
-		}
-	return NULL;
-}
-
-static void add_commit_info(struct commit *commit, void *util,
-		struct commit_info_lifo *lifo)
-{
-	struct commit_info *info;
-	ALLOC_GROW(lifo->items, lifo->nr + 1, lifo->alloc);
-	info = lifo->items + lifo->nr;
-	info->commit = commit;
-	info->util = util;
-	lifo->nr++;
-}
-
 struct commit_reflog {
 	int recno;
 	enum selector_type {
@@ -144,7 +105,8 @@ struct commit_reflog {
 };
 
 struct reflog_walk_info {
-	struct commit_info_lifo reflogs;
+	struct commit_reflog **logs;
+	size_t nr, alloc;
 	struct string_list complete_reflogs;
 	struct commit_reflog *last_commit_reflog;
 };
@@ -233,52 +195,10 @@ int add_reflog_for_walk(struct reflog_walk_info *info,
 	commit_reflog->selector = selector;
 	commit_reflog->reflogs = reflogs;
 
-	add_commit_info(commit, commit_reflog, &info->reflogs);
-	return 0;
-}
+	ALLOC_GROW(info->logs, info->nr + 1, info->alloc);
+	info->logs[info->nr++] = commit_reflog;
 
-void fake_reflog_parent(struct reflog_walk_info *info, struct commit *commit)
-{
-	struct commit_info *commit_info =
-		get_commit_info(commit, &info->reflogs, 0);
-	struct commit_reflog *commit_reflog;
-	struct object *logobj;
-	struct reflog_info *reflog;
-
-	info->last_commit_reflog = NULL;
-	if (!commit_info)
-		return;
-
-	commit_reflog = commit_info->util;
-	if (commit_reflog->recno < 0) {
-		commit->parents = NULL;
-		return;
-	}
-	info->last_commit_reflog = commit_reflog;
-
-	do {
-		reflog = &commit_reflog->reflogs->items[commit_reflog->recno];
-		commit_reflog->recno--;
-		logobj = parse_object(&reflog->ooid);
-	} while (commit_reflog->recno && (logobj && logobj->type != OBJ_COMMIT));
-
-	if (!logobj && commit_reflog->recno >= 0 && is_null_oid(&reflog->ooid)) {
-		/* a root commit, but there are still more entries to show */
-		reflog = &commit_reflog->reflogs->items[commit_reflog->recno];
-		logobj = parse_object(&reflog->noid);
-		if (!logobj)
-			logobj = parse_object(&reflog->ooid);
-	}
-
-	if (!logobj || logobj->type != OBJ_COMMIT) {
-		commit_info->commit = NULL;
-		commit->parents = NULL;
-		return;
-	}
-	commit_info->commit = (struct commit *)logobj;
-
-	commit->parents = xcalloc(1, sizeof(struct commit_list));
-	commit->parents->item = commit_info->commit;
+	return 0;
 }
 
 void get_reflog_selector(struct strbuf *sb,
@@ -344,6 +264,18 @@ const char *get_reflog_ident(struct reflog_walk_info *reflog_info)
 	return info->email;
 }
 
+timestamp_t get_reflog_timestamp(struct reflog_walk_info *reflog_info)
+{
+	struct commit_reflog *commit_reflog = reflog_info->last_commit_reflog;
+	struct reflog_info *info;
+
+	if (!commit_reflog)
+		return 0;
+
+	info = &commit_reflog->reflogs->items[commit_reflog->recno+1];
+	return info->timestamp;
+}
+
 void show_reflog_message(struct reflog_walk_info *reflog_info, int oneline,
 			 const struct date_mode *dmode, int force_date)
 {
@@ -365,3 +297,53 @@ void show_reflog_message(struct reflog_walk_info *reflog_info, int oneline,
 		strbuf_release(&selector);
 	}
 }
+
+int reflog_walk_empty(struct reflog_walk_info *info)
+{
+	return !info || !info->nr;
+}
+
+static struct commit *next_reflog_commit(struct commit_reflog *log)
+{
+	for (; log->recno >= 0; log->recno--) {
+		struct reflog_info *entry = &log->reflogs->items[log->recno];
+		struct object *obj = parse_object(&entry->noid);
+
+		if (obj && obj->type == OBJ_COMMIT)
+			return (struct commit *)obj;
+	}
+	return NULL;
+}
+
+static timestamp_t log_timestamp(struct commit_reflog *log)
+{
+	return log->reflogs->items[log->recno].timestamp;
+}
+
+struct commit *next_reflog_entry(struct reflog_walk_info *walk)
+{
+	struct commit_reflog *best = NULL;
+	struct commit *best_commit = NULL;
+	size_t i;
+
+	for (i = 0; i < walk->nr; i++) {
+		struct commit_reflog *log = walk->logs[i];
+		struct commit *commit = next_reflog_commit(log);
+
+		if (!commit)
+			continue;
+
+		if (!best || log_timestamp(log) > log_timestamp(best)) {
+			best = log;
+			best_commit = commit;
+		}
+	}
+
+	if (best) {
+		best->recno--;
+		walk->last_commit_reflog = best;
+		return best_commit;
+	}
+
+	return NULL;
+}
diff --git a/reflog-walk.h b/reflog-walk.h
index 27886f793e..7553c448fe 100644
--- a/reflog-walk.h
+++ b/reflog-walk.h
@@ -8,16 +8,19 @@ struct reflog_walk_info;
 extern void init_reflog_walk(struct reflog_walk_info **info);
 extern int add_reflog_for_walk(struct reflog_walk_info *info,
 		struct commit *commit, const char *name);
-extern void fake_reflog_parent(struct reflog_walk_info *info,
-		struct commit *commit);
 extern void show_reflog_message(struct reflog_walk_info *info, int,
 				const struct date_mode *, int force_date);
 extern void get_reflog_message(struct strbuf *sb,
 		struct reflog_walk_info *reflog_info);
 extern const char *get_reflog_ident(struct reflog_walk_info *reflog_info);
+extern timestamp_t get_reflog_timestamp(struct reflog_walk_info *reflog_info);
 extern void get_reflog_selector(struct strbuf *sb,
 		struct reflog_walk_info *reflog_info,
 		const struct date_mode *dmode, int force_date,
 		int shorten);
 
+extern int reflog_walk_empty(struct reflog_walk_info *walk);
+
+struct commit *next_reflog_entry(struct reflog_walk_info *reflog_info);
+
 #endif
diff --git a/revision.c b/revision.c
index 6603af9444..2631b013a5 100644
--- a/revision.c
+++ b/revision.c
@@ -148,16 +148,14 @@ static void add_pending_object_with_path(struct rev_info *revs,
 	if (revs->reflog_info && obj->type == OBJ_COMMIT) {
 		struct strbuf buf = STRBUF_INIT;
 		int len = interpret_branch_name(name, 0, &buf, 0);
-		int st;
 
 		if (0 < len && name[len] && buf.len)
 			strbuf_addstr(&buf, name + len);
-		st = add_reflog_for_walk(revs->reflog_info,
-					 (struct commit *)obj,
-					 buf.buf[0] ? buf.buf: name);
+		add_reflog_for_walk(revs->reflog_info,
+				    (struct commit *)obj,
+				    buf.buf[0] ? buf.buf: name);
 		strbuf_release(&buf);
-		if (st)
-			return;
+		return; /* do not add the commit itself */
 	}
 	add_object_array_with_path(obj, name, &revs->pending, mode, path);
 }
@@ -2364,6 +2362,8 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct s
 
 	if (revs->reverse && revs->reflog_info)
 		die("cannot combine --reverse with --walk-reflogs");
+	if (revs->reflog_info && revs->limited)
+		die("cannot combine --walk-reflogs with history-limiting options");
 	if (revs->rewrite_parents && revs->children.name)
 		die("cannot combine --parents and --children");
 
@@ -2963,6 +2963,18 @@ static inline int want_ancestry(const struct rev_info *revs)
 	return (revs->rewrite_parents || revs->children.name);
 }
 
+/*
+ * Return a timestamp to be used for --since/--until comparisons for this
+ * commit, based on the revision options.
+ */
+static timestamp_t comparison_date(const struct rev_info *revs,
+				   struct commit *commit)
+{
+	return revs->reflog_info ?
+		get_reflog_timestamp(revs->reflog_info) :
+		commit->date;
+}
+
 enum commit_action get_commit_action(struct rev_info *revs, struct commit *commit)
 {
 	if (commit->object.flags & SHOWN)
@@ -2973,8 +2985,9 @@ enum commit_action get_commit_action(struct rev_info *revs, struct commit *commi
 		return commit_show;
 	if (commit->object.flags & UNINTERESTING)
 		return commit_ignore;
-	if (revs->min_age != -1 && (commit->date > revs->min_age))
-		return commit_ignore;
+	if (revs->min_age != -1 &&
+	    comparison_date(revs, commit) > revs->min_age)
+			return commit_ignore;
 	if (revs->min_parents || (revs->max_parents >= 0)) {
 		int n = commit_list_count(commit->parents);
 		if ((n < revs->min_parents) ||
@@ -3107,17 +3120,19 @@ static void track_linear(struct rev_info *revs, struct commit *commit)
 
 static struct commit *get_revision_1(struct rev_info *revs)
 {
-	if (!revs->commits)
-		return NULL;
+	while (1) {
+		struct commit *commit;
 
-	do {
-		struct commit *commit = pop_commit(&revs->commits);
+		if (revs->reflog_info)
+			commit = next_reflog_entry(revs->reflog_info);
+		else
+			commit = pop_commit(&revs->commits);
 
-		if (revs->reflog_info) {
-			save_parents(revs, commit);
-			fake_reflog_parent(revs->reflog_info, commit);
+		if (!commit)
+			return NULL;
+
+		if (revs->reflog_info)
 			commit->object.flags &= ~(ADDED | SEEN | SHOWN);
-		}
 
 		/*
 		 * If we haven't done the list limiting, we need to look at
@@ -3126,9 +3141,12 @@ static struct commit *get_revision_1(struct rev_info *revs)
 		 */
 		if (!revs->limited) {
 			if (revs->max_age != -1 &&
-			    (commit->date < revs->max_age))
+			    comparison_date(revs, commit) < revs->max_age)
 				continue;
-			if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
+
+			if (revs->reflog_info)
+				try_to_simplify_commit(revs, commit);
+			else if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
 				if (!revs->ignore_missing_links)
 					die("Failed to traverse parents of commit %s",
 						oid_to_hex(&commit->object.oid));
@@ -3146,8 +3164,7 @@ static struct commit *get_revision_1(struct rev_info *revs)
 				track_linear(revs, commit);
 			return commit;
 		}
-	} while (revs->commits);
-	return NULL;
+	}
 }
 
 /*
diff --git a/t/t1411-reflog-show.sh b/t/t1411-reflog-show.sh
index b9cb76654b..6ac7734d79 100755
--- a/t/t1411-reflog-show.sh
+++ b/t/t1411-reflog-show.sh
@@ -171,14 +171,4 @@ test_expect_success 'reflog exists works' '
 	! git reflog exists refs/heads/nonexistent
 '
 
-# The behavior with two reflogs is buggy and the output is in flux; for now
-# we're just checking that the program works at all without segfaulting.
-test_expect_success 'showing multiple reflogs works' '
-	git log -g HEAD HEAD >actual
-'
-
-test_expect_success 'showing multiple reflogs with an old date' '
-	git log -g HEAD@{1979-01-01} HEAD >actual
-'
-
 test_done
diff --git a/t/t1414-reflog-walk.sh b/t/t1414-reflog-walk.sh
new file mode 100755
index 0000000000..feb1efd8ff
--- /dev/null
+++ b/t/t1414-reflog-walk.sh
@@ -0,0 +1,135 @@
+#!/bin/sh
+
+test_description='various tests of reflog walk (log -g) behavior'
+. ./test-lib.sh
+
+test_expect_success 'set up some reflog entries' '
+	test_commit one &&
+	test_commit two &&
+	git checkout -b side HEAD^ &&
+	test_commit three &&
+	git merge --no-commit master &&
+	echo evil-merge-content >>one.t &&
+	test_tick &&
+	git commit --no-edit -a
+'
+
+do_walk () {
+	git log -g --format="%gd %gs" "$@"
+}
+
+sq="'"
+test_expect_success 'set up expected reflog' '
+	cat >expect.all <<-EOF
+	HEAD@{0} commit (merge): Merge branch ${sq}master${sq} into side
+	HEAD@{1} commit: three
+	HEAD@{2} checkout: moving from master to side
+	HEAD@{3} commit: two
+	HEAD@{4} commit (initial): one
+	EOF
+'
+
+test_expect_success 'reflog walk shows expected logs' '
+	do_walk >actual &&
+	test_cmp expect.all actual
+'
+
+test_expect_success 'reflog can limit with --no-merges' '
+	grep -v merge expect.all >expect &&
+	do_walk --no-merges >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'reflog can limit with pathspecs' '
+	grep two expect.all >expect &&
+	do_walk -- two.t >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'pathspec limiting handles merges' '
+	# we pick up:
+	#   - the initial commit of one
+	#   - the checkout back to commit one
+	#   - the evil merge which touched one
+	sed -n "1p;3p;5p" expect.all >expect &&
+	do_walk -- one.t >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success '--parents shows true parents' '
+	# convert newlines to spaces
+	echo $(git rev-parse HEAD HEAD^1 HEAD^2) >expect &&
+	git rev-list -g --parents -1 HEAD >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'walking multiple reflogs shows all' '
+	# We expect to see all entries for all reflogs, but interleaved by
+	# date, with order on the command line breaking ties. We
+	# can use "sort" on the separate lists to generate this,
+	# but note two tricks:
+	#
+	#   1. We use "{" as the delimiter, which lets us skip to the reflog
+	#      date specifier as our second field, and then our "-n" numeric
+	#      sort ignores the bits after the timestamp.
+	#
+	#   2. POSIX leaves undefined whether this is a stable sort or not. So
+	#      we use "-k 1" to ensure that we see HEAD before master before
+	#      side when breaking ties.
+	{
+		do_walk --date=unix HEAD &&
+		do_walk --date=unix side &&
+		do_walk --date=unix master
+	} >expect.raw &&
+	sort -t "{" -k 2nr -k 1 <expect.raw >expect &&
+	do_walk --date=unix HEAD master side >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'date-limiting does not interfere with other logs' '
+	do_walk HEAD@{1979-01-01} HEAD >actual &&
+	test_cmp expect.all actual
+'
+
+test_expect_success 'min/max age uses entry date to limit' '
+	# Flip between commits one and two so each ref update actually
+	# does something (and does not get optimized out). We know
+	# that the timestamps of those commits will be before our "min".
+
+	git update-ref -m before refs/heads/minmax one &&
+
+	test_tick &&
+	min=$test_tick &&
+	git update-ref -m min refs/heads/minmax two &&
+
+	test_tick &&
+	max=$test_tick &&
+	git update-ref -m max refs/heads/minmax one &&
+
+	test_tick &&
+	git update-ref -m after refs/heads/minmax two &&
+
+	cat >expect <<-\EOF &&
+	max
+	min
+	EOF
+	git log -g --since=$min --until=$max --format=%gs minmax >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'walk prefers reflog to ref tip' '
+	head=$(git rev-parse HEAD) &&
+	one=$(git rev-parse one) &&
+	ident="$GIT_COMMITTER_NAME <$GIT_COMMITTER_EMAIL> $GIT_COMMITTER_DATE" &&
+	echo "$head $one $ident	broken reflog entry" >>.git/logs/HEAD &&
+
+	echo $one >expect &&
+	git log -g --format=%H -1 >actual &&
+	test_cmp expect actual
+'
+
+test_expect_success 'rev-list -g complains when there are no reflogs' '
+	test_must_fail git rev-list -g
+'
+
+test_done
diff --git a/t/t3200-branch.sh b/t/t3200-branch.sh
index dd37ac47c5..9d707d2a40 100755
--- a/t/t3200-branch.sh
+++ b/t/t3200-branch.sh
@@ -166,10 +166,9 @@ test_expect_success 'resulting reflog can be shown by log -g' '
 	oid=$(git rev-parse HEAD) &&
 	cat >expect <<-EOF &&
 	HEAD@{0} $oid $msg
-	HEAD@{1} $oid $msg
 	HEAD@{2} $oid checkout: moving from foo to baz
 	EOF
-	git log -g --format="%gd %H %gs" -3 HEAD >actual &&
+	git log -g --format="%gd %H %gs" -2 HEAD >actual &&
 	test_cmp expect actual
 '