1 #![deny(rustc::untranslatable_diagnostic)]
2 #![deny(rustc::diagnostic_outside_of_impl)]
3 use crate::ArtificialField;
5 use crate::{AccessDepth, Deep, Shallow};
7 use rustc_middle::mir::{Body, BorrowKind, Local, Place, PlaceElem, PlaceRef, ProjectionElem};
8 use rustc_middle::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 pub(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 pub(crate) fn places_conflict<'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 },
39 access_place.as_ref(),
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 #[instrument(level = "debug", skip(tcx, body))]
50 pub(super) fn borrow_conflicts_with_place<'tcx>(
53 borrow_place: Place<'tcx>,
54 borrow_kind: BorrowKind,
55 access_place: PlaceRef<'tcx>,
57 bias: PlaceConflictBias,
59 // This Local/Local case is handled by the more general code below, but
60 // it's so common that it's a speed win to check for it first.
61 if let Some(l1) = borrow_place.as_local() && let Some(l2) = access_place.as_local() {
65 place_components_conflict(tcx, body, borrow_place, borrow_kind, access_place, access, bias)
68 fn place_components_conflict<'tcx>(
71 borrow_place: Place<'tcx>,
72 borrow_kind: BorrowKind,
73 access_place: PlaceRef<'tcx>,
75 bias: PlaceConflictBias,
77 // The borrowck rules for proving disjointness are applied from the "root" of the
78 // borrow forwards, iterating over "similar" projections in lockstep until
79 // we can prove overlap one way or another. Essentially, we treat `Overlap` as
80 // a monoid and report a conflict if the product ends up not being `Disjoint`.
82 // At each step, if we didn't run out of borrow or place, we know that our elements
83 // have the same type, and that they only overlap if they are the identical.
85 // For example, if we are comparing these:
86 // BORROW: (*x1[2].y).z.a
87 // ACCESS: (*x1[i].y).w.b
89 // Then our steps are:
90 // x1 | x1 -- places are the same
91 // x1[2] | x1[i] -- equal or disjoint (disjoint if indexes differ)
92 // x1[2].y | x1[i].y -- equal or disjoint
93 // *x1[2].y | *x1[i].y -- equal or disjoint
94 // (*x1[2].y).z | (*x1[i].y).w -- we are disjoint and don't need to check more!
96 // Because `zip` does potentially bad things to the iterator inside, this loop
97 // also handles the case where the access might be a *prefix* of the borrow, e.g.
99 // BORROW: (*x1[2].y).z.a
102 // Then our steps are:
103 // x1 | x1 -- places are the same
104 // x1[2] | x1[i] -- equal or disjoint (disjoint if indexes differ)
105 // x1[2].y | x1[i].y -- equal or disjoint
107 // -- here we run out of access - the borrow can access a part of it. If this
108 // is a full deep access, then we *know* the borrow conflicts with it. However,
109 // if the access is shallow, then we can proceed:
111 // x1[2].y | (*x1[i].y) -- a deref! the access can't get past this, so we
114 // Our invariant is, that at each step of the iteration:
115 // - If we didn't run out of access to match, our borrow and access are comparable
116 // and either equal or disjoint.
117 // - If we did run out of access, the borrow can access a part of it.
119 let borrow_local = borrow_place.local;
120 let access_local = access_place.local;
122 match place_base_conflict(borrow_local, access_local) {
123 Overlap::Arbitrary => {
124 bug!("Two base can't return Arbitrary");
126 Overlap::EqualOrDisjoint => {
127 // This is the recursive case - proceed to the next element.
129 Overlap::Disjoint => {
130 // We have proven the borrow disjoint - further
131 // projections will remain disjoint.
132 debug!("borrow_conflicts_with_place: disjoint");
137 // loop invariant: borrow_c is always either equal to access_c or disjoint from it.
138 for (i, (borrow_c, &access_c)) in
139 iter::zip(borrow_place.projection, access_place.projection).enumerate()
141 debug!(?borrow_c, ?access_c);
143 let borrow_proj_base = &borrow_place.projection[..i];
145 // Borrow and access path both have more components.
149 // - borrow of `a.(...)`, access to `a.(...)`
150 // - borrow of `a.(...)`, access to `b.(...)`
152 // Here we only see the components we have checked so
153 // far (in our examples, just the first component). We
154 // check whether the components being borrowed vs
155 // accessed are disjoint (as in the second example,
156 // but not the first).
157 match place_projection_conflict(
166 Overlap::Arbitrary => {
167 // We have encountered different fields of potentially
168 // the same union - the borrow now partially overlaps.
170 // There is no *easy* way of comparing the fields
171 // further on, because they might have different types
172 // (e.g., borrows of `u.a.0` and `u.b.y` where `.0` and
173 // `.y` come from different structs).
175 // We could try to do some things here - e.g., count
176 // dereferences - but that's probably not a good
177 // idea, at least for now, so just give up and
178 // report a conflict. This is unsafe code anyway so
179 // the user could always use raw pointers.
180 debug!("arbitrary -> conflict");
183 Overlap::EqualOrDisjoint => {
184 // This is the recursive case - proceed to the next element.
186 Overlap::Disjoint => {
187 // We have proven the borrow disjoint - further
188 // projections will remain disjoint.
195 if borrow_place.projection.len() > access_place.projection.len() {
196 for (i, elem) in borrow_place.projection[access_place.projection.len()..].iter().enumerate()
198 // Borrow path is longer than the access path. Examples:
200 // - borrow of `a.b.c`, access to `a.b`
202 // Here, we know that the borrow can access a part of
203 // our place. This is a conflict if that is a part our
204 // access cares about.
206 let proj_base = &borrow_place.projection[..access_place.projection.len() + i];
207 let base_ty = Place::ty_from(borrow_local, proj_base, body, tcx).ty;
209 match (elem, &base_ty.kind(), access) {
210 (_, _, Shallow(Some(ArtificialField::ArrayLength)))
211 | (_, _, Shallow(Some(ArtificialField::ShallowBorrow))) => {
212 // The array length is like additional fields on the
213 // type; it does not overlap any existing data there.
214 // Furthermore, if cannot actually be a prefix of any
215 // borrowed place (at least in MIR as it is currently.)
217 // e.g., a (mutable) borrow of `a[5]` while we read the
218 // array length of `a`.
219 debug!("borrow_conflicts_with_place: implicit field");
223 (ProjectionElem::Deref, _, Shallow(None)) => {
224 // e.g., a borrow of `*x.y` while we shallowly access `x.y` or some
225 // prefix thereof - the shallow access can't touch anything behind
227 debug!("borrow_conflicts_with_place: shallow access behind ptr");
230 (ProjectionElem::Deref, ty::Ref(_, _, hir::Mutability::Not), _) => {
231 // Shouldn't be tracked
232 bug!("Tracking borrow behind shared reference.");
234 (ProjectionElem::Deref, ty::Ref(_, _, hir::Mutability::Mut), AccessDepth::Drop) => {
235 // Values behind a mutable reference are not access either by dropping a
236 // value, or by StorageDead
237 debug!("borrow_conflicts_with_place: drop access behind ptr");
241 (ProjectionElem::Field { .. }, ty::Adt(def, _), AccessDepth::Drop) => {
242 // Drop can read/write arbitrary projections, so places
243 // conflict regardless of further projections.
244 if def.has_dtor(tcx) {
249 (ProjectionElem::Deref, _, Deep)
250 | (ProjectionElem::Deref, _, AccessDepth::Drop)
251 | (ProjectionElem::Field { .. }, _, _)
252 | (ProjectionElem::Index { .. }, _, _)
253 | (ProjectionElem::ConstantIndex { .. }, _, _)
254 | (ProjectionElem::Subslice { .. }, _, _)
255 | (ProjectionElem::OpaqueCast { .. }, _, _)
256 | (ProjectionElem::Downcast { .. }, _, _) => {
257 // Recursive case. This can still be disjoint on a
258 // further iteration if this a shallow access and
259 // there's a deref later on, e.g., a borrow
260 // of `*x.y` while accessing `x`.
266 // Borrow path ran out but access path may not
269 // - borrow of `a.b`, access to `a.b.c`
270 // - borrow of `a.b`, access to `a.b`
272 // In the first example, where we didn't run out of
273 // access, the borrow can access all of our place, so we
276 // If the second example, where we did, then we still know
277 // that the borrow can access a *part* of our place that
278 // our access cares about, so we still have a conflict.
279 if borrow_kind == BorrowKind::Shallow
280 && borrow_place.projection.len() < access_place.projection.len()
282 debug!("borrow_conflicts_with_place: shallow borrow");
285 debug!("borrow_conflicts_with_place: full borrow, CONFLICT");
290 // Given that the bases of `elem1` and `elem2` are always either equal
291 // or disjoint (and have the same type!), return the overlap situation
292 // between `elem1` and `elem2`.
293 fn place_base_conflict(l1: Local, l2: Local) -> Overlap {
295 // the same local - base case, equal
296 debug!("place_element_conflict: DISJOINT-OR-EQ-LOCAL");
297 Overlap::EqualOrDisjoint
299 // different locals - base case, disjoint
300 debug!("place_element_conflict: DISJOINT-LOCAL");
305 // Given that the bases of `elem1` and `elem2` are always either equal
306 // or disjoint (and have the same type!), return the overlap situation
307 // between `elem1` and `elem2`.
308 fn place_projection_conflict<'tcx>(
312 pi1_proj_base: &[PlaceElem<'tcx>],
313 pi1_elem: PlaceElem<'tcx>,
314 pi2_elem: PlaceElem<'tcx>,
315 bias: PlaceConflictBias,
317 match (pi1_elem, pi2_elem) {
318 (ProjectionElem::Deref, ProjectionElem::Deref) => {
319 // derefs (e.g., `*x` vs. `*x`) - recur.
320 debug!("place_element_conflict: DISJOINT-OR-EQ-DEREF");
321 Overlap::EqualOrDisjoint
323 (ProjectionElem::OpaqueCast(v1), ProjectionElem::OpaqueCast(v2)) => {
325 // same type - recur.
326 debug!("place_element_conflict: DISJOINT-OR-EQ-OPAQUE");
327 Overlap::EqualOrDisjoint
329 // Different types. Disjoint!
330 debug!("place_element_conflict: DISJOINT-OPAQUE");
334 (ProjectionElem::Field(f1, _), ProjectionElem::Field(f2, _)) => {
336 // same field (e.g., `a.y` vs. `a.y`) - recur.
337 debug!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
338 Overlap::EqualOrDisjoint
340 let ty = Place::ty_from(pi1_local, pi1_proj_base, body, tcx).ty;
342 // Different fields of a union, we are basically stuck.
343 debug!("place_element_conflict: STUCK-UNION");
346 // Different fields of a struct (`a.x` vs. `a.y`). Disjoint!
347 debug!("place_element_conflict: DISJOINT-FIELD");
352 (ProjectionElem::Downcast(_, v1), ProjectionElem::Downcast(_, v2)) => {
353 // different variants are treated as having disjoint fields,
354 // even if they occupy the same "space", because it's
355 // impossible for 2 variants of the same enum to exist
356 // (and therefore, to be borrowed) at the same time.
358 // Note that this is different from unions - we *do* allow
359 // this code to compile:
362 // fn foo(x: &mut Result<i32, i32>) {
364 // if let Ok(ref mut a) = *x {
367 // // here, you would *think* that the
368 // // *entirety* of `x` would be borrowed,
369 // // but in fact only the `Ok` variant is,
370 // // so the `Err` variant is *entirely free*:
371 // if let Err(ref mut a) = *x {
378 debug!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
379 Overlap::EqualOrDisjoint
381 debug!("place_element_conflict: DISJOINT-FIELD");
386 ProjectionElem::Index(..),
387 ProjectionElem::Index(..)
388 | ProjectionElem::ConstantIndex { .. }
389 | ProjectionElem::Subslice { .. },
392 ProjectionElem::ConstantIndex { .. } | ProjectionElem::Subslice { .. },
393 ProjectionElem::Index(..),
395 // Array indexes (`a[0]` vs. `a[i]`). These can either be disjoint
396 // (if the indexes differ) or equal (if they are the same).
398 PlaceConflictBias::Overlap => {
399 // If we are biased towards overlapping, then this is the recursive
400 // case that gives "equal *or* disjoint" its meaning.
401 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-INDEX");
402 Overlap::EqualOrDisjoint
404 PlaceConflictBias::NoOverlap => {
405 // If we are biased towards no overlapping, then this is disjoint.
406 debug!("place_element_conflict: DISJOINT-ARRAY-INDEX");
412 ProjectionElem::ConstantIndex { offset: o1, min_length: _, from_end: false },
413 ProjectionElem::ConstantIndex { offset: o2, min_length: _, from_end: false },
416 ProjectionElem::ConstantIndex { offset: o1, min_length: _, from_end: true },
417 ProjectionElem::ConstantIndex { offset: o2, min_length: _, from_end: true },
420 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX");
421 Overlap::EqualOrDisjoint
423 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX");
428 ProjectionElem::ConstantIndex {
429 offset: offset_from_begin,
430 min_length: min_length1,
433 ProjectionElem::ConstantIndex {
434 offset: offset_from_end,
435 min_length: min_length2,
440 ProjectionElem::ConstantIndex {
441 offset: offset_from_end,
442 min_length: min_length1,
445 ProjectionElem::ConstantIndex {
446 offset: offset_from_begin,
447 min_length: min_length2,
451 // both patterns matched so it must be at least the greater of the two
452 let min_length = max(min_length1, min_length2);
453 // `offset_from_end` can be in range `[1..min_length]`, 1 indicates the last
454 // element (like -1 in Python) and `min_length` the first.
455 // Therefore, `min_length - offset_from_end` gives the minimal possible
456 // offset from the beginning
457 if offset_from_begin >= min_length - offset_from_end {
458 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-FE");
459 Overlap::EqualOrDisjoint
461 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-FE");
466 ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
467 ProjectionElem::Subslice { from, to, from_end: false },
470 ProjectionElem::Subslice { from, to, from_end: false },
471 ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
473 if (from..to).contains(&offset) {
474 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-SUBSLICE");
475 Overlap::EqualOrDisjoint
477 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-SUBSLICE");
482 ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
483 ProjectionElem::Subslice { from, .. },
486 ProjectionElem::Subslice { from, .. },
487 ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
490 debug!("place_element_conflict: DISJOINT-OR-EQ-SLICE-CONSTANT-INDEX-SUBSLICE");
491 Overlap::EqualOrDisjoint
493 debug!("place_element_conflict: DISJOINT-SLICE-CONSTANT-INDEX-SUBSLICE");
498 ProjectionElem::ConstantIndex { offset, min_length: _, from_end: true },
499 ProjectionElem::Subslice { to, from_end: true, .. },
502 ProjectionElem::Subslice { to, from_end: true, .. },
503 ProjectionElem::ConstantIndex { offset, min_length: _, from_end: true },
507 "place_element_conflict: \
508 DISJOINT-OR-EQ-SLICE-CONSTANT-INDEX-SUBSLICE-FE"
510 Overlap::EqualOrDisjoint
512 debug!("place_element_conflict: DISJOINT-SLICE-CONSTANT-INDEX-SUBSLICE-FE");
517 ProjectionElem::Subslice { from: f1, to: t1, from_end: false },
518 ProjectionElem::Subslice { from: f2, to: t2, from_end: false },
520 if f2 >= t1 || f1 >= t2 {
521 debug!("place_element_conflict: DISJOINT-ARRAY-SUBSLICES");
524 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-SUBSLICES");
525 Overlap::EqualOrDisjoint
528 (ProjectionElem::Subslice { .. }, ProjectionElem::Subslice { .. }) => {
529 debug!("place_element_conflict: DISJOINT-OR-EQ-SLICE-SUBSLICES");
530 Overlap::EqualOrDisjoint
533 ProjectionElem::Deref
534 | ProjectionElem::Field(..)
535 | ProjectionElem::Index(..)
536 | ProjectionElem::ConstantIndex { .. }
537 | ProjectionElem::OpaqueCast { .. }
538 | ProjectionElem::Subslice { .. }
539 | ProjectionElem::Downcast(..),
542 "mismatched projections in place_element_conflict: {:?} and {:?}",