Reconciliation makes more moves than necessary?

[luwes]

Discussed in #168

^{Originally posted by mindplay-dk April 6, 2021}
I've been interested in the reconciliation algo for a while, and I'm sort of an idiot when it comes to this stuff - it's really difficult for me to understand the reconciliation code in most of the libraries I've looked at, and frankly I didn't really trust that any of them were doing it optimally.

So I set up a use-case driven test bench with a bunch of console.log statements, so I can actually try various operations on a list, and see what sort of DOM operations result from those.

Here it is, first for Sinuous - with diff.js from the map module:

https://jsfiddle.net/mindplay/gdzrmshq/

Here, I noticed that "Rotate Up" moves 3 elements, while "Rotate Down" moves 2 elements - in either case, one move should be enough, since it's just the first/last element moving to the opposite end of the range.

I understand your code is derived from udomdiff? So here's the same test-bench for udomdiff:

https://jsfiddle.net/mindplay/o4gbaqw0/

Here, "Rotate Up" takes two moves (one of them a replaceNode) which is still one too many - while "Rotate Down" does it accurately, in a single move.

As said, I am an idiot at this stuff, but I decided to try my own naive approach - I simply remove old elements, append new elements, and then take two passes: first, I move only the nodes where moving them isn't going to break the order somewhere else - and then, I take a second pass, moving all remaining nodes that aren't already in the right place.

https://jsfiddle.net/mindplay/924xfvow/

Here, "Rotate Up" and "Rotate Down" both finish in one move.

As said, this approach is totally naive, and probably isn't blazing fast, since I'm using a two passes (and lots of comparisons with next/previous siblings) but I wanted something simple enough that I could understand it myself, being (as stated) an idiot.

Apparently, I'm not a complete idiot, because it works. 😂

I expect this simple algo could be optimized as well, because for most operations (all but "Shuffle") it doesn't actually need to do anything in the second pass - there's only one difference between the first and second pass, and it's this:

So, basically, if that second expression is ever false during the first pass, you can return before the second pass, because it would be fully identical to the first pass.

By the way, don't ask me why these loops are backwards. I've no idea if they need to be. I was just trying stuff, and it ended up this way, and it seems to work, so I didn't question it. (Might be good for micro perf anyway.)

I haven't benchmarked or optimized this at all, just throwing it up here for discussion.

Any thoughts? 🙂

[rozek]

is there any plan when to fix map?

[rozek]

well, since map even crashes my application and I don't want to analyze code which may be replaced soon, I'll try and implement the abovementioned approach myself (especially, since I need a fix now or I'll have to proceed to another library/framework with a working list renderer)

Give me time til tomorrow...

[rozek]

Good evening!

As mentioned yesterday, I needed a replacement for the original map implementation as that crashed my application.

For that reason, I tried to understand the internals of sinuous and its way of creating and destroying HTML nodes and took the ideas from #168 to implement it anew.

I made two versions

• a trivial one which simply asserts that already existing nodes (with any focus, selections, drop-down states etc.) are kept whenever possible, and
• one based on the "snabbdom" algorithm (without node creation and removal - as that is done outside)

Both versions have the following restrictions:

• list items must be objects
• the list item rendering function should always create exactly one DOM node per item

You will find the sources below. Both versions have passed some "smoke" tests (and do not crash, at least) but have not yet been tested for efficiency

[rozek]

Here is the "trivial" map implementation:

  import { api } from 'sinuous'

/**
 * Map over a list of items that create DOM nodes.
 *
 * @param  {Function} items - Function or observable that creates a list.
 * @param  {Function} expr
 * @param  {boolean} [cleaning]
 * @return {DocumentFragment}
 */
  export function map (ListFn, ItemRenderer, cleaning) {
    const { subscribe, root, sample, cleanup } = api

    if (cleaning == null) {         // disable cleaning for templates by default
      cleaning = ! ItemRenderer.$t
    }
    const Disposers = new Map()

    let Parent = document.createDocumentFragment()

    const NodeAfterList = add(Parent, '')

    const unsubscribe = subscribe((oldItemList) => {
      const newItemList = ListFn()
      return sample(() => updateInPlace(
        oldItemList || [], newItemList || [], NodeAfterList, createFn,
        cleaning && dispose
      ))
    })

    cleanup(unsubscribe)
    cleanup(disposeAll)

  /**** createFn ****/

    function createFn (Parent, ListItem, ListIndex, List, FollowUpNode) {
      if (cleaning) {
        return root((Disposer) => {
          const Node = add(Parent, ItemRenderer(ListItem,ListIndex,List), FollowUpNode)
            Disposers.set(Node,Disposer)
          return Node
        })
      } else {
        return add(Parent, ItemRenderer(ListItem,ListIndex,List), FollowUpNode)
      }
    }

  /**** dispose ****/

    function dispose (Node) {
      let Disposer = Disposers.get(Node)
      if (Disposer != null) {
        Disposer()
      }
      Disposers.delete(Node)
    }

  /**** disposeAll ****/

    function disposeAll () {
      Disposers.forEach( (Disposer) => Disposer() )
      Disposers.clear()
    }

    return Parent
  }

/**** updateInPlace - to keep focus, drop-downs etc. intact ****/

  function updateInPlace (
    oldItemList, newItemList, NodeAfterList, createFn, dispose
  ) {
    const Parent = NodeAfterList.parentNode

  /**** allow for quick lookup of new list items ****/

    let newItemSet = new Set()
    newItemList.forEach((Item) => newItemSet.add(Item) )

  /**** associate existing HTML nodes with their list items ****/

    let oldNodeMap = new Map(), oldNode = NodeAfterList
    for (let i = oldItemList.length-1; i >= 0; i--) {
      const Item = oldItemList[i]
      oldNodeMap.set(Item,oldNode = oldNode.previousSibling)
    }

  /**** remove no longer needed HTML nodes ****/

    oldItemList.forEach((Item) => {
      if (! newItemSet.has(Item)) {
        const oldNode = oldNodeMap.get(Item)
        Parent.removeChild(oldNode)
        if (dispose != null) { dispose(oldNode) }
      }
    })

  /**** now reorder existing HTML node or create new ones ****/

    let FollowUpNode = NodeAfterList
    for (let i = newItemList.length-1; i >= 0; i--) {
      const Item = newItemList[i]

      let Node = oldNodeMap.get(Item)
      if (Node == null) {
        Node = createFn(Parent, Item,i,newItemList, FollowUpNode)
      } else {
        Parent.insertBefore(Node,FollowUpNode)
      }

      FollowUpNode = Node
    }

  /**** that's it! ****/

    return newItemList.slice()
  }

/**** add (has been taken from former map "utils") ****/

  const GROUPING = '__g';

  let groupCounter = 0;

  function add (parent, value, endMark) {
    let mark;

    if (typeof value === 'string') {
      value = document.createTextNode(value);
    } else if (!(value instanceof Node)) {
      // Passing an empty array creates a DocumentFragment.
      value = api.h([], value);
    }

    if (
      value.nodeType === 11 &&
      (mark = value.firstChild) &&
      mark !== value.lastChild
    ) {
      mark[GROUPING] = value.lastChild[GROUPING] = ++groupCounter;
    }

    // If endMark is `null`, value will be added to the end of the list.
    parent.insertBefore(value, endMark);

    // Explicit undefined to store if frag.firstChild is null.
    return mark || value;
  }

[rozek]

and here is the one based on the "snabbdom" algorithm:

  import { api } from 'sinuous'

/**
 * Map over a list of items that create DOM nodes.
 *
 * @param  {Function} items - Function or observable that creates a list.
 * @param  {Function} expr
 * @param  {boolean} [cleaning]
 * @return {DocumentFragment}
 */
  export function map (ListFn, ItemRenderer, cleaning) {
    const { subscribe, root, sample, cleanup } = api

    if (cleaning == null) {         // disable cleaning for templates by default
      cleaning = ! ItemRenderer.$t
    }
    const Disposers = new Map()

    let Parent = document.createDocumentFragment()

    const NodeAfterList = add(Parent, '')

    const unsubscribe = subscribe((oldItemList) => {
      const newItemList = ListFn()
      return sample(() => updateInPlace(
        oldItemList || [], newItemList || [], NodeAfterList, createFn,
        cleaning && dispose
      ))
    })

    cleanup(unsubscribe)
    cleanup(disposeAll)

  /**** createFn ****/

    function createFn (Parent, ListItem, ListIndex, List, FollowUpNode) {
      if (cleaning) {
        return root((Disposer) => {
          const Node = add(Parent, ItemRenderer(ListItem,ListIndex,List), FollowUpNode)
            Disposers.set(Node,Disposer)
          return Node
        })
      } else {
        return add(Parent, ItemRenderer(ListItem,ListIndex,List), FollowUpNode)
      }
    }

  /**** dispose ****/

    function dispose (Node) {
      let Disposer = Disposers.get(Node)
      if (Disposer != null) {
        Disposer()
      }
      Disposers.delete(Node)
    }

  /**** disposeAll ****/

    function disposeAll () {
      Disposers.forEach( (Disposer) => Disposer() )
      Disposers.clear()
    }

    return Parent
  }

/**** updateInPlace - to keep focus, drop-downs etc. intact ****/

  function updateInPlace (
    oldItemList, newItemList, NodeAfterList, createFn, dispose
  ) {
    const Parent = NodeAfterList.parentNode

  /**** allow for quick lookup of new list items ****/

    let newItemSet = new Set()
    newItemList.forEach((Item) => newItemSet.add(Item) )

  /**** associate existing HTML nodes with their list items ****/

    let oldNodeMap = new Map(), oldNode = NodeAfterList
    for (let i = oldItemList.length-1; i >= 0; i--) {
      const Item = oldItemList[i]
      oldNodeMap.set(Item,oldNode = oldNode.previousSibling)
    }

  /**** remove no longer needed HTML nodes and collect all others ****/

    let oldNodeList = []             // the "snabbdom" algorithm needs this list
    oldItemList.forEach((Item) => {
      const oldNode = oldNodeMap.get(Item)
      if (newItemSet.has(Item)) {
        oldNodeList.push(oldNode)
      } else {
        Parent.removeChild(oldNode)
        if (dispose != null) { dispose(oldNode) }
      }
    })

  /**** create a list of (already existing) HTML nodes for the new item list ****/

    let newNodeList = []    // the "snabbdom" algorithm needs this list as well
    newItemList.forEach((Item,Index) => {
      let oldNode = oldNodeMap.get(Item)
      if (oldNode != null) {
        newNodeList.push(oldNode)
      }
    })

  /**** now bring the existing HTML nodes in their proper order ****/

    reorder(Parent, oldNodeList,newNodeList, NodeAfterList)

  /**** finally add nodes for any new items ****/

    let FollowUpNode = NodeAfterList
    for (let i = newItemList.length-1; i >= 0; i--) {
      const Item = newItemList[i]

      let Node = oldNodeMap.get(Item)
      if (Node == null) {
        Node = createFn(Parent, Item,i,newItemList, FollowUpNode)
      }

      FollowUpNode = Node
    }

  /**** that's it! ****/

    return newItemList.slice()
  }

/**** reorder ****/
// originally taken from taken from https://github.com/luwes/js-diff-benchmark/blob/master/libs/snabbdom.js
// but without node removal (which has already been done before)

  function reorder (parent, a, b, afterNode) {
    const a_index = new Map();
    const b_index = new Map();

    let need_indices;
    let start_i = 0;
    let end_i = a.length - 1;
    let start_j = 0;
    let end_j = b.length - 1;
    let start_a = a[start_i];
    let end_a = a[end_i];
    let start_b = b[start_j];
    let end_b = b[end_j];
    let old_start_j;
    let new_start_i;

    while (start_i <= end_i && start_j <= end_j) {
      if (start_a == null) {
        start_a = a[++start_i];
      } else if (end_a == null) {
        end_a = a[--end_i];
      } else if (start_b == null) {
        start_b = b[++start_j];
      } else if (end_b == null) {
        end_b = b[--end_j];
      } else if (start_a === start_b) {
        start_a = a[++start_i];
        start_b = b[++start_j];
      } else if (end_a === end_b) {
        end_a = a[--end_i];
        end_b = b[--end_j];
      }
      else if (start_a === end_b) {
        parent.insertBefore(
          a[start_i],
          a[end_i].nextSibling || afterNode
        );
        start_a = a[++start_i];
        end_b = b[--end_j];
      } else if (end_a === start_b) {
        parent.insertBefore(
          a[end_i],
          a[start_i] || afterNode
        );
        end_a = a[--end_i];
        start_b = b[++start_j];
      }
      else {
        let i;
        // Lazily build maps here. They are relevant only if there has been
        // a move, or a mid-list insertion or deletion and not if there
        // has been an insertion at the end or deletion from the front.
        if (!need_indices) {
          need_indices = true;

          // Create a mapping from keys to their position in the old list
          for (i = 0; i < a.length; i++) {
            a_index.set(a[i], i);
          }
          // Create a mapping from keys to their position in the new list
          for (i = 0; i < b.length; i++) {
            b_index.set(b[i], i);
          }
        }

        old_start_j = a_index.get(start_b);
        new_start_i = b_index.get(start_a);

        // Insertion
        if (old_start_j === undefined) {
          parent.insertBefore(
            start_b,
            a[start_i] || afterNode
          );
          start_b = b[++start_j];
        }
        // Move
        else {
          parent.insertBefore(
            start_b,
            a[start_i] || afterNode
          );
          a[old_start_j] = null;
          start_b = b[++start_j];
        }
      }
    }
    if (start_i <= end_i || start_j <= end_j) {
      if (start_i > end_i) { // old list exhausted; process new list additions
        for (start_j; start_j <= end_j; start_b = b[++start_j]) {
          parent.insertBefore(start_b, a[start_i] || afterNode);
        }
      }
    }
    return b;
  }

/**** add (has been taken from former map "utils") ****/

  const GROUPING = '__g';

  let groupCounter = 0;

  function add (parent, value, endMark) {
    let mark;

    if (typeof value === 'string') {
      value = document.createTextNode(value);
    } else if (!(value instanceof Node)) {
      // Passing an empty array creates a DocumentFragment.
      value = api.h([], value);
    }

    if (
      value.nodeType === 11 &&
      (mark = value.firstChild) &&
      mark !== value.lastChild
    ) {
      mark[GROUPING] = value.lastChild[GROUPING] = ++groupCounter;
    }

    // If endMark is `null`, value will be added to the end of the list.
    parent.insertBefore(value, endMark);

    // Explicit undefined to store if frag.firstChild is null.
    return mark || value;
  }

[rozek]

Nota bene: the // Insertion and the process new list additions sections could probably also be removed from the reorder function in the snabbdom variant - but I did not test that yet