Weak Graph

[Jussi Kalliokoski]

Usually my first assumption when I think I need weak references is that I
should use WeakMaps instead. Today I came across an interesting use case
and was wrong for the first time. However it wasn't weak references I
needed either.

I'm trying to come up with a solution to the problem of rendering lists
that's often used as a counter argument for using a framework / view
library instead of direct DOM manipulation, where - even with React -
updating (even appending to) a list is O(n) at best.

My idea for a solution is that the lists are immutable, contain a reference
to their parent and a changeset / diff compared to their parent. This would
allow rendering the whole list initally, then just applying the diffs on
subsequent renders by walking the graph up to the last known ancestor and
combining the changesets. This would make subsequent renders O(1) which is
a great improvement even with small lists.

The biggest problem is that this will leak memory like crazy; every
revision of the list will be preserved. Let's say we have the following
implementation:

```JS
function WeakGraph () {
    const parentByNode = new WeakMap();

    this.getLineage = function (node, ancestor) {
        const lineage = [];

        let currentNode = node;
        do {
            lineage.push(currentNode);
            if ( !parentByNode.has(currentNode) ) { throw new Error("node
is not a descendant of ancestor"); }
            currentNode = parentByNode.get(currentNode);
        } while ( currentNode !== ancestor );

        return lineage;
    };

    this.addNode = function (node, parent) {
        parentByNode.set(node, parent);
    };
}
```

It provides the needed interface and the unused child revisions get cleaned
up properly. However:

* This is a complete nightmare for GC performance because of cyclical weak
references.
* Any reference to a child will maintain references to all its parents.

However this doesn't necessarily need to be the case because the stored
ancestry is not observable to anything that creates a WeakGraph, except to
the oldest ancestor that has a reference elsewhere.

I'm not sure if this use case alone warrants adding a new feature to the
language, or if I'm just missing something and it can be implemented with
existing constructs or if there should be some other lower level primitive
that would allow building a WeakGraph on the user level.

- Jussi
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20151104/3b3031a3/attachment.html>