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

[PATCH 2/6] Split out "exact content match" phase of rename detection

From
Linus Torvalds <torvalds@linux-foundation.org>
Date
Oct 25, 2007, 18:17 UTC
Message-ID
<alpine.LFD.0.999.0710251116570.30120@woody.linux-foundation.org>
In-Reply-To
<alpine.LFD.0.999.0710251112120.30120@woody.linux-foundation.org>
From: Linus Torvalds <torvalds@linux-foundation.org>
Subject: [PATCH 2/6] Split out "exact content match" phase of rename detection

This makes the exact content match a separate function of its own. Partly to cut down a bit on the size of the diffcore_rename() function (which is too complex as it is), and partly because there are smarter ways to do this than an O(m*n) loop over it all, and that function should be rewritten to take that into account.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
---

This is, I think, identical to the patch you already have. Feel free to skip this, and base the rest of the patch-series on your existing one.

 diffcore-rename.c |   90 +++++++++++++++++++++++++++++++++--------------------
 1 files changed, 56 insertions(+), 34 deletions(-)
diff --git a/diffcore-rename.c b/diffcore-rename.c
index 142e537..2077a9b 100644
--- a/diffcore-rename.c
+++ b/diffcore-rename.c
@@ -262,6 +262,58 @@ static int compute_stays(struct diff_queue_struct *q,
 	return 1;
 }
 
+/*
+ * Find exact renames first.
+ *
+ * The first round matches up the up-to-date entries,
+ * and then during the second round we try to match
+ * cache-dirty entries as well.
+ *
+ * Note: the rest of the rename logic depends on this
+ * phase also populating all the filespecs for any
+ * entry that isn't matched up with an exact rename,
+ * see "is_exact_match()".
+ */
+static int find_exact_renames(void)
+{
+	int rename_count = 0;
+	int contents_too;
+
+	for (contents_too = 0; contents_too < 2; contents_too++) {
+		int i;
+
+		for (i = 0; i < rename_dst_nr; i++) {
+			struct diff_filespec *two = rename_dst[i].two;
+			int j;
+
+			if (rename_dst[i].pair)
+				continue; /* dealt with an earlier round */
+			for (j = 0; j < rename_src_nr; j++) {
+				int k;
+				struct diff_filespec *one = rename_src[j].one;
+				if (!is_exact_match(one, two, contents_too))
+					continue;
+
+				/* see if there is a basename match, too */
+				for (k = j; k < rename_src_nr; k++) {
+					one = rename_src[k].one;
+					if (basename_same(one, two) &&
+						is_exact_match(one, two,
+							contents_too)) {
+						j = k;
+						break;
+					}
+				}
+
+				record_rename_pair(i, j, (int)MAX_SCORE);
+				rename_count++;
+				break; /* we are done with this entry */
+			}
+		}
+	}
+	return rename_count;
+}
+
 void diffcore_rename(struct diff_options *options)
 {
 	int detect_rename = options->detect_rename;
@@ -270,12 +322,11 @@ void diffcore_rename(struct diff_options *options)
 	struct diff_queue_struct *q = &diff_queued_diff;
 	struct diff_queue_struct outq;
 	struct diff_score *mx;
-	int i, j, rename_count, contents_too;
+	int i, j, rename_count;
 	int num_create, num_src, dst_cnt;
 
 	if (!minimum_score)
 		minimum_score = DEFAULT_RENAME_SCORE;
-	rename_count = 0;
 
 	for (i = 0; i < q->nr; i++) {
 		struct diff_filepair *p = q->queue[i];
@@ -318,40 +369,11 @@ void diffcore_rename(struct diff_options *options)
 	if (rename_dst_nr * rename_src_nr > rename_limit * rename_limit)
 		goto cleanup;
 
-	/* We really want to cull the candidates list early
+	/*
+	 * We really want to cull the candidates list early
 	 * with cheap tests in order to avoid doing deltas.
-	 * The first round matches up the up-to-date entries,
-	 * and then during the second round we try to match
-	 * cache-dirty entries as well.
 	 */
-	for (contents_too = 0; contents_too < 2; contents_too++) {
-		for (i = 0; i < rename_dst_nr; i++) {
-			struct diff_filespec *two = rename_dst[i].two;
-			if (rename_dst[i].pair)
-				continue; /* dealt with an earlier round */
-			for (j = 0; j < rename_src_nr; j++) {
-				int k;
-				struct diff_filespec *one = rename_src[j].one;
-				if (!is_exact_match(one, two, contents_too))
-					continue;
-
-				/* see if there is a basename match, too */
-				for (k = j; k < rename_src_nr; k++) {
-					one = rename_src[k].one;
-					if (basename_same(one, two) &&
-						is_exact_match(one, two,
-							contents_too)) {
-						j = k;
-						break;
-					}
-				}
-
-				record_rename_pair(i, j, (int)MAX_SCORE);
-				rename_count++;
-				break; /* we are done with this entry */
-			}
-		}
-	}
+	rename_count = find_exact_renames();
 
 	/* Have we run out the created file pool?  If so we can avoid
 	 * doing the delta matrix altogether.

-- 
1.5.3.4.330.g1dec6
Previous: Linus TorvaldsNext: Linus Torvalds
Message 3 of 18 in “Cleaned-up rename detection patch-series”
  1. 0/6 Cleaned-up rename detection patch-seriesLinus Torvalds, Oct 25, 2007
  2. 1/6 Add 'diffcore.h' to LIB_HLinus Torvalds, Oct 25, 2007
  3. 2/6 Split out "exact content match" phase of rename detectionLinus Torvalds, Oct 25, 2007
  4. 3/6 Ref-count the filespecs used by diffcoreLinus Torvalds, Oct 25, 2007
  5. 4/6 copy vs rename detection: avoid unnecessary O(n*m) loopsLinus Torvalds, Oct 25, 2007
  6. Junio C HamanoOct 26, 2007
  7. Linus TorvaldsOct 26, 2007
  8. Junio C HamanoOct 26, 2007
  9. Linus TorvaldsOct 26, 2007
  10. 5/6 Do linear-time/space rename logic for exact renamesLinus Torvalds, Oct 25, 2007
  11. Daniel BarkalowOct 25, 2007
  12. Jeff KingOct 25, 2007
  13. Daniel BarkalowOct 25, 2007
  14. Linus TorvaldsOct 25, 2007
  15. Daniel BarkalowOct 25, 2007
  16. 6/6 Do exact rename detection regardless of rename limitsLinus Torvalds, Oct 25, 2007
  17. Linus TorvaldsOct 25, 2007
  18. Jeff KingOct 25, 2007

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.