nextSibling issue - Githubissues

dy commented 4 years ago

  let parent = new Dommy()
  const childNodes = [];
  for (let i = 0; i < 100; i++) childNodes.push(new Nody(parent, i));

  console.log(childNodes[0].nextSibling)  // here it's end node
  parent.appendChild(childNodes[1])
  console.log(childNodes[0].nextSibling) // here it's childNodes[1]

luwes commented 4 years ago

not ideal, is it resulting in wrong behavior in the benchmark?

dy commented 4 years ago

It breaks some algos that depend on checking nextSibling, like swapping items etc.

dy commented 4 years ago

In particular, than bug doesn't allow this 235b implementation to be qualified:

export function merge (parent, a, b, before) {
  const bs = new Set(b), as = new Set(a)
  let i, ai, bi, off

  // walk by b from tail
  // a: 1 2 3 4 5, b: 1 2 3 → off: +2
  for (i = b.length, off = a.length - b.length; i--;) {
    ai = a[i + off], bi = b[i]

    if (ai === bi) {}

    // replace
    else if (ai && !as.has(bi) && !bs.has(ai)) (parent.replaceChild(bi, ai))

    // remove
    else if (ai && !bs.has(ai)) (parent.removeChild(ai), off--, i++)

    else if (bi.nextSibling != before || !bi.nextSibling) {
      // swap
      if (as.has(bi)) (parent.insertBefore(ai, bi), off--)

      // insert
      parent.insertBefore(bi, before), off++
    }

    before = bi
  }

  return b
}

In real dom it works brilliant. I couldn't manage to figure out why there's _childNodes with extra element and fix that.

dy commented 4 years ago

Interestingly, list-difference is broken in real DOM due to that reason.

dy commented 4 years ago

Ok, just in case - reproduced benchmark in DOM fully: https://github.com/spectjs/spect/blob/h-reducers/test/diff.js Libs seems to be broken on real DOM, unfortunately.

luwes commented 4 years ago

great find, which ones are broken?

dy commented 4 years ago

I've tested list-difference, snabbdom, udomdiff - all algos seem to fail on real DOM (I've just reproduced benchmark tests). It's due to that childNodes.lastElement thing I suppose.

dy commented 4 years ago

Just in case - there are multiple various DOM implementations for nodejs:

luwes commented 4 years ago

hmm that would be strange, that all would be failing.

yea good idea, I haven't thought of using a more robust DOM library. I'll look into some. I guess we would want to keep the operation count but that could be patched on maybe.

luwes commented 4 years ago

ah I see you removed the before node completely. yes I think some algorithms really rely on that to be there.

luwes commented 4 years ago

also wanted to mention sometimes spect fails the assertion of the shuffled test. not a lot but once every 3 or 4 times.

dy commented 4 years ago

Thanks for letting know. I caught similar error rewriting the thing today, basically nextSibling array was error-prone. The 232b version doesn't have that issue:

WebReflection commented 4 years ago

I couldn't manage to figure out why there's _childNodes with extra element and fix that.

As the benchmark was born after a file which only purpose was to code-cover synthetically udomdiff, benchmark that simply reproduces what js-framework-benchmark showcases, the last element is needed to pin the operation in a specific point.

Here how it works:

<body>
  <!--pin-->
</body>

That pin comment node, makes it possible to confine all operations before it.

var newNodes = udomdiff(
  document.body,
  [],
  [document.createElement('a'), document.createElement('b')],
  pin
);

After this operation, the layout would look like:

<body>
  <a></a><b></b>
  <!--pin-->
</body>

The pin basically confines operations because otherwise, if a node that should be inserted but it's not live yet, uses nextSibling, and the value is null, the insertBefore operation would append that node at the end of the parent container, and the end can be after any other node.

udomdiff is a standalone library that covers all real-world uses cases I could try, so if there's a scenario where it fails in the real DOM, but again, it's heavily tested against that, an issue filed in udomdiff repository would be much better than discussing in here the Dommy facade, as that's, once again, there only to synthetically quickly test and benchmark the library, it was never meant to be used across multiple libraries.

You can try basichtml or jsdom instead, if you want a more reliable DOM env, or you can rewrite Dommy as such:

class Dommy extends Array {
  constructor() {
    super().operations = [];
  }
  get childNodes() {
    return this.slice(0);
  }
  get textContent() {
    return this.map(node => node.value).join('');
  }
  insertBefore(newNode, liveNode) {
    // add operation
    if (newNode === liveNode)
      return;
    this._remove(newNode);
    if (liveNode == null)
      this.push(newNode);
    else {
      const i = this.indexOf(liveNode);
      if (i < 0)
        throw new Error('invalid insertBefore');
      this.splice(i, 0, newNode);
    }
    newNode.dommy = this;
  }
  replaceChild(newNode, oldNode) {
    // add operation
    this._remove(newNode);
    const i = this.indexOf(oldNode);
    if (i < 0)
        throw new Error('invalid replaceChild');
    this[i] = newNode;
    newNode.dommy = this;
    oldNode.dommy = [];
  }
  removeChild(node) {
    // add operation
    if (!this.includes(node))
      throw new Error('invalid removeChild');
    this._remove(node);
    node.dommy = [];
  }
  _remove(node) {
    const i = this.indexOf(node);
    if (i < 0)
      this.splice(i, 1);
  }

  // previously ...
  // count() { return this.length; }
  // reset() { this.splice(0); }
}

class Nody {
  constructor(value) {
    this.dommy = [];
    this.value = value;
  }
  get nextSibling() {
    const i = this.dommy.indexOf(this) + 1;
    return 0 < i && i < this.dommy.length ? this.dommy[i] : null;
  }
}

At that point you can either do an initial push of a comment node and pass it along, verifying that it never gets removed and it's always the last element, or you can just drop the before part, as this particular benchmark doesn't need it.

I would prefer to keep the pin concept, as diffing without that ability, in the real-world is kinda useless, 'cause handling all nodes per each container, is not really how libraries applied to the DOM work.

dy commented 4 years ago

The pin basically confines operations because otherwise, if a node that should be inserted but it's not live yet, uses nextSibling, and the value is null, the insertBefore operation would append that node at the end of the parent container, and the end can be after any other node.

I see. In other words, to differentiate detached element from the last element in container in eg. el.nextSibling === end case. That problem is mixing of concerns - figuring out node.parentNode === currentParent and node.nextSibling === null in a single node.nextSibling === null check. Btw that's not mandatory for all algos - some do just fine considering end === null as the "end of container", same as el.insertBefore(child, null).

I tried rewriting Dommy for both problems - refs for nextSibling/previousSibling instead of indexOf and getting rid of _childNodes, with little success.

diffing without that ability, in the real-world is kinda useless

I'd rather disagree: diffing all child nodes of a container is what react/preact/morphdom/nanomorph/etc do: render(children, container), and the last element is implied null here, so algos should be just fine without last pin.

I see you fixed that in the #19, great!

WebReflection commented 4 years ago

Btw that's not mandatory for all algos

I've removed the before from the equation, it's optionally enabled on top of the file now.

render(children, container)

same goes for uhtml, render(where, what), but when it maps a template literal, it needs to know where to work, and never append anything after, example:

render(document.body, html`
  <div>
    ${items.map(item => html`<p>${item.value}</p>`)}
    <p>This should stay</p>
  </div>
`);

The udomdiff before element here becomes handy because it will work on this tree:

<div>
  <!--pin-->
  <p>This should stay</p>
</div>

The list of items can grow and shrink at any time and nothing will ever be appended to that container.

<div>
  <p>first</p>
  <p>second</p>
  <!--pin-->
  <p>This should stay</p>
</div>

However, I see that even enabling the before in the current refactoring, all libraries seems to work just fine, as they use nextSibling anyway, so they work in a clean way, which is why I am not using before anymore, but all libraries could receive it, either as undefined/null or as a proper node.

luwes / js-diff-benchmark

nextSibling issue #16