File Explorer

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 compiles8    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 running19        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 values48        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 tokenizer51            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 can54        // definitely reach the end of the edit graph in no more than k edits, so55        // there's no point in considering any moves to diagonal k+1 any more (from56        // 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 no58        // point considering moves to lower diagonals.59        // We record this fact by setting minDiagonalToConsider and60        // maxDiagonalToConsider to some finite value once we've hit the edge of61        // the edit graph.62        // This optimization is not faithful to the original algorithm presented in63        // Myers's paper, which instead pointlessly extends D-paths off the end of64        // the edit graph - see page 7 of Myers's paper which notes this point65        // explicitly and illustrates it with a diagram. This has major performance66        // implications for some common scenarios. For instance, to compute a diff67        // where the new text simply appends d characters on the end of the68        // 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 it78                    // @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 prune90                    // @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 prior95                // path whose position in the old string is the farthest from the origin96                // and does not pass the bounds of the diff graph97                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 done106                    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 the121        // sync and async mode which is never fun. Loops over execEditLength until a value122        // 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 === right183                || (!!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-vars196    Diff.prototype.castInput = function (value, options) {197        return value;198    };199    // eslint-disable-next-line @typescript-eslint/no-unused-vars200    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 OF207        // 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-vars212    options) {213        return changeObjects;214    };215    Object.defineProperty(Diff.prototype, "useLongestToken", {216        get: function () {217            return false;218        },219        enumerable: false,220        configurable: true221    });222    Diff.prototype.buildValues = function (lastComponent, newTokens, oldTokens) {223        // First we convert our linked list of components in reverse order to an224        // 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 case252                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