miri/borrow_tracker/tree_borrows/
tree.rs

1//! In this file we handle the "Tree" part of Tree Borrows, i.e. all tree
2//! traversal functions, optimizations to trim branches, and keeping track of
3//! the relative position of the access to each node being updated. This of course
4//! also includes the definition of the tree structure.
5//!
6//! Functions here manipulate permissions but are oblivious to them: as
7//! the internals of `Permission` are private, the update process is a black
8//! box. All we need to know here are
9//! - the fact that updates depend only on the old state, the status of protectors,
10//!   and the relative position of the access;
11//! - idempotency properties asserted in `perms.rs` (for optimizations)
12
13use std::ops::Range;
14use std::{fmt, mem};
15
16use rustc_abi::Size;
17use rustc_data_structures::fx::FxHashSet;
18use rustc_span::Span;
19use smallvec::SmallVec;
20
21use crate::borrow_tracker::tree_borrows::Permission;
22use crate::borrow_tracker::tree_borrows::diagnostics::{
23    self, NodeDebugInfo, TbError, TransitionError,
24};
25use crate::borrow_tracker::tree_borrows::foreign_access_skipping::IdempotentForeignAccess;
26use crate::borrow_tracker::tree_borrows::perms::PermTransition;
27use crate::borrow_tracker::tree_borrows::unimap::{UniEntry, UniIndex, UniKeyMap, UniValMap};
28use crate::borrow_tracker::{GlobalState, ProtectorKind};
29use crate::*;
30
31mod tests;
32
33/// Data for a single *location*.
34#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
35pub(super) struct LocationState {
36    /// A location is "accessed" when it is child-accessed for the first time (and the initial
37    /// retag initializes the location for the range covered by the type), and it then stays
38    /// accessed forever.
39    /// For accessed locations, "permission" is the current permission. However, for
40    /// non-accessed locations, we still need to track the "future initial permission": this will
41    /// start out to be `default_initial_perm`, but foreign accesses need to be taken into account.
42    /// Crucially however, while transitions to `Disabled` would usually be UB if this location is
43    /// protected, that is *not* the case for non-accessed locations. Instead we just have a latent
44    /// "future initial permission" of `Disabled`, causing UB only if an access is ever actually
45    /// performed.
46    /// Note that the tree root is also always accessed, as if the allocation was a write access.
47    accessed: bool,
48    /// This pointer's current permission / future initial permission.
49    permission: Permission,
50    /// See `foreign_access_skipping.rs`.
51    /// Stores an idempotent foreign access for this location and its children.
52    /// For correctness, this must not be too strong, and the recorded idempotent foreign access
53    /// of all children must be at least as strong as this. For performance, it should be as strong as possible.
54    idempotent_foreign_access: IdempotentForeignAccess,
55}
56
57impl LocationState {
58    /// Constructs a new initial state. It has neither been accessed, nor been subjected
59    /// to any foreign access yet.
60    /// The permission is not allowed to be `Active`.
61    /// `sifa` is the (strongest) idempotent foreign access, see `foreign_access_skipping.rs`
62    pub fn new_non_accessed(permission: Permission, sifa: IdempotentForeignAccess) -> Self {
63        assert!(permission.is_initial() || permission.is_disabled());
64        Self { permission, accessed: false, idempotent_foreign_access: sifa }
65    }
66
67    /// Constructs a new initial state. It has not yet been subjected
68    /// to any foreign access. However, it is already marked as having been accessed.
69    /// `sifa` is the (strongest) idempotent foreign access, see `foreign_access_skipping.rs`
70    pub fn new_accessed(permission: Permission, sifa: IdempotentForeignAccess) -> Self {
71        Self { permission, accessed: true, idempotent_foreign_access: sifa }
72    }
73
74    /// Check if the location has been accessed, i.e. if it has
75    /// ever been accessed through a child pointer.
76    pub fn is_accessed(&self) -> bool {
77        self.accessed
78    }
79
80    /// Check if the state can exist as the initial permission of a pointer.
81    ///
82    /// Do not confuse with `is_accessed`, the two are almost orthogonal
83    /// as apart from `Active` which is not initial and must be accessed,
84    /// any other permission can have an arbitrary combination of being
85    /// initial/accessed.
86    /// FIXME: when the corresponding `assert` in `tree_borrows/mod.rs` finally
87    /// passes and can be uncommented, remove this `#[allow(dead_code)]`.
88    #[cfg_attr(not(test), allow(dead_code))]
89    pub fn is_initial(&self) -> bool {
90        self.permission.is_initial()
91    }
92
93    pub fn permission(&self) -> Permission {
94        self.permission
95    }
96
97    /// Apply the effect of an access to one location, including
98    /// - applying `Permission::perform_access` to the inner `Permission`,
99    /// - emitting protector UB if the location is accessed,
100    /// - updating the accessed status (child accesses produce accessed locations).
101    fn perform_access(
102        &mut self,
103        access_kind: AccessKind,
104        rel_pos: AccessRelatedness,
105        protected: bool,
106    ) -> Result<PermTransition, TransitionError> {
107        let old_perm = self.permission;
108        let transition = Permission::perform_access(access_kind, rel_pos, old_perm, protected)
109            .ok_or(TransitionError::ChildAccessForbidden(old_perm))?;
110        self.accessed |= !rel_pos.is_foreign();
111        self.permission = transition.applied(old_perm).unwrap();
112        // Why do only accessed locations cause protector errors?
113        // Consider two mutable references `x`, `y` into disjoint parts of
114        // the same allocation. A priori, these may actually both be used to
115        // access the entire allocation, as long as only reads occur. However,
116        // a write to `y` needs to somehow record that `x` can no longer be used
117        // on that location at all. For these non-accessed locations (i.e., locations
118        // that haven't been accessed with `x` yet), we track the "future initial state":
119        // it defaults to whatever the initial state of the tag is,
120        // but the access to `y` moves that "future initial state" of `x` to `Disabled`.
121        // However, usually a `Reserved -> Disabled` transition would be UB due to the protector!
122        // So clearly protectors shouldn't fire for such "future initial state" transitions.
123        //
124        // See the test `two_mut_protected_same_alloc` in `tests/pass/tree_borrows/tree-borrows.rs`
125        // for an example of safe code that would be UB if we forgot to check `self.accessed`.
126        if protected && self.accessed && transition.produces_disabled() {
127            return Err(TransitionError::ProtectedDisabled(old_perm));
128        }
129        Ok(transition)
130    }
131
132    /// Like `perform_access`, but ignores the concrete error cause and also uses state-passing
133    /// rather than a mutable reference. As such, it returns `Some(x)` if the transition succeeded,
134    /// or `None` if there was an error.
135    #[cfg(test)]
136    fn perform_access_no_fluff(
137        mut self,
138        access_kind: AccessKind,
139        rel_pos: AccessRelatedness,
140        protected: bool,
141    ) -> Option<Self> {
142        match self.perform_access(access_kind, rel_pos, protected) {
143            Ok(_) => Some(self),
144            Err(_) => None,
145        }
146    }
147
148    /// Tree traversal optimizations. See `foreign_access_skipping.rs`.
149    /// This checks if such a foreign access can be skipped.
150    fn skip_if_known_noop(
151        &self,
152        access_kind: AccessKind,
153        rel_pos: AccessRelatedness,
154    ) -> ContinueTraversal {
155        if rel_pos.is_foreign() {
156            let happening_now = IdempotentForeignAccess::from_foreign(access_kind);
157            let mut new_access_noop =
158                self.idempotent_foreign_access.can_skip_foreign_access(happening_now);
159            if self.permission.is_disabled() {
160                // A foreign access to a `Disabled` tag will have almost no observable effect.
161                // It's a theorem that `Disabled` node have no protected accessed children,
162                // and so this foreign access will never trigger any protector.
163                // (Intuition: You're either protected accessed, and thus can't become Disabled
164                // or you're already Disabled protected, but not accessed, and then can't
165                // become accessed since that requires a child access, which Disabled blocks.)
166                // Further, the children will never be able to read or write again, since they
167                // have a `Disabled` parent. So this only affects diagnostics, such that the
168                // blocking write will still be identified directly, just at a different tag.
169                new_access_noop = true;
170            }
171            if self.permission.is_frozen() && access_kind == AccessKind::Read {
172                // A foreign read to a `Frozen` tag will have almost no observable effect.
173                // It's a theorem that `Frozen` nodes have no active children, so all children
174                // already survive foreign reads. Foreign reads in general have almost no
175                // effect, the only further thing they could do is make protected `Reserved`
176                // nodes become conflicted, i.e. make them reject child writes for the further
177                // duration of their protector. But such a child write is already rejected
178                // because this node is frozen. So this only affects diagnostics, but the
179                // blocking read will still be identified directly, just at a different tag.
180                new_access_noop = true;
181            }
182            if new_access_noop {
183                // Abort traversal if the new access is indeed guaranteed
184                // to be noop.
185                // No need to update `self.idempotent_foreign_access`,
186                // the type of the current streak among nonempty read-only
187                // or nonempty with at least one write has not changed.
188                ContinueTraversal::SkipSelfAndChildren
189            } else {
190                // Otherwise propagate this time, and also record the
191                // access that just occurred so that we can skip the propagation
192                // next time.
193                ContinueTraversal::Recurse
194            }
195        } else {
196            // A child access occurred, this breaks the streak of foreign
197            // accesses in a row and the sequence since the previous child access
198            // is now empty.
199            ContinueTraversal::Recurse
200        }
201    }
202
203    /// Records a new access, so that future access can potentially be skipped
204    /// by `skip_if_known_noop`. This must be called on child accesses, and otherwise
205    /// shoud be called on foreign accesses for increased performance. It should not be called
206    /// when `skip_if_known_noop` indicated skipping, since it then is a no-op.
207    /// See `foreign_access_skipping.rs`
208    fn record_new_access(&mut self, access_kind: AccessKind, rel_pos: AccessRelatedness) {
209        debug_assert!(matches!(
210            self.skip_if_known_noop(access_kind, rel_pos),
211            ContinueTraversal::Recurse
212        ));
213        self.idempotent_foreign_access
214            .record_new(IdempotentForeignAccess::from_acc_and_rel(access_kind, rel_pos));
215    }
216}
217
218impl fmt::Display for LocationState {
219    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
220        write!(f, "{}", self.permission)?;
221        if !self.accessed {
222            write!(f, "?")?;
223        }
224        Ok(())
225    }
226}
227
228/// Tree structure with both parents and children since we want to be
229/// able to traverse the tree efficiently in both directions.
230#[derive(Clone, Debug)]
231pub struct Tree {
232    /// Mapping from tags to keys. The key obtained can then be used in
233    /// any of the `UniValMap` relative to this allocation, i.e. both the
234    /// `nodes` and `rperms` of the same `Tree`.
235    /// The parent-child relationship in `Node` is encoded in terms of these same
236    /// keys, so traversing the entire tree needs exactly one access to
237    /// `tag_mapping`.
238    pub(super) tag_mapping: UniKeyMap<BorTag>,
239    /// All nodes of this tree.
240    pub(super) nodes: UniValMap<Node>,
241    /// Maps a tag and a location to a perm, with possible lazy
242    /// initialization.
243    ///
244    /// NOTE: not all tags registered in `nodes` are necessarily in all
245    /// ranges of `rperms`, because `rperms` is in part lazily initialized.
246    /// Just because `nodes.get(key)` is `Some(_)` does not mean you can safely
247    /// `unwrap` any `perm.get(key)`.
248    ///
249    /// We do uphold the fact that `keys(perms)` is a subset of `keys(nodes)`
250    pub(super) rperms: RangeMap<UniValMap<LocationState>>,
251    /// The index of the root node.
252    pub(super) root: UniIndex,
253}
254
255/// A node in the borrow tree. Each node is uniquely identified by a tag via
256/// the `nodes` map of `Tree`.
257#[derive(Clone, Debug)]
258pub(super) struct Node {
259    /// The tag of this node.
260    pub tag: BorTag,
261    /// All tags except the root have a parent tag.
262    pub parent: Option<UniIndex>,
263    /// If the pointer was reborrowed, it has children.
264    // FIXME: bench to compare this to FxHashSet and to other SmallVec sizes
265    pub children: SmallVec<[UniIndex; 4]>,
266    /// Either `Reserved`,  `Frozen`, or `Disabled`, it is the permission this tag will
267    /// lazily be initialized to on the first access.
268    /// It is only ever `Disabled` for a tree root, since the root is initialized to `Active` by
269    /// its own separate mechanism.
270    default_initial_perm: Permission,
271    /// The default initial (strongest) idempotent foreign access.
272    /// This participates in the invariant for `LocationState::idempotent_foreign_access`
273    /// in cases where there is no location state yet. See `foreign_access_skipping.rs`,
274    /// and `LocationState::idempotent_foreign_access` for more information
275    default_initial_idempotent_foreign_access: IdempotentForeignAccess,
276    /// Some extra information useful only for debugging purposes
277    pub debug_info: NodeDebugInfo,
278}
279
280/// Data given to the transition function
281struct NodeAppArgs<'node> {
282    /// Node on which the transition is currently being applied
283    node: &'node mut Node,
284    /// Mutable access to its permissions
285    perm: UniEntry<'node, LocationState>,
286    /// Relative position of the access
287    rel_pos: AccessRelatedness,
288}
289/// Data given to the error handler
290struct ErrHandlerArgs<'node, InErr> {
291    /// Kind of error that occurred
292    error_kind: InErr,
293    /// Tag that triggered the error (not the tag that was accessed,
294    /// rather the parent tag that had insufficient permissions or the
295    /// non-parent tag that had a protector).
296    conflicting_info: &'node NodeDebugInfo,
297    /// Information about the tag that was accessed just before the
298    /// error was triggered.
299    accessed_info: &'node NodeDebugInfo,
300}
301/// Internal contents of `Tree` with the minimum of mutable access for
302/// the purposes of the tree traversal functions: the permissions (`perms`) can be
303/// updated but not the tree structure (`tag_mapping` and `nodes`)
304struct TreeVisitor<'tree> {
305    tag_mapping: &'tree UniKeyMap<BorTag>,
306    nodes: &'tree mut UniValMap<Node>,
307    perms: &'tree mut UniValMap<LocationState>,
308}
309
310/// Whether to continue exploring the children recursively or not.
311enum ContinueTraversal {
312    Recurse,
313    SkipSelfAndChildren,
314}
315
316#[derive(Clone, Copy)]
317pub enum ChildrenVisitMode {
318    VisitChildrenOfAccessed,
319    SkipChildrenOfAccessed,
320}
321
322enum RecursionState {
323    BeforeChildren,
324    AfterChildren,
325}
326
327/// Stack of nodes left to explore in a tree traversal.
328/// See the docs of `traverse_this_parents_children_other` for details on the
329/// traversal order.
330struct TreeVisitorStack<NodeContinue, NodeApp, ErrHandler> {
331    /// Identifier of the original access.
332    initial: UniIndex,
333    /// Function describing whether to continue at a tag.
334    /// This is only invoked for foreign accesses.
335    f_continue: NodeContinue,
336    /// Function to apply to each tag.
337    f_propagate: NodeApp,
338    /// Handler to add the required context to diagnostics.
339    err_builder: ErrHandler,
340    /// Mutable state of the visit: the tags left to handle.
341    /// Every tag pushed should eventually be handled,
342    /// and the precise order is relevant for diagnostics.
343    /// Since the traversal is piecewise bottom-up, we need to
344    /// remember whether we're here initially, or after visiting all children.
345    /// The last element indicates this.
346    /// This is just an artifact of how you hand-roll recursion,
347    /// it does not have a deeper meaning otherwise.
348    stack: Vec<(UniIndex, AccessRelatedness, RecursionState)>,
349}
350
351impl<NodeContinue, NodeApp, InnErr, OutErr, ErrHandler>
352    TreeVisitorStack<NodeContinue, NodeApp, ErrHandler>
353where
354    NodeContinue: Fn(&NodeAppArgs<'_>) -> ContinueTraversal,
355    NodeApp: Fn(NodeAppArgs<'_>) -> Result<(), InnErr>,
356    ErrHandler: Fn(ErrHandlerArgs<'_, InnErr>) -> OutErr,
357{
358    fn should_continue_at(
359        &self,
360        this: &mut TreeVisitor<'_>,
361        idx: UniIndex,
362        rel_pos: AccessRelatedness,
363    ) -> ContinueTraversal {
364        let node = this.nodes.get_mut(idx).unwrap();
365        let args = NodeAppArgs { node, perm: this.perms.entry(idx), rel_pos };
366        (self.f_continue)(&args)
367    }
368
369    fn propagate_at(
370        &mut self,
371        this: &mut TreeVisitor<'_>,
372        idx: UniIndex,
373        rel_pos: AccessRelatedness,
374    ) -> Result<(), OutErr> {
375        let node = this.nodes.get_mut(idx).unwrap();
376        (self.f_propagate)(NodeAppArgs { node, perm: this.perms.entry(idx), rel_pos }).map_err(
377            |error_kind| {
378                (self.err_builder)(ErrHandlerArgs {
379                    error_kind,
380                    conflicting_info: &this.nodes.get(idx).unwrap().debug_info,
381                    accessed_info: &this.nodes.get(self.initial).unwrap().debug_info,
382                })
383            },
384        )
385    }
386
387    fn go_upwards_from_accessed(
388        &mut self,
389        this: &mut TreeVisitor<'_>,
390        accessed_node: UniIndex,
391        visit_children: ChildrenVisitMode,
392    ) -> Result<(), OutErr> {
393        // We want to visit the accessed node's children first.
394        // However, we will below walk up our parents and push their children (our cousins)
395        // onto the stack. To ensure correct iteration order, this method thus finishes
396        // by reversing the stack. This only works if the stack is empty initially.
397        assert!(self.stack.is_empty());
398        // First, handle accessed node. A bunch of things need to
399        // be handled differently here compared to the further parents
400        // of `accesssed_node`.
401        {
402            self.propagate_at(this, accessed_node, AccessRelatedness::This)?;
403            if matches!(visit_children, ChildrenVisitMode::VisitChildrenOfAccessed) {
404                let accessed_node = this.nodes.get(accessed_node).unwrap();
405                // We `rev()` here because we reverse the entire stack later.
406                for &child in accessed_node.children.iter().rev() {
407                    self.stack.push((
408                        child,
409                        AccessRelatedness::AncestorAccess,
410                        RecursionState::BeforeChildren,
411                    ));
412                }
413            }
414        }
415        // Then, handle the accessed node's parents. Here, we need to
416        // make sure we only mark the "cousin" subtrees for later visitation,
417        // not the subtree that contains the accessed node.
418        let mut last_node = accessed_node;
419        while let Some(current) = this.nodes.get(last_node).unwrap().parent {
420            self.propagate_at(this, current, AccessRelatedness::StrictChildAccess)?;
421            let node = this.nodes.get(current).unwrap();
422            // We `rev()` here because we reverse the entire stack later.
423            for &child in node.children.iter().rev() {
424                if last_node == child {
425                    continue;
426                }
427                self.stack.push((
428                    child,
429                    AccessRelatedness::CousinAccess,
430                    RecursionState::BeforeChildren,
431                ));
432            }
433            last_node = current;
434        }
435        // Reverse the stack, as discussed above.
436        self.stack.reverse();
437        Ok(())
438    }
439
440    fn finish_foreign_accesses(&mut self, this: &mut TreeVisitor<'_>) -> Result<(), OutErr> {
441        while let Some((idx, rel_pos, step)) = self.stack.last_mut() {
442            let idx = *idx;
443            let rel_pos = *rel_pos;
444            match *step {
445                // How to do bottom-up traversal, 101: Before you handle a node, you handle all children.
446                // For this, you must first find the children, which is what this code here does.
447                RecursionState::BeforeChildren => {
448                    // Next time we come back will be when all the children are handled.
449                    *step = RecursionState::AfterChildren;
450                    // Now push the children, except if we are told to skip this subtree.
451                    let handle_children = self.should_continue_at(this, idx, rel_pos);
452                    match handle_children {
453                        ContinueTraversal::Recurse => {
454                            let node = this.nodes.get(idx).unwrap();
455                            for &child in node.children.iter() {
456                                self.stack.push((child, rel_pos, RecursionState::BeforeChildren));
457                            }
458                        }
459                        ContinueTraversal::SkipSelfAndChildren => {
460                            // skip self
461                            self.stack.pop();
462                            continue;
463                        }
464                    }
465                }
466                // All the children are handled, let's actually visit this node
467                RecursionState::AfterChildren => {
468                    self.stack.pop();
469                    self.propagate_at(this, idx, rel_pos)?;
470                }
471            }
472        }
473        Ok(())
474    }
475
476    fn new(
477        initial: UniIndex,
478        f_continue: NodeContinue,
479        f_propagate: NodeApp,
480        err_builder: ErrHandler,
481    ) -> Self {
482        Self { initial, f_continue, f_propagate, err_builder, stack: Vec::new() }
483    }
484}
485
486impl<'tree> TreeVisitor<'tree> {
487    /// Applies `f_propagate` to every vertex of the tree in a piecewise bottom-up way: First, visit
488    /// all ancestors of `start` (starting with `start` itself), then children of `start`, then the rest,
489    /// going bottom-up in each of these two "pieces" / sections.
490    /// This ensures that errors are triggered in the following order
491    /// - first invalid accesses with insufficient permissions, closest to the accessed node first,
492    /// - then protector violations, bottom-up, starting with the children of the accessed node, and then
493    ///   going upwards and outwards.
494    ///
495    /// The following graphic visualizes it, with numbers indicating visitation order and `start` being
496    /// the node that is visited first ("1"):
497    ///
498    /// ```text
499    ///         3
500    ///        /|
501    ///       / |
502    ///      9  2
503    ///      |  |\
504    ///      |  | \
505    ///      8  1  7
506    ///        / \
507    ///       4   6
508    ///           |
509    ///           5
510    /// ```
511    ///
512    /// `f_propagate` should follow the following format: for a given `Node` it updates its
513    /// `Permission` depending on the position relative to `start` (given by an
514    /// `AccessRelatedness`).
515    /// `f_continue` is called earlier on foreign nodes, and describes whether to even start
516    /// visiting the subtree at that node. If it e.g. returns `SkipSelfAndChildren` on node 6
517    /// above, then nodes 5 _and_ 6 would not be visited by `f_propagate`. It is not used for
518    /// notes having a child access (nodes 1, 2, 3).
519    ///
520    /// Finally, remember that the iteration order is not relevant for UB, it only affects
521    /// diagnostics. It also affects tree traversal optimizations built on top of this, so
522    /// those need to be reviewed carefully as well whenever this changes.
523    fn traverse_this_parents_children_other<InnErr, OutErr>(
524        mut self,
525        start: BorTag,
526        f_continue: impl Fn(&NodeAppArgs<'_>) -> ContinueTraversal,
527        f_propagate: impl Fn(NodeAppArgs<'_>) -> Result<(), InnErr>,
528        err_builder: impl Fn(ErrHandlerArgs<'_, InnErr>) -> OutErr,
529    ) -> Result<(), OutErr> {
530        let start_idx = self.tag_mapping.get(&start).unwrap();
531        let mut stack = TreeVisitorStack::new(start_idx, f_continue, f_propagate, err_builder);
532        // Visits the accessed node itself, and all its parents, i.e. all nodes
533        // undergoing a child access. Also pushes the children and the other
534        // cousin nodes (i.e. all nodes undergoing a foreign access) to the stack
535        // to be processed later.
536        stack.go_upwards_from_accessed(
537            &mut self,
538            start_idx,
539            ChildrenVisitMode::VisitChildrenOfAccessed,
540        )?;
541        // Now visit all the foreign nodes we remembered earlier.
542        // For this we go bottom-up, but also allow f_continue to skip entire
543        // subtrees from being visited if it would be a NOP.
544        stack.finish_foreign_accesses(&mut self)
545    }
546
547    /// Like `traverse_this_parents_children_other`, but skips the children of `start`.
548    fn traverse_nonchildren<InnErr, OutErr>(
549        mut self,
550        start: BorTag,
551        f_continue: impl Fn(&NodeAppArgs<'_>) -> ContinueTraversal,
552        f_propagate: impl Fn(NodeAppArgs<'_>) -> Result<(), InnErr>,
553        err_builder: impl Fn(ErrHandlerArgs<'_, InnErr>) -> OutErr,
554    ) -> Result<(), OutErr> {
555        let start_idx = self.tag_mapping.get(&start).unwrap();
556        let mut stack = TreeVisitorStack::new(start_idx, f_continue, f_propagate, err_builder);
557        // Visits the accessed node itself, and all its parents, i.e. all nodes
558        // undergoing a child access. Also pushes the other cousin nodes to the
559        // stack, but not the children of the accessed node.
560        stack.go_upwards_from_accessed(
561            &mut self,
562            start_idx,
563            ChildrenVisitMode::SkipChildrenOfAccessed,
564        )?;
565        // Now visit all the foreign nodes we remembered earlier.
566        // For this we go bottom-up, but also allow f_continue to skip entire
567        // subtrees from being visited if it would be a NOP.
568        stack.finish_foreign_accesses(&mut self)
569    }
570}
571
572impl Tree {
573    /// Create a new tree, with only a root pointer.
574    pub fn new(root_tag: BorTag, size: Size, span: Span) -> Self {
575        // The root has `Disabled` as the default permission,
576        // so that any access out of bounds is invalid.
577        let root_default_perm = Permission::new_disabled();
578        let mut tag_mapping = UniKeyMap::default();
579        let root_idx = tag_mapping.insert(root_tag);
580        let nodes = {
581            let mut nodes = UniValMap::<Node>::default();
582            let mut debug_info = NodeDebugInfo::new(root_tag, root_default_perm, span);
583            // name the root so that all allocations contain one named pointer
584            debug_info.add_name("root of the allocation");
585            nodes.insert(
586                root_idx,
587                Node {
588                    tag: root_tag,
589                    parent: None,
590                    children: SmallVec::default(),
591                    default_initial_perm: root_default_perm,
592                    // The root may never be skipped, all accesses will be local.
593                    default_initial_idempotent_foreign_access: IdempotentForeignAccess::None,
594                    debug_info,
595                },
596            );
597            nodes
598        };
599        let rperms = {
600            let mut perms = UniValMap::default();
601            // We manually set it to `Active` on all in-bounds positions.
602            // We also ensure that it is accessed, so that no `Active` but
603            // not yet accessed nodes exist. Essentially, we pretend there
604            // was a write that initialized these to `Active`.
605            perms.insert(
606                root_idx,
607                LocationState::new_accessed(
608                    Permission::new_active(),
609                    IdempotentForeignAccess::None,
610                ),
611            );
612            RangeMap::new(size, perms)
613        };
614        Self { root: root_idx, nodes, rperms, tag_mapping }
615    }
616}
617
618impl<'tcx> Tree {
619    /// Insert a new tag in the tree.
620    ///
621    /// `initial_perms` defines the initial permissions for the part of memory
622    /// that is already considered "initialized" immediately. The ranges in this
623    /// map are relative to `base_offset`.
624    /// `default_perm` defines the initial permission for the rest of the allocation.
625    ///
626    /// For all non-accessed locations in the RangeMap (those that haven't had an
627    /// implicit read), their SIFA must be weaker than or as weak as the SIFA of
628    /// `default_perm`.
629    pub(super) fn new_child(
630        &mut self,
631        base_offset: Size,
632        parent_tag: BorTag,
633        new_tag: BorTag,
634        initial_perms: RangeMap<LocationState>,
635        default_perm: Permission,
636        protected: bool,
637        span: Span,
638    ) -> InterpResult<'tcx> {
639        let idx = self.tag_mapping.insert(new_tag);
640        let parent_idx = self.tag_mapping.get(&parent_tag).unwrap();
641        assert!(default_perm.is_initial());
642
643        let default_strongest_idempotent =
644            default_perm.strongest_idempotent_foreign_access(protected);
645        // Create the node
646        self.nodes.insert(
647            idx,
648            Node {
649                tag: new_tag,
650                parent: Some(parent_idx),
651                children: SmallVec::default(),
652                default_initial_perm: default_perm,
653                default_initial_idempotent_foreign_access: default_strongest_idempotent,
654                debug_info: NodeDebugInfo::new(new_tag, default_perm, span),
655            },
656        );
657        // Register new_tag as a child of parent_tag
658        self.nodes.get_mut(parent_idx).unwrap().children.push(idx);
659
660        for (Range { start, end }, &perm) in
661            initial_perms.iter(Size::from_bytes(0), initial_perms.size())
662        {
663            assert!(perm.is_initial());
664            for (_perms_range, perms) in self
665                .rperms
666                .iter_mut(Size::from_bytes(start) + base_offset, Size::from_bytes(end - start))
667            {
668                assert!(
669                    default_strongest_idempotent
670                        >= perm.permission.strongest_idempotent_foreign_access(protected)
671                );
672                perms.insert(idx, perm);
673            }
674        }
675
676        // Inserting the new perms might have broken the SIFA invariant (see `foreign_access_skipping.rs`).
677        // We now weaken the recorded SIFA for our parents, until the invariant is restored.
678        // We could weaken them all to `LocalAccess`, but it is more efficient to compute the SIFA
679        // for the new permission statically, and use that.
680        // See the comment in `tb_reborrow` for why it is correct to use the SIFA of `default_uninit_perm`.
681        self.update_last_accessed_after_retag(parent_idx, default_strongest_idempotent);
682
683        interp_ok(())
684    }
685
686    /// Restores the SIFA "children are stronger" invariant after a retag.
687    /// See `foreign_access_skipping` and `new_child`.
688    fn update_last_accessed_after_retag(
689        &mut self,
690        mut current: UniIndex,
691        strongest_allowed: IdempotentForeignAccess,
692    ) {
693        // We walk the tree upwards, until the invariant is restored
694        loop {
695            let current_node = self.nodes.get_mut(current).unwrap();
696            // Call `ensure_no_stronger_than` on all SIFAs for this node: the per-location SIFA, as well
697            // as the default SIFA for not-yet-initialized locations.
698            // Record whether we did any change; if not, the invariant is restored and we can stop the traversal.
699            let mut any_change = false;
700            for (_, map) in self.rperms.iter_mut_all() {
701                // Check if this node has a state for this location (or range of locations).
702                if let Some(perm) = map.get_mut(current) {
703                    // Update the per-location SIFA, recording if it changed.
704                    any_change |=
705                        perm.idempotent_foreign_access.ensure_no_stronger_than(strongest_allowed);
706                }
707            }
708            // Now update `default_initial_idempotent_foreign_access`, which stores the default SIFA for not-yet-initialized locations.
709            any_change |= current_node
710                .default_initial_idempotent_foreign_access
711                .ensure_no_stronger_than(strongest_allowed);
712
713            if any_change {
714                let Some(next) = self.nodes.get(current).unwrap().parent else {
715                    // We have arrived at the root.
716                    break;
717                };
718                current = next;
719                continue;
720            } else {
721                break;
722            }
723        }
724    }
725
726    /// Deallocation requires
727    /// - a pointer that permits write accesses
728    /// - the absence of Strong Protectors anywhere in the allocation
729    pub fn dealloc(
730        &mut self,
731        tag: BorTag,
732        access_range: AllocRange,
733        global: &GlobalState,
734        alloc_id: AllocId, // diagnostics
735        span: Span,        // diagnostics
736    ) -> InterpResult<'tcx> {
737        self.perform_access(
738            tag,
739            Some((access_range, AccessKind::Write, diagnostics::AccessCause::Dealloc)),
740            global,
741            alloc_id,
742            span,
743        )?;
744        for (perms_range, perms) in self.rperms.iter_mut(access_range.start, access_range.size) {
745            TreeVisitor { nodes: &mut self.nodes, tag_mapping: &self.tag_mapping, perms }
746                .traverse_this_parents_children_other(
747                    tag,
748                    // visit all children, skipping none
749                    |_| ContinueTraversal::Recurse,
750                    |args: NodeAppArgs<'_>| -> Result<(), TransitionError> {
751                        let NodeAppArgs { node, perm, .. } = args;
752                        let perm =
753                            perm.get().copied().unwrap_or_else(|| node.default_location_state());
754                        if global.borrow().protected_tags.get(&node.tag)
755                            == Some(&ProtectorKind::StrongProtector)
756                            // Don't check for protector if it is a Cell (see `unsafe_cell_deallocate` in `interior_mutability.rs`).
757                            // Related to https://github.com/rust-lang/rust/issues/55005.
758                            && !perm.permission().is_cell()
759                        {
760                            Err(TransitionError::ProtectedDealloc)
761                        } else {
762                            Ok(())
763                        }
764                    },
765                    |args: ErrHandlerArgs<'_, TransitionError>| -> InterpErrorKind<'tcx> {
766                        let ErrHandlerArgs { error_kind, conflicting_info, accessed_info } = args;
767                        TbError {
768                            conflicting_info,
769                            access_cause: diagnostics::AccessCause::Dealloc,
770                            alloc_id,
771                            error_offset: perms_range.start,
772                            error_kind,
773                            accessed_info,
774                        }
775                        .build()
776                    },
777                )?;
778        }
779        interp_ok(())
780    }
781
782    /// Map the per-node and per-location `LocationState::perform_access`
783    /// to each location of the first component of `access_range_and_kind`,
784    /// on every tag of the allocation.
785    ///
786    /// If `access_range_and_kind` is `None`, this is interpreted as the special
787    /// access that is applied on protector release:
788    /// - the access will be applied only to accessed locations of the allocation,
789    /// - it will not be visible to children,
790    /// - it will be recorded as a `FnExit` diagnostic access
791    /// - and it will be a read except if the location is `Active`, i.e. has been written to,
792    ///   in which case it will be a write.
793    ///
794    /// `LocationState::perform_access` will take care of raising transition
795    /// errors and updating the `accessed` status of each location,
796    /// this traversal adds to that:
797    /// - inserting into the map locations that do not exist yet,
798    /// - trimming the traversal,
799    /// - recording the history.
800    pub fn perform_access(
801        &mut self,
802        tag: BorTag,
803        access_range_and_kind: Option<(AllocRange, AccessKind, diagnostics::AccessCause)>,
804        global: &GlobalState,
805        alloc_id: AllocId, // diagnostics
806        span: Span,        // diagnostics
807    ) -> InterpResult<'tcx> {
808        use std::ops::Range;
809        // Performs the per-node work:
810        // - insert the permission if it does not exist
811        // - perform the access
812        // - record the transition
813        // to which some optimizations are added:
814        // - skip the traversal of the children in some cases
815        // - do not record noop transitions
816        //
817        // `perms_range` is only for diagnostics (it is the range of
818        // the `RangeMap` on which we are currently working).
819        let node_skipper = |access_kind: AccessKind, args: &NodeAppArgs<'_>| -> ContinueTraversal {
820            let NodeAppArgs { node, perm, rel_pos } = args;
821
822            let old_state = perm.get().copied().unwrap_or_else(|| node.default_location_state());
823            old_state.skip_if_known_noop(access_kind, *rel_pos)
824        };
825        let node_app = |perms_range: Range<u64>,
826                        access_kind: AccessKind,
827                        access_cause: diagnostics::AccessCause,
828                        args: NodeAppArgs<'_>|
829         -> Result<(), TransitionError> {
830            let NodeAppArgs { node, mut perm, rel_pos } = args;
831
832            let old_state = perm.or_insert(node.default_location_state());
833
834            // Call this function now, which ensures it is only called when
835            // `skip_if_known_noop` returns `Recurse`, due to the contract of
836            // `traverse_this_parents_children_other`.
837            old_state.record_new_access(access_kind, rel_pos);
838
839            let protected = global.borrow().protected_tags.contains_key(&node.tag);
840            let transition = old_state.perform_access(access_kind, rel_pos, protected)?;
841            // Record the event as part of the history
842            if !transition.is_noop() {
843                node.debug_info.history.push(diagnostics::Event {
844                    transition,
845                    is_foreign: rel_pos.is_foreign(),
846                    access_cause,
847                    access_range: access_range_and_kind.map(|x| x.0),
848                    transition_range: perms_range,
849                    span,
850                });
851            }
852            Ok(())
853        };
854
855        // Error handler in case `node_app` goes wrong.
856        // Wraps the faulty transition in more context for diagnostics.
857        let err_handler = |perms_range: Range<u64>,
858                           access_cause: diagnostics::AccessCause,
859                           args: ErrHandlerArgs<'_, TransitionError>|
860         -> InterpErrorKind<'tcx> {
861            let ErrHandlerArgs { error_kind, conflicting_info, accessed_info } = args;
862            TbError {
863                conflicting_info,
864                access_cause,
865                alloc_id,
866                error_offset: perms_range.start,
867                error_kind,
868                accessed_info,
869            }
870            .build()
871        };
872
873        if let Some((access_range, access_kind, access_cause)) = access_range_and_kind {
874            // Default branch: this is a "normal" access through a known range.
875            // We iterate over affected locations and traverse the tree for each of them.
876            for (perms_range, perms) in self.rperms.iter_mut(access_range.start, access_range.size)
877            {
878                TreeVisitor { nodes: &mut self.nodes, tag_mapping: &self.tag_mapping, perms }
879                    .traverse_this_parents_children_other(
880                        tag,
881                        |args| node_skipper(access_kind, args),
882                        |args| node_app(perms_range.clone(), access_kind, access_cause, args),
883                        |args| err_handler(perms_range.clone(), access_cause, args),
884                    )?;
885            }
886        } else {
887            // This is a special access through the entire allocation.
888            // It actually only affects `accessed` locations, so we need
889            // to filter on those before initiating the traversal.
890            //
891            // In addition this implicit access should not be visible to children,
892            // thus the use of `traverse_nonchildren`.
893            // See the test case `returned_mut_is_usable` from
894            // `tests/pass/tree_borrows/tree-borrows.rs` for an example of
895            // why this is important.
896            for (perms_range, perms) in self.rperms.iter_mut_all() {
897                let idx = self.tag_mapping.get(&tag).unwrap();
898                // Only visit accessed permissions
899                if let Some(p) = perms.get(idx)
900                    && let Some(access_kind) = p.permission.protector_end_access()
901                    && p.accessed
902                {
903                    let access_cause = diagnostics::AccessCause::FnExit(access_kind);
904                    TreeVisitor { nodes: &mut self.nodes, tag_mapping: &self.tag_mapping, perms }
905                        .traverse_nonchildren(
906                        tag,
907                        |args| node_skipper(access_kind, args),
908                        |args| node_app(perms_range.clone(), access_kind, access_cause, args),
909                        |args| err_handler(perms_range.clone(), access_cause, args),
910                    )?;
911                }
912            }
913        }
914        interp_ok(())
915    }
916}
917
918/// Integration with the BorTag garbage collector
919impl Tree {
920    pub fn remove_unreachable_tags(&mut self, live_tags: &FxHashSet<BorTag>) {
921        self.remove_useless_children(self.root, live_tags);
922        // Right after the GC runs is a good moment to check if we can
923        // merge some adjacent ranges that were made equal by the removal of some
924        // tags (this does not necessarily mean that they have identical internal representations,
925        // see the `PartialEq` impl for `UniValMap`)
926        self.rperms.merge_adjacent_thorough();
927    }
928
929    /// Checks if a node is useless and should be GC'ed.
930    /// A node is useless if it has no children and also the tag is no longer live.
931    fn is_useless(&self, idx: UniIndex, live: &FxHashSet<BorTag>) -> bool {
932        let node = self.nodes.get(idx).unwrap();
933        node.children.is_empty() && !live.contains(&node.tag)
934    }
935
936    /// Checks whether a node can be replaced by its only child.
937    /// If so, returns the index of said only child.
938    /// If not, returns none.
939    fn can_be_replaced_by_single_child(
940        &self,
941        idx: UniIndex,
942        live: &FxHashSet<BorTag>,
943    ) -> Option<UniIndex> {
944        let node = self.nodes.get(idx).unwrap();
945
946        let [child_idx] = node.children[..] else { return None };
947
948        // We never want to replace the root node, as it is also kept in `root_ptr_tags`.
949        if live.contains(&node.tag) || node.parent.is_none() {
950            return None;
951        }
952        // Since protected nodes are never GC'd (see `borrow_tracker::FrameExtra::visit_provenance`),
953        // we know that `node` is not protected because otherwise `live` would
954        // have contained `node.tag`.
955        let child = self.nodes.get(child_idx).unwrap();
956        // Check that for that one child, `can_be_replaced_by_child` holds for the permission
957        // on all locations.
958        for (_, data) in self.rperms.iter_all() {
959            let parent_perm =
960                data.get(idx).map(|x| x.permission).unwrap_or_else(|| node.default_initial_perm);
961            let child_perm = data
962                .get(child_idx)
963                .map(|x| x.permission)
964                .unwrap_or_else(|| child.default_initial_perm);
965            if !parent_perm.can_be_replaced_by_child(child_perm) {
966                return None;
967            }
968        }
969
970        Some(child_idx)
971    }
972
973    /// Properly removes a node.
974    /// The node to be removed should not otherwise be usable. It also
975    /// should have no children, but this is not checked, so that nodes
976    /// whose children were rotated somewhere else can be deleted without
977    /// having to first modify them to clear that array.
978    fn remove_useless_node(&mut self, this: UniIndex) {
979        // Due to the API of UniMap we must make sure to call
980        // `UniValMap::remove` for the key of this node on *all* maps that used it
981        // (which are `self.nodes` and every range of `self.rperms`)
982        // before we can safely apply `UniKeyMap::remove` to truly remove
983        // this tag from the `tag_mapping`.
984        let node = self.nodes.remove(this).unwrap();
985        for (_perms_range, perms) in self.rperms.iter_mut_all() {
986            perms.remove(this);
987        }
988        self.tag_mapping.remove(&node.tag);
989    }
990
991    /// Traverses the entire tree looking for useless tags.
992    /// Removes from the tree all useless child nodes of root.
993    /// It will not delete the root itself.
994    ///
995    /// NOTE: This leaves in the middle of the tree tags that are unreachable but have
996    /// reachable children. There is a potential for compacting the tree by reassigning
997    /// children of dead tags to the nearest live parent, but it must be done with care
998    /// not to remove UB.
999    ///
1000    /// Example: Consider the tree `root - parent - child`, with `parent: Frozen` and
1001    /// `child: Reserved`. This tree can exist. If we blindly delete `parent` and reassign
1002    /// `child` to be a direct child of `root` then Writes to `child` are now permitted
1003    /// whereas they were not when `parent` was still there.
1004    fn remove_useless_children(&mut self, root: UniIndex, live: &FxHashSet<BorTag>) {
1005        // To avoid stack overflows, we roll our own stack.
1006        // Each element in the stack consists of the current tag, and the number of the
1007        // next child to be processed.
1008
1009        // The other functions are written using the `TreeVisitorStack`, but that does not work here
1010        // since we need to 1) do a post-traversal and 2) remove nodes from the tree.
1011        // Since we do a post-traversal (by deleting nodes only after handling all children),
1012        // we also need to be a bit smarter than "pop node, push all children."
1013        let mut stack = vec![(root, 0)];
1014        while let Some((tag, nth_child)) = stack.last_mut() {
1015            let node = self.nodes.get(*tag).unwrap();
1016            if *nth_child < node.children.len() {
1017                // Visit the child by pushing it to the stack.
1018                // Also increase `nth_child` so that when we come back to the `tag` node, we
1019                // look at the next child.
1020                let next_child = node.children[*nth_child];
1021                *nth_child += 1;
1022                stack.push((next_child, 0));
1023                continue;
1024            } else {
1025                // We have processed all children of `node`, so now it is time to process `node` itself.
1026                // First, get the current children of `node`. To appease the borrow checker,
1027                // we have to temporarily move the list out of the node, and then put the
1028                // list of remaining children back in.
1029                let mut children_of_node =
1030                    mem::take(&mut self.nodes.get_mut(*tag).unwrap().children);
1031                // Remove all useless children.
1032                children_of_node.retain_mut(|idx| {
1033                    if self.is_useless(*idx, live) {
1034                        // Delete `idx` node everywhere else.
1035                        self.remove_useless_node(*idx);
1036                        // And delete it from children_of_node.
1037                        false
1038                    } else {
1039                        if let Some(nextchild) = self.can_be_replaced_by_single_child(*idx, live) {
1040                            // `nextchild` is our grandchild, and will become our direct child.
1041                            // Delete the in-between node, `idx`.
1042                            self.remove_useless_node(*idx);
1043                            // Set the new child's parent.
1044                            self.nodes.get_mut(nextchild).unwrap().parent = Some(*tag);
1045                            // Save the new child in children_of_node.
1046                            *idx = nextchild;
1047                        }
1048                        // retain it
1049                        true
1050                    }
1051                });
1052                // Put back the now-filtered vector.
1053                self.nodes.get_mut(*tag).unwrap().children = children_of_node;
1054
1055                // We are done, the parent can continue.
1056                stack.pop();
1057                continue;
1058            }
1059        }
1060    }
1061}
1062
1063impl Node {
1064    pub fn default_location_state(&self) -> LocationState {
1065        LocationState::new_non_accessed(
1066            self.default_initial_perm,
1067            self.default_initial_idempotent_foreign_access,
1068        )
1069    }
1070}
1071
1072impl VisitProvenance for Tree {
1073    fn visit_provenance(&self, visit: &mut VisitWith<'_>) {
1074        // To ensure that the root never gets removed, we visit it
1075        // (the `root` node of `Tree` is not an `Option<_>`)
1076        visit(None, Some(self.nodes.get(self.root).unwrap().tag))
1077    }
1078}
1079
1080/// Relative position of the access
1081#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1082pub enum AccessRelatedness {
1083    /// The accessed pointer is the current one
1084    This,
1085    /// The accessed pointer is a (transitive) child of the current one.
1086    // Current pointer is excluded (unlike in some other places of this module
1087    // where "child" is inclusive).
1088    StrictChildAccess,
1089    /// The accessed pointer is a (transitive) parent of the current one.
1090    // Current pointer is excluded.
1091    AncestorAccess,
1092    /// The accessed pointer is neither of the above.
1093    // It's a cousin/uncle/etc., something in a side branch.
1094    CousinAccess,
1095}
1096
1097impl AccessRelatedness {
1098    /// Check that access is either Ancestor or Distant, i.e. not
1099    /// a transitive child (initial pointer included).
1100    pub fn is_foreign(self) -> bool {
1101        matches!(self, AccessRelatedness::AncestorAccess | AccessRelatedness::CousinAccess)
1102    }
1103}