1 use crate::borrow_check::ArtificialField;
2 use crate::borrow_check::Overlap;
3 use crate::borrow_check::{Deep, Shallow, AccessDepth};
5 use rustc::mir::{BorrowKind, Mir, Place, PlaceBase, Projection, ProjectionElem, StaticKind};
6 use rustc::ty::{self, TyCtxt};
9 /// When checking if a place conflicts with another place, this enum is used to influence decisions
10 /// where a place might be equal or disjoint with another place, such as if `a[i] == a[j]`.
11 /// `PlaceConflictBias::Overlap` would bias toward assuming that `i` might equal `j` and that these
12 /// places overlap. `PlaceConflictBias::NoOverlap` assumes that for the purposes of the predicate
13 /// being run in the calling context, the conservative choice is to assume the compared indices
14 /// are disjoint (and therefore, do not overlap).
15 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
16 crate enum PlaceConflictBias {
21 /// Helper function for checking if places conflict with a mutable borrow and deep access depth.
22 /// This is used to check for places conflicting outside of the borrow checking code (such as in
24 crate fn places_conflict<'gcx, 'tcx>(
25 tcx: TyCtxt<'_, 'gcx, 'tcx>,
27 borrow_place: &Place<'tcx>,
28 access_place: &Place<'tcx>,
29 bias: PlaceConflictBias,
31 borrow_conflicts_with_place(
35 BorrowKind::Mut { allow_two_phase_borrow: true },
42 /// Checks whether the `borrow_place` conflicts with the `access_place` given a borrow kind and
43 /// access depth. The `bias` parameter is used to determine how the unknowable (comparing runtime
44 /// array indices, for example) should be interpreted - this depends on what the caller wants in
45 /// order to make the conservative choice and preserve soundness.
46 pub(super) fn borrow_conflicts_with_place<'gcx, 'tcx>(
47 tcx: TyCtxt<'_, 'gcx, 'tcx>,
49 borrow_place: &Place<'tcx>,
50 borrow_kind: BorrowKind,
51 access_place: &Place<'tcx>,
53 bias: PlaceConflictBias,
56 "borrow_conflicts_with_place({:?}, {:?}, {:?}, {:?})",
57 borrow_place, access_place, access, bias,
60 // This Local/Local case is handled by the more general code below, but
61 // it's so common that it's a speed win to check for it first.
62 if let Place::Base(PlaceBase::Local(l1)) = borrow_place {
63 if let Place::Base(PlaceBase::Local(l2)) = access_place {
68 unroll_place(borrow_place, None, |borrow_components| {
69 unroll_place(access_place, None, |access_components| {
70 place_components_conflict(
83 fn place_components_conflict<'gcx, 'tcx>(
84 tcx: TyCtxt<'_, 'gcx, 'tcx>,
86 mut borrow_components: PlaceComponentsIter<'_, 'tcx>,
87 borrow_kind: BorrowKind,
88 mut access_components: PlaceComponentsIter<'_, 'tcx>,
90 bias: PlaceConflictBias,
92 // The borrowck rules for proving disjointness are applied from the "root" of the
93 // borrow forwards, iterating over "similar" projections in lockstep until
94 // we can prove overlap one way or another. Essentially, we treat `Overlap` as
95 // a monoid and report a conflict if the product ends up not being `Disjoint`.
97 // At each step, if we didn't run out of borrow or place, we know that our elements
98 // have the same type, and that they only overlap if they are the identical.
100 // For example, if we are comparing these:
101 // BORROW: (*x1[2].y).z.a
102 // ACCESS: (*x1[i].y).w.b
104 // Then our steps are:
105 // x1 | x1 -- places are the same
106 // x1[2] | x1[i] -- equal or disjoint (disjoint if indexes differ)
107 // x1[2].y | x1[i].y -- equal or disjoint
108 // *x1[2].y | *x1[i].y -- equal or disjoint
109 // (*x1[2].y).z | (*x1[i].y).w -- we are disjoint and don't need to check more!
111 // Because `zip` does potentially bad things to the iterator inside, this loop
112 // also handles the case where the access might be a *prefix* of the borrow, e.g.
114 // BORROW: (*x1[2].y).z.a
117 // Then our steps are:
118 // x1 | x1 -- places are the same
119 // x1[2] | x1[i] -- equal or disjoint (disjoint if indexes differ)
120 // x1[2].y | x1[i].y -- equal or disjoint
122 // -- here we run out of access - the borrow can access a part of it. If this
123 // is a full deep access, then we *know* the borrow conflicts with it. However,
124 // if the access is shallow, then we can proceed:
126 // x1[2].y | (*x1[i].y) -- a deref! the access can't get past this, so we
129 // Our invariant is, that at each step of the iteration:
130 // - If we didn't run out of access to match, our borrow and access are comparable
131 // and either equal or disjoint.
132 // - If we did run out of access, the borrow can access a part of it.
134 // loop invariant: borrow_c is always either equal to access_c or disjoint from it.
135 if let Some(borrow_c) = borrow_components.next() {
136 debug!("borrow_conflicts_with_place: borrow_c = {:?}", borrow_c);
138 if let Some(access_c) = access_components.next() {
139 debug!("borrow_conflicts_with_place: access_c = {:?}", access_c);
141 // Borrow and access path both have more components.
145 // - borrow of `a.(...)`, access to `a.(...)`
146 // - borrow of `a.(...)`, access to `b.(...)`
148 // Here we only see the components we have checked so
149 // far (in our examples, just the first component). We
150 // check whether the components being borrowed vs
151 // accessed are disjoint (as in the second example,
152 // but not the first).
153 match place_element_conflict(tcx, mir, borrow_c, access_c, bias) {
154 Overlap::Arbitrary => {
155 // We have encountered different fields of potentially
156 // the same union - the borrow now partially overlaps.
158 // There is no *easy* way of comparing the fields
159 // further on, because they might have different types
160 // (e.g., borrows of `u.a.0` and `u.b.y` where `.0` and
161 // `.y` come from different structs).
163 // We could try to do some things here - e.g., count
164 // dereferences - but that's probably not a good
165 // idea, at least for now, so just give up and
166 // report a conflict. This is unsafe code anyway so
167 // the user could always use raw pointers.
168 debug!("borrow_conflicts_with_place: arbitrary -> conflict");
171 Overlap::EqualOrDisjoint => {
172 // This is the recursive case - proceed to the next element.
174 Overlap::Disjoint => {
175 // We have proven the borrow disjoint - further
176 // projections will remain disjoint.
177 debug!("borrow_conflicts_with_place: disjoint");
182 // Borrow path is longer than the access path. Examples:
184 // - borrow of `a.b.c`, access to `a.b`
186 // Here, we know that the borrow can access a part of
187 // our place. This is a conflict if that is a part our
188 // access cares about.
190 let (base, elem) = match borrow_c {
191 Place::Projection(box Projection { base, elem }) => (base, elem),
192 _ => bug!("place has no base?"),
194 let base_ty = base.ty(mir, tcx).to_ty(tcx);
196 match (elem, &base_ty.sty, access) {
197 (_, _, Shallow(Some(ArtificialField::ArrayLength)))
198 | (_, _, Shallow(Some(ArtificialField::ShallowBorrow))) => {
199 // The array length is like additional fields on the
200 // type; it does not overlap any existing data there.
201 // Furthermore, if cannot actually be a prefix of any
202 // borrowed place (at least in MIR as it is currently.)
204 // e.g., a (mutable) borrow of `a[5]` while we read the
205 // array length of `a`.
206 debug!("borrow_conflicts_with_place: implicit field");
210 (ProjectionElem::Deref, _, Shallow(None)) => {
211 // e.g., a borrow of `*x.y` while we shallowly access `x.y` or some
212 // prefix thereof - the shallow access can't touch anything behind
214 debug!("borrow_conflicts_with_place: shallow access behind ptr");
217 (ProjectionElem::Deref, ty::Ref(_, _, hir::MutImmutable), _) => {
218 // Shouldn't be tracked
219 bug!("Tracking borrow behind shared reference.");
221 (ProjectionElem::Deref, ty::Ref(_, _, hir::MutMutable), AccessDepth::Drop) => {
222 // Values behind a mutable reference are not access either by dropping a
223 // value, or by StorageDead
224 debug!("borrow_conflicts_with_place: drop access behind ptr");
228 (ProjectionElem::Field { .. }, ty::Adt(def, _), AccessDepth::Drop) => {
229 // Drop can read/write arbitrary projections, so places
230 // conflict regardless of further projections.
231 if def.has_dtor(tcx) {
236 (ProjectionElem::Deref, _, Deep)
237 | (ProjectionElem::Deref, _, AccessDepth::Drop)
238 | (ProjectionElem::Field { .. }, _, _)
239 | (ProjectionElem::Index { .. }, _, _)
240 | (ProjectionElem::ConstantIndex { .. }, _, _)
241 | (ProjectionElem::Subslice { .. }, _, _)
242 | (ProjectionElem::Downcast { .. }, _, _) => {
243 // Recursive case. This can still be disjoint on a
244 // further iteration if this a shallow access and
245 // there's a deref later on, e.g., a borrow
246 // of `*x.y` while accessing `x`.
251 // Borrow path ran out but access path may not
254 // - borrow of `a.b`, access to `a.b.c`
255 // - borrow of `a.b`, access to `a.b`
257 // In the first example, where we didn't run out of
258 // access, the borrow can access all of our place, so we
261 // If the second example, where we did, then we still know
262 // that the borrow can access a *part* of our place that
263 // our access cares about, so we still have a conflict.
264 if borrow_kind == BorrowKind::Shallow && access_components.next().is_some() {
265 debug!("borrow_conflicts_with_place: shallow borrow");
268 debug!("borrow_conflicts_with_place: full borrow, CONFLICT");
275 /// A linked list of places running up the stack; begins with the
276 /// innermost place and extends to projections (e.g., `a.b` would have
277 /// the place `a` with a "next" pointer to `a.b`). Created by
280 /// N.B., this particular impl strategy is not the most obvious. It was
281 /// chosen because it makes a measurable difference to NLL
282 /// performance, as this code (`borrow_conflicts_with_place`) is somewhat hot.
283 struct PlaceComponents<'p, 'tcx: 'p> {
284 component: &'p Place<'tcx>,
285 next: Option<&'p PlaceComponents<'p, 'tcx>>,
288 impl<'p, 'tcx> PlaceComponents<'p, 'tcx> {
289 /// Converts a list of `Place` components into an iterator; this
290 /// iterator yields up a never-ending stream of `Option<&Place>`.
291 /// These begin with the "innermost" place and then with each
292 /// projection therefrom. So given a place like `a.b.c` it would
296 /// Some(`a`), Some(`a.b`), Some(`a.b.c`), None, None, ...
298 fn iter(&self) -> PlaceComponentsIter<'_, 'tcx> {
299 PlaceComponentsIter { value: Some(self) }
303 /// Iterator over components; see `PlaceComponents::iter` for more
306 /// N.B., this is not a *true* Rust iterator -- the code above just
307 /// manually invokes `next`. This is because we (sometimes) want to
308 /// keep executing even after `None` has been returned.
309 struct PlaceComponentsIter<'p, 'tcx: 'p> {
310 value: Option<&'p PlaceComponents<'p, 'tcx>>,
313 impl<'p, 'tcx> PlaceComponentsIter<'p, 'tcx> {
314 fn next(&mut self) -> Option<&'p Place<'tcx>> {
315 if let Some(&PlaceComponents { component, next }) = self.value {
324 /// Recursively "unroll" a place into a `PlaceComponents` list,
325 /// invoking `op` with a `PlaceComponentsIter`.
326 fn unroll_place<'tcx, R>(
328 next: Option<&PlaceComponents<'_, 'tcx>>,
329 op: impl FnOnce(PlaceComponentsIter<'_, 'tcx>) -> R,
332 Place::Projection(interior) => unroll_place(
334 Some(&PlaceComponents {
341 Place::Base(PlaceBase::Local(_)) | Place::Base(PlaceBase::Static(_)) => {
342 let list = PlaceComponents {
351 // Given that the bases of `elem1` and `elem2` are always either equal
352 // or disjoint (and have the same type!), return the overlap situation
353 // between `elem1` and `elem2`.
354 fn place_element_conflict<'a, 'gcx: 'tcx, 'tcx>(
355 tcx: TyCtxt<'a, 'gcx, 'tcx>,
359 bias: PlaceConflictBias,
361 match (elem1, elem2) {
362 (Place::Base(PlaceBase::Local(l1)), Place::Base(PlaceBase::Local(l2))) => {
364 // the same local - base case, equal
365 debug!("place_element_conflict: DISJOINT-OR-EQ-LOCAL");
366 Overlap::EqualOrDisjoint
368 // different locals - base case, disjoint
369 debug!("place_element_conflict: DISJOINT-LOCAL");
373 (Place::Base(PlaceBase::Static(s1)), Place::Base(PlaceBase::Static(s2))) => {
374 match (&s1.kind, &s2.kind) {
375 (StaticKind::Static(def_id_1), StaticKind::Static(def_id_2)) => {
376 if def_id_1 != def_id_2 {
377 debug!("place_element_conflict: DISJOINT-STATIC");
379 } else if tcx.is_static(*def_id_1) == Some(hir::Mutability::MutMutable) {
380 // We ignore mutable statics - they can only be unsafe code.
381 debug!("place_element_conflict: IGNORE-STATIC-MUT");
384 debug!("place_element_conflict: DISJOINT-OR-EQ-STATIC");
385 Overlap::EqualOrDisjoint
388 (StaticKind::Promoted(promoted_1), StaticKind::Promoted(promoted_2)) => {
389 if promoted_1 == promoted_2 {
390 if let ty::Array(_, size) = s1.ty.sty {
391 if size.unwrap_usize(tcx) == 0 {
392 // Ignore conflicts with promoted [T; 0].
393 debug!("place_element_conflict: IGNORE-LEN-0-PROMOTED");
394 return Overlap::Disjoint;
397 // the same promoted - base case, equal
398 debug!("place_element_conflict: DISJOINT-OR-EQ-PROMOTED");
399 Overlap::EqualOrDisjoint
401 // different promoteds - base case, disjoint
402 debug!("place_element_conflict: DISJOINT-PROMOTED");
407 debug!("place_element_conflict: DISJOINT-STATIC-PROMOTED");
412 (Place::Base(PlaceBase::Local(_)), Place::Base(PlaceBase::Static(_))) |
413 (Place::Base(PlaceBase::Static(_)), Place::Base(PlaceBase::Local(_))) => {
414 debug!("place_element_conflict: DISJOINT-STATIC-LOCAL-PROMOTED");
417 (Place::Projection(pi1), Place::Projection(pi2)) => {
418 match (&pi1.elem, &pi2.elem) {
419 (ProjectionElem::Deref, ProjectionElem::Deref) => {
420 // derefs (e.g., `*x` vs. `*x`) - recur.
421 debug!("place_element_conflict: DISJOINT-OR-EQ-DEREF");
422 Overlap::EqualOrDisjoint
424 (ProjectionElem::Field(f1, _), ProjectionElem::Field(f2, _)) => {
426 // same field (e.g., `a.y` vs. `a.y`) - recur.
427 debug!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
428 Overlap::EqualOrDisjoint
430 let ty = pi1.base.ty(mir, tcx).to_ty(tcx);
432 ty::Adt(def, _) if def.is_union() => {
433 // Different fields of a union, we are basically stuck.
434 debug!("place_element_conflict: STUCK-UNION");
438 // Different fields of a struct (`a.x` vs. `a.y`). Disjoint!
439 debug!("place_element_conflict: DISJOINT-FIELD");
445 (ProjectionElem::Downcast(_, v1), ProjectionElem::Downcast(_, v2)) => {
446 // different variants are treated as having disjoint fields,
447 // even if they occupy the same "space", because it's
448 // impossible for 2 variants of the same enum to exist
449 // (and therefore, to be borrowed) at the same time.
451 // Note that this is different from unions - we *do* allow
452 // this code to compile:
455 // fn foo(x: &mut Result<i32, i32>) {
457 // if let Ok(ref mut a) = *x {
460 // // here, you would *think* that the
461 // // *entirety* of `x` would be borrowed,
462 // // but in fact only the `Ok` variant is,
463 // // so the `Err` variant is *entirely free*:
464 // if let Err(ref mut a) = *x {
471 debug!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
472 Overlap::EqualOrDisjoint
474 debug!("place_element_conflict: DISJOINT-FIELD");
478 (ProjectionElem::Index(..), ProjectionElem::Index(..))
479 | (ProjectionElem::Index(..), ProjectionElem::ConstantIndex { .. })
480 | (ProjectionElem::Index(..), ProjectionElem::Subslice { .. })
481 | (ProjectionElem::ConstantIndex { .. }, ProjectionElem::Index(..))
482 | (ProjectionElem::Subslice { .. }, ProjectionElem::Index(..)) => {
483 // Array indexes (`a[0]` vs. `a[i]`). These can either be disjoint
484 // (if the indexes differ) or equal (if they are the same).
486 PlaceConflictBias::Overlap => {
487 // If we are biased towards overlapping, then this is the recursive
488 // case that gives "equal *or* disjoint" its meaning.
489 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-INDEX");
490 Overlap::EqualOrDisjoint
492 PlaceConflictBias::NoOverlap => {
493 // If we are biased towards no overlapping, then this is disjoint.
494 debug!("place_element_conflict: DISJOINT-ARRAY-INDEX");
499 (ProjectionElem::ConstantIndex { offset: o1, min_length: _, from_end: false },
500 ProjectionElem::ConstantIndex { offset: o2, min_length: _, from_end: false })
501 | (ProjectionElem::ConstantIndex { offset: o1, min_length: _, from_end: true },
502 ProjectionElem::ConstantIndex {
503 offset: o2, min_length: _, from_end: true }) => {
505 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX");
506 Overlap::EqualOrDisjoint
508 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX");
512 (ProjectionElem::ConstantIndex {
513 offset: offset_from_begin, min_length: min_length1, from_end: false },
514 ProjectionElem::ConstantIndex {
515 offset: offset_from_end, min_length: min_length2, from_end: true })
516 | (ProjectionElem::ConstantIndex {
517 offset: offset_from_end, min_length: min_length1, from_end: true },
518 ProjectionElem::ConstantIndex {
519 offset: offset_from_begin, min_length: min_length2, from_end: false }) => {
520 // both patterns matched so it must be at least the greater of the two
521 let min_length = max(min_length1, min_length2);
522 // `offset_from_end` can be in range `[1..min_length]`, 1 indicates the last
523 // element (like -1 in Python) and `min_length` the first.
524 // Therefore, `min_length - offset_from_end` gives the minimal possible
525 // offset from the beginning
526 if *offset_from_begin >= min_length - offset_from_end {
527 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-FE");
528 Overlap::EqualOrDisjoint
530 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-FE");
534 (ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
535 ProjectionElem::Subslice {from, .. })
536 | (ProjectionElem::Subslice {from, .. },
537 ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false }) => {
540 "place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-SUBSLICE");
541 Overlap::EqualOrDisjoint
543 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-SUBSLICE");
547 (ProjectionElem::ConstantIndex { offset, min_length: _, from_end: true },
548 ProjectionElem::Subslice {from: _, to })
549 | (ProjectionElem::Subslice {from: _, to },
550 ProjectionElem::ConstantIndex { offset, min_length: _, from_end: true }) => {
552 debug!("place_element_conflict: \
553 DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-SUBSLICE-FE");
554 Overlap::EqualOrDisjoint
556 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-SUBSLICE-FE");
560 (ProjectionElem::Subslice { .. }, ProjectionElem::Subslice { .. }) => {
561 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-SUBSLICES");
562 Overlap::EqualOrDisjoint
564 (ProjectionElem::Deref, _)
565 | (ProjectionElem::Field(..), _)
566 | (ProjectionElem::Index(..), _)
567 | (ProjectionElem::ConstantIndex { .. }, _)
568 | (ProjectionElem::Subslice { .. }, _)
569 | (ProjectionElem::Downcast(..), _) => bug!(
570 "mismatched projections in place_element_conflict: {:?} and {:?}",
576 (Place::Projection(_), _) | (_, Place::Projection(_)) => bug!(
577 "unexpected elements in place_element_conflict: {:?} and {:?}",