onion-core/dist/lib/delta.js

"use strict";
Object.defineProperty(exports, "__esModule", { value: true });
exports.findTxDependencies = exports.Transaction = exports.EdgeUpdate = exports.TargetValue = exports.TargetNode = exports.ExistingEdge = exports.NewEdge = exports.Edge = exports.NodeDeletion = exports.ReadAllOutgoing = exports.NodeCreation = exports.PrimitiveDelta = exports.Delta = void 0;
const buffer_xor_1 = require("./util/buffer_xor");
class Delta {
    constructor(hash, description) {
        this.conflictsWith = [];
        this.partOf = [];
        this.hash = hash;
        this.description = description;
    }
    hasTransitiveDependency(other) {
        if (this === other)
            return true;
        for (const [d] of this.getDependencies()) {
            if (d.hasTransitiveDependency(other))
                return true;
        }
        return false;
    }
    serialize() {
        return {
            hash: this.hash.toString('hex'),
            type: this.constructor.name,
        };
    }
}
exports.Delta = Delta;
class PrimitiveDelta extends Delta {
    // constructor(hash: Buffer, description: string) {
    //   super(has, description);
    // }
    *iterPrimitiveDeltas() {
        yield this;
    }
}
exports.PrimitiveDelta = PrimitiveDelta;
function registerConflict(d1, d2, type) {
    d1.conflictsWith.push([d2, type]);
    d2.conflictsWith.push([d1, type]);
}
class NodeCreation extends PrimitiveDelta {
    constructor(hash, id) {
        super(hash, `NEW(${JSON.stringify(id)})`);
        // Inverse dependencies
        this.outgoingEdges = new Map();
        this.incomingEdges = []; // all deltas EVER that set this node as target of an edge.
        this.readAllOutgoing = [];
        this.deletions = [];
        this.id = id;
    }
    getDependencies() {
        return [];
    }
    createOutgoingEdge(label, after = []) {
        const edgeId = label + ':' + (0, buffer_xor_1.buffersXOR)(...after.map(a => a.hash)).toString('hex');
        return this.outgoingEdges.get(edgeId) || (() => {
            const newEdge = new NewEdge(this, label, after, edgeId);
            this.outgoingEdges.set(edgeId, newEdge);
            return newEdge;
        })();
    }
    registerOutgoingEdge(u) {
        // A new outgoing edge will always conflict with all existing deletions.
        for (const d of this.deletions) {
            registerConflict(d, u, "U/D");
        }
        for (const r of this.readAllOutgoing) {
            if (!u.overwrites.after.includes(r)) {
                registerConflict(r, u, "R*/U");
            }
        }
        // outgoing edge already stored in Edge.
    }
    registerIncomingEdge(u) {
        // A new incoming edge always will conflict with all existing deletions.
        for (const d of this.deletions) {
            registerConflict(d, u, "U/D");
        }
        this.incomingEdges.push(u);
    }
    registerDeletion(d) {
        // A new deletion will conflict with all earliest incoming/outgoing edge operations that the deletion does not transitively explicitly depend on.
        for (const o of this.outgoingEdges.values()) {
            for (const u of o.iterOverwriters(u => !d.afterSrc.some(a => a.hasTransitiveDependency(u)))) {
                registerConflict(d, u, "U/D");
            }
        }
        for (const i of this.incomingEdges.filter(i => !d.afterTgt.some(a => a.hasTransitiveDependency(i)))) {
            registerConflict(i, d, "U/D");
        }
        // Delete/Delete conflict
        for (const other of this.deletions) {
            if (other !== d) {
                registerConflict(d, other, "D/D");
            }
        }
        this.deletions.push(d);
    }
    registerReadAllOutgoing(r) {
        // ReadAllOutgoing will conflict with all outgoing edge creations that are not a dependency of ReadAllOutgoing
        // (in essence just a R/W conflict)
        for (const o of this.outgoingEdges.values()) {
            if (!r.after.includes(o)) {
                // TODO: We could turn NewEdge into an actual delta type. Then we could just conflict with that delta (possibly more efficient, maybe more elegant)
                for (const u of o.overwrittenBy) {
                    registerConflict(r, u, "R*/U");
                }
            }
        }
        this.readAllOutgoing.push(r);
    }
    serialize() {
        return Object.assign(Object.assign({}, super.serialize()), { id: this.id });
    }
}
exports.NodeCreation = NodeCreation;
// This delta represents getting all outgoing edges of a node.
// For instance, when getting all the elements of a set (e.g., when checking some constraint), or iterating over a dictionary.
class ReadAllOutgoing extends PrimitiveDelta {
    constructor(hash, node, after) {
        super(hash, `R*(${node.id})`);
        this.node = node;
        this.after = after;
        // Register inverse dependencies:
        node.registerReadAllOutgoing(this);
    }
    getDependencies() {
        return [
            [this.node, "N"],
            ...[].concat(...this.after.map(a => a.overwrittenBy.map(u => [u, "A"]))),
        ];
    }
}
exports.ReadAllOutgoing = ReadAllOutgoing;
class NodeDeletion extends PrimitiveDelta {
    constructor(hash, node, afterSrc, afterTgt) {
        super(hash, `DEL(${JSON.stringify(node.id)})`);
        this.node = node;
        this.afterSrc = afterSrc;
        this.afterTgt = afterTgt;
        if (afterSrc.some(a => a.target.value !== null)) {
            throw new Error("NodeDeletion can only depend on EdgeUpdates that set outgoing edges to null.");
        }
        if (afterTgt.some(a => a.target.value === node)) {
            throw new Error("NodeDeletion cannot depend on EdgeUpdates that set incoming edges to node being deleted.");
        }
        // Register our dependencies' inverse dependencies + detect conflicts:
        node.registerDeletion(this);
    }
    getDependencies() {
        return [
            [this.node, "D"],
            ...this.afterSrc.map(u => [u, "A"]),
            ...this.afterTgt.map(u => [u, "A"]),
        ];
    }
    serialize() {
        return Object.assign(Object.assign({}, super.serialize()), { node: this.node.hash.toString('hex'), afterSrc: this.afterSrc.map(u => u.hash.toString('hex')), afterTgt: this.afterTgt.map(u => u.hash.toString('hex')) });
    }
}
exports.NodeDeletion = NodeDeletion;
// Detects write/write and write/read conflicts.
class Edge {
    constructor(source, label) {
        // Inverse dependencies
        this.overwrittenBy = [];
        this.readBy = [];
        this.source = source;
        this.label = label;
    }
    // Iterate over all overwriters, from early to late, depth-first.
    // When in some branch the 'condition' is satisfied, the satisfying element is yielded, and the descendants ignored.
    *iterOverwriters(filter) {
        for (const ovr of this.overwrittenBy) {
            if (filter(ovr)) {
                yield ovr;
            }
            else {
                yield* ovr.overwritable.iterOverwriters(filter);
            }
        }
    }
    registerWrite(write) {
        for (const other of this.overwrittenBy) {
            // A write conflicts with all other writes:
            registerConflict(write, other, "U/U");
        }
        for (const read of this.readBy) {
            if (read !== write && !write.afterReads.includes(read)) {
                // A write conflicts with all reads:
                registerConflict(read, write, "R/U");
            }
        }
        this.overwrittenBy.push(write);
        // Also check conflicts with deletions of source:
        this.source.registerOutgoingEdge(write);
    }
    registerRead(read) {
        for (const write of this.overwrittenBy) {
            if (read !== write) {
                // A read conflicts with all writes:
                registerConflict(read, write, "R/U");
            }
        }
        this.readBy.push(read);
    }
}
exports.Edge = Edge;
// An Edge that does not yet have a target
class NewEdge extends Edge {
    constructor(source, label, after, edgeId) {
        super(source, label);
        this.after = after;
        this.edgeId = edgeId;
    }
    getDependencies() {
        return [[this.source, "SRC"]];
    }
    serialize() {
        return {
            type: "NewEdge",
            source: this.source.hash.toString('hex'),
            label: this.label,
        };
    }
}
exports.NewEdge = NewEdge;
// An Edge that has been assigned a target (by an EdgeUpdate) at least once.
class ExistingEdge extends Edge {
    constructor(source, label, delta) {
        super(source, label);
        this.delta = delta;
    }
    getDependencies() {
        return [[this.delta, "U"]];
    }
    serialize() {
        return {
            type: "ExistingEdge",
            overwrites: this.delta.hash.toString('hex'),
        };
    }
}
exports.ExistingEdge = ExistingEdge;
class TargetNode {
    constructor(value) {
        this.value = value;
    }
    registerDependency(u) {
        this.value.registerIncomingEdge(u);
    }
    getDependencies() {
        return [[this.value, "TGT"]];
    }
    serialize() {
        return { type: "TargetNode", node: this.value.hash.toString('hex') };
    }
}
exports.TargetNode = TargetNode;
class TargetValue {
    constructor(value) {
        this.value = value;
    }
    registerDependency() { }
    getDependencies() {
        return [];
    }
    serialize() {
        return { type: "TargetValue", value: this.value };
    }
}
exports.TargetValue = TargetValue;
class EdgeUpdate extends PrimitiveDelta {
    constructor(hash, overwrites, target, reads, afterReads) {
        super(hash, `U(${overwrites.label}->${target.value instanceof NodeCreation ? target.value.description : target.value})`);
        // Record our own dependencies:
        this.overwrites = overwrites;
        this.target = target;
        this.reads = reads;
        this.afterReads = afterReads;
        this.overwritable = new ExistingEdge(overwrites.source, overwrites.label, this);
        // Register our dependencies' inverse dependencies + detect conflicts:
        overwrites.registerWrite(this);
        reads.forEach(r => r.registerRead(this));
        target.registerDependency(this);
    }
    // Makes code slightly easier to read
    overwrite() {
        return this.overwritable;
    }
    // Makes code slightly easier to read
    read() {
        return this.overwritable;
    }
    getDependencies() {
        return this.overwrites.getDependencies()
            .concat(this.target.getDependencies())
            .concat(this.reads.map(r => [r.delta, "R"]))
            .concat(this.afterReads.map(a => [a, "A"]));
    }
    serialize() {
        return Object.assign(Object.assign({}, super.serialize()), { overwrites: this.overwrites.serialize(), target: this.target.serialize(), reads: this.reads.map(r => r.serialize()), afterReads: this.afterReads.map(a => a.hash.toString('hex')) });
    }
}
exports.EdgeUpdate = EdgeUpdate;
// export class EdgeRead extends PrimitiveDelta {
//   // Every read has a unique ID (otherwise, different concurrent reads would be represented by the same delta)
//   readonly id: UUID;
//   // Dependencies
//   readonly reads: ExistingEdge;
//   constructor(hash: Buffer, id: UUID, reads: ExistingEdge) {
//     super(hash, `R(${reads.label})`);
//     // Record our own dependencies:
//     this.reads = reads;
//     reads.registerRead(this);
//   }
//   serialize(): any {
//     return {
//       ...super.serialize(),
//       id: this.id,
//       reads: this.reads.map(r => r.serialize()),
//     };
//   }
// }
class Transaction extends Delta {
    constructor(hash, deltas, description, dependencies) {
        super(hash, description);
        this.deltas = deltas;
        this.dependencies = dependencies;
        // TODO: validate dependencies.
        // Derive conflicts from deltas
        for (const delta of deltas) {
            for (const [conflictingDelta, conflictType] of delta.conflictsWith) {
                if (deltas.includes(conflictingDelta)) {
                    throw new Error("Cannot create a composite delta out of conflicting deltas");
                }
                const conflictingTxs = conflictingDelta.partOf;
                for (const otherTx of conflictingTxs) {
                    if (!this.conflictsWith.some(([c]) => c === otherTx)) {
                        registerConflict(this, otherTx, conflictType);
                    }
                }
            }
        }
        for (const [dependency] of dependencies) {
            for (const [c, conflictKind] of this.conflictsWith) {
                if (c === dependency) {
                    // // only for debugging, print all the detailed dependencies:
                    // const detailedDependencies: [Delta,Delta,string][] = [];
                    // for (const d of deltas) {
                    //   for (const d2 of dependency.deltas) {
                    //     for (const [dd, kind] of d.getDependencies()) {
                    //       if (dd === d2) {
                    //         detailedDependencies.push([d, d2, kind]);
                    //       }
                    //     }
                    //   }
                    // }
                    // console.log({tx: deltas, dependency: dependency.deltas, detailedDependencies});
                    throw new Error(`Assertion failed: Transaction '${description}' (${hash.toString('hex').substring(0, 8)}) depends on another conflicting (${conflictKind}) transaction '${dependency.description}' (${dependency.hash.toString('hex').substring(0, 8)}).`);
                }
            }
        }
        deltas.forEach(d => d.partOf.push(this));
    }
    getDependencies() {
        return this.dependencies;
    }
    serialize() {
        return Object.assign(Object.assign({}, super.serialize()), { deltas: this.deltas.map(d => d.hash.toString('hex')), description: this.description, dependencies: this.dependencies.map(([d, kind]) => ({ tx: d.hash.toString('hex'), kind })) });
    }
    *iterPrimitiveDeltas() {
        for (const d of this.deltas) {
            yield* d.iterPrimitiveDeltas();
        }
    }
}
exports.Transaction = Transaction;
// Given a set of deltas that we are trying to glue together in a (new) transaction, what other transactions should this new transaction depend on?
// Argument 'currentDeltas' is a set of deltas to be considered as possible dependencies. Typically you only want to consider the deltas that make up the current version. This is decide which transaction to depend on, if a delta is contained by multiple transactions. If this argument is left undefined, then an error will be thrown if one of the deltas is contained by multiple transactions.
function findTxDependencies(deltas, candidates) {
    const txDependencies = new Map();
    for (const delta of deltas) {
        const dependencies = delta.getDependencies();
        for (const [dependency, kind] of dependencies) {
            if (!deltas.includes(dependency)) {
                const txs = dependency.partOf;
                const filteredTxs = candidates !== undefined
                    ? txs.filter(tx => candidates.has(tx))
                    : txs;
                if (filteredTxs.length > 1) {
                    // This error can never occur when passing a proper 'candidates' argument.
                    throw new Error("Error: One of the composite's dependencies is contained by multiple composites.");
                }
                if (filteredTxs.length === 0) {
                    throw new Error("Assertion failed: delta " + delta.description + " depends on " + dependency.description + " but this dependency could not be found in a composite.");
                }
                const [tx] = filteredTxs;
                const kinds = txDependencies.get(tx) || (() => {
                    const kinds = new Set();
                    txDependencies.set(tx, kinds);
                    return kinds;
                })();
                kinds.add(kind);
            }
        }
    }
    return [...txDependencies.entries()].map(([tx, kinds]) => [tx, [...kinds.values()].join(',')]);
}
exports.findTxDependencies = findTxDependencies;
//# sourceMappingURL=delta.js.map