Method verify_tree

cranelift/bforest/src/pool.rs:82–206

Verify the consistency of the tree rooted at `node`.

(&self, node: Node, comp: &C)

impl<F: Forest> NodePool<F> {
    /// Verify the consistency of the tree rooted at `node`.
    pub fn verify_tree<C: Comparator<F::Key>>(&self, node: Node, comp: &C)
    where
        NodeData<F>: fmt::Display,
        F::Key: fmt::Display,
    {
        use crate::entity::EntitySet;
        use alloc::vec::Vec;
        use core::borrow::Borrow;
        use core::cmp::Ordering;

        // The root node can't be an inner node with just a single sub-tree. It should have been
        // pruned.
        if let NodeData::Inner { size, .. } = self[node] {
            assert!(size > 0, "Root must have more than one sub-tree");
        }

        let mut done = match self[node] {
            NodeData::Inner { size, .. } | NodeData::Leaf { size, .. } => {
                EntitySet::with_capacity(size.into())
            }
            _ => EntitySet::new(),
        };

        let mut todo = Vec::new();

        // Todo-list entries are:
        // 1. Optional LHS key which must be <= all node entries.
        // 2. The node reference.
        // 3. Optional RHS key which must be > all node entries.
        todo.push((None, node, None));

        while let Some((lkey, node, rkey)) = todo.pop() {
            assert!(done.insert(node), "Node appears more than once in tree");
            let mut lower = lkey;

            match self[node] {
                NodeData::Inner { size, keys, tree } => {
                    let size = size as usize;
                    let capacity = tree.len();
                    let keys = &keys[0..size];

                    // Verify occupancy.
                    // Right-most nodes can be small, but others must be at least half full.
                    assert!(
                        rkey.is_none() || (size + 1) * 2 >= capacity,
                        "Only {}/{} entries in {}:{}, upper={}",
                        size + 1,
                        capacity,
                        node,
                        self[node],
                        rkey.unwrap()
                    );

                    // Queue up the sub-trees, checking for duplicates.
                    for i in 0..size + 1 {
                        // Get an upper bound for node[i].
                        let upper = keys.get(i).cloned().or(rkey);