From 5173099aae25bedf7a87225891d124569cba7076 Mon Sep 17 00:00:00 2001
From: Jeff King <peff@peff.net>
Date: Thu, 9 Jan 2025 03:33:10 -0500
Subject: tree-diff: clear parent array in path_appendnew()

All of the other functions which allocate a combine_diff_path struct
zero out the parent array, but this code path does not. There's no bug,
since our caller will fill in most of the fields. But leaving the unused
fields (like combine_diff_parent.path) uninitialized makes working with
the struct more error-prone than it needs to be.

Let's just zero the parent field to be consistent with the
combine_diff_path_new() allocator.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 tree-diff.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

(limited to 'tree-diff.c')

diff --git a/tree-diff.c b/tree-diff.c
index d9237ffd9b..24f7b5912c 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -151,8 +151,6 @@ static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_
  *	process(p);
  *	p = pprev;
  *	; don't forget to free tail->next in the end
- *
- * p->parent[] remains uninitialized.
  */
 static struct combine_diff_path *path_appendnew(struct combine_diff_path *last,
 	int nparent, const struct strbuf *base, const char *path, int pathlen,
@@ -187,6 +185,8 @@ static struct combine_diff_path *path_appendnew(struct combine_diff_path *last,
 	p->mode = mode;
 	oidcpy(&p->oid, oid ? oid : null_oid());
 
+	memset(p->parent, 0, sizeof(p->parent[0]) * nparent);
+
 	return p;
 }
 
-- 
cgit v1.2.3


From a8dda1af6ab400d45b7524bc46b64e04d14fc912 Mon Sep 17 00:00:00 2001
From: Jeff King <peff@peff.net>
Date: Thu, 9 Jan 2025 03:46:49 -0500
Subject: tree-diff: drop path_appendnew() alloc optimization
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

When we're diffing trees, we create a list of combine_diff_path structs
that represent changed paths. We allocate each struct and add it to the
list with path_appendnew(), which we then feed to opt->pathchange().
That function tells us whether the path is of interest or not; if not,
then we can throw away the struct we allocated.

So there's an optimization to avoid extra allocations: instead of
throwing away the new entry, we try to reuse it. If it was large enough
to store the next path we care about, we can do so. And if not, we fall
back to freeing and re-allocating a new struct.

This comes from 72441af7c4 (tree-diff: rework diff_tree() to generate
diffs for multiparent cases as well, 2014-04-07), where the goal was to
have even the 2-parent diff code use the combine-diff infrastructure,
but without taking a performance hit.

The implementation causes some complexities in the interface (as we
store the allocation length inside the "next" pointer), and prevents us
from using the regular combine_diff_path_new() constructor. The
complexity is mostly contained inside two functions, but it's worth
re-evaluating how much it's helping.

That commit claims it helps ~1% on generating two-parent diffs in
linux.git. Here are the timings I get on the same command today ("old"
is the current tip of master, and "new" has this patch applied):

  Benchmark 1: ./git.old log --raw --no-abbrev --no-renames v3.10..v3.11
    Time (mean ± σ):     532.9 ms ±   5.8 ms    [User: 472.7 ms, System: 59.6 ms]
    Range (min … max):   525.9 ms … 543.3 ms    10 runs

  Benchmark 2: ./git.new log --raw --no-abbrev --no-renames v3.10..v3.11
    Time (mean ± σ):     538.3 ms ±   5.7 ms    [User: 478.0 ms, System: 59.7 ms]
    Range (min … max):   528.5 ms … 545.3 ms    10 runs

  Summary
    ./git.old log --raw --no-abbrev --no-renames v3.10..v3.11 ran
    1.01 ± 0.02 times faster than ./git.new log --raw --no-abbrev --no-renames v3.10..v3.11

So we do end up on average 1% faster, but with 2% of noise. I tried to
focus more on diff performance by running the commit traversal
separately, like:

  git rev-list v3.10..v3.11 >in

and then timing just the diffs:

  Benchmark 1: ./git.old diff-tree --stdin -r <in
    Time (mean ± σ):     415.7 ms ±   5.8 ms    [User: 357.7 ms, System: 58.0 ms]
    Range (min … max):   410.9 ms … 430.3 ms    10 runs

  Benchmark 2: ./git.new diff-tree --stdin -r <in
    Time (mean ± σ):     418.5 ms ±   2.1 ms    [User: 361.7 ms, System: 56.6 ms]
    Range (min … max):   414.9 ms … 421.3 ms    10 runs

  Summary
    ./git.old diff-tree --stdin -r <in ran
      1.01 ± 0.02 times faster than ./git.new diff-tree --stdin -r <in

That gets roughly the same result.

Adding in "-c" to do multi-parent diffs doesn't change much:

  Benchmark 1: ./git.old diff-tree --stdin -r -c <in
    Time (mean ± σ):     525.3 ms ±   6.6 ms    [User: 470.0 ms, System: 55.1 ms]
    Range (min … max):   508.4 ms … 531.0 ms    10 runs

  Benchmark 2: ./git.new diff-tree --stdin -r -c <in
    Time (mean ± σ):     532.3 ms ±   6.2 ms    [User: 469.0 ms, System: 63.1 ms]
    Range (min … max):   520.3 ms … 539.4 ms    10 runs

  Summary
    ./git.old diff-tree --stdin -r -c <in ran
      1.01 ± 0.02 times faster than ./git.new diff-tree --stdin -r -c <in

And of course if you add in a lot more work by doing actual
content-level diffs, any difference is lost entirely (here the newer
version is actually faster, but that's really just noise):

  Benchmark 1: ./git.old diff-tree --stdin -r --cc <in
    Time (mean ± σ):     11.571 s ±  0.064 s    [User: 11.287 s, System: 0.283 s]
    Range (min … max):   11.497 s … 11.615 s    3 runs

  Benchmark 2: ./git.new diff-tree --stdin -r --cc <in
    Time (mean ± σ):     11.466 s ±  0.109 s    [User: 11.108 s, System: 0.357 s]
    Range (min … max):   11.346 s … 11.560 s    3 runs

  Summary
    ./git.new diff-tree --stdin -r --cc <in ran
      1.01 ± 0.01 times faster than ./git.old diff-tree --stdin -r --cc <in

So my conclusion is that it probably does help a little, but it's mostly
lost in the noise. I could see an argument for keeping it, as the
complexity is hidden away in functions that do not often need to be
touched. But it does make them more confusing than necessary (despite
some detailed explanations from the author of that commit; it just took
me a while to wrap my head around what was going on) and prevents
further refactoring of the combine_diff_path struct. So let's drop it.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 tree-diff.c | 67 ++++++-------------------------------------------------------
 1 file changed, 6 insertions(+), 61 deletions(-)

(limited to 'tree-diff.c')

diff --git a/tree-diff.c b/tree-diff.c
index 24f7b5912c..22fc2d8f8c 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -127,30 +127,6 @@ static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_
 /*
  * Make a new combine_diff_path from path/mode/sha1
  * and append it to paths list tail.
- *
- * Memory for created elements could be reused:
- *
- *	- if last->next == NULL, the memory is allocated;
- *
- *	- if last->next != NULL, it is assumed that p=last->next was returned
- *	  earlier by this function, and p->next was *not* modified.
- *	  The memory is then reused from p.
- *
- * so for clients,
- *
- * - if you do need to keep the element
- *
- *	p = path_appendnew(p, ...);
- *	process(p);
- *	p->next = NULL;
- *
- * - if you don't need to keep the element after processing
- *
- *	pprev = p;
- *	p = path_appendnew(p, ...);
- *	process(p);
- *	p = pprev;
- *	; don't forget to free tail->next in the end
  */
 static struct combine_diff_path *path_appendnew(struct combine_diff_path *last,
 	int nparent, const struct strbuf *base, const char *path, int pathlen,
@@ -160,22 +136,8 @@ static struct combine_diff_path *path_appendnew(struct combine_diff_path *last,
 	size_t len = st_add(base->len, pathlen);
 	size_t alloclen = combine_diff_path_size(nparent, len);
 
-	/* if last->next is !NULL - it is a pre-allocated memory, we can reuse */
-	p = last->next;
-	if (p && (alloclen > (intptr_t)p->next)) {
-		FREE_AND_NULL(p);
-	}
-
-	if (!p) {
-		p = xmalloc(alloclen);
-
-		/*
-		 * until we go to it next round, .next holds how many bytes we
-		 * allocated (for faster realloc - we don't need copying old data).
-		 */
-		p->next = (struct combine_diff_path *)(intptr_t)alloclen;
-	}
-
+	p = xmalloc(alloclen);
+	p->next = NULL;
 	last->next = p;
 
 	p->path = (char *)&(p->parent[nparent]);
@@ -279,21 +241,11 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,
 		if (opt->pathchange)
 			keep = opt->pathchange(opt, p);
 
-		/*
-		 * If a path was filtered or consumed - we don't need to add it
-		 * to the list and can reuse its memory, leaving it as
-		 * pre-allocated element on the tail.
-		 *
-		 * On the other hand, if path needs to be kept, we need to
-		 * correct its .next to NULL, as it was pre-initialized to how
-		 * much memory was allocated.
-		 *
-		 * see path_appendnew() for details.
-		 */
-		if (!keep)
+		if (!keep) {
+			free(p);
+			pprev->next = NULL;
 			p = pprev;
-		else
-			p->next = NULL;
+		}
 	}
 
 	if (recurse) {
@@ -585,13 +537,6 @@ struct combine_diff_path *diff_tree_paths(
 	struct strbuf *base, struct diff_options *opt)
 {
 	p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt, 0);
-
-	/*
-	 * free pre-allocated last element, if any
-	 * (see path_appendnew() for details about why)
-	 */
-	FREE_AND_NULL(p->next);
-
 	return p;
 }
 
-- 
cgit v1.2.3


From 8c53354658462aa6783022def86750ab0b79eb6f Mon Sep 17 00:00:00 2001
From: Jeff King <peff@peff.net>
Date: Thu, 9 Jan 2025 03:49:07 -0500
Subject: tree-diff: pass whole path string to path_appendnew()

When diffing trees, we'll have a strbuf "base" containing the
slash-separted names of our parent trees, and a "path" string
representing an entry name from the current tree. We pass these
separately to path_appendnew(), which combines them to form a single
path string in the combine_diff_path struct.

Instead, let's append the path string to our base strbuf ourselves, pass
in the result, and then roll it back with strbuf_setlen(). This lets us
simplify path_appendnew() a bit, enabling further refactoring.

And while it might seem like this causes extra wasted allocations, it
does not in practice. We reuse the same strbuf for each tree entry, so
we only have to allocate it to match the largest name. Plus, in a
recursive diff we'll end up doing this same operation to extend the base
for the next level of recursion. So we're really just incurring a small
memcpy().

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 tree-diff.c | 11 ++++++-----
 1 file changed, 6 insertions(+), 5 deletions(-)

(limited to 'tree-diff.c')

diff --git a/tree-diff.c b/tree-diff.c
index 22fc2d8f8c..d2f8dd14a6 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -129,11 +129,10 @@ static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_
  * and append it to paths list tail.
  */
 static struct combine_diff_path *path_appendnew(struct combine_diff_path *last,
-	int nparent, const struct strbuf *base, const char *path, int pathlen,
+	int nparent, const char *path, size_t len,
 	unsigned mode, const struct object_id *oid)
 {
 	struct combine_diff_path *p;
-	size_t len = st_add(base->len, pathlen);
 	size_t alloclen = combine_diff_path_size(nparent, len);
 
 	p = xmalloc(alloclen);
@@ -141,8 +140,7 @@ static struct combine_diff_path *path_appendnew(struct combine_diff_path *last,
 	last->next = p;
 
 	p->path = (char *)&(p->parent[nparent]);
-	memcpy(p->path, base->buf, base->len);
-	memcpy(p->path + base->len, path, pathlen);
+	memcpy(p->path, path, len);
 	p->path[len] = 0;
 	p->mode = mode;
 	oidcpy(&p->oid, oid ? oid : null_oid());
@@ -206,7 +204,10 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,
 	if (emitthis) {
 		int keep;
 		struct combine_diff_path *pprev = p;
-		p = path_appendnew(p, nparent, base, path, pathlen, mode, oid);
+
+		strbuf_add(base, path, pathlen);
+		p = path_appendnew(p, nparent, base->buf, base->len, mode, oid);
+		strbuf_setlen(base, old_baselen);
 
 		for (i = 0; i < nparent; ++i) {
 			/*
-- 
cgit v1.2.3


From b20d7d348c4d32777cd577c221de529452baca03 Mon Sep 17 00:00:00 2001
From: Jeff King <peff@peff.net>
Date: Thu, 9 Jan 2025 03:49:44 -0500
Subject: tree-diff: inline path_appendnew()

Our path_appendnew() has been simplified to the point that it is mostly
just implementing combine_diff_path_new(), plus setting the "next"
pointer. Since there's only one caller, let's replace it completely with
a call to that helper function.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 tree-diff.c | 31 ++++---------------------------
 1 file changed, 4 insertions(+), 27 deletions(-)

(limited to 'tree-diff.c')

diff --git a/tree-diff.c b/tree-diff.c
index d2f8dd14a6..18e5a16716 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -124,32 +124,6 @@ static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_
 }
 
 
-/*
- * Make a new combine_diff_path from path/mode/sha1
- * and append it to paths list tail.
- */
-static struct combine_diff_path *path_appendnew(struct combine_diff_path *last,
-	int nparent, const char *path, size_t len,
-	unsigned mode, const struct object_id *oid)
-{
-	struct combine_diff_path *p;
-	size_t alloclen = combine_diff_path_size(nparent, len);
-
-	p = xmalloc(alloclen);
-	p->next = NULL;
-	last->next = p;
-
-	p->path = (char *)&(p->parent[nparent]);
-	memcpy(p->path, path, len);
-	p->path[len] = 0;
-	p->mode = mode;
-	oidcpy(&p->oid, oid ? oid : null_oid());
-
-	memset(p->parent, 0, sizeof(p->parent[0]) * nparent);
-
-	return p;
-}
-
 /*
  * new path should be added to combine diff
  *
@@ -206,7 +180,10 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,
 		struct combine_diff_path *pprev = p;
 
 		strbuf_add(base, path, pathlen);
-		p = path_appendnew(p, nparent, base->buf, base->len, mode, oid);
+		p = combine_diff_path_new(base->buf, base->len, mode,
+					  oid ? oid : null_oid(),
+					  nparent);
+		pprev->next = p;
 		strbuf_setlen(base, old_baselen);
 
 		for (i = 0; i < nparent; ++i) {
-- 
cgit v1.2.3


From a5c4e31af9b8b8fb362472ce3a1ec404df0da032 Mon Sep 17 00:00:00 2001
From: Jeff King <peff@peff.net>
Date: Thu, 9 Jan 2025 03:51:56 -0500
Subject: tree-diff: drop list-tail argument to diff_tree_paths()

The internals of the path diffing code, including ll_diff_tree_paths(),
all take an extra combine_diff_path parameter which they use as the tail
of a list of results, appending any new entries to it.

The public-facing diff_tree_paths() takes the same argument, but it just
makes the callers more awkward. They always start with a clean list, and
have to set up a fake head struct to pass in.

Let's keep the public API clean by always returning a new list. That
keeps the fake struct as an implementation detail of tree-diff.c.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 combine-diff.c |  9 +++------
 diff.h         |  2 +-
 tree-diff.c    | 14 ++++++++------
 3 files changed, 12 insertions(+), 13 deletions(-)

(limited to 'tree-diff.c')

diff --git a/combine-diff.c b/combine-diff.c
index f21e1f58ba..9527f3160d 100644
--- a/combine-diff.c
+++ b/combine-diff.c
@@ -1428,22 +1428,19 @@ static struct combine_diff_path *find_paths_multitree(
 {
 	int i, nparent = parents->nr;
 	const struct object_id **parents_oid;
-	struct combine_diff_path paths_head;
+	struct combine_diff_path *paths;
 	struct strbuf base;
 
 	ALLOC_ARRAY(parents_oid, nparent);
 	for (i = 0; i < nparent; i++)
 		parents_oid[i] = &parents->oid[i];
 
-	/* fake list head, so worker can assume it is non-NULL */
-	paths_head.next = NULL;
-
 	strbuf_init(&base, PATH_MAX);
-	diff_tree_paths(&paths_head, oid, parents_oid, nparent, &base, opt);
+	paths = diff_tree_paths(oid, parents_oid, nparent, &base, opt);
 
 	strbuf_release(&base);
 	free(parents_oid);
-	return paths_head.next;
+	return paths;
 }
 
 static int match_objfind(struct combine_diff_path *path,
diff --git a/diff.h b/diff.h
index 32ad17fd38..7831ed1a2b 100644
--- a/diff.h
+++ b/diff.h
@@ -462,7 +462,7 @@ const char *diff_line_prefix(struct diff_options *);
 extern const char mime_boundary_leader[];
 
 struct combine_diff_path *diff_tree_paths(
-	struct combine_diff_path *p, const struct object_id *oid,
+	const struct object_id *oid,
 	const struct object_id **parents_oid, int nparent,
 	struct strbuf *base, struct diff_options *opt);
 void diff_tree_oid(const struct object_id *old_oid,
diff --git a/tree-diff.c b/tree-diff.c
index 18e5a16716..e99e40da18 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -510,11 +510,14 @@ static struct combine_diff_path *ll_diff_tree_paths(
 }
 
 struct combine_diff_path *diff_tree_paths(
-	struct combine_diff_path *p, const struct object_id *oid,
+	const struct object_id *oid,
 	const struct object_id **parents_oid, int nparent,
 	struct strbuf *base, struct diff_options *opt)
 {
-	p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt, 0);
+	struct combine_diff_path head, *p;
+	/* fake list head, so worker can assume it is non-NULL */
+	head.next = NULL;
+	p = ll_diff_tree_paths(&head, oid, parents_oid, nparent, base, opt, 0);
 	return p;
 }
 
@@ -631,14 +634,13 @@ static void ll_diff_tree_oid(const struct object_id *old_oid,
 			     const struct object_id *new_oid,
 			     struct strbuf *base, struct diff_options *opt)
 {
-	struct combine_diff_path phead, *p;
+	struct combine_diff_path *paths, *p;
 	pathchange_fn_t pathchange_old = opt->pathchange;
 
-	phead.next = NULL;
 	opt->pathchange = emit_diff_first_parent_only;
-	diff_tree_paths(&phead, new_oid, &old_oid, 1, base, opt);
+	paths = diff_tree_paths(new_oid, &old_oid, 1, base, opt);
 
-	for (p = phead.next; p;) {
+	for (p = paths; p;) {
 		struct combine_diff_path *pprev = p;
 		p = p->next;
 		free(pprev);
-- 
cgit v1.2.3


From d8baf083c5a1a3e8dd27fe73e6000c5f6dddf1ca Mon Sep 17 00:00:00 2001
From: Jeff King <peff@peff.net>
Date: Thu, 9 Jan 2025 03:53:09 -0500
Subject: tree-diff: use the name "tail" to refer to list tail

The ll_diff_tree_paths() function and its helpers all append to a
running list by taking in a pointer to the old tail and returning the
new tail. But they just call this argument "p", which is not very
descriptive.

It gets particularly confusing in emit_path(), where we actually add to
the list, because "p" does double-duty: it is the tail of the list, but
it is also the entry which we add. Except that in some cases we _don't_
add a new entry (or we might even add it and roll it back) if the path
isn't interesting. At first glance, this makes it look like a bug that
we pass "p" on to ll_diff_tree_paths() to recurse; sometimes it is
getting the new entry we made and sometimes not!

But it's not a bug, because ll_diff_tree_paths() does not care about the
entry itself at all. It is only using its "next" pointer as the tail of
the list.

Let's swap out "p" for "tail" to make this obvious. And then in
emit_path() we'll continue to use "p" for our newly allocated entry.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 tree-diff.c | 33 +++++++++++++++++----------------
 1 file changed, 17 insertions(+), 16 deletions(-)

(limited to 'tree-diff.c')

diff --git a/tree-diff.c b/tree-diff.c
index e99e40da18..a1a611bef6 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -49,7 +49,7 @@
 } while(0)
 
 static struct combine_diff_path *ll_diff_tree_paths(
-	struct combine_diff_path *p, const struct object_id *oid,
+	struct combine_diff_path *tail, const struct object_id *oid,
 	const struct object_id **parents_oid, int nparent,
 	struct strbuf *base, struct diff_options *opt,
 	int depth);
@@ -134,7 +134,7 @@ static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_
  *	 t,  tp		-> path modified/added
  *			   (M for tp[i]=tp[imin], A otherwise)
  */
-static struct combine_diff_path *emit_path(struct combine_diff_path *p,
+static struct combine_diff_path *emit_path(struct combine_diff_path *tail,
 	struct strbuf *base, struct diff_options *opt, int nparent,
 	struct tree_desc *t, struct tree_desc *tp,
 	int imin, int depth)
@@ -177,13 +177,14 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,
 
 	if (emitthis) {
 		int keep;
-		struct combine_diff_path *pprev = p;
+		struct combine_diff_path *pprev = tail, *p;
 
 		strbuf_add(base, path, pathlen);
 		p = combine_diff_path_new(base->buf, base->len, mode,
 					  oid ? oid : null_oid(),
 					  nparent);
-		pprev->next = p;
+		tail->next = p;
+		tail = p;
 		strbuf_setlen(base, old_baselen);
 
 		for (i = 0; i < nparent; ++i) {
@@ -222,7 +223,7 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,
 		if (!keep) {
 			free(p);
 			pprev->next = NULL;
-			p = pprev;
+			tail = pprev;
 		}
 	}
 
@@ -239,13 +240,13 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *p,
 
 		strbuf_add(base, path, pathlen);
 		strbuf_addch(base, '/');
-		p = ll_diff_tree_paths(p, oid, parents_oid, nparent, base, opt,
-				       depth + 1);
+		tail = ll_diff_tree_paths(tail, oid, parents_oid, nparent, base, opt,
+					  depth + 1);
 		FAST_ARRAY_FREE(parents_oid, nparent);
 	}
 
 	strbuf_setlen(base, old_baselen);
-	return p;
+	return tail;
 }
 
 static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
@@ -359,7 +360,7 @@ static inline void update_tp_entries(struct tree_desc *tp, int nparent)
 }
 
 static struct combine_diff_path *ll_diff_tree_paths(
-	struct combine_diff_path *p, const struct object_id *oid,
+	struct combine_diff_path *tail, const struct object_id *oid,
 	const struct object_id **parents_oid, int nparent,
 	struct strbuf *base, struct diff_options *opt,
 	int depth)
@@ -463,8 +464,8 @@ static struct combine_diff_path *ll_diff_tree_paths(
 			}
 
 			/* D += {δ(t,pi) if pi=p[imin];  "+a" if pi > p[imin]} */
-			p = emit_path(p, base, opt, nparent,
-					&t, tp, imin, depth);
+			tail = emit_path(tail, base, opt, nparent,
+					 &t, tp, imin, depth);
 
 		skip_emit_t_tp:
 			/* t↓,  ∀ pi=p[imin]  pi↓ */
@@ -475,8 +476,8 @@ static struct combine_diff_path *ll_diff_tree_paths(
 		/* t < p[imin] */
 		else if (cmp < 0) {
 			/* D += "+t" */
-			p = emit_path(p, base, opt, nparent,
-					&t, /*tp=*/NULL, -1, depth);
+			tail = emit_path(tail, base, opt, nparent,
+					 &t, /*tp=*/NULL, -1, depth);
 
 			/* t↓ */
 			update_tree_entry(&t);
@@ -491,8 +492,8 @@ static struct combine_diff_path *ll_diff_tree_paths(
 						goto skip_emit_tp;
 			}
 
-			p = emit_path(p, base, opt, nparent,
-					/*t=*/NULL, tp, imin, depth);
+			tail = emit_path(tail, base, opt, nparent,
+					 /*t=*/NULL, tp, imin, depth);
 
 		skip_emit_tp:
 			/* ∀ pi=p[imin]  pi↓ */
@@ -506,7 +507,7 @@ static struct combine_diff_path *ll_diff_tree_paths(
 	FAST_ARRAY_FREE(tptree, nparent);
 	FAST_ARRAY_FREE(tp, nparent);
 
-	return p;
+	return tail;
 }
 
 struct combine_diff_path *diff_tree_paths(
-- 
cgit v1.2.3


From 6632bcba514f4a195447eb77264f75fed3a768e6 Mon Sep 17 00:00:00 2001
From: Jeff King <peff@peff.net>
Date: Thu, 9 Jan 2025 03:54:05 -0500
Subject: tree-diff: simplify emit_path() list management

In emit_path() we may append a new combine_diff_path entry to our list,
decide that we don't want it (because opt->pathchange() told us so) and
then roll it back.

Between the addition and the rollback, it doesn't matter if it's in the
list or not (no functions can even tell, since it's a singly-linked list
and we pass around just the tail entry).

So it's much simpler to just wait until opt->pathchange() tells us
whether to keep it, and either attach it (or free it) then. We do still
have to allocate it up front since it's that struct itself which is
passed to the pathchange callback.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 tree-diff.c | 11 +++++------
 1 file changed, 5 insertions(+), 6 deletions(-)

(limited to 'tree-diff.c')

diff --git a/tree-diff.c b/tree-diff.c
index a1a611bef6..f5ec19113c 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -177,14 +177,12 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *tail,
 
 	if (emitthis) {
 		int keep;
-		struct combine_diff_path *pprev = tail, *p;
+		struct combine_diff_path *p;
 
 		strbuf_add(base, path, pathlen);
 		p = combine_diff_path_new(base->buf, base->len, mode,
 					  oid ? oid : null_oid(),
 					  nparent);
-		tail->next = p;
-		tail = p;
 		strbuf_setlen(base, old_baselen);
 
 		for (i = 0; i < nparent; ++i) {
@@ -220,10 +218,11 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *tail,
 		if (opt->pathchange)
 			keep = opt->pathchange(opt, p);
 
-		if (!keep) {
+		if (keep) {
+			tail->next = p;
+			tail = p;
+		} else {
 			free(p);
-			pprev->next = NULL;
-			tail = pprev;
 		}
 	}
 
-- 
cgit v1.2.3


From 6979bf6f8f5e831ef38214edb158c7fb493540f7 Mon Sep 17 00:00:00 2001
From: Jeff King <peff@peff.net>
Date: Thu, 9 Jan 2025 03:57:00 -0500
Subject: tree-diff: make list tail-passing more explicit

The ll_diff_tree_paths() function and its helpers all take a pointer to
a list tail, possibly add to it, and then return the new tail. This
works but has two downsides:

  - The top-level caller (diff_tree_paths() in this case) has to make a
    fake combine_diff_path struct to act as the list head. This is
    especially weird here, as it's a flexible-sized struct which will
    have an empty FLEX_ARRAY field. That used to be a portability
    problem, though these days it is legal because our FLEX_ARRAY macro
    over-allocates if necessary. It's still kind of ugly, though.

  - Besides the name "tail", it's not immediately obvious that the entry
    we pass around will not be examined by each function. Using a
    pointer-to-pointer or similar makes it more obvious we only care
    about the pointer itself, not its contents.

We can solve both by passing around a pointer to the tail instead. That
gets rid of the return value entirely, though note that because of the
recursion we actually need a three-star pointer for this to work.

The result is fairly readable, as we only need to dereference the tail
in one spot. If we wanted to make it simpler we could wrap the tail in a
struct, which we pass around.

Another option is to convert combine_diff to use our generic list_head
API. I tried that and found the result became much harder to read
overall. It means that _all_ code that looks at combine_diff_path
structs needs to be modified, since the "next" pointer is now inside a
list_head which has to be dereferenced with list_entry(). And we lose
some type safety, since we're just passing around a list_head struct
everywhere, and everybody who looks at it has to specify the type to
list_entry themselves.

Signed-off-by: Jeff King <peff@peff.net>
Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 tree-diff.c | 47 +++++++++++++++++++++--------------------------
 1 file changed, 21 insertions(+), 26 deletions(-)

(limited to 'tree-diff.c')

diff --git a/tree-diff.c b/tree-diff.c
index f5ec19113c..60c558c2b5 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -48,8 +48,8 @@
 		free((x)); \
 } while(0)
 
-static struct combine_diff_path *ll_diff_tree_paths(
-	struct combine_diff_path *tail, const struct object_id *oid,
+static void ll_diff_tree_paths(
+	struct combine_diff_path ***tail, const struct object_id *oid,
 	const struct object_id **parents_oid, int nparent,
 	struct strbuf *base, struct diff_options *opt,
 	int depth);
@@ -134,10 +134,10 @@ static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_
  *	 t,  tp		-> path modified/added
  *			   (M for tp[i]=tp[imin], A otherwise)
  */
-static struct combine_diff_path *emit_path(struct combine_diff_path *tail,
-	struct strbuf *base, struct diff_options *opt, int nparent,
-	struct tree_desc *t, struct tree_desc *tp,
-	int imin, int depth)
+static void emit_path(struct combine_diff_path ***tail,
+		      struct strbuf *base, struct diff_options *opt,
+		      int nparent, struct tree_desc *t, struct tree_desc *tp,
+		      int imin, int depth)
 {
 	unsigned short mode;
 	const char *path;
@@ -219,8 +219,8 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *tail,
 			keep = opt->pathchange(opt, p);
 
 		if (keep) {
-			tail->next = p;
-			tail = p;
+			**tail = p;
+			*tail = &p->next;
 		} else {
 			free(p);
 		}
@@ -239,13 +239,12 @@ static struct combine_diff_path *emit_path(struct combine_diff_path *tail,
 
 		strbuf_add(base, path, pathlen);
 		strbuf_addch(base, '/');
-		tail = ll_diff_tree_paths(tail, oid, parents_oid, nparent, base, opt,
-					  depth + 1);
+		ll_diff_tree_paths(tail, oid, parents_oid, nparent, base, opt,
+				   depth + 1);
 		FAST_ARRAY_FREE(parents_oid, nparent);
 	}
 
 	strbuf_setlen(base, old_baselen);
-	return tail;
 }
 
 static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
@@ -358,8 +357,8 @@ static inline void update_tp_entries(struct tree_desc *tp, int nparent)
 			update_tree_entry(&tp[i]);
 }
 
-static struct combine_diff_path *ll_diff_tree_paths(
-	struct combine_diff_path *tail, const struct object_id *oid,
+static void ll_diff_tree_paths(
+	struct combine_diff_path ***tail, const struct object_id *oid,
 	const struct object_id **parents_oid, int nparent,
 	struct strbuf *base, struct diff_options *opt,
 	int depth)
@@ -463,8 +462,8 @@ static struct combine_diff_path *ll_diff_tree_paths(
 			}
 
 			/* D += {δ(t,pi) if pi=p[imin];  "+a" if pi > p[imin]} */
-			tail = emit_path(tail, base, opt, nparent,
-					 &t, tp, imin, depth);
+			emit_path(tail, base, opt, nparent,
+				  &t, tp, imin, depth);
 
 		skip_emit_t_tp:
 			/* t↓,  ∀ pi=p[imin]  pi↓ */
@@ -475,8 +474,8 @@ static struct combine_diff_path *ll_diff_tree_paths(
 		/* t < p[imin] */
 		else if (cmp < 0) {
 			/* D += "+t" */
-			tail = emit_path(tail, base, opt, nparent,
-					 &t, /*tp=*/NULL, -1, depth);
+			emit_path(tail, base, opt, nparent,
+				  &t, /*tp=*/NULL, -1, depth);
 
 			/* t↓ */
 			update_tree_entry(&t);
@@ -491,8 +490,8 @@ static struct combine_diff_path *ll_diff_tree_paths(
 						goto skip_emit_tp;
 			}
 
-			tail = emit_path(tail, base, opt, nparent,
-					 /*t=*/NULL, tp, imin, depth);
+			emit_path(tail, base, opt, nparent,
+				  /*t=*/NULL, tp, imin, depth);
 
 		skip_emit_tp:
 			/* ∀ pi=p[imin]  pi↓ */
@@ -505,8 +504,6 @@ static struct combine_diff_path *ll_diff_tree_paths(
 		free(tptree[i]);
 	FAST_ARRAY_FREE(tptree, nparent);
 	FAST_ARRAY_FREE(tp, nparent);
-
-	return tail;
 }
 
 struct combine_diff_path *diff_tree_paths(
@@ -514,11 +511,9 @@ struct combine_diff_path *diff_tree_paths(
 	const struct object_id **parents_oid, int nparent,
 	struct strbuf *base, struct diff_options *opt)
 {
-	struct combine_diff_path head, *p;
-	/* fake list head, so worker can assume it is non-NULL */
-	head.next = NULL;
-	p = ll_diff_tree_paths(&head, oid, parents_oid, nparent, base, opt, 0);
-	return p;
+	struct combine_diff_path *head = NULL, **tail = &head;
+	ll_diff_tree_paths(&tail, oid, parents_oid, nparent, base, opt, 0);
+	return head;
 }
 
 /*
-- 
cgit v1.2.3