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