codekingpro/portable-devtools
115k
1export default class Diff {
2 diff(oldStr, newStr,
3 // Type below is not accurate/complete - see above for full possibilities - but it compiles
4 options = {}) {
5 let callback;
6 if (typeof options === 'function') {
7 callback = options;
8 options = {};
9 }
10 else if ('callback' in options) {
11 callback = options.callback;
12 }
13 // Allow subclasses to massage the input prior to running
14 const oldString = this.castInput(oldStr, options);
15 const newString = this.castInput(newStr, options);
16 const oldTokens = this.removeEmpty(this.tokenize(oldString, options));
17 const newTokens = this.removeEmpty(this.tokenize(newString, options));
18 return this.diffWithOptionsObj(oldTokens, newTokens, options, callback);
19 }
20 diffWithOptionsObj(oldTokens, newTokens, options, callback) {
21 var _a;
22 const done = (value) => {
23 value = this.postProcess(value, options);
24 if (callback) {
25 setTimeout(function () { callback(value); }, 0);
26 return undefined;
27 }
28 else {
29 return value;
30 }
31 };
32 const newLen = newTokens.length, oldLen = oldTokens.length;
33 let editLength = 1;
34 let maxEditLength = newLen + oldLen;
35 if (options.maxEditLength != null) {
36 maxEditLength = Math.min(maxEditLength, options.maxEditLength);
37 }
38 const maxExecutionTime = (_a = options.timeout) !== null && _a !== void 0 ? _a : Infinity;
39 const abortAfterTimestamp = Date.now() + maxExecutionTime;
40 const bestPath = [{ oldPos: -1, lastComponent: undefined }];
41 // Seed editLength = 0, i.e. the content starts with the same values
42 let newPos = this.extractCommon(bestPath[0], newTokens, oldTokens, 0, options);
43 if (bestPath[0].oldPos + 1 >= oldLen && newPos + 1 >= newLen) {
44 // Identity per the equality and tokenizer
45 return done(this.buildValues(bestPath[0].lastComponent, newTokens, oldTokens));
46 }
47 // Once we hit the right edge of the edit graph on some diagonal k, we can
48 // definitely reach the end of the edit graph in no more than k edits, so
49 // there's no point in considering any moves to diagonal k+1 any more (from
50 // which we're guaranteed to need at least k+1 more edits).
51 // Similarly, once we've reached the bottom of the edit graph, there's no
52 // point considering moves to lower diagonals.
53 // We record this fact by setting minDiagonalToConsider and
54 // maxDiagonalToConsider to some finite value once we've hit the edge of
55 // the edit graph.
56 // This optimization is not faithful to the original algorithm presented in
57 // Myers's paper, which instead pointlessly extends D-paths off the end of
58 // the edit graph - see page 7 of Myers's paper which notes this point
59 // explicitly and illustrates it with a diagram. This has major performance
60 // implications for some common scenarios. For instance, to compute a diff
61 // where the new text simply appends d characters on the end of the
62 // original text of length n, the true Myers algorithm will take O(n+d^2)
63 // time while this optimization needs only O(n+d) time.
64 let minDiagonalToConsider = -Infinity, maxDiagonalToConsider = Infinity;
65 // Main worker method. checks all permutations of a given edit length for acceptance.
66 const execEditLength = () => {
67 for (let diagonalPath = Math.max(minDiagonalToConsider, -editLength); diagonalPath <= Math.min(maxDiagonalToConsider, editLength); diagonalPath += 2) {
68 let basePath;
69 const removePath = bestPath[diagonalPath - 1], addPath = bestPath[diagonalPath + 1];
70 if (removePath) {
71 // No one else is going to attempt to use this value, clear it
72 // @ts-expect-error - perf optimisation. This type-violating value will never be read.
73 bestPath[diagonalPath - 1] = undefined;
74 }
75 let canAdd = false;
76 if (addPath) {
77 // what newPos will be after we do an insertion:
78 const addPathNewPos = addPath.oldPos - diagonalPath;
79 canAdd = addPath && 0 <= addPathNewPos && addPathNewPos < newLen;
80 }
81 const canRemove = removePath && removePath.oldPos + 1 < oldLen;
82 if (!canAdd && !canRemove) {
83 // If this path is a terminal then prune
84 // @ts-expect-error - perf optimisation. This type-violating value will never be read.
85 bestPath[diagonalPath] = undefined;
86 continue;
87 }
88 // Select the diagonal that we want to branch from. We select the prior
89 // path whose position in the old string is the farthest from the origin
90 // and does not pass the bounds of the diff graph
91 if (!canRemove || (canAdd && removePath.oldPos < addPath.oldPos)) {
92 basePath = this.addToPath(addPath, true, false, 0, options);
93 }
94 else {
95 basePath = this.addToPath(removePath, false, true, 1, options);
96 }
97 newPos = this.extractCommon(basePath, newTokens, oldTokens, diagonalPath, options);
98 if (basePath.oldPos + 1 >= oldLen && newPos + 1 >= newLen) {
99 // If we have hit the end of both strings, then we are done
100 return done(this.buildValues(basePath.lastComponent, newTokens, oldTokens)) || true;
101 }
102 else {
103 bestPath[diagonalPath] = basePath;
104 if (basePath.oldPos + 1 >= oldLen) {
105 maxDiagonalToConsider = Math.min(maxDiagonalToConsider, diagonalPath - 1);
106 }
107 if (newPos + 1 >= newLen) {
108 minDiagonalToConsider = Math.max(minDiagonalToConsider, diagonalPath + 1);
109 }
110 }
111 }
112 editLength++;
113 };
114 // Performs the length of edit iteration. Is a bit fugly as this has to support the
115 // sync and async mode which is never fun. Loops over execEditLength until a value
116 // is produced, or until the edit length exceeds options.maxEditLength (if given),
117 // in which case it will return undefined.
118 if (callback) {
119 (function exec() {
120 setTimeout(function () {
121 if (editLength > maxEditLength || Date.now() > abortAfterTimestamp) {
122 return callback(undefined);
123 }
124 if (!execEditLength()) {
125 exec();
126 }
127 }, 0);
128 }());
129 }
130 else {
131 while (editLength <= maxEditLength && Date.now() <= abortAfterTimestamp) {
132 const ret = execEditLength();
133 if (ret) {
134 return ret;
135 }
136 }
137 }
138 }
139 addToPath(path, added, removed, oldPosInc, options) {
140 const last = path.lastComponent;
141 if (last && !options.oneChangePerToken && last.added === added && last.removed === removed) {
142 return {
143 oldPos: path.oldPos + oldPosInc,
144 lastComponent: { count: last.count + 1, added: added, removed: removed, previousComponent: last.previousComponent }
145 };
146 }
147 else {
148 return {
149 oldPos: path.oldPos + oldPosInc,
150 lastComponent: { count: 1, added: added, removed: removed, previousComponent: last }
151 };
152 }
153 }
154 extractCommon(basePath, newTokens, oldTokens, diagonalPath, options) {
155 const newLen = newTokens.length, oldLen = oldTokens.length;
156 let oldPos = basePath.oldPos, newPos = oldPos - diagonalPath, commonCount = 0;
157 while (newPos + 1 < newLen && oldPos + 1 < oldLen && this.equals(oldTokens[oldPos + 1], newTokens[newPos + 1], options)) {
158 newPos++;
159 oldPos++;
160 commonCount++;
161 if (options.oneChangePerToken) {
162 basePath.lastComponent = { count: 1, previousComponent: basePath.lastComponent, added: false, removed: false };
163 }
164 }
165 if (commonCount && !options.oneChangePerToken) {
166 basePath.lastComponent = { count: commonCount, previousComponent: basePath.lastComponent, added: false, removed: false };
167 }
168 basePath.oldPos = oldPos;
169 return newPos;
170 }
171 equals(left, right, options) {
172 if (options.comparator) {
173 return options.comparator(left, right);
174 }
175 else {
176 return left === right
177 || (!!options.ignoreCase && left.toLowerCase() === right.toLowerCase());
178 }
179 }
180 removeEmpty(array) {
181 const ret = [];
182 for (let i = 0; i < array.length; i++) {
183 if (array[i]) {
184 ret.push(array[i]);
185 }
186 }
187 return ret;
188 }
189 // eslint-disable-next-line @typescript-eslint/no-unused-vars
190 castInput(value, options) {
191 return value;
192 }
193 // eslint-disable-next-line @typescript-eslint/no-unused-vars
194 tokenize(value, options) {
195 return Array.from(value);
196 }
197 join(chars) {
198 // Assumes ValueT is string, which is the case for most subclasses.
199 // When it's false, e.g. in diffArrays, this method needs to be overridden (e.g. with a no-op)
200 // Yes, the casts are verbose and ugly, because this pattern - of having the base class SORT OF
201 // assume tokens and values are strings, but not completely - is weird and janky.
202 return chars.join('');
203 }
204 postProcess(changeObjects,
205 // eslint-disable-next-line @typescript-eslint/no-unused-vars
206 options) {
207 return changeObjects;
208 }
209 get useLongestToken() {
210 return false;
211 }
212 buildValues(lastComponent, newTokens, oldTokens) {
213 // First we convert our linked list of components in reverse order to an
214 // array in the right order:
215 const components = [];
216 let nextComponent;
217 while (lastComponent) {
218 components.push(lastComponent);
219 nextComponent = lastComponent.previousComponent;
220 delete lastComponent.previousComponent;
221 lastComponent = nextComponent;
222 }
223 components.reverse();
224 const componentLen = components.length;
225 let componentPos = 0, newPos = 0, oldPos = 0;
226 for (; componentPos < componentLen; componentPos++) {
227 const component = components[componentPos];
228 if (!component.removed) {
229 if (!component.added && this.useLongestToken) {
230 let value = newTokens.slice(newPos, newPos + component.count);
231 value = value.map(function (value, i) {
232 const oldValue = oldTokens[oldPos + i];
233 return oldValue.length > value.length ? oldValue : value;
234 });
235 component.value = this.join(value);
236 }
237 else {
238 component.value = this.join(newTokens.slice(newPos, newPos + component.count));
239 }
240 newPos += component.count;
241 // Common case
242 if (!component.added) {
243 oldPos += component.count;
244 }
245 }
246 else {
247 component.value = this.join(oldTokens.slice(oldPos, oldPos + component.count));
248 oldPos += component.count;
249 }
250 }
251 return components;
252 }
253}
254