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

[PATCH v6.1] [RFC] Consider all parents of a file as candidates for bulk rename.

From
Yann Dirson <ydirson@altern.org>
Date
Oct 17, 2010, 19:24 UTC
Message-ID
<1287343443-23098-1-git-send-email-ydirson@altern.org>
In-Reply-To
<1287098999-9244-5-git-send-email-ydirson@altern.org>

We previously only looked at the immediate parents of a file involved in a move. Now consider upper ones as candidates too.

The way it is done here is somewhat inefficient, but at least it handles all previously-known cases of incorrectness.

Signed-off-by: Yann Dirson <ydirson@free.fr>
---
 diffcore-rename.c |  120 ++++++++++++++++++++++++++++-------------------------
 1 files changed, 63 insertions(+), 57 deletions(-)

There was a major flaw in the first iteration of this patch (never looking again at discarded renames). This iteration also adds more explicit comments about why this piece of code should work, despite having been written late at night and having already shown one problem which demonstrated that a testsuite is no replacement for a good night of sleep :)

I'm still not happy with the thing, though - the loops can surely be made shorter by using the discarded flags previously set, and more importantly we need to consider moves to parents of the file's destination too, which will add a loop of its own which will have to be made as short as possible. All of this seems to require to sort bulkmove_candidates so we can binary-search into it and rapidly access related paths.

Other opinions on the spirit of this patch still gladly welcome :)
diff --git a/diffcore-rename.c b/diffcore-rename.c
index 1be1af1..a8f3a8b 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -542,7 +542,7 @@ static int maybe_disqualify_bulkmove(const char* one_parent_path,
 		if (strncmp(rename_dst[j].two->path,
 			    one_parent_path, onep_len))
 			break; /* exhausted directory in this direction */
-		fprintf(stderr, "[DBG] leftover file %s in %s\n",
+		fprintf(stderr, "[DBG] leftover file %s in '%s'\n",
 			rename_dst[j].two->path, one_parent_path);
 		if (rename_dst[j].i_am_not_single || /* those were already here */
 		    (rename_dst[j].pair &&
@@ -596,66 +596,72 @@ static void check_one_bulk_move(struct diff_filepair *dstpair)
 	    maybe_disqualify_bulkmove(one_parent_path, one_leftover))
 		return;
 
-	fprintf(stderr, "[] %s -> %s ?\n",dstpair->one->path, dstpair->two->path);
-
-	// FIXME: loop over successive prefixes
-	unsigned needs_adding = 1;
+	fprintf(stderr, "[] %s -> %s ?\n", dstpair->one->path, dstpair->two->path);
 
-	/* already considered ? */
-	for (seen=bulkmove_candidates; seen; seen = seen->next) {
-		if (seen->discarded) {
-			/* already seen a rename from seen->one to some than ->two */
-			needs_adding = 0;
-			continue;
-		}
-		/* check exact dir */
-		if (!strcmp(seen->one->path, one_parent_path)) {
-			/* already added */
-			needs_adding = 0;
-			/* check that seen entry matches this rename */
-			if (strcmp(two_parent_path, seen->two->path)) {
-				fprintf(stderr, "[DBG] discarding dir %s from bulk moves (split into %s and %s)\n",
-					seen->one->path, two_parent_path, seen->two->path);
-				// FIXME: may be worth to free it instead
-				seen->discarded = 1;
+	/* loop up one_parent_path over successive parents */
+	// FIXME: also loop over two_parent_path prefixes ?
+	// FIXME: use a more informative prefixcmp to avoid strcmp calls
+	do {
+		unsigned needs_adding = 1;
+
+		fprintf(stderr, "[[]] %s ...\n", one_parent_path);
+
+		/* already considered ? */
+		for (seen=bulkmove_candidates; seen; seen = seen->next) {
+			fprintf(stderr, "[DBG]  ? %s -> %s\n", seen->one->path, seen->two->path);
+			/* subdir of "seen" source dir ? */
+			if (!prefixcmp(one_parent_path, seen->one->path)) {
+				/* subdir of "seen" dest dir ? */
+				if (!prefixcmp(two_parent_path, seen->two->path)) {
+					if (!strcmp(seen->one->path, one_parent_path) &&
+					    !strcmp(seen->two->path, two_parent_path)) {
+						/* already added */
+						fprintf(stderr, "[DBG]  already added\n");
+						needs_adding = 0;
+					} else /* is in a subdir: confirms but still
+						* may need adding */
+						fprintf(stderr, "[DBG]  'dstpair' conforts 'seen'\n");
+				} else {
+					fprintf(stderr, "[DBG] discarding %s -> %s from bulk moves (split into %s and %s)\n",
+						seen->one->path, seen->two->path,
+						two_parent_path, seen->two->path);
+					seen->discarded = 1;
+					/* Need to discard dstpair as well, unless moving
+					 * from a strict subdir of seen->one or to a
+					 * strict subdir of seen->two */
+					if (!strcmp(seen->one->path, one_parent_path) &&
+					    prefixcmp(seen->two->path, two_parent_path)) {
+						fprintf(stderr, "[DBG] ... and not adding self\n");
+						needs_adding = 0;
+					}
+					continue;
+				}
 			}
-			continue;
+			else fprintf(stderr, "[DBG]  %s outside of %s\n",
+				     one_parent_path, seen->one->path);
+
+			/* dstpair confirms seen, or does not infirm */
+			fprintf(stderr, "[DBG] %s -> %s DOES NOT cause discard of %s -> %s\n",
+				dstpair->one->path, dstpair->two->path,
+				seen->one->path, seen->two->path);
 		}
-		if (!prefixcmp(one_parent_path, seen->one->path)) {
-			if (prefixcmp(two_parent_path, seen->two->path)) {
-				fprintf(stderr, "[DBG] discarding dir %s from bulk moves (split into %s and %s)\n",
-					seen->one->path, two_parent_path, seen->two->path);
-				// FIXME: may be worth to free it instead
-				seen->discarded = 1;
-				continue;
-			}
-		} else {
-			fprintf(stderr, "[DBG]  %s considered irrelevant for %s -> %s\n",
-				dstpair->one->path, seen->one->path, seen->two->path);
-			continue;
+		if (needs_adding) { /* record potential dir rename */
+			seen = xmalloc(sizeof(*seen));
+			seen->one = alloc_filespec(one_parent_path);
+			fill_filespec(seen->one, null_sha1, S_IFDIR);
+			seen->two = alloc_filespec(two_parent_path);
+			fill_filespec(seen->two, null_sha1, S_IFDIR);
+			seen->discarded = 0;
+			seen->next = bulkmove_candidates;
+			bulkmove_candidates = seen;
+			fprintf(stderr, "[DBG] %s -> %s suggests possible bulk move from %s to %s\n",
+				dstpair->one->path,
+				dstpair->two->path,
+				one_parent_path, two_parent_path);
 		}
-
-		/* dstpair confirms seen */
-		fprintf(stderr, "[DBG] %s -> %s DOES NOT cause discard of %s -> %s\n",
-			dstpair->one->path, dstpair->two->path,
-			seen->one->path, seen->two->path);
-	}
-	if (needs_adding) { /* record potential dir rename */
-		/* all checks ok, we keep that entry */
-		seen = xmalloc(sizeof(*seen));
-		seen->one = alloc_filespec(one_parent_path);
-		fill_filespec(seen->one, null_sha1, S_IFDIR);
-		seen->two = alloc_filespec(two_parent_path);
-		fill_filespec(seen->two, null_sha1, S_IFDIR);
-		seen->discarded = 0;
-		seen->next = bulkmove_candidates;
-		bulkmove_candidates = seen;
-		fprintf(stderr, "[DBG] %s -> %s suggests possible bulk move from %s to %s\n",
-			dstpair->one->path,
-			dstpair->two->path,
-			one_parent_path, two_parent_path);
-		return;
-	}
+		/* next parent if any */
+		copy_dirname(one_parent_path, one_parent_path);
+	} while (*one_parent_path);
 }
 
 /*

-- 
1.7.2.3
Previous: Yann DirsonNext: Jonathan Nieder
Message 7 of 17 in “Detection of directory renames”
  1. 0/5 Detection of directory renamesYann Dirson, Oct 14, 2010
  2. 1/5 Introduce bulk-move detection in diffcore.Yann Dirson, Oct 14, 2010
  3. 2/5 Add testcases for the --detect-bulk-moves diffcore flag.Yann Dirson, Oct 14, 2010
  4. 3/5 [RFC] Handle the simpler case of a subdir invalidating bulk move.Yann Dirson, Oct 14, 2010
  5. 4/5 [RFC] Consider all parents of a file as candidates for bulk rename.Yann Dirson, Oct 14, 2010
  6. 5/5 [WIP] Allow hiding renames of individual files involved in a directory rename.Yann Dirson, Oct 14, 2010
  7. [RFC] Consider all parents of a file as candidates for bulk rename.Yann Dirson, Oct 17, 2010
  8. compat: add memrchr()Jonathan Nieder, Oct 15, 2010
  9. Ævar Arnfjörð BjarmasonOct 15, 2010
  10. Jonathan NiederOct 15, 2010
  11. Ævar Arnfjörð BjarmasonOct 15, 2010
  12. Junio C HamanoOct 15, 2010
  13. Johannes SixtOct 15, 2010
  14. Ludvig StrigeusOct 15, 2010
  15. compat: add memrchr()Jonathan Nieder, Oct 15, 2010
  16. Erik Faye-LundOct 15, 2010
  17. Johannes SixtOct 15, 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.