diff options
| -rw-r--r-- | compiler/rustc_borrowck/src/invalidation.rs | 3 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/lib.rs | 17 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/path_utils.rs | 14 | ||||
| -rw-r--r-- | compiler/rustc_borrowck/src/places_conflict.rs | 143 |
4 files changed, 87 insertions, 90 deletions
diff --git a/compiler/rustc_borrowck/src/invalidation.rs b/compiler/rustc_borrowck/src/invalidation.rs index 0152d89eb83..df5e383ad40 100644 --- a/compiler/rustc_borrowck/src/invalidation.rs +++ b/compiler/rustc_borrowck/src/invalidation.rs @@ -353,7 +353,6 @@ impl<'cx, 'tcx> InvalidationGenerator<'cx, 'tcx> { let tcx = self.tcx; let body = self.body; let borrow_set = self.borrow_set; - let indices = self.borrow_set.indices(); each_borrow_involving_path( self, tcx, @@ -361,7 +360,7 @@ impl<'cx, 'tcx> InvalidationGenerator<'cx, 'tcx> { location, (sd, place), borrow_set, - indices, + |_| true, |this, borrow_index, borrow| { match (rw, borrow.kind) { // Obviously an activation is compatible with its own diff --git a/compiler/rustc_borrowck/src/lib.rs b/compiler/rustc_borrowck/src/lib.rs index ba1d31ee002..317af8ae1f6 100644 --- a/compiler/rustc_borrowck/src/lib.rs +++ b/compiler/rustc_borrowck/src/lib.rs @@ -23,7 +23,7 @@ use rustc_errors::{Diagnostic, DiagnosticBuilder, DiagnosticMessage, Subdiagnost use rustc_fluent_macro::fluent_messages; use rustc_hir as hir; use rustc_hir::def_id::LocalDefId; -use rustc_index::bit_set::ChunkedBitSet; +use rustc_index::bit_set::{BitSet, ChunkedBitSet}; use rustc_index::{IndexSlice, IndexVec}; use rustc_infer::infer::{ InferCtxt, NllRegionVariableOrigin, RegionVariableOrigin, TyCtxtInferExt, @@ -42,7 +42,6 @@ use rustc_session::lint::builtin::UNUSED_MUT; use rustc_span::{Span, Symbol}; use rustc_target::abi::FieldIdx; -use either::Either; use smallvec::SmallVec; use std::cell::RefCell; use std::collections::BTreeMap; @@ -1035,12 +1034,16 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> { let borrow_set = self.borrow_set.clone(); // Use polonius output if it has been enabled. - let polonius_output = self.polonius_output.clone(); - let borrows_in_scope = if let Some(polonius) = &polonius_output { + let mut polonius_output; + let borrows_in_scope = if let Some(polonius) = &self.polonius_output { let location = self.location_table.start_index(location); - Either::Left(polonius.errors_at(location).iter().copied()) + polonius_output = BitSet::new_empty(borrow_set.len()); + for &idx in polonius.errors_at(location) { + polonius_output.insert(idx); + } + &polonius_output } else { - Either::Right(flow_state.borrows.iter()) + &flow_state.borrows }; each_borrow_involving_path( @@ -1050,7 +1053,7 @@ impl<'cx, 'tcx> MirBorrowckCtxt<'cx, 'tcx> { location, (sd, place_span.0), &borrow_set, - borrows_in_scope, + |borrow_index| borrows_in_scope.contains(borrow_index), |this, borrow_index, borrow| match (rw, borrow.kind) { // Obviously an activation is compatible with its own // reservation (or even prior activating uses of same diff --git a/compiler/rustc_borrowck/src/path_utils.rs b/compiler/rustc_borrowck/src/path_utils.rs index ea9f8683ca7..ed93a560981 100644 --- a/compiler/rustc_borrowck/src/path_utils.rs +++ b/compiler/rustc_borrowck/src/path_utils.rs @@ -33,20 +33,24 @@ pub(super) fn each_borrow_involving_path<'tcx, F, I, S>( _location: Location, access_place: (AccessDepth, Place<'tcx>), borrow_set: &BorrowSet<'tcx>, - candidates: I, + is_candidate: I, mut op: F, ) where F: FnMut(&mut S, BorrowIndex, &BorrowData<'tcx>) -> Control, - I: Iterator<Item = BorrowIndex>, + I: Fn(BorrowIndex) -> bool, { let (access, place) = access_place; - // FIXME: analogous code in check_loans first maps `place` to - // its base_path. + // The number of candidates can be large, but borrows for different locals cannot conflict with + // each other, so we restrict the working set a priori. + let Some(borrows_for_place_base) = borrow_set.local_map.get(&place.local) else { return }; // check for loan restricting path P being used. Accounts for // borrows of P, P.a.b, etc. - for i in candidates { + for &i in borrows_for_place_base { + if !is_candidate(i) { + continue; + } let borrowed = &borrow_set[i]; if places_conflict::borrow_conflicts_with_place( diff --git a/compiler/rustc_borrowck/src/places_conflict.rs b/compiler/rustc_borrowck/src/places_conflict.rs index 1217dcb9c40..c02f6f3b687 100644 --- a/compiler/rustc_borrowck/src/places_conflict.rs +++ b/compiler/rustc_borrowck/src/places_conflict.rs @@ -1,3 +1,55 @@ +//! The borrowck rules for proving disjointness are applied from the "root" of the +//! borrow forwards, iterating over "similar" projections in lockstep until +//! we can prove overlap one way or another. Essentially, we treat `Overlap` as +//! a monoid and report a conflict if the product ends up not being `Disjoint`. +//! +//! At each step, if we didn't run out of borrow or place, we know that our elements +//! have the same type, and that they only overlap if they are the identical. +//! +//! For example, if we are comparing these: +//! ```text +//! BORROW: (*x1[2].y).z.a +//! ACCESS: (*x1[i].y).w.b +//! ``` +//! +//! Then our steps are: +//! ```text +//! x1 | x1 -- places are the same +//! x1[2] | x1[i] -- equal or disjoint (disjoint if indexes differ) +//! x1[2].y | x1[i].y -- equal or disjoint +//! *x1[2].y | *x1[i].y -- equal or disjoint +//! (*x1[2].y).z | (*x1[i].y).w -- we are disjoint and don't need to check more! +//! ``` +//! +//! Because `zip` does potentially bad things to the iterator inside, this loop +//! also handles the case where the access might be a *prefix* of the borrow, e.g. +//! +//! ```text +//! BORROW: (*x1[2].y).z.a +//! ACCESS: x1[i].y +//! ``` +//! +//! Then our steps are: +//! ```text +//! x1 | x1 -- places are the same +//! x1[2] | x1[i] -- equal or disjoint (disjoint if indexes differ) +//! x1[2].y | x1[i].y -- equal or disjoint +//! ``` +//! +//! -- here we run out of access - the borrow can access a part of it. If this +//! is a full deep access, then we *know* the borrow conflicts with it. However, +//! if the access is shallow, then we can proceed: +//! +//! ```text +//! x1[2].y | (*x1[i].y) -- a deref! the access can't get past this, so we +//! are disjoint +//! ``` +//! +//! Our invariant is, that at each step of the iteration: +//! - If we didn't run out of access to match, our borrow and access are comparable +//! and either equal or disjoint. +//! - If we did run out of access, the borrow can access a part of it. + #![deny(rustc::untranslatable_diagnostic)] #![deny(rustc::diagnostic_outside_of_impl)] use crate::ArtificialField; @@ -5,7 +57,7 @@ use crate::Overlap; use crate::{AccessDepth, Deep, Shallow}; use rustc_hir as hir; use rustc_middle::mir::{ - Body, BorrowKind, Local, MutBorrowKind, Place, PlaceElem, PlaceRef, ProjectionElem, + Body, BorrowKind, MutBorrowKind, Place, PlaceElem, PlaceRef, ProjectionElem, }; use rustc_middle::ty::{self, TyCtxt}; use std::cmp::max; @@ -48,7 +100,7 @@ pub fn places_conflict<'tcx>( /// access depth. The `bias` parameter is used to determine how the unknowable (comparing runtime /// array indices, for example) should be interpreted - this depends on what the caller wants in /// order to make the conservative choice and preserve soundness. -#[instrument(level = "debug", skip(tcx, body))] +#[inline] pub(super) fn borrow_conflicts_with_place<'tcx>( tcx: TyCtxt<'tcx>, body: &Body<'tcx>, @@ -58,15 +110,24 @@ pub(super) fn borrow_conflicts_with_place<'tcx>( access: AccessDepth, bias: PlaceConflictBias, ) -> bool { + let borrow_local = borrow_place.local; + let access_local = access_place.local; + + if borrow_local != access_local { + // We have proven the borrow disjoint - further projections will remain disjoint. + return false; + } + // This Local/Local case is handled by the more general code below, but // it's so common that it's a speed win to check for it first. - if let Some(l1) = borrow_place.as_local() && let Some(l2) = access_place.as_local() { - return l1 == l2; + if borrow_place.projection.is_empty() && access_place.projection.is_empty() { + return true; } place_components_conflict(tcx, body, borrow_place, borrow_kind, access_place, access, bias) } +#[instrument(level = "debug", skip(tcx, body))] fn place_components_conflict<'tcx>( tcx: TyCtxt<'tcx>, body: &Body<'tcx>, @@ -76,65 +137,10 @@ fn place_components_conflict<'tcx>( access: AccessDepth, bias: PlaceConflictBias, ) -> bool { - // The borrowck rules for proving disjointness are applied from the "root" of the - // borrow forwards, iterating over "similar" projections in lockstep until - // we can prove overlap one way or another. Essentially, we treat `Overlap` as - // a monoid and report a conflict if the product ends up not being `Disjoint`. - // - // At each step, if we didn't run out of borrow or place, we know that our elements - // have the same type, and that they only overlap if they are the identical. - // - // For example, if we are comparing these: - // BORROW: (*x1[2].y).z.a - // ACCESS: (*x1[i].y).w.b - // - // Then our steps are: - // x1 | x1 -- places are the same - // x1[2] | x1[i] -- equal or disjoint (disjoint if indexes differ) - // x1[2].y | x1[i].y -- equal or disjoint - // *x1[2].y | *x1[i].y -- equal or disjoint - // (*x1[2].y).z | (*x1[i].y).w -- we are disjoint and don't need to check more! - // - // Because `zip` does potentially bad things to the iterator inside, this loop - // also handles the case where the access might be a *prefix* of the borrow, e.g. - // - // BORROW: (*x1[2].y).z.a - // ACCESS: x1[i].y - // - // Then our steps are: - // x1 | x1 -- places are the same - // x1[2] | x1[i] -- equal or disjoint (disjoint if indexes differ) - // x1[2].y | x1[i].y -- equal or disjoint - // - // -- here we run out of access - the borrow can access a part of it. If this - // is a full deep access, then we *know* the borrow conflicts with it. However, - // if the access is shallow, then we can proceed: - // - // x1[2].y | (*x1[i].y) -- a deref! the access can't get past this, so we - // are disjoint - // - // Our invariant is, that at each step of the iteration: - // - If we didn't run out of access to match, our borrow and access are comparable - // and either equal or disjoint. - // - If we did run out of access, the borrow can access a part of it. - let borrow_local = borrow_place.local; let access_local = access_place.local; - - match place_base_conflict(borrow_local, access_local) { - Overlap::Arbitrary => { - bug!("Two base can't return Arbitrary"); - } - Overlap::EqualOrDisjoint => { - // This is the recursive case - proceed to the next element. - } - Overlap::Disjoint => { - // We have proven the borrow disjoint - further - // projections will remain disjoint. - debug!("borrow_conflicts_with_place: disjoint"); - return false; - } - } + // borrow_conflicts_with_place should have checked that. + assert_eq!(borrow_local, access_local); // loop invariant: borrow_c is always either equal to access_c or disjoint from it. for ((borrow_place, borrow_c), &access_c) in @@ -280,21 +286,6 @@ fn place_components_conflict<'tcx>( // Given that the bases of `elem1` and `elem2` are always either equal // or disjoint (and have the same type!), return the overlap situation // between `elem1` and `elem2`. -fn place_base_conflict(l1: Local, l2: Local) -> Overlap { - if l1 == l2 { - // the same local - base case, equal - debug!("place_element_conflict: DISJOINT-OR-EQ-LOCAL"); - Overlap::EqualOrDisjoint - } else { - // different locals - base case, disjoint - debug!("place_element_conflict: DISJOINT-LOCAL"); - Overlap::Disjoint - } -} - -// Given that the bases of `elem1` and `elem2` are always either equal -// or disjoint (and have the same type!), return the overlap situation -// between `elem1` and `elem2`. fn place_projection_conflict<'tcx>( tcx: TyCtxt<'tcx>, body: &Body<'tcx>, |