Mirror of forum.nim-lang.org

6393 :: Further development of a tree iterator that allows mutations

• sschwarzer (orginal) [2020-05-31T15:14:48+02:00] view original

  TL;DR: I've done some work on a recursive tree iterator that allows modifying the tree while iterating. For further development, I need your feedback about the mutations the iterator should support.

  In a recent project, I needed the ability to delete nodes from an xmltree.XmlNode tree while iterating over that tree. Something like:

  for nodeInfo in treeIter(rootNode):
    if nodeInfo.node.kind == xnElement and nodeInfo.node.tag in @[...]:
      nodeInfo.parentNode.delete(nodeInfo.childIndex)
    # Possibly do other things with the node.
    ...
  Run

  If you delete a node, the iterator doesn't descend into the children of the deleted node. Recursive iteration continues with the node after the deleted node.

  I have an implementation that can do this. The iterator detects deletions by comparing the number of child nodes between iterations.

  In a discussion in https://forum.nim-lang.org/t/5697 and yesterday on IRC, I had the impression that there was some interest in such an iterator. However, there were also requests to support insertions in the tree during the iteration, which sounds quite reasonable. Supporting this is more complicated though, especially in the case where you delete a node and insert one at the same position.

  I'm now a bit lost about how I should continue with this project. Personally, I only need deletions, but I'm quite open for enhancements. But I'm not sure what enhancements should be implemented. Neither do I want to implement unnecessary features nor would I like it if the iterator was mostly unusable for you because important features are missing.

  So my question is: How would you want to use such an iterator? Your requirements may be clearer if you add some hypothetical example code.

  Here's some more context if you're interested:

  • The current version of the iterator uses generics to support any type with the operations parentNode.len(), parentNode[index] and parentNode.delete(index). For insertions you'd need parentNode.insert(newChildNode, index).
  • If "your" node type doesn't support these operations, you would need to add them (with the semantics of xmltree.XmlNode). That said, I'm also open to support a more generic API instead of modeling the API on XmlNode if there are good reasons.
  • At the moment, you can delete nodes as in the example above. However, if the iterator should support more features, it would probably be better to use proxy methods on the nodeInfo objects, say, nodeInfo.deleteNode(). This also would make it easier to describe to a user which operations and combinations of them are supported.
  • The nodeInfo object could be extended to have fields for the nesting level or some kind of path. (I'm not sure about the path because different types of trees may need different path concepts/representations.)
  • You may think you could just compare nodes to check if a node has been replaced by another. However, for tree structures this can be complicated. For example, consider two XML nodes that only differ in one attribute value for one grandgrandgrandchild. You'd need a recursive comparison which might be expensive and if your node type doesn't already have such a comparison, you'd need to implement it. Hence I'd rather like to avoid this.
  • I haven't checked whether there are other projects which already provide such an iterator. In that case, I'd be thankful for pointers. Maybe we don't need another iterator then?

---

• cblake (orginal) [2020-05-31T18:37:42+02:00] view original

  I think not descending into a just-inserted-node makes total sense. By definition, you had to either unlink such a subtree from somewhere else or you had to forge it/create it. So, treating it like an atom in this iterator makes sense just as not descending the deleted node does. This solves the delete-then-insert right at the same spot problem, too. I think if you treat the inserts as "atoms" like the "deletes" it works out.

  You might want to provide an API call named "replace" that does the delete/insert pair so client code can be clear about that. Not having the "iteration contract" mean descending into either seems the clean semantic. Just my opinion, of course.

  It might be worth searching for XML Tree (or HTML DOM) surgery APIs in other programming languages for ideas. Another possible use case of all this might be editing Nim ASTs in macros which I don't think has been mentioned thus far. (I didn't check IRC.)

---