[Proposal] Snapshot and diffing based on copy-on-write DOM tree

[malash]

What

The DOM tree means the proposal DOM API. For now we can reguard it web's DOM.

const snapshotA = document.createSnapshot();
document.appendChild(document.createElement('view'));
document.appendChild(document.createElement('text'));
document.appendChild(document.createElement('video'));
const snapshotB = document.createSnapshot();

const diffAtoB = generateDiff(snapshotA, snapshotB);
console.log(diffAtoB); // output which DOMs are modified

Why

Immutable snapshot

By using copy-on-write we can create immutable snapshot for eact commit ( setData call ) with low cost. This is useful for diffing algorithm, debug logging and React dev tool supporting. It's imageable that we can even make a DOM history with prev and next buttons to see how the UI changed.

Improve diff generation

In current Goji we generate both data ( full DOM data ) and diff ( part of DOM data for less transfer size ) in the pure method ( however this function is not pure at all 😂 ). There are several known probleams:

1. The pure methods is expensive becuase it traverse the whole DOM tree every called.
2. Not same as other VDOM implement, Goji diff generation rely on a tag system that reconciler adds the tag to DOM tree and pure removes the tags. In most cases mutable api is worse then immutable one.
3. Current implement is too complex to maintain and test. Although write some test cases to cover the corner case we cannot ensure it won't go wrong in production code.

By this proposal we can implement a real pure function the create diff based on two DOM tree:

const diff = generateDiff(oldDom, newDom)

And we can benefit:

1. Thanks to copy-on-write creating a snapshot is much more cheap and we don't need to mutate the existing DOM tree at all.
2. We can just use === to check whether a subtree was modified. It is more clear and lite than the tag system.
3. Immutable API is easier to test.

Support blocking mode

Imaging an use case, we use blocking mode to improve sequency setData calls' performance. If there were 3 commits, useually means business code trigger component re-rendering in different 3 time ticks, the time sequence would be:

As you can see, besides dataA wo genersate two DOM diff diffAtoB and diffBtoC then merge them as diffAtoC = merge(diffAtoB, diffBtoC). DOM diffing is expensive because it traverses almost the whole DOM tree and figure out which path should be emit.

By using snapshot we can create diff for only once:

// setData A called
lastSnapshot = currentDomTree
// commit B
newSnapshot = currentDomTree
// commot C, override the `newDomTree`
newSnapshot = currentDomTree
// call setData B+C
setData(diff(lastSnapshot, newSnapshot))
// then 
lastSnapshot = newSnapshot
// ...

Memory pool ( optional )

Most copy-on-write system can use reference counting to control the memory usage precisely. After user navgiate to a new page and navigate back so many DOM instances should be GC by V8 virtual matchine. We guess in some platforms the GC won't work as expected and may cause white screen and memory leak issues.

We can maintain a memory pool of DOM elements and reuse the instances as needed. I'm not sure couold it fix the issues but we can exclude some factors of GC probleam.

How

TBD

References

1. immer
2. btrfs