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}