Struct TreeVisitor 

pub struct TreeVisitor<'tree, T> {
    pub nodes: &'tree mut UniValMap<Node>,
    pub data: &'tree mut T,
}

Internal contents of Tree with the minimum of mutable access for For soundness do not modify the children or parent indexes of nodes during traversal.

Fields

nodes: &'tree mut UniValMap<Node>

data: &'tree mut T

Implementations

impl<'tree, T> TreeVisitor<'tree, T>

pub fn traverse_this_parents_children_other<Err>( self, start_idx: UniIndex, f_continue: impl Fn(&NodeAppArgs<'_, T>) -> ContinueTraversal, f_propagate: impl FnMut(NodeAppArgs<'_, T>) -> Result<(), Err>, ) -> Result<UniIndex, Err>

Applies f_propagate to every vertex of the tree in a piecewise bottom-up way: First, visit all ancestors of start_idx (starting with start_idx itself), then children of start_idx, then the rest, going bottom-up in each of these two “pieces” / sections. This ensures that errors are triggered in the following order

• first invalid accesses with insufficient permissions, closest to the accessed node first,
• then protector violations, bottom-up, starting with the children of the accessed node, and then going upwards and outwards.

The following graphic visualizes it, with numbers indicating visitation order and start_idx being the node that is visited first (“1”):

        3
       /|
      / |
     9  2
     |  |\
     |  | \
     8  1  7
       / \
      4   6
          |
          5

f_propagate should follow the following format: for a given Node it updates its Permission depending on the position relative to start_idx (given by an AccessRelatedness). f_continue is called earlier on foreign nodes, and describes whether to even start visiting the subtree at that node. If it e.g. returns SkipSelfAndChildren on node 6 above, then nodes 5 and 6 would not be visited by f_propagate. It is not used for notes having a child access (nodes 1, 2, 3).

Finally, remember that the iteration order is not relevant for UB, it only affects diagnostics. It also affects tree traversal optimizations built on top of this, so those need to be reviewed carefully as well whenever this changes.

Returns the index of the root of the accessed tree.

pub fn traverse_nonchildren<Err>( self, start_idx: UniIndex, f_continue: impl Fn(&NodeAppArgs<'_, T>) -> ContinueTraversal, f_propagate: impl FnMut(NodeAppArgs<'_, T>) -> Result<(), Err>, ) -> Result<UniIndex, Err>

Like traverse_this_parents_children_other, but skips the children of start_idx.

Returns the index of the root of the accessed tree.

pub fn traverse_children_this<Err>( self, start_idx: UniIndex, f_continue: impl Fn(&NodeAppArgs<'_, T>) -> ContinueTraversal, f_propagate: impl FnMut(NodeAppArgs<'_, T>) -> Result<(), Err>, ) -> Result<(), Err>

Traverses all children of start_idx including start_idx itself. Uses f_continue to filter out subtrees and then processes each node with f_propagate so that the children get processed before their parents.

Layout

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 16 bytes