Iterate a Vec in reverse, while updating its elements/length

We have this in-place Vec manipulation, which happens in the forward direction:

    /// Steps the VM into the next operation.
    fn step_in(&mut self) {
        // iterate up to the *live* length (i.e. the loop is allowed to modify
        // the length).
        // NOTE: we need to use while-let so as to not borrow anything in an
        // iterator. filtering happens on the *result* of the iterator.
        let mut index_iter = 0..;
        while let Some(index) = index_iter.next().filter(|&i| {
            i < self.interp.frames.len()
        }) {
            let frame = &mut self.interp.frames[index];
            if frame.overstep > 0 || !frame.matches {
                // overstepped and non-matching frames
                *frame.overstep += 1;
            } else {
                if !frame.next() {
                    // empty/end-of frames
                    // 1 layer of step-in.
                    // step-out will undo this.
                    // this is correct because this branch implies overstep = 0
                    frame.overstep = 1;
                } else if matches!(
                    frame.op(),
                    PatternElement::SubtreeMarker,
                ) {
                    // subtrees!
                    // these are tricky, because the current frame can be moved
                    // in memory. so we have to use indexing every time.
                    // tho first we set it as overstep because it has special
                    // handling.
                    frame.overstep = 1;
                    let mut at = index + 1;
                    while self.interp.frames[index].next() {
                        let op = self.interp.frames[index].op();
                        if let PatternElement::ValueSubtree {
                            index: subtree, ..
                        } = op {
                            let new_frame = Frame {
                                ops: &self.interp.pat.protos[subtree][..],
                                iar: None,
                                overstep: None,
                            };
                            // we want the "newest" frame last, so it is
                            // easier to unwind back.
                            self.interp.frames.insert(at, new_frame);
                            at += 1;
                        } else {
                            unreachable!()
                        }
                    }
                }
            }
        }
    }

We need to make an in-place Vec manipulation which happens in the reverse direction. What's the cleanest way of doing so?

(Ideally we'd have a proper tree structure but eh meh :person_shrugging: )

Options we're considering:

  1. doing the same as the above, but with a shadowed index?
  2. honestly we really have no idea which is why we're trying to ask here.

Wow, there's a lot going on in that code.

Are you able to rephrase it using Vec::retain_mut() which updates/removes an item based on its current value, or is there some logic which requires access to multiple frames at a time to determine how/if an element should be updated?

Also, if this sort of operation is common, maybe Vec isn't the right data structure to be using and it'll be easier trying something else.

we cannot. step_out requires looking through multiple frames (and even updating multiple Vecs simultanenously!).

yeah a doubly-linked (...triple-linked?) tree structure would be ideal but those don't exist in Rust and we're not about to roll our own.

If you're looking for a tree structure, petgraph could probably help you out. It provides various graph datatypes with arbitrary node and edge weights, just picking the most appropriate one and using it as a tree would probably be much easier than manually implementing one yourself, as you seem to be doing here.

1 Like

Since that's an arbitrary graph library, we'd still need to implement the tree ourselves. We'd just be able to let petgraph handle the underlying storage.

we think we'll just go with this.