1 use crate::ArtificialField
;
3 use crate::{AccessDepth, Deep, Shallow}
;
5 use rustc_middle
::mir
::{Body, BorrowKind, Local, Place, PlaceElem, PlaceRef, ProjectionElem}
;
6 use rustc_middle
::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
<'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 }
,
37 access_place
.as_ref(),
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
<'tcx
>(
50 borrow_place
: Place
<'tcx
>,
51 borrow_kind
: BorrowKind
,
52 access_place
: PlaceRef
<'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 Some(l1
) = borrow_place
.as_local() {
64 if let Some(l2
) = access_place
.as_local() {
69 place_components_conflict(tcx
, body
, borrow_place
, borrow_kind
, access_place
, access
, bias
)
72 fn place_components_conflict
<'tcx
>(
75 borrow_place
: Place
<'tcx
>,
76 borrow_kind
: BorrowKind
,
77 access_place
: PlaceRef
<'tcx
>,
79 bias
: PlaceConflictBias
,
81 // The borrowck rules for proving disjointness are applied from the "root" of the
82 // borrow forwards, iterating over "similar" projections in lockstep until
83 // we can prove overlap one way or another. Essentially, we treat `Overlap` as
84 // a monoid and report a conflict if the product ends up not being `Disjoint`.
86 // At each step, if we didn't run out of borrow or place, we know that our elements
87 // have the same type, and that they only overlap if they are the identical.
89 // For example, if we are comparing these:
90 // BORROW: (*x1[2].y).z.a
91 // ACCESS: (*x1[i].y).w.b
93 // Then our steps are:
94 // x1 | x1 -- places are the same
95 // x1[2] | x1[i] -- equal or disjoint (disjoint if indexes differ)
96 // x1[2].y | x1[i].y -- equal or disjoint
97 // *x1[2].y | *x1[i].y -- equal or disjoint
98 // (*x1[2].y).z | (*x1[i].y).w -- we are disjoint and don't need to check more!
100 // Because `zip` does potentially bad things to the iterator inside, this loop
101 // also handles the case where the access might be a *prefix* of the borrow, e.g.
103 // BORROW: (*x1[2].y).z.a
106 // Then our steps are:
107 // x1 | x1 -- places are the same
108 // x1[2] | x1[i] -- equal or disjoint (disjoint if indexes differ)
109 // x1[2].y | x1[i].y -- equal or disjoint
111 // -- here we run out of access - the borrow can access a part of it. If this
112 // is a full deep access, then we *know* the borrow conflicts with it. However,
113 // if the access is shallow, then we can proceed:
115 // x1[2].y | (*x1[i].y) -- a deref! the access can't get past this, so we
118 // Our invariant is, that at each step of the iteration:
119 // - If we didn't run out of access to match, our borrow and access are comparable
120 // and either equal or disjoint.
121 // - If we did run out of access, the borrow can access a part of it.
123 let borrow_local
= borrow_place
.local
;
124 let access_local
= access_place
.local
;
126 match place_base_conflict(borrow_local
, access_local
) {
127 Overlap
::Arbitrary
=> {
128 bug
!("Two base can't return Arbitrary");
130 Overlap
::EqualOrDisjoint
=> {
131 // This is the recursive case - proceed to the next element.
133 Overlap
::Disjoint
=> {
134 // We have proven the borrow disjoint - further
135 // projections will remain disjoint.
136 debug
!("borrow_conflicts_with_place: disjoint");
141 // loop invariant: borrow_c is always either equal to access_c or disjoint from it.
142 for (i
, (borrow_c
, &access_c
)) in
143 iter
::zip(borrow_place
.projection
, access_place
.projection
).enumerate()
145 debug
!("borrow_conflicts_with_place: borrow_c = {:?}", borrow_c
);
146 let borrow_proj_base
= &borrow_place
.projection
[..i
];
148 debug
!("borrow_conflicts_with_place: access_c = {:?}", access_c
);
150 // Borrow and access path both have more components.
154 // - borrow of `a.(...)`, access to `a.(...)`
155 // - borrow of `a.(...)`, access to `b.(...)`
157 // Here we only see the components we have checked so
158 // far (in our examples, just the first component). We
159 // check whether the components being borrowed vs
160 // accessed are disjoint (as in the second example,
161 // but not the first).
162 match place_projection_conflict(
171 Overlap
::Arbitrary
=> {
172 // We have encountered different fields of potentially
173 // the same union - the borrow now partially overlaps.
175 // There is no *easy* way of comparing the fields
176 // further on, because they might have different types
177 // (e.g., borrows of `u.a.0` and `u.b.y` where `.0` and
178 // `.y` come from different structs).
180 // We could try to do some things here - e.g., count
181 // dereferences - but that's probably not a good
182 // idea, at least for now, so just give up and
183 // report a conflict. This is unsafe code anyway so
184 // the user could always use raw pointers.
185 debug
!("borrow_conflicts_with_place: arbitrary -> conflict");
188 Overlap
::EqualOrDisjoint
=> {
189 // This is the recursive case - proceed to the next element.
191 Overlap
::Disjoint
=> {
192 // We have proven the borrow disjoint - further
193 // projections will remain disjoint.
194 debug
!("borrow_conflicts_with_place: disjoint");
200 if borrow_place
.projection
.len() > access_place
.projection
.len() {
201 for (i
, elem
) in borrow_place
.projection
[access_place
.projection
.len()..].iter().enumerate()
203 // Borrow path is longer than the access path. Examples:
205 // - borrow of `a.b.c`, access to `a.b`
207 // Here, we know that the borrow can access a part of
208 // our place. This is a conflict if that is a part our
209 // access cares about.
211 let proj_base
= &borrow_place
.projection
[..access_place
.projection
.len() + i
];
212 let base_ty
= Place
::ty_from(borrow_local
, proj_base
, body
, tcx
).ty
;
214 match (elem
, &base_ty
.kind(), access
) {
215 (_
, _
, Shallow(Some(ArtificialField
::ArrayLength
)))
216 | (_
, _
, Shallow(Some(ArtificialField
::ShallowBorrow
))) => {
217 // The array length is like additional fields on the
218 // type; it does not overlap any existing data there.
219 // Furthermore, if cannot actually be a prefix of any
220 // borrowed place (at least in MIR as it is currently.)
222 // e.g., a (mutable) borrow of `a[5]` while we read the
223 // array length of `a`.
224 debug
!("borrow_conflicts_with_place: implicit field");
228 (ProjectionElem
::Deref
, _
, Shallow(None
)) => {
229 // e.g., a borrow of `*x.y` while we shallowly access `x.y` or some
230 // prefix thereof - the shallow access can't touch anything behind
232 debug
!("borrow_conflicts_with_place: shallow access behind ptr");
235 (ProjectionElem
::Deref
, ty
::Ref(_
, _
, hir
::Mutability
::Not
), _
) => {
236 // Shouldn't be tracked
237 bug
!("Tracking borrow behind shared reference.");
239 (ProjectionElem
::Deref
, ty
::Ref(_
, _
, hir
::Mutability
::Mut
), AccessDepth
::Drop
) => {
240 // Values behind a mutable reference are not access either by dropping a
241 // value, or by StorageDead
242 debug
!("borrow_conflicts_with_place: drop access behind ptr");
246 (ProjectionElem
::Field { .. }
, ty
::Adt(def
, _
), AccessDepth
::Drop
) => {
247 // Drop can read/write arbitrary projections, so places
248 // conflict regardless of further projections.
249 if def
.has_dtor(tcx
) {
254 (ProjectionElem
::Deref
, _
, Deep
)
255 | (ProjectionElem
::Deref
, _
, AccessDepth
::Drop
)
256 | (ProjectionElem
::Field { .. }
, _
, _
)
257 | (ProjectionElem
::Index { .. }
, _
, _
)
258 | (ProjectionElem
::ConstantIndex { .. }
, _
, _
)
259 | (ProjectionElem
::Subslice { .. }
, _
, _
)
260 | (ProjectionElem
::Downcast { .. }
, _
, _
) => {
261 // Recursive case. This can still be disjoint on a
262 // further iteration if this a shallow access and
263 // there's a deref later on, e.g., a borrow
264 // of `*x.y` while accessing `x`.
270 // Borrow path ran out but access path may not
273 // - borrow of `a.b`, access to `a.b.c`
274 // - borrow of `a.b`, access to `a.b`
276 // In the first example, where we didn't run out of
277 // access, the borrow can access all of our place, so we
280 // If the second example, where we did, then we still know
281 // that the borrow can access a *part* of our place that
282 // our access cares about, so we still have a conflict.
283 if borrow_kind
== BorrowKind
::Shallow
284 && borrow_place
.projection
.len() < access_place
.projection
.len()
286 debug
!("borrow_conflicts_with_place: shallow borrow");
289 debug
!("borrow_conflicts_with_place: full borrow, CONFLICT");
294 // Given that the bases of `elem1` and `elem2` are always either equal
295 // or disjoint (and have the same type!), return the overlap situation
296 // between `elem1` and `elem2`.
297 fn place_base_conflict(l1
: Local
, l2
: Local
) -> Overlap
{
299 // the same local - base case, equal
300 debug
!("place_element_conflict: DISJOINT-OR-EQ-LOCAL");
301 Overlap
::EqualOrDisjoint
303 // different locals - base case, disjoint
304 debug
!("place_element_conflict: DISJOINT-LOCAL");
309 // Given that the bases of `elem1` and `elem2` are always either equal
310 // or disjoint (and have the same type!), return the overlap situation
311 // between `elem1` and `elem2`.
312 fn place_projection_conflict
<'tcx
>(
316 pi1_proj_base
: &[PlaceElem
<'tcx
>],
317 pi1_elem
: PlaceElem
<'tcx
>,
318 pi2_elem
: PlaceElem
<'tcx
>,
319 bias
: PlaceConflictBias
,
321 match (pi1_elem
, pi2_elem
) {
322 (ProjectionElem
::Deref
, ProjectionElem
::Deref
) => {
323 // derefs (e.g., `*x` vs. `*x`) - recur.
324 debug
!("place_element_conflict: DISJOINT-OR-EQ-DEREF");
325 Overlap
::EqualOrDisjoint
327 (ProjectionElem
::Field(f1
, _
), ProjectionElem
::Field(f2
, _
)) => {
329 // same field (e.g., `a.y` vs. `a.y`) - recur.
330 debug
!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
331 Overlap
::EqualOrDisjoint
333 let ty
= Place
::ty_from(pi1_local
, pi1_proj_base
, body
, tcx
).ty
;
335 // Different fields of a union, we are basically stuck.
336 debug
!("place_element_conflict: STUCK-UNION");
339 // Different fields of a struct (`a.x` vs. `a.y`). Disjoint!
340 debug
!("place_element_conflict: DISJOINT-FIELD");
345 (ProjectionElem
::Downcast(_
, v1
), ProjectionElem
::Downcast(_
, v2
)) => {
346 // different variants are treated as having disjoint fields,
347 // even if they occupy the same "space", because it's
348 // impossible for 2 variants of the same enum to exist
349 // (and therefore, to be borrowed) at the same time.
351 // Note that this is different from unions - we *do* allow
352 // this code to compile:
355 // fn foo(x: &mut Result<i32, i32>) {
357 // if let Ok(ref mut a) = *x {
360 // // here, you would *think* that the
361 // // *entirety* of `x` would be borrowed,
362 // // but in fact only the `Ok` variant is,
363 // // so the `Err` variant is *entirely free*:
364 // if let Err(ref mut a) = *x {
371 debug
!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
372 Overlap
::EqualOrDisjoint
374 debug
!("place_element_conflict: DISJOINT-FIELD");
379 ProjectionElem
::Index(..),
380 ProjectionElem
::Index(..)
381 | ProjectionElem
::ConstantIndex { .. }
382 | ProjectionElem
::Subslice { .. }
,
385 ProjectionElem
::ConstantIndex { .. }
| ProjectionElem
::Subslice { .. }
,
386 ProjectionElem
::Index(..),
388 // Array indexes (`a[0]` vs. `a[i]`). These can either be disjoint
389 // (if the indexes differ) or equal (if they are the same).
391 PlaceConflictBias
::Overlap
=> {
392 // If we are biased towards overlapping, then this is the recursive
393 // case that gives "equal *or* disjoint" its meaning.
394 debug
!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-INDEX");
395 Overlap
::EqualOrDisjoint
397 PlaceConflictBias
::NoOverlap
=> {
398 // If we are biased towards no overlapping, then this is disjoint.
399 debug
!("place_element_conflict: DISJOINT-ARRAY-INDEX");
405 ProjectionElem
::ConstantIndex { offset: o1, min_length: _, from_end: false }
,
406 ProjectionElem
::ConstantIndex { offset: o2, min_length: _, from_end: false }
,
409 ProjectionElem
::ConstantIndex { offset: o1, min_length: _, from_end: true }
,
410 ProjectionElem
::ConstantIndex { offset: o2, min_length: _, from_end: true }
,
413 debug
!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX");
414 Overlap
::EqualOrDisjoint
416 debug
!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX");
421 ProjectionElem
::ConstantIndex
{
422 offset
: offset_from_begin
,
423 min_length
: min_length1
,
426 ProjectionElem
::ConstantIndex
{
427 offset
: offset_from_end
,
428 min_length
: min_length2
,
433 ProjectionElem
::ConstantIndex
{
434 offset
: offset_from_end
,
435 min_length
: min_length1
,
438 ProjectionElem
::ConstantIndex
{
439 offset
: offset_from_begin
,
440 min_length
: min_length2
,
444 // both patterns matched so it must be at least the greater of the two
445 let min_length
= max(min_length1
, min_length2
);
446 // `offset_from_end` can be in range `[1..min_length]`, 1 indicates the last
447 // element (like -1 in Python) and `min_length` the first.
448 // Therefore, `min_length - offset_from_end` gives the minimal possible
449 // offset from the beginning
450 if offset_from_begin
>= min_length
- offset_from_end
{
451 debug
!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-FE");
452 Overlap
::EqualOrDisjoint
454 debug
!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-FE");
459 ProjectionElem
::ConstantIndex { offset, min_length: _, from_end: false }
,
460 ProjectionElem
::Subslice { from, to, from_end: false }
,
463 ProjectionElem
::Subslice { from, to, from_end: false }
,
464 ProjectionElem
::ConstantIndex { offset, min_length: _, from_end: false }
,
466 if (from
..to
).contains(&offset
) {
467 debug
!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-SUBSLICE");
468 Overlap
::EqualOrDisjoint
470 debug
!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-SUBSLICE");
475 ProjectionElem
::ConstantIndex { offset, min_length: _, from_end: false }
,
476 ProjectionElem
::Subslice { from, .. }
,
479 ProjectionElem
::Subslice { from, .. }
,
480 ProjectionElem
::ConstantIndex { offset, min_length: _, from_end: false }
,
483 debug
!("place_element_conflict: DISJOINT-OR-EQ-SLICE-CONSTANT-INDEX-SUBSLICE");
484 Overlap
::EqualOrDisjoint
486 debug
!("place_element_conflict: DISJOINT-SLICE-CONSTANT-INDEX-SUBSLICE");
491 ProjectionElem
::ConstantIndex { offset, min_length: _, from_end: true }
,
492 ProjectionElem
::Subslice { to, from_end: true, .. }
,
495 ProjectionElem
::Subslice { to, from_end: true, .. }
,
496 ProjectionElem
::ConstantIndex { offset, min_length: _, from_end: true }
,
500 "place_element_conflict: \
501 DISJOINT-OR-EQ-SLICE-CONSTANT-INDEX-SUBSLICE-FE"
503 Overlap
::EqualOrDisjoint
505 debug
!("place_element_conflict: DISJOINT-SLICE-CONSTANT-INDEX-SUBSLICE-FE");
510 ProjectionElem
::Subslice { from: f1, to: t1, from_end: false }
,
511 ProjectionElem
::Subslice { from: f2, to: t2, from_end: false }
,
513 if f2
>= t1
|| f1
>= t2
{
514 debug
!("place_element_conflict: DISJOINT-ARRAY-SUBSLICES");
517 debug
!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-SUBSLICES");
518 Overlap
::EqualOrDisjoint
521 (ProjectionElem
::Subslice { .. }
, ProjectionElem
::Subslice { .. }
) => {
522 debug
!("place_element_conflict: DISJOINT-OR-EQ-SLICE-SUBSLICES");
523 Overlap
::EqualOrDisjoint
526 ProjectionElem
::Deref
527 | ProjectionElem
::Field(..)
528 | ProjectionElem
::Index(..)
529 | ProjectionElem
::ConstantIndex { .. }
530 | ProjectionElem
::Subslice { .. }
531 | ProjectionElem
::Downcast(..),
534 "mismatched projections in place_element_conflict: {:?} and {:?}",