src/librustc_mir/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::mir::{Body, BorrowKind, Place, PlaceBase, PlaceElem, PlaceRef, ProjectionElem};
   5 use rustc::ty::{self, TyCtxt};
   6 use rustc_hir as hir;
   7 use std::cmp::max;
   8
   9 /// When checking if a place conflicts with another place, this enum is used to influence decisions
  10 /// where a place might be equal or disjoint with another place, such as if `a[i] == a[j]`.
  11 /// `PlaceConflictBias::Overlap` would bias toward assuming that `i` might equal `j` and that these
  12 /// places overlap. `PlaceConflictBias::NoOverlap` assumes that for the purposes of the predicate
  13 /// being run in the calling context, the conservative choice is to assume the compared indices
  14 /// are disjoint (and therefore, do not overlap).
  15 #[derive(Copy, Clone, Debug, Eq, PartialEq)]
  16 crate enum PlaceConflictBias {
  17     Overlap,
  18     NoOverlap,
  19 }
  20
  21 /// Helper function for checking if places conflict with a mutable borrow and deep access depth.
  22 /// This is used to check for places conflicting outside of the borrow checking code (such as in
  23 /// dataflow).
  24 crate fn places_conflict<'tcx>(
  25     tcx: TyCtxt<'tcx>,
  26     body: &Body<'tcx>,
  27     borrow_place: &Place<'tcx>,
  28     access_place: &Place<'tcx>,
  29     bias: PlaceConflictBias,
  30 ) -> bool {
  31     borrow_conflicts_with_place(
  32         tcx,
  33         body,
  34         borrow_place,
  35         BorrowKind::Mut { allow_two_phase_borrow: true },
  36         access_place.as_ref(),
  37         AccessDepth::Deep,
  38         bias,
  39     )
  40 }
  41
  42 /// Checks whether the `borrow_place` conflicts with the `access_place` given a borrow kind and
  43 /// access depth. The `bias` parameter is used to determine how the unknowable (comparing runtime
  44 /// array indices, for example) should be interpreted - this depends on what the caller wants in
  45 /// order to make the conservative choice and preserve soundness.
  46 pub(super) fn borrow_conflicts_with_place<'tcx>(
  47     tcx: TyCtxt<'tcx>,
  48     body: &Body<'tcx>,
  49     borrow_place: &Place<'tcx>,
  50     borrow_kind: BorrowKind,
  51     access_place: PlaceRef<'_, 'tcx>,
  52     access: AccessDepth,
  53     bias: PlaceConflictBias,
  54 ) -> bool {
  55     debug!(
  56         "borrow_conflicts_with_place({:?}, {:?}, {:?}, {:?})",
  57         borrow_place, access_place, access, bias,
  58     );
  59
  60     // This Local/Local case is handled by the more general code below, but
  61     // it's so common that it's a speed win to check for it first.
  62     if let Some(l1) = borrow_place.as_local() {
  63         if let Some(l2) = access_place.as_local() {
  64             return l1 == l2;
  65         }
  66     }
  67
  68     place_components_conflict(tcx, body, borrow_place, borrow_kind, access_place, access, bias)
  69 }
  70
  71 fn place_components_conflict<'tcx>(
  72     tcx: TyCtxt<'tcx>,
  73     body: &Body<'tcx>,
  74     borrow_place: &Place<'tcx>,
  75     borrow_kind: BorrowKind,
  76     access_place: PlaceRef<'_, 'tcx>,
  77     access: AccessDepth,
  78     bias: PlaceConflictBias,
  79 ) -> bool {
  80     // The borrowck rules for proving disjointness are applied from the "root" of the
  81     // borrow forwards, iterating over "similar" projections in lockstep until
  82     // we can prove overlap one way or another. Essentially, we treat `Overlap` as
  83     // a monoid and report a conflict if the product ends up not being `Disjoint`.
  84     //
  85     // At each step, if we didn't run out of borrow or place, we know that our elements
  86     // have the same type, and that they only overlap if they are the identical.
  87     //
  88     // For example, if we are comparing these:
  89     // BORROW:  (*x1[2].y).z.a
  90     // ACCESS:  (*x1[i].y).w.b
  91     //
  92     // Then our steps are:
  93     //       x1         |   x1          -- places are the same
  94     //       x1[2]      |   x1[i]       -- equal or disjoint (disjoint if indexes differ)
  95     //       x1[2].y    |   x1[i].y     -- equal or disjoint
  96     //      *x1[2].y    |  *x1[i].y     -- equal or disjoint
  97     //     (*x1[2].y).z | (*x1[i].y).w  -- we are disjoint and don't need to check more!
  98     //
  99     // Because `zip` does potentially bad things to the iterator inside, this loop
 100     // also handles the case where the access might be a *prefix* of the borrow, e.g.
 101     //
 102     // BORROW:  (*x1[2].y).z.a
 103     // ACCESS:  x1[i].y
 104     //
 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     //
 110     // -- here we run out of access - the borrow can access a part of it. If this
 111     // is a full deep access, then we *know* the borrow conflicts with it. However,
 112     // if the access is shallow, then we can proceed:
 113     //
 114     //       x1[2].y    | (*x1[i].y)    -- a deref! the access can't get past this, so we
 115     //                                     are disjoint
 116     //
 117     // Our invariant is, that at each step of the iteration:
 118     //  - If we didn't run out of access to match, our borrow and access are comparable
 119     //    and either equal or disjoint.
 120     //  - If we did run out of access, the borrow can access a part of it.
 121
 122     let borrow_base = &borrow_place.base;
 123     let access_base = access_place.base;
 124
 125     match place_base_conflict(borrow_base, access_base) {
 126         Overlap::Arbitrary => {
 127             bug!("Two base can't return Arbitrary");
 128         }
 129         Overlap::EqualOrDisjoint => {
 130             // This is the recursive case - proceed to the next element.
 131         }
 132         Overlap::Disjoint => {
 133             // We have proven the borrow disjoint - further
 134             // projections will remain disjoint.
 135             debug!("borrow_conflicts_with_place: disjoint");
 136             return false;
 137         }
 138     }
 139
 140     // loop invariant: borrow_c is always either equal to access_c or disjoint from it.
 141     for (i, (borrow_c, access_c)) in
 142         borrow_place.projection.iter().zip(access_place.projection.iter()).enumerate()
 143     {
 144         debug!("borrow_conflicts_with_place: borrow_c = {:?}", borrow_c);
 145         let borrow_proj_base = &borrow_place.projection[..i];
 146
 147         debug!("borrow_conflicts_with_place: access_c = {:?}", access_c);
 148
 149         // Borrow and access path both have more components.
 150         //
 151         // Examples:
 152         //
 153         // - borrow of `a.(...)`, access to `a.(...)`
 154         // - borrow of `a.(...)`, access to `b.(...)`
 155         //
 156         // Here we only see the components we have checked so
 157         // far (in our examples, just the first component). We
 158         // check whether the components being borrowed vs
 159         // accessed are disjoint (as in the second example,
 160         // but not the first).
 161         match place_projection_conflict(
 162             tcx,
 163             body,
 164             borrow_base,
 165             borrow_proj_base,
 166             borrow_c,
 167             access_c,
 168             bias,
 169         ) {
 170             Overlap::Arbitrary => {
 171                 // We have encountered different fields of potentially
 172                 // the same union - the borrow now partially overlaps.
 173                 //
 174                 // There is no *easy* way of comparing the fields
 175                 // further on, because they might have different types
 176                 // (e.g., borrows of `u.a.0` and `u.b.y` where `.0` and
 177                 // `.y` come from different structs).
 178                 //
 179                 // We could try to do some things here - e.g., count
 180                 // dereferences - but that's probably not a good
 181                 // idea, at least for now, so just give up and
 182                 // report a conflict. This is unsafe code anyway so
 183                 // the user could always use raw pointers.
 184                 debug!("borrow_conflicts_with_place: arbitrary -> conflict");
 185                 return true;
 186             }
 187             Overlap::EqualOrDisjoint => {
 188                 // This is the recursive case - proceed to the next element.
 189             }
 190             Overlap::Disjoint => {
 191                 // We have proven the borrow disjoint - further
 192                 // projections will remain disjoint.
 193                 debug!("borrow_conflicts_with_place: disjoint");
 194                 return false;
 195             }
 196         }
 197     }
 198
 199     if borrow_place.projection.len() > access_place.projection.len() {
 200         for (i, elem) in borrow_place.projection[access_place.projection.len()..].iter().enumerate()
 201         {
 202             // Borrow path is longer than the access path. Examples:
 203             //
 204             // - borrow of `a.b.c`, access to `a.b`
 205             //
 206             // Here, we know that the borrow can access a part of
 207             // our place. This is a conflict if that is a part our
 208             // access cares about.
 209
 210             let proj_base = &borrow_place.projection[..access_place.projection.len() + i];
 211             let base_ty = Place::ty_from(borrow_base, proj_base, body, tcx).ty;
 212
 213             match (elem, &base_ty.kind, access) {
 214                 (_, _, Shallow(Some(ArtificialField::ArrayLength)))
 215                 | (_, _, Shallow(Some(ArtificialField::ShallowBorrow))) => {
 216                     // The array length is like  additional fields on the
 217                     // type; it does not overlap any existing data there.
 218                     // Furthermore, if cannot actually be a prefix of any
 219                     // borrowed place (at least in MIR as it is currently.)
 220                     //
 221                     // e.g., a (mutable) borrow of `a[5]` while we read the
 222                     // array length of `a`.
 223                     debug!("borrow_conflicts_with_place: implicit field");
 224                     return false;
 225                 }
 226
 227                 (ProjectionElem::Deref, _, Shallow(None)) => {
 228                     // e.g., a borrow of `*x.y` while we shallowly access `x.y` or some
 229                     // prefix thereof - the shallow access can't touch anything behind
 230                     // the pointer.
 231                     debug!("borrow_conflicts_with_place: shallow access behind ptr");
 232                     return false;
 233                 }
 234                 (ProjectionElem::Deref, ty::Ref(_, _, hir::Mutability::Not), _) => {
 235                     // Shouldn't be tracked
 236                     bug!("Tracking borrow behind shared reference.");
 237                 }
 238                 (ProjectionElem::Deref, ty::Ref(_, _, hir::Mutability::Mut), AccessDepth::Drop) => {
 239                     // Values behind a mutable reference are not access either by dropping a
 240                     // value, or by StorageDead
 241                     debug!("borrow_conflicts_with_place: drop access behind ptr");
 242                     return false;
 243                 }
 244
 245                 (ProjectionElem::Field { .. }, ty::Adt(def, _), AccessDepth::Drop) => {
 246                     // Drop can read/write arbitrary projections, so places
 247                     // conflict regardless of further projections.
 248                     if def.has_dtor(tcx) {
 249                         return true;
 250                     }
 251                 }
 252
 253                 (ProjectionElem::Deref, _, Deep)
 254                 | (ProjectionElem::Deref, _, AccessDepth::Drop)
 255                 | (ProjectionElem::Field { .. }, _, _)
 256                 | (ProjectionElem::Index { .. }, _, _)
 257                 | (ProjectionElem::ConstantIndex { .. }, _, _)
 258                 | (ProjectionElem::Subslice { .. }, _, _)
 259                 | (ProjectionElem::Downcast { .. }, _, _) => {
 260                     // Recursive case. This can still be disjoint on a
 261                     // further iteration if this a shallow access and
 262                     // there's a deref later on, e.g., a borrow
 263                     // of `*x.y` while accessing `x`.
 264                 }
 265             }
 266         }
 267     }
 268
 269     // Borrow path ran out but access path may not
 270     // have. Examples:
 271     //
 272     // - borrow of `a.b`, access to `a.b.c`
 273     // - borrow of `a.b`, access to `a.b`
 274     //
 275     // In the first example, where we didn't run out of
 276     // access, the borrow can access all of our place, so we
 277     // have a conflict.
 278     //
 279     // If the second example, where we did, then we still know
 280     // that the borrow can access a *part* of our place that
 281     // our access cares about, so we still have a conflict.
 282     if borrow_kind == BorrowKind::Shallow
 283         && borrow_place.projection.len() < access_place.projection.len()
 284     {
 285         debug!("borrow_conflicts_with_place: shallow borrow");
 286         false
 287     } else {
 288         debug!("borrow_conflicts_with_place: full borrow, CONFLICT");
 289         true
 290     }
 291 }
 292
 293 // Given that the bases of `elem1` and `elem2` are always either equal
 294 // or disjoint (and have the same type!), return the overlap situation
 295 // between `elem1` and `elem2`.
 296 fn place_base_conflict(elem1: &PlaceBase, elem2: &PlaceBase) -> Overlap {
 297     match (elem1, elem2) {
 298         (PlaceBase::Local(l1), PlaceBase::Local(l2)) => {
 299             if l1 == l2 {
 300                 // the same local - base case, equal
 301                 debug!("place_element_conflict: DISJOINT-OR-EQ-LOCAL");
 302                 Overlap::EqualOrDisjoint
 303             } else {
 304                 // different locals - base case, disjoint
 305                 debug!("place_element_conflict: DISJOINT-LOCAL");
 306                 Overlap::Disjoint
 307             }
 308         }
 309     }
 310 }
 311
 312 // Given that the bases of `elem1` and `elem2` are always either equal
 313 // or disjoint (and have the same type!), return the overlap situation
 314 // between `elem1` and `elem2`.
 315 fn place_projection_conflict<'tcx>(
 316     tcx: TyCtxt<'tcx>,
 317     body: &Body<'tcx>,
 318     pi1_base: &PlaceBase,
 319     pi1_proj_base: &[PlaceElem<'tcx>],
 320     pi1_elem: &PlaceElem<'tcx>,
 321     pi2_elem: &PlaceElem<'tcx>,
 322     bias: PlaceConflictBias,
 323 ) -> Overlap {
 324     match (pi1_elem, pi2_elem) {
 325         (ProjectionElem::Deref, ProjectionElem::Deref) => {
 326             // derefs (e.g., `*x` vs. `*x`) - recur.
 327             debug!("place_element_conflict: DISJOINT-OR-EQ-DEREF");
 328             Overlap::EqualOrDisjoint
 329         }
 330         (ProjectionElem::Field(f1, _), ProjectionElem::Field(f2, _)) => {
 331             if f1 == f2 {
 332                 // same field (e.g., `a.y` vs. `a.y`) - recur.
 333                 debug!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
 334                 Overlap::EqualOrDisjoint
 335             } else {
 336                 let ty = Place::ty_from(pi1_base, pi1_proj_base, body, tcx).ty;
 337                 match ty.kind {
 338                     ty::Adt(def, _) if def.is_union() => {
 339                         // Different fields of a union, we are basically stuck.
 340                         debug!("place_element_conflict: STUCK-UNION");
 341                         Overlap::Arbitrary
 342                     }
 343                     _ => {
 344                         // Different fields of a struct (`a.x` vs. `a.y`). Disjoint!
 345                         debug!("place_element_conflict: DISJOINT-FIELD");
 346                         Overlap::Disjoint
 347                     }
 348                 }
 349             }
 350         }
 351         (ProjectionElem::Downcast(_, v1), ProjectionElem::Downcast(_, v2)) => {
 352             // different variants are treated as having disjoint fields,
 353             // even if they occupy the same "space", because it's
 354             // impossible for 2 variants of the same enum to exist
 355             // (and therefore, to be borrowed) at the same time.
 356             //
 357             // Note that this is different from unions - we *do* allow
 358             // this code to compile:
 359             //
 360             // ```
 361             // fn foo(x: &mut Result<i32, i32>) {
 362             //     let mut v = None;
 363             //     if let Ok(ref mut a) = *x {
 364             //         v = Some(a);
 365             //     }
 366             //     // here, you would *think* that the
 367             //     // *entirety* of `x` would be borrowed,
 368             //     // but in fact only the `Ok` variant is,
 369             //     // so the `Err` variant is *entirely free*:
 370             //     if let Err(ref mut a) = *x {
 371             //         v = Some(a);
 372             //     }
 373             //     drop(v);
 374             // }
 375             // ```
 376             if v1 == v2 {
 377                 debug!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
 378                 Overlap::EqualOrDisjoint
 379             } else {
 380                 debug!("place_element_conflict: DISJOINT-FIELD");
 381                 Overlap::Disjoint
 382             }
 383         }
 384         (ProjectionElem::Index(..), ProjectionElem::Index(..))
 385         | (ProjectionElem::Index(..), ProjectionElem::ConstantIndex { .. })
 386         | (ProjectionElem::Index(..), ProjectionElem::Subslice { .. })
 387         | (ProjectionElem::ConstantIndex { .. }, ProjectionElem::Index(..))
 388         | (ProjectionElem::Subslice { .. }, ProjectionElem::Index(..)) => {
 389             // Array indexes (`a[0]` vs. `a[i]`). These can either be disjoint
 390             // (if the indexes differ) or equal (if they are the same).
 391             match bias {
 392                 PlaceConflictBias::Overlap => {
 393                     // If we are biased towards overlapping, then this is the recursive
 394                     // case that gives "equal *or* disjoint" its meaning.
 395                     debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-INDEX");
 396                     Overlap::EqualOrDisjoint
 397                 }
 398                 PlaceConflictBias::NoOverlap => {
 399                     // If we are biased towards no overlapping, then this is disjoint.
 400                     debug!("place_element_conflict: DISJOINT-ARRAY-INDEX");
 401                     Overlap::Disjoint
 402                 }
 403             }
 404         }
 405         (
 406             ProjectionElem::ConstantIndex { offset: o1, min_length: _, from_end: false },
 407             ProjectionElem::ConstantIndex { offset: o2, min_length: _, from_end: false },
 408         )
 409         | (
 410             ProjectionElem::ConstantIndex { offset: o1, min_length: _, from_end: true },
 411             ProjectionElem::ConstantIndex { offset: o2, min_length: _, from_end: true },
 412         ) => {
 413             if o1 == o2 {
 414                 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX");
 415                 Overlap::EqualOrDisjoint
 416             } else {
 417                 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX");
 418                 Overlap::Disjoint
 419             }
 420         }
 421         (
 422             ProjectionElem::ConstantIndex {
 423                 offset: offset_from_begin,
 424                 min_length: min_length1,
 425                 from_end: false,
 426             },
 427             ProjectionElem::ConstantIndex {
 428                 offset: offset_from_end,
 429                 min_length: min_length2,
 430                 from_end: true,
 431             },
 432         )
 433         | (
 434             ProjectionElem::ConstantIndex {
 435                 offset: offset_from_end,
 436                 min_length: min_length1,
 437                 from_end: true,
 438             },
 439             ProjectionElem::ConstantIndex {
 440                 offset: offset_from_begin,
 441                 min_length: min_length2,
 442                 from_end: false,
 443             },
 444         ) => {
 445             // both patterns matched so it must be at least the greater of the two
 446             let min_length = max(min_length1, min_length2);
 447             // `offset_from_end` can be in range `[1..min_length]`, 1 indicates the last
 448             // element (like -1 in Python) and `min_length` the first.
 449             // Therefore, `min_length - offset_from_end` gives the minimal possible
 450             // offset from the beginning
 451             if *offset_from_begin >= *min_length - *offset_from_end {
 452                 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-FE");
 453                 Overlap::EqualOrDisjoint
 454             } else {
 455                 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-FE");
 456                 Overlap::Disjoint
 457             }
 458         }
 459         (
 460             ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
 461             ProjectionElem::Subslice { from, to, from_end: false },
 462         )
 463         | (
 464             ProjectionElem::Subslice { from, to, from_end: false },
 465             ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
 466         ) => {
 467             if (from..to).contains(&offset) {
 468                 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-SUBSLICE");
 469                 Overlap::EqualOrDisjoint
 470             } else {
 471                 debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-SUBSLICE");
 472                 Overlap::Disjoint
 473             }
 474         }
 475         (
 476             ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
 477             ProjectionElem::Subslice { from, .. },
 478         )
 479         | (
 480             ProjectionElem::Subslice { from, .. },
 481             ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
 482         ) => {
 483             if offset >= from {
 484                 debug!("place_element_conflict: DISJOINT-OR-EQ-SLICE-CONSTANT-INDEX-SUBSLICE");
 485                 Overlap::EqualOrDisjoint
 486             } else {
 487                 debug!("place_element_conflict: DISJOINT-SLICE-CONSTANT-INDEX-SUBSLICE");
 488                 Overlap::Disjoint
 489             }
 490         }
 491         (
 492             ProjectionElem::ConstantIndex { offset, min_length: _, from_end: true },
 493             ProjectionElem::Subslice { to, from_end: true, .. },
 494         )
 495         | (
 496             ProjectionElem::Subslice { to, from_end: true, .. },
 497             ProjectionElem::ConstantIndex { offset, min_length: _, from_end: true },
 498         ) => {
 499             if offset > to {
 500                 debug!(
 501                     "place_element_conflict: \
 502                        DISJOINT-OR-EQ-SLICE-CONSTANT-INDEX-SUBSLICE-FE"
 503                 );
 504                 Overlap::EqualOrDisjoint
 505             } else {
 506                 debug!("place_element_conflict: DISJOINT-SLICE-CONSTANT-INDEX-SUBSLICE-FE");
 507                 Overlap::Disjoint
 508             }
 509         }
 510         (
 511             ProjectionElem::Subslice { from: f1, to: t1, from_end: false },
 512             ProjectionElem::Subslice { from: f2, to: t2, from_end: false },
 513         ) => {
 514             if f2 >= t1 || f1 >= t2 {
 515                 debug!("place_element_conflict: DISJOINT-ARRAY-SUBSLICES");
 516                 Overlap::Disjoint
 517             } else {
 518                 debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-SUBSLICES");
 519                 Overlap::EqualOrDisjoint
 520             }
 521         }
 522         (ProjectionElem::Subslice { .. }, ProjectionElem::Subslice { .. }) => {
 523             debug!("place_element_conflict: DISJOINT-OR-EQ-SLICE-SUBSLICES");
 524             Overlap::EqualOrDisjoint
 525         }
 526         (ProjectionElem::Deref, _)
 527         | (ProjectionElem::Field(..), _)
 528         | (ProjectionElem::Index(..), _)
 529         | (ProjectionElem::ConstantIndex { .. }, _)
 530         | (ProjectionElem::Subslice { .. }, _)
 531         | (ProjectionElem::Downcast(..), _) => bug!(
 532             "mismatched projections in place_element_conflict: {:?} and {:?}",
 533             pi1_elem,
 534             pi2_elem
 535         ),
 536     }
 537 }