src/librustc_mir/borrow_check/places_conflict.rs

   1 // Copyright 2018 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use borrow_check::ArtificialField;
  12 use borrow_check::Overlap;
  13 use borrow_check::{Deep, Shallow, ShallowOrDeep};
  14 use rustc::hir;
  15 use rustc::mir::{Mir, Place};
  16 use rustc::mir::{Projection, ProjectionElem};
  17 use rustc::ty::{self, TyCtxt};
  18 use std::cmp::max;
  19
  20 pub(super) fn places_conflict<'gcx, 'tcx>(
  21     tcx: TyCtxt<'_, 'gcx, 'tcx>,
  22     mir: &Mir<'tcx>,
  23     borrow_place: &Place<'tcx>,
  24     access_place: &Place<'tcx>,
  25     access: ShallowOrDeep,
  26 ) -> bool {
  27     debug!(
  28         "places_conflict({:?},{:?},{:?})",
  29         borrow_place, access_place, access
  30     );
  31
  32     unroll_place(borrow_place, None, |borrow_components| {
  33         unroll_place(access_place, None, |access_components| {
  34             place_components_conflict(tcx, mir, borrow_components, access_components, access)
  35         })
  36     })
  37 }
  38
  39 fn place_components_conflict<'gcx, 'tcx>(
  40     tcx: TyCtxt<'_, 'gcx, 'tcx>,
  41     mir: &Mir<'tcx>,
  42     mut borrow_components: PlaceComponentsIter<'_, 'tcx>,
  43     mut access_components: PlaceComponentsIter<'_, 'tcx>,
  44     access: ShallowOrDeep,
  45 ) -> bool {
  46     // The borrowck rules for proving disjointness are applied from the "root" of the
  47     // borrow forwards, iterating over "similar" projections in lockstep until
  48     // we can prove overlap one way or another. Essentially, we treat `Overlap` as
  49     // a monoid and report a conflict if the product ends up not being `Disjoint`.
  50     //
  51     // At each step, if we didn't run out of borrow or place, we know that our elements
  52     // have the same type, and that they only overlap if they are the identical.
  53     //
  54     // For example, if we are comparing these:
  55     // BORROW:  (*x1[2].y).z.a
  56     // ACCESS:  (*x1[i].y).w.b
  57     //
  58     // Then our steps are:
  59     //       x1         |   x1          -- places are the same
  60     //       x1[2]      |   x1[i]       -- equal or disjoint (disjoint if indexes differ)
  61     //       x1[2].y    |   x1[i].y     -- equal or disjoint
  62     //      *x1[2].y    |  *x1[i].y     -- equal or disjoint
  63     //     (*x1[2].y).z | (*x1[i].y).w  -- we are disjoint and don't need to check more!
  64     //
  65     // Because `zip` does potentially bad things to the iterator inside, this loop
  66     // also handles the case where the access might be a *prefix* of the borrow, e.g.
  67     //
  68     // BORROW:  (*x1[2].y).z.a
  69     // ACCESS:  x1[i].y
  70     //
  71     // Then our steps are:
  72     //       x1         |   x1          -- places are the same
  73     //       x1[2]      |   x1[i]       -- equal or disjoint (disjoint if indexes differ)
  74     //       x1[2].y    |   x1[i].y     -- equal or disjoint
  75     //
  76     // -- here we run out of access - the borrow can access a part of it. If this
  77     // is a full deep access, then we *know* the borrow conflicts with it. However,
  78     // if the access is shallow, then we can proceed:
  79     //
  80     //       x1[2].y    | (*x1[i].y)    -- a deref! the access can't get past this, so we
  81     //                                     are disjoint
  82     //
  83     // Our invariant is, that at each step of the iteration:
  84     //  - If we didn't run out of access to match, our borrow and access are comparable
  85     //    and either equal or disjoint.
  86     //  - If we did run out of accesss, the borrow can access a part of it.
  87     loop {
  88         // loop invariant: borrow_c is always either equal to access_c or disjoint from it.
  89         if let Some(borrow_c) = borrow_components.next() {
  90             debug!("places_conflict: borrow_c = {:?}", borrow_c);
  91
  92             if let Some(access_c) = access_components.next() {
  93                 debug!("places_conflict: access_c = {:?}", access_c);
  94
  95                 // Borrow and access path both have more components.
  96                 //
  97                 // Examples:
  98                 //
  99                 // - borrow of `a.(...)`, access to `a.(...)`
 100                 // - borrow of `a.(...)`, access to `b.(...)`
 101                 //
 102                 // Here we only see the components we have checked so
 103                 // far (in our examples, just the first component). We
 104                 // check whether the components being borrowed vs
 105                 // accessed are disjoint (as in the second example,
 106                 // but not the first).
 107                 match place_element_conflict(tcx, mir, borrow_c, access_c) {
 108                     Overlap::Arbitrary => {
 109                         // We have encountered different fields of potentially
 110                         // the same union - the borrow now partially overlaps.
 111                         //
 112                         // There is no *easy* way of comparing the fields
 113                         // further on, because they might have different types
 114                         // (e.g. borrows of `u.a.0` and `u.b.y` where `.0` and
 115                         // `.y` come from different structs).
 116                         //
 117                         // We could try to do some things here - e.g. count
 118                         // dereferences - but that's probably not a good
 119                         // idea, at least for now, so just give up and
 120                         // report a conflict. This is unsafe code anyway so
 121                         // the user could always use raw pointers.
 122                         debug!("places_conflict: arbitrary -> conflict");
 123                         return true;
 124                     }
 125                     Overlap::EqualOrDisjoint => {
 126                         // This is the recursive case - proceed to the next element.
 127                     }
 128                     Overlap::Disjoint => {
 129                         // We have proven the borrow disjoint - further
 130                         // projections will remain disjoint.
 131                         debug!("places_conflict: disjoint");
 132                         return false;
 133                     }
 134                 }
 135             } else {
 136                 // Borrow path is longer than the access path. Examples:
 137                 //
 138                 // - borrow of `a.b.c`, access to `a.b`
 139                 //
 140                 // Here, we know that the borrow can access a part of
 141                 // our place. This is a conflict if that is a part our
 142                 // access cares about.
 143
 144                 let (base, elem) = match borrow_c {
 145                     Place::Projection(box Projection { base, elem }) => (base, elem),
 146                     _ => bug!("place has no base?"),
 147                 };
 148                 let base_ty = base.ty(mir, tcx).to_ty(tcx);
 149
 150                 match (elem, &base_ty.sty, access) {
 151                     (_, _, Shallow(Some(ArtificialField::Discriminant)))
 152                     | (_, _, Shallow(Some(ArtificialField::ArrayLength))) => {
 153                         // The discriminant and array length are like
 154                         // additional fields on the type; they do not
 155                         // overlap any existing data there. Furthermore,
 156                         // they cannot actually be a prefix of any
 157                         // borrowed place (at least in MIR as it is
 158                         // currently.)
 159                         //
 160                         // e.g. a (mutable) borrow of `a[5]` while we read the
 161                         // array length of `a`.
 162                         debug!("places_conflict: implicit field");
 163                         return false;
 164                     }
 165
 166                     (ProjectionElem::Deref, _, Shallow(None)) => {
 167                         // e.g. a borrow of `*x.y` while we shallowly access `x.y` or some
 168                         // prefix thereof - the shallow access can't touch anything behind
 169                         // the pointer.
 170                         debug!("places_conflict: shallow access behind ptr");
 171                         return false;
 172                     }
 173                     (ProjectionElem::Deref, ty::TyRef(_, _, hir::MutImmutable), _) => {
 174                         // the borrow goes through a dereference of a shared reference.
 175                         //
 176                         // I'm not sure why we are tracking these borrows - shared
 177                         // references can *always* be aliased, which means the
 178                         // permission check already account for this borrow.
 179                         debug!("places_conflict: behind a shared ref");
 180                         return false;
 181                     }
 182
 183                     (ProjectionElem::Deref, _, Deep)
 184                     | (ProjectionElem::Field { .. }, _, _)
 185                     | (ProjectionElem::Index { .. }, _, _)
 186                     | (ProjectionElem::ConstantIndex { .. }, _, _)
 187                     | (ProjectionElem::Subslice { .. }, _, _)
 188                     | (ProjectionElem::Downcast { .. }, _, _) => {
 189                         // Recursive case. This can still be disjoint on a
 190                         // further iteration if this a shallow access and
 191                         // there's a deref later on, e.g. a borrow
 192                         // of `*x.y` while accessing `x`.
 193                     }
 194                 }
 195             }
 196         } else {
 197             // Borrow path ran out but access path may not
 198             // have. Examples:
 199             //
 200             // - borrow of `a.b`, access to `a.b.c`
 201             // - borrow of `a.b`, access to `a.b`
 202             //
 203             // In the first example, where we didn't run out of
 204             // access, the borrow can access all of our place, so we
 205             // have a conflict.
 206             //
 207             // If the second example, where we did, then we still know
 208             // that the borrow can access a *part* of our place that
 209             // our access cares about, so we still have a conflict.
 210             //
 211             // FIXME: Differs from AST-borrowck; includes drive-by fix
 212             // to #38899. Will probably need back-compat mode flag.
 213             debug!("places_conflict: full borrow, CONFLICT");
 214             return true;
 215         }
 216     }
 217 }
 218
 219 /// A linked list of places running up the stack; begins with the
 220 /// innermost place and extends to projections (e.g., `a.b` would have
 221 /// the place `a` with a "next" pointer to `a.b`).  Created by
 222 /// `unroll_place`.
 223 ///
 224 /// NB: This particular impl strategy is not the most obvious.  It was
 225 /// chosen because it makes a measurable difference to NLL
 226 /// performance, as this code (`places_conflict`) is somewhat hot.
 227 struct PlaceComponents<'p, 'tcx: 'p> {
 228     component: &'p Place<'tcx>,
 229     next: Option<&'p PlaceComponents<'p, 'tcx>>,
 230 }
 231
 232 impl<'p, 'tcx> PlaceComponents<'p, 'tcx> {
 233     /// Converts a list of `Place` components into an iterator; this
 234     /// iterator yields up a never-ending stream of `Option<&Place>`.
 235     /// These begin with the "innermst" place and then with each
 236     /// projection therefrom. So given a place like `a.b.c` it would
 237     /// yield up:
 238     ///
 239     /// ```notrust
 240     /// Some(`a`), Some(`a.b`), Some(`a.b.c`), None, None, ...
 241     /// ```
 242     fn iter(&self) -> PlaceComponentsIter<'_, 'tcx> {
 243         PlaceComponentsIter { value: Some(self) }
 244     }
 245 }
 246
 247 /// Iterator over components; see `PlaceComponents::iter` for more
 248 /// information.
 249 ///
 250 /// NB: This is not a *true* Rust iterator -- the code above just
 251 /// manually invokes `next`. This is because we (sometimes) want to
 252 /// keep executing even after `None` has been returned.
 253 struct PlaceComponentsIter<'p, 'tcx: 'p> {
 254     value: Option<&'p PlaceComponents<'p, 'tcx>>,
 255 }
 256
 257 impl<'p, 'tcx> PlaceComponentsIter<'p, 'tcx> {
 258     fn next(&mut self) -> Option<&'p Place<'tcx>> {
 259         if let Some(&PlaceComponents { component, next }) = self.value {
 260             self.value = next;
 261             Some(component)
 262         } else {
 263             None
 264         }
 265     }
 266 }
 267
 268 /// Recursively "unroll" a place into a `PlaceComponents` list,
 269 /// invoking `op` with a `PlaceComponentsIter`.
 270 fn unroll_place<'tcx, R>(
 271     place: &Place<'tcx>,
 272     next: Option<&PlaceComponents<'_, 'tcx>>,
 273     op: impl FnOnce(PlaceComponentsIter<'_, 'tcx>) -> R,
 274 ) -> R {
 275     match place {
 276         Place::Projection(interior) => unroll_place(
 277             &interior.base,
 278             Some(&PlaceComponents {
 279                 component: place,
 280                 next,
 281             }),
 282             op,
 283         ),
 284
 285         Place::Promoted(_) |
 286         Place::Local(_) | Place::Static(_) => {
 287             let list = PlaceComponents {
 288                 component: place,
 289                 next,
 290             };
 291             op(list.iter())
 292         }
 293     }
 294 }
 295
 296 // Given that the bases of `elem1` and `elem2` are always either equal
 297 // or disjoint (and have the same type!), return the overlap situation
 298 // between `elem1` and `elem2`.
 299 fn place_element_conflict<'a, 'gcx: 'tcx, 'tcx>(
 300     tcx: TyCtxt<'a, 'gcx, 'tcx>,
 301     mir: &Mir<'tcx>,
 302     elem1: &Place<'tcx>,
 303     elem2: &Place<'tcx>,
 304 ) -> Overlap {
 305     match (elem1, elem2) {
 306         (Place::Local(l1), Place::Local(l2)) => {
 307             if l1 == l2 {
 308                 // the same local - base case, equal
 309                 debug!("place_element_conflict: DISJOINT-OR-EQ-LOCAL");
 310                 Overlap::EqualOrDisjoint
 311             } else {
 312                 // different locals - base case, disjoint
 313                 debug!("place_element_conflict: DISJOINT-LOCAL");
 314                 Overlap::Disjoint
 315             }
 316         }
 317         (Place::Static(static1), Place::Static(static2)) => {
 318             if static1.def_id != static2.def_id {
 319                 debug!("place_element_conflict: DISJOINT-STATIC");
 320                 Overlap::Disjoint
 321             } else if tcx.is_static(static1.def_id) == Some(hir::Mutability::MutMutable) {
 322                 // We ignore mutable statics - they can only be unsafe code.
 323                 debug!("place_element_conflict: IGNORE-STATIC-MUT");
 324                 Overlap::Disjoint
 325             } else {
 326                 debug!("place_element_conflict: DISJOINT-OR-EQ-STATIC");
 327                 Overlap::EqualOrDisjoint
 328             }
 329         }
 330         (Place::Promoted(p1), Place::Promoted(p2)) => {
 331             if p1.0 == p2.0 {
 332                 // the same promoted - base case, equal
 333                 debug!("place_element_conflict: DISJOINT-OR-EQ-PROMOTED");
 334                 Overlap::EqualOrDisjoint
 335             } else {
 336                 // different promoteds - base case, disjoint
 337                 debug!("place_element_conflict: DISJOINT-PROMOTED");
 338                 Overlap::Disjoint
 339             }
 340         }
 341         (Place::Local(_), Place::Promoted(_)) | (Place::Promoted(_), Place::Local(_)) |
 342         (Place::Promoted(_), Place::Static(_)) | (Place::Static(_), Place::Promoted(_)) |
 343         (Place::Local(_), Place::Static(_)) | (Place::Static(_), Place::Local(_)) => {
 344             debug!("place_element_conflict: DISJOINT-STATIC-LOCAL-PROMOTED");
 345             Overlap::Disjoint
 346         }
 347         (Place::Projection(pi1), Place::Projection(pi2)) => {
 348             match (&pi1.elem, &pi2.elem) {
 349                 (ProjectionElem::Deref, ProjectionElem::Deref) => {
 350                     // derefs (e.g. `*x` vs. `*x`) - recur.
 351                     debug!("place_element_conflict: DISJOINT-OR-EQ-DEREF");
 352                     Overlap::EqualOrDisjoint
 353                 }
 354                 (ProjectionElem::Field(f1, _), ProjectionElem::Field(f2, _)) => {
 355                     if f1 == f2 {
 356                         // same field (e.g. `a.y` vs. `a.y`) - recur.
 357                         debug!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
 358                         Overlap::EqualOrDisjoint
 359                     } else {
 360                         let ty = pi1.base.ty(mir, tcx).to_ty(tcx);
 361                         match ty.sty {
 362                             ty::TyAdt(def, _) if def.is_union() => {
 363                                 // Different fields of a union, we are basically stuck.
 364                                 debug!("place_element_conflict: STUCK-UNION");
 365                                 Overlap::Arbitrary
 366                             }
 367                             _ => {
 368                                 // Different fields of a struct (`a.x` vs. `a.y`). Disjoint!
 369                                 debug!("place_element_conflict: DISJOINT-FIELD");
 370                                 Overlap::Disjoint
 371                             }
 372                         }
 373                     }
 374                 }
 375                 (ProjectionElem::Downcast(_, v1), ProjectionElem::Downcast(_, v2)) => {
 376                     // different variants are treated as having disjoint fields,
 377                     // even if they occupy the same "space", because it's
 378                     // impossible for 2 variants of the same enum to exist
 379                     // (and therefore, to be borrowed) at the same time.
 380                     //
 381                     // Note that this is different from unions - we *do* allow
 382                     // this code to compile:
 383                     //
 384                     // ```
 385                     // fn foo(x: &mut Result<i32, i32>) {
 386                     //     let mut v = None;
 387                     //     if let Ok(ref mut a) = *x {
 388                     //         v = Some(a);
 389                     //     }
 390                     //     // here, you would *think* that the
 391                     //     // *entirety* of `x` would be borrowed,
 392                     //     // but in fact only the `Ok` variant is,
 393                     //     // so the `Err` variant is *entirely free*:
 394                     //     if let Err(ref mut a) = *x {
 395                     //         v = Some(a);
 396                     //     }
 397                     //     drop(v);
 398                     // }
 399                     // ```
 400                     if v1 == v2 {
 401                         debug!("place_element_conflict: DISJOINT-OR-EQ-FIELD");
 402                         Overlap::EqualOrDisjoint
 403                     } else {
 404                         debug!("place_element_conflict: DISJOINT-FIELD");
 405                         Overlap::Disjoint
 406                     }
 407                 }
 408                 (ProjectionElem::Index(..), ProjectionElem::Index(..))
 409                 | (ProjectionElem::Index(..), ProjectionElem::ConstantIndex { .. })
 410                 | (ProjectionElem::Index(..), ProjectionElem::Subslice { .. })
 411                 | (ProjectionElem::ConstantIndex { .. }, ProjectionElem::Index(..))
 412                 | (ProjectionElem::Subslice { .. }, ProjectionElem::Index(..)) => {
 413                     // Array indexes (`a[0]` vs. `a[i]`). These can either be disjoint
 414                     // (if the indexes differ) or equal (if they are the same), so this
 415                     // is the recursive case that gives "equal *or* disjoint" its meaning.
 416                     debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-INDEX");
 417                     Overlap::EqualOrDisjoint
 418                 }
 419                 (ProjectionElem::ConstantIndex { offset: o1, min_length: _, from_end: false },
 420                     ProjectionElem::ConstantIndex { offset: o2, min_length: _, from_end: false })
 421                 | (ProjectionElem::ConstantIndex { offset: o1, min_length: _, from_end: true },
 422                     ProjectionElem::ConstantIndex {
 423                         offset: o2, min_length: _, from_end: true }) => {
 424                     if o1 == o2 {
 425                         debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX");
 426                         Overlap::EqualOrDisjoint
 427                     } else {
 428                         debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX");
 429                         Overlap::Disjoint
 430                     }
 431                 }
 432                 (ProjectionElem::ConstantIndex {
 433                     offset: offset_from_begin, min_length: min_length1, from_end: false },
 434                     ProjectionElem::ConstantIndex {
 435                         offset: offset_from_end, min_length: min_length2, from_end: true })
 436                 | (ProjectionElem::ConstantIndex {
 437                     offset: offset_from_end, min_length: min_length1, from_end: true },
 438                    ProjectionElem::ConstantIndex {
 439                        offset: offset_from_begin, min_length: min_length2, from_end: false }) => {
 440                     // both patterns matched so it must be at least the greater of the two
 441                     let min_length = max(min_length1, min_length2);
 442                     // `offset_from_end` can be in range `[1..min_length]`, 1 indicates the last
 443                     // element (like -1 in Python) and `min_length` the first.
 444                     // Therefore, `min_length - offset_from_end` gives the minimal possible
 445                     // offset from the beginning
 446                     if *offset_from_begin >= min_length - offset_from_end {
 447                         debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-FE");
 448                         Overlap::EqualOrDisjoint
 449                     } else {
 450                         debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-FE");
 451                         Overlap::Disjoint
 452                     }
 453                 }
 454                 (ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false },
 455                  ProjectionElem::Subslice {from, .. })
 456                 | (ProjectionElem::Subslice {from, .. },
 457                     ProjectionElem::ConstantIndex { offset, min_length: _, from_end: false }) => {
 458                     if offset >= from {
 459                         debug!(
 460                             "place_element_conflict: DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-SUBSLICE");
 461                         Overlap::EqualOrDisjoint
 462                     } else {
 463                         debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-SUBSLICE");
 464                         Overlap::Disjoint
 465                     }
 466                 }
 467                 (ProjectionElem::ConstantIndex { offset, min_length: _, from_end: true },
 468                  ProjectionElem::Subslice {from: _, to })
 469                 | (ProjectionElem::Subslice {from: _, to },
 470                     ProjectionElem::ConstantIndex { offset, min_length: _, from_end: true }) => {
 471                     if offset > to {
 472                         debug!("place_element_conflict: \
 473                                DISJOINT-OR-EQ-ARRAY-CONSTANT-INDEX-SUBSLICE-FE");
 474                         Overlap::EqualOrDisjoint
 475                     } else {
 476                         debug!("place_element_conflict: DISJOINT-ARRAY-CONSTANT-INDEX-SUBSLICE-FE");
 477                         Overlap::Disjoint
 478                     }
 479                 }
 480                 (ProjectionElem::Subslice { .. }, ProjectionElem::Subslice { .. }) => {
 481                     debug!("place_element_conflict: DISJOINT-OR-EQ-ARRAY-SUBSLICES");
 482                      Overlap::EqualOrDisjoint
 483                 }
 484                 (ProjectionElem::Deref, _)
 485                 | (ProjectionElem::Field(..), _)
 486                 | (ProjectionElem::Index(..), _)
 487                 | (ProjectionElem::ConstantIndex { .. }, _)
 488                 | (ProjectionElem::Subslice { .. }, _)
 489                 | (ProjectionElem::Downcast(..), _) => bug!(
 490                     "mismatched projections in place_element_conflict: {:?} and {:?}",
 491                     elem1,
 492                     elem2
 493                 ),
 494             }
 495         }
 496         (Place::Projection(_), _) | (_, Place::Projection(_)) => bug!(
 497             "unexpected elements in place_element_conflict: {:?} and {:?}",
 498             elem1,
 499             elem2
 500         ),
 501     }
 502 }