1 use crate::borrow_check::ArtificialField;
2 use crate::borrow_check::Overlap;
3 use crate::borrow_check::{Deep, Shallow, AccessDepth};
6 BorrowKind, Body, Place, PlaceBase, Projection, ProjectionElem, ProjectionsIter,
9 use rustc::ty::{self, TyCtxt};
12 /// When checking if a place conflicts with another place, this enum is used to influence decisions
13 /// where a place might be equal or disjoint with another place, such as if `a[i] == a[j]`.
14 /// `PlaceConflictBias::Overlap` would bias toward assuming that `i` might equal `j` and that these
15 /// places overlap. `PlaceConflictBias::NoOverlap` assumes that for the purposes of the predicate
16 /// being run in the calling context, the conservative choice is to assume the compared indices
17 /// are disjoint (and therefore, do not overlap).
18 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
19 crate enum PlaceConflictBias {
24 /// Helper function for checking if places conflict with a mutable borrow and deep access depth.
25 /// This is used to check for places conflicting outside of the borrow checking code (such as in
27 crate fn places_conflict<'gcx, 'tcx>(
28 tcx: TyCtxt<'_, 'gcx, 'tcx>,
30 borrow_place: &Place<'tcx>,
31 access_place: &Place<'tcx>,
32 bias: PlaceConflictBias,
34 borrow_conflicts_with_place(
38 BorrowKind::Mut { allow_two_phase_borrow: true },
45 /// Checks whether the `borrow_place` conflicts with the `access_place` given a borrow kind and
46 /// access depth. The `bias` parameter is used to determine how the unknowable (comparing runtime
47 /// array indices, for example) should be interpreted - this depends on what the caller wants in
48 /// order to make the conservative choice and preserve soundness.
49 pub(super) fn borrow_conflicts_with_place<'gcx, 'tcx>(
50 tcx: TyCtxt<'_, 'gcx, 'tcx>,
52 borrow_place: &Place<'tcx>,
53 borrow_kind: BorrowKind,
54 access_place: &Place<'tcx>,
56 bias: PlaceConflictBias,
59 "borrow_conflicts_with_place({:?}, {:?}, {:?}, {:?})",
60 borrow_place, access_place, access, bias,
63 // This Local/Local case is handled by the more general code below, but
64 // it's so common that it's a speed win to check for it first.
65 if let Place::Base(PlaceBase::Local(l1)) = borrow_place {
66 if let Place::Base(PlaceBase::Local(l2)) = access_place {
71 borrow_place.iterate(|borrow_base, borrow_projections| {
72 access_place.iterate(|access_base, access_projections| {
73 place_components_conflict(
76 (borrow_base, borrow_projections),
78 (access_base, access_projections),
86 fn place_components_conflict<'gcx, 'tcx>(
87 tcx: TyCtxt<'_, 'gcx, 'tcx>,
89 borrow_projections: (&PlaceBase<'tcx>, ProjectionsIter<'_, 'tcx>),
90 borrow_kind: BorrowKind,
91 access_projections: (&PlaceBase<'tcx>, ProjectionsIter<'_, 'tcx>),
93 bias: PlaceConflictBias,
95 // The borrowck rules for proving disjointness are applied from the "root" of the
96 // borrow forwards, iterating over "similar" projections in lockstep until
97 // we can prove overlap one way or another. Essentially, we treat `Overlap` as
98 // a monoid and report a conflict if the product ends up not being `Disjoint`.
100 // At each step, if we didn't run out of borrow or place, we know that our elements
101 // have the same type, and that they only overlap if they are the identical.
103 // For example, if we are comparing these:
104 // BORROW: (*x1[2].y).z.a
105 // ACCESS: (*x1[i].y).w.b
107 // Then our steps are:
108 // x1 | x1 -- places are the same
109 // x1[2] | x1[i] -- equal or disjoint (disjoint if indexes differ)
110 // x1[2].y | x1[i].y -- equal or disjoint
111 // *x1[2].y | *x1[i].y -- equal or disjoint
112 // (*x1[2].y).z | (*x1[i].y).w -- we are disjoint and don't need to check more!
114 // Because `zip` does potentially bad things to the iterator inside, this loop
115 // also handles the case where the access might be a *prefix* of the borrow, e.g.
117 // BORROW: (*x1[2].y).z.a
120 // Then our steps are:
121 // x1 | x1 -- places are the same
122 // x1[2] | x1[i] -- equal or disjoint (disjoint if indexes differ)
123 // x1[2].y | x1[i].y -- equal or disjoint
125 // -- here we run out of access - the borrow can access a part of it. If this
126 // is a full deep access, then we *know* the borrow conflicts with it. However,
127 // if the access is shallow, then we can proceed:
129 // x1[2].y | (*x1[i].y) -- a deref! the access can't get past this, so we
132 // Our invariant is, that at each step of the iteration:
133 // - If we didn't run out of access to match, our borrow and access are comparable
134 // and either equal or disjoint.
135 // - If we did run out of access, the borrow can access a part of it.
137 let borrow_base = borrow_projections.0;
138 let access_base = access_projections.0;
140 match place_base_conflict(tcx, borrow_base, access_base) {
141 Overlap::Arbitrary => {
142 bug!("Two base can't return Arbitrary");
144 Overlap::EqualOrDisjoint => {
145 // This is the recursive case - proceed to the next element.
147 Overlap::Disjoint => {
148 // We have proven the borrow disjoint - further
149 // projections will remain disjoint.
150 debug!("borrow_conflicts_with_place: disjoint");
155 let mut borrow_projections = borrow_projections.1;
156 let mut access_projections = access_projections.1;
159 // loop invariant: borrow_c is always either equal to access_c or disjoint from it.
160 if let Some(borrow_c) = borrow_projections.next() {
161 debug!("borrow_conflicts_with_place: borrow_c = {:?}", borrow_c);
163 if let Some(access_c) = access_projections.next() {
164 debug!("borrow_conflicts_with_place: access_c = {:?}", access_c);
166 // Borrow and access path both have more components.
170 // - borrow of `a.(...)`, access to `a.(...)`
171 // - borrow of `a.(...)`, access to `b.(...)`
173 // Here we only see the components we have checked so
174 // far (in our examples, just the first component). We
175 // check whether the components being borrowed vs
176 // accessed are disjoint (as in the second example,
177 // but not the first).
178 match place_projection_conflict(tcx, mir, borrow_c, access_c, bias) {
179 Overlap::Arbitrary => {
180 // We have encountered different fields of potentially
181 // the same union - the borrow now partially overlaps.
183 // There is no *easy* way of comparing the fields
184 // further on, because they might have different types
185 // (e.g., borrows of `u.a.0` and `u.b.y` where `.0` and
186 // `.y` come from different structs).
188 // We could try to do some things here - e.g., count
189 // dereferences - but that's probably not a good
190 // idea, at least for now, so just give up and
191 // report a conflict. This is unsafe code anyway so
192 // the user could always use raw pointers.
193 debug!("borrow_conflicts_with_place: arbitrary -> conflict");
196 Overlap::EqualOrDisjoint => {
197 // This is the recursive case - proceed to the next element.
199 Overlap::Disjoint => {
200 // We have proven the borrow disjoint - further
201 // projections will remain disjoint.
202 debug!("borrow_conflicts_with_place: disjoint");
207 // Borrow path is longer than the access path. Examples:
209 // - borrow of `a.b.c`, access to `a.b`
211 // Here, we know that the borrow can access a part of
212 // our place. This is a conflict if that is a part our
213 // access cares about.
215 let base = &borrow_c.base;
216 let elem = &borrow_c.elem;
217 let base_ty = base.ty(mir, tcx).ty;
219 match (elem, &base_ty.sty, access) {
220 (_, _, Shallow(Some(ArtificialField::ArrayLength)))
221 | (_, _, Shallow(Some(ArtificialField::ShallowBorrow))) => {
222 // The array length is like additional fields on the
223 // type; it does not overlap any existing data there.
224 // Furthermore, if cannot actually be a prefix of any
225 // borrowed place (at least in MIR as it is currently.)
227 // e.g., a (mutable) borrow of `a[5]` while we read the
228 // array length of `a`.
229 debug!("borrow_conflicts_with_place: implicit field");
233 (ProjectionElem::Deref, _, Shallow(None)) => {
234 // e.g., a borrow of `*x.y` while we shallowly access `x.y` or some
235 // prefix thereof - the shallow access can't touch anything behind
237 debug!("borrow_conflicts_with_place: shallow access behind ptr");
240 (ProjectionElem::Deref, ty::Ref(_, _, hir::MutImmutable), _) => {
241 // Shouldn't be tracked
242 bug!("Tracking borrow behind shared reference.");
244 (ProjectionElem::Deref, ty::Ref(_, _, hir::MutMutable), AccessDepth::Drop) => {
245 // Values behind a mutable reference are not access either by dropping a
246 // value, or by StorageDead
247 debug!("borrow_conflicts_with_place: drop access behind ptr");
251 (ProjectionElem::Field { .. }, ty::Adt(def, _), AccessDepth::Drop) => {
252 // Drop can read/write arbitrary projections, so places
253 // conflict regardless of further projections.
254 if def.has_dtor(tcx) {
259 (ProjectionElem::Deref, _, Deep)
260 | (ProjectionElem::Deref, _, AccessDepth::Drop)
261 | (ProjectionElem::Field { .. }, _, _)
262 | (ProjectionElem::Index { .. }, _, _)
263 | (ProjectionElem::ConstantIndex { .. }, _, _)
264 | (ProjectionElem::Subslice { .. }, _, _)
265 | (ProjectionElem::Downcast { .. }, _, _) => {
266 // Recursive case. This can still be disjoint on a
267 // further iteration if this a shallow access and
268 // there's a deref later on, e.g., a borrow
269 // of `*x.y` while accessing `x`.
274 // Borrow path ran out but access path may not
277 // - borrow of `a.b`, access to `a.b.c`
278 // - borrow of `a.b`, access to `a.b`
280 // In the first example, where we didn't run out of
281 // access, the borrow can access all of our place, so we
284 // If the second example, where we did, then we still know
285 // that the borrow can access a *part* of our place that
286 // our access cares about, so we still have a conflict.
287 if borrow_kind == BorrowKind::Shallow && access_projections.next().is_some() {
288 debug!("borrow_conflicts_with_place: shallow borrow");
291 debug!("borrow_conflicts_with_place: full borrow, CONFLICT");
298 // Given that the bases of `elem1` and `elem2` are always either equal
299 // or disjoint (and have the same type!), return the overlap situation
300 // between `elem1` and `elem2`.
301 fn place_base_conflict<'a, 'gcx: 'tcx, 'tcx>(
302 tcx: TyCtxt<'a, 'gcx, 'tcx>,
303 elem1: &PlaceBase<'tcx>,
304 elem2: &PlaceBase<'tcx>,
306 match (elem1, elem2) {
307 (PlaceBase::Local(l1), PlaceBase::Local(l2)) => {
309 // the same local - base case, equal
310 debug!("place_element_conflict: DISJOINT-OR-EQ-LOCAL");
311 Overlap::EqualOrDisjoint
313 // different locals - base case, disjoint
314 debug!("place_element_conflict: DISJOINT-LOCAL");
318 (PlaceBase::Static(s1), PlaceBase::Static(s2)) => {
319 match (&s1.kind, &s2.kind) {
320 (StaticKind::Static(def_id_1), StaticKind::Static(def_id_2)) => {
321 if def_id_1 != def_id_2 {
322 debug!("place_element_conflict: DISJOINT-STATIC");
324 } else if tcx.is_mutable_static(*def_id_1) {
325 // We ignore mutable statics - they can only be unsafe code.
326 debug!("place_element_conflict: IGNORE-STATIC-MUT");
329 debug!("place_element_conflict: DISJOINT-OR-EQ-STATIC");
330 Overlap::EqualOrDisjoint
333 (StaticKind::Promoted(promoted_1), StaticKind::Promoted(promoted_2)) => {
334 if promoted_1 == promoted_2 {
335 if let ty::Array(_, len) = s1.ty.sty {
336 if let Some(0) = len.assert_usize(tcx) {
337 // Ignore conflicts with promoted [T; 0].
338 debug!("place_element_conflict: IGNORE-LEN-0-PROMOTED");
339 return Overlap::Disjoint;
342 // the same promoted - base case, equal
343 debug!("place_element_conflict: DISJOINT-OR-EQ-PROMOTED");
344 Overlap::EqualOrDisjoint
346 // different promoteds - base case, disjoint
347 debug!("place_element_conflict: DISJOINT-PROMOTED");
352 debug!("place_element_conflict: DISJOINT-STATIC-PROMOTED");
357 (PlaceBase::Local(_), PlaceBase::Static(_)) |
358 (PlaceBase::Static(_), PlaceBase::Local(_)) => {
359 debug!("place_element_conflict: DISJOINT-STATIC-LOCAL-PROMOTED");
365 // Given that the bases of `elem1` and `elem2` are always either equal
366 // or disjoint (and have the same type!), return the overlap situation
367 // between `elem1` and `elem2`.
368 fn place_projection_conflict<'a, 'gcx: 'tcx, 'tcx>(
369 tcx: TyCtxt<'a, 'gcx, 'tcx>,
371 pi1: &Projection<'tcx>,
372 pi2: &Projection<'tcx>,
373 bias: PlaceConflictBias,
375 match (&pi1.elem, &pi2.elem) {
376 (ProjectionElem::Deref, ProjectionElem::Deref) => {
377 // derefs (e.g., `*x` vs. `*x`) - recur.
378 debug!("place_element_conflict: DISJOINT-OR-EQ-DEREF");
379 Overlap::EqualOrDisjoint
381 (ProjectionElem::Field(f1, _), ProjectionElem::Field(f2, _)) => {
383 // same field (e.g., `a.y` vs. `a.y`) - recur.
384 debug!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
385 Overlap::EqualOrDisjoint
387 let ty = pi1.base.ty(mir, tcx).ty;
389 ty::Adt(def, _) if def.is_union() => {
390 // Different fields of a union, we are basically stuck.
391 debug!("place_element_conflict: STUCK-UNION");
395 // Different fields of a struct (`a.x` vs. `a.y`). Disjoint!
396 debug!("place_element_conflict: DISJOINT-FIELD");
402 (ProjectionElem::Downcast(_, v1), ProjectionElem::Downcast(_, v2)) => {
403 // different variants are treated as having disjoint fields,
404 // even if they occupy the same "space", because it's
405 // impossible for 2 variants of the same enum to exist
406 // (and therefore, to be borrowed) at the same time.
408 // Note that this is different from unions - we *do* allow
409 // this code to compile:
412 // fn foo(x: &mut Result<i32, i32>) {
414 // if let Ok(ref mut a) = *x {
417 // // here, you would *think* that the
418 // // *entirety* of `x` would be borrowed,
419 // // but in fact only the `Ok` variant is,
420 // // so the `Err` variant is *entirely free*:
421 // if let Err(ref mut a) = *x {
428 debug!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
429 Overlap::EqualOrDisjoint
431 debug!("place_element_conflict: DISJOINT-FIELD");
435 (ProjectionElem::Index(..), ProjectionElem::Index(..))
436 | (ProjectionElem::Index(..), ProjectionElem::ConstantIndex { .. })
437 | (ProjectionElem::Index(..), ProjectionElem::Subslice { .. })
438 | (ProjectionElem::ConstantIndex { .. }, ProjectionElem::Index(..))
439 | (ProjectionElem::Subslice { .. }, ProjectionElem::Index(..)) => {
440 // Array indexes (`a[0]` vs. `a[i]`). These can either be disjoint
441 // (if the indexes differ) or equal (if they are the same).
443 PlaceConflictBias::Overlap => {
444 // If we are biased towards overlapping, then this is the recursive
445 // case that gives "equal *or* disjoint" its meaning.
446 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-INDEX");
447 Overlap::EqualOrDisjoint
449 PlaceConflictBias::NoOverlap => {
450 // If we are biased towards no overlapping, then this is disjoint.
451 debug!("place_element_conflict: DISJOINT-ARRAY-INDEX");
456 (ProjectionElem::ConstantIndex { offset: o1, min_length: _, from_end: false },
457 ProjectionElem::ConstantIndex { offset: o2, min_length: _, from_end: false })
458 | (ProjectionElem::ConstantIndex { offset: o1, min_length: _, from_end: true },
459 ProjectionElem::ConstantIndex {
460 offset: o2, min_length: _, from_end: true }) => {
462 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX");
463 Overlap::EqualOrDisjoint
465 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX");
469 (ProjectionElem::ConstantIndex {
470 offset: offset_from_begin, min_length: min_length1, from_end: false },
471 ProjectionElem::ConstantIndex {
472 offset: offset_from_end, min_length: min_length2, from_end: true })
473 | (ProjectionElem::ConstantIndex {
474 offset: offset_from_end, min_length: min_length1, from_end: true },
475 ProjectionElem::ConstantIndex {
476 offset: offset_from_begin, min_length: min_length2, from_end: false }) => {
477 // both patterns matched so it must be at least the greater of the two
478 let min_length = max(min_length1, min_length2);
479 // `offset_from_end` can be in range `[1..min_length]`, 1 indicates the last
480 // element (like -1 in Python) and `min_length` the first.
481 // Therefore, `min_length - offset_from_end` gives the minimal possible
482 // offset from the beginning
483 if *offset_from_begin >= min_length - offset_from_end {
484 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-FE");
485 Overlap::EqualOrDisjoint
487 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-FE");
491 (ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
492 ProjectionElem::Subslice {from, .. })
493 | (ProjectionElem::Subslice {from, .. },
494 ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false }) => {
497 "place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-SUBSLICE");
498 Overlap::EqualOrDisjoint
500 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-SUBSLICE");
504 (ProjectionElem::ConstantIndex { offset, min_length: _, from_end: true },
505 ProjectionElem::Subslice {from: _, to })
506 | (ProjectionElem::Subslice {from: _, to },
507 ProjectionElem::ConstantIndex { offset, min_length: _, from_end: true }) => {
509 debug!("place_element_conflict: \
510 DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-SUBSLICE-FE");
511 Overlap::EqualOrDisjoint
513 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-SUBSLICE-FE");
517 (ProjectionElem::Subslice { .. }, ProjectionElem::Subslice { .. }) => {
518 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-SUBSLICES");
519 Overlap::EqualOrDisjoint
521 (ProjectionElem::Deref, _)
522 | (ProjectionElem::Field(..), _)
523 | (ProjectionElem::Index(..), _)
524 | (ProjectionElem::ConstantIndex { .. }, _)
525 | (ProjectionElem::Subslice { .. }, _)
526 | (ProjectionElem::Downcast(..), _) => bug!(
527 "mismatched projections in place_element_conflict: {:?} and {:?}",