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
Jonathan Nieder <jrnieder@gmail.com>
Date
Oct 5, 2010, 01:06 UTC
Message-ID
<20101005010620.GC9994@burratino>
In-Reply-To
<1286138529-6780-2-git-send-email-ydirson@altern.org>
Yann Dirson wrote:
> This feature tries to group together files moving from and to
> identical directories - the most common case being directory renames.
Intro for the uninitiated (e.g., me):
1. Entry point for the existing rename detection.

The entry point to diffcore's rename translator is diffcore_rename(), which is used, naturally enough, by diffcore_std() if and only if the detect_rename option is enabled.

2. Semantics of the existing rename detection.

When diffcore_std() is called, the caller has already queued up a nice list of files to diff (see Documentation/technical/api-diff.txt). The rename detection pass replaces the queue with a new list of filepairs that reflects the detected renames, guided by the detect_rename, rename_score, and rename_limit options.

3. Implementation of the existing rename detection.
 I.   find rename candidates (all files, if detecting copies; added and
       deleted files, if not)
 II.  find exact renames and copies
 III. for each target file not accounted for yet, find the best 4
       candidate source files
 IV.  record rename winners, in order from most to least similar pair
 V.   record copy winners, in order from most to least similar pair
 VI.  queue up results
4. Data maintained by the existing rename detection.
 rename_dst, a list of rename candidates from step I, sorted by name
 For each rename dest candidate: a filespec and a filepair.
  filepair::one		source filespec
  filepair::two		destination filespec
  filepair::score	similarity score
 rename_src, a list of rename candidates from step I, sorted by name
 For each rename source candidate: a filespec and a score
  filespec::rename_used	number of filespecs it's paired against
			(to distinguish renames from copies)
Show 12 quoted lines
> --- 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;
>  		}
>  		oldmode = ce->ce_mode;

Sane. diff-files and friends need to pass unchanged files to the diffcore lib when directory renames are being considered, just like they would with -C -C.

Otherwise, we cannot distinguish between
	a/1 stays
	a/2 stays
	a/3 stays
	a/4 stays
	...
	a/1000 stays
	a/1001 -> b/1001
	a/1002 -> b/1002
which is clearly not a directory rename, and
	a/1001 -> b/1001
	a/1002 -> b/1002
which sure looks like one.
Reference: v0.99~515 (Diff overhaul, adding the other half of copy
detection, 2005-05-21).
Show 8 quoted lines
> @@ -338,7 +339,8 @@ static int show_modified(struct rev_info *revs,
>  
>  	oldmode = old->ce_mode;
>  	if (mode == oldmode && !hashcmp(sha1, old->sha1) && !dirty_submodule &&
> -	    !DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER))
> +	    !DIFF_OPT_TST(&revs->diffopt, FIND_COPIES_HARDER) &&
> +	    !DIFF_OPT_TST(&revs->diffopt, DETECT_DIR_RENAMES))
>  		return 0;
The diff-index part.

Would we also need something like v1.6.4-rc0~45^2 (Avoid "diff-index --cached" optimization under --find-copies-harder, 2009-05-22) in order to grok unchanged subtrees, or is that taken care of some other way?

[...]
Show 8 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;

If we're looking for directory renames but not finding-copies-harder, then unmodified files, while interesting and deserving of dst entries, should not be considered candidates for tracing individual files.

Yes?  If so, maybe the less colorful
	unsigned rename_target_candidate:1;

would make that clearer (and more importantly, the new kind of dst entry should be mentioned in the commit log message).

Show 7 quoted lines
> @@ -49,9 +50,36 @@ static struct diff_rename_dst *locate_rename_dst(struct diff_filespec *two,
>  	rename_dst[first].two = alloc_filespec(two->path);
>  	fill_filespec(rename_dst[first].two, two->sha1, two->mode);
>  	rename_dst[first].pair = NULL;
> +	rename_dst[first].i_am_not_single = 0;
>  	return &(rename_dst[first]);
>  }
All new files are rename target candidates.
Show 15 quoted lines
>  
> +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);
prefixcmp?
Show 11 quoted lines
> +		if (!cmp)
> +			return dst;
> +		if (cmp < 0) {
> +			last = next;
> +			continue;
> +		}
> +		first = next+1;
> +	}
> +	/* not found */
> +	return NULL;
> +}

Hmm, so this is like locate_rename_dst(..., 0), except it matches prefixes. Result is a rename_dst entry within that directory (why not spend the time to find the first?).

Show 14 quoted lines
> +
>  /* Table of rename/copy src files */
>  static struct diff_rename_src {
>  	struct diff_filespec *one;
> @@ -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);
> +	}

Prevents the new feature from turning on --find-copies-harder in step II. Good.

Show 13 quoted lines
>  
>  	/* Find the renames */
>  	i = for_each_hash(&file_table, find_same_files);
> @@ -414,6 +445,180 @@ static void record_if_better(struct diff_score m[], struct diff_score *o)
>  		m[worst] = *o;
>  }
>  
> +struct diff_dir_rename {
> +	struct diff_filespec *one;
> +	struct diff_filespec *two;
> +	int discarded;
> +	struct diff_dir_rename* next;
> +};
A linked list of renamed directories.  What functions maintain it?
[...]
> +static const char* copy_dirname(char* dst, const char* src)
Discussed already.
[...]
Show 7 quoted lines
> +static struct diff_dir_rename* factorization_candidates = NULL;
> +static void diffcore_factorize_renames(void)
> +{
> +	char one_parent_path[PATH_MAX], two_parent_path[PATH_MAX];
> +	int i;
> +
> +	for (i = 0; i < rename_dst_nr; i++) {
For each rename target candidate: ...
Would it make sense to give the body of this loop its own function?
Show 5 quoted lines
> +		struct diff_dir_rename* seen;
> +
> +		// FIXME: what are those ?
> +		if (!rename_dst[i].pair)
> +			continue;

Genuine new files are not interesting to us (since they do not provide evidence about directory renames, postive or negative).

> +		// dummy renames used by copy detection
> +		if (!strcmp(rename_dst[i].pair->one->path, rename_dst[i].pair->two->path))
> +			continue;

Whether a file was copied is probably interesting to us, but the corresponding filepair isn't.

Show 7 quoted lines
> +
> +		copy_dirname(one_parent_path, rename_dst[i].pair->one->path);
> +		copy_dirname(two_parent_path, rename_dst[i].pair->two->path);
> +
> +		// simple rename with no directory change
> +		if (!strcmp(one_parent_path, two_parent_path))
> +			continue;
File renames within a flat directory are not interesting to us.
> +
> +		struct diff_filespec* one_parent = alloc_filespec(one_parent_path);
> +		fill_filespec(one_parent, null_sha1 /*FIXME*/, S_IFDIR);

Initialize a filespec, for use in filepairs in case the containing directories are a source/target pair. (?)

> +
> +		// After this commit, are there any files still under one_parent_path ?
> +		struct diff_rename_dst* one_leftover = locate_rename_dst_dir(one_parent);
> +		if (one_leftover) { // FIXME: should only be run if !seen
[...]
> +		}

A candidate for a separate function, no? The idea, if I understand it: too many unchanged files can disqualify a rename source.

> +
> +		// already considered ?
> +		for (seen=factorization_candidates; seen; seen = seen->next)
> +			if (!strcmp(seen->one->path, one_parent_path)) break;
Lookup.  A candidate for a separate function, I think.
Show 13 quoted lines
> +		if (!seen) {
> +			// record potential dir rename
> +			seen = xmalloc(sizeof(*seen));
> +			seen->one = one_parent;
> +			seen->two = alloc_filespec(two_parent_path);
> +			fill_filespec(seen->two, null_sha1 /*FIXME*/, S_IFDIR);
> +			seen->discarded = 0;
> +			seen->next = factorization_candidates;
> +			factorization_candidates = seen;
> +			fprintf(stderr, "[DBG] %s -> %s suggests possible rename from %s to %s\n",
> +				rename_dst[i].pair->one->path,
> +				rename_dst[i].pair->two->path,
> +				one_parent_path, two_parent_path);
Insertion.  Likewise.
> +			continue;
> +		}
> +		if (seen->discarded)
> +			continue;
One disqualification disqualifies a directory completely.
Show 6 quoted lines
> +		// check that seen entry matches this rename
> +		if (strcmp(two_parent_path, seen->two->path)) {
> +			fprintf(stderr, "[DBG] discarding dir %s from renames (split into %s and %s)\n",
> +				one_parent_path, two_parent_path, seen->two->path);
> +			seen->discarded = 1;
> +		}
If a directory split in two, it gets disqualified.  Ok.
Show 11 quoted lines
> +
> +		/* all checks ok, we keep that entry */
> +	}
> +
> +	return;
> +}
> +
>  void diffcore_rename(struct diff_options *options)
>  {
>  	int detect_rename = options->detect_rename;
> @@ -451,13 +656,22 @@ void diffcore_rename(struct diff_options *options)
[...]
Show 14 quoted lines
>  			if (detect_rename == DIFF_DETECT_COPY) {
>  				/*
>  				 * Increment the "rename_used" score by
>  				 * one, to indicate ourselves as a user.
>  				 */
>  				p->one->rename_used++;
>  				register_rename_src(p->one, p->score);
>  			}
> +			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;
... except when --find-copies-harder is being used, right?
So I suspect there needs to be a
	DIFF_OPT_TST(options, FIND_COPIES_HARDER)
somewhere around here.
Show 9 quoted lines
> @@ -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. */
>  
>  		m = &mx[dst_cnt * NUM_CANDIDATE_PER_DST];
>  		for (j = 0; j < NUM_CANDIDATE_PER_DST; j++)

Prevents the new feature from turning on --find-copies-harder in step III. Good.

Show 24 quoted lines
> @@ -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();
> +
>  	DIFF_QUEUE_CLEAR(&outq);
> +
> +	// Now turn non-discarded factorization_candidates into real renames
> +	struct diff_dir_rename* candidate;
> +	for (candidate=factorization_candidates; candidate; candidate = candidate->next) {
> +		struct diff_filepair* pair;
> +		if (candidate->discarded) continue;
> +		// visualize toplevel dir if needed - FIXME: wrong place for this ?
> +		if (!*candidate->one->path)
> +			candidate->one->path = "./";
> +		if (!*candidate->two->path)
> +			candidate->two->path = "./";
> +		pair = diff_queue(&outq, candidate->one, candidate->two);
> +		pair->score = MAX_SCORE;
> +		pair->renamed_pair = 1;
Outputting the discovered directory renames.
Show 18 quoted lines
> +	}
> +
>  	for (i = 0; i < q->nr; i++) {
>  		struct diff_filepair *p = q->queue[i];
>  		struct diff_filepair *pair_to_free = NULL;
> diff --git a/tree-diff.c b/tree-diff.c
> index cd659c6..ca0b84f 100644
> --- a/tree-diff.c
> +++ b/tree-diff.c
> @@ -49,7 +49,9 @@ static int compare_tree_entry(struct tree_desc *t1, struct tree_desc *t2, const
>  		show_entry(opt, "+", t2, base, baselen);
>  		return 1;
>  	}
> -	if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) && !hashcmp(sha1, sha2) && mode1 == mode2)
> +	if (!DIFF_OPT_TST(opt, FIND_COPIES_HARDER) &&
> +	    !DIFF_OPT_TST(opt, DETECT_DIR_RENAMES) &&
> +	    !hashcmp(sha1, sha2) && mode1 == mode2)
>  		return 0;
Right, makes sense.
Conclusions:
 - the basic idea looks sane
 - the main function would benefit a lot from being split up a bit
 - would be nice to have an overview of the design (especially, a
   quick description of the heuristics used) for the commit message
Looks promising, and a lot simpler than I feared. :)
Thanks.
Previous: Yann DirsonNext: Yann Dirson
Message 21 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.