src/librustc_borrowck/borrowck/fragments.rs

   1 // Copyright 2012-2014 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 //! Helper routines used for fragmenting structural paths due to moves for
  12 //! tracking drop obligations. Please see the extensive comments in the
  13 //! section "Structural fragments" in `README.md`.
  14
  15 use self::Fragment::*;
  16
  17 use borrowck::InteriorKind::{InteriorField, InteriorElement};
  18 use borrowck::LoanPath;
  19 use borrowck::LoanPathKind::{LpVar, LpUpvar, LpDowncast, LpExtend};
  20 use borrowck::LoanPathElem::{LpDeref, LpInterior};
  21 use borrowck::move_data::InvalidMovePathIndex;
  22 use borrowck::move_data::{MoveData, MovePathIndex};
  23 use rustc::middle::ty;
  24 use rustc::middle::mem_categorization as mc;
  25 use rustc::util::ppaux::{Repr, UserString};
  26 use std::mem;
  27 use std::rc::Rc;
  28 use syntax::ast;
  29 use syntax::attr::AttrMetaMethods;
  30 use syntax::codemap::Span;
  31
  32 #[derive(PartialEq, Eq, PartialOrd, Ord)]
  33 enum Fragment {
  34     // This represents the path described by the move path index
  35     Just(MovePathIndex),
  36
  37     // This represents the collection of all but one of the elements
  38     // from an array at the path described by the move path index.
  39     // Note that attached MovePathIndex should have mem_categorization
  40     // of InteriorElement (i.e. array dereference `&foo[..]`).
  41     AllButOneFrom(MovePathIndex),
  42 }
  43
  44 impl Fragment {
  45     fn loan_path_repr<'tcx>(&self, move_data: &MoveData<'tcx>, tcx: &ty::ctxt<'tcx>) -> String {
  46         let repr = |mpi| move_data.path_loan_path(mpi).repr(tcx);
  47         match *self {
  48             Just(mpi) => repr(mpi),
  49             AllButOneFrom(mpi) => format!("$(allbutone {})", repr(mpi)),
  50         }
  51     }
  52
  53     fn loan_path_user_string<'tcx>(&self,
  54                                    move_data: &MoveData<'tcx>,
  55                                    tcx: &ty::ctxt<'tcx>) -> String {
  56         let user_string = |mpi| move_data.path_loan_path(mpi).user_string(tcx);
  57         match *self {
  58             Just(mpi) => user_string(mpi),
  59             AllButOneFrom(mpi) => format!("$(allbutone {})", user_string(mpi)),
  60         }
  61     }
  62 }
  63
  64 pub struct FragmentSets {
  65     /// During move_data construction, `moved_leaf_paths` tracks paths
  66     /// that have been used directly by being moved out of.  When
  67     /// move_data construction has been completed, `moved_leaf_paths`
  68     /// tracks such paths that are *leaf fragments* (e.g. `a.j` if we
  69     /// never move out any child like `a.j.x`); any parent paths
  70     /// (e.g. `a` for the `a.j` example) are moved over to
  71     /// `parents_of_fragments`.
  72     moved_leaf_paths: Vec<MovePathIndex>,
  73
  74     /// `assigned_leaf_paths` tracks paths that have been used
  75     /// directly by being overwritten, but is otherwise much like
  76     /// `moved_leaf_paths`.
  77     assigned_leaf_paths: Vec<MovePathIndex>,
  78
  79     /// `parents_of_fragments` tracks paths that are definitely
  80     /// parents of paths that have been moved.
  81     ///
  82     /// FIXME(pnkfelix) probably do not want/need
  83     /// `parents_of_fragments` at all, if we can avoid it.
  84     ///
  85     /// Update: I do not see a way to to avoid it.  Maybe just remove
  86     /// above fixme, or at least document why doing this may be hard.
  87     parents_of_fragments: Vec<MovePathIndex>,
  88
  89     /// During move_data construction (specifically the
  90     /// fixup_fragment_sets call), `unmoved_fragments` tracks paths
  91     /// that have been "left behind" after a sibling has been moved or
  92     /// assigned.  When move_data construction has been completed,
  93     /// `unmoved_fragments` tracks paths that were *only* results of
  94     /// being left-behind, and never directly moved themselves.
  95     unmoved_fragments: Vec<Fragment>,
  96 }
  97
  98 impl FragmentSets {
  99     pub fn new() -> FragmentSets {
 100         FragmentSets {
 101             unmoved_fragments: Vec::new(),
 102             moved_leaf_paths: Vec::new(),
 103             assigned_leaf_paths: Vec::new(),
 104             parents_of_fragments: Vec::new(),
 105         }
 106     }
 107
 108     pub fn add_move(&mut self, path_index: MovePathIndex) {
 109         self.moved_leaf_paths.push(path_index);
 110     }
 111
 112     pub fn add_assignment(&mut self, path_index: MovePathIndex) {
 113         self.assigned_leaf_paths.push(path_index);
 114     }
 115 }
 116
 117 pub fn instrument_move_fragments<'tcx>(this: &MoveData<'tcx>,
 118                                        tcx: &ty::ctxt<'tcx>,
 119                                        sp: Span,
 120                                        id: ast::NodeId) {
 121     let span_err = tcx.map.attrs(id).iter()
 122                           .any(|a| a.check_name("rustc_move_fragments"));
 123     let print = tcx.sess.opts.debugging_opts.print_move_fragments;
 124
 125     if !span_err && !print { return; }
 126
 127     let instrument_all_paths = |kind, vec_rc: &Vec<MovePathIndex>| {
 128         for (i, mpi) in vec_rc.iter().enumerate() {
 129             let render = || this.path_loan_path(*mpi).user_string(tcx);
 130             if span_err {
 131                 tcx.sess.span_err(sp, &format!("{}: `{}`", kind, render()));
 132             }
 133             if print {
 134                 println!("id:{} {}[{}] `{}`", id, kind, i, render());
 135             }
 136         }
 137     };
 138
 139     let instrument_all_fragments = |kind, vec_rc: &Vec<Fragment>| {
 140         for (i, f) in vec_rc.iter().enumerate() {
 141             let render = || f.loan_path_user_string(this, tcx);
 142             if span_err {
 143                 tcx.sess.span_err(sp, &format!("{}: `{}`", kind, render()));
 144             }
 145             if print {
 146                 println!("id:{} {}[{}] `{}`", id, kind, i, render());
 147             }
 148         }
 149     };
 150
 151     let fragments = this.fragments.borrow();
 152     instrument_all_paths("moved_leaf_path", &fragments.moved_leaf_paths);
 153     instrument_all_fragments("unmoved_fragment", &fragments.unmoved_fragments);
 154     instrument_all_paths("parent_of_fragments", &fragments.parents_of_fragments);
 155     instrument_all_paths("assigned_leaf_path", &fragments.assigned_leaf_paths);
 156 }
 157
 158 /// Normalizes the fragment sets in `this`; i.e., removes duplicate entries, constructs the set of
 159 /// parents, and constructs the left-over fragments.
 160 ///
 161 /// Note: "left-over fragments" means paths that were not directly referenced in moves nor
 162 /// assignments, but must nonetheless be tracked as potential drop obligations.
 163 pub fn fixup_fragment_sets<'tcx>(this: &MoveData<'tcx>, tcx: &ty::ctxt<'tcx>) {
 164
 165     let mut fragments = this.fragments.borrow_mut();
 166
 167     // Swap out contents of fragments so that we can modify the fields
 168     // without borrowing the common fragments.
 169     let mut unmoved = mem::replace(&mut fragments.unmoved_fragments, vec![]);
 170     let mut parents = mem::replace(&mut fragments.parents_of_fragments, vec![]);
 171     let mut moved = mem::replace(&mut fragments.moved_leaf_paths, vec![]);
 172     let mut assigned = mem::replace(&mut fragments.assigned_leaf_paths, vec![]);
 173
 174     let path_lps = |mpis: &[MovePathIndex]| -> Vec<String> {
 175         mpis.iter().map(|mpi| this.path_loan_path(*mpi).repr(tcx)).collect()
 176     };
 177
 178     let frag_lps = |fs: &[Fragment]| -> Vec<String> {
 179         fs.iter().map(|f| f.loan_path_repr(this, tcx)).collect()
 180     };
 181
 182     // First, filter out duplicates
 183     moved.sort();
 184     moved.dedup();
 185     debug!("fragments 1 moved: {:?}", path_lps(&moved[..]));
 186
 187     assigned.sort();
 188     assigned.dedup();
 189     debug!("fragments 1 assigned: {:?}", path_lps(&assigned[..]));
 190
 191     // Second, build parents from the moved and assigned.
 192     for m in &moved {
 193         let mut p = this.path_parent(*m);
 194         while p != InvalidMovePathIndex {
 195             parents.push(p);
 196             p = this.path_parent(p);
 197         }
 198     }
 199     for a in &assigned {
 200         let mut p = this.path_parent(*a);
 201         while p != InvalidMovePathIndex {
 202             parents.push(p);
 203             p = this.path_parent(p);
 204         }
 205     }
 206
 207     parents.sort();
 208     parents.dedup();
 209     debug!("fragments 2 parents: {:?}", path_lps(&parents[..]));
 210
 211     // Third, filter the moved and assigned fragments down to just the non-parents
 212     moved.retain(|f| non_member(*f, &parents[..]));
 213     debug!("fragments 3 moved: {:?}", path_lps(&moved[..]));
 214
 215     assigned.retain(|f| non_member(*f, &parents[..]));
 216     debug!("fragments 3 assigned: {:?}", path_lps(&assigned[..]));
 217
 218     // Fourth, build the leftover from the moved, assigned, and parents.
 219     for m in &moved {
 220         let lp = this.path_loan_path(*m);
 221         add_fragment_siblings(this, tcx, &mut unmoved, lp, None);
 222     }
 223     for a in &assigned {
 224         let lp = this.path_loan_path(*a);
 225         add_fragment_siblings(this, tcx, &mut unmoved, lp, None);
 226     }
 227     for p in &parents {
 228         let lp = this.path_loan_path(*p);
 229         add_fragment_siblings(this, tcx, &mut unmoved, lp, None);
 230     }
 231
 232     unmoved.sort();
 233     unmoved.dedup();
 234     debug!("fragments 4 unmoved: {:?}", frag_lps(&unmoved[..]));
 235
 236     // Fifth, filter the leftover fragments down to its core.
 237     unmoved.retain(|f| match *f {
 238         AllButOneFrom(_) => true,
 239         Just(mpi) => non_member(mpi, &parents[..]) &&
 240             non_member(mpi, &moved[..]) &&
 241             non_member(mpi, &assigned[..])
 242     });
 243     debug!("fragments 5 unmoved: {:?}", frag_lps(&unmoved[..]));
 244
 245     // Swap contents back in.
 246     fragments.unmoved_fragments = unmoved;
 247     fragments.parents_of_fragments = parents;
 248     fragments.moved_leaf_paths = moved;
 249     fragments.assigned_leaf_paths = assigned;
 250
 251     return;
 252
 253     fn non_member(elem: MovePathIndex, set: &[MovePathIndex]) -> bool {
 254         match set.binary_search(&elem) {
 255             Ok(_) => false,
 256             Err(_) => true,
 257         }
 258     }
 259 }
 260
 261 /// Adds all of the precisely-tracked siblings of `lp` as potential move paths of interest. For
 262 /// example, if `lp` represents `s.x.j`, then adds moves paths for `s.x.i` and `s.x.k`, the
 263 /// siblings of `s.x.j`.
 264 fn add_fragment_siblings<'tcx>(this: &MoveData<'tcx>,
 265                                tcx: &ty::ctxt<'tcx>,
 266                                gathered_fragments: &mut Vec<Fragment>,
 267                                lp: Rc<LoanPath<'tcx>>,
 268                                origin_id: Option<ast::NodeId>) {
 269     match lp.kind {
 270         LpVar(_) | LpUpvar(..) => {} // Local variables have no siblings.
 271
 272         // Consuming a downcast is like consuming the original value, so propage inward.
 273         LpDowncast(ref loan_parent, _) => {
 274             add_fragment_siblings(this, tcx, gathered_fragments, loan_parent.clone(), origin_id);
 275         }
 276
 277         // *LV for Unique consumes the contents of the box (at
 278         // least when it is non-copy...), so propagate inward.
 279         LpExtend(ref loan_parent, _, LpDeref(mc::Unique)) => {
 280             add_fragment_siblings(this, tcx, gathered_fragments, loan_parent.clone(), origin_id);
 281         }
 282
 283         // *LV for unsafe and borrowed pointers do not consume their loan path, so stop here.
 284         LpExtend(_, _, LpDeref(mc::UnsafePtr(..)))   |
 285         LpExtend(_, _, LpDeref(mc::Implicit(..)))    |
 286         LpExtend(_, _, LpDeref(mc::BorrowedPtr(..))) => {}
 287
 288         // FIXME (pnkfelix): LV[j] should be tracked, at least in the
 289         // sense of we will track the remaining drop obligation of the
 290         // rest of the array.
 291         //
 292         // Well, either that or LV[j] should be made illegal.
 293         // But even then, we will need to deal with destructuring
 294         // bind.
 295         //
 296         // Anyway, for now: LV[j] is not tracked precisely
 297         LpExtend(_, _, LpInterior(InteriorElement(..))) => {
 298             let mp = this.move_path(tcx, lp.clone());
 299             gathered_fragments.push(AllButOneFrom(mp));
 300         }
 301
 302         // field access LV.x and tuple access LV#k are the cases
 303         // we are interested in
 304         LpExtend(ref loan_parent, mc,
 305                  LpInterior(InteriorField(ref field_name))) => {
 306             let enum_variant_info = match loan_parent.kind {
 307                 LpDowncast(ref loan_parent_2, variant_def_id) =>
 308                     Some((variant_def_id, loan_parent_2.clone())),
 309                 LpExtend(..) | LpVar(..) | LpUpvar(..) =>
 310                     None,
 311             };
 312             add_fragment_siblings_for_extension(
 313                 this,
 314                 tcx,
 315                 gathered_fragments,
 316                 loan_parent, mc, field_name, &lp, origin_id, enum_variant_info);
 317         }
 318     }
 319 }
 320
 321 /// We have determined that `origin_lp` destructures to LpExtend(parent, original_field_name).
 322 /// Based on this, add move paths for all of the siblings of `origin_lp`.
 323 fn add_fragment_siblings_for_extension<'tcx>(this: &MoveData<'tcx>,
 324                                              tcx: &ty::ctxt<'tcx>,
 325                                              gathered_fragments: &mut Vec<Fragment>,
 326                                              parent_lp: &Rc<LoanPath<'tcx>>,
 327                                              mc: mc::MutabilityCategory,
 328                                              origin_field_name: &mc::FieldName,
 329                                              origin_lp: &Rc<LoanPath<'tcx>>,
 330                                              origin_id: Option<ast::NodeId>,
 331                                              enum_variant_info: Option<(ast::DefId,
 332                                                                         Rc<LoanPath<'tcx>>)>) {
 333     let parent_ty = parent_lp.to_type();
 334
 335     let mut add_fragment_sibling_local = |field_name, variant_did| {
 336         add_fragment_sibling_core(
 337             this, tcx, gathered_fragments, parent_lp.clone(), mc, field_name, origin_lp,
 338             variant_did);
 339     };
 340
 341     match (&parent_ty.sty, enum_variant_info) {
 342         (&ty::ty_tup(ref v), None) => {
 343             let tuple_idx = match *origin_field_name {
 344                 mc::PositionalField(tuple_idx) => tuple_idx,
 345                 mc::NamedField(_) =>
 346                     panic!("tuple type {} should not have named fields.",
 347                            parent_ty.repr(tcx)),
 348             };
 349             let tuple_len = v.len();
 350             for i in 0..tuple_len {
 351                 if i == tuple_idx { continue }
 352                 let field_name = mc::PositionalField(i);
 353                 add_fragment_sibling_local(field_name, None);
 354             }
 355         }
 356
 357         (&ty::ty_struct(def_id, ref _substs), None) => {
 358             let fields = ty::lookup_struct_fields(tcx, def_id);
 359             match *origin_field_name {
 360                 mc::NamedField(ast_name) => {
 361                     for f in &fields {
 362                         if f.name == ast_name {
 363                             continue;
 364                         }
 365                         let field_name = mc::NamedField(f.name);
 366                         add_fragment_sibling_local(field_name, None);
 367                     }
 368                 }
 369                 mc::PositionalField(tuple_idx) => {
 370                     for (i, _f) in fields.iter().enumerate() {
 371                         if i == tuple_idx {
 372                             continue
 373                         }
 374                         let field_name = mc::PositionalField(i);
 375                         add_fragment_sibling_local(field_name, None);
 376                     }
 377                 }
 378             }
 379         }
 380
 381         (&ty::ty_enum(enum_def_id, substs), ref enum_variant_info) => {
 382             let variant_info = {
 383                 let mut variants = ty::substd_enum_variants(tcx, enum_def_id, substs);
 384                 match *enum_variant_info {
 385                     Some((variant_def_id, ref _lp2)) =>
 386                         variants.iter()
 387                         .find(|variant| variant.id == variant_def_id)
 388                         .expect("enum_variant_with_id(): no variant exists with that ID")
 389                         .clone(),
 390                     None => {
 391                         assert_eq!(variants.len(), 1);
 392                         variants.pop().unwrap()
 393                     }
 394                 }
 395             };
 396             match *origin_field_name {
 397                 mc::NamedField(ast_name) => {
 398                     let variant_arg_names = variant_info.arg_names.as_ref().unwrap();
 399                     for &variant_arg_name in variant_arg_names {
 400                         if variant_arg_name == ast_name {
 401                             continue;
 402                         }
 403                         let field_name = mc::NamedField(variant_arg_name);
 404                         add_fragment_sibling_local(field_name, Some(variant_info.id));
 405                     }
 406                 }
 407                 mc::PositionalField(tuple_idx) => {
 408                     let variant_arg_types = &variant_info.args;
 409                     for (i, _variant_arg_ty) in variant_arg_types.iter().enumerate() {
 410                         if tuple_idx == i {
 411                             continue;
 412                         }
 413                         let field_name = mc::PositionalField(i);
 414                         add_fragment_sibling_local(field_name, None);
 415                     }
 416                 }
 417             }
 418         }
 419
 420         ref sty_and_variant_info => {
 421             let msg = format!("type {} ({:?}) is not fragmentable",
 422                               parent_ty.repr(tcx), sty_and_variant_info);
 423             let opt_span = origin_id.and_then(|id|tcx.map.opt_span(id));
 424             tcx.sess.opt_span_bug(opt_span, &msg[..])
 425         }
 426     }
 427 }
 428
 429 /// Adds the single sibling `LpExtend(parent, new_field_name)` of `origin_lp` (the original
 430 /// loan-path).
 431 fn add_fragment_sibling_core<'tcx>(this: &MoveData<'tcx>,
 432                                    tcx: &ty::ctxt<'tcx>,
 433                                    gathered_fragments: &mut Vec<Fragment>,
 434                                    parent: Rc<LoanPath<'tcx>>,
 435                                    mc: mc::MutabilityCategory,
 436                                    new_field_name: mc::FieldName,
 437                                    origin_lp: &Rc<LoanPath<'tcx>>,
 438                                    enum_variant_did: Option<ast::DefId>) -> MovePathIndex {
 439     let opt_variant_did = match parent.kind {
 440         LpDowncast(_, variant_did) => Some(variant_did),
 441         LpVar(..) | LpUpvar(..) | LpExtend(..) => enum_variant_did,
 442     };
 443
 444     let loan_path_elem = LpInterior(InteriorField(new_field_name));
 445     let new_lp_type = match new_field_name {
 446         mc::NamedField(ast_name) =>
 447             ty::named_element_ty(tcx, parent.to_type(), ast_name, opt_variant_did),
 448         mc::PositionalField(idx) =>
 449             ty::positional_element_ty(tcx, parent.to_type(), idx, opt_variant_did),
 450     };
 451     let new_lp_variant = LpExtend(parent, mc, loan_path_elem);
 452     let new_lp = LoanPath::new(new_lp_variant, new_lp_type.unwrap());
 453     debug!("add_fragment_sibling_core(new_lp={}, origin_lp={})",
 454            new_lp.repr(tcx), origin_lp.repr(tcx));
 455     let mp = this.move_path(tcx, Rc::new(new_lp));
 456
 457     // Do not worry about checking for duplicates here; we will sort
 458     // and dedup after all are added.
 459     gathered_fragments.push(Just(mp));
 460
 461     mp
 462 }