Subject: Re: [PATCH v2 14/19] tree-diff: rework diff_tree interface to be sha1 based

From: Junio C Hamano <[email-masked]>
Date: Mon, 24 Mar 2014 14:36:22 -0700

Kirill Smelkov <[email-masked]> writes:

> 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,

That would depend on how often the codepath triggered in your test
case, but is totally understandable.  It fires only when the path we
have been following disappears from the parent, and the processing
of try-to-follow itself is very compute-intensive (it needs to run
find-copies-harder logic) that will end up reading many subtrees of
the two initial trees; two more reading of tree objects will be
dwarfed by the actual processing.

> and which is outweighed cogently by the upsides.

> Changes since v1:
>
>  - don't need to touch diff.h, as diff_tree() became static.

Nice.  I wonder if it is an option to let the function keep its name
diff_tree() without renaming it to __diff_tree_whatever(), though.

>  tree-diff.c | 60 ++++++++++++++++++++++++++++--------------------------------
>  1 file changed, 28 insertions(+), 32 deletions(-)
>
> diff --git a/tree-diff.c b/tree-diff.c
> index b99622c..f90acf5 100644
> --- a/tree-diff.c
> +++ b/tree-diff.c
> @@ -137,12 +137,17 @@ static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,
>  	}
>  }
>  
> -static int diff_tree(struct tree_desc *t1, struct tree_desc *t2,
> -		     const char *base_str, struct diff_options *opt)
> +static 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);
>  
> @@ -155,39 +160,41 @@ static 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;
>  }
>  
> @@ -202,7 +209,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;
> @@ -240,7 +247,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);
>  
> @@ -301,23 +308,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;
>  }