Fallback to a single region for incorrect intra-line diffs
In some rare cases, intra-line diffs produce incorrect results, which
confuse users since the light/dark colors of added and removed areas do
not accurately represent what was added and deleted.
In this change, we add a safety check at the end of the intraline
computation by reconstructing the right text using the left text and the
list of edits. If this transformation doesn't match the right text, we
fallback to a single replace edit that covers the entire region.
We had a test in #RevisionDiffIT reproducing this bug. We adapt the test
to reflect the new behaviour.
Bug: Issue 13563
Change-Id: Ib6f300a21922339e8c564613df1cc5e7f8a685d3
diff --git a/java/com/google/gerrit/server/patch/IntraLineLoader.java b/java/com/google/gerrit/server/patch/IntraLineLoader.java
index 34ac3d8..29f5c2c 100644
--- a/java/com/google/gerrit/server/patch/IntraLineLoader.java
+++ b/java/com/google/gerrit/server/patch/IntraLineLoader.java
@@ -15,6 +15,7 @@
package com.google.gerrit.server.patch;
+import com.google.common.base.Supplier;
import com.google.common.base.Throwables;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
@@ -25,6 +26,7 @@
import com.google.inject.Inject;
import com.google.inject.assistedinject.Assisted;
import java.util.ArrayList;
+import java.util.Arrays;
import java.util.List;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
@@ -250,13 +252,70 @@
wordEdits.set(j, new Edit(ab, ae, bb, be));
}
- edits.set(i, new ReplaceEdit(e, wordEdits));
+ // Validate that the intra-line edits applied to the "a" text produces the "b" text. If this
+ // check fails, fallback to a single replace edit that covers the whole area.
+ if (isValidTransformation(a, b, wordEdits)) {
+ edits.set(i, new ReplaceEdit(e, wordEdits));
+ } else {
+ edits.set(i, new ReplaceEdit(e, Arrays.asList(new Edit(0, a.size(), 0, b.size()))));
+ }
}
}
return new IntraLineDiff(edits);
}
+ /**
+ * Validate that the application of the list of {@code edits} to the {@code lText} text produces
+ * the {@code rText} text.
+ *
+ * @return true if {@code lText} + {@code edits} results in the {@code rText} text, and false
+ * otherwise.
+ */
+ private static boolean isValidTransformation(CharText lText, CharText rText, List<Edit> edits) {
+ Supplier<String> applyDeleteAndReplaceEditsToLeft =
+ () -> {
+ StringBuilder reconstructed = toStringBuilder(lText);
+ String right = toStringBuilder(rText).toString();
+ // Process edits right to left to avoid re-computation of indices when characters are
+ // removed.
+ for (int i = edits.size() - 1; i >= 0; i--) {
+ Edit edit = edits.get(i);
+ if (edit.getType() == Edit.Type.REPLACE) {
+ reconstructed.replace(
+ edit.getBeginA(),
+ edit.getEndA(),
+ right.substring(edit.getBeginB(), edit.getEndB()));
+ } else if (edit.getType() == Edit.Type.DELETE) {
+ reconstructed.delete(edit.getBeginA(), edit.getEndA());
+ }
+ }
+ return reconstructed.toString();
+ };
+ Supplier<StringBuilder> removeInsertEditsFromRight =
+ () -> {
+ StringBuilder reconstructed = toStringBuilder(rText);
+ // Process edits right to left to avoid re-computation of indices when characters are
+ // removed.
+ for (int i = edits.size() - 1; i >= 0; i--) {
+ Edit edit = edits.get(i);
+ if (edit.getType() == Edit.Type.INSERT) {
+ reconstructed.delete(edit.getBeginB(), edit.getEndB());
+ }
+ }
+ return reconstructed;
+ };
+ return applyDeleteAndReplaceEditsToLeft.get().contentEquals(removeInsertEditsFromRight.get());
+ }
+
+ private static StringBuilder toStringBuilder(CharText text) {
+ StringBuilder result = new StringBuilder();
+ for (int i = 0; i < text.size(); i++) {
+ result.append(text.charAt(i));
+ }
+ return result;
+ }
+
private static void combineLineEdits(
List<Edit> edits, ImmutableSet<Edit> editsDueToRebase, Text a, Text b) {
for (int j = 0; j < edits.size() - 1; ) {
diff --git a/javatests/com/google/gerrit/acceptance/api/revision/RevisionDiffIT.java b/javatests/com/google/gerrit/acceptance/api/revision/RevisionDiffIT.java
index 5f3b702..bcd98d4 100644
--- a/javatests/com/google/gerrit/acceptance/api/revision/RevisionDiffIT.java
+++ b/javatests/com/google/gerrit/acceptance/api/revision/RevisionDiffIT.java
@@ -1019,9 +1019,9 @@
@Test
public void intralineEditsAreIdentified() throws Exception {
- // TODO(ghareeb): This test asserts the wrong behavior due to the following issue
- // bugs.chromium.org/p/gerrit/issues/detail?id=13563
- // Please remove this comment and assert the correct behavior when the bug is fixed.
+ // In some corner cases, intra-line diffs produce wrong results. In this case, the algorithm
+ // falls back to a single edit covering the whole range.
+ // See: bugs.chromium.org/p/gerrit/issues/detail?id=13563
assume().that(intraline).isTrue();
@@ -1032,10 +1032,10 @@
String previousPatchSetId = gApi.changes().id(changeId).get().currentRevision;
addModifiedPatchSet(changeId, FILE_NAME, fileContent -> fileContent.replace(orig, replace));
- // TODO(ghareeb): remove this comment when the issue is fixed.
- // The returned diff incorrectly contains:
+ // Intra-line logic wrongly produces
// replace [-9999{,99}99] with [-999{,}999].
- // If this replace edit is done, the resulting string incorrectly becomes [-9999,99].
+ // which if done, results in an incorrect [-9999,99].
+ // the intra-line algorithm detects this case and falls back to a single region edit.
DiffInfo diffInfo =
getDiffRequest(changeId, CURRENT, FILE_NAME).withBase(previousPatchSetId).get();
@@ -1044,8 +1044,7 @@
List<List<Integer>> editsB = diffInfo.content.get(1).editB;
String reconstructed = transformStringUsingEditList(orig, replace, editsA, editsB);
- // TODO(ghareeb): assert equals when the issue is fixed.
- assertThat(reconstructed).isNotEqualTo(replace);
+ assertThat(reconstructed).isEqualTo(replace);
}
@Test
