miri/borrow_tracker/tree_borrows/
perms.rs

1use std::cmp::{Ordering, PartialOrd};
2use std::fmt;
3
4use crate::AccessKind;
5use crate::borrow_tracker::tree_borrows::diagnostics::TransitionError;
6use crate::borrow_tracker::tree_borrows::tree::AccessRelatedness;
7
8/// The activation states of a pointer.
9#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
10enum PermissionPriv {
11    /// represents: a shared reference to interior mutable data.
12    /// allows: all foreign and child accesses;
13    /// rejects: nothing
14    Cell,
15    /// represents: a local mutable reference that has not yet been written to;
16    /// allows: child reads, foreign reads;
17    /// affected by: child writes (becomes Active),
18    /// rejects: foreign writes (Disabled).
19    ///
20    /// `ReservedFrz` is mostly for types that are `Freeze` (no interior mutability).
21    /// If the type has interior mutability, see `ReservedIM` instead.
22    /// (Note: since the discovery of `tests/fail/tree_borrows/reservedim_spurious_write.rs`,
23    /// we also use `ReservedFreeze` for mutable references that were retagged with a protector
24    /// independently of interior mutability)
25    ///
26    /// special case: behaves differently when protected, which is where `conflicted`
27    /// is relevant
28    /// - `conflicted` is set on foreign reads,
29    /// - `conflicted` must not be set on child writes (there is UB otherwise).
30    ///
31    /// This is so that the behavior of `Reserved` adheres to the rules of `noalias`:
32    /// - foreign-read then child-write is UB due to `conflicted`,
33    /// - child-write then foreign-read is UB since child-write will activate and then
34    ///   foreign-read disables a protected `Active`, which is UB.
35    ReservedFrz { conflicted: bool },
36    /// Alternative version of `ReservedFrz` made for types with interior mutability.
37    /// allows: child reads, foreign reads, foreign writes (extra);
38    /// affected by: child writes (becomes Active);
39    /// rejects: nothing.
40    ReservedIM,
41    /// represents: a unique pointer;
42    /// allows: child reads, child writes;
43    /// rejects: foreign reads (Frozen), foreign writes (Disabled).
44    Active,
45    /// represents: a shared pointer;
46    /// allows: all read accesses;
47    /// rejects child writes (UB), foreign writes (Disabled).
48    Frozen,
49    /// represents: a dead pointer;
50    /// allows: all foreign accesses;
51    /// rejects: all child accesses (UB).
52    Disabled,
53}
54use self::PermissionPriv::*;
55use super::foreign_access_skipping::IdempotentForeignAccess;
56
57impl PartialOrd for PermissionPriv {
58    /// PermissionPriv is ordered by the reflexive transitive closure of
59    /// `Reserved(conflicted=false) < Reserved(conflicted=true) < Active < Frozen < Disabled`.
60    /// `Reserved` that have incompatible `ty_is_freeze` are incomparable to each other.
61    /// This ordering matches the reachability by transitions, as asserted by the exhaustive test
62    /// `permissionpriv_partialord_is_reachability`.
63    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
64        use Ordering::*;
65        Some(match (self, other) {
66            (a, b) if a == b => Equal,
67            // Versions of `Reserved` with different interior mutability are incomparable with each
68            // other.
69            (ReservedIM, ReservedFrz { .. })
70            | (ReservedFrz { .. }, ReservedIM)
71            // `Cell` is not comparable with any other permission
72            // since it never transitions to any other state and we
73            // can never get to `Cell` from another state.
74            | (Cell, _) | (_, Cell) => return None,
75            (Disabled, _) => Greater,
76            (_, Disabled) => Less,
77            (Frozen, _) => Greater,
78            (_, Frozen) => Less,
79            (Active, _) => Greater,
80            (_, Active) => Less,
81            (ReservedIM, ReservedIM) => Equal,
82            (ReservedFrz { conflicted: c1 }, ReservedFrz { conflicted: c2 }) => {
83                // `bool` is ordered such that `false <= true`, so this works as intended.
84                c1.cmp(c2)
85            }
86        })
87    }
88}
89
90impl PermissionPriv {
91    /// Check if `self` can be the initial state of a pointer.
92    fn is_initial(&self) -> bool {
93        matches!(self, ReservedFrz { conflicted: false } | Frozen | ReservedIM | Cell)
94    }
95
96    /// Reject `ReservedIM` that cannot exist in the presence of a protector.
97    #[cfg(test)]
98    fn compatible_with_protector(&self) -> bool {
99        // FIXME(TB-Cell): It is unclear what to do here.
100        // `Cell` will occur with a protector but won't provide the guarantees
101        // of noalias (it will fail the `protected_enforces_noalias` test).
102        !matches!(self, ReservedIM | Cell)
103    }
104
105    /// See `foreign_access_skipping.rs`. Computes the SIFA of a permission.
106    fn strongest_idempotent_foreign_access(&self, prot: bool) -> IdempotentForeignAccess {
107        match self {
108            // Cell survives any foreign access
109            Cell => IdempotentForeignAccess::Write,
110            // A protected non-conflicted Reserved will become conflicted under a foreign read,
111            // and is hence not idempotent under it.
112            ReservedFrz { conflicted } if prot && !conflicted => IdempotentForeignAccess::None,
113            // Otherwise, foreign reads do not affect Reserved
114            ReservedFrz { .. } => IdempotentForeignAccess::Read,
115            // Famously, ReservedIM survives foreign writes. It is never protected.
116            ReservedIM if prot => unreachable!("Protected ReservedIM should not exist!"),
117            ReservedIM => IdempotentForeignAccess::Write,
118            // Active changes on any foreign access (becomes Frozen/Disabled).
119            Active => IdempotentForeignAccess::None,
120            // Frozen survives foreign reads, but not writes.
121            Frozen => IdempotentForeignAccess::Read,
122            // Disabled survives foreign reads and writes. It survives them
123            // even if protected, because a protected `Disabled` is not initialized
124            // and does therefore not trigger UB.
125            Disabled => IdempotentForeignAccess::Write,
126        }
127    }
128}
129
130/// This module controls how each permission individually reacts to an access.
131/// Although these functions take `protected` as an argument, this is NOT because
132/// we check protector violations here, but because some permissions behave differently
133/// when protected.
134mod transition {
135    use super::*;
136    /// A child node was read-accessed: UB on Disabled, noop on the rest.
137    fn child_read(state: PermissionPriv, _protected: bool) -> Option<PermissionPriv> {
138        Some(match state {
139            Disabled => return None,
140            // The inner data `ty_is_freeze` of `Reserved` is always irrelevant for Read
141            // accesses, since the data is not being mutated. Hence the `{ .. }`.
142            readable @ (Cell | ReservedFrz { .. } | ReservedIM | Active | Frozen) => readable,
143        })
144    }
145
146    /// A non-child node was read-accessed: keep `Reserved` but mark it as `conflicted` if it
147    /// is protected; invalidate `Active`.
148    fn foreign_read(state: PermissionPriv, protected: bool) -> Option<PermissionPriv> {
149        Some(match state {
150            // Cell ignores foreign reads.
151            Cell => Cell,
152            // Non-writeable states just ignore foreign reads.
153            non_writeable @ (Frozen | Disabled) => non_writeable,
154            // Writeable states are more tricky, and depend on whether things are protected.
155            // The inner data `ty_is_freeze` of `Reserved` is always irrelevant for Read
156            // accesses, since the data is not being mutated. Hence the `{ .. }`
157
158            // Someone else read. To make sure we won't write before function exit,
159            // we set the "conflicted" flag, which will disallow writes while we are protected.
160            ReservedFrz { .. } if protected => ReservedFrz { conflicted: true },
161            // Before activation and without protectors, foreign reads are fine.
162            // That's the entire point of 2-phase borrows.
163            res @ (ReservedFrz { .. } | ReservedIM) => {
164                // Even though we haven't checked `ReservedIM if protected` separately,
165                // it is a state that cannot occur because under a protector we only
166                // create `ReservedFrz` never `ReservedIM`.
167                assert!(!protected);
168                res
169            }
170            Active =>
171                if protected {
172                    // We wrote, someone else reads -- that's bad.
173                    // (Since Active is always initialized, this move-to-protected will mean insta-UB.)
174                    Disabled
175                } else {
176                    // We don't want to disable here to allow read-read reordering: it is crucial
177                    // that the foreign read does not invalidate future reads through this tag.
178                    Frozen
179                },
180        })
181    }
182
183    /// A child node was write-accessed: `Reserved` must become `Active` to obtain
184    /// write permissions, `Frozen` and `Disabled` cannot obtain such permissions and produce UB.
185    fn child_write(state: PermissionPriv, protected: bool) -> Option<PermissionPriv> {
186        Some(match state {
187            // Cell ignores child writes.
188            Cell => Cell,
189            // If the `conflicted` flag is set, then there was a foreign read during
190            // the function call that is still ongoing (still `protected`),
191            // this is UB (`noalias` violation).
192            ReservedFrz { conflicted: true } if protected => return None,
193            // A write always activates the 2-phase borrow, even with interior
194            // mutability
195            ReservedFrz { .. } | ReservedIM | Active => Active,
196            Frozen | Disabled => return None,
197        })
198    }
199
200    /// A non-child node was write-accessed: this makes everything `Disabled` except for
201    /// non-protected interior mutable `Reserved` which stay the same.
202    fn foreign_write(state: PermissionPriv, protected: bool) -> Option<PermissionPriv> {
203        // There is no explicit dependency on `protected`, but recall that interior mutable
204        // types receive a `ReservedFrz` instead of `ReservedIM` when retagged under a protector,
205        // so the result of this function does indirectly depend on (past) protector status.
206        Some(match state {
207            // Cell ignores foreign writes.
208            Cell => Cell,
209            res @ ReservedIM => {
210                // We can never create a `ReservedIM` under a protector, only `ReservedFrz`.
211                assert!(!protected);
212                res
213            }
214            _ => Disabled,
215        })
216    }
217
218    /// Dispatch handler depending on the kind of access and its position.
219    pub(super) fn perform_access(
220        kind: AccessKind,
221        rel_pos: AccessRelatedness,
222        child: PermissionPriv,
223        protected: bool,
224    ) -> Option<PermissionPriv> {
225        match (kind, rel_pos.is_foreign()) {
226            (AccessKind::Write, true) => foreign_write(child, protected),
227            (AccessKind::Read, true) => foreign_read(child, protected),
228            (AccessKind::Write, false) => child_write(child, protected),
229            (AccessKind::Read, false) => child_read(child, protected),
230        }
231    }
232}
233
234/// Public interface to the state machine that controls read-write permissions.
235/// This is the "private `enum`" pattern.
236#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd)]
237pub struct Permission {
238    inner: PermissionPriv,
239}
240
241/// Transition from one permission to the next.
242#[derive(Debug, Clone, Copy, PartialEq, Eq)]
243pub struct PermTransition {
244    from: PermissionPriv,
245    to: PermissionPriv,
246}
247
248impl Permission {
249    /// Check if `self` can be the initial state of a pointer.
250    pub fn is_initial(&self) -> bool {
251        self.inner.is_initial()
252    }
253    /// Check if `self` is the terminal state of a pointer (is `Disabled`).
254    pub fn is_disabled(&self) -> bool {
255        self.inner == Disabled
256    }
257    /// Check if `self` is the never-allow-writes-again state of a pointer (is `Frozen`).
258    pub fn is_frozen(&self) -> bool {
259        self.inner == Frozen
260    }
261
262    /// Check if `self` is the shared-reference-to-interior-mutable-data state of a pointer.
263    pub fn is_cell(&self) -> bool {
264        self.inner == Cell
265    }
266
267    /// Default initial permission of the root of a new tree at inbounds positions.
268    /// Must *only* be used for the root, this is not in general an "initial" permission!
269    pub fn new_active() -> Self {
270        Self { inner: Active }
271    }
272
273    /// Default initial permission of a reborrowed mutable reference that is either
274    /// protected or not interior mutable.
275    fn new_reserved_frz() -> Self {
276        Self { inner: ReservedFrz { conflicted: false } }
277    }
278
279    /// Default initial permission of an unprotected interior mutable reference.
280    fn new_reserved_im() -> Self {
281        Self { inner: ReservedIM }
282    }
283
284    /// Wrapper around `new_reserved_frz` and `new_reserved_im` that decides
285    /// which to call based on the interior mutability and the retag kind (whether there
286    /// is a protector is relevant because being protected takes priority over being
287    /// interior mutable)
288    pub fn new_reserved(ty_is_freeze: bool, protected: bool) -> Self {
289        // As demonstrated by `tests/fail/tree_borrows/reservedim_spurious_write.rs`,
290        // interior mutability and protectors interact poorly.
291        // To eliminate the case of Protected Reserved IM we override interior mutability
292        // in the case of a protected reference: protected references are always considered
293        // "freeze" in their reservation phase.
294        if ty_is_freeze || protected { Self::new_reserved_frz() } else { Self::new_reserved_im() }
295    }
296
297    /// Default initial permission of a reborrowed shared reference.
298    pub fn new_frozen() -> Self {
299        Self { inner: Frozen }
300    }
301
302    /// Default initial permission of  the root of a new tree at out-of-bounds positions.
303    /// Must *only* be used for the root, this is not in general an "initial" permission!
304    pub fn new_disabled() -> Self {
305        Self { inner: Disabled }
306    }
307
308    /// Default initial permission of a shared reference to interior mutable data.
309    pub fn new_cell() -> Self {
310        Self { inner: Cell }
311    }
312
313    /// Reject `ReservedIM` that cannot exist in the presence of a protector.
314    #[cfg(test)]
315    pub fn compatible_with_protector(&self) -> bool {
316        self.inner.compatible_with_protector()
317    }
318
319    /// What kind of access to perform before releasing the protector.
320    pub fn protector_end_access(&self) -> Option<AccessKind> {
321        match self.inner {
322            // Do not do perform access if it is a `Cell`, as this
323            // can cause data races when using thread-safe data types.
324            Cell => None,
325            Active => Some(AccessKind::Write),
326            _ => Some(AccessKind::Read),
327        }
328    }
329
330    /// Apply the transition to the inner PermissionPriv.
331    pub fn perform_access(
332        kind: AccessKind,
333        rel_pos: AccessRelatedness,
334        old_perm: Self,
335        protected: bool,
336    ) -> Option<PermTransition> {
337        let old_state = old_perm.inner;
338        transition::perform_access(kind, rel_pos, old_state, protected)
339            .map(|new_state| PermTransition { from: old_state, to: new_state })
340    }
341
342    /// During a provenance GC, we want to compact the tree.
343    /// For this, we want to merge nodes upwards if they have a singleton parent.
344    /// But we need to be careful: If the parent is Frozen, and the child is Reserved,
345    /// we can not do such a merge. In general, such a merge is possible if the parent
346    /// allows similar accesses, and in particular if the parent never causes UB on its
347    /// own. This is enforced by a test, namely `tree_compacting_is_sound`. See that
348    /// test for more information.
349    /// This method is only sound if the parent is not protected. We never attempt to
350    /// remove protected parents.
351    pub fn can_be_replaced_by_child(self, child: Self) -> bool {
352        match (self.inner, child.inner) {
353            // Cell allows all transitions.
354            (Cell, _) => true,
355            // Cell is the most permissive, nothing can be replaced by Cell.
356            // (ReservedIM, Cell) => true,
357            (_, Cell) => false,
358            // ReservedIM can be replaced by anything besides Cell.
359            // ReservedIM allows all transitions, but unlike Cell, a local write
360            // to ReservedIM transitions to Active, while it is a no-op for Cell.
361            (ReservedIM, _) => true,
362            (_, ReservedIM) => false,
363            // Reserved (as parent, where conflictedness does not matter)
364            // can be replaced by all but ReservedIM and Cell,
365            // since ReservedIM and Cell alone would survive foreign writes
366            (ReservedFrz { .. }, _) => true,
367            (_, ReservedFrz { .. }) => false,
368            // Active can not be replaced by something surviving
369            // foreign reads and then remaining writable (i.e., Reserved*).
370            // Replacing a state by itself is always okay, even if the child state is protected.
371            // Active can be replaced by Frozen, since it is not protected.
372            (Active, Active | Frozen | Disabled) => true,
373            (_, Active) => false,
374            // Frozen can only be replaced by Disabled (and itself).
375            (Frozen, Frozen | Disabled) => true,
376            (_, Frozen) => false,
377            // Disabled can not be replaced by anything else.
378            (Disabled, Disabled) => true,
379        }
380    }
381
382    /// Returns the strongest foreign action this node survives (without change),
383    /// where `prot` indicates if it is protected.
384    /// See `foreign_access_skipping`
385    pub fn strongest_idempotent_foreign_access(&self, prot: bool) -> IdempotentForeignAccess {
386        self.inner.strongest_idempotent_foreign_access(prot)
387    }
388}
389
390impl PermTransition {
391    /// All transitions created through normal means (using `perform_access`)
392    /// should be possible, but the same is not guaranteed by construction of
393    /// transitions inferred by diagnostics. This checks that a transition
394    /// reconstructed by diagnostics is indeed one that could happen.
395    fn is_possible(self) -> bool {
396        self.from <= self.to
397    }
398
399    pub fn is_noop(self) -> bool {
400        self.from == self.to
401    }
402
403    /// Extract result of a transition (checks that the starting point matches).
404    pub fn applied(self, starting_point: Permission) -> Option<Permission> {
405        (starting_point.inner == self.from).then_some(Permission { inner: self.to })
406    }
407
408    /// Determines if this transition would disable the permission.
409    pub fn produces_disabled(self) -> bool {
410        self.to == Disabled
411    }
412}
413
414pub mod diagnostics {
415    use super::*;
416    impl fmt::Display for PermissionPriv {
417        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
418            write!(
419                f,
420                "{}",
421                match self {
422                    Cell => "Cell",
423                    ReservedFrz { conflicted: false } => "Reserved",
424                    ReservedFrz { conflicted: true } => "Reserved (conflicted)",
425                    ReservedIM => "Reserved (interior mutable)",
426                    Active => "Active",
427                    Frozen => "Frozen",
428                    Disabled => "Disabled",
429                }
430            )
431        }
432    }
433
434    impl fmt::Display for PermTransition {
435        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
436            write!(f, "from {} to {}", self.from, self.to)
437        }
438    }
439
440    impl fmt::Display for Permission {
441        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
442            write!(f, "{}", self.inner)
443        }
444    }
445
446    impl Permission {
447        /// Abbreviated name of the permission (uniformly 3 letters for nice alignment).
448        pub fn short_name(self) -> &'static str {
449            // Make sure there are all of the same length as each other
450            // and also as `diagnostics::DisplayFmtPermission.uninit` otherwise
451            // alignment will be incorrect.
452            match self.inner {
453                Cell => "Cel ",
454                ReservedFrz { conflicted: false } => "Res ",
455                ReservedFrz { conflicted: true } => "ResC",
456                ReservedIM => "ReIM",
457                Active => "Act ",
458                Frozen => "Frz ",
459                Disabled => "Dis ",
460            }
461        }
462    }
463
464    impl PermTransition {
465        /// Readable explanation of the consequences of an event.
466        /// Fits in the sentence "This transition corresponds to {trans.summary()}".
467        pub fn summary(&self) -> &'static str {
468            assert!(self.is_possible());
469            assert!(!self.is_noop());
470            match (self.from, self.to) {
471                (_, Active) => "the first write to a 2-phase borrowed mutable reference",
472                (_, Frozen) => "a loss of write permissions",
473                (ReservedFrz { conflicted: false }, ReservedFrz { conflicted: true }) =>
474                    "a temporary loss of write permissions until function exit",
475                (Frozen, Disabled) => "a loss of read permissions",
476                (_, Disabled) => "a loss of read and write permissions",
477                (old, new) =>
478                    unreachable!("Transition from {old:?} to {new:?} should never be possible"),
479            }
480        }
481
482        /// Determines whether `self` is a relevant transition for the error `err`.
483        /// `self` will be a transition that happened to a tag some time before
484        /// that tag caused the error.
485        ///
486        /// Irrelevant events:
487        /// - modifications of write permissions when the error is related to read permissions
488        ///   (on failed reads and protected `Frozen -> Disabled`, ignore `Reserved -> Active`,
489        ///   `Reserved(conflicted=false) -> Reserved(conflicted=true)`, and `Active -> Frozen`)
490        /// - all transitions for attempts to deallocate strongly protected tags
491        ///
492        /// # Panics
493        ///
494        /// This function assumes that its arguments apply to the same location
495        /// and that they were obtained during a normal execution. It will panic otherwise.
496        /// - all transitions involved in `self` and `err` should be increasing
497        ///   (Reserved < Active < Frozen < Disabled);
498        /// - between `self` and `err` the permission should also be increasing,
499        ///   so all permissions inside `err` should be greater than `self.1`;
500        /// - `Active`, `Reserved(conflicted=false)`, and `Cell` cannot cause an error
501        ///   due to insufficient permissions, so `err` cannot be a `ChildAccessForbidden(_)`
502        ///   of either of them;
503        /// - `err` should not be `ProtectedDisabled(Disabled)`, because the protected
504        ///   tag should not have been `Disabled` in the first place (if this occurs it means
505        ///   we have unprotected tags that become protected)
506        pub(in super::super) fn is_relevant(&self, err: TransitionError) -> bool {
507            // NOTE: `super::super` is the visibility of `TransitionError`
508            assert!(self.is_possible());
509            if self.is_noop() {
510                return false;
511            }
512            match err {
513                TransitionError::ChildAccessForbidden(insufficient) => {
514                    // Show where the permission was gained then lost,
515                    // but ignore unrelated permissions.
516                    // This eliminates transitions like `Active -> Frozen`
517                    // when the error is a failed `Read`.
518                    match (self.to, insufficient.inner) {
519                        (Frozen, Frozen) => true,
520                        (Active, Frozen) => true,
521                        (Disabled, Disabled) => true,
522                        (
523                            ReservedFrz { conflicted: true, .. },
524                            ReservedFrz { conflicted: true, .. },
525                        ) => true,
526                        // A pointer being `Disabled` is a strictly stronger source of
527                        // errors than it being `Frozen`. If we try to access a `Disabled`,
528                        // then where it became `Frozen` (or `Active` or `Reserved`) is the least
529                        // of our concerns for now.
530                        (ReservedFrz { conflicted: true } | Active | Frozen, Disabled) => false,
531                        (ReservedFrz { conflicted: true }, Frozen) => false,
532
533                        // `Active`, `Reserved`, and `Cell` have all permissions, so a
534                        // `ChildAccessForbidden(Reserved | Active)` can never exist.
535                        (_, Active) | (_, ReservedFrz { conflicted: false }) | (_, Cell) =>
536                            unreachable!("this permission cannot cause an error"),
537                        // No transition has `Reserved { conflicted: false }` or `ReservedIM`
538                        // as its `.to` unless it's a noop. `Cell` cannot be in its `.to`
539                        // because all child accesses are a noop.
540                        (ReservedFrz { conflicted: false } | ReservedIM | Cell, _) =>
541                            unreachable!("self is a noop transition"),
542                        // All transitions produced in normal executions (using `apply_access`)
543                        // change permissions in the order `Reserved -> Active -> Frozen -> Disabled`.
544                        // We assume that the error was triggered on the same location that
545                        // the transition `self` applies to, so permissions found must be increasing
546                        // in the order `self.from < self.to <= insufficient.inner`
547                        (Active | Frozen | Disabled, ReservedFrz { .. } | ReservedIM)
548                        | (Disabled, Frozen)
549                        | (ReservedFrz { .. }, ReservedIM) =>
550                            unreachable!("permissions between self and err must be increasing"),
551                    }
552                }
553                TransitionError::ProtectedDisabled(before_disabled) => {
554                    // Show how we got to the starting point of the forbidden transition,
555                    // but ignore what came before.
556                    // This eliminates transitions like `Reserved -> Active`
557                    // when the error is a `Frozen -> Disabled`.
558                    match (self.to, before_disabled.inner) {
559                        // We absolutely want to know where it was activated/frozen/marked
560                        // conflicted.
561                        (Active, Active) => true,
562                        (Frozen, Frozen) => true,
563                        (
564                            ReservedFrz { conflicted: true, .. },
565                            ReservedFrz { conflicted: true, .. },
566                        ) => true,
567                        // If the error is a transition `Frozen -> Disabled`, then we don't really
568                        // care whether before that was `Reserved -> Active -> Frozen` or
569                        // `Frozen` directly.
570                        // The error will only show either
571                        // - created as Reserved { conflicted: false },
572                        //   then Reserved { .. } -> Disabled is forbidden
573                        // - created as Reserved { conflicted: false },
574                        //   then Active -> Disabled is forbidden
575                        // A potential `Reserved { conflicted: false }
576                        //   -> Reserved { conflicted: true }` is inexistant or irrelevant,
577                        // and so is the `Reserved { conflicted: false } -> Active`
578                        (Active, Frozen) => false,
579                        (ReservedFrz { conflicted: true }, _) => false,
580
581                        (_, Disabled) =>
582                            unreachable!(
583                                "permission that results in Disabled should not itself be Disabled in the first place"
584                            ),
585                        // No transition has `Reserved { conflicted: false }` or `ReservedIM` as its `.to`
586                        // unless it's a noop. `Cell` cannot be in its `.to` because all child
587                        // accesses are a noop.
588                        (ReservedFrz { conflicted: false } | ReservedIM | Cell, _) =>
589                            unreachable!("self is a noop transition"),
590
591                        // Permissions only evolve in the order `Reserved -> Active -> Frozen -> Disabled`,
592                        // so permissions found must be increasing in the order
593                        // `self.from < self.to <= forbidden.from < forbidden.to`.
594                        (Disabled, Cell | ReservedFrz { .. } | ReservedIM | Active | Frozen)
595                        | (Frozen, Cell | ReservedFrz { .. } | ReservedIM | Active)
596                        | (Active, Cell | ReservedFrz { .. } | ReservedIM) =>
597                            unreachable!("permissions between self and err must be increasing"),
598                    }
599                }
600                // We don't care because protectors evolve independently from
601                // permissions.
602                TransitionError::ProtectedDealloc => false,
603            }
604        }
605
606        /// Endpoint of a transition.
607        /// Meant only for diagnostics, use `applied` in non-diagnostics
608        /// code, which also checks that the starting point matches the current state.
609        pub fn endpoint(&self) -> Permission {
610            Permission { inner: self.to }
611        }
612    }
613}
614
615#[cfg(test)]
616impl Permission {
617    pub fn is_reserved_frz_with_conflicted(&self, expected_conflicted: bool) -> bool {
618        match self.inner {
619            ReservedFrz { conflicted } => conflicted == expected_conflicted,
620            _ => false,
621        }
622    }
623}
624
625#[cfg(test)]
626mod propagation_optimization_checks {
627    pub use super::*;
628    use crate::borrow_tracker::tree_borrows::exhaustive::{Exhaustive, precondition};
629
630    impl Exhaustive for PermissionPriv {
631        fn exhaustive() -> Box<dyn Iterator<Item = Self>> {
632            Box::new(
633                vec![Active, Frozen, Disabled, ReservedIM, Cell]
634                    .into_iter()
635                    .chain(<bool>::exhaustive().map(|conflicted| ReservedFrz { conflicted })),
636            )
637        }
638    }
639
640    impl Exhaustive for Permission {
641        fn exhaustive() -> Box<dyn Iterator<Item = Self>> {
642            Box::new(PermissionPriv::exhaustive().map(|inner| Self { inner }))
643        }
644    }
645
646    impl Exhaustive for AccessKind {
647        fn exhaustive() -> Box<dyn Iterator<Item = Self>> {
648            use AccessKind::*;
649            Box::new(vec![Read, Write].into_iter())
650        }
651    }
652
653    impl Exhaustive for AccessRelatedness {
654        fn exhaustive() -> Box<dyn Iterator<Item = Self>> {
655            use AccessRelatedness::*;
656            Box::new(vec![This, StrictChildAccess, AncestorAccess, CousinAccess].into_iter())
657        }
658    }
659
660    #[test]
661    // For any kind of access, if we do it twice the second should be a no-op.
662    // Even if the protector has disappeared.
663    fn all_transitions_idempotent() {
664        use transition::*;
665        for old in PermissionPriv::exhaustive() {
666            for (old_protected, new_protected) in <(bool, bool)>::exhaustive() {
667                // Protector can't appear out of nowhere: either the permission was
668                // created with a protector (`old_protected = true`) and it then may
669                // or may not lose it (`new_protected = false`, resp. `new_protected = true`),
670                // or it didn't have one upon creation and never will
671                // (`old_protected = new_protected = false`).
672                // We thus eliminate from this test and all other tests
673                // the case where the tag is initially unprotected and later becomes protected.
674                precondition!(old_protected || !new_protected);
675                if old_protected {
676                    precondition!(old.compatible_with_protector());
677                }
678                for (access, rel_pos) in <(AccessKind, AccessRelatedness)>::exhaustive() {
679                    if let Some(new) = perform_access(access, rel_pos, old, old_protected) {
680                        assert_eq!(
681                            new,
682                            perform_access(access, rel_pos, new, new_protected).unwrap()
683                        );
684                    }
685                }
686            }
687        }
688    }
689
690    #[test]
691    #[rustfmt::skip]
692    fn foreign_read_is_noop_after_foreign_write() {
693        use transition::*;
694        let old_access = AccessKind::Write;
695        let new_access = AccessKind::Read;
696        for old in PermissionPriv::exhaustive() {
697            for [old_protected, new_protected] in <[bool; 2]>::exhaustive() {
698                precondition!(old_protected || !new_protected);
699                if old_protected {
700                    precondition!(old.compatible_with_protector());
701                }
702                for rel_pos in AccessRelatedness::exhaustive() {
703                    precondition!(rel_pos.is_foreign());
704                    if let Some(new) = perform_access(old_access, rel_pos, old, old_protected) {
705                        assert_eq!(
706                            new,
707                            perform_access(new_access, rel_pos, new, new_protected).unwrap()
708                        );
709                    }
710                }
711            }
712        }
713    }
714
715    #[test]
716    #[rustfmt::skip]
717    fn permission_sifa_is_correct() {
718        // Tests that `strongest_idempotent_foreign_access` is correct. See `foreign_access_skipping.rs`.
719        for perm in PermissionPriv::exhaustive() {
720            // Assert that adding a protector makes it less idempotent.
721            if perm.compatible_with_protector() {
722                assert!(perm.strongest_idempotent_foreign_access(true) <= perm.strongest_idempotent_foreign_access(false));
723            }
724            for prot in bool::exhaustive() {
725                if prot {
726                    precondition!(perm.compatible_with_protector());
727                }
728                let access = perm.strongest_idempotent_foreign_access(prot);
729                // We now assert it is idempotent, and never causes UB.
730                // First, if the SIFA includes foreign reads, assert it is idempotent under foreign reads.
731                if access >= IdempotentForeignAccess::Read {
732                    // We use `CousinAccess` here. We could also use `AncestorAccess`, since `transition::perform_access` treats these the same.
733                    // The only place they are treated differently is in protector end accesses, but these are not handled here.
734                    assert_eq!(perm, transition::perform_access(AccessKind::Read, AccessRelatedness::CousinAccess, perm, prot).unwrap());
735                }
736                // Then, if the SIFA includes foreign writes, assert it is idempotent under foreign writes.
737                if access >= IdempotentForeignAccess::Write {
738                    assert_eq!(perm, transition::perform_access(AccessKind::Write, AccessRelatedness::CousinAccess, perm, prot).unwrap());
739                }
740            }
741        }
742    }
743
744    #[test]
745    // Check that all transitions are consistent with the order on PermissionPriv,
746    // i.e. Reserved -> Active -> Frozen -> Disabled
747    fn permissionpriv_partialord_is_reachability() {
748        let reach = {
749            let mut reach = rustc_data_structures::fx::FxHashSet::default();
750            // One-step transitions + reflexivity
751            for start in PermissionPriv::exhaustive() {
752                reach.insert((start, start));
753                for (access, rel) in <(AccessKind, AccessRelatedness)>::exhaustive() {
754                    for prot in bool::exhaustive() {
755                        if prot {
756                            precondition!(start.compatible_with_protector());
757                        }
758                        if let Some(end) = transition::perform_access(access, rel, start, prot) {
759                            reach.insert((start, end));
760                        }
761                    }
762                }
763            }
764            // Transitive closure
765            let mut finished = false;
766            while !finished {
767                finished = true;
768                for [start, mid, end] in <[PermissionPriv; 3]>::exhaustive() {
769                    if reach.contains(&(start, mid))
770                        && reach.contains(&(mid, end))
771                        && !reach.contains(&(start, end))
772                    {
773                        finished = false;
774                        reach.insert((start, end));
775                    }
776                }
777            }
778            reach
779        };
780        // Check that it matches `<`
781        for [p1, p2] in <[PermissionPriv; 2]>::exhaustive() {
782            let le12 = p1 <= p2;
783            let reach12 = reach.contains(&(p1, p2));
784            assert!(
785                le12 == reach12,
786                "`{p1} reach {p2}` ({reach12}) does not match `{p1} <= {p2}` ({le12})"
787            );
788        }
789    }
790}