Skip to content

Commit a2c47ca

Browse files
alexdimaalexdima
committed
prettier diff (microsoft#30087)
1 parent 40ac250 commit a2c47ca

6 files changed

Lines changed: 175 additions & 23 deletions

File tree

‎src/vs/base/common/diff/diff.ts‎

Lines changed: 75 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -15,8 +15,8 @@ function createStringSequence(a: string): ISequence {
1515
};
1616
}
1717

18-
export function stringDiff(original: string, modified: string): IDiffChange[] {
19-
return new LcsDiff(createStringSequence(original), createStringSequence(modified)).ComputeDiff();
18+
export function stringDiff(original: string, modified: string, pretty: boolean): IDiffChange[] {
19+
return new LcsDiff(createStringSequence(original), createStringSequence(modified)).ComputeDiff(pretty);
2020
}
2121

2222

@@ -286,18 +286,35 @@ export class LcsDiff {
286286
return this.m_originalIds[originalIndex] === this.m_modifiedIds[newIndex];
287287
}
288288

289-
public ComputeDiff(): IDiffChange[] {
290-
return this._ComputeDiff(0, this.OriginalSequence.getLength() - 1, 0, this.ModifiedSequence.getLength() - 1);
289+
private OriginalElementsAreEqual(index1: number, index2: number): boolean {
290+
return this.m_originalIds[index1] === this.m_originalIds[index2];
291+
}
292+
293+
private ModifiedElementsAreEqual(index1: number, index2: number): boolean {
294+
return this.m_modifiedIds[index1] === this.m_modifiedIds[index2];
295+
}
296+
297+
public ComputeDiff(pretty: boolean): IDiffChange[] {
298+
return this._ComputeDiff(0, this.OriginalSequence.getLength() - 1, 0, this.ModifiedSequence.getLength() - 1, pretty);
291299
}
292300

293301
/**
294302
* Computes the differences between the original and modified input
295303
* sequences on the bounded range.
296304
* @returns An array of the differences between the two input sequences.
297305
*/
298-
private _ComputeDiff(originalStart: number, originalEnd: number, modifiedStart: number, modifiedEnd: number): DiffChange[] {
306+
private _ComputeDiff(originalStart: number, originalEnd: number, modifiedStart: number, modifiedEnd: number, pretty: boolean): DiffChange[] {
299307
let quitEarlyArr = [false];
300-
return this.ComputeDiffRecursive(originalStart, originalEnd, modifiedStart, modifiedEnd, quitEarlyArr);
308+
let changes = this.ComputeDiffRecursive(originalStart, originalEnd, modifiedStart, modifiedEnd, quitEarlyArr);
309+
310+
if (pretty) {
311+
// We have to clean up the computed diff to be more intuitive
312+
// but it turns out this cannot be done correctly until the entire set
313+
// of diffs have been computed
314+
return this.ShiftChanges(changes);
315+
}
316+
317+
return changes;
301318
}
302319

303320
/**
@@ -769,6 +786,57 @@ export class LcsDiff {
769786
);
770787
}
771788

789+
/**
790+
* Shifts the given changes to provide a more intuitive diff.
791+
* While the first element in a diff matches the first element after the diff,
792+
* we shift the diff down.
793+
*
794+
* @param changes The list of changes to shift
795+
* @returns The shifted changes
796+
*/
797+
private ShiftChanges(changes: DiffChange[]): DiffChange[] {
798+
let mergedDiffs: boolean;
799+
do {
800+
mergedDiffs = false;
801+
802+
// Shift all the changes first
803+
for (let i = 0; i < changes.length; i++) {
804+
const change = changes[i];
805+
const originalStop = (i < changes.length - 1) ? changes[i + 1].originalStart : this.OriginalSequence.getLength();
806+
const modifiedStop = (i < changes.length - 1) ? changes[i + 1].modifiedStart : this.ModifiedSequence.getLength();
807+
const checkOriginal = change.originalLength > 0;
808+
const checkModified = change.modifiedLength > 0;
809+
810+
while (change.originalStart + change.originalLength < originalStop &&
811+
change.modifiedStart + change.modifiedLength < modifiedStop &&
812+
(!checkOriginal || this.OriginalElementsAreEqual(change.originalStart, change.originalStart + change.originalLength)) &&
813+
(!checkModified || this.ModifiedElementsAreEqual(change.modifiedStart, change.modifiedStart + change.modifiedLength))) {
814+
change.originalStart++;
815+
change.modifiedStart++;
816+
}
817+
}
818+
819+
// Build up the new list (we have to build a new list because we
820+
// might have changes we can merge together now)
821+
let result = new Array<DiffChange>();
822+
let mergedChangeArr: DiffChange[] = [null];
823+
for (let i = 0; i < changes.length; i++) {
824+
if (i < changes.length - 1 && this.ChangesOverlap(changes[i], changes[i + 1], mergedChangeArr)) {
825+
mergedDiffs = true;
826+
result.push(mergedChangeArr[0]);
827+
i++;
828+
}
829+
else {
830+
result.push(changes[i]);
831+
}
832+
}
833+
834+
changes = result;
835+
} while (mergedDiffs);
836+
837+
return changes;
838+
}
839+
772840
/**
773841
* Concatenates the two input DiffChange lists and returns the resulting
774842
* list.
@@ -847,7 +915,6 @@ export class LcsDiff {
847915
* @param numDiagonals The total number of diagonals.
848916
* @returns The clipped diagonal index.
849917
*/
850-
851918
private ClipDiagonalBound(diagonal: number, numDifferences: number, diagonalBaseIndex: number, numDiagonals: number): number {
852919
if (diagonal >= 0 && diagonal < numDiagonals) {
853920
// Nothing to clip, its in range
@@ -868,5 +935,4 @@ export class LcsDiff {
868935
return (diffEven === upperBoundEven) ? numDiagonals - 1 : numDiagonals - 2;
869936
}
870937
}
871-
872-
}
938+
}

‎src/vs/base/parts/tree/browser/treeView.ts‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -955,7 +955,7 @@ export class TreeView extends HeightMap {
955955
getElementHash: (i: number) => afterModelItems[i].id
956956
}, null);
957957

958-
diff = lcs.ComputeDiff();
958+
diff = lcs.ComputeDiff(false);
959959

960960
// this means that the result of the diff algorithm would result
961961
// in inserting items that were already registered. this can only

‎src/vs/base/test/common/diff/diff.test.ts‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -143,7 +143,7 @@ suite('Diff - Ported from VS', () => {
143143
// cancel processing
144144
return false;
145145
});
146-
var changes = diff.ComputeDiff();
146+
var changes = diff.ComputeDiff(true);
147147

148148
assert.equal(predicateCallCount, 1);
149149

@@ -159,7 +159,7 @@ suite('Diff - Ported from VS', () => {
159159
// Continue processing as long as there hasn't been a match made.
160160
return longestMatchSoFar < 1;
161161
});
162-
changes = diff.ComputeDiff();
162+
changes = diff.ComputeDiff(true);
163163

164164
assertAnswer(left, right, changes, 'abcf');
165165

@@ -172,7 +172,7 @@ suite('Diff - Ported from VS', () => {
172172
// Continue processing as long as there hasn't been a match made.
173173
return longestMatchSoFar < 2;
174174
});
175-
changes = diff.ComputeDiff();
175+
changes = diff.ComputeDiff(true);
176176

177177
assertAnswer(left, right, changes, 'abcdf');
178178

@@ -188,7 +188,7 @@ suite('Diff - Ported from VS', () => {
188188
// Continue processing as long as there hasn't been a match made.
189189
return !hitYet;
190190
});
191-
changes = diff.ComputeDiff();
191+
changes = diff.ComputeDiff(true);
192192

193193
assertAnswer(left, right, changes, 'abcdf');
194194

@@ -201,7 +201,7 @@ suite('Diff - Ported from VS', () => {
201201
// Continue processing as long as there hasn't been a match made.
202202
return longestMatchSoFar < 3;
203203
});
204-
changes = diff.ComputeDiff();
204+
changes = diff.ComputeDiff(true);
205205

206206
assertAnswer(left, right, changes, 'abcdef');
207207
});

‎src/vs/editor/common/diff/diffComputer.ts‎

Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -17,9 +17,9 @@ interface IMarker {
1717
offset: number;
1818
}
1919

20-
function computeDiff(originalSequence: ISequence, modifiedSequence: ISequence, continueProcessingPredicate: () => boolean): IDiffChange[] {
20+
function computeDiff(originalSequence: ISequence, modifiedSequence: ISequence, continueProcessingPredicate: () => boolean, pretty: boolean): IDiffChange[] {
2121
var diffAlgo = new LcsDiff(originalSequence, modifiedSequence, continueProcessingPredicate);
22-
return diffAlgo.ComputeDiff();
22+
return diffAlgo.ComputeDiff(pretty);
2323
}
2424

2525
class MarkerSequence implements ISequence {
@@ -252,7 +252,7 @@ class LineChange implements ILineChange {
252252
var originalCharSequence = originalLineSequence.getCharSequence(diffChange.originalStart, diffChange.originalStart + diffChange.originalLength - 1);
253253
var modifiedCharSequence = modifiedLineSequence.getCharSequence(diffChange.modifiedStart, diffChange.modifiedStart + diffChange.modifiedLength - 1);
254254

255-
var rawChanges = computeDiff(originalCharSequence, modifiedCharSequence, continueProcessingPredicate);
255+
var rawChanges = computeDiff(originalCharSequence, modifiedCharSequence, continueProcessingPredicate, false);
256256

257257
if (shouldPostProcessCharChanges) {
258258
rawChanges = postProcessCharChanges(rawChanges);
@@ -271,12 +271,14 @@ export interface IDiffComputerOpts {
271271
shouldPostProcessCharChanges: boolean;
272272
shouldIgnoreTrimWhitespace: boolean;
273273
shouldConsiderTrimWhitespaceInEmptyCase: boolean;
274+
shouldMakePrettyDiff: boolean;
274275
}
275276

276277
export class DiffComputer {
277278

278279
private shouldPostProcessCharChanges: boolean;
279280
private shouldIgnoreTrimWhitespace: boolean;
281+
private shouldMakePrettyDiff: boolean;
280282
private maximumRunTimeMs: number;
281283
private original: LineMarkerSequence;
282284
private modified: LineMarkerSequence;
@@ -286,6 +288,7 @@ export class DiffComputer {
286288
constructor(originalLines: string[], modifiedLines: string[], opts: IDiffComputerOpts) {
287289
this.shouldPostProcessCharChanges = opts.shouldPostProcessCharChanges;
288290
this.shouldIgnoreTrimWhitespace = opts.shouldIgnoreTrimWhitespace;
291+
this.shouldMakePrettyDiff = opts.shouldMakePrettyDiff;
289292
this.maximumRunTimeMs = MAXIMUM_RUN_TIME;
290293
this.original = new LineMarkerSequence(originalLines, this.shouldIgnoreTrimWhitespace);
291294
this.modified = new LineMarkerSequence(modifiedLines, this.shouldIgnoreTrimWhitespace);
@@ -341,7 +344,7 @@ export class DiffComputer {
341344

342345
this.computationStartTime = (new Date()).getTime();
343346

344-
var rawChanges = computeDiff(this.original, this.modified, this._continueProcessingPredicate.bind(this));
347+
var rawChanges = computeDiff(this.original, this.modified, this._continueProcessingPredicate.bind(this), this.shouldMakePrettyDiff);
345348

346349
var lineChanges: ILineChange[] = [];
347350
for (var i = 0, length = rawChanges.length; i < length; i++) {

‎src/vs/editor/common/services/editorSimpleWorker.ts‎

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -313,7 +313,8 @@ export abstract class BaseEditorSimpleWorker {
313313
let diffComputer = new DiffComputer(originalLines, modifiedLines, {
314314
shouldPostProcessCharChanges: true,
315315
shouldIgnoreTrimWhitespace: ignoreTrimWhitespace,
316-
shouldConsiderTrimWhitespaceInEmptyCase: true
316+
shouldConsiderTrimWhitespaceInEmptyCase: true,
317+
shouldMakePrettyDiff: true
317318
});
318319
return TPromise.as(diffComputer.computeDiff());
319320
}
@@ -330,7 +331,8 @@ export abstract class BaseEditorSimpleWorker {
330331
let diffComputer = new DiffComputer(originalLines, modifiedLines, {
331332
shouldPostProcessCharChanges: false,
332333
shouldIgnoreTrimWhitespace: ignoreTrimWhitespace,
333-
shouldConsiderTrimWhitespaceInEmptyCase: false
334+
shouldConsiderTrimWhitespaceInEmptyCase: false,
335+
shouldMakePrettyDiff: true
334336
});
335337
return TPromise.as(diffComputer.computeDiff());
336338
}
@@ -377,7 +379,7 @@ export abstract class BaseEditorSimpleWorker {
377379
}
378380

379381
// compute diff between original and edit.text
380-
const changes = stringDiff(original, text);
382+
const changes = stringDiff(original, text, false);
381383
const editOffset = model.offsetAt(Range.lift(range).getStartPosition());
382384

383385
for (const change of changes) {

‎src/vs/editor/test/common/diff/diffComputer.test.ts‎

Lines changed: 82 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -55,7 +55,8 @@ function assertDiff(originalLines: string[], modifiedLines: string[], expectedCh
5555
var diffComputer = new DiffComputer(originalLines, modifiedLines, {
5656
shouldPostProcessCharChanges: shouldPostProcessCharChanges || false,
5757
shouldIgnoreTrimWhitespace: shouldIgnoreTrimWhitespace || false,
58-
shouldConsiderTrimWhitespaceInEmptyCase: true
58+
shouldConsiderTrimWhitespaceInEmptyCase: true,
59+
shouldMakePrettyDiff: true
5960
});
6061
var changes = diffComputer.computeDiff();
6162

@@ -458,4 +459,84 @@ suite('Editor Diff - DiffComputer', () => {
458459
];
459460
assertDiff(original, modified, expected, false, true);
460461
});
462+
463+
test('pretty diff 1', () => {
464+
var original = [
465+
'suite(function () {',
466+
' test1() {',
467+
' assert.ok(true);',
468+
' }',
469+
'',
470+
' test2() {',
471+
' assert.ok(true);',
472+
' }',
473+
'});',
474+
'',
475+
];
476+
var modified = [
477+
'// An insertion',
478+
'suite(function () {',
479+
' test1() {',
480+
' assert.ok(true);',
481+
' }',
482+
'',
483+
' test2() {',
484+
' assert.ok(true);',
485+
' }',
486+
'',
487+
' test3() {',
488+
' assert.ok(true);',
489+
' }',
490+
'});',
491+
'',
492+
];
493+
var expected = [
494+
createLineInsertion(1, 1, 0),
495+
createLineInsertion(10, 13, 8)
496+
];
497+
assertDiff(original, modified, expected, false, true);
498+
});
499+
500+
test('pretty diff 2', () => {
501+
var original = [
502+
'// Just a comment',
503+
'',
504+
'function compute(a, b, c, d) {',
505+
' if (a) {',
506+
' if (b) {',
507+
' if (c) {',
508+
' return 5;',
509+
' }',
510+
' }',
511+
' // These next lines will be deleted',
512+
' if (d) {',
513+
' return -1;',
514+
' }',
515+
' return 0;',
516+
' }',
517+
'}',
518+
];
519+
var modified = [
520+
'// Here is an inserted line',
521+
'// and another inserted line',
522+
'// and another one',
523+
'// Just a comment',
524+
'',
525+
'function compute(a, b, c, d) {',
526+
' if (a) {',
527+
' if (b) {',
528+
' if (c) {',
529+
' return 5;',
530+
' }',
531+
' }',
532+
' return 0;',
533+
' }',
534+
'}',
535+
];
536+
var expected = [
537+
createLineInsertion(1, 3, 0),
538+
createLineDeletion(10, 13, 12),
539+
];
540+
assertDiff(original, modified, expected, false, true);
541+
});
461542
});

0 commit comments

Comments
 (0)