[PATCH 00/11] More preparatory work for multiparent tree-walker

[PATCH 00/11] More preparatory work for multiparent tree-walker

[Kirill Smelkov]

Here I'm preparing tree-diff.c to be ready for the new tree-walker, so that the
final change is tractable and looks good and non noisy. Some small speedups
are gained along the way. The final bits are almost ready, but I don't want to
release them in a hurry.

Please apply and thanks,
Kirill

Kirill Smelkov (11):
  tree-diff: show_tree() is not needed
  tree-diff: consolidate code for emitting diffs and recursion in one place
  tree-diff: don't assume compare_tree_entry() returns -1,0,1
  tree-diff: move all action-taking code out of compare_tree_entry()
  tree-diff: rename compare_tree_entry -> tree_entry_pathcmp
  tree-diff: show_path prototype is not needed anymore
  tree-diff: simplify tree_entry_pathcmp
  tree-diff: remove special-case diff-emitting code for empty-tree cases
  tree-diff: rework diff_tree interface to be sha1 based
  tree-diff: no need to call "full" diff_tree_sha1 from show_path()
  tree-diff: reuse base str(buf) memory on sub-tree recursion

 diff.h      |   4 +-
 tree-diff.c | 270 ++++++++++++++++++++++++++++++++----------------------------
 2 files changed, 145 insertions(+), 129 deletions(-)

-- 
1.9.rc1.181.g641f458

[PATCH 01/11] tree-diff: show_tree() is not needed

[Kirill Smelkov]

We don't need special code for showing added/removed subtree, because we
can do the same via diff_tree_sha1, just passing NULL for absent tree.

And compared to show_tree(), which was calling show_entry() for every
tree entry, that would lead to the same show_entry() callings:

    show_tree(t):
        for e in t.entries:
            show_entry(e)

    diff_tree_sha1(NULL, new):  /* the same applies to (old, NULL) */
        diff_tree(t1=NULL, t2)
            ...
            if (!t1->size)
                show_entry(t2)
            ...

and possible overhead is negligible, since after the patch, timing for

    `git log --raw --no-abbrev --no-renames`

for navy.git and `linux.git v3.10..v3.11` is practically the same.

So let's say goodbye to show_tree() - it removes some code, but also,
and what is important, consolidates more code for showing/recursing into
trees into one place.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
---
 tree-diff.c | 35 +++--------------------------------
 1 file changed, 3 insertions(+), 32 deletions(-)

diff --git a/tree-diff.c b/tree-diff.c
index a8c2aec..2ad7788 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -55,25 +55,7 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2,
 	return 0;
 }
 
-/* A whole sub-tree went away or appeared */
-static void show_tree(struct diff_options *opt, const char *prefix,
-		      struct tree_desc *desc, struct strbuf *base)
-{
-	enum interesting match = entry_not_interesting;
-	for (; desc->size; update_tree_entry(desc)) {
-		if (match != all_entries_interesting) {
-			match = tree_entry_interesting(&desc->entry, base, 0,
-						       &opt->pathspec);
-			if (match == all_entries_not_interesting)
-				break;
-			if (match == entry_not_interesting)
-				continue;
-		}
-		show_entry(opt, prefix, desc, base);
-	}
-}
-
-/* A file entry went away or appeared */
+/* An entry went away or appeared */
 static void show_entry(struct diff_options *opt, const char *prefix,
 		       struct tree_desc *desc, struct strbuf *base)
 {
@@ -85,23 +67,12 @@ static void show_entry(struct diff_options *opt, const char *prefix,
 
 	strbuf_add(base, path, pathlen);
 	if (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode)) {
-		enum object_type type;
-		struct tree_desc inner;
-		void *tree;
-		unsigned long size;
-
-		tree = read_sha1_file(sha1, &type, &size);
-		if (!tree || type != OBJ_TREE)
-			die("corrupt tree sha %s", sha1_to_hex(sha1));
-
 		if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE))
 			opt->add_remove(opt, *prefix, mode, sha1, 1, base->buf, 0);
 
 		strbuf_addch(base, '/');
-
-		init_tree_desc(&inner, tree, size);
-		show_tree(opt, prefix, &inner, base);
-		free(tree);
+		diff_tree_sha1(*prefix == '-' ? sha1 : NULL,
+			       *prefix == '+' ? sha1 : NULL, base->buf, opt);
 	} else
 		opt->add_remove(opt, prefix[0], mode, sha1, 1, base->buf, 0);
 
-- 
1.9.rc1.181.g641f458

[PATCH 02/11] tree-diff: consolidate code for emitting diffs and recursion in one place

[Kirill Smelkov]

Currently both compare_tree_entry() and show_path() invoke opt diff
callbacks (opt->add_remove() and opt->change()), and also they both have
code which decides whether to recurse into sub-tree, and whether to emit
a tree as separate entry if DIFF_OPT_TREE_IN_RECURSIVE is set.

I.e. we have code duplication and logic scattered on two places.

Let's consolidate it - all diff emmiting code and recurion logic moves
to show_entry, which is now named as show_path, because it shows diff
for a path, based on up to two tree entries, with actual diff emitting
code being kept in new helper emit_diff() for clarity.

What we have as the result, is that compare_tree_entry is now free from
code with logic for diff generation, and also performance is not
affected as timings for

    `git log --raw --no-abbrev --no-renames`

for navy.git and `linux.git v3.10..v3.11`, just like in previous patch,
stay the same.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
---
 tree-diff.c | 117 ++++++++++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 86 insertions(+), 31 deletions(-)

diff --git a/tree-diff.c b/tree-diff.c
index 2ad7788..0c8e3fc 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -6,8 +6,8 @@
 #include "diffcore.h"
 #include "tree.h"
 
-static void show_entry(struct diff_options *opt, const char *prefix,
-		       struct tree_desc *desc, struct strbuf *base);
+static void show_path(struct strbuf *base, struct diff_options *opt,
+		      struct tree_desc *t1, struct tree_desc *t2);
 
 static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2,
 			      struct strbuf *base, struct diff_options *opt)
@@ -16,7 +16,6 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2,
 	const char *path1, *path2;
 	const unsigned char *sha1, *sha2;
 	int cmp, pathlen1, pathlen2;
-	int old_baselen = base->len;
 
 	sha1 = tree_entry_extract(t1, &path1, &mode1);
 	sha2 = tree_entry_extract(t2, &path2, &mode2);
@@ -30,51 +29,107 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2,
 	 */
 	cmp = base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);
 	if (cmp < 0) {
-		show_entry(opt, "-", t1, base);
+		show_path(base, opt, t1, /*t2=*/NULL);
 		return -1;
 	}
 	if (cmp > 0) {
-		show_entry(opt, "+", t2, base);
+		show_path(base, opt, /*t1=*/NULL, t2);
 		return 1;
 	}
 	if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) && mode1 == mode2)
 		return 0;
 
-	strbuf_add(base, path1, pathlen1);
-	if (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode1)) {
-		if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE)) {
-			opt->change(opt, mode1, mode2,
-				    sha1, sha2, 1, 1, base->buf, 0, 0);
-		}
-		strbuf_addch(base, '/');
-		diff_tree_sha1(sha1, sha2, base->buf, opt);
-	} else {
-		opt->change(opt, mode1, mode2, sha1, sha2, 1, 1, base->buf, 0, 0);
-	}
-	strbuf_setlen(base, old_baselen);
+	show_path(base, opt, t1, t2);
 	return 0;
 }
 
-/* An entry went away or appeared */
-static void show_entry(struct diff_options *opt, const char *prefix,
-		       struct tree_desc *desc, struct strbuf *base)
+
+/* convert path, t1/t2 -> opt->diff_*() callbacks */
+static void emit_diff(struct diff_options *opt, struct strbuf *path,
+		      struct tree_desc *t1, struct tree_desc *t2)
+{
+	unsigned int mode1 = t1 ? t1->entry.mode : 0;
+	unsigned int mode2 = t2 ? t2->entry.mode : 0;
+
+	if (mode1 && mode2) {
+		opt->change(opt, mode1, mode2, t1->entry.sha1, t2->entry.sha1,
+			1, 1, path->buf, 0, 0);
+	}
+	else {
+		const unsigned char *sha1;
+		unsigned int mode;
+		int addremove;
+
+		if (mode2) {
+			addremove = '+';
+			sha1 = t2->entry.sha1;
+			mode = mode2;
+		}
+		else {
+			addremove = '-';
+			sha1 = t1->entry.sha1;
+			mode = mode1;
+		}
+
+		opt->add_remove(opt, addremove, mode, sha1, 1, path->buf, 0);
+	}
+}
+
+
+/* new path should be added to diff
+ *
+ * 3 cases on how/when it should be called and behaves:
+ *
+ *	!t1,  t2	-> path added, parent lacks it
+ *	 t1, !t2	-> path removed from parent
+ *	 t1,  t2	-> path modified
+ */
+static void show_path(struct strbuf *base, struct diff_options *opt,
+		      struct tree_desc *t1, struct tree_desc *t2)
 {
 	unsigned mode;
 	const char *path;
-	const unsigned char *sha1 = tree_entry_extract(desc, &path, &mode);
-	int pathlen = tree_entry_len(&desc->entry);
+	const unsigned char *sha1;
+	int pathlen;
 	int old_baselen = base->len;
+	int isdir, recurse = 0, emitthis = 1;
+
+	/* at least something has to be valid */
+	assert(t1 || t2);
+
+	if (t2) {
+		/* path present in resulting tree */
+		sha1 = tree_entry_extract(t2, &path, &mode);
+		pathlen = tree_entry_len(&t2->entry);
+		isdir = S_ISDIR(mode);
+	}
+	else {
+		/* a path was removed - take path from parent. Also take
+		 * mode from parent, to decide on recursion.
+		 */
+		tree_entry_extract(t1, &path, &mode);
+		pathlen = tree_entry_len(&t1->entry);
+
+		isdir = S_ISDIR(mode);
+		sha1 = NULL;
+		mode = 0;
+	}
+
+	if (DIFF_OPT_TST(opt, RECURSIVE) && isdir) {
+		recurse = 1;
+		emitthis = DIFF_OPT_TST(opt, TREE_IN_RECURSIVE);
+	}
 
 	strbuf_add(base, path, pathlen);
-	if (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode)) {
-		if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE))
-			opt->add_remove(opt, *prefix, mode, sha1, 1, base->buf, 0);
 
+	if (emitthis)
+		emit_diff(opt, base, t1, t2);
+
+	if (recurse) {
 		strbuf_addch(base, '/');
-		diff_tree_sha1(*prefix == '-' ? sha1 : NULL,
-			       *prefix == '+' ? sha1 : NULL, base->buf, opt);
-	} else
-		opt->add_remove(opt, prefix[0], mode, sha1, 1, base->buf, 0);
+		diff_tree_sha1(t1 ? t1->entry.sha1 : NULL,
+			       t2 ? t2->entry.sha1 : NULL, base->buf, opt);
+	}
 
 	strbuf_setlen(base, old_baselen);
 }
@@ -117,12 +172,12 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
 		if (!t1->size) {
 			if (!t2->size)
 				break;
-			show_entry(opt, "+", t2, &base);
+			show_path(&base, opt, /*t1=*/NULL, t2);
 			update_tree_entry(t2);
 			continue;
 		}
 		if (!t2->size) {
-			show_entry(opt, "-", t1, &base);
+			show_path(&base, opt, t1, /*t2=*/NULL);
 			update_tree_entry(t1);
 			continue;
 		}
-- 
1.9.rc1.181.g641f458

[PATCH 03/11] tree-diff: don't assume compare_tree_entry() returns -1,0,1

[Kirill Smelkov]

It does, but we'll be reworking it in the next patch after it won't, and
besides it is better to stick to standard
strcmp/memcmp/base_name_compare/etc... convention, where comparison
function returns <0, =0, >0

Regarding performance, comparing for <0, =0, >0 should be a little bit
faster, than switch, because it is just 1 test-without-immediate
instruction and then up to 3 conditional branches, and in switch you
have up to 3 tests with immediate and up to 3 conditional branches.

No worry, that update_tree_entry(t2) is duplicated for =0 and >0 - it
will be good after we'll be adding support for multiparent walker and
will stay that way.

=0 case goes first, because it happens more often in real diffs - i.e.
paths are the same.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
---
 tree-diff.c | 22 ++++++++++++++--------
 1 file changed, 14 insertions(+), 8 deletions(-)

diff --git a/tree-diff.c b/tree-diff.c
index 0c8e3fc..c3fbfba 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -181,18 +181,24 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
 			update_tree_entry(t1);
 			continue;
 		}
-		switch (compare_tree_entry(t1, t2, &base, opt)) {
-		case -1:
+
+		cmp = compare_tree_entry(t1, t2, &base, opt);
+
+		/* t1 = t2 */
+		if (cmp == 0) {
 			update_tree_entry(t1);
-			continue;
-		case 0:
+			update_tree_entry(t2);
+		}
+
+		/* t1 < t2 */
+		else if (cmp < 0) {
 			update_tree_entry(t1);
-			/* Fallthrough */
-		case 1:
+		}
+
+		/* t1 > t2 */
+		else {
 			update_tree_entry(t2);
-			continue;
 		}
-		die("git diff-tree: internal error");
 	}
 
 	strbuf_release(&base);
-- 
1.9.rc1.181.g641f458

[PATCH 04/11] tree-diff: move all action-taking code out of compare_tree_entry()

[Kirill Smelkov]

- let it do only comparison.

This way the code is cleaner and more structured - cmp function only
compares, and the driver takes action based on comparison result.

There should be no change in performance, as effectively, we just move
if series from on place into another, and merge it to was-already-there
same switch/if, so the result is maybe a little bit faster.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
---
 tree-diff.c | 28 ++++++++++++----------------
 1 file changed, 12 insertions(+), 16 deletions(-)

diff --git a/tree-diff.c b/tree-diff.c
index c3fbfba..54a3d23 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -9,8 +9,7 @@
 static void show_path(struct strbuf *base, struct diff_options *opt,
 		      struct tree_desc *t1, struct tree_desc *t2);
 
-static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2,
-			      struct strbuf *base, struct diff_options *opt)
+static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2)
 {
 	unsigned mode1, mode2;
 	const char *path1, *path2;
@@ -28,19 +27,7 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2,
 	 * even when having the same name.
 	 */
 	cmp = base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);
-	if (cmp < 0) {
-		show_path(base, opt, t1, /*t2=*/NULL);
-		return -1;
-	}
-	if (cmp > 0) {
-		show_path(base, opt, /*t1=*/NULL, t2);
-		return 1;
-	}
-	if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) && mode1 == mode2)
-		return 0;
-
-	show_path(base, opt, t1, t2);
-	return 0;
+	return cmp;
 }
 
 
@@ -163,6 +150,8 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
 	strbuf_add(&base, base_str, baselen);
 
 	for (;;) {
+		int cmp;
+
 		if (diff_can_quit_early(opt))
 			break;
 		if (opt->pathspec.nr) {
@@ -182,21 +171,28 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
 			continue;
 		}
 
-		cmp = compare_tree_entry(t1, t2, &base, opt);
+		cmp = compare_tree_entry(t1, t2);
 
 		/* t1 = t2 */
 		if (cmp == 0) {
+			if (DIFF_OPT_TST(opt, FIND_COPIES_HARDER) ||
+			    hashcmp(t1->entry.sha1, t2->entry.sha1) ||
+			    (t1->entry.mode != t2->entry.mode))
+				show_path(&base, opt, t1, t2);
+
 			update_tree_entry(t1);
 			update_tree_entry(t2);
 		}
 
 		/* t1 < t2 */
 		else if (cmp < 0) {
+			show_path(&base, opt, t1, /*t2=*/NULL);
 			update_tree_entry(t1);
 		}
 
 		/* t1 > t2 */
 		else {
+			show_path(&base, opt, /*t1=*/NULL, t2);
 			update_tree_entry(t2);
 		}
 	}
-- 
1.9.rc1.181.g641f458

[PATCH 05/11] tree-diff: rename compare_tree_entry -> tree_entry_pathcmp

[Kirill Smelkov]

Since previous commit, this function does not compare entry hashes, and
mode are compared fully outside of it. So what it does is compare entry
names and DIR bit in modes. Reflect this in its name.

Add documentation stating the semantics, and move the note about
files/dirs comparison to it.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
---
 tree-diff.c | 15 +++++++++------
 1 file changed, 9 insertions(+), 6 deletions(-)

diff --git a/tree-diff.c b/tree-diff.c
index 54a3d23..df90bbe 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -9,7 +9,14 @@
 static void show_path(struct strbuf *base, struct diff_options *opt,
 		      struct tree_desc *t1, struct tree_desc *t2);
 
-static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2)
+/*
+ * Compare two tree entries, taking into account only path/S_ISDIR(mode),
+ * but not their sha1's.
+ *
+ * NOTE files and directories *always* compare differently, even when having
+ *      the same name - thanks to base_name_compare().
+ */
+static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)
 {
 	unsigned mode1, mode2;
 	const char *path1, *path2;
@@ -22,10 +29,6 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2)
 	pathlen1 = tree_entry_len(&t1->entry);
 	pathlen2 = tree_entry_len(&t2->entry);
 
-	/*
-	 * NOTE files and directories *always* compare differently,
-	 * even when having the same name.
-	 */
 	cmp = base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);
 	return cmp;
 }
@@ -171,7 +174,7 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
 			continue;
 		}
 
-		cmp = compare_tree_entry(t1, t2);
+		cmp = tree_entry_pathcmp(t1, t2);
 
 		/* t1 = t2 */
 		if (cmp == 0) {
-- 
1.9.rc1.181.g641f458

[PATCH 06/11] tree-diff: show_path prototype is not needed anymore

[Kirill Smelkov]

We moved all action-taking code below show_path() in recent HEAD~~
(tree-diff: move all action-taking code out of compare_tree_entry).

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
---
 tree-diff.c | 3 ---
 1 file changed, 3 deletions(-)

diff --git a/tree-diff.c b/tree-diff.c
index df90bbe..604dc57 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -6,9 +6,6 @@
 #include "diffcore.h"
 #include "tree.h"
 
-static void show_path(struct strbuf *base, struct diff_options *opt,
-		      struct tree_desc *t1, struct tree_desc *t2);
-
 /*
  * Compare two tree entries, taking into account only path/S_ISDIR(mode),
  * but not their sha1's.
-- 
1.9.rc1.181.g641f458

[PATCH 07/11] tree-diff: simplify tree_entry_pathcmp

[Kirill Smelkov]

Since 74aa4a18 (Finally switch over tree descriptors to contain a
pre-parsed entry) we can safely access all tree_desc->entry fields directly
instead of first "extracting" them through tree_entry_extract.

Use it. The code generated stays the same - only it now visually looks
cleaner.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
---
 tree-diff.c | 17 ++++++-----------
 1 file changed, 6 insertions(+), 11 deletions(-)

diff --git a/tree-diff.c b/tree-diff.c
index 604dc57..330ca07 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -15,18 +15,13 @@
  */
 static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)
 {
-	unsigned mode1, mode2;
-	const char *path1, *path2;
-	const unsigned char *sha1, *sha2;
-	int cmp, pathlen1, pathlen2;
+	struct name_entry *e1, *e2;
+	int cmp;
 
-	sha1 = tree_entry_extract(t1, &path1, &mode1);
-	sha2 = tree_entry_extract(t2, &path2, &mode2);
-
-	pathlen1 = tree_entry_len(&t1->entry);
-	pathlen2 = tree_entry_len(&t2->entry);
-
-	cmp = base_name_compare(path1, pathlen1, mode1, path2, pathlen2, mode2);
+	e1 = &t1->entry;
+	e2 = &t2->entry;
+	cmp = base_name_compare(e1->path, tree_entry_len(e1), e1->mode,
+				e2->path, tree_entry_len(e2), e2->mode);
 	return cmp;
 }
 
-- 
1.9.rc1.181.g641f458

[PATCH 08/11] tree-diff: remove special-case diff-emitting code for empty-tree cases

[Kirill Smelkov]

via teaching tree_entry_pathcmp() how to compare empty tree descriptors:

While walking trees, we iterate their entries from lowest to highest in
sort order, so empty tree means all entries were already went over.

If we artificially assign +infinity value to such tree "entry", it will
go after all usual entries, and through the usual driver loop we will be
taking the same actions, which were hand-coded for special cases, i.e.

    t1 empty, t2 non-empty
        pathcmp(+∞, t2) -> +1
        show_path(/*t1=*/NULL, t2);     /* = t1 > t2 case in main loop */

    t1 non-empty, t2-empty
        pathcmp(t1, +∞) -> -1
        show_path(t1, /*t2=*/NULL);     /* = t1 < t2 case in main loop */

Right now we never go to when compared tree descriptors are infinity, as
this condition is checked in the loop beginning as finishing criteria,
but will do in the future, when there will be several parents iterated
simultaneously, and some pair of them would run to the end.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
---
 tree-diff.c | 21 +++++++++------------
 1 file changed, 9 insertions(+), 12 deletions(-)

diff --git a/tree-diff.c b/tree-diff.c
index 330ca07..7688402 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -12,12 +12,19 @@
  *
  * NOTE files and directories *always* compare differently, even when having
  *      the same name - thanks to base_name_compare().
+ *
+ * NOTE empty (=invalid) descriptor(s) take part in comparison as +infty.
  */
 static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)
 {
 	struct name_entry *e1, *e2;
 	int cmp;
 
+	if (!t1->size)
+		return t2->size ? +1 /* +∞ > c */  : 0 /* +∞ = +∞ */;
+	else if (!t2->size)
+		return -1;	/* c < +∞ */
+
 	e1 = &t1->entry;
 	e2 = &t2->entry;
 	cmp = base_name_compare(e1->path, tree_entry_len(e1), e1->mode,
@@ -153,18 +160,8 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
 			skip_uninteresting(t1, &base, opt);
 			skip_uninteresting(t2, &base, opt);
 		}
-		if (!t1->size) {
-			if (!t2->size)
-				break;
-			show_path(&base, opt, /*t1=*/NULL, t2);
-			update_tree_entry(t2);
-			continue;
-		}
-		if (!t2->size) {
-			show_path(&base, opt, t1, /*t2=*/NULL);
-			update_tree_entry(t1);
-			continue;
-		}
+		if (!t1->size && !t2->size)
+			break;
 
 		cmp = tree_entry_pathcmp(t1, t2);
 
-- 
1.9.rc1.181.g641f458

[PATCH 09/11] tree-diff: rework diff_tree interface to be sha1 based

[Kirill Smelkov]

In the next commit this will allow to reduce intermediate calls, when
recursing into subtrees - at that stage we know only subtree sha1, and
it is natural for tree walker to start from that phase. For now we do

    diff_tree
        show_path
            diff_tree_sha1
                diff_tree
                    ...

and the change will allow to reduce it to

    diff_tree
        show_path
            diff_tree

Also, it will allow to omit allocating strbuf for each subtree, and just
reuse the common strbuf via playing with its len.

The above-mentioned improvements go in the next 2 patches.

The downside is that try_to_follow_renames(), if active, we cause
re-reading of 2 initial trees, which was negligible based on my timings,
and which is outweighed cogently by the upsides.

NOTE To keep with the current interface and semantics, I needed to
rename the function. It will probably be renamed once more later, when
its semantic will change to just generate paths for a diff, instead of
producing it. So the current name is appropriate, but probably temporary.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
---
 diff.h      |  4 ++--
 tree-diff.c | 60 ++++++++++++++++++++++++++++--------------------------------
 2 files changed, 30 insertions(+), 34 deletions(-)

diff --git a/diff.h b/diff.h
index a24a767..4994d15 100644
--- a/diff.h
+++ b/diff.h
@@ -189,8 +189,8 @@ const char *diff_line_prefix(struct diff_options *);
 
 extern const char mime_boundary_leader[];
 
-extern int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
-		     const char *base, struct diff_options *opt);
+extern int __diff_tree_sha1(const unsigned char *old, const unsigned char *new,
+			    const char *base, struct diff_options *opt);
 extern int diff_tree_sha1(const unsigned char *old, const unsigned char *new,
 			  const char *base, struct diff_options *opt);
 extern int diff_root_tree_sha1(const unsigned char *new, const char *base,
diff --git a/tree-diff.c b/tree-diff.c
index 7688402..dd6c760 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -139,12 +139,17 @@ static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
 	}
 }
 
-int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
-	      const char *base_str, struct diff_options *opt)
+int __diff_tree_sha1(const unsigned char *old, const unsigned char *new,
+		     const char *base_str, struct diff_options *opt)
 {
+	struct tree_desc t1, t2;
+	void *t1tree, *t2tree;
 	struct strbuf base;
 	int baselen = strlen(base_str);
 
+	t1tree = fill_tree_descriptor(&t1, old);
+	t2tree = fill_tree_descriptor(&t2, new);
+
 	/* Enable recursion indefinitely */
 	opt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);
 
@@ -157,39 +162,41 @@ int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
 		if (diff_can_quit_early(opt))
 			break;
 		if (opt->pathspec.nr) {
-			skip_uninteresting(t1, &base, opt);
-			skip_uninteresting(t2, &base, opt);
+			skip_uninteresting(&t1, &base, opt);
+			skip_uninteresting(&t2, &base, opt);
 		}
-		if (!t1->size && !t2->size)
+		if (!t1.size && !t2.size)
 			break;
 
-		cmp = tree_entry_pathcmp(t1, t2);
+		cmp = tree_entry_pathcmp(&t1, &t2);
 
 		/* t1 = t2 */
 		if (cmp == 0) {
 			if (DIFF_OPT_TST(opt, FIND_COPIES_HARDER) ||
-			    hashcmp(t1->entry.sha1, t2->entry.sha1) ||
-			    (t1->entry.mode != t2->entry.mode))
-				show_path(&base, opt, t1, t2);
+			    hashcmp(t1.entry.sha1, t2.entry.sha1) ||
+			    (t1.entry.mode != t2.entry.mode))
+				show_path(&base, opt, &t1, &t2);
 
-			update_tree_entry(t1);
-			update_tree_entry(t2);
+			update_tree_entry(&t1);
+			update_tree_entry(&t2);
 		}
 
 		/* t1 < t2 */
 		else if (cmp < 0) {
-			show_path(&base, opt, t1, /*t2=*/NULL);
-			update_tree_entry(t1);
+			show_path(&base, opt, &t1, /*t2=*/NULL);
+			update_tree_entry(&t1);
 		}
 
 		/* t1 > t2 */
 		else {
-			show_path(&base, opt, /*t1=*/NULL, t2);
-			update_tree_entry(t2);
+			show_path(&base, opt, /*t1=*/NULL, &t2);
+			update_tree_entry(&t2);
 		}
 	}
 
 	strbuf_release(&base);
+	free(t2tree);
+	free(t1tree);
 	return 0;
 }
 
@@ -204,7 +211,7 @@ static inline int diff_might_be_rename(void)
 		!DIFF_FILE_VALID(diff_queued_diff.queue[0]->one);
 }
 
-static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, const char *base, struct diff_options *opt)
+static void try_to_follow_renames(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
 {
 	struct diff_options diff_opts;
 	struct diff_queue_struct *q = &diff_queued_diff;
@@ -242,7 +249,7 @@ static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, co
 	diff_opts.break_opt = opt->break_opt;
 	diff_opts.rename_score = opt->rename_score;
 	diff_setup_done(&diff_opts);
-	diff_tree(t1, t2, base, &diff_opts);
+	__diff_tree_sha1(old, new, base, &diff_opts);
 	diffcore_std(&diff_opts);
 	free_pathspec(&diff_opts.pathspec);
 
@@ -303,23 +310,12 @@ static void try_to_follow_renames(struct tree_desc *t1, struct tree_desc *t2, co
 
 int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
 {
-	void *tree1, *tree2;
-	struct tree_desc t1, t2;
-	unsigned long size1, size2;
 	int retval;
 
-	tree1 = fill_tree_descriptor(&t1, old);
-	tree2 = fill_tree_descriptor(&t2, new);
-	size1 = t1.size;
-	size2 = t2.size;
-	retval = diff_tree(&t1, &t2, base, opt);
-	if (!*base && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename()) {
-		init_tree_desc(&t1, tree1, size1);
-		init_tree_desc(&t2, tree2, size2);
-		try_to_follow_renames(&t1, &t2, base, opt);
-	}
-	free(tree1);
-	free(tree2);
+	retval = __diff_tree_sha1(old, new, base, opt);
+	if (!*base && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename())
+		try_to_follow_renames(old, new, base, opt);
+
 	return retval;
 }
 
-- 
1.9.rc1.181.g641f458

[PATCH 10/11] tree-diff: no need to call "full" diff_tree_sha1 from show_path()

[Kirill Smelkov]

As described in previous commit, when recursing into sub-trees, we can
use lower-level tree walker, since its interface is now sha1 based.

The change is ok, because diff_tree_sha1() only invokes
__diff_tree_sha1(), and also, if base is empty, try_to_follow_renames().
But base is not empty here, as we have added a path and '/' before
recursing.

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
---
 tree-diff.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/tree-diff.c b/tree-diff.c
index dd6c760..e385ed4 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -116,8 +116,8 @@ static void show_path(struct strbuf *base, struct diff_options *opt,
 
 	if (recurse) {
 		strbuf_addch(base, '/');
-		diff_tree_sha1(t1 ? t1->entry.sha1 : NULL,
-			       t2 ? t2->entry.sha1 : NULL, base->buf, opt);
+		__diff_tree_sha1(t1 ? t1->entry.sha1 : NULL,
+				 t2 ? t2->entry.sha1 : NULL, base->buf, opt);
 	}
 
 	strbuf_setlen(base, old_baselen);
-- 
1.9.rc1.181.g641f458

[PATCH 11/11] tree-diff: reuse base str(buf) memory on sub-tree recursion

[Kirill Smelkov]

instead of allocating it all the time for every subtree in
__diff_tree_sha1, let's allocate it once in diff_tree_sha1, and then all
callee just use it in stacking style, without memory allocations.

This should be faster, and for me this change gives the following
slight speedups for `git log --raw --no-abbrev --no-renames`

                navy.git    linux.git v3.10..v3.11

    before      0.547s      1.791s
    after       0.541s      1.777s
    speedup     1.1%        0.8%

Signed-off-by: Kirill Smelkov <kirr@mns.spb.ru>
---
 diff.h      |  2 +-
 tree-diff.c | 36 ++++++++++++++++++------------------
 2 files changed, 19 insertions(+), 19 deletions(-)

diff --git a/diff.h b/diff.h
index 4994d15..14016ce 100644
--- a/diff.h
+++ b/diff.h
@@ -190,7 +190,7 @@ const char *diff_line_prefix(struct diff_options *);
 extern const char mime_boundary_leader[];
 
 extern int __diff_tree_sha1(const unsigned char *old, const unsigned char *new,
-			    const char *base, struct diff_options *opt);
+			    struct strbuf *base, struct diff_options *opt);
 extern int diff_tree_sha1(const unsigned char *old, const unsigned char *new,
 			  const char *base, struct diff_options *opt);
 extern int diff_root_tree_sha1(const unsigned char *new, const char *base,
diff --git a/tree-diff.c b/tree-diff.c
index e385ed4..2adda04 100644
--- a/tree-diff.c
+++ b/tree-diff.c
@@ -117,7 +117,7 @@ static void show_path(struct strbuf *base, struct diff_options *opt,
 	if (recurse) {
 		strbuf_addch(base, '/');
 		__diff_tree_sha1(t1 ? t1->entry.sha1 : NULL,
-				 t2 ? t2->entry.sha1 : NULL, base->buf, opt);
+				 t2 ? t2->entry.sha1 : NULL, base, opt);
 	}
 
 	strbuf_setlen(base, old_baselen);
@@ -140,12 +140,10 @@ static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
 }
 
 int __diff_tree_sha1(const unsigned char *old, const unsigned char *new,
-		     const char *base_str, struct diff_options *opt)
+		     struct strbuf *base, struct diff_options *opt)
 {
 	struct tree_desc t1, t2;
 	void *t1tree, *t2tree;
-	struct strbuf base;
-	int baselen = strlen(base_str);
 
 	t1tree = fill_tree_descriptor(&t1, old);
 	t2tree = fill_tree_descriptor(&t2, new);
@@ -153,17 +151,14 @@ int __diff_tree_sha1(const unsigned char *old, const unsigned char *new,
 	/* Enable recursion indefinitely */
 	opt->pathspec.recursive = DIFF_OPT_TST(opt, RECURSIVE);
 
-	strbuf_init(&base, PATH_MAX);
-	strbuf_add(&base, base_str, baselen);
-
 	for (;;) {
 		int cmp;
 
 		if (diff_can_quit_early(opt))
 			break;
 		if (opt->pathspec.nr) {
-			skip_uninteresting(&t1, &base, opt);
-			skip_uninteresting(&t2, &base, opt);
+			skip_uninteresting(&t1, base, opt);
+			skip_uninteresting(&t2, base, opt);
 		}
 		if (!t1.size && !t2.size)
 			break;
@@ -175,7 +170,7 @@ int __diff_tree_sha1(const unsigned char *old, const unsigned char *new,
 			if (DIFF_OPT_TST(opt, FIND_COPIES_HARDER) ||
 			    hashcmp(t1.entry.sha1, t2.entry.sha1) ||
 			    (t1.entry.mode != t2.entry.mode))
-				show_path(&base, opt, &t1, &t2);
+				show_path(base, opt, &t1, &t2);
 
 			update_tree_entry(&t1);
 			update_tree_entry(&t2);
@@ -183,18 +178,17 @@ int __diff_tree_sha1(const unsigned char *old, const unsigned char *new,
 
 		/* t1 < t2 */
 		else if (cmp < 0) {
-			show_path(&base, opt, &t1, /*t2=*/NULL);
+			show_path(base, opt, &t1, /*t2=*/NULL);
 			update_tree_entry(&t1);
 		}
 
 		/* t1 > t2 */
 		else {
-			show_path(&base, opt, /*t1=*/NULL, &t2);
+			show_path(base, opt, /*t1=*/NULL, &t2);
 			update_tree_entry(&t2);
 		}
 	}
 
-	strbuf_release(&base);
 	free(t2tree);
 	free(t1tree);
 	return 0;
@@ -211,7 +205,7 @@ static inline int diff_might_be_rename(void)
 		!DIFF_FILE_VALID(diff_queued_diff.queue[0]->one);
 }
 
-static void try_to_follow_renames(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
+static void try_to_follow_renames(const unsigned char *old, const unsigned char *new, struct strbuf *base, struct diff_options *opt)
 {
 	struct diff_options diff_opts;
 	struct diff_queue_struct *q = &diff_queued_diff;
@@ -308,13 +302,19 @@ static void try_to_follow_renames(const unsigned char *old, const unsigned char
 	q->nr = 1;
 }
 
-int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base, struct diff_options *opt)
+int diff_tree_sha1(const unsigned char *old, const unsigned char *new, const char *base_str, struct diff_options *opt)
 {
+	struct strbuf base;
 	int retval;
 
-	retval = __diff_tree_sha1(old, new, base, opt);
-	if (!*base && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename())
-		try_to_follow_renames(old, new, base, opt);
+	strbuf_init(&base, PATH_MAX);
+	strbuf_addstr(&base, base_str);
+
+	retval = __diff_tree_sha1(old, new, &base, opt);
+	if (!*base_str && DIFF_OPT_TST(opt, FOLLOW_RENAMES) && diff_might_be_rename())
+		try_to_follow_renames(old, new, &base, opt);
+
+	strbuf_release(&base);
 
 	return retval;
 }
-- 
1.9.rc1.181.g641f458

Re: [PATCH 00/11] More preparatory work for multiparent tree-walker

[Junio C Hamano]

Kirill Smelkov <kirr@mns.spb.ru> writes:

> Here I'm preparing tree-diff.c to be ready for the new tree-walker, so that the
> final change is tractable and looks good and non noisy. Some small speedups
> are gained along the way. The final bits are almost ready, but I don't want to
> release them in a hurry.

No worries.  We are not in a hurry to apply non-regression-fix
changes during a pre-release feature freeze period anyway.

This seems to somehow conflict with other topics and does not
cleanly apply on top of your other tree-diff topic, by the way.

Re: [PATCH 00/11] More preparatory work for multiparent tree-walker

[Kirill Smelkov]

On Mon, Feb 10, 2014 at 04:28:33PM -0800, Junio C Hamano wrote:
> Kirill Smelkov <kirr@mns.spb.ru> writes:
> 
> > Here I'm preparing tree-diff.c to be ready for the new tree-walker, so that the
> > final change is tractable and looks good and non noisy. Some small speedups
> > are gained along the way. The final bits are almost ready, but I don't want to
> > release them in a hurry.
> 
> No worries.  We are not in a hurry to apply non-regression-fix
> changes during a pre-release feature freeze period anyway.

I see.


> This seems to somehow conflict with other topics and does not
> cleanly apply on top of your other tree-diff topic, by the way.

Sorry for the confusion. Could you please do the following:

Patches should be applied over to ks/tree-diff-walk
(74aa4a18). Before applying the patches, please cherry-pick

    c90483d9    (tree-diff: no need to manually verify that there is no
                 mode change for a path)

    ef4f0928    (tree-diff: no need to pass match to
                 skip_uninteresting())

into that branch, and drop them from ks/combine-diff - we'll have one
branch reworking the diff tree-walker, and the other taking advantage of
it for combine-diff.

Then apply sent-here patches, which, as I've verified this time, should
apply cleanly.

Thanks and sorry again,
Kirill

Re: [PATCH 00/11] More preparatory work for multiparent tree-walker

[Junio C Hamano]

Kirill Smelkov <kirr@mns.spb.ru> writes:

> Sorry for the confusion. Could you please do the following:
>
> Patches should be applied over to ks/tree-diff-walk
> (74aa4a18). Before applying the patches, please cherry-pick
>
>     c90483d9    (tree-diff: no need to manually verify that there is no
>                  mode change for a path)
>
>     ef4f0928    (tree-diff: no need to pass match to
>                  skip_uninteresting())
>
> into that branch, and drop them from ks/combine-diff - we'll have one
> branch reworking the diff tree-walker, and the other taking advantage of
> it for combine-diff.

As long as that does not lose changes to tests and clean-ups, I'm
fine with that direction.  For example, I do not know if you want to
lose e3f62d12 (diffcore-order: export generic ordering interface,
2014-01-20), which is part of the combine-diff topic.

Re: [PATCH 00/11] More preparatory work for multiparent tree-walker

[Kirill Smelkov]

On Tue, Feb 11, 2014 at 11:59:02AM -0800, Junio C Hamano wrote:
> Kirill Smelkov <kirr@mns.spb.ru> writes:
> 
> > Sorry for the confusion. Could you please do the following:
> >
> > Patches should be applied over to ks/tree-diff-walk
> > (74aa4a18). Before applying the patches, please cherry-pick
> >
> >     c90483d9    (tree-diff: no need to manually verify that there is no
> >                  mode change for a path)
> >
> >     ef4f0928    (tree-diff: no need to pass match to
> >                  skip_uninteresting())
> >
> > into that branch, and drop them from ks/combine-diff - we'll have one
> > branch reworking the diff tree-walker, and the other taking advantage of
> > it for combine-diff.
> 
> As long as that does not lose changes to tests and clean-ups, I'm
> fine with that direction.  For example, I do not know if you want to
> lose e3f62d12 (diffcore-order: export generic ordering interface,
> 2014-01-20), which is part of the combine-diff topic.

Sorry for the confusion again, and please don't worry: we are not going
to lose anything - my only plea here was to transfer two of the patches
to more appropriate topic.

That couple touches tree-diff.c - they were some initial cleanups I've
noticed while working on separate combine-diff tree-walker, which we
decided to drop instead of generalizing diff tree-walker to handle all
cases. Only the cleanups are still relevant and needed as a base for
what I've sent you here.

And as to e3f62d12 (diffcore-order: export generic ordering interface,
2014-01-20) and other patches on ks/diff-c-with-diff-order topic - they
stay as they are - we do not need to rework them as ks/combine-diff
builds on top of the topic and generalizing diff tree-walker is
orthogonal work.


So in short: could you please transform the two "tree-diff" patches from
ks/combine-diff to ks/tree-diff-walk, then apply sent-here patches to
ks/tree-diff-walk; thats all.


Thanks,
Kirill

Re: [PATCH 00/11] More preparatory work for multiparent tree-walker

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> Kirill Smelkov <kirr@mns.spb.ru> writes:
>
>> Sorry for the confusion. Could you please do the following:
>>
>> Patches should be applied over to ks/tree-diff-walk
>> (74aa4a18). Before applying the patches, please cherry-pick
>>
>>     c90483d9    (tree-diff: no need to manually verify that there is no
>>                  mode change for a path)
>>
>>     ef4f0928    (tree-diff: no need to pass match to
>>                  skip_uninteresting())
>>
>> into that branch, and drop them from ks/combine-diff - we'll have one
>> branch reworking the diff tree-walker, and the other taking advantage of
>> it for combine-diff.
>
> As long as that does not lose changes to tests and clean-ups, I'm
> fine with that direction.  For example, I do not know if you want to
> lose e3f62d12 (diffcore-order: export generic ordering interface,
> 2014-01-20), which is part of the combine-diff topic.

Ahh, sorry, I misread the "drop" as "salvage these two and drop the
rest".  The new series does apply cleanly on a commit in master..pu
that has both ks/tree-diff-walk and ks/combine-diff, and the latter
is not yet in 'next' so we are free to reorganize.

Let me flip the latter topic around, also queue these updates and
push the result out on 'pu'.

Thanks.

Re: [PATCH 11/11] tree-diff: reuse base str(buf) memory on sub-tree recursion

[Kirill Smelkov]

On Fri, Feb 07, 2014 at 09:48:52PM +0400, Kirill Smelkov wrote:
> instead of allocating it all the time for every subtree in
> __diff_tree_sha1, let's allocate it once in diff_tree_sha1, and then all
> callee just use it in stacking style, without memory allocations.
> 
> This should be faster, and for me this change gives the following
> slight speedups for `git log --raw --no-abbrev --no-renames`
> 
>                 navy.git    linux.git v3.10..v3.11
> 
>     before      0.547s      1.791s
>     after       0.541s      1.777s
>     speedup     1.1%        0.8%

The timings above was done with

    `git log --raw --no-abbrev --no-renames --format='%H'`
                                            ^^^^^^^^^^^^^

Please change them to correct timings:


                navy.git    linux.git v3.10..v3.11

    before      0.618s      1.903s
    after       0.611s      1.889s
    speedup     1.1%        0.7%



Thanks,
Kirill

Re: [PATCH 00/11] More preparatory work for multiparent tree-walker

[Kirill Smelkov]

On Wed, Feb 12, 2014 at 09:25:51AM -0800, Junio C Hamano wrote:
> Junio C Hamano <gitster@pobox.com> writes:
> 
> > Kirill Smelkov <kirr@mns.spb.ru> writes:
> >
> >> Sorry for the confusion. Could you please do the following:
> >>
> >> Patches should be applied over to ks/tree-diff-walk
> >> (74aa4a18). Before applying the patches, please cherry-pick
> >>
> >>     c90483d9    (tree-diff: no need to manually verify that there is no
> >>                  mode change for a path)
> >>
> >>     ef4f0928    (tree-diff: no need to pass match to
> >>                  skip_uninteresting())
> >>
> >> into that branch, and drop them from ks/combine-diff - we'll have one
> >> branch reworking the diff tree-walker, and the other taking advantage of
> >> it for combine-diff.
> >
> > As long as that does not lose changes to tests and clean-ups, I'm
> > fine with that direction.  For example, I do not know if you want to
> > lose e3f62d12 (diffcore-order: export generic ordering interface,
> > 2014-01-20), which is part of the combine-diff topic.
> 
> Ahh, sorry, I misread the "drop" as "salvage these two and drop the
> rest".  The new series does apply cleanly on a commit in master..pu
> that has both ks/tree-diff-walk and ks/combine-diff, and the latter
> is not yet in 'next' so we are free to reorganize.
> 
> Let me flip the latter topic around, also queue these updates and
> push the result out on 'pu'.
> 
> Thanks.

Thank you. As we've managed to apply this to pu, I've send the final
speedup patches. Please review them as time permits.

Thanks beforehand,
Kirill

Re: [PATCH 02/11] tree-diff: consolidate code for emitting diffs and recursion in one place

[Junio C Hamano]

Kirill Smelkov <kirr@mns.spb.ru> writes:

> +static void show_path(struct strbuf *base, struct diff_options *opt,
> +		      struct tree_desc *t1, struct tree_desc *t2)
>  {
>  	unsigned mode;
>  	const char *path;
> -	const unsigned char *sha1 = tree_entry_extract(desc, &path, &mode);
> -	int pathlen = tree_entry_len(&desc->entry);
> +	const unsigned char *sha1;
> +	int pathlen;
>  	int old_baselen = base->len;
> +	int isdir, recurse = 0, emitthis = 1;
> +
> +	/* at least something has to be valid */
> +	assert(t1 || t2);
> +
> +	if (t2) {
> +		/* path present in resulting tree */
> +		sha1 = tree_entry_extract(t2, &path, &mode);
> +		pathlen = tree_entry_len(&t2->entry);
> +		isdir = S_ISDIR(mode);
> +	}
> +	else {
> +		/* a path was removed - take path from parent. Also take
> +		 * mode from parent, to decide on recursion.
> +		 */
> +		tree_entry_extract(t1, &path, &mode);
> +		pathlen = tree_entry_len(&t1->entry);
> +
> +		isdir = S_ISDIR(mode);
> +		sha1 = NULL;
> +		mode = 0;
> +	}
> +
> +	if (DIFF_OPT_TST(opt, RECURSIVE) && isdir) {
> +		recurse = 1;
> +		emitthis = DIFF_OPT_TST(opt, TREE_IN_RECURSIVE);
> +	}
>  
>  	strbuf_add(base, path, pathlen);
> -	if (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode)) {
> -		if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE))
> -			opt->add_remove(opt, *prefix, mode, sha1, 1, base->buf, 0);
>  
> +	if (emitthis)
> +		emit_diff(opt, base, t1, t2);
> +
> +	if (recurse) {
>  		strbuf_addch(base, '/');
> -		diff_tree_sha1(*prefix == '-' ? sha1 : NULL,
> -			       *prefix == '+' ? sha1 : NULL, base->buf, opt);
> -	} else
> -		opt->add_remove(opt, prefix[0], mode, sha1, 1, base->buf, 0);
> +		diff_tree_sha1(t1 ? t1->entry.sha1 : NULL,
> +			       t2 ? t2->entry.sha1 : NULL, base->buf, opt);
> +	}


After this step, "sha1" is assigned but never gets used.  Please
double-check the fix-up I queued in the series before merging it to
'pu'.

Thanks.

Re: [PATCH 02/11] tree-diff: consolidate code for emitting diffs and recursion in one place

[Kirill Smelkov]

On Thu, Feb 13, 2014 at 09:43:27AM -0800, Junio C Hamano wrote:
> Kirill Smelkov <kirr@mns.spb.ru> writes:
> 
> > +static void show_path(struct strbuf *base, struct diff_options *opt,
> > +		      struct tree_desc *t1, struct tree_desc *t2)
> >  {
> >  	unsigned mode;
> >  	const char *path;
> > -	const unsigned char *sha1 = tree_entry_extract(desc, &path, &mode);
> > -	int pathlen = tree_entry_len(&desc->entry);
> > +	const unsigned char *sha1;
> > +	int pathlen;
> >  	int old_baselen = base->len;
> > +	int isdir, recurse = 0, emitthis = 1;
> > +
> > +	/* at least something has to be valid */
> > +	assert(t1 || t2);
> > +
> > +	if (t2) {
> > +		/* path present in resulting tree */
> > +		sha1 = tree_entry_extract(t2, &path, &mode);
> > +		pathlen = tree_entry_len(&t2->entry);
> > +		isdir = S_ISDIR(mode);
> > +	}
> > +	else {
> > +		/* a path was removed - take path from parent. Also take
> > +		 * mode from parent, to decide on recursion.
> > +		 */
> > +		tree_entry_extract(t1, &path, &mode);
> > +		pathlen = tree_entry_len(&t1->entry);
> > +
> > +		isdir = S_ISDIR(mode);
> > +		sha1 = NULL;
> > +		mode = 0;
> > +	}
> > +
> > +	if (DIFF_OPT_TST(opt, RECURSIVE) && isdir) {
> > +		recurse = 1;
> > +		emitthis = DIFF_OPT_TST(opt, TREE_IN_RECURSIVE);
> > +	}
> >  
> >  	strbuf_add(base, path, pathlen);
> > -	if (DIFF_OPT_TST(opt, RECURSIVE) && S_ISDIR(mode)) {
> > -		if (DIFF_OPT_TST(opt, TREE_IN_RECURSIVE))
> > -			opt->add_remove(opt, *prefix, mode, sha1, 1, base->buf, 0);
> >  
> > +	if (emitthis)
> > +		emit_diff(opt, base, t1, t2);
> > +
> > +	if (recurse) {
> >  		strbuf_addch(base, '/');
> > -		diff_tree_sha1(*prefix == '-' ? sha1 : NULL,
> > -			       *prefix == '+' ? sha1 : NULL, base->buf, opt);
> > -	} else
> > -		opt->add_remove(opt, prefix[0], mode, sha1, 1, base->buf, 0);
> > +		diff_tree_sha1(t1 ? t1->entry.sha1 : NULL,
> > +			       t2 ? t2->entry.sha1 : NULL, base->buf, opt);
> > +	}
> 
> 
> After this step, "sha1" is assigned but never gets used.  Please
> double-check the fix-up I queued in the series before merging it to
> 'pu'.

Your fixup is correct - it was my overlook when preparing the patch -
sha1 is needed for later patch (multiparent diff tree-walker), but I've
mistakenly left it here.

The two interesting patches I've sent you today, are already adjusted to
this correction - it is safe to squash the fixup in.

Thanks for noticing,
Kirill