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