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