Note on mutation

[jlevy]

This is a doc suggestion + a more general question.

It may be worth putting in the docs some thoughts on what the contract is wrt mutating the tree. In particular, modifying individual nodes is fine, but unist-util-visit assumes the visitor does not mutate the number of children of the parent.

This is a bit of a pitfall, as it's not uncommon to want to traverse and mutate adjacent children. For example, see https://github.com/jackycute/remark-html-emoji-image/blob/master/index.js#L66-L69 — but it appears that approach is buggy, since unist-util-visit visits children sequentially by index.

More generally, I'd be interested to know what approach is best to handle the fully mutating use case. https://github.com/syntax-tree/unist-util-map and https://github.com/eush77/unist-util-filter are listed but cover different use cases. One easy option (but may not be the best) is to make a visit-dynamic variant, something like:

'use strict';

module.exports = visit;

/**
 * A mutating version of https://github.com/syntax-tree/unist-util-visit
 *
 * Traverse a Unist tree, while also allowing addition/deletion of children.
 * Visitor should return number of nodes added/deleted (positive for addition, negative for removal,
 * 0 if only visited), or false to terminate. To avoid confusion, we don't support reverse traversal.
 */
function visit(tree, type, visitor) {
  if (typeof type === 'function') {
    visitor = type;
    type = null;
  }

  one(tree);

  /* Visit a single node. */
  function one(node, index, parent) {
    let result;

    index = index || (parent ? 0 : null);

    if (!type || node.type === type) {
      result = visitor(node, index, parent || null);
    }

    if (node.children && result !== false) {
      all(node);
    }

    return result;
  }

  /* Visit children in `parent`, possibly adding or removing children. */
  function all(parent) {
    let child;
    let index = 0;
    while (index < parent.children.length) {
      child = parent.children[index];

      let delta = 0;
      if (child) {
        delta = one(child, index, parent);
        if (delta === false) {  // Abort.
          return;
        }
      }

      index += 1 + (delta || 0);
    }
  }
}

[wooorm]

Hey Joshua! I’m extremely sorry for the long wait. I’ve been busy with holiday, and then super busy creating a new course (which is actually paid, so I’d like to make that great too). I know, I know, excuses. Anyway, thanks for waiting!

It may be worth putting in the docs some thoughts on what the contract is wrt mutating the tree. In particular, modifying individual nodes is fine, but unist-util-visit assumes the visitor does not mutate the number of children of the parent.

Correct. If we’re talking about docs here. What do you suggest?

More generally, I'd be interested to know what approach is best to handle the fully mutating use case. https://github.com/syntax-tree/unist-util-map and https://github.com/eush77/unist-util-filter are listed but cover different use cases. One easy option (but may not be the best) is to make a visit-dynamic variant, something like:

That looks good! I think that makes sense to have, so I’d support a utility that does that!

I had a similar problem building natural language parsers, and wrapped it in array-iterate. Maybe that can be useful too?

I hope you’re still interested in this, cheers,

Titus

[wooorm]

@jlevy Ping! :)

I know I know, I took way longer 😛

[jlevy]

Hey @wooorm ! Cool, thanks for the response. Well, good to hear my understanding matches yours. :)

We ended up using visit-dynamic variant I put above, and it's been working fine for our use cases. I'm not sure if I'll have bandwidth to publish/maintain it myself right now — perhaps we can set it up under syntax-tree as an alternative to this visitor, if you think it's useful? You're welcome to the code above!

Also just PR'ed a doc clarification.

[wooorm]

Sweet, thanks! I added you to the org, so feel free to create a utility here and we’ll help maintain it!

How much code would it add in this utility to have this added here though, without breaking current things?

[jlevy]

Cool, thanks. Hm on second thought, yes, I believe you can just add support here by modifying your existing all() to something like (code not tested!):

  /* Visit children in `parent`, possibly adding or removing children. */
  function all(children, parent) {
    var sign = reverse ? -1 : 1;
    var index = reverse ? children.length - 1 : 0;
    var child;

    while (index >= 0 && index < children.length) {
      child = children[index];

      let delta = 0;
      if (child && (delta = one(child, index, parent)) === false) {
        return false;
      }

      index += sign * (1 + (delta || 0));
    }

    return true;
  }

This should then support forward/reverse, abort, and adding/removing nodes. Luckily the check you currently have for false (abort) is exact (===) so it won't conflate 0 and false, and so should be backwards compatible with previous uses of this lib. :)

[wooorm]

Done! Only difference is that this quires absolute indexes, instead of your proposed deltas.

[jlevy]

cool!