Skip to content

Commit 186334b

Browse files
amalloyError Prone Team
amalloy
authored and
Error Prone Team
committed
Apply replacements in forward order instead of reverse
This avoids quadratic re-copying, and also simplifies finding the first edited line. PiperOrigin-RevId: 439899685
1 parent 3498bb9 commit 186334b

2 files changed

Lines changed: 61 additions & 71 deletions

File tree

‎check_api/src/main/java/com/google/errorprone/fixes/AppliedFix.java‎

Lines changed: 53 additions & 71 deletions
Original file line numberDiff line numberDiff line change
@@ -18,17 +18,10 @@
1818

1919
import static com.google.common.base.Preconditions.checkArgument;
2020

21-
import com.google.common.base.Supplier;
22-
import com.google.common.base.Suppliers;
23-
import com.google.common.collect.ImmutableSortedMap;
21+
import com.google.common.collect.ImmutableSet;
22+
import com.google.common.collect.Iterables;
2423
import com.sun.tools.javac.tree.EndPosTable;
25-
import java.io.IOException;
26-
import java.io.LineNumberReader;
27-
import java.io.StringReader;
28-
import java.util.HashSet;
2924
import java.util.Set;
30-
import java.util.regex.Matcher;
31-
import java.util.regex.Pattern;
3225
import javax.annotation.Nullable;
3326

3427
/**
@@ -57,12 +50,10 @@ public boolean isRemoveLine() {
5750
public static class Applier {
5851
private final CharSequence source;
5952
private final EndPosTable endPositions;
60-
private final Supplier<ImmutableSortedMap<Integer, Integer>> lineOffsets;
6153

6254
public Applier(CharSequence source, EndPosTable endPositions) {
6355
this.source = source;
6456
this.endPositions = endPositions;
65-
this.lineOffsets = Suppliers.memoize(() -> lineOffsets(source.toString()));
6657
}
6758

6859
/**
@@ -71,86 +62,77 @@ public Applier(CharSequence source, EndPosTable endPositions) {
7162
*/
7263
@Nullable
7364
public AppliedFix apply(Fix suggestedFix) {
74-
StringBuilder replaced = new StringBuilder(source);
75-
76-
// We have to apply the replacements in descending order, since otherwise the positions in
77-
// subsequent replacements are invalidated by earlier replacements.
78-
Set<Replacement> replacements = descending(suggestedFix.getReplacements(endPositions));
65+
// We apply the replacements in ascending order here. Descending is simpler, since applying a
66+
// replacement can't change the index for future replacements, but it leads to quadratic
67+
// copying behavior as we constantly shift the tail of the file around in our StringBuilder.
68+
ImmutableSet<Replacement> replacements =
69+
ascending(suggestedFix.getReplacements(endPositions));
70+
if (replacements.isEmpty()) {
71+
return null;
72+
}
7973

80-
Set<Integer> modifiedLines = new HashSet<>();
74+
StringBuilder replaced = new StringBuilder();
75+
int positionInOriginal = 0;
8176
for (Replacement repl : replacements) {
8277
checkArgument(
8378
repl.endPosition() <= source.length(),
8479
"End [%s] should not exceed source length [%s]",
8580
repl.endPosition(),
8681
source.length());
87-
replaced.replace(repl.startPosition(), repl.endPosition(), repl.replaceWith());
88-
89-
// Find the line number(s) being modified
90-
modifiedLines.add(lineOffsets.get().floorEntry(repl.startPosition()).getValue());
91-
}
9282

93-
// Not sure this is really the right behavior, but otherwise we can end up with an infinite
94-
// loop below.
95-
if (modifiedLines.isEmpty()) {
96-
return null;
83+
// Write the unmodified content leading up to this change
84+
replaced.append(source, positionInOriginal, repl.startPosition());
85+
// And the modified content for this change
86+
replaced.append(repl.replaceWith());
87+
// Then skip everything from source between start and end
88+
positionInOriginal = repl.endPosition();
9789
}
90+
// Flush out any remaining content after the final change
91+
replaced.append(source, positionInOriginal, source.length());
9892

99-
LineNumberReader lineNumberReader =
100-
new LineNumberReader(new StringReader(replaced.toString()));
101-
String snippet = null;
102-
boolean isRemoveLine = false;
103-
try {
104-
while (!modifiedLines.contains(lineNumberReader.getLineNumber())) {
105-
lineNumberReader.readLine();
106-
}
107-
// TODO: this is over-simplified; need a failing test case
108-
snippet = lineNumberReader.readLine();
109-
if (snippet == null) {
110-
// The file's last line was removed.
111-
snippet = "";
112-
} else {
113-
snippet = snippet.trim();
114-
// snip comment from line
115-
if (snippet.contains("//")) {
116-
snippet = snippet.substring(0, snippet.indexOf("//")).trim();
117-
}
118-
}
119-
if (snippet.isEmpty()) {
120-
isRemoveLine = true;
121-
snippet = "to remove this line";
122-
}
123-
} catch (IOException e) {
124-
// impossible since source is in-memory
93+
// Find the changed line containing the first edit
94+
String snippet = firstEditedLine(replaced, Iterables.get(replacements, 0));
95+
if (snippet.isEmpty()) {
96+
return new AppliedFix("to remove this line", /* isRemoveLine= */ true);
12597
}
126-
return new AppliedFix(snippet, isRemoveLine);
98+
return new AppliedFix(snippet, /* isRemoveLine= */ false);
12799
}
128100

129101
/** Get the replacements in an appropriate order to apply correctly. */
130-
private static Set<Replacement> descending(Set<Replacement> set) {
102+
private static ImmutableSet<Replacement> ascending(Set<Replacement> set) {
131103
Replacements replacements = new Replacements();
132104
set.forEach(replacements::add);
133-
return replacements.descending();
105+
return replacements.ascending();
106+
}
107+
108+
/**
109+
* Finds the full text of the first line that's changed. In this case "line" means "bracketed by
110+
* \n characters". We don't handle \r\n specially, because the strings that javac provides to
111+
* Error Prone have already been transformed from platform line endings to newlines (and even if
112+
* it didn't, the dangling \r characters would be handled by a trim() call).
113+
*/
114+
private static String firstEditedLine(StringBuilder content, Replacement firstEdit) {
115+
// We subtract 1 here because we want to find the first newline *before* the edit, not one
116+
// at its beginning.
117+
int startOfFirstEditedLine = content.lastIndexOf("\n", firstEdit.startPosition() - 1);
118+
int endOfFirstEditedLine = content.indexOf("\n", firstEdit.startPosition());
119+
if (startOfFirstEditedLine == -1) {
120+
startOfFirstEditedLine = 0; // Change to start of file with no preceding newline
121+
}
122+
if (endOfFirstEditedLine == -1) {
123+
// Change to last line of file
124+
endOfFirstEditedLine = content.length();
125+
}
126+
String snippet = content.substring(startOfFirstEditedLine, endOfFirstEditedLine);
127+
snippet = snippet.trim();
128+
if (snippet.contains("//")) {
129+
snippet = snippet.substring(0, snippet.indexOf("//")).trim();
130+
}
131+
return snippet;
134132
}
135133
}
136134

137135
public static Applier fromSource(CharSequence source, EndPosTable endPositions) {
138136
return new Applier(source, endPositions);
139137
}
140-
141-
private static final Pattern NEWLINE = Pattern.compile("\\R");
142-
143-
/** Returns the start offsets of the lines in the input. */
144-
private static ImmutableSortedMap<Integer, Integer> lineOffsets(String input) {
145-
ImmutableSortedMap.Builder<Integer, Integer> lines = ImmutableSortedMap.naturalOrder();
146-
int line = 0;
147-
int idx = 0;
148-
lines.put(idx, line++);
149-
Matcher matcher = NEWLINE.matcher(input);
150-
while (matcher.find(idx)) {
151-
idx = matcher.end();
152-
lines.put(idx, line++);
153-
}
154-
return lines.buildOrThrow();
155-
}
156138
}

‎check_api/src/main/java/com/google/errorprone/fixes/Replacements.java‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@
2020

2121
import com.google.common.base.Joiner;
2222
import com.google.common.collect.ComparisonChain;
23+
import com.google.common.collect.ImmutableSet;
2324
import com.google.common.collect.Ordering;
2425
import com.google.common.collect.Range;
2526
import com.google.common.collect.RangeMap;
@@ -148,6 +149,13 @@ public Set<Replacement> descending() {
148149
return new LinkedHashSet<>(replacements.values());
149150
}
150151

152+
/** Non-overlapping replacements, sorted in ascending order by position. */
153+
public ImmutableSet<Replacement> ascending() {
154+
// TODO(amalloy): Encourage using this instead of descending()
155+
// Applying replacements in forward order is substantially more efficient, and only a bit harder
156+
return ImmutableSet.copyOf(replacements.descendingMap().values());
157+
}
158+
151159
public boolean isEmpty() {
152160
return replacements.isEmpty();
153161
}

0 commit comments

Comments
 (0)