Repository: blitz-js/superjson
Pull request #47 (2020-08-03 20:24:19)

Compress paths into tree
Depends on #37, #36

This PR implements Idea 1 described in #11.

Instead of saving paths like so ...

```json
{
  "a.deep.nested.path.containing.multiple.keys": "map",
  "a.deep.nested.path.containing.multiple.keys.a": "number",
  "a.deep.nested.path.containing.multiple.keys.b": "number",
}
```

... we save it like so:

```json
{
  "a.deep.nested.path.containing.multiple.keys": [
    "map",
    { "a": ["number"], "b": ["number"] }
  ]
}
```


Patch:
diff --git a/README.md b/README.md
index f580a7d..dffc73c 100644
--- a/README.md
+++ b/README.md
@@ -98,8 +98,8 @@ json = {
 
 // note that `normal` is not included here; `meta` only has special cases
 meta = {
-  timestamp: 'date',
-  test: 'regexp',
+  timestamp: ['date'],
+  test: ['regexp'],
 };
 */
 ```
diff --git a/src/annotator.ts b/src/annotator.ts
index 3ae71ad..3e4f461 100644
--- a/src/annotator.ts
+++ b/src/annotator.ts
@@ -1,12 +1,6 @@
 import { getDeep, setDeep } from './accessDeep';
-import { isPrimitive } from './is';
+import { isPrimitive, isString } from './is';
 import * as IteratorUtils from './iteratorutils';
-import {
-  StringifiedPath,
-  isStringifiedPath,
-  parsePath,
-  stringifyPath,
-} from './pathstringifier';
 import { Walker } from './plainer';
 import {
   TypeAnnotation,
@@ -14,31 +8,31 @@ import {
   transformValue,
   untransformValue,
 } from './transformer';
+import { PathTree } from './pathtree';
 
 export interface Annotations {
-  root?: TypeAnnotation;
-  values?: Record<StringifiedPath, TypeAnnotation>;
-  referentialEqualities?: Record<StringifiedPath, StringifiedPath[]>;
-  referentialEqualitiesRoot?: StringifiedPath[];
+  values?: PathTree.CollapsedRootTree<TypeAnnotation>;
+  referentialEqualities?: PathTree.CollapsedRootTree<
+    PathTree.CollapsedRootTree<string>
+  >;
 }
 
 export function isAnnotations(object: any): object is Annotations {
   try {
-    if (!!object.root && !isTypeAnnotation(object.root)) {
-      return false;
-    }
-
-    if (!!object.values) {
-      return Object.entries(object.values).every(
-        ([key, value]) => isStringifiedPath(key) && isTypeAnnotation(value)
-      );
+    if (object.values) {
+      if (!PathTree.isMinimizedTree(object.values, isTypeAnnotation)) {
+        return false;
+      }
     }
 
-    if (!!object.referentialEqualities) {
-      return Object.entries(object.referentialEqualities).every(
-        ([key, value]) =>
-          isStringifiedPath(key) && (value as string[]).every(isStringifiedPath)
-      );
+    if (object.referentialEqualities) {
+      if (
+        !PathTree.isMinimizedTree(object.referentialEqualities, tree =>
+          PathTree.isMinimizedTree(tree, isString)
+        )
+      ) {
+        return false;
+      }
     }
 
     return true;
@@ -47,105 +41,123 @@ export function isAnnotations(object: any): object is Annotations {
   }
 }
 
-export const makeAnnotator = () => {
-  const annotations: Annotations = {};
+class ValueAnnotationFactory {
+  private tree = PathTree.create<TypeAnnotation | null>(null);
+
+  add(path: any[], annotation: TypeAnnotation) {
+    this.tree = PathTree.append(this.tree, path.map(String), annotation);
+  }
 
-  const objectIdentities = new Map<any, any[][]>();
-  function registerObjectPath(object: any, path: any[]) {
-    const paths = objectIdentities.get(object) ?? [];
+  create() {
+    return PathTree.collapseRoot(this.tree);
+  }
+}
+
+class ReferentialEqualityAnnotationFactory {
+  private readonly objectIdentities = new Map<any, any[][]>();
+
+  register(object: any, path: any[]) {
+    const paths = this.objectIdentities.get(object) ?? [];
     paths.push(path);
-    objectIdentities.set(object, paths);
+    this.objectIdentities.set(object, paths);
   }
 
+  create() {
+    let tree = PathTree.create<PathTree.CollapsedRootTree<string> | null>(null);
+
+    IteratorUtils.forEach(this.objectIdentities.values(), paths => {
+      if (paths.length <= 1) {
+        return;
+      }
+
+      const [shortestPath, ...identicalPaths] = paths
+        .map(path => path.map(String))
+        .sort((a, b) => a.length - b.length);
+
+      let identities = PathTree.create<string | null>(null);
+      for (const identicalPath of identicalPaths) {
+        identities = PathTree.appendPath(identities, identicalPath);
+      }
+
+      const minimizedIdentities = PathTree.collapseRoot(identities);
+      if (!minimizedIdentities) {
+        throw new Error('Illegal State');
+      }
+
+      tree = PathTree.append(tree, shortestPath, minimizedIdentities);
+    });
+
+    return PathTree.collapseRoot(tree);
+  }
+}
+
+class AnnotationFactory {
+  public readonly valueAnnotations = new ValueAnnotationFactory();
+  public readonly objectIdentities = new ReferentialEqualityAnnotationFactory();
+
+  create(): Annotations {
+    const annotations: Annotations = {};
+
+    const values = this.valueAnnotations.create();
+    if (values) {
+      annotations.values = values;
+    }
+
+    const referentialEqualities = this.objectIdentities.create();
+    if (referentialEqualities) {
+      annotations.referentialEqualities = referentialEqualities;
+    }
+
+    return annotations;
+  }
+}
+
+export const makeAnnotator = () => {
+  const annotationFactory = new AnnotationFactory();
+  const { valueAnnotations, objectIdentities } = annotationFactory;
+
   const annotator: Walker = ({ path, node }) => {
     if (!isPrimitive(node)) {
-      registerObjectPath(node, path);
+      objectIdentities.register(node, path);
     }
 
     const transformed = transformValue(node);
 
     if (transformed) {
-      if (path.length === 0) {
-        annotations.root = transformed.type;
-      } else {
-        if (!annotations.values) {
-          annotations.values = {};
-        }
-
-        annotations.values[stringifyPath(path)] = transformed.type;
-      }
-
+      valueAnnotations.add(path, transformed.type);
       return transformed.value;
     } else {
       return node;
     }
   };
 
-  function getAnnotations(): Annotations {
-    IteratorUtils.forEach(objectIdentities.values(), paths => {
-      if (paths.length > 1) {
-        const [shortestPath, ...identityPaths] = paths
-          .sort((a, b) => a.length - b.length)
-          .map(stringifyPath);
-
-        const isRoot = shortestPath.length === 0;
-        if (isRoot) {
-          annotations.referentialEqualitiesRoot = identityPaths;
-        } else {
-          if (!annotations.referentialEqualities) {
-            annotations.referentialEqualities = {};
-          }
-
-          annotations.referentialEqualities[shortestPath] = identityPaths;
-        }
-      }
-    });
-
-    return annotations;
-  }
-
-  return { getAnnotations, annotator };
+  return { getAnnotations: () => annotationFactory.create(), annotator };
 };
 
 export const applyAnnotations = (plain: any, annotations: Annotations): any => {
   if (annotations.values) {
-    const annotationsWithPaths = Object.entries(annotations.values).map(
-      ([key, type]) => [parsePath(key), type] as [string[], TypeAnnotation]
-    );
-
-    const annotationsWithPathsLeavesToRoot = annotationsWithPaths.sort(
-      ([pathA], [pathB]) => pathB.length - pathA.length
+    PathTree.traverseWhileIgnoringNullRoot(
+      PathTree.expandRoot(annotations.values),
+      (type, path) => {
+        plain = setDeep(plain, path, v => untransformValue(v, type));
+      }
     );
-
-    for (const [path, type] of annotationsWithPathsLeavesToRoot) {
-      plain = setDeep(plain, path, v =>
-        untransformValue(v, type as TypeAnnotation)
-      );
-    }
-  }
-
-  if (annotations.root) {
-    plain = untransformValue(plain, annotations.root);
   }
 
   if (annotations.referentialEqualities) {
-    for (const [objectPath, identicalObjectsPaths] of Object.entries(
-      annotations.referentialEqualities
-    )) {
-      const object = getDeep(plain, parsePath(objectPath));
-
-      for (const identicalObjectPath of identicalObjectsPaths.map(parsePath)) {
-        setDeep(plain, identicalObjectPath, () => object);
+    PathTree.traverseWhileIgnoringNullRoot(
+      PathTree.expandRoot(annotations.referentialEqualities),
+      (identicalObjects, path) => {
+        const object = getDeep(plain, path);
+
+        PathTree.traversePaths(
+          PathTree.expandRoot(identicalObjects),
+          identicalObjectPath => {
+            plain = setDeep(plain, identicalObjectPath, () => object);
+          }
+        );
       }
-    }
-  }
-
-  if (annotations.referentialEqualitiesRoot) {
-    for (const identicalObjectPath of annotations.referentialEqualitiesRoot.map(
-      parsePath
-    )) {
-      setDeep(plain, identicalObjectPath, () => plain);
-    }
+    );
   }
 
   return plain;
diff --git a/src/pathstringifier.ts b/src/pathstringifier.ts
index 7b5dfe5..63c04c6 100644
--- a/src/pathstringifier.ts
+++ b/src/pathstringifier.ts
@@ -1,25 +1,14 @@
 export type StringifiedPath = string;
-type Path = (number | string)[];
+type Path = string[];
 
-const escape = (key: string) => key.replace(/\./g, '\\.');
-const unescape = (k: string) => k.replace(/\\\./g, '.');
+export const escapeKey = (key: string) => key.replace(/\./g, '\\.');
+export const unescapeKey = (k: string) => k.replace(/\\\./g, '.');
 
 export const stringifyPath = (path: Path): StringifiedPath =>
   path
     .map(String)
-    .map(escape)
+    .map(escapeKey)
     .join('.');
 
 export const parsePath = (string: StringifiedPath): Path =>
-  string.split(/(?<!\\)\./g).map(unescape);
-
-export const isStringifiedPath = (
-  string: string
-): string is StringifiedPath => {
-  try {
-    parsePath(string);
-    return true;
-  } catch (anyError) {
-    return false;
-  }
-};
+  string.split(/(?<!\\)\./g).map(unescapeKey);
diff --git a/src/pathtree.ts b/src/pathtree.ts
new file mode 100644
index 0000000..12c7757
--- /dev/null
+++ b/src/pathtree.ts
@@ -0,0 +1,196 @@
+import { stringifyPath, parsePath } from './pathstringifier';
+import { isUndefined, isNull, isArray, isPlainObject } from './is';
+
+export type Tree<T> = InnerNode<T> | Leaf<T>;
+type Leaf<T> = [T];
+type InnerNode<T> = [T, Record<string, Tree<T>>];
+
+export function isTree<T>(
+  v: any,
+  valueChecker: (nodeValue: T) => boolean
+): v is Tree<T> {
+  if (!isArray(v)) {
+    return false;
+  }
+
+  if (v.length === 1) {
+    return valueChecker(v[0]);
+  } else if (v.length === 2) {
+    return (
+      valueChecker(v[0]) &&
+      Object.values(v[1]).every(v => isTree(v, valueChecker))
+    );
+  }
+
+  return false;
+}
+
+export module PathTree {
+  export function create<T>(value: T): Tree<T> {
+    return [value];
+  }
+
+  export function get<T>(
+    tree: Tree<T>,
+    path: string[]
+  ): [T, true] | [null, false] {
+    if (path.length === 0) {
+      return [tree[0] as T, true];
+    }
+
+    if (tree.length === 1) {
+      return [null, false];
+    } else {
+      const [head, ...tail] = path;
+      const [, children] = tree;
+      return get(children[head], tail);
+    }
+  }
+
+  /**
+   * @description Optimised for adding new leaves. Does not support adding inner nodes.
+   */
+  export function append<T>(tree: Tree<T>, path: string[], value: T): Tree<T> {
+    if (path.length === 0) {
+      if (tree.length === 1) {
+        return [value];
+      } else {
+        const [, children] = tree;
+        return [value, children];
+      }
+    }
+
+    if (tree.length === 1) {
+      const [nodeValue] = tree;
+      return [nodeValue, { [stringifyPath(path)]: [value] }];
+    } else {
+      const [nodeValue, children] = tree;
+      const availablePaths = Object.keys(children);
+
+      const stringifiedPath = stringifyPath(path);
+      // due to the constraints mentioned in the functions description,
+      // there may be prefixes of `path` already set, but no extensions of it.
+      // If there's such a prefix, we'll find it.
+      const prefix = availablePaths.find(candidate =>
+        stringifiedPath.startsWith(candidate)
+      );
+
+      if (isUndefined(prefix)) {
+        return [nodeValue, { ...children, [stringifyPath(path)]: [value] }];
+      } else {
+        const pathWithoutPrefix = path.slice(parsePath(prefix).length);
+        return [
+          nodeValue,
+          {
+            ...children,
+            [prefix]: append(children[prefix], pathWithoutPrefix, value),
+          },
+        ];
+      }
+    }
+  }
+
+  export function appendPath(
+    tree: Tree<string | null>,
+    path: string[]
+  ): Tree<string | null> {
+    const front = path.slice(0, path.length - 1);
+    const last = path[path.length - 1];
+    return append(tree, front, last);
+  }
+
+  /**
+   * Depth-first post-order traversal.
+   */
+  export function traverse<T>(
+    tree: Tree<T>,
+    walker: (v: T, path: string[]) => void,
+    origin: string[] = []
+  ): void {
+    if (tree.length === 1) {
+      const [nodeValue] = tree;
+      walker(nodeValue, origin);
+    } else {
+      const [nodeValue, children] = tree;
+
+      Object.entries(children).forEach(([key, children]) => {
+        traverse(children, walker, [...origin, ...parsePath(key)]);
+      });
+
+      walker(nodeValue, origin);
+    }
+  }
+
+  export function traverseWhileIgnoringNullRoot<T>(
+    tree: Tree<T | null>,
+    walker: (v: T, path: string[]) => void
+  ): void {
+    traverse(tree, (v, path) => {
+      if (isNull(v)) {
+        if (path.length === 0) {
+          return;
+        }
+
+        throw new Error('Illegal State');
+      }
+
+      walker(v, path);
+    });
+  }
+
+  export function traversePaths(
+    tree: Tree<string | null>,
+    walker: (path: string[]) => void
+  ) {
+    traverseWhileIgnoringNullRoot(tree, (last, front) =>
+      walker([...front, last])
+    );
+  }
+
+  export type CollapsedRootTree<T> =
+    | Tree<T>
+    | Record<string, Tree<T>>
+    | undefined;
+
+  export function isMinimizedTree<T>(
+    v: any,
+    valueChecker: (v: T) => boolean
+  ): v is CollapsedRootTree<T> {
+    if (isUndefined(v)) {
+      return true;
+    }
+
+    if (isPlainObject(v)) {
+      return Object.values(v).every(v => isTree(v, valueChecker));
+    }
+
+    return isTree(v, valueChecker);
+  }
+
+  /**
+   * @description Minimizes trees that start with a `null`-root
+   */
+  export function collapseRoot<T>(tree: Tree<T | null>): CollapsedRootTree<T> {
+    if (isNull(tree[0])) {
+      if (tree.length === 1) {
+        return undefined;
+      } else {
+        return tree[1] as Record<string, Tree<T>>;
+      }
+    }
+
+    return tree as Tree<T>;
+  }
+
+  export function expandRoot<T>(tree: CollapsedRootTree<T>): Tree<T | null> {
+    if (isArray(tree)) {
+      return tree;
+    }
+
+    if (isUndefined(tree)) {
+      return [null];
+    }
+
+    return [null, tree];
+  }
+}


Test patch:
diff --git a/src/annotator.test.ts b/src/annotator.test.ts
index c229dcc..5b35371 100644
--- a/src/annotator.test.ts
+++ b/src/annotator.test.ts
@@ -14,7 +14,7 @@ describe('annotator', () => {
 
     expect(getAnnotations()).toEqual({
       values: {
-        'a.1.b': 'undefined',
+        'a.1.b': ['undefined'],
       },
     });
   });
diff --git a/src/index.test.ts b/src/index.test.ts
index 6f9a317..4bfb47f 100644
--- a/src/index.test.ts
+++ b/src/index.test.ts
@@ -44,7 +44,7 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         values: {
-          'a.1': 'undefined',
+          'a.1': ['undefined'],
         },
       },
     },
@@ -58,8 +58,7 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         values: {
-          a: 'set',
-          'a.1': 'undefined',
+          a: ['set', { 1: ['undefined'] }],
         },
       },
     },
@@ -68,10 +67,7 @@ describe('stringify & parse', () => {
       input: new Set([1, undefined, 2]),
       output: [1, undefined, 2],
       outputAnnotations: {
-        root: 'set',
-        values: {
-          '1': 'undefined',
-        },
+        values: ['set', { 1: ['undefined'] }],
       },
     },
 
@@ -96,10 +92,9 @@ describe('stringify & parse', () => {
 
       outputAnnotations: {
         values: {
-          a: 'map',
-          'a.1.0': 'number',
-          b: 'map',
-          d: 'map',
+          a: ['map', { '1.0': ['number'] }],
+          b: ['map'],
+          d: ['map'],
         },
       },
     },
@@ -119,7 +114,7 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         referentialEqualities: {
-          selected: ['options.0'],
+          selected: [{ options: ['0'] }],
         },
       },
       customExpectations: output => {
@@ -140,7 +135,7 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         values: {
-          'a\\.1.b': 'set',
+          'a\\.1.b': ['set'],
         },
       },
     },
@@ -158,7 +153,7 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         values: {
-          'a\\\\.1.b': 'set',
+          'a\\\\.1.b': ['set'],
         },
       },
     },
@@ -176,7 +171,7 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         values: {
-          'meeting.date': 'Date',
+          'meeting.date': ['Date'],
         },
       },
     },
@@ -190,7 +185,7 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         values: {
-          a: 'regexp',
+          a: ['regexp'],
         },
       },
     },
@@ -204,7 +199,7 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         values: {
-          a: 'number',
+          a: ['number'],
         },
       },
     },
@@ -218,7 +213,7 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         values: {
-          a: 'number',
+          a: ['number'],
         },
       },
     },
@@ -232,7 +227,7 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         values: {
-          a: 'number',
+          a: ['number'],
         },
       },
     },
@@ -246,7 +241,7 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         values: {
-          a: 'bigint',
+          a: ['bigint'],
         },
       },
     },
@@ -268,7 +263,7 @@ describe('stringify & parse', () => {
         ],
       },
       outputAnnotations: {
-        referentialEqualitiesRoot: ['children.0.parents.0'],
+        referentialEqualities: [{ 'children.0.parents': ['0'] }],
       },
     },
 
@@ -282,11 +277,13 @@ describe('stringify & parse', () => {
         ['/a/g', 'bar'],
       ],
       outputAnnotations: {
-        root: 'map',
-        values: {
-          '0.0': 'regexp',
-          '1.0': 'regexp',
-        },
+        values: [
+          'map',
+          {
+            '0.0': ['regexp'],
+            '1.0': ['regexp'],
+          },
+        ],
       },
     },
 
@@ -305,10 +302,10 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         values: {
-          highscores: 'map',
+          highscores: ['map'],
         },
         referentialEqualities: {
-          topScorer: ['highscores.0.0'],
+          topScorer: [{ 'highscores.0': ['0'] }] as any,
         },
       },
     },
@@ -327,11 +324,11 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         values: {
-          a: 'map',
-          b: 'map',
+          a: ['map'],
+          b: ['map'],
         },
         referentialEqualities: {
-          a: ['b'],
+          a: [['b']],
         },
       },
       customExpectations: value => {
@@ -354,7 +351,7 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         values: {
-          map: 'map',
+          map: ['map'],
         },
       },
     },
@@ -373,10 +370,10 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         values: {
-          users: 'set',
+          users: ['set'],
         },
         referentialEqualities: {
-          userOfTheMonth: ['users.0'],
+          userOfTheMonth: [{ users: ['0'] }],
         },
       },
       customExpectations: value => {
@@ -473,7 +470,7 @@ describe('stringify & parse', () => {
 
       expect(meta).toEqual({
         values: {
-          s7: ['class', 'Train'],
+          s7: [['class', 'Train']],
         },
       });
 
diff --git a/src/pathstringifier.test.ts b/src/pathstringifier.test.ts
new file mode 100644
index 0000000..9d5fa52
--- /dev/null
+++ b/src/pathstringifier.test.ts
@@ -0,0 +1,10 @@
+import { escapeKey } from './pathstringifier';
+
+describe('escapeKey', () => {
+  test.each([
+    ['dontescape', 'dontescape'],
+    ['escape.me', 'escape\\.me'],
+  ])('escapeKey(%s) === %s', (input, expectedOutput) => {
+    expect(escapeKey(input)).toEqual(expectedOutput);
+  });
+});
diff --git a/src/pathtree.test.ts b/src/pathtree.test.ts
new file mode 100644
index 0000000..56a2f18
--- /dev/null
+++ b/src/pathtree.test.ts
@@ -0,0 +1,34 @@
+import { PathTree } from './pathtree';
+
+test('pathtree', () => {
+  let tree = PathTree.create<string | null>(null);
+
+  tree = PathTree.append(tree, ['abc'], '1');
+
+  expect(tree).toEqual([null, { abc: ['1'] }]);
+
+  tree = PathTree.append(tree, ['abc', 'd'], '2');
+
+  expect(tree).toEqual([null, { abc: ['1', { d: ['2'] }] }]);
+
+  tree = PathTree.append(tree, ['foo', 'bar'], '3');
+
+  expect(tree).toEqual([null, { abc: ['1', { d: ['2'] }], 'foo.bar': ['3'] }]);
+
+  tree = PathTree.append(tree, ['foo', 'bar', 'lel', 'lol'], '4');
+
+  expect(tree).toEqual([
+    null,
+    { abc: ['1', { d: ['2'] }], 'foo.bar': ['3', { 'lel.lol': ['4'] }] },
+  ]);
+
+  const traversalResults: [string[], string | null][] = [];
+  PathTree.traverse(tree, (v, path) => traversalResults.push([path, v]));
+  expect(traversalResults).toEqual([
+    [['abc', 'd'], '2'],
+    [['abc'], '1'],
+    [['foo', 'bar', 'lel', 'lol'], '4'],
+    [['foo', 'bar'], '3'],
+    [[], null],
+  ]);
+});