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