git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH 6/6] reflog-walk: stop using fake parents

From
Jeff King <peff@peff.net>
Date
Jul 5, 2017, 08:09 UTC
Message-ID
<20170705080904.idlpm6ecslzfbm75@sigill.intra.peff.net>
In-Reply-To
<20170705075508.c5ul23vivzpklpy6@sigill.intra.peff.net>

The reflog-walk system works by putting a ref's tip into the pending queue, and then "traversing" the reflog by pretending that the parent of each commit is the previous reflog entry.

This causes a number of user-visible oddities, as documented in t1414 (and the commit message which introduced it). We can fix all of them in one go by replacing the fake-reflog system with a much simpler one: just keeping a list of reflogs to show, and walking through them entry by entry.

The implementation is fairly straight-forward, but there are a few items to note:

  1. We obviously must skip calling add_parents_to_list()
     when we are traversing reflogs, since we do not want to
     walk the original parents at all.
     As a result, we must call try_to_simplify_commit()
     ourselves and skip any TREESAME commits.
     There are other parts of add_parents_to_list() we skip,
     as well, but none of them should matter for a reflog
     traversal:
       -  We do not allow UNINTERESTING commits, nor
          symmetric ranges (and we bail when these are used
          with "-g").
       - Using --source makes no sense, since we aren't
         traversing. The reflog selector shows the same
         information with more detail.
       - Using --first-parent is still sensible, since you
         may want to see the first-parent diff for each
         entry. But since we're not traversing, we don't
         need to cull the parent list here.
  2. Since we now just walk the reflog entries themselves,
     rather than starting with the ref tip, we now look at
     the "new" field of each entry rather than the "old"
     (i.e., we are showing entries, not faking parents).
     This removes all of the tricky logic around skipping
     past root commits.
     But note that we have no way to show an entry with the
     null sha1 in its "new" field (because such a commit
     obviously does not exist). Normally this would not
     happen, since we delete reflogs along with refs, but
     there is one special case. When we rename the currently
     checked out branch, we write two reflog entries into
     the HEAD log: one where the commit goes away, and
     another where it comes back.
     Prior to this commit, we show both entries with
     identical reflog messages. After this commit, we show
     only the "comes back" entry. See the update in t3200
     which demonstrates this.
     Arguably either is fine, as the whole double-entry
     thing is a bit hacky in the first place. And until a
     recent fix, we truncated the traversal in such a case
     anyway, which was _definitely_ wrong.
Signed-off-by: Jeff King <peff@peff.net>
---
 reflog-walk.c          | 116 +++++++++++++------------------------------------
 reflog-walk.h          |   4 +-
 revision.c             |  30 ++++++++-----
 t/t1414-reflog-walk.sh |  12 ++---
 t/t3200-branch.sh      |   3 +-
 5 files changed, 57 insertions(+), 108 deletions(-)
diff --git a/reflog-walk.c b/reflog-walk.c
index 89e719c459..a7644d944e 100644
--- a/reflog-walk.c
+++ b/reflog-walk.c
@@ -78,45 +78,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 {
@@ -128,7 +89,8 @@ struct commit_reflog {
 };
 
 struct reflog_walk_info {
-	struct commit_info_lifo reflogs;
+	struct commit_reflog **logs;
+	size_t nr, alloc, cur;
 	struct string_list complete_reflogs;
 	struct commit_reflog *last_commit_reflog;
 };
@@ -226,52 +188,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;
-}
-
-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;
+	ALLOC_GROW(info->logs, info->nr + 1, info->alloc);
+	info->logs[info->nr++] = commit_reflog;
 
-	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,
@@ -361,5 +281,29 @@ void show_reflog_message(struct reflog_walk_info *reflog_info, int oneline,
 
 int reflog_walk_empty(struct reflog_walk_info *info)
 {
-	return !info || !info->reflogs.nr;
+	return !info || !info->nr;
+}
+
+struct commit *next_entry_in_log(struct commit_reflog *log)
+{
+	while (log->recno >= 0) {
+		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;
+}
+
+struct commit *next_reflog_entry(struct reflog_walk_info *walk)
+{
+	for (; walk->cur < walk->nr; walk->cur++) {
+		struct commit *ret = next_entry_in_log(walk->logs[walk->cur]);
+		if (ret) {
+			walk->last_commit_reflog = walk->logs[walk->cur];
+			return ret;
+		}
+	}
+	return NULL;
 }
diff --git a/reflog-walk.h b/reflog-walk.h
index af32361072..373388cd14 100644
--- a/reflog-walk.h
+++ b/reflog-walk.h
@@ -8,8 +8,6 @@ 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,
@@ -22,4 +20,6 @@ extern void get_reflog_selector(struct strbuf *sb,
 
 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 4dc7c63654..5fc01f2d26 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);
 }
@@ -3110,16 +3108,18 @@ static void track_linear(struct rev_info *revs, struct commit *commit)
 static struct commit *get_revision_1(struct rev_info *revs)
 {
 	while (1) {
-		struct commit *commit = pop_commit(&revs->commits);
+		struct commit *commit;
+
+		if (revs->reflog_info)
+			commit = next_reflog_entry(revs->reflog_info);
+		else
+			commit = pop_commit(&revs->commits);
 
 		if (!commit)
 			return NULL;
 
-		if (revs->reflog_info) {
-			save_parents(revs, commit);
-			fake_reflog_parent(revs->reflog_info, commit);
+		if (revs->reflog_info)
 			commit->object.flags &= ~(ADDED | SEEN | SHOWN);
-		}
 
 		/*
 		 * If we haven't done the list limiting, we need to look at
@@ -3130,7 +3130,8 @@ static struct commit *get_revision_1(struct rev_info *revs)
 			if (revs->max_age != -1 &&
 			    (commit->date < revs->max_age))
 				continue;
-			if (add_parents_to_list(revs, commit, &revs->commits, NULL) < 0) {
+			if (!revs->reflog_info &&
+			    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,6 +3147,11 @@ static struct commit *get_revision_1(struct rev_info *revs)
 		default:
 			if (revs->track_linear)
 				track_linear(revs, commit);
+			if (revs->reflog_info) {
+				try_to_simplify_commit(revs, commit);
+				if (commit->object.flags & TREESAME)
+					continue;
+			}
 			return commit;
 		}
 	}
diff --git a/t/t1414-reflog-walk.sh b/t/t1414-reflog-walk.sh
index fba6788e94..7cc52d946d 100755
--- a/t/t1414-reflog-walk.sh
+++ b/t/t1414-reflog-walk.sh
@@ -34,32 +34,32 @@ test_expect_success 'reflog walk shows expected logs' '
 	test_cmp expect.all actual
 '
 
-test_expect_failure 'reflog can limit with --no-merges' '
+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_failure 'reflog can limit with pathspecs' '
+test_expect_success 'reflog can limit with pathspecs' '
 	grep two expect.all >expect &&
 	do_walk -- two.t >actual &&
 	test_cmp expect actual
 '
 
-test_expect_failure 'pathspec limiting handles merges' '
+test_expect_success 'pathspec limiting handles merges' '
 	sed -n "1p;3p;5p" expect.all >expect &&
 	do_walk -- one.t >actual &&
 	test_cmp expect actual
 '
 
-test_expect_failure '--parents shows true parents' '
+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_failure 'walking multiple reflogs shows both' '
+test_expect_success 'walking multiple reflogs shows both' '
 	{
 		do_walk HEAD &&
 		do_walk side
@@ -68,7 +68,7 @@ test_expect_failure 'walking multiple reflogs shows both' '
 	test_cmp expect actual
 '
 
-test_expect_failure 'walk prefers reflog to ref tip' '
+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" &&
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
 '
 

-- 
2.13.2.892.g25f9b59978
Previous: Jeff KingNext: Eric Wong
Message 40 of 69 in “Truncating HEAD reflog on branch move”
  1. brian m. carlsonJun 21, 2017
  2. Junio C HamanoJun 21, 2017
  3. Kyle MeyerJun 21, 2017
  4. Kyle MeyerJun 21, 2017
  5. Jeff KingJun 22, 2017
  6. Junio C HamanoJun 22, 2017
  7. Jeff KingJun 22, 2017
  8. Junio C HamanoJun 22, 2017
  9. Jeff KingJun 22, 2017
  10. Junio C HamanoJun 22, 2017
  11. Jeff KingJun 22, 2017
  12. Jeff KingJun 22, 2017
  13. Jeff KingJun 23, 2017
  14. brian m. carlsonJul 4, 2017
  15. Jeff KingJul 4, 2017
  16. brian m. carlsonJul 4, 2017
  17. Jeff KingJul 4, 2017
  18. Junio C HamanoJul 5, 2017
  19. 0/6 fixing reflog-walk odditiesJeff King, Jul 5, 2017
  20. 1/6 reflog-walk: skip over double-null oid due to HEAD renameJeff King, Jul 5, 2017
  21. Junio C HamanoJul 5, 2017
  22. Jeff KingJul 5, 2017
  23. 2/6 t1414: document some reflog-walk odditiesJeff King, Jul 5, 2017
  24. Junio C HamanoJul 5, 2017
  25. Jeff KingJul 5, 2017
  26. Junio C HamanoJul 5, 2017
  27. Jeff KingJul 6, 2017
  28. Jeff KingJul 6, 2017
  29. Junio C HamanoJul 6, 2017
  30. Jeff KingJul 7, 2017
  31. Junio C HamanoJul 7, 2017
  32. Jeff KingJul 7, 2017
  33. Ramsay JonesJul 5, 2017
  34. Jeff KingJul 5, 2017
  35. 3/6 log: do not free parents when walking reflogJeff King, Jul 5, 2017
  36. 4/6 get_revision_1(): replace do-while with an early returnJeff King, Jul 5, 2017
  37. 5/6 rev-list: check reflog_info before showing usageJeff King, Jul 5, 2017
  38. Junio C HamanoJul 5, 2017
  39. Jeff KingJul 5, 2017
  40. 6/6 reflog-walk: stop using fake parentsJeff King, Jul 5, 2017
  41. Eric WongJul 7, 2017
  42. Jeff KingJul 7, 2017
  43. Jeff KingJul 7, 2017
  44. Eric WongJul 10, 2017
  45. Jeff KingJul 10, 2017
  46. Junio C HamanoJul 10, 2017
  47. 0/4 reflog-walk fixes for maintJeff King, Jul 7, 2017
  48. 1/4 reflog-walk: skip over double-null oid due to HEAD renameJeff King, Jul 7, 2017
  49. 2/4 reflog-walk: duplicate strings in complete_reflogs listJeff King, Jul 7, 2017
  50. 3/4 reflog-walk: don't free reflogs added to cacheJeff King, Jul 7, 2017
  51. 4/4 reflog-walk: include all fields when freeing complete_reflogsJeff King, Jul 7, 2017
  52. 0/7 fixing reflog-walk odditiesJeff King, Jul 7, 2017
  53. 1/7 t1414: document some reflog-walk odditiesJeff King, Jul 7, 2017
  54. Jeff KingJul 7, 2017
  55. Kyle MeyerJul 7, 2017
  56. 2/7 revision: disallow reflog walking with revs->limitedJeff King, Jul 7, 2017
  57. 4/7 get_revision_1(): replace do-while with an early returnJeff King, Jul 7, 2017
  58. 5/7 rev-list: check reflog_info before showing usageJeff King, Jul 7, 2017
  59. 3/7 log: do not free parents when walking reflogJeff King, Jul 7, 2017
  60. Junio C HamanoJul 7, 2017
  61. Jeff KingJul 9, 2017
  62. Junio C HamanoJul 9, 2017
  63. Jeff KingJul 10, 2017
  64. 6/7 reflog-walk: stop using fake parentsJeff King, Jul 7, 2017
  65. Jeff KingJul 7, 2017
  66. Kyle MeyerJul 7, 2017
  67. Jeff KingJul 9, 2017
  68. 7/7 reflog-walk: apply --since/--until to reflog datesJeff King, Jul 7, 2017
  69. Junio C HamanoJul 7, 2017

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.