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::middle::ty;
  23 use rustc::middle::mem_categorization as mc;
  24 use rustc::util::ppaux::{Repr, UserString};
  25 use std::mem;
  26 use std::rc::Rc;
  27 use syntax::ast;
  28 use syntax::ast_map;
  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, print) = {
 122         let attrs : &[ast::Attribute];
 123         attrs = match tcx.map.find(id) {
 124             Some(ast_map::NodeItem(ref item)) =>
 125                 &item.attrs[],
 126             Some(ast_map::NodeImplItem(&ast::MethodImplItem(ref m))) =>
 127                 &m.attrs[],
 128             Some(ast_map::NodeTraitItem(&ast::ProvidedMethod(ref m))) =>
 129                 &m.attrs[],
 130             _ => &[][],
 131         };
 132
 133         let span_err =
 134             attrs.iter().any(|a| a.check_name("rustc_move_fragments"));
 135         let print = tcx.sess.opts.debugging_opts.print_move_fragments;
 136
 137         (span_err, print)
 138     };
 139
 140     if !span_err && !print { return; }
 141
 142     let instrument_all_paths = |&: kind, vec_rc: &Vec<MovePathIndex>| {
 143         for (i, mpi) in vec_rc.iter().enumerate() {
 144             let render = |&:| this.path_loan_path(*mpi).user_string(tcx);
 145             if span_err {
 146                 tcx.sess.span_err(sp, &format!("{}: `{}`", kind, render())[]);
 147             }
 148             if print {
 149                 println!("id:{} {}[{}] `{}`", id, kind, i, render());
 150             }
 151         }
 152     };
 153
 154     let instrument_all_fragments = |&: kind, vec_rc: &Vec<Fragment>| {
 155         for (i, f) in vec_rc.iter().enumerate() {
 156             let render = |&:| f.loan_path_user_string(this, tcx);
 157             if span_err {
 158                 tcx.sess.span_err(sp, &format!("{}: `{}`", kind, render())[]);
 159             }
 160             if print {
 161                 println!("id:{} {}[{}] `{}`", id, kind, i, render());
 162             }
 163         }
 164     };
 165
 166     let fragments = this.fragments.borrow();
 167     instrument_all_paths("moved_leaf_path", &fragments.moved_leaf_paths);
 168     instrument_all_fragments("unmoved_fragment", &fragments.unmoved_fragments);
 169     instrument_all_paths("parent_of_fragments", &fragments.parents_of_fragments);
 170     instrument_all_paths("assigned_leaf_path", &fragments.assigned_leaf_paths);
 171 }
 172
 173 /// Normalizes the fragment sets in `this`; i.e., removes duplicate entries, constructs the set of
 174 /// parents, and constructs the left-over fragments.
 175 ///
 176 /// Note: "left-over fragments" means paths that were not directly referenced in moves nor
 177 /// assignments, but must nonetheless be tracked as potential drop obligations.
 178 pub fn fixup_fragment_sets<'tcx>(this: &MoveData<'tcx>, tcx: &ty::ctxt<'tcx>) {
 179
 180     let mut fragments = this.fragments.borrow_mut();
 181
 182     // Swap out contents of fragments so that we can modify the fields
 183     // without borrowing the common fragments.
 184     let mut unmoved = mem::replace(&mut fragments.unmoved_fragments, vec![]);
 185     let mut parents = mem::replace(&mut fragments.parents_of_fragments, vec![]);
 186     let mut moved = mem::replace(&mut fragments.moved_leaf_paths, vec![]);
 187     let mut assigned = mem::replace(&mut fragments.assigned_leaf_paths, vec![]);
 188
 189     let path_lps = |&: mpis: &[MovePathIndex]| -> Vec<String> {
 190         mpis.iter().map(|mpi| this.path_loan_path(*mpi).repr(tcx)).collect()
 191     };
 192
 193     let frag_lps = |&: fs: &[Fragment]| -> Vec<String> {
 194         fs.iter().map(|f| f.loan_path_repr(this, tcx)).collect()
 195     };
 196
 197     // First, filter out duplicates
 198     moved.sort();
 199     moved.dedup();
 200     debug!("fragments 1 moved: {:?}", path_lps(&moved[]));
 201
 202     assigned.sort();
 203     assigned.dedup();
 204     debug!("fragments 1 assigned: {:?}", path_lps(&assigned[]));
 205
 206     // Second, build parents from the moved and assigned.
 207     for m in &moved {
 208         let mut p = this.path_parent(*m);
 209         while p != InvalidMovePathIndex {
 210             parents.push(p);
 211             p = this.path_parent(p);
 212         }
 213     }
 214     for a in &assigned {
 215         let mut p = this.path_parent(*a);
 216         while p != InvalidMovePathIndex {
 217             parents.push(p);
 218             p = this.path_parent(p);
 219         }
 220     }
 221
 222     parents.sort();
 223     parents.dedup();
 224     debug!("fragments 2 parents: {:?}", path_lps(&parents[]));
 225
 226     // Third, filter the moved and assigned fragments down to just the non-parents
 227     moved.retain(|f| non_member(*f, &parents[]));
 228     debug!("fragments 3 moved: {:?}", path_lps(&moved[]));
 229
 230     assigned.retain(|f| non_member(*f, &parents[]));
 231     debug!("fragments 3 assigned: {:?}", path_lps(&assigned[]));
 232
 233     // Fourth, build the leftover from the moved, assigned, and parents.
 234     for m in &moved {
 235         let lp = this.path_loan_path(*m);
 236         add_fragment_siblings(this, tcx, &mut unmoved, lp, None);
 237     }
 238     for a in &assigned {
 239         let lp = this.path_loan_path(*a);
 240         add_fragment_siblings(this, tcx, &mut unmoved, lp, None);
 241     }
 242     for p in &parents {
 243         let lp = this.path_loan_path(*p);
 244         add_fragment_siblings(this, tcx, &mut unmoved, lp, None);
 245     }
 246
 247     unmoved.sort();
 248     unmoved.dedup();
 249     debug!("fragments 4 unmoved: {:?}", frag_lps(&unmoved[]));
 250
 251     // Fifth, filter the leftover fragments down to its core.
 252     unmoved.retain(|f| match *f {
 253         AllButOneFrom(_) => true,
 254         Just(mpi) => non_member(mpi, &parents[]) &&
 255             non_member(mpi, &moved[]) &&
 256             non_member(mpi, &assigned[])
 257     });
 258     debug!("fragments 5 unmoved: {:?}", frag_lps(&unmoved[]));
 259
 260     // Swap contents back in.
 261     fragments.unmoved_fragments = unmoved;
 262     fragments.parents_of_fragments = parents;
 263     fragments.moved_leaf_paths = moved;
 264     fragments.assigned_leaf_paths = assigned;
 265
 266     return;
 267
 268     fn non_member(elem: MovePathIndex, set: &[MovePathIndex]) -> bool {
 269         match set.binary_search(&elem) {
 270             Ok(_) => false,
 271             Err(_) => true,
 272         }
 273     }
 274 }
 275
 276 /// Adds all of the precisely-tracked siblings of `lp` as potential move paths of interest. For
 277 /// example, if `lp` represents `s.x.j`, then adds moves paths for `s.x.i` and `s.x.k`, the
 278 /// siblings of `s.x.j`.
 279 fn add_fragment_siblings<'tcx>(this: &MoveData<'tcx>,
 280                                tcx: &ty::ctxt<'tcx>,
 281                                gathered_fragments: &mut Vec<Fragment>,
 282                                lp: Rc<LoanPath<'tcx>>,
 283                                origin_id: Option<ast::NodeId>) {
 284     match lp.kind {
 285         LpVar(_) | LpUpvar(..) => {} // Local variables have no siblings.
 286
 287         // Consuming a downcast is like consuming the original value, so propage inward.
 288         LpDowncast(ref loan_parent, _) => {
 289             add_fragment_siblings(this, tcx, gathered_fragments, loan_parent.clone(), origin_id);
 290         }
 291
 292         // *LV for Unique consumes the contents of the box (at
 293         // least when it is non-copy...), so propagate inward.
 294         LpExtend(ref loan_parent, _, LpDeref(mc::Unique)) => {
 295             add_fragment_siblings(this, tcx, gathered_fragments, loan_parent.clone(), origin_id);
 296         }
 297
 298         // *LV for unsafe and borrowed pointers do not consume their loan path, so stop here.
 299         LpExtend(_, _, LpDeref(mc::UnsafePtr(..)))   |
 300         LpExtend(_, _, LpDeref(mc::Implicit(..)))    |
 301         LpExtend(_, _, LpDeref(mc::BorrowedPtr(..))) => {}
 302
 303         // FIXME(pnkfelix): LV[j] should be tracked, at least in the
 304         // sense of we will track the remaining drop obligation of the
 305         // rest of the array.
 306         //
 307         // LV[j] is not tracked precisely
 308         LpExtend(_, _, LpInterior(mc::InteriorElement(_))) => {
 309             let mp = this.move_path(tcx, lp.clone());
 310             gathered_fragments.push(AllButOneFrom(mp));
 311         }
 312
 313         // field access LV.x and tuple access LV#k are the cases
 314         // we are interested in
 315         LpExtend(ref loan_parent, mc,
 316                  LpInterior(mc::InteriorField(ref field_name))) => {
 317             let enum_variant_info = match loan_parent.kind {
 318                 LpDowncast(ref loan_parent_2, variant_def_id) =>
 319                     Some((variant_def_id, loan_parent_2.clone())),
 320                 LpExtend(..) | LpVar(..) | LpUpvar(..) =>
 321                     None,
 322             };
 323             add_fragment_siblings_for_extension(
 324                 this,
 325                 tcx,
 326                 gathered_fragments,
 327                 loan_parent, mc, field_name, &lp, origin_id, enum_variant_info);
 328         }
 329     }
 330 }
 331
 332 /// We have determined that `origin_lp` destructures to LpExtend(parent, original_field_name).
 333 /// Based on this, add move paths for all of the siblings of `origin_lp`.
 334 fn add_fragment_siblings_for_extension<'tcx>(this: &MoveData<'tcx>,
 335                                              tcx: &ty::ctxt<'tcx>,
 336                                              gathered_fragments: &mut Vec<Fragment>,
 337                                              parent_lp: &Rc<LoanPath<'tcx>>,
 338                                              mc: mc::MutabilityCategory,
 339                                              origin_field_name: &mc::FieldName,
 340                                              origin_lp: &Rc<LoanPath<'tcx>>,
 341                                              origin_id: Option<ast::NodeId>,
 342                                              enum_variant_info: Option<(ast::DefId,
 343                                                                         Rc<LoanPath<'tcx>>)>) {
 344     let parent_ty = parent_lp.to_type();
 345
 346     let mut add_fragment_sibling_local = |&mut : field_name, variant_did| {
 347         add_fragment_sibling_core(
 348             this, tcx, gathered_fragments, parent_lp.clone(), mc, field_name, origin_lp,
 349             variant_did);
 350     };
 351
 352     match (&parent_ty.sty, enum_variant_info) {
 353         (&ty::ty_tup(ref v), None) => {
 354             let tuple_idx = match *origin_field_name {
 355                 mc::PositionalField(tuple_idx) => tuple_idx,
 356                 mc::NamedField(_) =>
 357                     panic!("tuple type {} should not have named fields.",
 358                            parent_ty.repr(tcx)),
 359             };
 360             let tuple_len = v.len();
 361             for i in 0..tuple_len {
 362                 if i == tuple_idx { continue }
 363                 let field_name = mc::PositionalField(i);
 364                 add_fragment_sibling_local(field_name, None);
 365             }
 366         }
 367
 368         (&ty::ty_struct(def_id, ref _substs), None) => {
 369             let fields = ty::lookup_struct_fields(tcx, def_id);
 370             match *origin_field_name {
 371                 mc::NamedField(ast_name) => {
 372                     for f in &fields {
 373                         if f.name == ast_name {
 374                             continue;
 375                         }
 376                         let field_name = mc::NamedField(f.name);
 377                         add_fragment_sibling_local(field_name, None);
 378                     }
 379                 }
 380                 mc::PositionalField(tuple_idx) => {
 381                     for (i, _f) in fields.iter().enumerate() {
 382                         if i == tuple_idx {
 383                             continue
 384                         }
 385                         let field_name = mc::PositionalField(i);
 386                         add_fragment_sibling_local(field_name, None);
 387                     }
 388                 }
 389             }
 390         }
 391
 392         (&ty::ty_enum(enum_def_id, substs), ref enum_variant_info) => {
 393             let variant_info = {
 394                 let mut variants = ty::substd_enum_variants(tcx, enum_def_id, substs);
 395                 match *enum_variant_info {
 396                     Some((variant_def_id, ref _lp2)) =>
 397                         variants.iter()
 398                         .find(|variant| variant.id == variant_def_id)
 399                         .expect("enum_variant_with_id(): no variant exists with that ID")
 400                         .clone(),
 401                     None => {
 402                         assert_eq!(variants.len(), 1);
 403                         variants.pop().unwrap()
 404                     }
 405                 }
 406             };
 407             match *origin_field_name {
 408                 mc::NamedField(ast_name) => {
 409                     let variant_arg_names = variant_info.arg_names.as_ref().unwrap();
 410                     for variant_arg_ident in variant_arg_names {
 411                         if variant_arg_ident.name == ast_name {
 412                             continue;
 413                         }
 414                         let field_name = mc::NamedField(variant_arg_ident.name);
 415                         add_fragment_sibling_local(field_name, Some(variant_info.id));
 416                     }
 417                 }
 418                 mc::PositionalField(tuple_idx) => {
 419                     let variant_arg_types = &variant_info.args;
 420                     for (i, _variant_arg_ty) in variant_arg_types.iter().enumerate() {
 421                         if tuple_idx == i {
 422                             continue;
 423                         }
 424                         let field_name = mc::PositionalField(i);
 425                         add_fragment_sibling_local(field_name, None);
 426                     }
 427                 }
 428             }
 429         }
 430
 431         ref sty_and_variant_info => {
 432             let msg = format!("type {} ({:?}) is not fragmentable",
 433                               parent_ty.repr(tcx), sty_and_variant_info);
 434             let opt_span = origin_id.and_then(|id|tcx.map.opt_span(id));
 435             tcx.sess.opt_span_bug(opt_span, &msg[])
 436         }
 437     }
 438 }
 439
 440 /// Adds the single sibling `LpExtend(parent, new_field_name)` of `origin_lp` (the original
 441 /// loan-path).
 442 fn add_fragment_sibling_core<'tcx>(this: &MoveData<'tcx>,
 443                                    tcx: &ty::ctxt<'tcx>,
 444                                    gathered_fragments: &mut Vec<Fragment>,
 445                                    parent: Rc<LoanPath<'tcx>>,
 446                                    mc: mc::MutabilityCategory,
 447                                    new_field_name: mc::FieldName,
 448                                    origin_lp: &Rc<LoanPath<'tcx>>,
 449                                    enum_variant_did: Option<ast::DefId>) -> MovePathIndex {
 450     let opt_variant_did = match parent.kind {
 451         LpDowncast(_, variant_did) => Some(variant_did),
 452         LpVar(..) | LpUpvar(..) | LpExtend(..) => enum_variant_did,
 453     };
 454
 455     let loan_path_elem = LpInterior(mc::InteriorField(new_field_name));
 456     let new_lp_type = match new_field_name {
 457         mc::NamedField(ast_name) =>
 458             ty::named_element_ty(tcx, parent.to_type(), ast_name, opt_variant_did),
 459         mc::PositionalField(idx) =>
 460             ty::positional_element_ty(tcx, parent.to_type(), idx, opt_variant_did),
 461     };
 462     let new_lp_variant = LpExtend(parent, mc, loan_path_elem);
 463     let new_lp = LoanPath::new(new_lp_variant, new_lp_type.unwrap());
 464     debug!("add_fragment_sibling_core(new_lp={}, origin_lp={})",
 465            new_lp.repr(tcx), origin_lp.repr(tcx));
 466     let mp = this.move_path(tcx, Rc::new(new_lp));
 467
 468     // Do not worry about checking for duplicates here; we will sort
 469     // and dedup after all are added.
 470     gathered_fragments.push(Just(mp));
 471
 472     mp
 473 }