miri/borrow_tracker/tree_borrows/

tree.rs

//! In this file we handle the "Tree" part of Tree Borrows, i.e. all tree
//! traversal functions, optimizations to trim branches, and keeping track of
//! the relative position of the access to each node being updated. This of course
//! also includes the definition of the tree structure.
//!
//! Functions here manipulate permissions but are oblivious to them: as
//! the internals of `Permission` are private, the update process is a black
//! box. All we need to know here are
//! - the fact that updates depend only on the old state, the status of protectors,
//!   and the relative position of the access;
//! - idempotency properties asserted in `perms.rs` (for optimizations)

use std::ops::Range;
use std::{cmp, fmt, mem};

use rustc_abi::Size;
use rustc_data_structures::fx::FxHashSet;
use rustc_span::Span;
use smallvec::SmallVec;

use super::diagnostics::{
    AccessCause, DiagnosticInfo, NodeDebugInfo, TbError, TransitionError,
    no_valid_exposed_references_error,
};
use super::foreign_access_skipping::IdempotentForeignAccess;
use super::perms::{PermTransition, Permission};
use super::tree_visitor::{ChildrenVisitMode, ContinueTraversal, NodeAppArgs, TreeVisitor};
use super::unimap::{UniIndex, UniKeyMap, UniValMap};
use super::wildcard::ExposedCache;
use crate::borrow_tracker::{AccessKind, GlobalState, ProtectorKind};
use crate::*;

mod tests;

/// Data for a reference at single *location*.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub(super) struct LocationState {
    /// A location is "accessed" when it is child-accessed for the first time (and the initial
    /// retag initializes the location for the range covered by the type), and it then stays
    /// accessed forever.
    /// For accessed locations, "permission" is the current permission. However, for
    /// non-accessed locations, we still need to track the "future initial permission": this will
    /// start out to be `default_initial_perm`, but foreign accesses need to be taken into account.
    /// Crucially however, while transitions to `Disabled` would usually be UB if this location is
    /// protected, that is *not* the case for non-accessed locations. Instead we just have a latent
    /// "future initial permission" of `Disabled`, causing UB only if an access is ever actually
    /// performed.
    /// Note that the tree root is also always accessed, as if the allocation was a write access.
    accessed: bool,
    /// This pointer's current permission / future initial permission.
    permission: Permission,
    /// See `foreign_access_skipping.rs`.
    /// Stores an idempotent foreign access for this location and its children.
    /// For correctness, this must not be too strong, and the recorded idempotent foreign access
    /// of all children must be at least as strong as this. For performance, it should be as strong as possible.
    idempotent_foreign_access: IdempotentForeignAccess,
}

impl LocationState {
    /// Constructs a new initial state. It has neither been accessed, nor been subjected
    /// to any foreign access yet.
    /// The permission is not allowed to be `Unique`.
    /// `sifa` is the (strongest) idempotent foreign access, see `foreign_access_skipping.rs`
    pub fn new_non_accessed(permission: Permission, sifa: IdempotentForeignAccess) -> Self {
        assert!(permission.is_initial() || permission.is_disabled());
        assert!(!permission.is_unique());
        Self { permission, accessed: false, idempotent_foreign_access: sifa }
    }

    /// Constructs a new initial state. It has not yet been subjected
    /// to any foreign access. However, it is already marked as having been accessed.
    /// `sifa` is the (strongest) idempotent foreign access, see `foreign_access_skipping.rs`
    pub fn new_accessed(permission: Permission, sifa: IdempotentForeignAccess) -> Self {
        Self { permission, accessed: true, idempotent_foreign_access: sifa }
    }

    /// Checks whether the current location state is ever reachable in a real execution.
    pub fn possible(&self) -> bool {
        // `Unique` can only be reached on actually accessed locations.
        self.accessed || !self.permission.is_unique()
    }

    /// Check if the location has been accessed, i.e. if it has
    /// ever been accessed through a child pointer.
    pub fn accessed(&self) -> bool {
        self.accessed
    }

    pub fn permission(&self) -> Permission {
        self.permission
    }

    /// Performs an access on this index and updates node,
    /// perm and wildcard_state to reflect the transition.
    fn perform_transition(
        &mut self,
        idx: UniIndex,
        nodes: &mut UniValMap<Node>,
        exposed_cache: &mut ExposedCache,
        access_kind: AccessKind,
        relatedness: AccessRelatedness,
        protected: bool,
        diagnostics: &DiagnosticInfo,
    ) -> Result<(), TransitionError> {
        // Call this function now (i.e. only if we know `relatedness`), which
        // ensures it is only called when `skip_if_known_noop` returns
        // `Recurse`, due to the contract of `traverse_this_parents_children_other`.
        self.record_new_access(access_kind, relatedness);
        let old_access_level = self.permission.strongest_allowed_local_access(protected);
        let transition = self.perform_access(access_kind, relatedness, protected)?;
        if !transition.is_noop() {
            let node = nodes.get_mut(idx).unwrap();
            // Record the event as part of the history.
            node.debug_info
                .history
                .push(diagnostics.create_event(transition, relatedness.is_foreign()));

            // We need to update the wildcard state, if the permission
            // of an exposed pointer changes.
            if node.is_exposed {
                let access_level = self.permission.strongest_allowed_local_access(protected);
                exposed_cache.update_exposure(nodes, idx, old_access_level, access_level);
            }
        }
        Ok(())
    }

    /// Apply the effect of an access to one location, including
    /// - applying `Permission::perform_access` to the inner `Permission`,
    /// - emitting protector UB if the location is accessed,
    /// - updating the accessed status (child accesses produce accessed locations).
    fn perform_access(
        &mut self,
        access_kind: AccessKind,
        rel_pos: AccessRelatedness,
        protected: bool,
    ) -> Result<PermTransition, TransitionError> {
        let old_perm = self.permission;
        let transition = Permission::perform_access(access_kind, rel_pos, old_perm, protected)
            .ok_or(TransitionError::ChildAccessForbidden(old_perm))?;
        self.accessed |= !rel_pos.is_foreign();
        self.permission = transition.applied(old_perm).unwrap();
        // Why do only accessed locations cause protector errors?
        // Consider two mutable references `x`, `y` into disjoint parts of
        // the same allocation. A priori, these may actually both be used to
        // access the entire allocation, as long as only reads occur. However,
        // a write to `y` needs to somehow record that `x` can no longer be used
        // on that location at all. For these non-accessed locations (i.e., locations
        // that haven't been accessed with `x` yet), we track the "future initial state":
        // it defaults to whatever the initial state of the tag is,
        // but the access to `y` moves that "future initial state" of `x` to `Disabled`.
        // However, usually a `Reserved -> Disabled` transition would be UB due to the protector!
        // So clearly protectors shouldn't fire for such "future initial state" transitions.
        //
        // See the test `two_mut_protected_same_alloc` in `tests/pass/tree_borrows/tree-borrows.rs`
        // for an example of safe code that would be UB if we forgot to check `self.accessed`.
        if protected && self.accessed && transition.produces_disabled() {
            return Err(TransitionError::ProtectedDisabled(old_perm));
        }
        debug_assert!(self.possible());
        Ok(transition)
    }

    /// Like `perform_access`, but ignores the concrete error cause and also uses state-passing
    /// rather than a mutable reference. As such, it returns `Some(x)` if the transition succeeded,
    /// or `None` if there was an error.
    #[cfg(test)]
    fn perform_access_no_fluff(
        mut self,
        access_kind: AccessKind,
        rel_pos: AccessRelatedness,
        protected: bool,
    ) -> Option<Self> {
        match self.perform_access(access_kind, rel_pos, protected) {
            Ok(_) => Some(self),
            Err(_) => None,
        }
    }

    /// Tree traversal optimizations. See `foreign_access_skipping.rs`.
    /// This checks if such a foreign access can be skipped.
    fn skip_if_known_noop(
        &self,
        access_kind: AccessKind,
        rel_pos: AccessRelatedness,
    ) -> ContinueTraversal {
        if rel_pos.is_foreign() {
            let happening_now = IdempotentForeignAccess::from_foreign(access_kind);
            let mut new_access_noop =
                self.idempotent_foreign_access.can_skip_foreign_access(happening_now);
            if self.permission.is_disabled() {
                // A foreign access to a `Disabled` tag will have almost no observable effect.
                // It's a theorem that `Disabled` node have no protected accessed children,
                // and so this foreign access will never trigger any protector.
                // (Intuition: You're either protected accessed, and thus can't become Disabled
                // or you're already Disabled protected, but not accessed, and then can't
                // become accessed since that requires a child access, which Disabled blocks.)
                // Further, the children will never be able to read or write again, since they
                // have a `Disabled` parent. So this only affects diagnostics, such that the
                // blocking write will still be identified directly, just at a different tag.
                new_access_noop = true;
            }
            if self.permission.is_frozen() && access_kind == AccessKind::Read {
                // A foreign read to a `Frozen` tag will have almost no observable effect.
                // It's a theorem that `Frozen` nodes have no `Unique` children, so all children
                // already survive foreign reads. Foreign reads in general have almost no
                // effect, the only further thing they could do is make protected `Reserved`
                // nodes become conflicted, i.e. make them reject child writes for the further
                // duration of their protector. But such a child write is already rejected
                // because this node is frozen. So this only affects diagnostics, but the
                // blocking read will still be identified directly, just at a different tag.
                new_access_noop = true;
            }
            if new_access_noop {
                // Abort traversal if the new access is indeed guaranteed
                // to be noop.
                // No need to update `self.idempotent_foreign_access`,
                // the type of the current streak among nonempty read-only
                // or nonempty with at least one write has not changed.
                ContinueTraversal::SkipSelfAndChildren
            } else {
                // Otherwise propagate this time, and also record the
                // access that just occurred so that we can skip the propagation
                // next time.
                ContinueTraversal::Recurse
            }
        } else {
            // A child access occurred, this breaks the streak of foreign
            // accesses in a row and the sequence since the previous child access
            // is now empty.
            ContinueTraversal::Recurse
        }
    }

    /// Records a new access, so that future access can potentially be skipped
    /// by `skip_if_known_noop`. This must be called on child accesses, and otherwise
    /// should be called on foreign accesses for increased performance. It should not be called
    /// when `skip_if_known_noop` indicated skipping, since it then is a no-op.
    /// See `foreign_access_skipping.rs`
    fn record_new_access(&mut self, access_kind: AccessKind, rel_pos: AccessRelatedness) {
        debug_assert!(matches!(
            self.skip_if_known_noop(access_kind, rel_pos),
            ContinueTraversal::Recurse
        ));
        self.idempotent_foreign_access
            .record_new(IdempotentForeignAccess::from_acc_and_rel(access_kind, rel_pos));
    }
}

impl fmt::Display for LocationState {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "{}", self.permission)?;
        if !self.accessed {
            write!(f, "?")?;
        }
        Ok(())
    }
}
/// The state of the full tree for a particular location: for all nodes, the local permissions
/// of that node, and the tracking for wildcard accesses.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct LocationTree {
    /// Maps a tag to a perm, with possible lazy initialization.
    ///
    /// NOTE: not all tags registered in `Tree::nodes` are necessarily in all
    /// ranges of `perms`, because `perms` is in part lazily initialized.
    /// Just because `nodes.get(key)` is `Some(_)` does not mean you can safely
    /// `unwrap` any `perm.get(key)`.
    ///
    /// We do uphold the fact that `keys(perms)` is a subset of `keys(nodes)`
    pub perms: UniValMap<LocationState>,
    /// Caches information about the relatedness of nodes for a wildcard access.
    pub exposed_cache: ExposedCache,
}
/// Tree structure with both parents and children since we want to be
/// able to traverse the tree efficiently in both directions.
#[derive(Clone, Debug)]
pub struct Tree {
    /// Mapping from tags to keys. The key obtained can then be used in
    /// any of the `UniValMap` relative to this allocation, i.e.
    /// `nodes`, `LocationTree::perms` and `LocationTree::exposed_cache`
    /// of the same `Tree`.
    /// The parent-child relationship in `Node` is encoded in terms of these same
    /// keys, so traversing the entire tree needs exactly one access to
    /// `tag_mapping`.
    pub(super) tag_mapping: UniKeyMap<BorTag>,
    /// All nodes of this tree.
    pub(super) nodes: UniValMap<Node>,
    /// Associates with each location its state and wildcard access tracking.
    pub(super) locations: DedupRangeMap<LocationTree>,
    /// Contains both the root of the main tree as well as the roots of the wildcard subtrees.
    ///
    /// If we reborrow a reference which has wildcard provenance, then we do not know where in
    /// the tree to attach them. Instead we create a new additional tree for this allocation
    /// with this new reference as a root. We call this additional tree a wildcard subtree.
    ///
    /// The actual structure should be a single tree but with wildcard provenance we approximate
    /// this with this ordered set of trees. Each wildcard subtree is the direct child of *some* exposed
    /// tag (that is smaller than the root), but we do not know which. This also means that it can only be the
    /// child of a tree that comes before it in the vec ensuring we don't have any cycles in our
    /// approximated tree.
    ///
    /// Sorted according to `BorTag` from low to high. This also means the main root is `root[0]`.
    ///
    /// Has array size 2 because that still ensures the minimum size for SmallVec.
    pub(super) roots: SmallVec<[UniIndex; 2]>,
}

/// A node in the borrow tree. Each node is uniquely identified by a tag via
/// the `nodes` map of `Tree`.
#[derive(Clone, Debug)]
pub(super) struct Node {
    /// The tag of this node.
    pub tag: BorTag,
    /// All tags except the root have a parent tag.
    pub parent: Option<UniIndex>,
    /// If the pointer was reborrowed, it has children.
    // FIXME: bench to compare this to FxHashSet and to other SmallVec sizes
    pub children: SmallVec<[UniIndex; 4]>,
    /// Either `Reserved`,  `Frozen`, or `Disabled`, it is the permission this tag will
    /// lazily be initialized to on the first access.
    /// It is only ever `Disabled` for a tree root, since the root is initialized to `Unique` by
    /// its own separate mechanism.
    default_initial_perm: Permission,
    /// The default initial (strongest) idempotent foreign access.
    /// This participates in the invariant for `LocationState::idempotent_foreign_access`
    /// in cases where there is no location state yet. See `foreign_access_skipping.rs`,
    /// and `LocationState::idempotent_foreign_access` for more information
    default_initial_idempotent_foreign_access: IdempotentForeignAccess,
    /// Whether a wildcard access could happen through this node.
    pub is_exposed: bool,
    /// Some extra information useful only for debugging purposes.
    pub debug_info: NodeDebugInfo,
}

impl Tree {
    /// Create a new tree, with only a root pointer.
    pub fn new(root_tag: BorTag, size: Size, span: Span) -> Self {
        // The root has `Disabled` as the default permission,
        // so that any access out of bounds is invalid.
        let root_default_perm = Permission::new_disabled();
        let mut tag_mapping = UniKeyMap::default();
        let root_idx = tag_mapping.insert(root_tag);
        let nodes = {
            let mut nodes = UniValMap::<Node>::default();
            let mut debug_info = NodeDebugInfo::new(root_tag, root_default_perm, span);
            // name the root so that all allocations contain one named pointer
            debug_info.add_name("root of the allocation");
            nodes.insert(
                root_idx,
                Node {
                    tag: root_tag,
                    parent: None,
                    children: SmallVec::default(),
                    default_initial_perm: root_default_perm,
                    // The root may never be skipped, all accesses will be local.
                    default_initial_idempotent_foreign_access: IdempotentForeignAccess::None,
                    is_exposed: false,
                    debug_info,
                },
            );
            nodes
        };
        let locations = {
            let mut perms = UniValMap::default();
            // We manually set it to `Unique` on all in-bounds positions.
            // We also ensure that it is accessed, so that no `Unique` but
            // not yet accessed nodes exist. Essentially, we pretend there
            // was a write that initialized these to `Unique`.
            perms.insert(
                root_idx,
                LocationState::new_accessed(
                    Permission::new_unique(),
                    IdempotentForeignAccess::None,
                ),
            );
            let exposed_cache = ExposedCache::default();
            DedupRangeMap::new(size, LocationTree { perms, exposed_cache })
        };
        Self { roots: SmallVec::from_slice(&[root_idx]), nodes, locations, tag_mapping }
    }
}

impl<'tcx> Tree {
    /// Insert a new tag in the tree.
    ///
    /// `inside_perm` defines the initial permissions for a block of memory starting at
    /// `base_offset`. These may nor may not be already marked as "accessed".
    /// `outside_perm` defines the initial permission for the rest of the allocation.
    /// These are definitely not "accessed".
    pub(super) fn new_child(
        &mut self,
        base_offset: Size,
        parent_prov: ProvenanceExtra,
        new_tag: BorTag,
        inside_perms: DedupRangeMap<LocationState>,
        outside_perm: Permission,
        protected: bool,
        span: Span,
    ) -> InterpResult<'tcx> {
        let idx = self.tag_mapping.insert(new_tag);
        let parent_idx = match parent_prov {
            ProvenanceExtra::Concrete(parent_tag) =>
                Some(self.tag_mapping.get(&parent_tag).unwrap()),
            ProvenanceExtra::Wildcard => None,
        };
        assert!(outside_perm.is_initial());
        assert!(!outside_perm.is_unique());

        let default_strongest_idempotent =
            outside_perm.strongest_idempotent_foreign_access(protected);
        // Create the node
        self.nodes.insert(
            idx,
            Node {
                tag: new_tag,
                parent: parent_idx,
                children: SmallVec::default(),
                default_initial_perm: outside_perm,
                default_initial_idempotent_foreign_access: default_strongest_idempotent,
                is_exposed: false,
                debug_info: NodeDebugInfo::new(new_tag, outside_perm, span),
            },
        );
        if let Some(parent_idx) = parent_idx {
            let parent_node = self.nodes.get_mut(parent_idx).unwrap();
            // Register new_tag as a child of parent_tag
            parent_node.children.push(idx);
        } else {
            // If the parent had wildcard provenance, then register the idx
            // as a new wildcard root.
            // This preserves the orderedness of `roots` because a newly created
            // tag is greater than all previous tags.
            self.roots.push(idx);
        }

        // We need to know the weakest SIFA for `update_idempotent_foreign_access_after_retag`.
        let mut min_sifa = default_strongest_idempotent;
        for (Range { start, end }, &perm) in
            inside_perms.iter(Size::from_bytes(0), inside_perms.size())
        {
            assert!(perm.permission.is_initial());
            assert_eq!(
                perm.idempotent_foreign_access,
                perm.permission.strongest_idempotent_foreign_access(protected)
            );

            min_sifa = cmp::min(min_sifa, perm.idempotent_foreign_access);
            for (_range, loc) in self
                .locations
                .iter_mut(Size::from_bytes(start) + base_offset, Size::from_bytes(end - start))
            {
                loc.perms.insert(idx, perm);
            }
        }

        // We don't have to update `exposed_cache` as the new node is not exposed and
        // has no children so the default counts of 0 are correct.

        // If the parent is a wildcard pointer, then it doesn't track SIFA and doesn't need to be updated.
        if let Some(parent_idx) = parent_idx {
            // Inserting the new perms might have broken the SIFA invariant (see
            // `foreign_access_skipping.rs`) if the SIFA we inserted is weaker than that of some parent.
            // We now weaken the recorded SIFA for our parents, until the invariant is restored. We
            // could weaken them all to `None`, but it is more efficient to compute the SIFA for the new
            // permission statically, and use that. For this we need the *minimum* SIFA (`None` needs
            // more fixup than `Write`).
            self.update_idempotent_foreign_access_after_retag(parent_idx, min_sifa);
        }

        interp_ok(())
    }

    /// Restores the SIFA "children are stronger"/"parents are weaker" invariant after a retag:
    /// reduce the SIFA of `current` and its parents to be no stronger than `strongest_allowed`.
    /// See `foreign_access_skipping.rs` and [`Tree::new_child`].
    fn update_idempotent_foreign_access_after_retag(
        &mut self,
        mut current: UniIndex,
        strongest_allowed: IdempotentForeignAccess,
    ) {
        if strongest_allowed == IdempotentForeignAccess::Write {
            // Nothing is stronger than `Write`.
            return;
        }
        // We walk the tree upwards, until the invariant is restored
        loop {
            let current_node = self.nodes.get_mut(current).unwrap();
            // Call `ensure_no_stronger_than` on all SIFAs for this node: the per-location SIFA, as well
            // as the default SIFA for not-yet-initialized locations.
            // Record whether we did any change; if not, the invariant is restored and we can stop the traversal.
            let mut any_change = false;
            for (_range, loc) in self.locations.iter_mut_all() {
                // Check if this node has a state for this location (or range of locations).
                if let Some(perm) = loc.perms.get_mut(current) {
                    // Update the per-location SIFA, recording if it changed.
                    any_change |=
                        perm.idempotent_foreign_access.ensure_no_stronger_than(strongest_allowed);
                }
            }
            // Now update `default_initial_idempotent_foreign_access`, which stores the default SIFA for not-yet-initialized locations.
            any_change |= current_node
                .default_initial_idempotent_foreign_access
                .ensure_no_stronger_than(strongest_allowed);

            if any_change {
                let Some(next) = self.nodes.get(current).unwrap().parent else {
                    // We have arrived at the root.
                    break;
                };
                current = next;
                continue;
            } else {
                break;
            }
        }
    }

    /// Deallocation requires
    /// - a pointer that permits write accesses
    /// - the absence of Strong Protectors anywhere in the allocation
    pub fn dealloc(
        &mut self,
        prov: ProvenanceExtra,
        access_range: AllocRange,
        global: &GlobalState,
        alloc_id: AllocId, // diagnostics
        span: Span,        // diagnostics
    ) -> InterpResult<'tcx> {
        self.perform_access(
            prov,
            access_range,
            AccessKind::Write,
            AccessCause::Dealloc,
            global,
            alloc_id,
            span,
        )?;

        let start_idx = match prov {
            ProvenanceExtra::Concrete(tag) => Some(self.tag_mapping.get(&tag).unwrap()),
            ProvenanceExtra::Wildcard => None,
        };

        // Check if this breaks any strong protector.
        // (Weak protectors are already handled by `perform_access`.)
        for (loc_range, loc) in self.locations.iter_mut(access_range.start, access_range.size) {
            let diagnostics = DiagnosticInfo {
                alloc_id,
                span,
                transition_range: loc_range,
                access_range: Some(access_range),
                access_cause: AccessCause::Dealloc,
            };
            // Checks the tree containing `idx` for strong protector violations.
            // It does this in traversal order.
            let mut check_tree = |idx| {
                TreeVisitor { nodes: &mut self.nodes, data: loc }
                    .traverse_this_parents_children_other(
                        idx,
                        // Visit all children, skipping none.
                        |_| ContinueTraversal::Recurse,
                        |args: NodeAppArgs<'_, _>| {
                            let node = args.nodes.get(args.idx).unwrap();

                            let perm = args
                                .data
                                .perms
                                .get(args.idx)
                                .copied()
                                .unwrap_or_else(|| node.default_location_state());
                            if global.borrow().protected_tags.get(&node.tag)
                                == Some(&ProtectorKind::StrongProtector)
                                // Don't check for protector if it is a Cell (see `unsafe_cell_deallocate` in `interior_mutability.rs`).
                                // Related to https://github.com/rust-lang/rust/issues/55005.
                                && !perm.permission.is_cell()
                                // Only trigger UB if the accessed bit is set, i.e. if the protector
                                // is actually protecting this offset. See #4579. Note that this
                                // takes into account the access we just did above!
                                && perm.accessed
                            {
                                Err(TbError {
                                    error_kind: TransitionError::ProtectedDealloc,
                                    access_info: &diagnostics,
                                    conflicting_node_info: &node.debug_info,
                                    accessed_node_info: start_idx
                                        .map(|idx| &args.nodes.get(idx).unwrap().debug_info),
                                }
                                .build())
                            } else {
                                Ok(())
                            }
                        },
                    )
            };
            // If we have a start index we first check its subtree in traversal order.
            // This results in us showing the error of the closest node instead of an
            // arbitrary one.
            let accessed_root = start_idx.map(&mut check_tree).transpose()?;
            // Afterwards we check all other trees.
            // We iterate over the list in reverse order to ensure that we do not visit
            // a parent before its child.
            for &root in self.roots.iter().rev() {
                if Some(root) == accessed_root {
                    continue;
                }
                check_tree(root)?;
            }
        }
        interp_ok(())
    }

    /// Map the per-node and per-location `LocationState::perform_access`
    /// to each location of the first component of `access_range_and_kind`,
    /// on every tag of the allocation.
    ///
    /// `LocationState::perform_access` will take care of raising transition
    /// errors and updating the `accessed` status of each location,
    /// this traversal adds to that:
    /// - inserting into the map locations that do not exist yet,
    /// - trimming the traversal,
    /// - recording the history.
    pub fn perform_access(
        &mut self,
        prov: ProvenanceExtra,
        access_range: AllocRange,
        access_kind: AccessKind,
        access_cause: AccessCause, // diagnostics
        global: &GlobalState,
        alloc_id: AllocId, // diagnostics
        span: Span,        // diagnostics
    ) -> InterpResult<'tcx> {
        #[cfg(feature = "expensive-consistency-checks")]
        if self.roots.len() > 1 || matches!(prov, ProvenanceExtra::Wildcard) {
            self.verify_wildcard_consistency(global);
        }

        let source_idx = match prov {
            ProvenanceExtra::Concrete(tag) => Some(self.tag_mapping.get(&tag).unwrap()),
            ProvenanceExtra::Wildcard => None,
        };
        // We iterate over affected locations and traverse the tree for each of them.
        for (loc_range, loc) in self.locations.iter_mut(access_range.start, access_range.size) {
            let diagnostics = DiagnosticInfo {
                access_cause,
                access_range: Some(access_range),
                alloc_id,
                span,
                transition_range: loc_range,
            };
            loc.perform_access(
                self.roots.iter().copied(),
                &mut self.nodes,
                source_idx,
                access_kind,
                global,
                ChildrenVisitMode::VisitChildrenOfAccessed,
                &diagnostics,
                /* min_exposed_child */ None, // only matters for protector end access,
            )?;
        }
        interp_ok(())
    }
    /// This is the special access that is applied on protector release:
    /// - the access will be applied only to accessed locations of the allocation,
    /// - it will not be visible to children,
    /// - it will be recorded as a `FnExit` diagnostic access
    /// - and it will be a read except if the location is `Unique`, i.e. has been written to,
    ///   in which case it will be a write.
    /// - otherwise identical to `Tree::perform_access`
    pub fn perform_protector_end_access(
        &mut self,
        tag: BorTag,
        global: &GlobalState,
        alloc_id: AllocId, // diagnostics
        span: Span,        // diagnostics
    ) -> InterpResult<'tcx> {
        #[cfg(feature = "expensive-consistency-checks")]
        if self.roots.len() > 1 {
            self.verify_wildcard_consistency(global);
        }

        let source_idx = self.tag_mapping.get(&tag).unwrap();

        let min_exposed_child = if self.roots.len() > 1 {
            LocationTree::get_min_exposed_child(source_idx, &self.nodes)
        } else {
            // There's no point in computing this when there is just one tree.
            None
        };

        // This is a special access through the entire allocation.
        // It actually only affects `accessed` locations, so we need
        // to filter on those before initiating the traversal.
        //
        // In addition this implicit access should not be visible to children,
        // thus the use of `traverse_nonchildren`.
        // See the test case `returned_mut_is_usable` from
        // `tests/pass/tree_borrows/tree-borrows.rs` for an example of
        // why this is important.
        for (loc_range, loc) in self.locations.iter_mut_all() {
            // Only visit accessed permissions
            if let Some(p) = loc.perms.get(source_idx)
                && let Some(access_kind) = p.permission.associated_access()
                && p.accessed
            {
                let diagnostics = DiagnosticInfo {
                    access_cause: AccessCause::FnExit(access_kind),
                    access_range: None,
                    alloc_id,
                    span,
                    transition_range: loc_range,
                };
                loc.perform_access(
                    self.roots.iter().copied(),
                    &mut self.nodes,
                    Some(source_idx),
                    access_kind,
                    global,
                    ChildrenVisitMode::SkipChildrenOfAccessed,
                    &diagnostics,
                    min_exposed_child,
                )?;
            }
        }
        interp_ok(())
    }
}

/// Integration with the BorTag garbage collector
impl Tree {
    pub fn remove_unreachable_tags(&mut self, live_tags: &FxHashSet<BorTag>) {
        for i in 0..(self.roots.len()) {
            self.remove_useless_children(self.roots[i], live_tags);
        }
        // Right after the GC runs is a good moment to check if we can
        // merge some adjacent ranges that were made equal by the removal of some
        // tags (this does not necessarily mean that they have identical internal representations,
        // see the `PartialEq` impl for `UniValMap`)
        self.locations.merge_adjacent_thorough();
    }

    /// Checks if a node is useless and should be GC'ed.
    /// A node is useless if it has no children and also the tag is no longer live.
    fn is_useless(&self, idx: UniIndex, live: &FxHashSet<BorTag>) -> bool {
        let node = self.nodes.get(idx).unwrap();
        node.children.is_empty() && !live.contains(&node.tag)
    }

    /// Checks whether a node can be replaced by its only child.
    /// If so, returns the index of said only child.
    /// If not, returns none.
    fn can_be_replaced_by_single_child(
        &self,
        idx: UniIndex,
        live: &FxHashSet<BorTag>,
    ) -> Option<UniIndex> {
        let node = self.nodes.get(idx).unwrap();

        let [child_idx] = node.children[..] else { return None };

        // We never want to replace the root node, as it is also kept in `root_ptr_tags`.
        if live.contains(&node.tag) || node.parent.is_none() {
            return None;
        }
        // Since protected nodes are never GC'd (see `borrow_tracker::FrameExtra::visit_provenance`),
        // we know that `node` is not protected because otherwise `live` would
        // have contained `node.tag`.
        let child = self.nodes.get(child_idx).unwrap();
        // Check that for that one child, `can_be_replaced_by_child` holds for the permission
        // on all locations.
        for (_range, loc) in self.locations.iter_all() {
            let parent_perm = loc
                .perms
                .get(idx)
                .map(|x| x.permission)
                .unwrap_or_else(|| node.default_initial_perm);
            let child_perm = loc
                .perms
                .get(child_idx)
                .map(|x| x.permission)
                .unwrap_or_else(|| child.default_initial_perm);
            if !parent_perm.can_be_replaced_by_child(child_perm) {
                return None;
            }
        }

        Some(child_idx)
    }

    /// Properly removes a node.
    /// The node to be removed should not otherwise be usable. It also
    /// should have no children, but this is not checked, so that nodes
    /// whose children were rotated somewhere else can be deleted without
    /// having to first modify them to clear that array.
    fn remove_useless_node(&mut self, this: UniIndex) {
        // Due to the API of UniMap we must make sure to call
        // `UniValMap::remove` for the key of this node on *all* maps that used it
        // (which are `self.nodes` and every range of `self.rperms`)
        // before we can safely apply `UniKeyMap::remove` to truly remove
        // this tag from the `tag_mapping`.
        let node = self.nodes.remove(this).unwrap();
        for (_range, loc) in self.locations.iter_mut_all() {
            loc.perms.remove(this);
            loc.exposed_cache.remove(this);
        }
        self.tag_mapping.remove(&node.tag);
    }

    /// Traverses the entire tree looking for useless tags.
    /// Removes from the tree all useless child nodes of root.
    /// It will not delete the root itself.
    ///
    /// NOTE: This leaves in the middle of the tree tags that are unreachable but have
    /// reachable children. There is a potential for compacting the tree by reassigning
    /// children of dead tags to the nearest live parent, but it must be done with care
    /// not to remove UB.
    ///
    /// Example: Consider the tree `root - parent - child`, with `parent: Frozen` and
    /// `child: Reserved`. This tree can exist. If we blindly delete `parent` and reassign
    /// `child` to be a direct child of `root` then Writes to `child` are now permitted
    /// whereas they were not when `parent` was still there.
    fn remove_useless_children(&mut self, root: UniIndex, live: &FxHashSet<BorTag>) {
        // To avoid stack overflows, we roll our own stack.
        // Each element in the stack consists of the current tag, and the number of the
        // next child to be processed.

        // The other functions are written using the `TreeVisitorStack`, but that does not work here
        // since we need to 1) do a post-traversal and 2) remove nodes from the tree.
        // Since we do a post-traversal (by deleting nodes only after handling all children),
        // we also need to be a bit smarter than "pop node, push all children."
        let mut stack = vec![(root, 0)];
        while let Some((tag, nth_child)) = stack.last_mut() {
            let node = self.nodes.get(*tag).unwrap();
            if *nth_child < node.children.len() {
                // Visit the child by pushing it to the stack.
                // Also increase `nth_child` so that when we come back to the `tag` node, we
                // look at the next child.
                let next_child = node.children[*nth_child];
                *nth_child += 1;
                stack.push((next_child, 0));
                continue;
            } else {
                // We have processed all children of `node`, so now it is time to process `node` itself.
                // First, get the current children of `node`. To appease the borrow checker,
                // we have to temporarily move the list out of the node, and then put the
                // list of remaining children back in.
                let mut children_of_node =
                    mem::take(&mut self.nodes.get_mut(*tag).unwrap().children);
                // Remove all useless children.
                children_of_node.retain_mut(|idx| {
                    if self.is_useless(*idx, live) {
                        // Delete `idx` node everywhere else.
                        self.remove_useless_node(*idx);
                        // And delete it from children_of_node.
                        false
                    } else {
                        if let Some(nextchild) = self.can_be_replaced_by_single_child(*idx, live) {
                            // `nextchild` is our grandchild, and will become our direct child.
                            // Delete the in-between node, `idx`.
                            self.remove_useless_node(*idx);
                            // Set the new child's parent.
                            self.nodes.get_mut(nextchild).unwrap().parent = Some(*tag);
                            // Save the new child in children_of_node.
                            *idx = nextchild;
                        }
                        // retain it
                        true
                    }
                });
                // Put back the now-filtered vector.
                self.nodes.get_mut(*tag).unwrap().children = children_of_node;

                // We are done, the parent can continue.
                stack.pop();
                continue;
            }
        }
    }
}

impl<'tcx> LocationTree {
    /// Returns the smallest exposed tag, if any, that is a transitive child of `root`.
    fn get_min_exposed_child(root: UniIndex, nodes: &UniValMap<Node>) -> Option<BorTag> {
        // We cannot use the wildcard datastructure to improve this lookup. This is because
        // the datastructure only tracks enabled nodes and we need to also consider disabled ones.
        let mut stack = vec![root];
        let mut min_tag = None;
        while let Some(idx) = stack.pop() {
            let node = nodes.get(idx).unwrap();
            if min_tag.is_some_and(|min| min < node.tag) {
                // The minimum we found before is bigger than this tag, and therefore
                // also bigger than all its children, so we can skip this subtree.
                continue;
            }
            stack.extend_from_slice(node.children.as_slice());
            if node.is_exposed {
                min_tag = match min_tag {
                    Some(prev) if prev < node.tag => Some(prev),
                    _ => Some(node.tag),
                };
            }
        }
        min_tag
    }

    /// Performs an access on this location.
    /// * `access_source`: The index, if any, where the access came from.
    /// * `visit_children`: Whether to skip updating the children of `access_source`.
    /// * `min_exposed_child`: The tag of the smallest exposed (transitive) child of the accessed node.
    ///   This is only used with `visit_children == SkipChildrenOfAccessed`, where we need to skip children
    ///   of the accessed node.
    fn perform_access(
        &mut self,
        roots: impl Iterator<Item = UniIndex>,
        nodes: &mut UniValMap<Node>,
        access_source: Option<UniIndex>,
        access_kind: AccessKind,
        global: &GlobalState,
        visit_children: ChildrenVisitMode,
        diagnostics: &DiagnosticInfo,
        min_exposed_child: Option<BorTag>,
    ) -> InterpResult<'tcx> {
        let accessed_root = if let Some(idx) = access_source {
            Some(self.perform_normal_access(
                idx,
                nodes,
                access_kind,
                global,
                visit_children,
                diagnostics,
            )?)
        } else {
            // `SkipChildrenOfAccessed` only gets set on protector release, which only
            // occurs on a known node.
            assert!(matches!(visit_children, ChildrenVisitMode::VisitChildrenOfAccessed));
            None
        };

        let accessed_root_tag = accessed_root.map(|idx| nodes.get(idx).unwrap().tag);
        for (i, root) in roots.enumerate() {
            let tag = nodes.get(root).unwrap().tag;
            // On a protector release access we have to skip the children of the accessed tag.
            // However, if the tag has exposed children then some of the wildcard subtrees could
            // also be children of the accessed node and would also need to be skipped. We can
            // narrow down which wildcard trees might be children by comparing their root tag to the
            // minimum exposed child of the accessed node. As the parent tag is always smaller
            // than the child tag this means we only need to skip subtrees with a root tag larger
            // than `min_exposed_child`. Once we find such a root, we can leave the loop because roots
            // are sorted by tag.
            if matches!(visit_children, ChildrenVisitMode::SkipChildrenOfAccessed)
                && let Some(min_exposed_child) = min_exposed_child
                && tag > min_exposed_child
            {
                break;
            }
            // We don't perform a wildcard access on the tree we already performed a
            // normal access on.
            if Some(root) == accessed_root {
                continue;
            }
            // The choice of `max_local_tag` requires some thought.
            // This can only be a local access for nodes that are a parent of the accessed node
            // and are therefore smaller, so the accessed node itself is a valid choice for `max_local_tag`.
            // However, using `accessed_root` is better since that will be smaller. It is still a valid choice
            // because for nodes *in other trees*, if they are a parent of the accessed node then they
            // are a parent of `accessed_root`.
            //
            // As a consequence of this, since the root of the main tree is the smallest tag in the entire
            // allocation, if the access occurred in the main tree then other subtrees will only see foreign accesses.
            self.perform_wildcard_access(
                root,
                access_source,
                /*max_local_tag*/ accessed_root_tag,
                nodes,
                access_kind,
                global,
                diagnostics,
                /*is_wildcard_tree*/ i != 0,
            )?;
        }
        interp_ok(())
    }

    /// Performs a normal access on the tree containing `access_source`.
    ///
    /// Returns the root index of this tree.
    /// * `access_source`: The index of the tag being accessed.
    /// * `visit_children`: Whether to skip the children of `access_source`
    ///   during the access. Used for protector end access.
    fn perform_normal_access(
        &mut self,
        access_source: UniIndex,
        nodes: &mut UniValMap<Node>,
        access_kind: AccessKind,
        global: &GlobalState,
        visit_children: ChildrenVisitMode,
        diagnostics: &DiagnosticInfo,
    ) -> InterpResult<'tcx, UniIndex> {
        // Performs the per-node work:
        // - insert the permission if it does not exist
        // - perform the access
        // - record the transition
        // to which some optimizations are added:
        // - skip the traversal of the children in some cases
        // - do not record noop transitions
        //
        // `loc_range` is only for diagnostics (it is the range of
        // the `RangeMap` on which we are currently working).
        let node_skipper = |args: &NodeAppArgs<'_, LocationTree>| -> ContinueTraversal {
            let node = args.nodes.get(args.idx).unwrap();
            let perm = args.data.perms.get(args.idx);

            let old_state = perm.copied().unwrap_or_else(|| node.default_location_state());
            old_state.skip_if_known_noop(access_kind, args.rel_pos)
        };
        let node_app = |args: NodeAppArgs<'_, LocationTree>| {
            let node = args.nodes.get_mut(args.idx).unwrap();
            let mut perm = args.data.perms.entry(args.idx);

            let state = perm.or_insert(node.default_location_state());

            let protected = global.borrow().protected_tags.contains_key(&node.tag);
            state
                .perform_transition(
                    args.idx,
                    args.nodes,
                    &mut args.data.exposed_cache,
                    access_kind,
                    args.rel_pos,
                    protected,
                    diagnostics,
                )
                .map_err(|error_kind| {
                    TbError {
                        error_kind,
                        access_info: diagnostics,
                        conflicting_node_info: &args.nodes.get(args.idx).unwrap().debug_info,
                        accessed_node_info: Some(
                            &args.nodes.get(access_source).unwrap().debug_info,
                        ),
                    }
                    .build()
                })
        };

        let visitor = TreeVisitor { nodes, data: self };
        match visit_children {
            ChildrenVisitMode::VisitChildrenOfAccessed =>
                visitor.traverse_this_parents_children_other(access_source, node_skipper, node_app),
            ChildrenVisitMode::SkipChildrenOfAccessed =>
                visitor.traverse_nonchildren(access_source, node_skipper, node_app),
        }
        .into()
    }

    /// Performs a wildcard access on the tree with root `root`. Takes the `access_relatedness`
    /// for each node from the `WildcardState` datastructure.
    /// * `root`: Root of the tree being accessed.
    /// * `access_source`: the index of the accessed tag, if any.
    ///   This is only used for printing the correct tag on errors.
    /// * `max_local_tag`: The access can only be local for nodes whose tag is
    ///   at most `max_local_tag`.
    fn perform_wildcard_access(
        &mut self,
        root: UniIndex,
        access_source: Option<UniIndex>,
        max_local_tag: Option<BorTag>,
        nodes: &mut UniValMap<Node>,
        access_kind: AccessKind,
        global: &GlobalState,
        diagnostics: &DiagnosticInfo,
        is_wildcard_tree: bool,
    ) -> InterpResult<'tcx> {
        let get_relatedness = |idx: UniIndex, node: &Node, loc: &LocationTree| {
            // If the tag is larger than `max_local_tag` then the access can only be foreign.
            let only_foreign = max_local_tag.is_some_and(|max_local_tag| max_local_tag < node.tag);
            loc.exposed_cache.access_relatedness(
                root,
                idx,
                access_kind,
                is_wildcard_tree,
                only_foreign,
            )
        };

        // Whether there is an exposed node in this tree that allows this access.
        let mut has_valid_exposed = false;

        // This does a traversal across the tree updating children before their parents. The
        // difference to `perform_normal_access` is that we take the access relatedness from
        // the wildcard tracking state of the node instead of from the visitor itself.
        //
        // Unlike for a normal access, the iteration order is important for improving the
        // accuracy of wildcard accesses if `max_local_tag` is `Some`: processing the effects of this
        // access further down the tree can cause exposed nodes to lose permissions, thus updating
        // the wildcard data structure, which will be taken into account when processing the parent
        // nodes. Also see the test `cross_tree_update_older_invalid_exposed2.rs`
        // (Doing accesses in the opposite order cannot help with precision but the reasons are complicated;
        // see <https://github.com/rust-lang/miri/pull/4707#discussion_r2581661123>.)
        //
        // Note, however, that this is an approximation: there can be situations where a node is
        // marked as having an exposed foreign node, but actually that foreign node cannot be
        // the source of the access due to `max_local_tag`. The wildcard tracking cannot know
        // about `max_local_tag` so we will incorrectly assume that this might be a foreign access.
        TreeVisitor { data: self, nodes }.traverse_children_this(
            root,
            |args| -> ContinueTraversal {
                let node = args.nodes.get(args.idx).unwrap();
                let perm = args.data.perms.get(args.idx);

                let old_state = perm.copied().unwrap_or_else(|| node.default_location_state());
                // If we know where, relative to this node, the wildcard access occurs,
                // then check if we can skip the entire subtree.
                if let Some(relatedness) = get_relatedness(args.idx, node, args.data)
                    && let Some(relatedness) = relatedness.to_relatedness()
                {
                    // We can use the usual SIFA machinery to skip nodes.
                    old_state.skip_if_known_noop(access_kind, relatedness)
                } else {
                    ContinueTraversal::Recurse
                }
            },
            |args| {
                let node = args.nodes.get_mut(args.idx).unwrap();

                let protected = global.borrow().protected_tags.contains_key(&node.tag);

                let Some(wildcard_relatedness) = get_relatedness(args.idx, node, args.data) else {
                    // There doesn't exist a valid exposed reference for this access to
                    // happen through.
                    // This can only happen if `root` is the main root: We set
                    // `max_foreign_access==Write` on all wildcard roots, so at least a foreign access
                    // is always possible on all nodes in a wildcard subtree.
                    return Err(no_valid_exposed_references_error(diagnostics));
                };

                let mut entry = args.data.perms.entry(args.idx);
                let perm = entry.or_insert(node.default_location_state());

                // We only count exposed nodes through which an access could happen.
                if node.is_exposed
                    && perm.permission.strongest_allowed_local_access(protected).allows(access_kind)
                    && max_local_tag.is_none_or(|max_local_tag| max_local_tag >= node.tag)
                {
                    has_valid_exposed = true;
                }

                let Some(relatedness) = wildcard_relatedness.to_relatedness() else {
                    // If the access type is Either, then we do not apply any transition
                    // to this node, but we still update each of its children.
                    // This is an imprecision! In the future, maybe we can still do some sort
                    // of best-effort update here.
                    return Ok(());
                };

                // We know the exact relatedness, so we can actually do precise checks.
                perm.perform_transition(
                    args.idx,
                    args.nodes,
                    &mut args.data.exposed_cache,
                    access_kind,
                    relatedness,
                    protected,
                    diagnostics,
                )
                .map_err(|trans| {
                    let node = args.nodes.get(args.idx).unwrap();
                    TbError {
                        error_kind: trans,
                        access_info: diagnostics,
                        conflicting_node_info: &node.debug_info,
                        accessed_node_info: access_source
                            .map(|idx| &args.nodes.get(idx).unwrap().debug_info),
                    }
                    .build()
                })
            },
        )?;
        // If there is no exposed node in this tree that allows this access, then the access *must*
        // be foreign to the entire subtree. Foreign accesses are only possible on wildcard subtrees
        // as there are no ancestors to the main root. So if we do not find a valid exposed node in
        // the main tree then this access is UB.
        if !has_valid_exposed && !is_wildcard_tree {
            return Err(no_valid_exposed_references_error(diagnostics)).into();
        }
        interp_ok(())
    }
}

impl Node {
    pub fn default_location_state(&self) -> LocationState {
        LocationState::new_non_accessed(
            self.default_initial_perm,
            self.default_initial_idempotent_foreign_access,
        )
    }
}

impl VisitProvenance for Tree {
    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
        // To ensure that the roots never get removed, we visit them.
        // FIXME: it should be possible to GC wildcard tree roots.
        for id in self.roots.iter().copied() {
            visit(None, Some(self.nodes.get(id).unwrap().tag));
        }
        // We also need to keep around any exposed tags through which
        // an access could still happen.
        for (_id, node) in self.nodes.iter() {
            if node.is_exposed {
                visit(None, Some(node.tag))
            }
        }
    }
}

/// Relative position of the access
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum AccessRelatedness {
    /// The access happened either through the node itself or one of
    /// its transitive children.
    LocalAccess,
    /// The access happened through this nodes ancestor or through
    /// a sibling/cousin/uncle/etc.
    ForeignAccess,
}

impl AccessRelatedness {
    /// Check that access is either Ancestor or Distant, i.e. not
    /// a transitive child (initial pointer included).
    pub fn is_foreign(self) -> bool {
        matches!(self, AccessRelatedness::ForeignAccess)
    }
}