more precise filtering of events

impl of is_relevant on transitions makes for much less noise in error messages

Co-authored-by: Ralf Jung <post@ralfj.de>

8 files changed, 160 insertions, 66 deletions

diff --git a/src/tools/miri/src/borrow_tracker/tree_borrows/diagnostics.rs b/src/tools/miri/src/borrow_tracker/tree_borrows/diagnostics.rs
index 10873c46a6c..cea2cffa913 100644
--- a/src/tools/miri/src/borrow_tracker/tree_borrows/diagnostics.rs
+++ b/src/tools/miri/src/borrow_tracker/tree_borrows/diagnostics.rs
@@ -92,7 +92,7 @@ impl HistoryData {
         {
             // NOTE: `transition_range` is explicitly absent from the error message, it has no significance
             // to the user. The meaningful one is `access_range`.
-            self.events.push((Some(span.data()), format!("{this} then transitioned {transition} due to a {rel} {access_kind} at offsets {access_range:?}", rel = if is_foreign { "foreign" } else { "child" })));
+            self.events.push((Some(span.data()), format!("{this} later transitioned to {endpoint} due to a {rel} {access_kind} at offsets {access_range:?}", endpoint = transition.endpoint(), rel = if is_foreign { "foreign" } else { "child" })));
             self.events.push((None, format!("this corresponds to {}", transition.summary())));
         }
     }
@@ -212,12 +212,13 @@ impl History {
 
     /// Reconstruct the history relevant to `error_offset` by filtering
     /// only events whose range contains the offset we are interested in.
-    fn extract_relevant(&self, error_offset: u64) -> Self {
+    fn extract_relevant(&self, error_offset: u64, error_kind: TransitionError) -> Self {
         History {
             events: self
                 .events
                 .iter()
                 .filter(|e| e.transition_range.contains(&error_offset))
+                .filter(|e| e.transition.is_relevant(error_kind))
                 .cloned()
                 .collect::<Vec<_>>(),
             created: self.created,
@@ -303,7 +304,7 @@ impl TbError<'_> {
             history.extend(self.accessed_info.history.forget(), "accessed", false);
         }
         history.extend(
-            self.conflicting_info.history.extract_relevant(self.error_offset),
+            self.conflicting_info.history.extract_relevant(self.error_offset, self.error_kind),
             conflicting_tag_name,
             true,
         );
diff --git a/src/tools/miri/src/borrow_tracker/tree_borrows/perms.rs b/src/tools/miri/src/borrow_tracker/tree_borrows/perms.rs
index 7e3e587db72..6b1e722b65e 100644
--- a/src/tools/miri/src/borrow_tracker/tree_borrows/perms.rs
+++ b/src/tools/miri/src/borrow_tracker/tree_borrows/perms.rs
@@ -1,6 +1,7 @@
 use std::cmp::{Ordering, PartialOrd};
 use std::fmt;
 
+use crate::borrow_tracker::tree_borrows::diagnostics::TransitionError;
 use crate::borrow_tracker::tree_borrows::tree::AccessRelatedness;
 use crate::borrow_tracker::AccessKind;
 
@@ -115,26 +116,31 @@ mod transition {
 /// Public interface to the state machine that controls read-write permissions.
 /// This is the "private `enum`" pattern.
 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
-pub struct Permission(PermissionPriv);
+pub struct Permission {
+    inner: PermissionPriv,
+}
 
 /// Transition from one permission to the next.
 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
-pub struct PermTransition(PermissionPriv, PermissionPriv);
+pub struct PermTransition {
+    from: PermissionPriv,
+    to: PermissionPriv,
+}
 
 impl Permission {
     /// Default initial permission of the root of a new tree.
     pub fn new_root() -> Self {
-        Self(Active)
+        Self { inner: Active }
     }
 
     /// Default initial permission of a reborrowed mutable reference.
     pub fn new_unique_2phase(ty_is_freeze: bool) -> Self {
-        Self(Reserved { ty_is_freeze })
+        Self { inner: Reserved { ty_is_freeze } }
     }
 
     /// Default initial permission of a reborrowed shared reference
     pub fn new_frozen() -> Self {
-        Self(Frozen)
+        Self { inner: Frozen }
     }
 
     /// Apply the transition to the inner PermissionPriv.
@@ -144,9 +150,9 @@ impl Permission {
         old_perm: Self,
         protected: bool,
     ) -> Option<PermTransition> {
-        let old_state = old_perm.0;
+        let old_state = old_perm.inner;
         transition::perform_access(kind, rel_pos, old_state, protected)
-            .map(|new_state| PermTransition(old_state, new_state))
+            .map(|new_state| PermTransition { from: old_state, to: new_state })
     }
 }
 
@@ -155,26 +161,27 @@ impl PermTransition {
     /// should be possible, but the same is not guaranteed by construction of
     /// transitions inferred by diagnostics. This checks that a transition
     /// reconstructed by diagnostics is indeed one that could happen.
-    fn is_possible(old: PermissionPriv, new: PermissionPriv) -> bool {
-        old <= new
+    fn is_possible(self) -> bool {
+        self.from <= self.to
     }
 
-    pub fn from(old: Permission, new: Permission) -> Option<Self> {
-        Self::is_possible(old.0, new.0).then_some(Self(old.0, new.0))
+    pub fn from(from: Permission, to: Permission) -> Option<Self> {
+        let t = Self { from: from.inner, to: to.inner };
+        t.is_possible().then_some(t)
     }
 
     pub fn is_noop(self) -> bool {
-        self.0 == self.1
+        self.from == self.to
     }
 
     /// Extract result of a transition (checks that the starting point matches).
     pub fn applied(self, starting_point: Permission) -> Option<Permission> {
-        (starting_point.0 == self.0).then_some(Permission(self.1))
+        (starting_point.inner == self.from).then_some(Permission { inner: self.to })
     }
 
     /// Extract starting point of a transition
     pub fn started(self) -> Permission {
-        Permission(self.0)
+        Permission { inner: self.from }
     }
 
     /// Determines whether a transition that occured is compatible with the presence
@@ -190,10 +197,9 @@ impl PermTransition {
     /// };
     /// ```
     pub fn is_allowed_by_protector(&self) -> bool {
-        let &Self(old, new) = self;
-        assert!(Self::is_possible(old, new));
-        match (old, new) {
-            _ if old == new => true,
+        assert!(self.is_possible());
+        match (self.from, self.to) {
+            _ if self.from == self.to => true,
             // It is always a protector violation to not be readable anymore
             (_, Disabled) => false,
             // In the case of a `Reserved` under a protector, both transitions
@@ -204,16 +210,9 @@ impl PermTransition {
             (Reserved { .. }, Active) | (Reserved { .. }, Frozen) => true,
             // This pointer should have stayed writeable for the whole function
             (Active, Frozen) => false,
-            _ => unreachable!("Transition from {old:?} to {new:?} should never be possible"),
+            _ => unreachable!("Transition {} should never be possible", self),
         }
     }
-
-    /// Composition function: get the transition that can be added after `app` to
-    /// produce `self`.
-    pub fn apply_start(self, app: Self) -> Option<Self> {
-        let new_start = app.applied(Permission(self.0))?;
-        Self::from(new_start, Permission(self.1))
-    }
 }
 
 pub mod diagnostics {
@@ -224,10 +223,10 @@ pub mod diagnostics {
                 f,
                 "{}",
                 match self {
-                    PermissionPriv::Reserved { .. } => "Reserved",
-                    PermissionPriv::Active => "Active",
-                    PermissionPriv::Frozen => "Frozen",
-                    PermissionPriv::Disabled => "Disabled",
+                    Reserved { .. } => "Reserved",
+                    Active => "Active",
+                    Frozen => "Frozen",
+                    Disabled => "Disabled",
                 }
             )
         }
@@ -235,13 +234,13 @@ pub mod diagnostics {
 
     impl fmt::Display for PermTransition {
         fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-            write!(f, "from {} to {}", self.0, self.1)
+            write!(f, "from {} to {}", self.from, self.to)
         }
     }
 
     impl fmt::Display for Permission {
         fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
-            write!(f, "{}", self.0)
+            write!(f, "{}", self.inner)
         }
     }
 
@@ -251,7 +250,7 @@ pub mod diagnostics {
             // Make sure there are all of the same length as each other
             // and also as `diagnostics::DisplayFmtPermission.uninit` otherwise
             // alignment will be incorrect.
-            match self.0 {
+            match self.inner {
                 Reserved { ty_is_freeze: true } => "Res",
                 Reserved { ty_is_freeze: false } => "Re*",
                 Active => "Act",
@@ -269,9 +268,9 @@ pub mod diagnostics {
         /// to have write permissions, because that's what the diagnostics care about
         /// (otherwise `Reserved -> Frozen` would be considered a noop).
         pub fn summary(&self) -> &'static str {
-            assert!(Self::is_possible(self.0, self.1));
-            match (self.0, self.1) {
-                (_, Active) => "an activation",
+            assert!(self.is_possible());
+            match (self.from, self.to) {
+                (_, Active) => "the first write to a 2-phase borrowed mutable reference",
                 (_, Frozen) => "a loss of write permissions",
                 (Frozen, Disabled) => "a loss of read permissions",
                 (_, Disabled) => "a loss of read and write permissions",
@@ -279,6 +278,118 @@ pub mod diagnostics {
                     unreachable!("Transition from {old:?} to {new:?} should never be possible"),
             }
         }
+
+        /// Determines whether `self` is a relevant transition for the error `err`.
+        /// `self` will be a transition that happened to a tag some time before
+        /// that tag caused the error.
+        ///
+        /// Irrelevant events:
+        /// - modifications of write permissions when the error is related to read permissions
+        ///   (on failed reads and protected `Frozen -> Disabled`, ignore `Reserved -> Active`,
+        ///   `Reserved -> Frozen`, and `Active -> Frozen`)
+        /// - all transitions for attempts to deallocate strongly protected tags
+        ///
+        /// # Panics
+        ///
+        /// This function assumes that its arguments apply to the same location
+        /// and that they were obtained during a normal execution. It will panic otherwise.
+        /// - `err` cannot be a `ProtectedTransition(_)` of a noop transition, as those
+        /// never trigger protectors;
+        /// - all transitions involved in `self` and `err` should be increasing
+        /// (Reserved < Active < Frozen < Disabled);
+        /// - between `self` and `err` the permission should also be increasing,
+        /// so all permissions inside `err` should be greater than `self.1`;
+        /// - `Active` and `Reserved` cannot cause an error due to insufficient permissions,
+        /// so `err` cannot be a `ChildAccessForbidden(_)` of either of them;
+        pub(in super::super) fn is_relevant(&self, err: TransitionError) -> bool {
+            // NOTE: `super::super` is the visibility of `TransitionError`
+            assert!(self.is_possible());
+            if self.is_noop() {
+                return false;
+            }
+            match err {
+                TransitionError::ChildAccessForbidden(insufficient) => {
+                    // Show where the permission was gained then lost,
+                    // but ignore unrelated permissions.
+                    // This eliminates transitions like `Active -> Frozen`
+                    // when the error is a failed `Read`.
+                    match (self.to, insufficient.inner) {
+                        (Frozen, Frozen) => true,
+                        (Active, Frozen) => true,
+                        (Disabled, Disabled) => true,
+                        // A pointer being `Disabled` is a strictly stronger source of
+                        // errors than it being `Frozen`. If we try to access a `Disabled`,
+                        // then where it became `Frozen` (or `Active`) is the least of our concerns for now.
+                        (Active | Frozen, Disabled) => false,
+
+                        // `Active` and `Reserved` have all permissions, so a
+                        // `ChildAccessForbidden(Reserved | Active)` can never exist.
+                        (_, Active) | (_, Reserved { .. }) =>
+                            unreachable!("this permission cannot cause an error"),
+                        // No transition has `Reserved` as its `.to` unless it's a noop.
+                        (Reserved { .. }, _) => unreachable!("self is a noop transition"),
+                        // All transitions produced in normal executions (using `apply_access`)
+                        // change permissions in the order `Reserved -> Active -> Frozen -> Disabled`.
+                        // We assume that the error was triggered on the same location that
+                        // the transition `self` applies to, so permissions found must be increasing
+                        // in the order `self.from < self.to <= insufficient.inner`
+                        (Disabled, Frozen) =>
+                            unreachable!("permissions between self and err must be increasing"),
+                    }
+                }
+                TransitionError::ProtectedTransition(forbidden) => {
+                    assert!(!forbidden.is_noop());
+                    // Show how we got to the starting point of the forbidden transition,
+                    // but ignore what came before.
+                    // This eliminates transitions like `Reserved -> Active`
+                    // when the error is a `Frozen -> Disabled`.
+                    match (self.to, forbidden.from, forbidden.to) {
+                        // We absolutely want to know where it was activated.
+                        (Active, Active, Frozen | Disabled) => true,
+                        // And knowing where it became Frozen is also important.
+                        (Frozen, Frozen, Disabled) => true,
+                        // If the error is a transition `Frozen -> Disabled`, then we don't really
+                        // care whether before that was `Reserved -> Active -> Frozen` or
+                        // `Reserved -> Frozen` or even `Frozen` directly.
+                        // The error will only show either
+                        // - created as Frozen, then Frozen -> Disabled is forbidden
+                        // - created as Reserved, later became Frozen, then Frozen -> Disabled is forbidden
+                        // In both cases the `Reserved -> Active` part is inexistant or irrelevant.
+                        (Active, Frozen, Disabled) => false,
+
+                        // `Reserved -> Frozen` does not trigger protectors.
+                        (_, Reserved { .. }, Frozen) =>
+                            unreachable!("this transition cannot cause an error"),
+                        // No transition has `Reserved` as its `.to` unless it's a noop.
+                        (Reserved { .. }, _, _) => unreachable!("self is a noop transition"),
+                        (_, Disabled, Disabled) | (_, Frozen, Frozen) | (_, Active, Active) =>
+                            unreachable!("err contains a noop transition"),
+
+                        // Permissions only evolve in the order `Reserved -> Active -> Frozen -> Disabled`,
+                        // so permissions found must be increasing in the order
+                        // `self.from < self.to <= forbidden.from < forbidden.to`.
+                        (Disabled, Reserved { .. } | Active | Frozen, _)
+                        | (Frozen, Reserved { .. } | Active, _)
+                        | (Active, Reserved { .. }, _) =>
+                            unreachable!("permissions between self and err must be increasing"),
+                        (_, Disabled, Reserved { .. } | Active | Frozen)
+                        | (_, Frozen, Reserved { .. } | Active)
+                        | (_, Active, Reserved { .. }) =>
+                            unreachable!("permissions within err must be increasing"),
+                    }
+                }
+                // We don't care because protectors evolve independently from
+                // permissions.
+                TransitionError::ProtectedDealloc => false,
+            }
+        }
+
+        /// Endpoint of a transition.
+        /// Meant only for diagnostics, use `applied` in non-diagnostics
+        /// code, which also checks that the starting point matches the current state.
+        pub fn endpoint(&self) -> Permission {
+            Permission { inner: self.to }
+        }
     }
 }
 
diff --git a/src/tools/miri/tests/fail/tree-borrows/alternate-read-write.stderr b/src/tools/miri/tests/fail/tree-borrows/alternate-read-write.stderr
index bb601fc8835..d82cb8288a3 100644
--- a/src/tools/miri/tests/fail/tree-borrows/alternate-read-write.stderr
+++ b/src/tools/miri/tests/fail/tree-borrows/alternate-read-write.stderr
@@ -17,13 +17,13 @@ help: the conflicting tag <TAG> was created here, in the initial state Reserved
    |
 LL |     let y = unsafe { &mut *(x as *mut u8) };
    |                      ^^^^^^^^^^^^^^^^^^^^
-help: the conflicting tag <TAG> then transitioned from Reserved to Active due to a child write access at offsets [0x0..0x1]
+help: the conflicting tag <TAG> later transitioned to Active due to a child write access at offsets [0x0..0x1]
   --> $DIR/alternate-read-write.rs:LL:CC
    |
 LL |     *y += 1; // Success
    |     ^^^^^^^
-   = help: this corresponds to an activation
-help: the conflicting tag <TAG> then transitioned from Active to Frozen due to a foreign read access at offsets [0x0..0x1]
+   = help: this corresponds to the first write to a 2-phase borrowed mutable reference
+help: the conflicting tag <TAG> later transitioned to Frozen due to a foreign read access at offsets [0x0..0x1]
   --> $DIR/alternate-read-write.rs:LL:CC
    |
 LL |     let _val = *x;
diff --git a/src/tools/miri/tests/fail/tree-borrows/error-range.stderr b/src/tools/miri/tests/fail/tree-borrows/error-range.stderr
index bc829fd86d3..10c2e95ca2f 100644
--- a/src/tools/miri/tests/fail/tree-borrows/error-range.stderr
+++ b/src/tools/miri/tests/fail/tree-borrows/error-range.stderr
@@ -17,19 +17,7 @@ help: the conflicting tag <TAG> was created here, in the initial state Reserved
    |
 LL |         let rmut = &mut *addr_of_mut!(data[0..6]);
    |                                       ^^^^
-help: the conflicting tag <TAG> then transitioned from Reserved to Active due to a child write access at offsets [0x5..0x6]
-  --> $DIR/error-range.rs:LL:CC
-   |
-LL |         rmut[5] += 1;
-   |         ^^^^^^^^^^^^
-   = help: this corresponds to an activation
-help: the conflicting tag <TAG> then transitioned from Active to Frozen due to a foreign read access at offsets [0x5..0x6]
-  --> $DIR/error-range.rs:LL:CC
-   |
-LL |         let _v = data[5];
-   |                  ^^^^^^^
-   = help: this corresponds to a loss of write permissions
-help: the conflicting tag <TAG> then transitioned from Frozen to Disabled due to a foreign write access at offsets [0x5..0x6]
+help: the conflicting tag <TAG> later transitioned to Disabled due to a foreign write access at offsets [0x5..0x6]
   --> $DIR/error-range.rs:LL:CC
    |
 LL |         data[5] = 1;
diff --git a/src/tools/miri/tests/fail/tree-borrows/fragile-data-race.stderr b/src/tools/miri/tests/fail/tree-borrows/fragile-data-race.stderr
index 79744964a8b..86fdf97ac41 100644
--- a/src/tools/miri/tests/fail/tree-borrows/fragile-data-race.stderr
+++ b/src/tools/miri/tests/fail/tree-borrows/fragile-data-race.stderr
@@ -17,7 +17,7 @@ help: the conflicting tag <TAG> was created here, in the initial state Reserved
    |
 LL | pub fn catch_unwind<F: FnOnce() -> R + UnwindSafe, R>(f: F) -> Result<R> {
    |                                                       ^
-help: the conflicting tag <TAG> then transitioned from Reserved to Frozen due to a foreign read access at offsets [0x0..0x1]
+help: the conflicting tag <TAG> later transitioned to Frozen due to a foreign read access at offsets [0x0..0x1]
   --> RUSTLIB/core/src/ptr/mod.rs:LL:CC
    |
 LL |         crate::intrinsics::read_via_copy(src)
diff --git a/src/tools/miri/tests/fail/tree-borrows/read-to-local.stderr b/src/tools/miri/tests/fail/tree-borrows/read-to-local.stderr
index 8c9c2f8f965..6deb4b43f6a 100644
--- a/src/tools/miri/tests/fail/tree-borrows/read-to-local.stderr
+++ b/src/tools/miri/tests/fail/tree-borrows/read-to-local.stderr
@@ -11,13 +11,13 @@ help: the accessed tag <TAG> was created here, in the initial state Reserved
    |
 LL |         let mref = &mut root;
    |                    ^^^^^^^^^
-help: the accessed tag <TAG> then transitioned from Reserved to Active due to a child write access at offsets [0x0..0x1]
+help: the accessed tag <TAG> later transitioned to Active due to a child write access at offsets [0x0..0x1]
   --> $DIR/read-to-local.rs:LL:CC
    |
 LL |         *ptr = 0; // Write
    |         ^^^^^^^^
-   = help: this corresponds to an activation
-help: the accessed tag <TAG> then transitioned from Active to Frozen due to a foreign read access at offsets [0x0..0x1]
+   = help: this corresponds to the first write to a 2-phase borrowed mutable reference
+help: the accessed tag <TAG> later transitioned to Frozen due to a foreign read access at offsets [0x0..0x1]
   --> $DIR/read-to-local.rs:LL:CC
    |
 LL |         assert_eq!(root, 0); // Parent Read
diff --git a/src/tools/miri/tests/fail/tree-borrows/strongly-protected.stderr b/src/tools/miri/tests/fail/tree-borrows/strongly-protected.stderr
index 071b216ff98..97088d5854c 100644
--- a/src/tools/miri/tests/fail/tree-borrows/strongly-protected.stderr
+++ b/src/tools/miri/tests/fail/tree-borrows/strongly-protected.stderr
@@ -17,12 +17,6 @@ help: the strongly protected tag <TAG> was created here, in the initial state Re
    |
 LL | fn inner(x: &mut i32, f: fn(&mut i32)) {
    |          ^
-help: the strongly protected tag <TAG> then transitioned from Reserved to Active due to a child write access at offsets [0x0..0x4]
-  --> $DIR/strongly-protected.rs:LL:CC
-   |
-LL |         drop(unsafe { Box::from_raw(raw) });
-   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
-   = help: this corresponds to an activation
    = note: BACKTRACE (of the first span):
    = note: inside `std::alloc::dealloc` at RUSTLIB/alloc/src/alloc.rs:LL:CC
    = note: inside `<std::alloc::Global as std::alloc::Allocator>::deallocate` at RUSTLIB/alloc/src/alloc.rs:LL:CC
diff --git a/src/tools/miri/tests/fail/tree-borrows/write-during-2phase.stderr b/src/tools/miri/tests/fail/tree-borrows/write-during-2phase.stderr
index f6285bdcf16..898f6108ccb 100644
--- a/src/tools/miri/tests/fail/tree-borrows/write-during-2phase.stderr
+++ b/src/tools/miri/tests/fail/tree-borrows/write-during-2phase.stderr
@@ -18,7 +18,7 @@ LL | |         *inner = 42;
 LL | |         n
 LL | |     });
    | |______^
-help: the accessed tag <TAG> then transitioned from Reserved to Disabled due to a foreign write access at offsets [0x0..0x8]
+help: the accessed tag <TAG> later transitioned to Disabled due to a foreign write access at offsets [0x0..0x8]
   --> $DIR/write-during-2phase.rs:LL:CC
    |
 LL |         *inner = 42;