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