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

Re: [PATCH v4 1/4] Introduce wholesame directory move detection in diffcore.

From
YDYann Dirson <ydirson@free.fr>
Date
Oct 4, 2010, 21:13 UTC
Message-ID
<20101004211359.GV4983@home.lan>
In-Reply-To
<20101004072850.GJ24884@burratino>
On Mon, Oct 04, 2010 at 02:28:50AM -0500, Jonathan Nieder wrote:
Show 6 quoted lines
> > of "mv a b" and "mv a/* b/" are displayed as "Rnnn a/ b/", which is
> > probably not what we want.  "Rnnn a/* b/" could be a good choice for
> > the latter if we want them to be distinguished, and even if we want
> > them to look the same.
> 
> Example?

It's just that every time we detect a bulk rename (of all files of a directory) it is currently shown as a directory rename, even if they all get moved into an existing dir. Technically, a "directory rename" (which I'd label "mv a b") is a special case of "bulk rename" (for which "mv a/* b/" is more correct), where the target directory is empty. Currently the distinction between the two is not done, but everything is incorrectly advertized as a rename. I shall fix that.

Show 6 quoted lines
> > Other future developements to be made on top of this include:
> > * extension of unified-diff format to express this
> [...]
> > ---
> 
> Oh, so this is for diff --raw only.

Right, but that TODO list has not be revised in this iteration. --detect-dir-renames does not need much to gain unified-diff, it is mostly --hide-dir-rename-details which needs thougth and work - but as it is now targetted at humans only, we can start with whatever seems adequate and rewrite/refine as see fit.

> For the confused: the discussion from v3 perhaps explains why.

Thanks for this work of putting everything into context - I should have done that myself.

Show 15 quoted lines
>  $ ./git-diff-tree --abbrev=6 ee491 --factorize-renames -r 
>  [DBG] possible rename from arm/ to bar/
>  [DBG] possible rename from ppc/ to moved/
>  [DBG] discarding dir rename of arm/, mixing moved/ and bar/
>  [DBG] ppc/* -> moved/* makes ppc/sha1ppc.S -> moved/sha1ppc.S uninteresting
>  [DBG] ppc/* -> moved/* makes ppc/sha1.c -> moved/sha1.c uninteresting
>  ee491a42190ec6e716f46a55fa0a7f4e307f1629
>  :040000 040000 000000... 000000... R100	ppc/	moved/
>  :100644 100644 9e3ae0... 9e3ae0... R100	arm/sha1.c	bar/sha1.c
>  :100644 100644 395264... 395264... R100	arm/sha1.h	bar/sha1.h
>  :100644 100644 c3c51a... c065ee... R099	ppc/sha1.h	moved/sha1.h
>  :100644 100644 8c1cb9... 8c1cb9... R100	arm/sha1_arm.S	moved/sha1_arm.S
> 
> Presumably this patch takes care of the first step (grouping potential
> full-directory moves) and not the second (hiding the redundant file renames).

No, it did hide the two moves labeled as "uninteresting" in the debug traces above. The ones left are one which is part of the dif rename but was also modified, and the other ones (from arm/) are part of a directory split (see 3rd debug line).

Show 18 quoted lines
> Naïve review:
> 
> > --- a/diff-lib.c
> > +++ b/diff-lib.c
> > @@ -208,7 +208,8 @@ int run_diff_files(struct rev_info *revs, unsigned int option)
> >  						    ce_option, &dirty_submodule);
> >  		if (!changed && !dirty_submodule) {
> >  			ce_mark_uptodate(ce);
> > -			if (!DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER))
> > +			if (!DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER) &&
> > +			    !DIFF_OPT_TST(&revs->diffopt, DETECT_DIR_RENAMES))
> >  				continue;
> 
> Hm, why?
> > @@ -338,7 +339,8 @@ static int show_modified(struct rev_info *revs,
> [...]
> 
> Likewise.

The code below that (calls to diff_change) was previously only used for FIND_COPIES_HARDER, but we also need to go there for DETECT_DIR_RENAMES. Removing those eg. make test "validate the output for a move without a subdir." fail. I admit I have not re-analyzed this part recently, those tests were already parts of the first iterations.

Show 11 quoted lines
> [...]
> > --- a/diffcore-rename.c
> > +++ b/diffcore-rename.c
> > @@ -11,6 +11,7 @@
> >  static struct diff_rename_dst {
> >  	struct diff_filespec *two;
> >  	struct diff_filepair *pair;
> > +	int i_am_not_single:1; // does not look for a match, only here to be looked at
> >  } *rename_dst;
> 
> What does single mean?
"looking for a match" :)
Show 14 quoted lines
> > @@ -451,13 +656,22 @@ void diffcore_rename(struct diff_options *options)
> >  				p->one->rename_used++;
> >  			register_rename_src(p->one, p->score);
> >  		}
> > +		else {
> [...]
> > +			if (DIFF_OPT_TST(options, DETECT_DIR_RENAMES)) {
> > +				/* similarly, rename factorization needs to
> > +				 * see all files from second tree, but we don't
> > +				 * want them to be matched against single sources.
> > +				 */
> > +				locate_rename_dst(p->two, 1)->i_am_not_single = 1;
> 
> Huh?
Show 15 quoted lines
> > @@ -386,8 +414,11 @@ static int find_exact_renames(void)
> >  	for (i = 0; i < rename_src_nr; i++)
> >  		insert_file_table(&file_table, -1, i, rename_src[i].one);
> >  
> > -	for (i = 0; i < rename_dst_nr; i++)
> > +	for (i = 0; i < rename_dst_nr; i++) {
> > +		if (rename_dst[i].i_am_not_single)
> > +			continue;
> >  		insert_file_table(&file_table, 1, i, rename_dst[i].two);
> > +	}
> 
> What is this code path for?  (Sorry for the tedious questions.  My
> thinking is, if I cannot answer them without doing some legwork, how
> could the person about to break your code who is only glancing for
> a moment before plunging forward on an exciting new feature?)

Those are definitely related to the above. This mimics the FIND_COPIES_HARDER behaviour (which is adding untouched files from *src* tree to the rename_dst list so the -C algorithm works): here we need to see all files from *dst* tree so we can tell if there was any file left in a dir after a move. This has a cost: we must ensure in other places that codepaths not intended for those extra files are ok.

Hm, thinking quickly about it, maybe we could use a separate list to store them, and only run through them when explicitely needed, that would cost less and avoid the polutions you pointed at. I shall have a look at that.

Show 31 quoted lines
> > @@ -49,9 +50,36 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,
> [...]
> >  
> > +static struct diff_rename_dst *locate_rename_dst_dir(struct diff_filespec *dir)
> > +{
> > +	/* code mostly duplicated from locate_rename_dst - not sure we
> > +	 * could merge them efficiently,though
> > +	 */
> > +	int first, last;
> > +	int prefixlength = strlen(dir->path);
> > +
> > +	first = 0;
> > +	last = rename_dst_nr;
> > +	while (last > first) {
> > +		int next = (last + first) >> 1;
> > +		struct diff_rename_dst *dst = &(rename_dst[next]);
> > +		int cmp = strncmp(dir->path, dst->two->path, prefixlength);
> > +		if (!cmp)
> > +			return dst;
> > +		if (cmp < 0) {
> > +			last = next;
> > +			continue;
> > +		}
> > +		first = next+1;
> > +	}
> > +	/* not found */
> > +	return NULL;
> > +}
> 
> Binary search --- this is just a way to index into the sorted list
> of rename_dsts, right?
right.
> At first I thought it was searching for a good rename destination.
> A comment (or overview in the log message) could help clarify.
Ok.  More comments are surely good in this hairy piece of code :)
Show 18 quoted lines
> > +// FIXME: prevent possible overflow
> > +/*
> > + * Copy dirname of src into dst, suitable to append a filename without
> > + * an additional "/".
> > + * Only handles relative paths since there is no absolute path in a git repo.
> > + * Writes "" when there is no "/" in src.
> > + * May overwrite more chars than really needed, if src ends with a "/".
> > + */
> > +static const char* copy_dirname(char* dst, const char* src)
> > +{
> > +	char* lastslash = strrchr(src, '/');
> > +	if (!lastslash) {
> > +		*dst = '\0';
> > +		return dst;
> > +	}
> > +	strncpy(dst, src, lastslash - src + 1);
> 
> memcpy?
right
Show 34 quoted lines
> > +	dst[lastslash - src + 1] = '\0';
> > +
> > +	// if src ends with a "/" strip the last component
> > +	if (lastslash[1] == '\0') {
> > +		lastslash = strrchr(dst, '/');
> > +		if (!lastslash)
> > +			return strcpy(dst, ".");
> > +		lastslash[1] = '\0';
> > +	}
> 
> It might be easier to read like this:
> 
> /* Write name of the parent directory of src to dest. */
> static char *remove_last_component(char *dst, const char *src)
> {
> 	size_t len = strlen(src);
> 	const char *slash;
> 
> 	if (len > 0 && src[len - 1] == '/')
> 		/* Trailing slash.  Ignore it. */
> 		len--;
> 
> 	slash = memrchr(src, '/', len);
> 	if (!slash) {
> 		*dst = '\0';
> 		return dst;
> 	}
> 
> 	*mempcpy(dst, src, slash - src) = '\0';
> 	return dst;
> }
> 
> Requires the glibc-specific function memrchr(), but that is easy to
> implement.  Compare strchrnul() [in git-compat-util.h].

Right, that's much more elegant - and should also be more efficient in the "ends with /" case.

Show 25 quoted lines
> [...]
> > +static struct diff_dir_rename* factorization_candidates = NULL;
> > +static void diffcore_factorize_renames(void)
> 
> Maybe this could be refactored into multiple functions?
> 
> > @@ -509,6 +723,8 @@ void diffcore_rename(struct diff_options *options)
> >  
> >  		if (rename_dst[i].pair)
> >  			continue; /* dealt with exact match already. */
> > +		if (rename_dst[i].i_am_not_single)
> > +			continue; /* not looking for a match. */
> 
> Oh, not single means "not seeking a new relationship".
> 
> > @@ -569,7 +785,28 @@ void diffcore_rename(struct diff_options *options)
> >  	/* At this point, we have found some renames and copies and they
> >  	 * are recorded in rename_dst.  The original list is still in *q.
> >  	 */
> > +
> > +	/* Now possibly factorize those renames and copies. */
> > +	if (DIFF_OPT_TST(options, DETECT_DIR_RENAMES))
> > +		diffcore_factorize_renames();
> 
> Huh?  Factorize?

"--factorize-renames" was how the single-option was called in the previous series. It has still not turned completely false, but sure using "bulk rename" would be easier to read.

> Looks like I'll need to read diffcore_factorize_renames() after all. :(
Hopefully that part is better commented :)
> Sorry, not much to say yet.  Hopefully some of that can be useful
> nonetheless.
Thanks for this review, that work is always useful.
Previous: Jonathan NiederNext: Jonathan Nieder
Message 20 of 25 in “Detection of directory renames”
  1. 0/4 Detection of directory renamesYann Dirson, Oct 3, 2010
  2. 1/4 Introduce wholesame directory move detection in diffcore.Yann Dirson, Oct 3, 2010
  3. 2/4 Add testcases for the --detect-dir-renames diffcore flag.Yann Dirson, Oct 3, 2010
  4. 3/4 Allow hiding renames of individual files involved in a directory rename.Yann Dirson, Oct 3, 2010
  5. 4/4 Add testcases for the --hide-dir-rename-details diffcore flag.Yann Dirson, Oct 3, 2010
  6. Sverre RabbelierOct 3, 2010
  7. Sverre RabbelierOct 3, 2010
  8. Junio C HamanoOct 3, 2010
  9. Sverre RabbelierOct 4, 2010
  10. Yann DirsonOct 4, 2010
  11. Ævar Arnfjörð BjarmasonOct 4, 2010
  12. Yann DirsonOct 4, 2010
  13. Jonathan NiederOct 4, 2010
  14. Yann DirsonOct 4, 2010
  15. Jonathan NiederOct 4, 2010
  16. Andreas EricssonOct 5, 2010
  17. Ævar Arnfjörð BjarmasonOct 4, 2010
  18. Yann DirsonOct 4, 2010
  19. Jonathan NiederOct 4, 2010
  20. Yann DirsonOct 4, 2010
  21. Jonathan NiederOct 5, 2010
  22. Yann DirsonOct 6, 2010
  23. Jonathan NiederOct 4, 2010
  24. Jonathan NiederOct 5, 2010
  25. Yann DirsonOct 6, 2010

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.