API for getting immutable / mutable references to all values inside a node

[yusdacra]

My use-case is that I'm writing a tower::Service and I have a Node<Handler> where Handler implements tower::Service. What I want to do is implement poll_ready for this tower::Service, but I can't do it due to not being able to get mutable references to all values inside the node.

[ibraheemdev]

Would:

fn routes(&self) -> impl Iterator<Item = (&str, &T)>;
fn routes_mut(&mut self) -> impl Iterator<Item = (&str, &mut T)>;

Work for your use case?

[yusdacra]

Yes, that would be very nice.

[yusdacra]

Actually, I would be fine with only getting an iterator over the values. I looked into this a bit and wrote something that would do the job, which was just values and values_mut methods.

EDIT: I have a branch here if you want to check it out.

[ibraheemdev]

I would like to provide the routes as well. I think the best way to do this would be to store a list of full paths and indices at the root of the tree. Node prefixes could then just be an index and a range, and providing an iterator would just be self.full.iter()

[yusdacra]

I would like to provide the routes as well. I think the best way to do this would be to store a list of full paths and indices at the root of the tree. Node prefixes could then just be an index and a range, and providing an iterator would just be self.full.iter()

How would this be implemented (maybe a general overview?) I'm not very familiar with radix trees. Would like to PR this!

[ibraheemdev]

I'm thinking something like:

pub struct Root<T> {
   node: Node<T>,
   // a list of prefixes, and nested indices
   paths: Vec<(Vec<u8>, Vec<u8>)>
}

impl Root<T> {
    // this would really be a concrete iterator type
    fn routes(&self) -> impl Iterator<Item = (&str, &T)> {
        self.paths.iter().map(|(path, indices)| {
            unsafe {
                &*indices.fold(&self.node, |node, i| &node.children[i]).value.get().unwrap()
            }
        })
    }
    
    // rest of node methods here...
}

When you insert a route, you add the route path, and the path (indices) to the value in the tree. It would need to be updated when the tree is shifted around. As an optimization, Node { prefix: Vec<u8>, .. } could be changed to a (usize, Range<usize>), pointing to a element and prefix in paths, but that isn't necessary at first.

This way iteration is very cheap; we don't have to allocate a stack for traversal.

[yusdacra]

I have implemented this on: https://github.com/yusdacra/matchit/tree/feat/values

My implementation is pretty different as it does not store indices, instead it takes advantage from the fact that the values don't get moved / removed. I have added tests to verify that it works properly. It however does add new unsafe, so it might not be wanted.

[ibraheemdev]

Your code aliases a Box, which is UB. You could do this with NonNull, but I would prefer the index-based solution.

[yusdacra]

Your code aliases a Box, which is UB. You could do this with NonNull, but I would prefer the index-based solution.

Hmm, yeah I checked around and it seems it's UB... I will try the index-based solution again then. I first tried the index-based solution but couldn't figure out how to properly get the indices...

[ibraheemdev]

Because of the tree structure it's not easy for us to create an efficient iterator. I don't want to expose a slow stack-based iterator because use cases like poll_ready are often performance sensitive. For anyone who needs this, I would suggest using a Router<usize> that stores indices into a separate Vec/SlotMap, and iterating over that.