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};
6 use rustc::mir::{Projection, ProjectionElem};
7 use rustc::ty::{self, TyCtxt};
10 /// When checking if a place conflicts with another place, this enum is used to influence decisions
11 /// where a place might be equal or disjoint with another place, such as if `a[i] == a[j]`.
12 /// `PlaceConflictBias::Overlap` would bias toward assuming that `i` might equal `j` and that these
13 /// places overlap. `PlaceConflictBias::NoOverlap` assumes that for the purposes of the predicate
14 /// being run in the calling context, the conservative choice is to assume the compared indices
15 /// are disjoint (and therefore, do not overlap).
16 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
17 crate enum PlaceConflictBias {
22 /// Helper function for checking if places conflict with a mutable borrow and deep access depth.
23 /// This is used to check for places conflicting outside of the borrow checking code (such as in
25 crate fn places_conflict<'gcx, 'tcx>(
26 tcx: TyCtxt<'_, 'gcx, 'tcx>,
28 borrow_place: &Place<'tcx>,
29 access_place: &Place<'tcx>,
30 bias: PlaceConflictBias,
32 borrow_conflicts_with_place(
36 BorrowKind::Mut { allow_two_phase_borrow: true },
43 /// Checks whether the `borrow_place` conflicts with the `access_place` given a borrow kind and
44 /// access depth. The `bias` parameter is used to determine how the unknowable (comparing runtime
45 /// array indices, for example) should be interpreted - this depends on what the caller wants in
46 /// order to make the conservative choice and preserve soundness.
47 pub(super) fn borrow_conflicts_with_place<'gcx, 'tcx>(
48 tcx: TyCtxt<'_, 'gcx, 'tcx>,
50 borrow_place: &Place<'tcx>,
51 borrow_kind: BorrowKind,
52 access_place: &Place<'tcx>,
54 bias: PlaceConflictBias,
57 "borrow_conflicts_with_place({:?}, {:?}, {:?}, {:?})",
58 borrow_place, access_place, access, bias,
61 // This Local/Local case is handled by the more general code below, but
62 // it's so common that it's a speed win to check for it first.
63 if let Place::Local(l1) = borrow_place {
64 if let Place::Local(l2) = access_place {
69 unroll_place(borrow_place, None, |borrow_components| {
70 unroll_place(access_place, None, |access_components| {
71 place_components_conflict(
84 fn place_components_conflict<'gcx, 'tcx>(
85 tcx: TyCtxt<'_, 'gcx, 'tcx>,
87 mut borrow_components: PlaceComponentsIter<'_, 'tcx>,
88 borrow_kind: BorrowKind,
89 mut access_components: PlaceComponentsIter<'_, 'tcx>,
91 bias: PlaceConflictBias,
93 // The borrowck rules for proving disjointness are applied from the "root" of the
94 // borrow forwards, iterating over "similar" projections in lockstep until
95 // we can prove overlap one way or another. Essentially, we treat `Overlap` as
96 // a monoid and report a conflict if the product ends up not being `Disjoint`.
98 // At each step, if we didn't run out of borrow or place, we know that our elements
99 // have the same type, and that they only overlap if they are the identical.
101 // For example, if we are comparing these:
102 // BORROW: (*x1[2].y).z.a
103 // ACCESS: (*x1[i].y).w.b
105 // Then our steps are:
106 // x1 | x1 -- places are the same
107 // x1[2] | x1[i] -- equal or disjoint (disjoint if indexes differ)
108 // x1[2].y | x1[i].y -- equal or disjoint
109 // *x1[2].y | *x1[i].y -- equal or disjoint
110 // (*x1[2].y).z | (*x1[i].y).w -- we are disjoint and don't need to check more!
112 // Because `zip` does potentially bad things to the iterator inside, this loop
113 // also handles the case where the access might be a *prefix* of the borrow, e.g.
115 // BORROW: (*x1[2].y).z.a
118 // Then our steps are:
119 // x1 | x1 -- places are the same
120 // x1[2] | x1[i] -- equal or disjoint (disjoint if indexes differ)
121 // x1[2].y | x1[i].y -- equal or disjoint
123 // -- here we run out of access - the borrow can access a part of it. If this
124 // is a full deep access, then we *know* the borrow conflicts with it. However,
125 // if the access is shallow, then we can proceed:
127 // x1[2].y | (*x1[i].y) -- a deref! the access can't get past this, so we
130 // Our invariant is, that at each step of the iteration:
131 // - If we didn't run out of access to match, our borrow and access are comparable
132 // and either equal or disjoint.
133 // - If we did run out of access, the borrow can access a part of it.
135 // loop invariant: borrow_c is always either equal to access_c or disjoint from it.
136 if let Some(borrow_c) = borrow_components.next() {
137 debug!("borrow_conflicts_with_place: borrow_c = {:?}", borrow_c);
139 if let Some(access_c) = access_components.next() {
140 debug!("borrow_conflicts_with_place: access_c = {:?}", access_c);
142 // Borrow and access path both have more components.
146 // - borrow of `a.(...)`, access to `a.(...)`
147 // - borrow of `a.(...)`, access to `b.(...)`
149 // Here we only see the components we have checked so
150 // far (in our examples, just the first component). We
151 // check whether the components being borrowed vs
152 // accessed are disjoint (as in the second example,
153 // but not the first).
154 match place_element_conflict(tcx, mir, borrow_c, access_c, bias) {
155 Overlap::Arbitrary => {
156 // We have encountered different fields of potentially
157 // the same union - the borrow now partially overlaps.
159 // There is no *easy* way of comparing the fields
160 // further on, because they might have different types
161 // (e.g., borrows of `u.a.0` and `u.b.y` where `.0` and
162 // `.y` come from different structs).
164 // We could try to do some things here - e.g., count
165 // dereferences - but that's probably not a good
166 // idea, at least for now, so just give up and
167 // report a conflict. This is unsafe code anyway so
168 // the user could always use raw pointers.
169 debug!("borrow_conflicts_with_place: arbitrary -> conflict");
172 Overlap::EqualOrDisjoint => {
173 // This is the recursive case - proceed to the next element.
175 Overlap::Disjoint => {
176 // We have proven the borrow disjoint - further
177 // projections will remain disjoint.
178 debug!("borrow_conflicts_with_place: disjoint");
183 // Borrow path is longer than the access path. Examples:
185 // - borrow of `a.b.c`, access to `a.b`
187 // Here, we know that the borrow can access a part of
188 // our place. This is a conflict if that is a part our
189 // access cares about.
191 let (base, elem) = match borrow_c {
192 Place::Projection(box Projection { base, elem }) => (base, elem),
193 _ => bug!("place has no base?"),
195 let base_ty = base.ty(mir, tcx).to_ty(tcx);
197 match (elem, &base_ty.sty, access) {
198 (_, _, Shallow(Some(ArtificialField::ArrayLength)))
199 | (_, _, Shallow(Some(ArtificialField::ShallowBorrow))) => {
200 // The array length is like additional fields on the
201 // type; it does not overlap any existing data there.
202 // Furthermore, if cannot actually be a prefix of any
203 // borrowed place (at least in MIR as it is currently.)
205 // e.g., a (mutable) borrow of `a[5]` while we read the
206 // array length of `a`.
207 debug!("borrow_conflicts_with_place: implicit field");
211 (ProjectionElem::Deref, _, Shallow(None)) => {
212 // e.g., a borrow of `*x.y` while we shallowly access `x.y` or some
213 // prefix thereof - the shallow access can't touch anything behind
215 debug!("borrow_conflicts_with_place: shallow access behind ptr");
218 (ProjectionElem::Deref, ty::Ref(_, _, hir::MutImmutable), _) => {
219 // Shouldn't be tracked
220 bug!("Tracking borrow behind shared reference.");
222 (ProjectionElem::Deref, ty::Ref(_, _, hir::MutMutable), AccessDepth::Drop) => {
223 // Values behind a mutable reference are not access either by dropping a
224 // value, or by StorageDead
225 debug!("borrow_conflicts_with_place: drop access behind ptr");
229 (ProjectionElem::Field { .. }, ty::Adt(def, _), AccessDepth::Drop) => {
230 // Drop can read/write arbitrary projections, so places
231 // conflict regardless of further projections.
232 if def.has_dtor(tcx) {
237 (ProjectionElem::Deref, _, Deep)
238 | (ProjectionElem::Deref, _, AccessDepth::Drop)
239 | (ProjectionElem::Field { .. }, _, _)
240 | (ProjectionElem::Index { .. }, _, _)
241 | (ProjectionElem::ConstantIndex { .. }, _, _)
242 | (ProjectionElem::Subslice { .. }, _, _)
243 | (ProjectionElem::Downcast { .. }, _, _) => {
244 // Recursive case. This can still be disjoint on a
245 // further iteration if this a shallow access and
246 // there's a deref later on, e.g., a borrow
247 // of `*x.y` while accessing `x`.
252 // Borrow path ran out but access path may not
255 // - borrow of `a.b`, access to `a.b.c`
256 // - borrow of `a.b`, access to `a.b`
258 // In the first example, where we didn't run out of
259 // access, the borrow can access all of our place, so we
262 // If the second example, where we did, then we still know
263 // that the borrow can access a *part* of our place that
264 // our access cares about, so we still have a conflict.
265 if borrow_kind == BorrowKind::Shallow && access_components.next().is_some() {
266 debug!("borrow_conflicts_with_place: shallow borrow");
269 debug!("borrow_conflicts_with_place: full borrow, CONFLICT");
276 /// A linked list of places running up the stack; begins with the
277 /// innermost place and extends to projections (e.g., `a.b` would have
278 /// the place `a` with a "next" pointer to `a.b`). Created by
281 /// N.B., this particular impl strategy is not the most obvious. It was
282 /// chosen because it makes a measurable difference to NLL
283 /// performance, as this code (`borrow_conflicts_with_place`) is somewhat hot.
284 struct PlaceComponents<'p, 'tcx: 'p> {
285 component: &'p Place<'tcx>,
286 next: Option<&'p PlaceComponents<'p, 'tcx>>,
289 impl<'p, 'tcx> PlaceComponents<'p, 'tcx> {
290 /// Converts a list of `Place` components into an iterator; this
291 /// iterator yields up a never-ending stream of `Option<&Place>`.
292 /// These begin with the "innermost" place and then with each
293 /// projection therefrom. So given a place like `a.b.c` it would
297 /// Some(`a`), Some(`a.b`), Some(`a.b.c`), None, None, ...
299 fn iter(&self) -> PlaceComponentsIter<'_, 'tcx> {
300 PlaceComponentsIter { value: Some(self) }
304 /// Iterator over components; see `PlaceComponents::iter` for more
307 /// N.B., this is not a *true* Rust iterator -- the code above just
308 /// manually invokes `next`. This is because we (sometimes) want to
309 /// keep executing even after `None` has been returned.
310 struct PlaceComponentsIter<'p, 'tcx: 'p> {
311 value: Option<&'p PlaceComponents<'p, 'tcx>>,
314 impl<'p, 'tcx> PlaceComponentsIter<'p, 'tcx> {
315 fn next(&mut self) -> Option<&'p Place<'tcx>> {
316 if let Some(&PlaceComponents { component, next }) = self.value {
325 /// Recursively "unroll" a place into a `PlaceComponents` list,
326 /// invoking `op` with a `PlaceComponentsIter`.
327 fn unroll_place<'tcx, R>(
329 next: Option<&PlaceComponents<'_, 'tcx>>,
330 op: impl FnOnce(PlaceComponentsIter<'_, 'tcx>) -> R,
333 Place::Projection(interior) => unroll_place(
335 Some(&PlaceComponents {
343 Place::Local(_) | Place::Static(_) => {
344 let list = PlaceComponents {
353 // Given that the bases of `elem1` and `elem2` are always either equal
354 // or disjoint (and have the same type!), return the overlap situation
355 // between `elem1` and `elem2`.
356 fn place_element_conflict<'a, 'gcx: 'tcx, 'tcx>(
357 tcx: TyCtxt<'a, 'gcx, 'tcx>,
361 bias: PlaceConflictBias,
363 match (elem1, elem2) {
364 (Place::Local(l1), Place::Local(l2)) => {
366 // the same local - base case, equal
367 debug!("place_element_conflict: DISJOINT-OR-EQ-LOCAL");
368 Overlap::EqualOrDisjoint
370 // different locals - base case, disjoint
371 debug!("place_element_conflict: DISJOINT-LOCAL");
375 (Place::Static(static1), Place::Static(static2)) => {
376 if static1.def_id != static2.def_id {
377 debug!("place_element_conflict: DISJOINT-STATIC");
379 } else if tcx.is_static(static1.def_id) == 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 (Place::Promoted(p1), Place::Promoted(p2)) => {
390 if let ty::Array(_, size) = p1.1.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");
406 (Place::Local(_), Place::Promoted(_)) | (Place::Promoted(_), Place::Local(_)) |
407 (Place::Promoted(_), Place::Static(_)) | (Place::Static(_), Place::Promoted(_)) |
408 (Place::Local(_), Place::Static(_)) | (Place::Static(_), Place::Local(_)) => {
409 debug!("place_element_conflict: DISJOINT-STATIC-LOCAL-PROMOTED");
412 (Place::Projection(pi1), Place::Projection(pi2)) => {
413 match (&pi1.elem, &pi2.elem) {
414 (ProjectionElem::Deref, ProjectionElem::Deref) => {
415 // derefs (e.g., `*x` vs. `*x`) - recur.
416 debug!("place_element_conflict: DISJOINT-OR-EQ-DEREF");
417 Overlap::EqualOrDisjoint
419 (ProjectionElem::Field(f1, _), ProjectionElem::Field(f2, _)) => {
421 // same field (e.g., `a.y` vs. `a.y`) - recur.
422 debug!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
423 Overlap::EqualOrDisjoint
425 let ty = pi1.base.ty(mir, tcx).to_ty(tcx);
427 ty::Adt(def, _) if def.is_union() => {
428 // Different fields of a union, we are basically stuck.
429 debug!("place_element_conflict: STUCK-UNION");
433 // Different fields of a struct (`a.x` vs. `a.y`). Disjoint!
434 debug!("place_element_conflict: DISJOINT-FIELD");
440 (ProjectionElem::Downcast(_, v1), ProjectionElem::Downcast(_, v2)) => {
441 // different variants are treated as having disjoint fields,
442 // even if they occupy the same "space", because it's
443 // impossible for 2 variants of the same enum to exist
444 // (and therefore, to be borrowed) at the same time.
446 // Note that this is different from unions - we *do* allow
447 // this code to compile:
450 // fn foo(x: &mut Result<i32, i32>) {
452 // if let Ok(ref mut a) = *x {
455 // // here, you would *think* that the
456 // // *entirety* of `x` would be borrowed,
457 // // but in fact only the `Ok` variant is,
458 // // so the `Err` variant is *entirely free*:
459 // if let Err(ref mut a) = *x {
466 debug!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
467 Overlap::EqualOrDisjoint
469 debug!("place_element_conflict: DISJOINT-FIELD");
473 (ProjectionElem::Index(..), ProjectionElem::Index(..))
474 | (ProjectionElem::Index(..), ProjectionElem::ConstantIndex { .. })
475 | (ProjectionElem::Index(..), ProjectionElem::Subslice { .. })
476 | (ProjectionElem::ConstantIndex { .. }, ProjectionElem::Index(..))
477 | (ProjectionElem::Subslice { .. }, ProjectionElem::Index(..)) => {
478 // Array indexes (`a[0]` vs. `a[i]`). These can either be disjoint
479 // (if the indexes differ) or equal (if they are the same).
481 PlaceConflictBias::Overlap => {
482 // If we are biased towards overlapping, then this is the recursive
483 // case that gives "equal *or* disjoint" its meaning.
484 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-INDEX");
485 Overlap::EqualOrDisjoint
487 PlaceConflictBias::NoOverlap => {
488 // If we are biased towards no overlapping, then this is disjoint.
489 debug!("place_element_conflict: DISJOINT-ARRAY-INDEX");
494 (ProjectionElem::ConstantIndex { offset: o1, min_length: _, from_end: false },
495 ProjectionElem::ConstantIndex { offset: o2, min_length: _, from_end: false })
496 | (ProjectionElem::ConstantIndex { offset: o1, min_length: _, from_end: true },
497 ProjectionElem::ConstantIndex {
498 offset: o2, min_length: _, from_end: true }) => {
500 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX");
501 Overlap::EqualOrDisjoint
503 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX");
507 (ProjectionElem::ConstantIndex {
508 offset: offset_from_begin, min_length: min_length1, from_end: false },
509 ProjectionElem::ConstantIndex {
510 offset: offset_from_end, min_length: min_length2, from_end: true })
511 | (ProjectionElem::ConstantIndex {
512 offset: offset_from_end, min_length: min_length1, from_end: true },
513 ProjectionElem::ConstantIndex {
514 offset: offset_from_begin, min_length: min_length2, from_end: false }) => {
515 // both patterns matched so it must be at least the greater of the two
516 let min_length = max(min_length1, min_length2);
517 // `offset_from_end` can be in range `[1..min_length]`, 1 indicates the last
518 // element (like -1 in Python) and `min_length` the first.
519 // Therefore, `min_length - offset_from_end` gives the minimal possible
520 // offset from the beginning
521 if *offset_from_begin >= min_length - offset_from_end {
522 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-FE");
523 Overlap::EqualOrDisjoint
525 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-FE");
529 (ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
530 ProjectionElem::Subslice {from, .. })
531 | (ProjectionElem::Subslice {from, .. },
532 ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false }) => {
535 "place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-SUBSLICE");
536 Overlap::EqualOrDisjoint
538 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-SUBSLICE");
542 (ProjectionElem::ConstantIndex { offset, min_length: _, from_end: true },
543 ProjectionElem::Subslice {from: _, to })
544 | (ProjectionElem::Subslice {from: _, to },
545 ProjectionElem::ConstantIndex { offset, min_length: _, from_end: true }) => {
547 debug!("place_element_conflict: \
548 DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-SUBSLICE-FE");
549 Overlap::EqualOrDisjoint
551 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-SUBSLICE-FE");
555 (ProjectionElem::Subslice { .. }, ProjectionElem::Subslice { .. }) => {
556 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-SUBSLICES");
557 Overlap::EqualOrDisjoint
559 (ProjectionElem::Deref, _)
560 | (ProjectionElem::Field(..), _)
561 | (ProjectionElem::Index(..), _)
562 | (ProjectionElem::ConstantIndex { .. }, _)
563 | (ProjectionElem::Subslice { .. }, _)
564 | (ProjectionElem::Downcast(..), _) => bug!(
565 "mismatched projections in place_element_conflict: {:?} and {:?}",
571 (Place::Projection(_), _) | (_, Place::Projection(_)) => bug!(
572 "unexpected elements in place_element_conflict: {:?} and {:?}",