[RFC PATCH] xdiff/xpatience: support anchoring a line

From

JTJonathan Tan <jonathantanmy@google.com>

Date

Nov 21, 2017, 22:17 UTC

Message-ID

<20171121221717.155301-1-jonathantanmy@google.com>

Signed-off-by: Jonathan Tan <jonathantanmy@google.com>
---
I'm sending this out to see if a change similar to this would be
welcome. It is useful to me as a reviewer (to check my own code, e.g.
when checking [1]). Probably more design needs to go into this,
including the best way to specify the "anchor" line, and the correct
behavior when the anchor is either not found or appears more than once.

Any thoughts?

[1]
https://public-inbox.org/git/20171121221256.154741-1-jonathantanmy@google.com/
---
 t/t4033-diff-patience.sh | 13 +++++++++++++
 xdiff/xpatience.c        | 29 +++++++++++++++++++++++++++--
 2 files changed, 40 insertions(+), 2 deletions(-)

diff --git a/t/t4033-diff-patience.sh b/t/t4033-diff-patience.sh
index 113304dc5..2147fd688 100755
--- a/t/t4033-diff-patience.sh
+++ b/t/t4033-diff-patience.sh
@@ -13,6 +13,19 @@ test_expect_success '--ignore-space-at-eol with a single appended character' '
 	grep "^+.*X" diff
 '
 
+test_expect_success 'anchor' '
+	printf "a\nb\nc\n" >pre &&
+	printf "c\na\nb\n" >post &&
+
+	# without anchor, c is moved
+	test_expect_code 1 git diff --no-index --patience pre post >diff &&
+	grep "^+c" diff &&
+
+	# with anchor, a is moved
+	DIFF_ANCHOR=c test_expect_code 1 git diff --no-index --patience pre post >diff &&
+	grep "^+a" diff
+'
+
 test_diff_frobnitz "patience"
 
 test_diff_unique "patience"
diff --git a/xdiff/xpatience.c b/xdiff/xpatience.c
index a44e77632..195a60e57 100644
--- a/xdiff/xpatience.c
+++ b/xdiff/xpatience.c
@@ -62,6 +62,8 @@ struct hashmap {
 		 * initially, "next" reflects only the order in file1.
 		 */
 		struct entry *next, *previous;
+
+		unsigned anchor : 1;
 	} *entries, *first, *last;
 	/* were common records found? */
 	unsigned long has_matches;
@@ -70,6 +72,14 @@ struct hashmap {
 	xpparam_t const *xpp;
 };
 
+static int is_anchor(const char *line)
+{
+	char *anchor = getenv("DIFF_ANCHOR");
+	if (!anchor)
+		return 0;
+	return !strncmp(line, anchor, strlen(anchor));
+}
+
 /* The argument "pass" is 1 for the first file, 2 for the second. */
 static void insert_record(int line, struct hashmap *map, int pass)
 {
@@ -110,6 +120,7 @@ static void insert_record(int line, struct hashmap *map, int pass)
 		return;
 	map->entries[index].line1 = line;
 	map->entries[index].hash = record->ha;
+	map->entries[index].anchor = is_anchor(map->env->xdf1.recs[line - 1]->ptr);
 	if (!map->first)
 		map->first = map->entries + index;
 	if (map->last) {
@@ -192,14 +203,28 @@ static struct entry *find_longest_common_sequence(struct hashmap *map)
 	int longest = 0, i;
 	struct entry *entry;
 
+	/*
+	 * If not -1, this entry in sequence must never be overridden. (Also,
+	 * do not override entries in sequence before this entry, since it is
+	 * useless.)
+	 */
+	int anchor_i = -1;
+
 	for (entry = map->first; entry; entry = entry->next) {
 		if (!entry->line2 || entry->line2 == NON_UNIQUE)
 			continue;
 		i = binary_search(sequence, longest, entry);
 		entry->previous = i < 0 ? NULL : sequence[i];
-		sequence[++i] = entry;
-		if (i == longest)
+		++i;
+		if (i <= anchor_i)
+			continue;
+		sequence[i] = entry;
+		if (anchor_i == -1 && entry->anchor) {
+			anchor_i = i;
+			longest = anchor_i + 1;
+		} else if (i == longest) {
 			longest++;
+		}
 	}
 
 	/* No common unique lines were found */

-- 
2.15.0.448.gf294e3d99a-goog