onion-core/dist/lib/version.js

"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.VersionRegistry = exports.Version = void 0;
const util_1 = require("util"); // NodeJS library
const buffer_1 = require("buffer"); // NodeJS library
const dfs_1 = require("./util/dfs");
const permutations_1 = require("./util/permutations");
const buffer_xor_1 = require("./util/buffer_xor");
// not exported -> use VersionRegistry to create versions
class Version {
    // DO NOT USE constructor directly - instead use VersionRegistry.createVersion.
    constructor(parents, hash, size, embeddings) {
        this.children = []; // reverse parents
        this.reverseEmbeddings = new Map(); // (host) versions in which this (guest) version is embedded.
        this.implicitSelfEmbedding = {
            version: this,
            overridings: new Map(), // no overrides
        };
        this.parents = parents;
        this.hash = hash;
        this.size = size;
        this.embeddings = embeddings(this);
    }
    // Returns iterator that yields all deltas of this version, from recent to early.
    // Or put more precisely: a delta's dependencies will be yielded AFTER the delta itself.
    *[Symbol.iterator]() {
        let current = this;
        while (current.parents.length !== 0) {
            // There may be multiple parents due to commutativity (multiple orders of deltas that yield the same version), but it doesn't matter which one we pick: all paths will yield the same set of deltas.
            const [parent, delta] = current.parents[0];
            yield delta;
            current = parent;
        }
    }
    *iterPrimitiveDeltas() {
        const executionOrder = [...this].reverse();
        for (const d of executionOrder) {
            yield* d.iterPrimitiveDeltas();
        }
    }
    [util_1.inspect.custom](depth, options) {
        return "Version{" + [...this].map(d => (0, util_1.inspect)(d, options)).join(",") + "}";
    }
    isSubSetOf(otherVersion) {
        // current implementation is probably quite slow
        for (const delta of this) {
            if (!otherVersion.contains(delta)) {
                return false;
            }
        }
        return true;
    }
    contains(delta) {
        for (const d of this) {
            if (d === delta) {
                return true;
            }
        }
        return false;
    }
    containsPrimitive(delta) {
        for (const d of this) {
            for (const p of d.iterPrimitiveDeltas()) {
                if (p === delta) {
                    return true;
                }
            }
        }
        return false;
    }
    // Returns a sequence of Delta's to be undone/redone to go from this version to the 'otherVersion'
    // Returned sequence is empty if otherVersion === this
    // Returns undefined when there is no path (which is impossible if both versions are part of the same VersionRegistry).
    // TODO: implement Breadth-First Search (BFS) for better performance.
    findPathTo(otherVersion) {
        const getNeighbors = (v) => {
            const parentVersions = v.parents.map(([parentVersion, delta]) => [['p', delta, parentVersion], parentVersion]);
            const childVersions = v.children.map(([childVersion, delta]) => [['c', delta, childVersion], childVersion]);
            // heuristic: look in newer or older versions first?
            if (v.size < otherVersion.size) {
                // make the common case fast: most of the time,
                // we just want to advance to the next version (i.e., after a user edit)
                return [...childVersions, ...parentVersions];
            }
            else {
                return [...parentVersions, ...childVersions];
            }
        };
        // console.time("findDFS")
        const result = (0, dfs_1.findDFS)(this, otherVersion, getNeighbors);
        // console.timeEnd("findDFS");
        // if (result)
        //   console.log("findPath:", result.map(([linkType])=>linkType));
        return result;
    }
    // Like findPathTo, but only searches 'down' (younger versions).
    findDescendant(otherVersion) {
        const getNeighbors = (v) => {
            const result = v.children.map(([childVersion, delta]) => [['c', delta, childVersion], childVersion]);
            return result;
        };
        return (0, dfs_1.findDFS)(this, otherVersion, getNeighbors);
    }
    getEmbedding(key) {
        return this.embeddings.get(key) || this.implicitSelfEmbedding;
    }
    getReverseEmbeddings(key) {
        return this.reverseEmbeddings.get(key) || [this];
    }
    // Serialize a path of Deltas from a Version in alreadyHave, to fully reconstruct this version.
    serialize(alreadyHave = new Set()) {
        const deltas = [];
        const versions = [];
        this.serializeInternal(new Set(alreadyHave), new Set(), deltas, versions);
        return {
            externalDependencies: [...alreadyHave].map(v => v.hash.toString('hex')),
            deltas,
            versions,
        };
    }
    serializeInternal(alreadyHaveVersions, alreadyHaveDeltas, deltas, versions) {
        if (alreadyHaveVersions.has(this)) {
            return;
        }
        alreadyHaveVersions.add(this);
        const embeddings = new Array();
        for (const [guestId, { version, overridings }] of this.embeddings) {
            version.serializeInternal(alreadyHaveVersions, alreadyHaveDeltas, deltas, versions);
            const ovr = {};
            for (const [key, val] of overridings.entries()) {
                ovr[key.hash.toString('hex')] = val.hash.toString('hex');
            }
            embeddings.push({ guestId, v: version.hash.toString('hex'), ovr });
        }
        if (this.parents.length > 0) {
            const [parentVersion, delta] = this.parents[0];
            parentVersion.serializeInternal(alreadyHaveVersions, alreadyHaveDeltas, deltas, versions);
            function visitDelta(delta) {
                for (const d of delta.getDependencies()) {
                    visitDelta(d);
                }
                if (!alreadyHaveDeltas.has(delta)) {
                    deltas.push(delta.serialize());
                    alreadyHaveDeltas.add(delta);
                }
            }
            visitDelta(delta);
            versions.push({
                id: this.hash.toString('hex'),
                parent: parentVersion.hash.toString('hex'),
                delta: delta.hash.toString('hex'),
                embeddings,
            });
        }
    }
}
exports.Version = Version;
const initialHash = buffer_1.Buffer.alloc(32); // all zeros
function isConflicting(deltaA, deltaB) {
    // for performance, iterate over the delta that has the least conflicts:
    if (deltaA.conflictsWith.length < deltaB.conflictsWith.length) {
        return deltaA.conflictsWith.some(([d]) => d === deltaB);
    }
    else {
        return deltaB.conflictsWith.some(([d]) => d === deltaA);
    }
}
class VersionRegistry {
    constructor() {
        this.initialVersion = new Version([], initialHash, 0, () => new Map());
        // Maps version ID (as string, because a Buffer cannot be a map key) to Version
        this.versionMap = new Map([
            [initialHash.toString('hex'), this.initialVersion], // the initial version, always already there
        ]);
    }
    lookupOptional(hash) {
        return this.versionMap.get(hash.toString('hex'));
    }
    lookup(hash) {
        const hex = hash.toString('hex');
        const version = this.versionMap.get(hex);
        if (version === undefined) {
            throw new Error("no such version: " + hex);
        }
        return version;
    }
    putVersion(hash, version) {
        this.versionMap.set(hash.toString('hex'), version);
    }
    // Idempotent
    // Pre-condition 1: all of the dependencies of delta must exist in parent.
    // Pre-condition 2: delta must be non-conflicting with any delta in parent.
    // Pre-condition 3: if the to-be-created ("host") version embeds other ("guest") versions,
    //   then all of the guest versions' deltas must exist in the host version, or be explicitly overridden.
    createVersion(parent, delta, embeddings = () => new Map()) {
        // Check pre-condition 1:
        for (const [dep] of delta.getDependencies()) {
            if (!parent.contains(dep)) {
                throw new Error("createVersion: precondition failed: Missing dependency: " + dep.description);
            }
        }
        // Check pre-condition 2:
        for (const [conflictingDelta] of delta.conflictsWith) {
            if (parent.contains(conflictingDelta)) {
                throw new Error("createVersion: precondition failed: Delta " + delta.description + " conflicts with " + conflictingDelta.description);
            }
        }
        const newVersion = this.createVersionUnsafe(parent, delta, embeddings);
        // Check pre-condition 3:
        const primitiveDeltas = [...delta.iterPrimitiveDeltas()];
        for (const [guestId, { version: guest, overridings }] of newVersion.embeddings.entries()) {
            const { version: guestParent } = parent.getEmbedding(guestId);
            const guestDiff = guestParent.findDescendant(guest);
            for (const [_, guestDelta] of guestDiff) {
                for (const guestPDelta of guestDelta.iterPrimitiveDeltas()) {
                    if (!primitiveDeltas.includes(overridings.get(guestPDelta) || guestPDelta)) {
                        throw new Error("createVersion: precondition failed: Guest's primitive delta " + guestPDelta.description + " does not occur in host, nor is it overridden.");
                    }
                }
            }
        }
        return newVersion;
    }
    // Faster than createVersion, but does not check pre-conditions.
    // Idempotent
    createVersionUnsafe(parent, delta, embeddings = () => new Map()) {
        const newHash = (0, buffer_xor_1.bufferXOR)(parent.hash, delta.hash);
        // TODO: include embeddings in hash digest.
        const existingVersion = this.lookupOptional(newHash);
        if (existingVersion !== undefined) {
            // this Version already exists
            const havePath = existingVersion.parents.some(([parentVersion, delta]) => parentVersion === parent);
            if (!havePath) {
                // but the path is new (there can be multiple 'paths' to the same version, because of commutation of deltas)
                existingVersion.parents.push([parent, delta]);
                parent.children.push([existingVersion, delta]);
            }
            for (const [guestId, { version, overridings }] of embeddings(existingVersion)) {
                const found = existingVersion.embeddings.get(guestId);
                if (!found) {
                    existingVersion.embeddings.set(guestId, { version, overridings });
                    // throw new Error("Assertion failed: created version already exists, but does not embed '" + guestId + "'");
                }
                else {
                    const { version: v, overridings: o } = found;
                    if (v !== version) {
                        throw new Error("Assertion failed: created version already exists and embeds a differrent version '" + guestId + "'");
                    }
                    // Merge overridings:
                    for (const [guestDelta, hostDelta] of overridings.entries()) {
                        const alreadyHostDelta = o.get(guestDelta) || hostDelta;
                        if (hostDelta !== alreadyHostDelta) {
                            throw new Error("Assertion failed: created version already exists BUT overrides delta '" + guestDelta.description + "' with another delta.");
                        }
                        o.set(guestDelta, hostDelta);
                    }
                }
            }
            return existingVersion;
        }
        else {
            const newVersion = new Version([[parent, delta]], newHash, parent.size + 1, embeddings);
            // Create reverse parent links:
            for (const [parent, delta] of newVersion.parents) {
                parent.children.push([newVersion, delta]);
            }
            // Create reverse embedding:
            for (const [key, embedding] of newVersion.embeddings.entries()) {
                const reverse = embedding.version.reverseEmbeddings.get(key);
                if (reverse !== undefined) {
                    reverse.push(newVersion);
                }
                else {
                    embedding.version.reverseEmbeddings.set(key, [newVersion]);
                }
            }
            this.putVersion(newHash, newVersion);
            return newVersion;
        }
    }
    // Mostly used for testing purposes.
    // Order of deltas should be recent -> early
    // Or put more precisely: a delta's dependencies should occur AFTER the delta in the array.
    quickVersion(deltas) {
        return deltas.reduceRight((parentVersion, delta) => this.createVersion(parentVersion, delta), this.initialVersion);
    }
    // Get the version whose deltas are a subset of all given versions AKA the 'largest common ancestor'.
    getIntersection(versions) {
        // treat special case first:
        if (versions.length === 0) {
            return this.initialVersion;
        }
        // sort versions (out place) from few deltas to many (FASTEST):
        const sortedVersions = versions.slice().sort((versionA, versionB) => versionA.size - versionB.size);
        const intersection = [];
        for (const delta of sortedVersions[0]) {
            let allVersionsHaveIt = true;
            for (let i = 1; i < sortedVersions.length; i++) {
                let thisVersionHasIt = false;
                for (const otherDelta of sortedVersions[i]) {
                    if (delta === otherDelta) {
                        thisVersionHasIt = true;
                        break;
                    }
                }
                if (!thisVersionHasIt) {
                    allVersionsHaveIt = false;
                    break;
                }
            }
            if (allVersionsHaveIt) {
                intersection.push(delta);
            }
        }
        return this.quickVersion(intersection);
    }
    getLCAInternal(versionA, versionB) {
        const ancestorsA = [versionA];
        const ancestorsB = [versionB];
        while (true) {
            const a = ancestorsA[ancestorsA.length - 1];
            // @ts-ignore: TypeScript doesn't know about 'findLast' method yet.
            if (ancestorsB.findLast(v => v === a)) {
                return a;
            }
            if (a.parents.length > 0) {
                const [parent] = a.parents[0];
                ancestorsA.push(parent);
            }
            const b = ancestorsB[ancestorsB.length - 1];
            // @ts-ignore: TypeScript doesn't know about 'findLast' method yet.
            if (ancestorsA.findLast(v => v === b)) {
                return b;
            }
            if (b.parents.length > 0) {
                const [parent] = b.parents[0];
                ancestorsB.push(parent);
            }
        }
    }
    getLCA(versions) {
        if (versions.length === 0) {
            return this.initialVersion;
        }
        return versions.reduce((a, b) => this.getLCAInternal(a, b));
    }
    // Idempotent
    // Of the union of all deltas of the versions given, compute the maximal left-closed conflict-free subsets.
    // These are the subsets to which no delta can be added without introducing a conflict or missing dependency.
    merge(versions, debugNames) {
        function printDebug(...args) {
            if (debugNames !== undefined) {
                for (const [i, arg] of args.entries()) {
                    try {
                        const name = debugNames(arg);
                        if (name !== undefined) {
                            args[i] = name;
                        }
                    }
                    catch (e) { }
                }
                console.log(...args);
            }
        }
        const lca = this.getLCA(versions);
        // ATTENTION: Constructing 'diff' must be made recursive (guest could also be a host)
        function visitEmbeddings(currentHost, nextHost) {
            const guestDeltaMap = new Map();
            for (const [guestId, { version: nextGuest, overridings }] of nextHost.embeddings.entries()) {
                const currentGuest = currentHost.getEmbedding(guestId).version;
                const guestPath = currentGuest.findDescendant(nextGuest);
                if (guestPath.length > 1) {
                    throw new Error("Did not expect guestPath to be longer than one delta");
                }
                if (guestPath.length === 1) {
                    const guestDelta = guestPath[0][1];
                    if (currentHost === currentGuest && nextHost === nextGuest) {
                        // prevent infinite recursion in case of self-embedding:
                        guestDeltaMap.set(guestId, [[guestDelta, guestDeltaMap], overridings]);
                    }
                    else {
                        const recursiveGuestDeltaMap = visitEmbeddings(currentGuest, nextGuest);
                        guestDeltaMap.set(guestId, [[guestDelta, recursiveGuestDeltaMap], overridings]);
                    }
                }
                else {
                    guestDeltaMap.set(guestId, [null, new Map()]);
                }
            }
            return guestDeltaMap;
        }
        let diff = [];
        for (const v of versions) {
            const path = lca.findDescendant(v);
            // all deltas on path from lca to 'v':
            let currentVersion = lca;
            for (const [_, delta, nextVersion] of path) {
                const guestDeltaMap = visitEmbeddings(currentVersion, nextVersion);
                // The following condition may be wrong, check this later:
                if (!diff.some(([d]) => d === delta)) {
                    diff.push([delta, guestDeltaMap]);
                }
                currentVersion = nextVersion;
            }
        }
        // Now we're ready to actually start merging...
        const result = [];
        // Recursively attempts to add deltas from 'deltasToTry' to 'startVersion'
        // When nothing can be added anymore without introducing a conflict, we have a 'maximal version' (a result).
        // It's possible that there is more than one 'maximal version'.
        // Precondition: We assume that any single delta of 'deltasToTry' will not be conflicting with 'startVersion'.
        const depthFirst = (startVersion, candidates, depth) => {
            function printIndent(...args) {
                printDebug("  ".repeat(depth), ...args);
            }
            // printIndent("deltasToTry=", ...candidates.map(([d])=>d));
            let couldNotRecurse = true;
            for (const [delta, guestDeltaMap] of candidates) {
                const haveMissingDependency = delta.getDependencies().some(([dependency]) => !startVersion.contains(dependency));
                if (haveMissingDependency) {
                    printIndent("missing dependency, trying next delta");
                    continue; // skip this delta, but keep it in deltasToTry (its missing dependency may be in deltasToTry)
                }
                // ATTENTION: Constructing embeddings must be made recursive (guest could also be a host)
                // 'delta' can be added
                // printIndent("including", delta, " => new version: ", delta, ...startVersion);
                const createMergedVersionRecursive = (startVersion, [delta, guestDeltaMap]) => {
                    const embeddings = new Map();
                    const selfEmbeddingKeys = new Set();
                    for (const [guestId, [guestDelta, overridings]] of guestDeltaMap.entries()) {
                        const { version: guestStartVersion } = startVersion.getEmbedding(guestId);
                        // console.log(guestId, "guestStartVersion: ", guestStartVersion);
                        let nextGuestVersion;
                        if (guestDelta === null) {
                            nextGuestVersion = guestStartVersion;
                        }
                        else {
                            if (guestStartVersion === startVersion && guestDelta[0] === delta && guestDelta[1] === guestDeltaMap) {
                                selfEmbeddingKeys.add(guestId);
                                continue;
                            }
                            else {
                                nextGuestVersion = createMergedVersionRecursive(guestStartVersion, guestDelta);
                            }
                        }
                        embeddings.set(guestId, { version: nextGuestVersion, overridings });
                    }
                    // printIndent("Creating version (", delta, ...[...startVersion].map(d => d), ") with embeddings", embeddings);
                    const nextVersion = this.createVersion(startVersion, delta, newVersion => {
                        // add self-embeddings:
                        for (const guestId of selfEmbeddingKeys) {
                            embeddings.set(guestId, { version: newVersion, overridings: new Map() });
                        }
                        return embeddings;
                    });
                    // printIndent("Created version (", ...[...nextVersion].map(d => d), ") with embeddings", embeddings);
                    return nextVersion;
                };
                const nextVersion = createMergedVersionRecursive(startVersion, [delta, guestDeltaMap]);
                // current delta does not have to be included again in next loop iterations
                candidates = candidates.filter(([d]) => d !== delta);
                // const [conflicting, nonConflicting] = _.partition(deltasToTry, ([d]) => isConflicting(d, delta));
                const nonConflicting = candidates.filter(([candidate]) => !isConflicting(candidate, delta));
                // if (conflicting.length > 0)
                //   printIndent("will be skipped (conflicts with", delta, "):", ...conflicting);
                depthFirst(nextVersion, nonConflicting, depth + 1);
                couldNotRecurse = false;
                if (nonConflicting.length === candidates.length) {
                    // all deltas from deltasToTry were included -> no need to try alternatives
                    break;
                }
            }
            if (couldNotRecurse) {
                // possibly have a new maximal version
                if (!result.some(v => startVersion.isSubSetOf(v))) {
                    // printIndent("new result");
                    result.push(startVersion);
                }
            }
        };
        depthFirst(lca, diff, 0);
        // printDebug("result of merge:", ..._.flatten(result.map(v => [...v, ","])));
        return result;
    }
    // Idempotent
    // Calls the merge-function for every permutation of 'versions'
    // This is useful for didactic purposes: a path is created from every input to at least one output.
    // Of course it won't scale to many inputs.
    crazyMerge(versions, debugNames) {
        let result;
        for (const v of (0, permutations_1.permutations)(versions)) {
            // whatever the permutation, result will always be the same:
            result = this.merge(v, debugNames);
        }
        return result;
    }
}
exports.VersionRegistry = VersionRegistry;
//# sourceMappingURL=version.js.map