Line data Source code
1 : // Copyright (C) 2019 The Android Open Source Project
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 :
15 : package com.google.gerrit.server.fixes;
16 :
17 : import static java.nio.charset.StandardCharsets.UTF_8;
18 :
19 : import com.google.common.collect.ImmutableList;
20 : import com.google.gerrit.entities.Comment;
21 : import com.google.gerrit.entities.FixReplacement;
22 : import com.google.gerrit.extensions.restapi.ResourceConflictException;
23 : import com.google.gerrit.jgit.diff.ReplaceEdit;
24 : import com.google.gerrit.server.patch.Text;
25 : import java.util.ArrayList;
26 : import java.util.Comparator;
27 : import java.util.List;
28 : import org.eclipse.jgit.diff.Edit;
29 :
30 : /**
31 : * Produces final version of an input content with all fixes applied together with list of edits.
32 : */
33 : public class FixCalculator {
34 5 : private static final Comparator<FixReplacement> ASC_RANGE_FIX_REPLACEMENT_COMPARATOR =
35 5 : Comparator.comparing(fixReplacement -> fixReplacement.range);
36 :
37 : private FixCalculator() {}
38 :
39 : /**
40 : * Returns a result of applying fixes to an original content.
41 : *
42 : * @param originalContent is a text to which fixes must be applied
43 : * @param fixReplacements is a list of fixes to be applied
44 : * @throws ResourceConflictException if the fixReplacements contains invalid data (for example, if
45 : * an item points to an invalid range or if some ranges are intersected).
46 : */
47 : public static String getNewFileContent(
48 : String originalContent, List<FixReplacement> fixReplacements)
49 : throws ResourceConflictException {
50 4 : FixResult fixResult = calculateFix(new Text(originalContent.getBytes(UTF_8)), fixReplacements);
51 4 : return fixResult.text.getString(0, fixResult.text.size(), false);
52 : }
53 :
54 : /**
55 : * Returns a result of applying fixes to an original content and list of applied edits.
56 : *
57 : * @param originalText is a text to which fixes must be applied
58 : * @param fixReplacements is a list of fixes to be applied
59 : * @return {@link FixResult}
60 : * @throws ResourceConflictException if the fixReplacements contains invalid data (for example, if
61 : * an item points to an invalid range or if some ranges are intersected).
62 : */
63 : public static FixResult calculateFix(Text originalText, List<FixReplacement> fixReplacements)
64 : throws ResourceConflictException {
65 5 : List<FixReplacement> sortedReplacements = new ArrayList<>(fixReplacements);
66 5 : sortedReplacements.sort(ASC_RANGE_FIX_REPLACEMENT_COMPARATOR);
67 5 : if (!sortedReplacements.isEmpty() && sortedReplacements.get(0).range.startLine <= 0) {
68 1 : throw new ResourceConflictException(
69 1 : String.format(
70 : "Cannot calculate fix replacement for range %s",
71 1 : toString(sortedReplacements.get(0).range)));
72 : }
73 5 : ContentBuilder builder = new ContentBuilder(originalText);
74 5 : for (FixReplacement fixReplacement : sortedReplacements) {
75 : try {
76 5 : builder.addReplacement(fixReplacement);
77 2 : } catch (IndexOutOfBoundsException e) {
78 2 : throw new ResourceConflictException(
79 2 : String.format(
80 2 : "Cannot calculate fix replacement for range %s", toString(fixReplacement.range)),
81 : e);
82 5 : }
83 5 : }
84 5 : return builder.build();
85 : }
86 :
87 : private static String toString(Comment.Range range) {
88 2 : return String.format(
89 2 : "(%s:%s - %s:%s)", range.startLine, range.startChar, range.endLine, range.endChar);
90 : }
91 : /*
92 : Algorithm:
93 : Input:
94 : Original text (aka srcText)
95 : Sorted list of replacements in ascending order, where each replacement has:
96 : srcRange - part of the original text to be
97 : replaced, inserted or deleted (see {@link Comment.Range} for details)
98 : replacement - text to be set instead of srcRange
99 : Replacement ranges must not intersect.
100 :
101 : Output:
102 : Final text (aka finalText)
103 : List of Edit, where each Edit is an instance of {@link ReplaceEdit}
104 : Each ReplaceEdit cover one or more lines in the original text
105 : Each ReplaceEdit contains one or more Edit for intraline edits
106 : See {@link ReplaceEdit} and {@link Edit} for details.
107 : *
108 : Note: The algorithm is implemented in this way to avoid string.replace operations.
109 : It has complexity O(len(replacements) + max(len(originalText), len(finalText)) )
110 :
111 : Main steps:
112 : - set srcPos to start of the original text. It is like a cursor position in the original text.
113 : - set dstPos to start of the final text. It is like a cursor position in the final text.
114 : - the finalText initially empty
115 :
116 : - for each replacement:
117 : - append text between a previous and a current replacement to the finalText
118 : (because replacements were sorted, this part of text can't be changed by
119 : following replacements). I.e. append substring of srcText between srcPos
120 : and replacement.srcRange.start to the finalText
121 : Update srcPos and dstPos - set them at the end of appended text
122 : (i.e. srcPos points to the position before replacement.srcRange.start,
123 : dstPos points to the position where replacement.text should be inserted)
124 : - set dstReplacementStart = dstPos
125 : - append replacement.text to the finalText.
126 : Update srcPos and dstPos accordingly (i.e. srcPos points to the position after
127 : replacement.srcRange, dstPos points to the position in the finalText after
128 : the appended replacement.text).
129 : - set dstReplacementEnd = dstPos
130 : - dstRange = (dstReplacementStart, dstReplacementEnd) - is the range in the finalText.
131 : - srcRange = (replacement.Start, replacement.End) - is the range in the original text *
132 :
133 : - If previously created ReplaceEdit ends on the same or previous line as srcRange.startLine,
134 : then intraline edit is added to it (and ReplaceEdit endLine must be updated if needed);
135 : srcRange and dstRange together is used to calculate intraline Edit
136 : otherwise
137 : create new ReplaceEdit and add intraline Edit to it
138 : srcRange and dstRange together is used to calculate intraline Edit
139 :
140 : - append text after the last replacements,
141 : i.e. add part of srcText after srcPos to the finalText
142 :
143 : - Return the finalText and all created ReplaceEdits
144 :
145 : Implementation notes:
146 : 1) The intraline Edits inside ReplaceEdit stores positions relative to ReplaceEdit start.
147 : 2) srcPos and dstPos tracks current position as 3 numbers:
148 : - line number
149 : - column number
150 : - textPos - absolute position from the start of the text. The textPos is used to calculate
151 : relative positions of Edit inside ReplaceEdit
152 : */
153 : private static class ContentBuilder {
154 : private static class FixRegion {
155 : int startSrcLine;
156 : int startDstLine;
157 : int startSrcPos;
158 : int startDstPos;
159 : List<Edit> internalEdits;
160 :
161 5 : FixRegion() {
162 5 : this.internalEdits = new ArrayList<>();
163 5 : }
164 : }
165 :
166 : private final ContentProcessor contentProcessor;
167 : final ImmutableList.Builder<Edit> edits;
168 : FixRegion currentRegion;
169 :
170 5 : ContentBuilder(Text src) {
171 5 : this.contentProcessor = new ContentProcessor(src);
172 5 : this.edits = new ImmutableList.Builder<>();
173 5 : }
174 :
175 : void addReplacement(FixReplacement replacement) {
176 5 : if (shouldStartNewEdit(replacement)) {
177 5 : finishExistingEdit();
178 : }
179 : // processSrcContent expects that line number is 0-based,
180 : // but replacement.range.startLine is 1-based, so subtract 1
181 5 : processSrcContent(replacement.range.startLine - 1, replacement.range.startChar, true);
182 5 : processReplacement(replacement);
183 5 : }
184 :
185 : Text getNewText() {
186 5 : return new Text(contentProcessor.sb.toString().getBytes(UTF_8));
187 : }
188 :
189 : void finish() {
190 5 : finishExistingEdit();
191 5 : if (contentProcessor.hasMoreLines()) {
192 4 : contentProcessor.appendLinesToEndOfContent();
193 : }
194 5 : }
195 :
196 : public FixResult build() {
197 5 : finish();
198 5 : return new FixResult(edits.build(), this.getNewText());
199 : }
200 :
201 : private void finishExistingEdit() {
202 5 : if (contentProcessor.srcPosition.column > 0 || contentProcessor.dstPosition.column > 0) {
203 5 : contentProcessor.processToEndOfLine(true);
204 : }
205 5 : if (currentRegion != null) {
206 5 : int endSrc = contentProcessor.srcPosition.line;
207 5 : if (contentProcessor.srcPosition.column > 0) {
208 4 : endSrc++;
209 : }
210 5 : int endDst = contentProcessor.dstPosition.line;
211 5 : if (contentProcessor.dstPosition.column > 0) {
212 2 : endDst++;
213 : }
214 5 : ReplaceEdit edit =
215 : new ReplaceEdit(
216 : currentRegion.startSrcLine,
217 : endSrc,
218 : currentRegion.startDstLine,
219 : endDst,
220 : currentRegion.internalEdits);
221 5 : currentRegion = null;
222 5 : edits.add(edit);
223 : }
224 5 : }
225 :
226 : private boolean shouldStartNewEdit(FixReplacement replacement) {
227 5 : if (currentRegion == null) {
228 5 : return true;
229 : }
230 : // New edit must be started if there is at least one unchanged line after the last edit
231 : // Subtract 1 from replacement.range.startLine because it is a 1-based line number,
232 : // and contentProcessor.srcPosition.line is a 0-based line number
233 3 : return replacement.range.startLine - 1 > contentProcessor.srcPosition.line + 1;
234 : }
235 :
236 : private void processSrcContent(int toLine, int toColumn, boolean append)
237 : throws IndexOutOfBoundsException {
238 : // toLine >= currentSrcLineIndex
239 5 : if (toLine == contentProcessor.srcPosition.line) {
240 5 : contentProcessor.processLineToColumn(toColumn, append);
241 : } else {
242 4 : contentProcessor.processToEndOfLine(append);
243 4 : contentProcessor.processMultiline(toLine, append);
244 4 : contentProcessor.processLineToColumn(toColumn, append);
245 : }
246 5 : }
247 :
248 : private void processReplacement(FixReplacement fix) {
249 5 : if (currentRegion == null) {
250 5 : currentRegion = new FixRegion();
251 5 : currentRegion.startSrcLine = contentProcessor.srcPosition.line;
252 5 : currentRegion.startSrcPos = contentProcessor.srcPosition.getLineStartPos();
253 5 : currentRegion.startDstLine = contentProcessor.dstPosition.line;
254 5 : currentRegion.startDstPos = contentProcessor.dstPosition.getLineStartPos();
255 : }
256 5 : int srcStartPos = contentProcessor.srcPosition.textPos;
257 5 : int dstStartPos = contentProcessor.dstPosition.textPos;
258 5 : contentProcessor.appendReplacement(fix.replacement);
259 5 : processSrcContent(fix.range.endLine - 1, fix.range.endChar, false);
260 :
261 5 : currentRegion.internalEdits.add(
262 : new Edit(
263 : srcStartPos - currentRegion.startSrcPos,
264 : contentProcessor.srcPosition.textPos - currentRegion.startSrcPos,
265 : dstStartPos - currentRegion.startDstPos,
266 : contentProcessor.dstPosition.textPos - currentRegion.startDstPos));
267 5 : }
268 : }
269 :
270 : private static class ContentProcessor {
271 5 : static class ContentPosition {
272 : int line;
273 : int column;
274 : int textPos;
275 :
276 : void appendMultilineContent(int lineCount, int charCount) {
277 4 : line += lineCount;
278 4 : column = 0;
279 4 : textPos += charCount;
280 4 : }
281 :
282 : void appendLineEndedWithEOLMark(int charCount) {
283 4 : textPos += charCount;
284 4 : line++;
285 4 : column = 0;
286 4 : }
287 :
288 : void appendStringWithoutEOLMark(int charCount) {
289 5 : textPos += charCount;
290 5 : column += charCount;
291 5 : }
292 :
293 : int getLineStartPos() {
294 5 : return textPos - column;
295 : }
296 : }
297 :
298 : private final StringBuilder sb;
299 : final ContentPosition srcPosition;
300 : final ContentPosition dstPosition;
301 : String currentSrcLine;
302 : Text src;
303 : boolean endOfSource;
304 :
305 5 : ContentProcessor(Text src) {
306 5 : this.src = src;
307 5 : sb = new StringBuilder(src.size());
308 5 : srcPosition = new ContentPosition();
309 5 : dstPosition = new ContentPosition();
310 5 : endOfSource = src.size() == 0;
311 5 : }
312 :
313 : void processMultiline(int toLine, boolean append) {
314 4 : if (endOfSource || toLine <= srcPosition.line) {
315 4 : return;
316 : }
317 4 : int fromLine = srcPosition.line;
318 4 : String lines = src.getString(fromLine, toLine, false);
319 4 : int lineCount = toLine - fromLine;
320 4 : int charCount = lines.length();
321 4 : srcPosition.appendMultilineContent(lineCount, charCount);
322 :
323 4 : if (append) {
324 4 : sb.append(lines);
325 4 : dstPosition.appendMultilineContent(lineCount, charCount);
326 : }
327 4 : currentSrcLine = null;
328 4 : endOfSource = srcPosition.line >= src.size();
329 4 : }
330 :
331 : void processToEndOfLine(boolean append) {
332 5 : if (endOfSource) {
333 1 : return;
334 : }
335 5 : String srcLine = getCurrentSrcLine();
336 5 : int from = srcPosition.column;
337 5 : int charCount = srcLine.length() - from;
338 5 : boolean lastLineNoEOLMark = srcPosition.line >= src.size() - 1 && src.isMissingNewlineAtEnd();
339 5 : if (!lastLineNoEOLMark) {
340 4 : srcPosition.appendLineEndedWithEOLMark(charCount);
341 4 : endOfSource = srcPosition.line >= src.size();
342 : } else {
343 4 : srcPosition.appendStringWithoutEOLMark(charCount);
344 4 : endOfSource = true;
345 : }
346 5 : if (append) {
347 5 : sb.append(srcLine, from, srcLine.length());
348 5 : if (!lastLineNoEOLMark) {
349 4 : dstPosition.appendLineEndedWithEOLMark(charCount);
350 : } else {
351 4 : dstPosition.appendStringWithoutEOLMark(charCount);
352 : }
353 : }
354 5 : currentSrcLine = null;
355 5 : }
356 :
357 : void processLineToColumn(int to, boolean append) throws IndexOutOfBoundsException {
358 5 : int from = srcPosition.column;
359 5 : if (from > to) {
360 2 : throw new IndexOutOfBoundsException(
361 2 : String.format("The parameter from is greater than to. from: %d, to: %d", from, to));
362 : }
363 5 : if (to == 0) {
364 4 : return;
365 : }
366 5 : String srcLine = getCurrentSrcLine();
367 5 : if (to > srcLine.length()) {
368 0 : throw new IndexOutOfBoundsException("Parameter to is out of string");
369 5 : } else if (to == srcLine.length()) {
370 3 : if (srcPosition.line < src.size() - 1 || !src.isMissingNewlineAtEnd()) {
371 1 : throw new IndexOutOfBoundsException("The processLineToColumn shouldn't add end of line");
372 : }
373 : }
374 5 : int charCount = to - from;
375 5 : srcPosition.appendStringWithoutEOLMark(charCount);
376 5 : if (append) {
377 5 : sb.append(srcLine, from, to);
378 5 : dstPosition.appendStringWithoutEOLMark(charCount);
379 : }
380 5 : }
381 :
382 : void appendLinesToEndOfContent() {
383 4 : processMultiline(src.size(), true);
384 4 : }
385 :
386 : void appendReplacement(String replacement) {
387 5 : if (replacement.length() == 0) {
388 1 : return;
389 : }
390 5 : sb.append(replacement);
391 5 : int lastNewLinePos = -1;
392 5 : int newLineMarkCount = 0;
393 : while (true) {
394 5 : int index = replacement.indexOf('\n', lastNewLinePos + 1);
395 5 : if (index < 0) {
396 5 : break;
397 : }
398 4 : lastNewLinePos = index;
399 4 : newLineMarkCount++;
400 4 : }
401 5 : if (newLineMarkCount > 0) {
402 4 : dstPosition.appendMultilineContent(newLineMarkCount, lastNewLinePos + 1);
403 : }
404 5 : dstPosition.appendStringWithoutEOLMark(replacement.length() - lastNewLinePos - 1);
405 5 : }
406 :
407 : boolean hasMoreLines() {
408 5 : return !endOfSource;
409 : }
410 :
411 : private String getCurrentSrcLine() {
412 5 : if (currentSrcLine == null) {
413 5 : currentSrcLine = src.getString(srcPosition.line, srcPosition.line + 1, false);
414 : }
415 5 : return currentSrcLine;
416 : }
417 : }
418 :
419 : /** The result of applying fix to a file content */
420 : public static class FixResult {
421 : /** List of edits to transform an original text to a final text (with all fixes applied) */
422 : public final ImmutableList<Edit> edits;
423 : /** Final text with all applied fixes */
424 : public final Text text;
425 :
426 5 : FixResult(ImmutableList<Edit> edits, Text text) {
427 5 : this.edits = edits;
428 5 : this.text = text;
429 5 : }
430 : }
431 : }
|
