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