**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](https://nim-lang.org/docs/xmltree.html#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](https://hg.sr.ht/~sschwarzer/lazytree/browse) 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](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](https://hg.sr.ht/~sschwarzer/lazytree/browse/src/lazytree.nim?rev=80fb0cea3fe6830f0ed8e2c2b87fb2c3c45da24b) 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?
