Iterate over Arena in Depth-first order

[georgemp]

Hi,

Is there anyway to iterate over all the nodes in an Arena in a depth-first order (iter seems to be in storage order). At the moment, I'm tracking all the root nodeid's (during insertion) in a separate vec, and, then iterating over each of their descendants. I was wondering, if there is a better way to do this? Thanks

[lo48576]

Use NodeId::descendants().

Note that this is implemented to NodeId, not arena, because the arena can have multiple unordered top-level nodes.
Currently there seems no ways to get toplevel nodes efficiently...

[lo48576]

Creating virtual root nodes and using it as the parent of actual top-level nodes would be a workaround.

[georgemp]

Use NodeId::descendants().

Note that this is implemented to NodeId, not arena, because the arena can have multiple unordered top-level nodes.
Currently there seems no ways to get toplevel nodes efficiently...

Makes sense.

Creating virtual root nodes and using it as the parent of actual top-level nodes would be a workaround.

Having a top level (virtual) l node would still require tracking (passing around) an entity that is external to the arena. Wish there was an easier way to track/get the toplevel nodes, but, this works for now :)

Edit: Added virtual to make clear that the node to be tracked is virtual

[coderedart]

I was wondering if arena could have this functionality built in.

I can workaround this issue with the above mentioned virtual root node trick or tracking top level nodes methods, but is this really that hard to implement into the crate itself?

Can arena maybe have a method to return all top level nodes maybe? Then I can simply call descendants on those top level nodes.

[alexmozaidze]

It would be possible to create a newtype for Arena that would simply make the root node inaccessible and leave everything else as-is. It would also be zero-cost in case we define that the root node is always at index 0:

#[repr(transparent)]
struct IndexTree<T>(Arena<T>);

It would take some planning to make it ergonomic, but it's theoretically possible.

Can arena maybe have a method to return all top level nodes maybe? Then I can simply call descendants on those top level nodes.

This would require a lot of changes. Arena is functionally like an allocator for homogenous data types, it is much simpler to make an abstraction over Arena than to add more cases and states to Arena itself.