compiler/rustc_mir/src/borrow_check/places_conflict.rs

   1 use crate::borrow_check::ArtificialField;
   2 use crate::borrow_check::Overlap;
   3 use crate::borrow_check::{AccessDepth, Deep, Shallow};
   4 use rustc_hir as hir;
   5 use rustc_middle::mir::{Body, BorrowKind, Local, Place, PlaceElem, PlaceRef, ProjectionElem};
   6 use rustc_middle::ty::{self, TyCtxt};
   7 use std::cmp::max;
   8 use std::iter;
   9
  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 {
  18     Overlap,
  19     NoOverlap,
  20 }
  21
  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
  24 /// dataflow).
  25 crate fn places_conflict<'tcx>(
  26     tcx: TyCtxt<'tcx>,
  27     body: &Body<'tcx>,
  28     borrow_place: Place<'tcx>,
  29     access_place: Place<'tcx>,
  30     bias: PlaceConflictBias,
  31 ) -> bool {
  32     borrow_conflicts_with_place(
  33         tcx,
  34         body,
  35         borrow_place,
  36         BorrowKind::Mut { allow_two_phase_borrow: true },
  37         access_place.as_ref(),
  38         AccessDepth::Deep,
  39         bias,
  40     )
  41 }
  42
  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>(
  48     tcx: TyCtxt<'tcx>,
  49     body: &Body<'tcx>,
  50     borrow_place: Place<'tcx>,
  51     borrow_kind: BorrowKind,
  52     access_place: PlaceRef<'tcx>,
  53     access: AccessDepth,
  54     bias: PlaceConflictBias,
  55 ) -> bool {
  56     debug!(
  57         "borrow_conflicts_with_place({:?}, {:?}, {:?}, {:?})",
  58         borrow_place, access_place, access, bias,
  59     );
  60
  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() {
  65             return l1 == l2;
  66         }
  67     }
  68
  69     place_components_conflict(tcx, body, borrow_place, borrow_kind, access_place, access, bias)
  70 }
  71
  72 fn place_components_conflict<'tcx>(
  73     tcx: TyCtxt<'tcx>,
  74     body: &Body<'tcx>,
  75     borrow_place: Place<'tcx>,
  76     borrow_kind: BorrowKind,
  77     access_place: PlaceRef<'tcx>,
  78     access: AccessDepth,
  79     bias: PlaceConflictBias,
  80 ) -> bool {
  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`.
  85     //
  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.
  88     //
  89     // For example, if we are comparing these:
  90     // BORROW:  (*x1[2].y).z.a
  91     // ACCESS:  (*x1[i].y).w.b
  92     //
  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!
  99     //
 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.
 102     //
 103     // BORROW:  (*x1[2].y).z.a
 104     // ACCESS:  x1[i].y
 105     //
 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
 110     //
 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:
 114     //
 115     //       x1[2].y    | (*x1[i].y)    -- a deref! the access can't get past this, so we
 116     //                                     are disjoint
 117     //
 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.
 122
 123     let borrow_local = borrow_place.local;
 124     let access_local = access_place.local;
 125
 126     match place_base_conflict(borrow_local, access_local) {
 127         Overlap::Arbitrary => {
 128             bug!("Two base can't return Arbitrary");
 129         }
 130         Overlap::EqualOrDisjoint => {
 131             // This is the recursive case - proceed to the next element.
 132         }
 133         Overlap::Disjoint => {
 134             // We have proven the borrow disjoint - further
 135             // projections will remain disjoint.
 136             debug!("borrow_conflicts_with_place: disjoint");
 137             return false;
 138         }
 139     }
 140
 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()
 144     {
 145         debug!("borrow_conflicts_with_place: borrow_c = {:?}", borrow_c);
 146         let borrow_proj_base = &borrow_place.projection[..i];
 147
 148         debug!("borrow_conflicts_with_place: access_c = {:?}", access_c);
 149
 150         // Borrow and access path both have more components.
 151         //
 152         // Examples:
 153         //
 154         // - borrow of `a.(...)`, access to `a.(...)`
 155         // - borrow of `a.(...)`, access to `b.(...)`
 156         //
 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(
 163             tcx,
 164             body,
 165             borrow_local,
 166             borrow_proj_base,
 167             borrow_c,
 168             access_c,
 169             bias,
 170         ) {
 171             Overlap::Arbitrary => {
 172                 // We have encountered different fields of potentially
 173                 // the same union - the borrow now partially overlaps.
 174                 //
 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).
 179                 //
 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");
 186                 return true;
 187             }
 188             Overlap::EqualOrDisjoint => {
 189                 // This is the recursive case - proceed to the next element.
 190             }
 191             Overlap::Disjoint => {
 192                 // We have proven the borrow disjoint - further
 193                 // projections will remain disjoint.
 194                 debug!("borrow_conflicts_with_place: disjoint");
 195                 return false;
 196             }
 197         }
 198     }
 199
 200     if borrow_place.projection.len() > access_place.projection.len() {
 201         for (i, elem) in borrow_place.projection[access_place.projection.len()..].iter().enumerate()
 202         {
 203             // Borrow path is longer than the access path. Examples:
 204             //
 205             // - borrow of `a.b.c`, access to `a.b`
 206             //
 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.
 210
 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;
 213
 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.)
 221                     //
 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");
 225                     return false;
 226                 }
 227
 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
 231                     // the pointer.
 232                     debug!("borrow_conflicts_with_place: shallow access behind ptr");
 233                     return false;
 234                 }
 235                 (ProjectionElem::Deref, ty::Ref(_, _, hir::Mutability::Not), _) => {
 236                     // Shouldn't be tracked
 237                     bug!("Tracking borrow behind shared reference.");
 238                 }
 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");
 243                     return false;
 244                 }
 245
 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) {
 250                         return true;
 251                     }
 252                 }
 253
 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`.
 265                 }
 266             }
 267         }
 268     }
 269
 270     // Borrow path ran out but access path may not
 271     // have. Examples:
 272     //
 273     // - borrow of `a.b`, access to `a.b.c`
 274     // - borrow of `a.b`, access to `a.b`
 275     //
 276     // In the first example, where we didn't run out of
 277     // access, the borrow can access all of our place, so we
 278     // have a conflict.
 279     //
 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()
 285     {
 286         debug!("borrow_conflicts_with_place: shallow borrow");
 287         false
 288     } else {
 289         debug!("borrow_conflicts_with_place: full borrow, CONFLICT");
 290         true
 291     }
 292 }
 293
 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 {
 298     if l1 == l2 {
 299         // the same local - base case, equal
 300         debug!("place_element_conflict: DISJOINT-OR-EQ-LOCAL");
 301         Overlap::EqualOrDisjoint
 302     } else {
 303         // different locals - base case, disjoint
 304         debug!("place_element_conflict: DISJOINT-LOCAL");
 305         Overlap::Disjoint
 306     }
 307 }
 308
 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>(
 313     tcx: TyCtxt<'tcx>,
 314     body: &Body<'tcx>,
 315     pi1_local: Local,
 316     pi1_proj_base: &[PlaceElem<'tcx>],
 317     pi1_elem: PlaceElem<'tcx>,
 318     pi2_elem: PlaceElem<'tcx>,
 319     bias: PlaceConflictBias,
 320 ) -> Overlap {
 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
 326         }
 327         (ProjectionElem::Field(f1, _), ProjectionElem::Field(f2, _)) => {
 328             if f1 == f2 {
 329                 // same field (e.g., `a.y` vs. `a.y`) - recur.
 330                 debug!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
 331                 Overlap::EqualOrDisjoint
 332             } else {
 333                 let ty = Place::ty_from(pi1_local, pi1_proj_base, body, tcx).ty;
 334                 match ty.kind() {
 335                     ty::Adt(def, _) if def.is_union() => {
 336                         // Different fields of a union, we are basically stuck.
 337                         debug!("place_element_conflict: STUCK-UNION");
 338                         Overlap::Arbitrary
 339                     }
 340                     _ => {
 341                         // Different fields of a struct (`a.x` vs. `a.y`). Disjoint!
 342                         debug!("place_element_conflict: DISJOINT-FIELD");
 343                         Overlap::Disjoint
 344                     }
 345                 }
 346             }
 347         }
 348         (ProjectionElem::Downcast(_, v1), ProjectionElem::Downcast(_, v2)) => {
 349             // different variants are treated as having disjoint fields,
 350             // even if they occupy the same "space", because it's
 351             // impossible for 2 variants of the same enum to exist
 352             // (and therefore, to be borrowed) at the same time.
 353             //
 354             // Note that this is different from unions - we *do* allow
 355             // this code to compile:
 356             //
 357             // ```
 358             // fn foo(x: &mut Result<i32, i32>) {
 359             //     let mut v = None;
 360             //     if let Ok(ref mut a) = *x {
 361             //         v = Some(a);
 362             //     }
 363             //     // here, you would *think* that the
 364             //     // *entirety* of `x` would be borrowed,
 365             //     // but in fact only the `Ok` variant is,
 366             //     // so the `Err` variant is *entirely free*:
 367             //     if let Err(ref mut a) = *x {
 368             //         v = Some(a);
 369             //     }
 370             //     drop(v);
 371             // }
 372             // ```
 373             if v1 == v2 {
 374                 debug!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
 375                 Overlap::EqualOrDisjoint
 376             } else {
 377                 debug!("place_element_conflict: DISJOINT-FIELD");
 378                 Overlap::Disjoint
 379             }
 380         }
 381         (
 382             ProjectionElem::Index(..),
 383             ProjectionElem::Index(..)
 384             | ProjectionElem::ConstantIndex { .. }
 385             | ProjectionElem::Subslice { .. },
 386         )
 387         | (
 388             ProjectionElem::ConstantIndex { .. } | ProjectionElem::Subslice { .. },
 389             ProjectionElem::Index(..),
 390         ) => {
 391             // Array indexes (`a[0]` vs. `a[i]`). These can either be disjoint
 392             // (if the indexes differ) or equal (if they are the same).
 393             match bias {
 394                 PlaceConflictBias::Overlap => {
 395                     // If we are biased towards overlapping, then this is the recursive
 396                     // case that gives "equal *or* disjoint" its meaning.
 397                     debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-INDEX");
 398                     Overlap::EqualOrDisjoint
 399                 }
 400                 PlaceConflictBias::NoOverlap => {
 401                     // If we are biased towards no overlapping, then this is disjoint.
 402                     debug!("place_element_conflict: DISJOINT-ARRAY-INDEX");
 403                     Overlap::Disjoint
 404                 }
 405             }
 406         }
 407         (
 408             ProjectionElem::ConstantIndex { offset: o1, min_length: _, from_end: false },
 409             ProjectionElem::ConstantIndex { offset: o2, min_length: _, from_end: false },
 410         )
 411         | (
 412             ProjectionElem::ConstantIndex { offset: o1, min_length: _, from_end: true },
 413             ProjectionElem::ConstantIndex { offset: o2, min_length: _, from_end: true },
 414         ) => {
 415             if o1 == o2 {
 416                 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX");
 417                 Overlap::EqualOrDisjoint
 418             } else {
 419                 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX");
 420                 Overlap::Disjoint
 421             }
 422         }
 423         (
 424             ProjectionElem::ConstantIndex {
 425                 offset: offset_from_begin,
 426                 min_length: min_length1,
 427                 from_end: false,
 428             },
 429             ProjectionElem::ConstantIndex {
 430                 offset: offset_from_end,
 431                 min_length: min_length2,
 432                 from_end: true,
 433             },
 434         )
 435         | (
 436             ProjectionElem::ConstantIndex {
 437                 offset: offset_from_end,
 438                 min_length: min_length1,
 439                 from_end: true,
 440             },
 441             ProjectionElem::ConstantIndex {
 442                 offset: offset_from_begin,
 443                 min_length: min_length2,
 444                 from_end: false,
 445             },
 446         ) => {
 447             // both patterns matched so it must be at least the greater of the two
 448             let min_length = max(min_length1, min_length2);
 449             // `offset_from_end` can be in range `[1..min_length]`, 1 indicates the last
 450             // element (like -1 in Python) and `min_length` the first.
 451             // Therefore, `min_length - offset_from_end` gives the minimal possible
 452             // offset from the beginning
 453             if offset_from_begin >= min_length - offset_from_end {
 454                 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-FE");
 455                 Overlap::EqualOrDisjoint
 456             } else {
 457                 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-FE");
 458                 Overlap::Disjoint
 459             }
 460         }
 461         (
 462             ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
 463             ProjectionElem::Subslice { from, to, from_end: false },
 464         )
 465         | (
 466             ProjectionElem::Subslice { from, to, from_end: false },
 467             ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
 468         ) => {
 469             if (from..to).contains(&offset) {
 470                 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-SUBSLICE");
 471                 Overlap::EqualOrDisjoint
 472             } else {
 473                 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-SUBSLICE");
 474                 Overlap::Disjoint
 475             }
 476         }
 477         (
 478             ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
 479             ProjectionElem::Subslice { from, .. },
 480         )
 481         | (
 482             ProjectionElem::Subslice { from, .. },
 483             ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
 484         ) => {
 485             if offset >= from {
 486                 debug!("place_element_conflict: DISJOINT-OR-EQ-SLICE-CONSTANT-INDEX-SUBSLICE");
 487                 Overlap::EqualOrDisjoint
 488             } else {
 489                 debug!("place_element_conflict: DISJOINT-SLICE-CONSTANT-INDEX-SUBSLICE");
 490                 Overlap::Disjoint
 491             }
 492         }
 493         (
 494             ProjectionElem::ConstantIndex { offset, min_length: _, from_end: true },
 495             ProjectionElem::Subslice { to, from_end: true, .. },
 496         )
 497         | (
 498             ProjectionElem::Subslice { to, from_end: true, .. },
 499             ProjectionElem::ConstantIndex { offset, min_length: _, from_end: true },
 500         ) => {
 501             if offset > to {
 502                 debug!(
 503                     "place_element_conflict: \
 504                        DISJOINT-OR-EQ-SLICE-CONSTANT-INDEX-SUBSLICE-FE"
 505                 );
 506                 Overlap::EqualOrDisjoint
 507             } else {
 508                 debug!("place_element_conflict: DISJOINT-SLICE-CONSTANT-INDEX-SUBSLICE-FE");
 509                 Overlap::Disjoint
 510             }
 511         }
 512         (
 513             ProjectionElem::Subslice { from: f1, to: t1, from_end: false },
 514             ProjectionElem::Subslice { from: f2, to: t2, from_end: false },
 515         ) => {
 516             if f2 >= t1 || f1 >= t2 {
 517                 debug!("place_element_conflict: DISJOINT-ARRAY-SUBSLICES");
 518                 Overlap::Disjoint
 519             } else {
 520                 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-SUBSLICES");
 521                 Overlap::EqualOrDisjoint
 522             }
 523         }
 524         (ProjectionElem::Subslice { .. }, ProjectionElem::Subslice { .. }) => {
 525             debug!("place_element_conflict: DISJOINT-OR-EQ-SLICE-SUBSLICES");
 526             Overlap::EqualOrDisjoint
 527         }
 528         (
 529             ProjectionElem::Deref
 530             | ProjectionElem::Field(..)
 531             | ProjectionElem::Index(..)
 532             | ProjectionElem::ConstantIndex { .. }
 533             | ProjectionElem::Subslice { .. }
 534             | ProjectionElem::Downcast(..),
 535             _,
 536         ) => bug!(
 537             "mismatched projections in place_element_conflict: {:?} and {:?}",
 538             pi1_elem,
 539             pi2_elem
 540         ),
 541     }
 542 }