onion-core/src/onion/version.test.ts

import * as _ from "lodash";

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

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

import {
  NodeCreation,
  NodeDeletion,
  EdgeCreation,
  EdgeUpdate,
} from "./primitive_delta";

import {
  CompositeLevel,
} from "./composite_delta"

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

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

describe("Version", () => {

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

    const nodeCreation = new NodeCreation(getId());
    const nodeDeletion = new NodeDeletion(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 getId = mockUuid();
    const registry = new VersionRegistry();

    const nodeCreationA = new NodeCreation(getId());
    const nodeCreationB = new NodeCreation(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 getId = mockUuid();
    const registry = new VersionRegistry();

    const A = new NodeCreation(getId());
    const B = new NodeCreation(getId());
    const C = new NodeCreation(getId());
    const D = new NodeDeletion(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([], new Map());
      assert(merged.length === 1 && merged[0] === registry.initialVersion, "expected intial version");

      mergeAgain(registry, merged, new Map());
    })

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

      const nodeCreationA = new NodeCreation(getId());
      const nodeCreationB = new NodeCreation(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], nameMap);
      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, nameMap);
    });

    it("Merge complex conflicting versions", () => {
      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 = new NodeCreation(getId());
      const Y = new NodeCreation(getId());
      const Z = new NodeCreation(getId());

      const A = new NodeDeletion(X, [], []);
      const B = new EdgeCreation(X, "label", Y); // conflicts with A
      assert(_.isEqual(B.getConflicts(), [A]), "Expected B to conflict with A");
      const C = new EdgeCreation(Y, "label", Z);
      const BB = new EdgeUpdate(B, null); // unset edge B.
      const D = new NodeDeletion(Y, [], [BB]); // conflicts with C

      assert(_.isEqual(D.getConflicts(), [C]), "Expected D to conflict with C");

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

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

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

      mergeAgain(registry, merged, nameMap);
    });

    it("Merge many non-conflicting versions (scalability test)", () => {
      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 = new NodeCreation(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, nameMap);
      assert(merged.length === 1, "only one merged version should result");

      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 many conflicting versions (scalability test)", () => {
      const getId = mockUuid();
      const registry = new VersionRegistry();

      const HOW_MANY = 3;

      const creations: Array<Delta> = [];
      const deletions: Array<Delta> = [];
      const edges: Array<Delta> = [];
      const versions: Array<Version> = [];

      const nameMap = new Map();

      for (let i=0; i<HOW_MANY; i++) {
        const creation = new NodeCreation(getId());
        const deletion = new NodeDeletion(creation, [], []);
        const edge = new EdgeCreation(creation, "l", creation); // conflicts with deletion0

        creations.push(creation);
        deletions.push(deletion);
        edges.push(edge);

        nameMap.set(creation, "C"+i.toString());
        nameMap.set(deletion, "D"+i.toString());
        nameMap.set(edge, "E"+i.toString());

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

      const merged = registry.merge(versions, nameMap);
      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.");

      mergeAgain(registry, merged, nameMap);
    });
  });

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

  //     const lvl1 = new CompositeLevel(); // transactions on CS or CORR
  //     const lvl2 = new CompositeLevel(); // transactions on CS+CORR

  //     // CS: a node is created, then deleted
  //     const csNode = new NodeCreation(getId());
  //     const csDel = new NodeDeletion(csNode, [], []);

  //     const csNodeLvl1 = lvl1.createComposite([csNode]);
  //     const csDelLvl1 = lvl1.createComposite([csDel]);

  //     const csV1 = registry.createVersion(initialVersion, csNodeLvl1);
  //     const csV2 = registry.createVersion(csV1, csDelLvl1);

  //     // CORR: a link is created from a corr-node to the cs-node, followed by the deletion of the corr-node
  //     // const corrLink = corrLvl.createComposite([csNode, new NodeCreation(getId()), corrLink]);
  //     const corrNode = new NodeCreation(getId());
  //     const corrLink = new EdgeCreation(corrNode, "cs", csNode);
  //     const corrDel = new NodeDeletion(corrNode, [corrLink], []);

  //     const corrLinkLvl1 = lvl1.createComposite([corrNode, corrLink]);

  //     const csCorrLinkLvl2 = lvl2.createComposite([csNodeLvl1, corrLinkLvl1]);

  //     // Patch: in order to avoid a conflict between csDel and corrLink, in corrV2, we override csDel by csDel1.
  //     const csDel1 = new NodeDeletion(csNode, [], [corrDel]);

  //     const corrDelLvl1 = lvl1.createComposite([corrDel]);
  //     const csDel1Lvl1 = lvl1.createComposite([csDel1]);

  //     const csCorrDelLvl2 = lvl2.createComposite([corrDelLvl1, csDel1Lvl1]);

  //     const corrV1 = registry.createVersion(initialVersion, csCorrLinkLvl2, embed(["cs", csV1, overrideDeltas()]));
  //     const corrV2 = registry.createVersion(corrV1, csCorrDelLvl2, embed(["cs", csV2, overrideDeltas( [csDel, csDel1] )]));

  //     assertThrows(() => {
  //       // same as above, but without the overridden deltas:
  //       registry.createVersion(corrV1, csCorrDelLvl2, embed(["cs", csV2, overrideDeltas()])); // should throw
  //     }, "should not be able to create a version that embeds csV2 without overriding csDel");
  //   });
  // });
});