onion-core/test/version.test.ts

import * as _ from "lodash";

import {
  Version,
  VersionRegistry,
  // embed,
  // overrideDeltas,
} from "../lib/version";

import {
  Delta,
} from "../lib/delta";

import {DeltaRegistry} from "../lib/delta_registry";

import {
  mockUuid,
} from "../lib/util/test_helpers";

import {
  assert,
  assertThrows,
} from "../lib/util/assert";

describe("Version", () => {

  it("Get deltas", () => {
    const deltaRegistry = new DeltaRegistry();
    const getId = mockUuid();
    const registry = new VersionRegistry();

    const nodeCreation = deltaRegistry.newNodeCreation(getId());
    const nodeDeletion = deltaRegistry.newNodeDeletion(nodeCreation, [], []);

    const version1 = registry.createVersion(registry.initialVersion, nodeCreation);
    const version2 = registry.createVersion(version1, nodeDeletion);

    assert(_.isEqual([... registry.initialVersion], []), "expected initialVersion to be empty");
    assert(_.isEqual([... version1], [nodeCreation]), "expected version1 to contain creation");
    assert(_.isEqual([... version2], [nodeDeletion, nodeCreation]), "expected version2 to contain creation and deletion");
  });

  it("Commutating operations yield equal versions", () => {
    const deltaRegistry = new DeltaRegistry();
    const getId = mockUuid();
    const registry = new VersionRegistry();

    const nodeCreationA = deltaRegistry.newNodeCreation(getId());
    const nodeCreationB = deltaRegistry.newNodeCreation(getId());

    const versionA = registry.createVersion(registry.initialVersion, nodeCreationA);
    const versionAB = registry.createVersion(versionA, nodeCreationB);

    const versionB = registry.createVersion(registry.initialVersion, nodeCreationB);
    const versionBA = registry.createVersion(versionB, nodeCreationA);

    assert(versionAB === versionBA, "expected versions to be equal");
  });

  it("Intersection", () => {
    const deltaRegistry = new DeltaRegistry();
    const getId = mockUuid();
    const registry = new VersionRegistry();

    const A = deltaRegistry.newNodeCreation(getId());
    const B = deltaRegistry.newNodeCreation(getId());
    const C = deltaRegistry.newNodeCreation(getId());
    const D = deltaRegistry.newNodeDeletion(A, [], []);

    const v1 = registry.quickVersion([D,B,A]);
    const v2 = registry.quickVersion([C,B]);

    const intersection0 = registry.getIntersection([v1, v2]);
    assert(intersection0 === registry.quickVersion([B]), "expected intersection of v1 and v2 to be B.");

    const intersection1 = registry.getIntersection([v1, v1]);
    assert(intersection1 === v1, "expected intersection of v1 with itself to be v1");

    const intersection2 = registry.getIntersection([v1]);
    assert(intersection2 === v1, "expected intersection of v1 with itself to be v1");

    const intersection3 = registry.getIntersection([]);
    assert(intersection3 === registry.initialVersion, "expected intersection of empty set to be initial (empty) version");
  });


  describe("Merging", () => {
    // Helper
    function mergeAgain(registry, merged, nameMap?) {
      const mergedAgain = registry.merge(merged, nameMap);
      assert(mergedAgain.length === merged.length
        && mergedAgain.every(version => merged.includes(version)),
        "merging a merge result should just give the same result again.");
    }

    it("Merge empty set", () => {
      const registry = new VersionRegistry();
      const merged = registry.merge([]);
      assert(merged.length === 1 && merged[0] === registry.initialVersion, "expected intial version");

      mergeAgain(registry, merged);
    })

    it("Merge non-conflicting versions", () => {
      const deltaRegistry = new DeltaRegistry();
      const getId = mockUuid();
      const registry = new VersionRegistry();

      const nodeCreationA = deltaRegistry.newNodeCreation(getId());
      const nodeCreationB = deltaRegistry.newNodeCreation(getId());

      const versionA = registry.createVersion(registry.initialVersion, nodeCreationA);
      const versionB = registry.createVersion(registry.initialVersion, nodeCreationB);

      const nameMap = new Map([[nodeCreationA, "A"], [nodeCreationB, "B"]]);

      const merged = registry.merge([versionA, versionB], delta => nameMap.get(delta)!);
      assert(merged.length === 1, "expected 1 merged version");

      const deltas = [... merged[0]];
      assert(deltas.length === 2
        && deltas.includes(nodeCreationA)
        && deltas.includes(nodeCreationB),
        "expected merged version to contain nodes A and B");

      mergeAgain(registry, merged, delta => nameMap.get(delta)!);
    });

    it("Merge complex conflicting versions", () => {
      const deltaRegistry = new DeltaRegistry();
      const getId = mockUuid();
      const registry = new VersionRegistry();

      // the names of the deltas and the versions in this test trace back to an illustration in a Xournal++ file.

      const X = deltaRegistry.newNodeCreation(getId());
      const Y = deltaRegistry.newNodeCreation(getId());
      const Z = deltaRegistry.newNodeCreation(getId());

      const A = deltaRegistry.newNodeDeletion(X, [], []);
      const B0 = deltaRegistry.newEdgeCreation(X, "label");
      const B = deltaRegistry.newEdgeUpdate(B0, Y); // conflicts with A
      assert(_.isEqual(B.conflictsWith, [[A, 'U/D']]), "Expected B to conflict with A");
      const C0 = deltaRegistry.newEdgeCreation(Y, "label");
      const C = deltaRegistry.newEdgeUpdate(C0, Z);
      const BB = deltaRegistry.newEdgeUpdate(B.overwrite(), null); // unset edge B.
      const D = deltaRegistry.newNodeDeletion(Y, [], [BB]); // conflicts with C

      assert(_.isEqual(D.conflictsWith, [[C, 'U/D']]), "Expected D to conflict with C");

      const nameMap: Map<Delta, string> = new Map<Delta,string>([
        [X, "X"],
        [Y, "Y"],
        [Z, "Z"],
        [A, "A"],
        [B0, "B0"],
        [B, "B"],
        [BB, "BB"],
        [C0, "C0"],
        [C, "C"],
        [D, "D"],
      ]);

      const three = registry.quickVersion([A,X,Y,Z]);
      const seven = registry.quickVersion([C,C0,X,Y,Z]);
      const five  = registry.quickVersion([D,BB,B,B0,X,Y,Z]);

      const merged = registry.merge([three, seven, five], d => nameMap.get(d)!);
      assert(merged.length === 3, "expected three maximal versions");
      // assert(merged.includes(registry.quickVersion([A,C,C0,X,Y,Z])), "expected [X,Y,Z,A,C] to be a maximal version");
      // assert(merged.includes(registry.quickVersion([BB,B,B0,C,C0,X,Y,Z])), "expected [X,Y,Z,B,C] to be a maximal version");
      // assert(merged.includes(registry.quickVersion([D,BB,B,B0,X,Y,Z])), "expected [X,Y,Z,B,D] to be a maximal version");

      mergeAgain(registry, merged, d => nameMap.get(d)!);
    });

    it("Merge many non-conflicting versions (scalability test)", () => {
      const deltaRegistry = new DeltaRegistry();
      const getId = mockUuid();
      const registry = new VersionRegistry();

      // Bunch of non-conflicting deltas:
      const deltas: Array<Delta> = [];
      const nameMap = new Map();
      for (let i=0; i<10; i++) {
        const delta = deltaRegistry.newNodeCreation(getId());
        deltas.push(delta);
        nameMap.set(delta, i.toString());
      }
      // Create a version for each delta, containing only that delta:
      const versions = deltas.map(d => registry.createVersion(registry.initialVersion, d));

      const merged = registry.merge(versions, d => nameMap.get(d)!);
      assert(merged.length === 1, "only one merged version should result");

      const mergedAgain = registry.merge(merged, d => nameMap.get(d)!);
      assert(mergedAgain.length === merged.length
        && mergedAgain.every(version => merged.includes(version)),
        "merging a merge result should just give the same result again.");
    });

    it("Merge many conflicting versions (scalability test 2)", () => {
      const deltaRegistry = new DeltaRegistry();
      const getId = mockUuid();
      const registry = new VersionRegistry();

      const HOW_MANY = 3;

      const versions: Array<Version> = [];

      const nameMap = new Map();

      for (let i=0; i<HOW_MANY; i++) {
        const creation = deltaRegistry.newNodeCreation(getId());
        const deletion = deltaRegistry.newNodeDeletion(creation, [], []);
        const edgeCreation = deltaRegistry.newEdgeCreation(creation, "l");
        const edgeUpdate = deltaRegistry.newEdgeUpdate(edgeCreation, creation); // conflicts with deletion0

        nameMap.set(creation, "C"+i.toString());
        nameMap.set(deletion, "D"+i.toString());
        nameMap.set(edgeCreation, "EC"+i.toString());
        nameMap.set(edgeUpdate, "EU"+i.toString());

        versions.push(registry.quickVersion([deletion, creation]));
        versions.push(registry.quickVersion([edgeUpdate, edgeCreation, creation]));
      }

      const merged = registry.merge(versions, d => nameMap.get(d)!);
      assert(merged.length === Math.pow(2, HOW_MANY), HOW_MANY.toString() + " binary choices should result in " + Math.pow(2,HOW_MANY).toString() + " possible conflict resolutions and therefore merge results.");

      console.log("merging again...");
      mergeAgain(registry, merged, d => nameMap.get(d)!);
    });
  });

  describe("Embedding of versions", () => {
    it("Creating embedded versions", () => {
      const deltaRegistry = new DeltaRegistry();
      const getId = mockUuid();
      const registry = new VersionRegistry();

      const guestCreate = deltaRegistry.newNodeCreation(getId());
      const guestV1 = registry.createVersion(registry.initialVersion, guestCreate);

      const guestDel = deltaRegistry.newNodeDeletion(guestCreate, [], []);
      const guestV2 = registry.createVersion(guestV1, guestDel);

      const hostCreate = deltaRegistry.newNodeCreation(getId());
      const hostEdgeCreate = deltaRegistry.newEdgeCreation(hostCreate, "guest")
      const hostLink = deltaRegistry.newEdgeUpdate(hostEdgeCreate, guestCreate);
      const allCreate = deltaRegistry.newTransaction([guestCreate, hostCreate, hostEdgeCreate, hostLink], "");
      const hostV1 = registry.createVersion(registry.initialVersion, allCreate, () => new Map([
        ["guest", {version: guestV1, overridings: new Map()}], // no overridings
      ]));

      const hostUnlink = deltaRegistry.newEdgeUpdate(hostLink.overwrite(), null);
      const hostDel = deltaRegistry.newNodeDeletion(hostCreate, [hostUnlink], []);

      const guestDelOverride = deltaRegistry.newNodeDeletion(guestCreate, [], [hostUnlink]);
      const allDel = deltaRegistry.newTransaction([hostUnlink, hostDel, guestDelOverride], "");

      assertThrows(() => {
        registry.createVersion(hostV1, allDel, () => new Map([
          ["guest", {version: guestV2, overridings: new Map()}]
        ]));
      }, "should not be able to create host version without explicitly stating that guestDel was overridden by guestDelOver");

      const hostV2 = registry.createVersion(hostV1, allDel, () => new Map([
          ["guest", {version: guestV2, overridings: new Map([[guestDel, guestDelOverride]])}],
        ]));
    });

    it("Merging host versions", () => {
      const deltaRegistry = new DeltaRegistry();
      const getId = mockUuid();
      const registry = new VersionRegistry();

      const createA = deltaRegistry.newNodeCreation(getId());
      const createB = deltaRegistry.newNodeCreation(getId());

      const guestA = registry.createVersion(registry.initialVersion, createA);
      const guestB = registry.createVersion(registry.initialVersion, createB);

      const createC = deltaRegistry.newNodeCreation(getId());
      const createD = deltaRegistry.newNodeCreation(getId());

      const createAC = deltaRegistry.newTransaction([createA, createC], "");
      const createBD = deltaRegistry.newTransaction([createB, createD], "");

      const debugNames = new Map<Delta,string>([
        [createA, "createA"],
        [createB, "createB"],
        [createC, "createC"],
        [createD, "createD"],
        [createAC, "createAC"],
        [createBD, "createBD"],
      ]);

      const hostAC = registry.createVersion(registry.initialVersion, createAC, () => new Map([
        ["guest", {version: guestA, overridings: new Map()}],
      ]));
      const hostBD = registry.createVersion(registry.initialVersion, createBD, () => new Map([
        ["guest", {version: guestB, overridings: new Map()}],
      ]));

      console.log("Merging hosts...");
      const mergedHosts = registry.merge([hostAC, hostBD], d => debugNames.get(d)!);
      assert(mergedHosts.length === 1, "expected no host merge conflict");

      console.log("Merging guests...");
      const mergedGuests = registry.merge([guestA, guestB], d => debugNames.get(d)!);
      assert(mergedGuests.length === 1, "expected no guest merge conflict");

      const [guestAB] = mergedGuests;
      const [hostABCD] = mergedHosts;

      const {version: mergedGuest, overridings: mergedOverridings} = hostABCD.getEmbedding("guest");
      assert(mergedGuest === guestAB, "merged host should embed merged guest");

      assert(mergedOverridings.size === 0, "expected no overridings in merged embedding");
    });

    it("Multi-level embedding", () => {
      const deltaRegistry = new DeltaRegistry();
      const getId = mockUuid();
      const registry = new VersionRegistry();

      const createA = deltaRegistry.newNodeCreation(getId());
      const createB = deltaRegistry.newNodeCreation(getId());
      const createC = deltaRegistry.newNodeCreation(getId());

      const createAB = deltaRegistry.newTransaction([createA, createB], "");
      const createABC = deltaRegistry.newTransaction([createAB, createC], "");

      const vA = registry.createVersion(registry.initialVersion, createA);
      const vAB = registry.createVersion(registry.initialVersion, createAB, () => new Map([
        ["L0", {version: vA, overridings: new Map()}],
      ]));
      const vABC = registry.createVersion(registry.initialVersion, createABC, () => new Map([
        ["L1", {version: vAB, overridings: new Map()}],
      ]));

      const createD = deltaRegistry.newNodeCreation(getId());
      const createE = deltaRegistry.newNodeCreation(getId());
      const createF = deltaRegistry.newNodeCreation(getId());

      const createDE = deltaRegistry.newTransaction([createD, createE], "");
      const createDEF = deltaRegistry.newTransaction([createDE, createF], "");

      const vD = registry.createVersion(registry.initialVersion, createD);
      const vDE = registry.createVersion(registry.initialVersion, createDE, () => new Map([
        ["L0", {version: vD, overridings: new Map()}],
      ]));
      const vDEF = registry.createVersion(registry.initialVersion, createDEF, () => new Map([
        ["L1", {version: vDE, overridings: new Map()}],
      ]));

      const [vABCDEF] = registry.merge([vABC, vDEF]);

      const vABDE = vABCDEF.embeddings.get("L1")?.version;

      assert(vABDE !== undefined,     "No L1 merged version");
      assert([...vABDE!].length === 2, "L1 merge result unexpected number of deltas: " + [...vABDE!].length);

      const vAD = vABDE!.embeddings.get("L0")?.version;

      assert(vAD !== undefined, "No L0 merged version");
      assert([...vAD!].length === 2, "L1 merge result unexpected number of deltas: " + [...vAD!].length);
    });

    it("Self-embedding", () => {
      const deltaRegistry = new DeltaRegistry();
      const getId = mockUuid();
      const registry = new VersionRegistry();

      const createA = deltaRegistry.newNodeCreation(getId());
      const createB = deltaRegistry.newNodeCreation(getId());

      const vA = registry.createVersion(registry.initialVersion, createA, version => new Map([
        ["self", {version, overridings: new Map()}]]));
      const vB = registry.createVersion(registry.initialVersion, createB, version => new Map([
        ["self", {version, overridings: new Map()}]]));

      const [vAB] = registry.merge([vA, vB]);

      assert(vAB.embeddings.get("self") !== undefined, "Expected merge result to embed itself");
    })
  });
});