Repository: blitz-js/superjson
Pull request #120 (2021-02-20 22:07:54)

Rewrite "Plainer", remove a whole lot of code.
This PR is a rather sizeable refactoring. It changes the `plainer` to recursively build the Annotation tree, removing the need for unneccessary tree traversals (looking at `PathTree#append` and `annotator.ts`).

It simplifies the inner workings of SuperJSON by large.

To fully remove `PathTree`, I had to change the representation of `referentialEquality`. This is not a breaking change, since SuperJSON's output is not considered a public API - but if you depend on it nonetheless, watch out.

It also removes the schema checks that where performed during deserialisation. I consider them unneccessary overhead.


Patch:
diff --git a/benchmark.js b/benchmark.js
index 0f9f397..edf24de 100644
--- a/benchmark.js
+++ b/benchmark.js
@@ -1,41 +1,93 @@
-const Benchmark = require("benchmark")
-const SuperJSON = require("./dist/").default
+const Benchmark = require('benchmark');
+const SuperJSON = require('./dist/').default;
 
 const instances = {
-    "toy example": {
-        a: new Map([
-            [1, NaN],
-            [2, null],
-            [3, "Hurray"]
-        ]),
-        a: /regexp/g,
-        b: [
-            new Set([1, 2, 3])
-        ]
-    },
-    "user graph": {
-        users: new Map([
-            ["abcde", { id: "abcde", created: new Date(2020), friendIds: new Set(["a", "b", "c"]) }],
-            ["dasdfa", { id: "dasdfa", created: new Date(2019), friendIds: new Set(["b", "c"]) }],
-            ["hu-ha-hu", { id: "hu-ha-hu", created: new Date(2018), friendIds: new Set(["b", "c", "d", "f"]) }],
-            ["umphrey", { id: "umphrey", created: new Date(2017), friendIds: new Set([]) }],
-        ])
+  'toy example': {
+    a: new Map([
+      [1, NaN],
+      [2, null],
+      [3, 'Hurray'],
+    ]),
+    a: /regexp/g,
+    b: [new Set([1, 2, 3])],
+  },
+  'user graph': {
+    users: new Map([
+      [
+        'abcde',
+        {
+          id: 'abcde',
+          created: new Date(2020),
+          friendIds: new Set(['a', 'b', 'c']),
+        },
+      ],
+      [
+        'dasdfa',
+        {
+          id: 'dasdfa',
+          created: new Date(2019),
+          friendIds: new Set(['b', 'c']),
+        },
+      ],
+      [
+        'hu-ha-hu',
+        {
+          id: 'hu-ha-hu',
+          created: new Date(2018),
+          friendIds: new Set(['b', 'c', 'd', 'f']),
+        },
+      ],
+      [
+        'umphrey',
+        { id: 'umphrey', created: new Date(2017), friendIds: new Set([]) },
+      ],
+    ]),
+  },
+  'deep nested': (() => {
+    const data = [];
+    for (let i = 0; i < 100; i++) {
+      let nested1 = [];
+      let nested2 = [];
+      for (let j = 0; j < 10; j++) {
+        nested1[j] = {
+          createdAt: new Date(),
+          updatedAt: new Date(),
+          innerNested: {
+            createdAt: new Date(),
+            updatedAt: new Date(),
+          },
+        };
+        nested2[j] = {
+          createdAt: new Date(),
+          updatedAt: new Date(),
+          innerNested: {
+            createdAt: new Date(),
+            updatedAt: new Date(),
+          },
+        };
+      }
+      const object = {
+        createdAt: new Date(),
+        updatedAt: new Date(),
+        nested1,
+        nested2,
+      };
+      data.push(object);
     }
-}
+    return data;
+  })(),
+};
 
-const suite = new Benchmark.Suite("serialize & deserialize")
+const suite = new Benchmark.Suite('serialize & deserialize');
 
 for (const [key, instance] of Object.entries(instances)) {
-    suite
-        .add(key, () => {
-            SuperJSON.deserialize(
-                SuperJSON.serialize(instance)
-            )
-        })
+  suite.add(key, () => {
+    SuperJSON.deserialize(SuperJSON.serialize(instance));
+  });
 }
 
-suite.on("cycle", event => {
-    console.log("" + event.target)
-})
+suite.on('cycle', event => {
+  console.log('' + event.target);
+});
 
-suite.run();
\ No newline at end of file
+suite.run();
diff --git a/src/accessDeep.ts b/src/accessDeep.ts
index d41d69a..292d4b1 100644
--- a/src/accessDeep.ts
+++ b/src/accessDeep.ts
@@ -1,6 +1,6 @@
 import { isMap, isArray, isPlainObject, isSet } from './is';
 
-export const getNthKey = (value: Map<any, any> | Set<any>, n: number): any => {
+const getNthKey = (value: Map<any, any> | Set<any>, n: number): any => {
   const keys = value.keys();
   while (n > 0) {
     keys.next();
@@ -47,7 +47,7 @@ export const setDeep = (
       }
 
       const row = +key;
-      const type = +path[i + 1] === 0 ? 'key' : 'value';
+      const type = +path[++i] === 0 ? 'key' : 'value';
 
       const keyOfRow = getNthKey(parent, row);
       switch (type) {
@@ -58,8 +58,6 @@ export const setDeep = (
           parent = parent.get(keyOfRow);
           break;
       }
-
-      i++;
     }
   }
 
diff --git a/src/annotator.ts b/src/annotator.ts
deleted file mode 100644
index aadaeec..0000000
--- a/src/annotator.ts
+++ /dev/null
@@ -1,164 +0,0 @@
-import { getDeep, setDeep } from './accessDeep';
-import { isPrimitive, isString } from './is';
-import { Walker } from './plainer';
-import {
-  TypeAnnotation,
-  isTypeAnnotation,
-  transformValue,
-  untransformValue,
-} from './transformer';
-import { PathTree } from './pathtree';
-
-export interface Annotations {
-  values?: PathTree.CollapsedRootTree<TypeAnnotation>;
-  referentialEqualities?: PathTree.CollapsedRootTree<
-    PathTree.CollapsedRootTree<string>
-  >;
-}
-
-export function isAnnotations(object: any): object is Annotations {
-  try {
-    if (object.values) {
-      if (!PathTree.isMinimizedTree(object.values, isTypeAnnotation)) {
-        return false;
-      }
-    }
-
-    if (object.referentialEqualities) {
-      if (
-        !PathTree.isMinimizedTree(object.referentialEqualities, tree =>
-          PathTree.isMinimizedTree(tree, isString)
-        )
-      ) {
-        return false;
-      }
-    }
-
-    return true;
-  } catch (error) {
-    return false;
-  }
-}
-
-class ValueAnnotationFactory {
-  private tree = PathTree.create<TypeAnnotation | null>(null);
-
-  add(path: any[], annotation: TypeAnnotation) {
-    PathTree.append(this.tree, path, annotation);
-  }
-
-  create() {
-    PathTree.compress(this.tree);
-    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);
-    this.objectIdentities.set(object, paths);
-  }
-
-  create() {
-    let tree = PathTree.create<PathTree.CollapsedRootTree<string> | null>(null);
-
-    this.objectIdentities.forEach(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);
-      identicalPaths.forEach(identicalPath => {
-        PathTree.appendPath(identities, identicalPath);
-      });
-
-      const minimizedIdentities = PathTree.collapseRoot(identities);
-      if (!minimizedIdentities) {
-        throw new Error('Illegal State');
-      }
-
-      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)) {
-      objectIdentities.register(node, path);
-    }
-
-    const transformed = transformValue(node);
-
-    if (transformed) {
-      valueAnnotations.add(path, transformed.type);
-      return transformed.value;
-    } else {
-      return node;
-    }
-  };
-
-  return { getAnnotations: () => annotationFactory.create(), annotator };
-};
-
-export const applyAnnotations = (plain: any, annotations: Annotations): any => {
-  if (annotations.values) {
-    PathTree.traverseWhileIgnoringNullRoot(
-      PathTree.expandRoot(annotations.values),
-      (type, path) => {
-        plain = setDeep(plain, path, v => untransformValue(v, type));
-      }
-    );
-  }
-
-  if (annotations.referentialEqualities) {
-    PathTree.traverseWhileIgnoringNullRoot(
-      PathTree.expandRoot(annotations.referentialEqualities),
-      (identicalObjects, path) => {
-        const object = getDeep(plain, path);
-
-        PathTree.traversePaths(
-          PathTree.expandRoot(identicalObjects),
-          identicalObjectPath => {
-            plain = setDeep(plain, identicalObjectPath, () => object);
-          }
-        );
-      }
-    );
-  }
-
-  return plain;
-};
diff --git a/src/index.ts b/src/index.ts
index 01545ef..c3aaf8c 100644
--- a/src/index.ts
+++ b/src/index.ts
@@ -1,13 +1,4 @@
-import { applyAnnotations, makeAnnotator } from './annotator';
-import { isEmptyObject } from './is';
-import { plainer } from './plainer';
-import {
-  SuperJSONResult,
-  SuperJSONValue,
-  isSuperJSONResult,
-  Class,
-  JSONValue,
-} from './types';
+import { SuperJSONResult, SuperJSONValue, Class, JSONValue } from './types';
 import { ClassRegistry, RegisterOptions } from './class-registry';
 import { SymbolRegistry } from './symbol-registry';
 import {
@@ -15,32 +6,54 @@ import {
   CustomTransformerRegistry,
 } from './custom-transformer-registry';
 import { allowErrorProps } from './error-props';
+import {
+  walker,
+  applyReferentialEqualityAnnotations,
+  applyValueAnnotations,
+  generateReferentialEqualityAnnotations,
+} from './plainer';
 
 export const serialize = (object: SuperJSONValue): SuperJSONResult => {
-  const { getAnnotations, annotator } = makeAnnotator();
-  const output = plainer(object, annotator);
-
-  const annotations = getAnnotations();
+  const identities = new Map<any, any[][]>();
+  const output = walker(object, identities);
   const res: SuperJSONResult = {
-    json: output,
+    json: output.transformedValue,
   };
-  if (!isEmptyObject(annotations)) {
-    res.meta = annotations;
+
+  if (output.annotations) {
+    res.meta = {
+      ...res.meta,
+      values: output.annotations,
+    };
+  }
+
+  const equalityAnnotations = generateReferentialEqualityAnnotations(
+    identities
+  );
+  if (equalityAnnotations) {
+    res.meta = {
+      ...res.meta,
+      referentialEqualities: equalityAnnotations,
+    };
   }
+
   return res;
 };
 
 export const deserialize = <T = unknown>(payload: SuperJSONResult): T => {
-  if (!isSuperJSONResult(payload)) {
-    throw new Error('Not a valid SuperJSON payload.');
-  }
-
   const { json, meta } = payload;
 
-  const result: T = json as any;
+  let result: T = json as any;
+
+  if (meta?.values) {
+    result = applyValueAnnotations(result, meta.values);
+  }
 
-  if (!!meta) {
-    return applyAnnotations(result, meta);
+  if (meta?.referentialEqualities) {
+    result = applyReferentialEqualityAnnotations(
+      result,
+      meta.referentialEqualities
+    );
   }
 
   return result;
diff --git a/src/pathstringifier.ts b/src/pathstringifier.ts
index d8d6b59..a3d4d37 100644
--- a/src/pathstringifier.ts
+++ b/src/pathstringifier.ts
@@ -38,14 +38,3 @@ export const parsePath = (string: StringifiedPath) => {
 
   return result;
 };
-
-export const isStringifiedPath = (
-  string: string
-): string is StringifiedPath => {
-  try {
-    parsePath(string);
-    return true;
-  } catch (anyError) {
-    return false;
-  }
-};
diff --git a/src/pathtree.ts b/src/pathtree.ts
deleted file mode 100644
index 369ebdf..0000000
--- a/src/pathtree.ts
+++ /dev/null
@@ -1,212 +0,0 @@
-import { stringifyPath, parsePath } from './pathstringifier';
-import { isUndefined, isNull, isArray, isPlainObject } from './is';
-import { forEach, every } from './util';
-
-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]) && every(v[1], 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) {
-    if (path.length === 0) {
-      tree[0] = value;
-      return;
-    }
-
-    if (tree.length === 1) {
-      ((tree as any) as InnerNode<T>)[1] = { [stringifyPath(path)]: [value] };
-    } else {
-      tree[1][stringifyPath(path)] = [value];
-    }
-  }
-
-  export function appendPath(tree: Tree<string | null>, path: string[]) {
-    const front = path.slice(0, path.length - 1);
-    const last = path[path.length - 1];
-    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;
-
-      forEach(children, (child, key) => {
-        traverse(child, 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 every(v, 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];
-  }
-
-  /**
-   * @description Compress nested trees for smaller output
-   */
-  export function compress<T>(tree: Tree<T | null>) {
-    if (tree.length === 1) {
-      // tree root is Leaf
-      return;
-    }
-
-    const origin = tree[1];
-    const keys = Object.keys(origin).sort((a, b) => a.length - b.length);
-    const transformed: Record<string, Tree<T | null>> = {};
-
-    for (let i = 0; i < keys.length; i++) {
-      const key = keys[i];
-
-      let parentKey = undefined;
-      let splittedKey = key.split('.');
-      while (splittedKey.length > 0) {
-        splittedKey.pop();
-        const possibleParentKey = splittedKey.join('.');
-        if (transformed.hasOwnProperty(possibleParentKey)) {
-          parentKey = possibleParentKey;
-          break;
-        }
-      }
-      if (parentKey && transformed[parentKey]) {
-        transformed[parentKey][1] = Object.assign(
-          transformed[parentKey][1] || {},
-          {
-            [key.substring(parentKey.length + 1)]: origin[key],
-          }
-        );
-        continue;
-      } else {
-        transformed[key] = origin[key];
-      }
-    }
-
-    // Recursive optimization
-    const transformedKeys = Object.keys(transformed);
-    for (let i = 0; i < transformedKeys.length; i++) {
-      compress(transformed[transformedKeys[i]]);
-    }
-
-    tree[1] = transformed;
-  }
-}
diff --git a/src/plainer.spec.ts b/src/plainer.spec.ts
new file mode 100644
index 0000000..ad96758
--- /dev/null
+++ b/src/plainer.spec.ts
@@ -0,0 +1,27 @@
+import { walker } from './plainer';
+
+test('walker', () => {
+  expect(
+    walker(
+      {
+        a: new Map([[NaN, null]]),
+        b: /test/g,
+      },
+      new Map()
+    )
+  ).toEqual({
+    transformedValue: {
+      a: [['NaN', null]],
+      b: '/test/g',
+    },
+    annotations: {
+      a: [
+        'map',
+        {
+          '0.0': ['number'],
+        },
+      ],
+      b: ['regexp'],
+    },
+  });
+});
diff --git a/src/plainer.ts b/src/plainer.ts
index d818cb5..53a6563 100644
--- a/src/plainer.ts
+++ b/src/plainer.ts
@@ -1,14 +1,92 @@
-import { isArray, isMap, isPlainObject, isPrimitive, isSet } from './is';
-import { isInstanceOfRegisteredClass } from './transformer';
-import { includes, mapValues } from './util';
-
-interface WalkerValue {
-  isLeaf: boolean;
-  path: any[];
-  node: any;
+import {
+  isArray,
+  isEmptyObject,
+  isMap,
+  isPlainObject,
+  isPrimitive,
+  isSet,
+} from './is';
+import { escapeKey, stringifyPath } from './pathstringifier';
+import {
+  isInstanceOfRegisteredClass,
+  transformValue,
+  TypeAnnotation,
+  untransformValue,
+} from './transformer';
+import { includes, forEach } from './util';
+import { parsePath } from './pathstringifier';
+import { getDeep, setDeep } from './accessDeep';
+
+type Tree<T> = InnerNode<T> | Leaf<T>;
+type Leaf<T> = [T];
+type InnerNode<T> = [T, Record<string, Tree<T>>];
+
+export type MinimisedTree<T> = Tree<T> | Record<string, Tree<T>> | undefined;
+
+function traverse<T>(
+  tree: MinimisedTree<T>,
+  walker: (v: T, path: string[]) => void,
+  origin: string[] = []
+): void {
+  if (!tree) {
+    return;
+  }
+
+  if (!isArray(tree)) {
+    forEach(tree, (subtree, key) =>
+      traverse(subtree, walker, [...origin, ...parsePath(key)])
+    );
+    return;
+  }
+
+  const [nodeValue, children] = tree;
+  if (children) {
+    forEach(children, (child, key) => {
+      traverse(child, walker, [...origin, ...parsePath(key)]);
+    });
+  }
+
+  walker(nodeValue, origin);
+}
+
+export function applyValueAnnotations(
+  plain: any,
+  annotations: MinimisedTree<TypeAnnotation>
+) {
+  traverse(annotations, (type, path) => {
+    plain = setDeep(plain, path, v => untransformValue(v, type));
+  });
+
+  return plain;
 }
 
-export type Walker = (v: WalkerValue) => any;
+export function applyReferentialEqualityAnnotations(
+  plain: any,
+  annotations: ReferentialEqualityAnnotations
+) {
+  function apply(identicalPaths: string[], path: string) {
+    const object = getDeep(plain, parsePath(path));
+
+    identicalPaths.map(parsePath).forEach(identicalObjectPath => {
+      plain = setDeep(plain, identicalObjectPath, () => object);
+    });
+  }
+
+  if (isArray(annotations)) {
+    const [root, other] = annotations;
+    root.forEach(identicalPath => {
+      plain = setDeep(plain, parsePath(identicalPath), () => plain);
+    });
+
+    if (other) {
+      forEach(other, apply);
+    }
+  } else {
+    forEach(annotations, apply);
+  }
+
+  return plain;
+}
 
 const isDeep = (object: any): boolean =>
   isPlainObject(object) ||
@@ -17,35 +95,131 @@ const isDeep = (object: any): boolean =>
   isSet(object) ||
   isInstanceOfRegisteredClass(object);
 
-export const plainer = (
+function addIdentity(object: any, path: any[], identities: Map<any, any[][]>) {
+  const existingSet = identities.get(object);
+
+  if (existingSet) {
+    existingSet.push(path);
+  } else {
+    identities.set(object, [path]);
+  }
+}
+
+interface Result {
+  transformedValue: any;
+  annotations?: MinimisedTree<TypeAnnotation>;
+}
+
+export type ReferentialEqualityAnnotations =
+  | Record<string, string[]>
+  | [string[]]
+  | [string[], Record<string, string[]>];
+
+export function generateReferentialEqualityAnnotations(
+  identitites: Map<any, any[][]>
+): ReferentialEqualityAnnotations | undefined {
+  const result: Record<string, string[]> = {};
+  let rootEqualityPaths: string[] | undefined = undefined;
+
+  identitites.forEach(paths => {
+    if (paths.length <= 1) {
+      return;
+    }
+
+    const [shortestPath, ...identicalPaths] = paths
+      .map(path => path.map(String))
+      .sort((a, b) => a.length - b.length);
+
+    if (shortestPath.length === 0) {
+      rootEqualityPaths = identicalPaths.map(stringifyPath);
+    } else {
+      result[stringifyPath(shortestPath)] = identicalPaths.map(stringifyPath);
+    }
+  });
+
+  if (rootEqualityPaths) {
+    if (isEmptyObject(result)) {
+      return [rootEqualityPaths];
+    } else {
+      return [rootEqualityPaths, result];
+    }
+  } else {
+    return isEmptyObject(result) ? undefined : result;
+  }
+}
+
+export const walker = (
   object: any,
-  walker: Walker,
+  identities: Map<any, any[][]>,
   path: any[] = [],
-  alreadySeenObjects: any[] = []
-): any => {
-  if (!isDeep(object)) {
-    return walker({ isLeaf: true, node: object, path });
+  objectsInThisPath: any[] = []
+): Result => {
+  if (!isPrimitive(object)) {
+    addIdentity(object, path, identities);
   }
 
-  object = walker({ isLeaf: false, path, node: object });
+  if (!isDeep(object)) {
+    const transformed = transformValue(object);
+    if (transformed) {
+      return {
+        transformedValue: transformed.value,
+        annotations: [transformed.type],
+      };
+    } else {
+      return {
+        transformedValue: object,
+      };
+    }
+  }
 
-  if (includes(alreadySeenObjects, object)) {
-    return null;
+  if (includes(objectsInThisPath, object)) {
+    return {
+      transformedValue: null,
+    };
   }
 
+  const transformationResult = transformValue(object);
+  const transformed = transformationResult?.value ?? object;
+
   if (!isPrimitive(object)) {
-    alreadySeenObjects = [...alreadySeenObjects, object];
+    objectsInThisPath = [...objectsInThisPath, object];
   }
 
-  if (isArray(object)) {
-    return object.map((value, index) =>
-      plainer(value, walker, [...path, index], alreadySeenObjects)
-    );
-  }
+  const transformedValue: any = isArray(transformed) ? [] : {};
+  const innerAnnotations: Record<string, Tree<TypeAnnotation>> = {};
 
-  if (isPlainObject(object)) {
-    return mapValues(object, (value, key) =>
-      plainer(value, walker, [...path, key], alreadySeenObjects)
+  forEach(transformed, (value, index) => {
+    const recursiveResult = walker(
+      value,
+      identities,
+      [...path, index],
+      objectsInThisPath
     );
+
+    transformedValue[index] = recursiveResult.transformedValue;
+
+    if (isArray(recursiveResult.annotations)) {
+      innerAnnotations[index] = recursiveResult.annotations;
+    } else if (isPlainObject(recursiveResult.annotations)) {
+      forEach(recursiveResult.annotations, (tree, key) => {
+        innerAnnotations[escapeKey(index) + '.' + key] = tree;
+      });
+    }
+  });
+
+  if (isEmptyObject(innerAnnotations)) {
+    return {
+      transformedValue,
+      annotations: !!transformationResult
+        ? [transformationResult.type]
+        : undefined,
+    };
+  } else {
+    return {
+      transformedValue,
+      annotations: !!transformationResult
+        ? [transformationResult.type, innerAnnotations]
+        : innerAnnotations,
+    };
   }
 };
diff --git a/src/transformer.ts b/src/transformer.ts
index 974bfcf..9c8aaed 100644
--- a/src/transformer.ts
+++ b/src/transformer.ts
@@ -15,7 +15,7 @@ import { ClassRegistry } from './class-registry';
 import { SymbolRegistry } from './symbol-registry';
 import { CustomTransformerRegistry } from './custom-transformer-registry';
 import { allowedErrorProps } from './error-props';
-import { includes, findArr } from './util';
+import { findArr } from './util';
 
 export type PrimitiveTypeAnnotation = 'number' | 'undefined' | 'bigint';
 
@@ -34,30 +34,6 @@ type CompositeTypeAnnotation =
 
 export type TypeAnnotation = SimpleTypeAnnotation | CompositeTypeAnnotation;
 
-const ALL_PRIMITIVE_TYPE_ANNOTATIONS: TypeAnnotation[] = [
-  'undefined',
-  'number',
-  'bigint',
-];
-
-export const isPrimitiveTypeAnnotation = (
-  value: any
-): value is PrimitiveTypeAnnotation => {
-  return includes(ALL_PRIMITIVE_TYPE_ANNOTATIONS, value);
-};
-
-const ALL_TYPE_ANNOTATIONS: TypeAnnotation[] = ALL_PRIMITIVE_TYPE_ANNOTATIONS.concat(
-  ['map', 'regexp', 'set', 'Date', 'Error']
-);
-
-export const isTypeAnnotation = (value: any): value is TypeAnnotation => {
-  if (Array.isArray(value)) {
-    return typeof value[1] === 'string';
-  }
-
-  return includes(ALL_TYPE_ANNOTATIONS, value);
-};
-
 function simpleTransformation<I, O, A extends SimpleTypeAnnotation>(
   isApplicable: (v: any) => v is I,
   annotation: A,
diff --git a/src/types.ts b/src/types.ts
index df2ea4e..10883b4 100644
--- a/src/types.ts
+++ b/src/types.ts
@@ -1,5 +1,5 @@
-import { Annotations, isAnnotations } from './annotator';
-import { isUndefined } from './is';
+import { TypeAnnotation } from './transformer';
+import { MinimisedTree, ReferentialEqualityAnnotations } from './plainer';
 
 export type Class = { new (...args: any[]): any };
 
@@ -39,17 +39,8 @@ export interface SuperJSONObject {
 
 export interface SuperJSONResult {
   json: JSONValue;
-  meta?: Annotations;
-}
-
-export function isSuperJSONResult(object: any): object is SuperJSONResult {
-  if (!('json' in object)) {
-    return false;
-  }
-
-  if (isUndefined(object.meta)) {
-    return true;
-  }
-
-  return isAnnotations(object.meta);
+  meta?: {
+    values?: MinimisedTree<TypeAnnotation>;
+    referentialEqualities?: ReferentialEqualityAnnotations;
+  };
 }
diff --git a/src/util.ts b/src/util.ts
index e2e4440..13a5288 100644
--- a/src/util.ts
+++ b/src/util.ts
@@ -45,39 +45,10 @@ export function forEach<T>(
   Object.entries(record).forEach(([key, value]) => run(value, key));
 }
 
-export function every<T>(
-  record: Record<string, T>,
-  predicate: (v: T) => boolean
-) {
-  const values = valuesOfObj(record);
-
-  for (let i = 0; i < values.length; i++) {
-    const value = values[i];
-    if (!predicate(value)) {
-      return false;
-    }
-  }
-
-  return true;
-}
-
 export function includes<T>(arr: T[], value: T) {
   return arr.indexOf(value) !== -1;
 }
 
-export function mapValues<A, B>(
-  record: Record<string, A>,
-  mapper: (v: A, key: string) => B
-): Record<string, B> {
-  const result: Record<string, B> = {};
-
-  forEach(record, (value, key) => {
-    result[key] = mapper(value, key);
-  });
-
-  return result;
-}
-
 export function findArr<T>(
   record: T[],
   predicate: (v: T) => boolean


Test patch:
diff --git a/src/accessDeep.test.ts b/src/accessDeep.test.ts
index 9f5ba5c..8162a33 100644
--- a/src/accessDeep.test.ts
+++ b/src/accessDeep.test.ts
@@ -3,25 +3,27 @@ import { setDeep } from './accessDeep';
 describe('setDeep', () => {
   it('correctly sets values in maps', () => {
     const obj = {
-      a: new Map([['NaN', 10]]),
+      a: new Map([[new Set(['NaN']), [[1, 'undefined']]]]),
     };
 
-    setDeep(obj, ['a', 0, 0], Number);
+    setDeep(obj, ['a', 0, 0, 0], Number);
+    setDeep(obj, ['a', 0, 1], entries => new Map(entries));
+    setDeep(obj, ['a', 0, 1, 0, 1], () => undefined);
 
     expect(obj).toEqual({
-      a: new Map([[NaN, 10]]),
+      a: new Map([[new Set([NaN]), new Map([[1, undefined]])]]),
     });
   });
 
   it('correctly sets values in sets', () => {
     const obj = {
-      a: new Set(['NaN']),
+      a: new Set([10, new Set(['NaN'])]),
     };
 
-    setDeep(obj, ['a', 0], Number);
+    setDeep(obj, ['a', 1, 0], Number);
 
     expect(obj).toEqual({
-      a: new Set([NaN]),
+      a: new Set([10, new Set([NaN])]),
     });
   });
 });
diff --git a/src/annotator.test.ts b/src/annotator.test.ts
deleted file mode 100644
index 6d00ddd..0000000
--- a/src/annotator.test.ts
+++ /dev/null
@@ -1,21 +0,0 @@
-import { makeAnnotator } from './annotator';
-
-describe('annotator', () => {
-  test('simple example', () => {
-    const { getAnnotations, annotator } = makeAnnotator();
-
-    expect(
-      annotator({
-        isLeaf: true,
-        path: ['a', 1, 'b'],
-        node: undefined,
-      })
-    ).toBe(null);
-
-    expect(getAnnotations()).toEqual({
-      values: {
-        'a.1.b': ['undefined'],
-      },
-    });
-  });
-});
diff --git a/src/index.test.ts b/src/index.test.ts
index e840bd7..98c0c56 100644
--- a/src/index.test.ts
+++ b/src/index.test.ts
@@ -2,8 +2,7 @@
 /* eslint-disable es5/no-es6-methods */
 
 import SuperJSON from './';
-import { JSONValue, SuperJSONValue } from './types';
-import { Annotations } from './annotator';
+import { JSONValue, SuperJSONResult, SuperJSONValue } from './types';
 import { isArray, isMap, isPlainObject, isPrimitive, isSet } from './is';
 
 import { ObjectID } from 'mongodb';
@@ -16,10 +15,11 @@ describe('stringify & parse', () => {
     {
       input: (() => SuperJSONValue) | SuperJSONValue;
       output: JSONValue | ((v: JSONValue) => void);
-      outputAnnotations?: Annotations;
+      outputAnnotations?: SuperJSONResult['meta'];
       customExpectations?: (value: any) => void;
       skipOnNode10?: boolean;
       dontExpectEquality?: boolean;
+      only?: boolean;
     }
   > = {
     'works for objects': {
@@ -123,7 +123,7 @@ describe('stringify & parse', () => {
       },
       outputAnnotations: {
         referentialEqualities: {
-          selected: [{ options: ['0'] }],
+          selected: ['options.0'],
         },
       },
       customExpectations: output => {
@@ -308,7 +308,7 @@ describe('stringify & parse', () => {
         ],
       },
       outputAnnotations: {
-        referentialEqualities: [{ 'children.0.parents': ['0'] }],
+        referentialEqualities: [['children.0.parents.0']],
       },
     },
 
@@ -350,7 +350,7 @@ describe('stringify & parse', () => {
           highscores: ['map'],
         },
         referentialEqualities: {
-          topScorer: [{ 'highscores.0': ['0'] }] as any,
+          topScorer: ['highscores.0.0'],
         },
       },
     },
@@ -373,7 +373,7 @@ describe('stringify & parse', () => {
           b: ['map'],
         },
         referentialEqualities: {
-          a: [['b']],
+          a: ['b'],
         },
       },
       customExpectations: value => {
@@ -418,7 +418,7 @@ describe('stringify & parse', () => {
           users: ['set'],
         },
         referentialEqualities: {
-          userOfTheMonth: [{ users: ['0'] }],
+          userOfTheMonth: ['users.0'],
         },
       },
       customExpectations: value => {
@@ -627,6 +627,7 @@ describe('stringify & parse', () => {
       customExpectations,
       skipOnNode10,
       dontExpectEquality,
+      only,
     },
   ] of Object.entries(cases)) {
     let testFunc = test;
@@ -635,6 +636,10 @@ describe('stringify & parse', () => {
       testFunc = test.skip;
     }
 
+    if (only) {
+      testFunc = test.only;
+    }
+
     testFunc(testName, () => {
       const inputValue = typeof input === 'function' ? input() : input;
 
@@ -733,35 +738,7 @@ describe('stringify & parse', () => {
   });
 
   describe('when given a non-SuperJSON object', () => {
-    it('throws', () => {
-      expect(() => {
-        SuperJSON.parse(
-          JSON.stringify({
-            value: {
-              a: 1,
-            },
-            meta: {
-              root: 'invalid_key',
-            },
-          })
-        );
-      }).toThrow();
-
-      expect(() => {
-        SuperJSON.parse(
-          JSON.stringify({
-            value: {
-              a: 1,
-            },
-            meta: {
-              values: {
-                a: 'invalid_key',
-              },
-            },
-          })
-        );
-      }).toThrow();
-    });
+    it.todo('has undefined behaviour');
   });
 
   test('regression #65: BigInt on Safari v13', () => {
diff --git a/src/pathtree.test.ts b/src/pathtree.test.ts
deleted file mode 100644
index cb642c7..0000000
--- a/src/pathtree.test.ts
+++ /dev/null
@@ -1,37 +0,0 @@
-import { PathTree } from './pathtree';
-
-test('pathtree', () => {
-  let tree = PathTree.create<string | null>(null);
-
-  PathTree.append(tree, ['abc'], '1');
-
-  expect(tree).toEqual([null, { abc: ['1'] }]);
-
-  PathTree.append(tree, ['abc', 'd'], '2');
-  PathTree.compress(tree);
-
-  expect(tree).toEqual([null, { abc: ['1', { d: ['2'] }] }]);
-
-  PathTree.append(tree, ['foo', 'bar'], '3');
-  PathTree.compress(tree);
-
-  expect(tree).toEqual([null, { abc: ['1', { d: ['2'] }], 'foo.bar': ['3'] }]);
-
-  PathTree.append(tree, ['foo', 'bar', 'lel', 'lol'], '4');
-  PathTree.compress(tree);
-
-  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],
-  ]);
-});
diff --git a/src/plainer.test.ts b/src/plainer.test.ts
deleted file mode 100644
index 7ca49d6..0000000
--- a/src/plainer.test.ts
+++ /dev/null
@@ -1,106 +0,0 @@
-import { plainer } from './plainer';
-
-describe('plainer', () => {
-  it('walks through the whole tree', () => {
-    const input = {
-      a: new Map([
-        [2, 'hallo'],
-        [undefined, null],
-      ]),
-      b: {
-        c: new Set([1, 1, 2, /hallo/g]),
-      },
-      d: {
-        0: 'a',
-        1: 'b',
-      },
-    };
-
-    const annotations: any = {};
-
-    const output = plainer(input, ({ path, node }) => {
-      annotations[path.join('.')] = node;
-      if (node instanceof Map) {
-        return [...node.entries()];
-      }
-      if (node instanceof Set) {
-        // eslint-disable-next-line es5/no-es6-methods
-        return [...node.values()];
-      }
-      return node;
-    });
-
-    expect(output).toEqual({
-      a: [
-        [2, 'hallo'],
-        [undefined, null],
-      ],
-      b: {
-        c: [1, 2, /hallo/g],
-      },
-      d: {
-        0: 'a',
-        1: 'b',
-      },
-    });
-
-    expect(annotations).toMatchInlineSnapshot(`
-      Object {
-        "": Object {
-          "a": Map {
-            2 => "hallo",
-            undefined => null,
-          },
-          "b": Object {
-            "c": Set {
-              1,
-              2,
-              /hallo/g,
-            },
-          },
-          "d": Object {
-            "0": "a",
-            "1": "b",
-          },
-        },
-        "a": Map {
-          2 => "hallo",
-          undefined => null,
-        },
-        "a.0": Array [
-          2,
-          "hallo",
-        ],
-        "a.0.0": 2,
-        "a.0.1": "hallo",
-        "a.1": Array [
-          undefined,
-          null,
-        ],
-        "a.1.0": undefined,
-        "a.1.1": null,
-        "b": Object {
-          "c": Set {
-            1,
-            2,
-            /hallo/g,
-          },
-        },
-        "b.c": Set {
-          1,
-          2,
-          /hallo/g,
-        },
-        "b.c.0": 1,
-        "b.c.1": 2,
-        "b.c.2": /hallo/g,
-        "d": Object {
-          "0": "a",
-          "1": "b",
-        },
-        "d.0": "a",
-        "d.1": "b",
-      }
-    `);
-  });
-});