compiler/rustc_borrowck/src/places_conflict.rs

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