compiler/rustc_borrowck/src/places_conflict.rs

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