Re: [PATCH 12/19] tree-diff: remove special-case diff-emitting code for empty-tree cases
From: Junio C Hamano <hidden>
Date: 2016-06-15 23:00:26
Kirill Smelkov [off-list ref] writes:
via teaching tree_entry_pathcmp() how to compare empty tree descriptors:
Drop this line, as you explain the "pretend empty compares bigger than anything else" idea later anyway? This early part of the proposed log message made me hiccup while reading it.
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 */
Sounds good. I would have phrased a bit differently, though:
When we have T1 and T2, we return a sign that tells the caller
to indicate the "earlier" one to be emitted, and by returning
the sign that causes the non-empty side to be emitted, we will
automatically cause the entries from the remaining side to be
emitted, without attempting to touch the empty side at all. We
can teach tree_entry_pathcmp() to pretend that an empty tree has
an element that sorts after anything else to achieve this.
without saying "infinity".
Right now we never go to when compared tree descriptors are infinity,...
Sorry, but I cannot parse this.
as this condition is checked in the loop beginning as finishing criteria,
What condition and which loop? The loop that immediately surrounds
the callsite of tree_entry_pathcmp() is the infinite "for (;;) {" loop,
and after it prepares t1 and t2 by skipping paths outside pathspec,
we check if both are empty (i.e. we ran out). Is that the condition
you are referring to?
quoted hunk
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 <redacted> Signed-off-by: Junio C Hamano <redacted> --- ( re-posting without change ) tree-diff.c | 21 +++++++++------------ 1 file changed, 9 insertions(+), 12 deletions(-)diff --git a/tree-diff.c b/tree-diff.c index cf96ad7..2fd6d0e 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.
The basic idea is very sane. It is a nice (and obvious---once you are told about the trick) and clean restructuring of the code.
*/
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 < +∞ */Where do these "c" come from? I somehow feel that these comments are making it harder to understand what is going on.
quoted hunk
e1 = &t1->entry; e2 = &t2->entry; cmp = base_name_compare(e1->path, tree_entry_len(e1), e1->mode,@@ -151,18 +158,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);