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 pub fn new_reserved_frz() -> Self {
276 Self { inner: ReservedFrz { conflicted: false } }
277 }
278
279 /// Default initial permission of an unprotected interior mutable reference.
280 pub fn new_reserved_im() -> Self {
281 Self { inner: ReservedIM }
282 }
283
284 /// Default initial permission of a reborrowed shared reference.
285 pub fn new_frozen() -> Self {
286 Self { inner: Frozen }
287 }
288
289 /// Default initial permission of the root of a new tree at out-of-bounds positions.
290 /// Must *only* be used for the root, this is not in general an "initial" permission!
291 pub fn new_disabled() -> Self {
292 Self { inner: Disabled }
293 }
294
295 /// Default initial permission of a shared reference to interior mutable data.
296 pub fn new_cell() -> Self {
297 Self { inner: Cell }
298 }
299
300 /// Reject `ReservedIM` that cannot exist in the presence of a protector.
301 #[cfg(test)]
302 pub fn compatible_with_protector(&self) -> bool {
303 self.inner.compatible_with_protector()
304 }
305
306 /// What kind of access to perform before releasing the protector.
307 pub fn protector_end_access(&self) -> Option<AccessKind> {
308 match self.inner {
309 // Do not do perform access if it is a `Cell`, as this
310 // can cause data races when using thread-safe data types.
311 Cell => None,
312 Active => Some(AccessKind::Write),
313 _ => Some(AccessKind::Read),
314 }
315 }
316
317 /// Apply the transition to the inner PermissionPriv.
318 pub fn perform_access(
319 kind: AccessKind,
320 rel_pos: AccessRelatedness,
321 old_perm: Self,
322 protected: bool,
323 ) -> Option<PermTransition> {
324 let old_state = old_perm.inner;
325 transition::perform_access(kind, rel_pos, old_state, protected)
326 .map(|new_state| PermTransition { from: old_state, to: new_state })
327 }
328
329 /// During a provenance GC, we want to compact the tree.
330 /// For this, we want to merge nodes upwards if they have a singleton parent.
331 /// But we need to be careful: If the parent is Frozen, and the child is Reserved,
332 /// we can not do such a merge. In general, such a merge is possible if the parent
333 /// allows similar accesses, and in particular if the parent never causes UB on its
334 /// own. This is enforced by a test, namely `tree_compacting_is_sound`. See that
335 /// test for more information.
336 /// This method is only sound if the parent is not protected. We never attempt to
337 /// remove protected parents.
338 pub fn can_be_replaced_by_child(self, child: Self) -> bool {
339 match (self.inner, child.inner) {
340 // Cell allows all transitions.
341 (Cell, _) => true,
342 // Cell is the most permissive, nothing can be replaced by Cell.
343 // (ReservedIM, Cell) => true,
344 (_, Cell) => false,
345 // ReservedIM can be replaced by anything besides Cell.
346 // ReservedIM allows all transitions, but unlike Cell, a local write
347 // to ReservedIM transitions to Active, while it is a no-op for Cell.
348 (ReservedIM, _) => true,
349 (_, ReservedIM) => false,
350 // Reserved (as parent, where conflictedness does not matter)
351 // can be replaced by all but ReservedIM and Cell,
352 // since ReservedIM and Cell alone would survive foreign writes
353 (ReservedFrz { .. }, _) => true,
354 (_, ReservedFrz { .. }) => false,
355 // Active can not be replaced by something surviving
356 // foreign reads and then remaining writable (i.e., Reserved*).
357 // Replacing a state by itself is always okay, even if the child state is protected.
358 // Active can be replaced by Frozen, since it is not protected.
359 (Active, Active | Frozen | Disabled) => true,
360 (_, Active) => false,
361 // Frozen can only be replaced by Disabled (and itself).
362 (Frozen, Frozen | Disabled) => true,
363 (_, Frozen) => false,
364 // Disabled can not be replaced by anything else.
365 (Disabled, Disabled) => true,
366 }
367 }
368
369 /// Returns the strongest foreign action this node survives (without change),
370 /// where `prot` indicates if it is protected.
371 /// See `foreign_access_skipping`
372 pub fn strongest_idempotent_foreign_access(&self, prot: bool) -> IdempotentForeignAccess {
373 self.inner.strongest_idempotent_foreign_access(prot)
374 }
375}
376
377impl PermTransition {
378 /// All transitions created through normal means (using `perform_access`)
379 /// should be possible, but the same is not guaranteed by construction of
380 /// transitions inferred by diagnostics. This checks that a transition
381 /// reconstructed by diagnostics is indeed one that could happen.
382 fn is_possible(self) -> bool {
383 self.from <= self.to
384 }
385
386 pub fn is_noop(self) -> bool {
387 self.from == self.to
388 }
389
390 /// Extract result of a transition (checks that the starting point matches).
391 pub fn applied(self, starting_point: Permission) -> Option<Permission> {
392 (starting_point.inner == self.from).then_some(Permission { inner: self.to })
393 }
394
395 /// Determines if this transition would disable the permission.
396 pub fn produces_disabled(self) -> bool {
397 self.to == Disabled
398 }
399}
400
401pub mod diagnostics {
402 use super::*;
403 impl fmt::Display for PermissionPriv {
404 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
405 write!(
406 f,
407 "{}",
408 match self {
409 Cell => "Cell",
410 ReservedFrz { conflicted: false } => "Reserved",
411 ReservedFrz { conflicted: true } => "Reserved (conflicted)",
412 ReservedIM => "Reserved (interior mutable)",
413 Active => "Active",
414 Frozen => "Frozen",
415 Disabled => "Disabled",
416 }
417 )
418 }
419 }
420
421 impl fmt::Display for PermTransition {
422 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
423 write!(f, "from {} to {}", self.from, self.to)
424 }
425 }
426
427 impl fmt::Display for Permission {
428 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
429 write!(f, "{}", self.inner)
430 }
431 }
432
433 impl Permission {
434 /// Abbreviated name of the permission (uniformly 3 letters for nice alignment).
435 pub fn short_name(self) -> &'static str {
436 // Make sure there are all of the same length as each other
437 // and also as `diagnostics::DisplayFmtPermission.uninit` otherwise
438 // alignment will be incorrect.
439 match self.inner {
440 Cell => "Cel ",
441 ReservedFrz { conflicted: false } => "Res ",
442 ReservedFrz { conflicted: true } => "ResC",
443 ReservedIM => "ReIM",
444 Active => "Act ",
445 Frozen => "Frz ",
446 Disabled => "Dis ",
447 }
448 }
449 }
450
451 impl PermTransition {
452 /// Readable explanation of the consequences of an event.
453 /// Fits in the sentence "This transition corresponds to {trans.summary()}".
454 pub fn summary(&self) -> &'static str {
455 assert!(self.is_possible());
456 assert!(!self.is_noop());
457 match (self.from, self.to) {
458 (_, Active) => "the first write to a 2-phase borrowed mutable reference",
459 (_, Frozen) => "a loss of write permissions",
460 (ReservedFrz { conflicted: false }, ReservedFrz { conflicted: true }) =>
461 "a temporary loss of write permissions until function exit",
462 (Frozen, Disabled) => "a loss of read permissions",
463 (_, Disabled) => "a loss of read and write permissions",
464 (old, new) =>
465 unreachable!("Transition from {old:?} to {new:?} should never be possible"),
466 }
467 }
468
469 /// Determines whether `self` is a relevant transition for the error `err`.
470 /// `self` will be a transition that happened to a tag some time before
471 /// that tag caused the error.
472 ///
473 /// Irrelevant events:
474 /// - modifications of write permissions when the error is related to read permissions
475 /// (on failed reads and protected `Frozen -> Disabled`, ignore `Reserved -> Active`,
476 /// `Reserved(conflicted=false) -> Reserved(conflicted=true)`, and `Active -> Frozen`)
477 /// - all transitions for attempts to deallocate strongly protected tags
478 ///
479 /// # Panics
480 ///
481 /// This function assumes that its arguments apply to the same location
482 /// and that they were obtained during a normal execution. It will panic otherwise.
483 /// - all transitions involved in `self` and `err` should be increasing
484 /// (Reserved < Active < Frozen < Disabled);
485 /// - between `self` and `err` the permission should also be increasing,
486 /// so all permissions inside `err` should be greater than `self.1`;
487 /// - `Active`, `Reserved(conflicted=false)`, and `Cell` cannot cause an error
488 /// due to insufficient permissions, so `err` cannot be a `ChildAccessForbidden(_)`
489 /// of either of them;
490 /// - `err` should not be `ProtectedDisabled(Disabled)`, because the protected
491 /// tag should not have been `Disabled` in the first place (if this occurs it means
492 /// we have unprotected tags that become protected)
493 pub(in super::super) fn is_relevant(&self, err: TransitionError) -> bool {
494 // NOTE: `super::super` is the visibility of `TransitionError`
495 assert!(self.is_possible());
496 if self.is_noop() {
497 return false;
498 }
499 match err {
500 TransitionError::ChildAccessForbidden(insufficient) => {
501 // Show where the permission was gained then lost,
502 // but ignore unrelated permissions.
503 // This eliminates transitions like `Active -> Frozen`
504 // when the error is a failed `Read`.
505 match (self.to, insufficient.inner) {
506 (Frozen, Frozen) => true,
507 (Active, Frozen) => true,
508 (Disabled, Disabled) => true,
509 (
510 ReservedFrz { conflicted: true, .. },
511 ReservedFrz { conflicted: true, .. },
512 ) => true,
513 // A pointer being `Disabled` is a strictly stronger source of
514 // errors than it being `Frozen`. If we try to access a `Disabled`,
515 // then where it became `Frozen` (or `Active` or `Reserved`) is the least
516 // of our concerns for now.
517 (ReservedFrz { conflicted: true } | Active | Frozen, Disabled) => false,
518 (ReservedFrz { conflicted: true }, Frozen) => false,
519
520 // `Active`, `Reserved`, and `Cell` have all permissions, so a
521 // `ChildAccessForbidden(Reserved | Active)` can never exist.
522 (_, Active) | (_, ReservedFrz { conflicted: false }) | (_, Cell) =>
523 unreachable!("this permission cannot cause an error"),
524 // No transition has `Reserved { conflicted: false }` or `ReservedIM`
525 // as its `.to` unless it's a noop. `Cell` cannot be in its `.to`
526 // because all child accesses are a noop.
527 (ReservedFrz { conflicted: false } | ReservedIM | Cell, _) =>
528 unreachable!("self is a noop transition"),
529 // All transitions produced in normal executions (using `apply_access`)
530 // change permissions in the order `Reserved -> Active -> Frozen -> Disabled`.
531 // We assume that the error was triggered on the same location that
532 // the transition `self` applies to, so permissions found must be increasing
533 // in the order `self.from < self.to <= insufficient.inner`
534 (Active | Frozen | Disabled, ReservedFrz { .. } | ReservedIM)
535 | (Disabled, Frozen)
536 | (ReservedFrz { .. }, ReservedIM) =>
537 unreachable!("permissions between self and err must be increasing"),
538 }
539 }
540 TransitionError::ProtectedDisabled(before_disabled) => {
541 // Show how we got to the starting point of the forbidden transition,
542 // but ignore what came before.
543 // This eliminates transitions like `Reserved -> Active`
544 // when the error is a `Frozen -> Disabled`.
545 match (self.to, before_disabled.inner) {
546 // We absolutely want to know where it was activated/frozen/marked
547 // conflicted.
548 (Active, Active) => true,
549 (Frozen, Frozen) => true,
550 (
551 ReservedFrz { conflicted: true, .. },
552 ReservedFrz { conflicted: true, .. },
553 ) => true,
554 // If the error is a transition `Frozen -> Disabled`, then we don't really
555 // care whether before that was `Reserved -> Active -> Frozen` or
556 // `Frozen` directly.
557 // The error will only show either
558 // - created as Reserved { conflicted: false },
559 // then Reserved { .. } -> Disabled is forbidden
560 // - created as Reserved { conflicted: false },
561 // then Active -> Disabled is forbidden
562 // A potential `Reserved { conflicted: false }
563 // -> Reserved { conflicted: true }` is inexistant or irrelevant,
564 // and so is the `Reserved { conflicted: false } -> Active`
565 (Active, Frozen) => false,
566 (ReservedFrz { conflicted: true }, _) => false,
567
568 (_, Disabled) =>
569 unreachable!(
570 "permission that results in Disabled should not itself be Disabled in the first place"
571 ),
572 // No transition has `Reserved { conflicted: false }` or `ReservedIM` as its `.to`
573 // unless it's a noop. `Cell` cannot be in its `.to` because all child
574 // accesses are a noop.
575 (ReservedFrz { conflicted: false } | ReservedIM | Cell, _) =>
576 unreachable!("self is a noop transition"),
577
578 // Permissions only evolve in the order `Reserved -> Active -> Frozen -> Disabled`,
579 // so permissions found must be increasing in the order
580 // `self.from < self.to <= forbidden.from < forbidden.to`.
581 (Disabled, Cell | ReservedFrz { .. } | ReservedIM | Active | Frozen)
582 | (Frozen, Cell | ReservedFrz { .. } | ReservedIM | Active)
583 | (Active, Cell | ReservedFrz { .. } | ReservedIM) =>
584 unreachable!("permissions between self and err must be increasing"),
585 }
586 }
587 // We don't care because protectors evolve independently from
588 // permissions.
589 TransitionError::ProtectedDealloc => false,
590 }
591 }
592
593 /// Endpoint of a transition.
594 /// Meant only for diagnostics, use `applied` in non-diagnostics
595 /// code, which also checks that the starting point matches the current state.
596 pub fn endpoint(&self) -> Permission {
597 Permission { inner: self.to }
598 }
599 }
600}
601
602#[cfg(test)]
603impl Permission {
604 pub fn is_reserved_frz_with_conflicted(&self, expected_conflicted: bool) -> bool {
605 match self.inner {
606 ReservedFrz { conflicted } => conflicted == expected_conflicted,
607 _ => false,
608 }
609 }
610}
611
612#[cfg(test)]
613mod propagation_optimization_checks {
614 pub use super::*;
615 use crate::borrow_tracker::tree_borrows::exhaustive::{Exhaustive, precondition};
616
617 impl Exhaustive for PermissionPriv {
618 fn exhaustive() -> Box<dyn Iterator<Item = Self>> {
619 Box::new(
620 vec![Active, Frozen, Disabled, ReservedIM, Cell]
621 .into_iter()
622 .chain(<bool>::exhaustive().map(|conflicted| ReservedFrz { conflicted })),
623 )
624 }
625 }
626
627 impl Exhaustive for Permission {
628 fn exhaustive() -> Box<dyn Iterator<Item = Self>> {
629 Box::new(PermissionPriv::exhaustive().map(|inner| Self { inner }))
630 }
631 }
632
633 impl Exhaustive for AccessKind {
634 fn exhaustive() -> Box<dyn Iterator<Item = Self>> {
635 use AccessKind::*;
636 Box::new(vec![Read, Write].into_iter())
637 }
638 }
639
640 impl Exhaustive for AccessRelatedness {
641 fn exhaustive() -> Box<dyn Iterator<Item = Self>> {
642 use AccessRelatedness::*;
643 Box::new(vec![This, StrictChildAccess, AncestorAccess, CousinAccess].into_iter())
644 }
645 }
646
647 #[test]
648 // For any kind of access, if we do it twice the second should be a no-op.
649 // Even if the protector has disappeared.
650 fn all_transitions_idempotent() {
651 use transition::*;
652 for old in PermissionPriv::exhaustive() {
653 for (old_protected, new_protected) in <(bool, bool)>::exhaustive() {
654 // Protector can't appear out of nowhere: either the permission was
655 // created with a protector (`old_protected = true`) and it then may
656 // or may not lose it (`new_protected = false`, resp. `new_protected = true`),
657 // or it didn't have one upon creation and never will
658 // (`old_protected = new_protected = false`).
659 // We thus eliminate from this test and all other tests
660 // the case where the tag is initially unprotected and later becomes protected.
661 precondition!(old_protected || !new_protected);
662 if old_protected {
663 precondition!(old.compatible_with_protector());
664 }
665 for (access, rel_pos) in <(AccessKind, AccessRelatedness)>::exhaustive() {
666 if let Some(new) = perform_access(access, rel_pos, old, old_protected) {
667 assert_eq!(
668 new,
669 perform_access(access, rel_pos, new, new_protected).unwrap()
670 );
671 }
672 }
673 }
674 }
675 }
676
677 #[test]
678 #[rustfmt::skip]
679 fn foreign_read_is_noop_after_foreign_write() {
680 use transition::*;
681 let old_access = AccessKind::Write;
682 let new_access = AccessKind::Read;
683 for old in PermissionPriv::exhaustive() {
684 for [old_protected, new_protected] in <[bool; 2]>::exhaustive() {
685 precondition!(old_protected || !new_protected);
686 if old_protected {
687 precondition!(old.compatible_with_protector());
688 }
689 for rel_pos in AccessRelatedness::exhaustive() {
690 precondition!(rel_pos.is_foreign());
691 if let Some(new) = perform_access(old_access, rel_pos, old, old_protected) {
692 assert_eq!(
693 new,
694 perform_access(new_access, rel_pos, new, new_protected).unwrap()
695 );
696 }
697 }
698 }
699 }
700 }
701
702 #[test]
703 #[rustfmt::skip]
704 fn permission_sifa_is_correct() {
705 // Tests that `strongest_idempotent_foreign_access` is correct. See `foreign_access_skipping.rs`.
706 for perm in PermissionPriv::exhaustive() {
707 // Assert that adding a protector makes it less idempotent.
708 if perm.compatible_with_protector() {
709 assert!(perm.strongest_idempotent_foreign_access(true) <= perm.strongest_idempotent_foreign_access(false));
710 }
711 for prot in bool::exhaustive() {
712 if prot {
713 precondition!(perm.compatible_with_protector());
714 }
715 let access = perm.strongest_idempotent_foreign_access(prot);
716 // We now assert it is idempotent, and never causes UB.
717 // First, if the SIFA includes foreign reads, assert it is idempotent under foreign reads.
718 if access >= IdempotentForeignAccess::Read {
719 // We use `CousinAccess` here. We could also use `AncestorAccess`, since `transition::perform_access` treats these the same.
720 // The only place they are treated differently is in protector end accesses, but these are not handled here.
721 assert_eq!(perm, transition::perform_access(AccessKind::Read, AccessRelatedness::CousinAccess, perm, prot).unwrap());
722 }
723 // Then, if the SIFA includes foreign writes, assert it is idempotent under foreign writes.
724 if access >= IdempotentForeignAccess::Write {
725 assert_eq!(perm, transition::perform_access(AccessKind::Write, AccessRelatedness::CousinAccess, perm, prot).unwrap());
726 }
727 }
728 }
729 }
730
731 #[test]
732 // Check that all transitions are consistent with the order on PermissionPriv,
733 // i.e. Reserved -> Active -> Frozen -> Disabled
734 fn permissionpriv_partialord_is_reachability() {
735 let reach = {
736 let mut reach = rustc_data_structures::fx::FxHashSet::default();
737 // One-step transitions + reflexivity
738 for start in PermissionPriv::exhaustive() {
739 reach.insert((start, start));
740 for (access, rel) in <(AccessKind, AccessRelatedness)>::exhaustive() {
741 for prot in bool::exhaustive() {
742 if prot {
743 precondition!(start.compatible_with_protector());
744 }
745 if let Some(end) = transition::perform_access(access, rel, start, prot) {
746 reach.insert((start, end));
747 }
748 }
749 }
750 }
751 // Transitive closure
752 let mut finished = false;
753 while !finished {
754 finished = true;
755 for [start, mid, end] in <[PermissionPriv; 3]>::exhaustive() {
756 if reach.contains(&(start, mid))
757 && reach.contains(&(mid, end))
758 && !reach.contains(&(start, end))
759 {
760 finished = false;
761 reach.insert((start, end));
762 }
763 }
764 }
765 reach
766 };
767 // Check that it matches `<`
768 for [p1, p2] in <[PermissionPriv; 2]>::exhaustive() {
769 let le12 = p1 <= p2;
770 let reach12 = reach.contains(&(p1, p2));
771 assert!(
772 le12 == reach12,
773 "`{p1} reach {p2}` ({reach12}) does not match `{p1} <= {p2}` ({le12})"
774 );
775 }
776 }
777}