Added fragments.rs: compute drop obligations remaining post moves.

Includes differentiation between assigned_fragments and
moved_fragments, support for all-but-one array fragments, and
instrumentation to print out the moved/assigned/unmmoved/parents for
each function, factored out into separate submodule.

9 files changed, 924 insertions, 8 deletions

diff --git a/src/librustc/middle/borrowck/doc.rs b/src/librustc/middle/borrowck/doc.rs
index 882b6bc8426..5b70d97b402 100644
--- a/src/librustc/middle/borrowck/doc.rs
+++ b/src/librustc/middle/borrowck/doc.rs
@@ -27,6 +27,7 @@ These docs are long. Search for the section you are interested in.
 - Formal model
 - Borrowing and loans
 - Moves and initialization
+- Drop flags and structural fragments
 - Future work
 
 # Overview
@@ -1019,6 +1020,175 @@ walk back over, identify all uses, assignments, and captures, and
 check that they are legal given the set of dataflow bits we have
 computed for that program point.
 
+# Drop flags and structural fragments
+
+In addition to the job of enforcing memory safety, the borrow checker
+code is also responsible for identifying the *structural fragments* of
+data in the function, to support out-of-band dynamic drop flags
+allocated on the stack. (For background, see [RFC PR #320].)
+
+[RFC PR #320]: https://github.com/rust-lang/rfcs/pull/320
+
+Semantically, each piece of data that has a destructor may need a
+boolean flag to indicate whether or not its destructor has been run
+yet. However, in many cases there is no need to actually maintain such
+a flag: It can be apparent from the code itself that a given path is
+always initialized (or always deinitialized) when control reaches the
+end of its owner's scope, and thus we can unconditionally emit (or
+not) the destructor invocation for that path.
+
+A simple example of this is the following:
+
+```rust
+struct D { p: int }
+impl D { fn new(x: int) -> D { ... }
+impl Drop for D { ... }
+
+fn foo(a: D, b: D, t: || -> bool) {
+    let c: D;
+    let d: D;
+    if t() { c = b; }
+}
+```
+
+At the end of the body of `foo`, the compiler knows that `a` is
+initialized, introducing a drop obligation (deallocating the boxed
+integer) for the end of `a`'s scope that is run unconditionally.
+Likewise the compiler knows that `d` is not initialized, and thus it
+leave out the drop code for `d`.
+
+The compiler cannot statically know the drop-state of `b` nor `c` at
+the end of their scope, since that depends on the value of
+`t`. Therefore, we need to insert boolean flags to track whether we
+need to drop `b` and `c`.
+
+However, the matter is not as simple as just mapping local variables
+to their corresponding drop flags when necessary. In particular, in
+addition to being able to move data out of local variables, Rust
+allows one to move values in and out of structured data.
+
+Consider the following:
+
+```rust
+struct S { x: D, y: D, z: D }
+
+fn foo(a: S, mut b: S, t: || -> bool) {
+    let mut c: S;
+    let d: S;
+    let e: S = a.clone();
+    if t() {
+        c = b;
+        b.x = e.y;
+    }
+    if t() { c.y = D::new(4); }
+}
+```
+
+As before, the drop obligations of `a` and `d` can be statically
+determined, and again the state of `b` and `c` depend on dynamic
+state. But additionally, the dynamic drop obligations introduced by
+`b` and `c` are not just per-local boolean flags. For example, if the
+first call to `t` returns `false` and the second call `true`, then at
+the end of their scope, `b` will be completely initialized, but only
+`c.y` in `c` will be initialized.  If both calls to `t` return `true`,
+then at the end of their scope, `c` will be completely initialized,
+but only `b.x` will be initialized in `b`, and only `e.x` and `e.z`
+will be initialized in `e`.
+
+Note that we need to cover the `z` field in each case in some way,
+since it may (or may not) need to be dropped, even though `z` is never
+directly mentioned in the body of the `foo` function. We call a path
+like `b.z` a *fragment sibling* of `b.x`, since the field `z` comes
+from the same structure `S` that declared the field `x` in `b.x`.
+
+In general we need to maintain boolean flags that match the
+`S`-structure of both `b` and `c`.  In addition, we need to consult
+such a flag when doing an assignment (such as `c.y = D::new(4);`
+above), in order to know whether or not there is a previous value that
+needs to be dropped before we do the assignment.
+
+So for any given function, we need to determine what flags are needed
+to track its drop obligations. Our strategy for determining the set of
+flags is to represent the fragmentation of the structure explicitly:
+by starting initially from the paths that are explicitly mentioned in
+moves and assignments (such as `b.x` and `c.y` above), and then
+traversing the structure of the path's type to identify leftover
+*unmoved fragments*: assigning into `c.y` means that `c.x` and `c.z`
+are leftover unmoved fragments. Each fragment represents a drop
+obligation that may need to be tracked. Paths that are only moved or
+assigned in their entirety (like `a` and `d`) are treated as a single
+drop obligation.
+
+The fragment construction process works by piggy-backing on the
+existing `move_data` module. We already have callbacks that visit each
+direct move and assignment; these form the basis for the sets of
+moved_leaf_paths and assigned_leaf_paths. From these leaves, we can
+walk up their parent chain to identify all of their parent paths.
+We need to identify the parents because of cases like the following:
+
+```rust
+struct Pair<X,Y>{ x: X, y: Y }
+fn foo(dd_d_d: Pair<Pair<Pair<D, D>, D>, D>) {
+    other_function(dd_d_d.x.y);
+}
+```
+
+In this code, the move of the path `dd_d.x.y` leaves behind not only
+the fragment drop-obligation `dd_d.x.x` but also `dd_d.y` as well.
+
+Once we have identified the directly-referenced leaves and their
+parents, we compute the left-over fragments, in the function
+`fragments::add_fragment_siblings`. As of this writing this works by
+looking at each directly-moved or assigned path P, and blindly
+gathering all sibling fields of P (as well as siblings for the parents
+of P, etc). After accumulating all such siblings, we filter out the
+entries added as siblings of P that turned out to be
+directly-referenced paths (or parents of directly referenced paths)
+themselves, thus leaving the never-referenced "left-overs" as the only
+thing left from the gathering step.
+
+## Array structural fragments
+
+A special case of the structural fragments discussed above are
+the elements of an array that has been passed by value, such as
+the following:
+
+```rust
+fn foo(a: [D, ..10], i: uint) -> D {
+    a[i]
+}
+```
+
+The above code moves a single element out of the input array `a`.
+The remainder of the array still needs to be dropped; i.e., it
+is a structural fragment. Note that after performing such a move,
+it is not legal to read from the array `a`. There are a number of
+ways to deal with this, but the important thing to note is that
+the semantics needs to distinguish in some manner between a
+fragment that is the *entire* array versus a fragment that represents
+all-but-one element of the array.  A place where that distinction
+would arise is the following:
+
+```rust
+fn foo(a: [D, ..10], b: [D, ..10], i: uint, t: bool) -> D {
+    if t {
+        a[i]
+    } else {
+        b[i]
+    }
+
+    // When control exits, we will need either to drop all of `a`
+    // and all-but-one of `b`, or to drop all of `b` and all-but-one
+    // of `a`.
+}
+```
+
+There are a number of ways that the trans backend could choose to
+compile this (e.g. a `[bool, ..10]` array for each such moved array;
+or an `Option<uint>` for each moved array).  From the viewpoint of the
+borrow-checker, the important thing is to record what kind of fragment
+is implied by the relevant moves.
+
 # Future work
 
 While writing up these docs, I encountered some rules I believe to be
diff --git a/src/librustc/middle/borrowck/fragments.rs b/src/librustc/middle/borrowck/fragments.rs
new file mode 100644
index 00000000000..7e766e9138e
--- /dev/null
+++ b/src/librustc/middle/borrowck/fragments.rs
@@ -0,0 +1,491 @@
+// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+/*!
+
+Helper routines used for fragmenting structural paths due to moves for
+tracking drop obligations. Please see the extensive comments in the
+section "Structural fragments" in `doc.rs`.
+
+*/
+use self::Fragment::*;
+
+use session::config;
+use middle::borrowck::{LoanPath};
+use middle::borrowck::LoanPathKind::{LpVar, LpUpvar, LpDowncast, LpExtend};
+use middle::borrowck::LoanPathElem::{LpDeref, LpInterior};
+use middle::borrowck::move_data::{InvalidMovePathIndex};
+use middle::borrowck::move_data::{MoveData, MovePathIndex};
+use middle::ty;
+use middle::mem_categorization as mc;
+use util::ppaux::{Repr, UserString};
+
+use std::mem;
+use std::rc::Rc;
+use std::slice;
+use syntax::ast;
+use syntax::ast_map;
+use syntax::attr::AttrMetaMethods;
+use syntax::codemap::Span;
+
+#[deriving(PartialEq, Eq, PartialOrd, Ord)]
+enum Fragment {
+    // This represents the path described by the move path index
+    Just(MovePathIndex),
+
+    // This represents the collection of all but one of the elements
+    // from an array at the path described by the move path index.
+    // Note that attached MovePathIndex should have mem_categorization
+    // of InteriorElement (i.e. array dereference `[]`).
+    AllButOneFrom(MovePathIndex),
+}
+
+impl Fragment {
+    fn loan_path_repr<'tcx>(&self, move_data: &MoveData<'tcx>, tcx: &ty::ctxt<'tcx>) -> String {
+        let repr = |mpi| move_data.path_loan_path(mpi).repr(tcx);
+        match *self {
+            Just(mpi) => repr(mpi),
+            AllButOneFrom(mpi) => format!("$(allbutone {})", repr(mpi)),
+        }
+    }
+
+    fn loan_path_user_string<'tcx>(&self,
+                                   move_data: &MoveData<'tcx>,
+                                   tcx: &ty::ctxt<'tcx>) -> String {
+        let user_string = |mpi| move_data.path_loan_path(mpi).user_string(tcx);
+        match *self {
+            Just(mpi) => user_string(mpi),
+            AllButOneFrom(mpi) => format!("$(allbutone {})", user_string(mpi)),
+        }
+    }
+}
+
+pub struct FragmentSets {
+    /// During move_data construction, `moved_leaf_paths` tracks paths
+    /// that have been used directly by being moved out of.  When
+    /// move_data construction has been completed, `moved_leaf_paths`
+    /// tracks such paths that are *leaf fragments* (e.g. `a.j` if we
+    /// never move out any child like `a.j.x`); any parent paths
+    /// (e.g. `a` for the `a.j` example) are moved over to
+    /// `parents_of_fragments`.
+    moved_leaf_paths: Vec<MovePathIndex>,
+
+    /// `assigned_leaf_paths` tracks paths that have been used
+    /// directly by being overwritten, but is otherwise much like
+    /// `moved_leaf_paths`.
+    assigned_leaf_paths: Vec<MovePathIndex>,
+
+    /// `parents_of_fragments` tracks paths that are definitely
+    /// parents of paths that have been moved.
+    ///
+    /// FIXME(pnkfelix) probably do not want/need
+    /// `parents_of_fragments` at all, if we can avoid it.
+    ///
+    /// Update: I do not see a way to to avoid it.  Maybe just remove
+    /// above fixme, or at least document why doing this may be hard.
+    parents_of_fragments: Vec<MovePathIndex>,
+
+    /// During move_data construction (specifically the
+    /// fixup_fragment_sets call), `unmoved_fragments` tracks paths
+    /// that have been "left behind" after a sibling has been moved or
+    /// assigned.  When move_data construction has been completed,
+    /// `unmoved_fragments` tracks paths that were *only* results of
+    /// being left-behind, and never directly moved themselves.
+    unmoved_fragments: Vec<Fragment>,
+}
+
+impl FragmentSets {
+    pub fn new() -> FragmentSets {
+        FragmentSets {
+            unmoved_fragments: Vec::new(),
+            moved_leaf_paths: Vec::new(),
+            assigned_leaf_paths: Vec::new(),
+            parents_of_fragments: Vec::new(),
+        }
+    }
+
+    pub fn add_move(&mut self, path_index: MovePathIndex) {
+        self.moved_leaf_paths.push(path_index);
+    }
+
+    pub fn add_assignment(&mut self, path_index: MovePathIndex) {
+        self.assigned_leaf_paths.push(path_index);
+    }
+}
+
+pub fn instrument_move_fragments<'tcx>(this: &MoveData<'tcx>,
+                                       tcx: &ty::ctxt<'tcx>,
+                                       sp: Span,
+                                       id: ast::NodeId) {
+    let (span_err, print) = {
+        let attrs : &[ast::Attribute];
+        attrs = match tcx.map.find(id) {
+            Some(ast_map::NodeItem(ref item)) =>
+                item.attrs.as_slice(),
+            Some(ast_map::NodeImplItem(&ast::MethodImplItem(ref m))) =>
+                m.attrs.as_slice(),
+            Some(ast_map::NodeTraitItem(&ast::ProvidedMethod(ref m))) =>
+                m.attrs.as_slice(),
+            _ => [].as_slice(),
+        };
+
+        let span_err =
+            attrs.iter().any(|a| a.check_name("rustc_move_fragments"));
+        let print = tcx.sess.debugging_opt(config::PRINT_MOVE_FRAGMENTS);
+
+        (span_err, print)
+    };
+
+    if !span_err && !print { return; }
+
+    let instrument_all_paths = |kind, vec_rc: &Vec<MovePathIndex>| {
+        for (i, mpi) in vec_rc.iter().enumerate() {
+            let render = || this.path_loan_path(*mpi).user_string(tcx);
+            if span_err {
+                tcx.sess.span_err(sp, format!("{}: `{}`", kind, render()).as_slice());
+            }
+            if print {
+                println!("id:{} {}[{}] `{}`", id, kind, i, render());
+            }
+        }
+    };
+
+    let instrument_all_fragments = |kind, vec_rc: &Vec<Fragment>| {
+        for (i, f) in vec_rc.iter().enumerate() {
+            let render = || f.loan_path_user_string(this, tcx);
+            if span_err {
+                tcx.sess.span_err(sp, format!("{}: `{}`", kind, render()).as_slice());
+            }
+            if print {
+                println!("id:{} {}[{}] `{}`", id, kind, i, render());
+            }
+        }
+    };
+
+    let fragments = this.fragments.borrow();
+    instrument_all_paths("moved_leaf_path", &fragments.moved_leaf_paths);
+    instrument_all_fragments("unmoved_fragment", &fragments.unmoved_fragments);
+    instrument_all_paths("parent_of_fragments", &fragments.parents_of_fragments);
+    instrument_all_paths("assigned_leaf_path", &fragments.assigned_leaf_paths);
+}
+
+pub fn fixup_fragment_sets<'tcx>(this: &MoveData<'tcx>, tcx: &ty::ctxt<'tcx>) {
+    /*!
+     * Normalizes the fragment sets in `this`; i.e., removes
+     * duplicate entries, constructs the set of parents, and
+     * constructs the left-over fragments.
+     *
+     * Note: "left-over fragments" means paths that were not
+     * directly referenced in moves nor assignments, but must
+     * nonetheless be tracked as potential drop obligations.
+     */
+
+    let mut fragments = this.fragments.borrow_mut();
+
+    // Swap out contents of fragments so that we can modify the fields
+    // without borrowing the common fragments.
+    let mut unmoved = mem::replace(&mut fragments.unmoved_fragments, vec![]);
+    let mut parents = mem::replace(&mut fragments.parents_of_fragments, vec![]);
+    let mut moved = mem::replace(&mut fragments.moved_leaf_paths, vec![]);
+    let mut assigned = mem::replace(&mut fragments.assigned_leaf_paths, vec![]);
+
+    let path_lps = |mpis: &[MovePathIndex]| -> Vec<String> {
+        mpis.iter().map(|mpi| this.path_loan_path(*mpi).repr(tcx)).collect()
+    };
+
+    let frag_lps = |fs: &[Fragment]| -> Vec<String> {
+        fs.iter().map(|f| f.loan_path_repr(this, tcx)).collect()
+    };
+
+    // First, filter out duplicates
+    moved.sort();
+    moved.dedup();
+    debug!("fragments 1 moved: {}", path_lps(moved.as_slice()));
+
+    assigned.sort();
+    assigned.dedup();
+    debug!("fragments 1 assigned: {}", path_lps(assigned.as_slice()));
+
+    // Second, build parents from the moved and assigned.
+    for m in moved.iter() {
+        let mut p = this.path_parent(*m);
+        while p != InvalidMovePathIndex {
+            parents.push(p);
+            p = this.path_parent(p);
+        }
+    }
+    for a in assigned.iter() {
+        let mut p = this.path_parent(*a);
+        while p != InvalidMovePathIndex {
+            parents.push(p);
+            p = this.path_parent(p);
+        }
+    }
+
+    parents.sort();
+    parents.dedup();
+    debug!("fragments 2 parents: {}", path_lps(parents.as_slice()));
+
+    // Third, filter the moved and assigned fragments down to just the non-parents
+    moved.retain(|f| non_member(*f, parents.as_slice()));
+    debug!("fragments 3 moved: {}", path_lps(moved.as_slice()));
+
+    assigned.retain(|f| non_member(*f, parents.as_slice()));
+    debug!("fragments 3 assigned: {}", path_lps(assigned.as_slice()));
+
+    // Fourth, build the leftover from the moved, assigned, and parents.
+    for m in moved.as_slice().iter() {
+        let lp = this.path_loan_path(*m);
+        add_fragment_siblings(this, tcx, &mut unmoved, lp, None);
+    }
+    for a in assigned.as_slice().iter() {
+        let lp = this.path_loan_path(*a);
+        add_fragment_siblings(this, tcx, &mut unmoved, lp, None);
+    }
+    for p in parents.as_slice().iter() {
+        let lp = this.path_loan_path(*p);
+        add_fragment_siblings(this, tcx, &mut unmoved, lp, None);
+    }
+
+    unmoved.sort();
+    unmoved.dedup();
+    debug!("fragments 4 unmoved: {}", frag_lps(unmoved.as_slice()));
+
+    // Fifth, filter the leftover fragments down to its core.
+    unmoved.retain(|f| match *f {
+        AllButOneFrom(_) => true,
+        Just(mpi) => non_member(mpi, parents.as_slice()) &&
+            non_member(mpi, moved.as_slice()) &&
+            non_member(mpi, assigned.as_slice())
+    });
+    debug!("fragments 5 unmoved: {}", frag_lps(unmoved.as_slice()));
+
+    // Swap contents back in.
+    fragments.unmoved_fragments = unmoved;
+    fragments.parents_of_fragments = parents;
+    fragments.moved_leaf_paths = moved;
+    fragments.assigned_leaf_paths = assigned;
+
+    return;
+
+    fn non_member(elem: MovePathIndex, set: &[MovePathIndex]) -> bool {
+        match set.binary_search_elem(&elem) {
+            slice::Found(_) => false,
+            slice::NotFound(_) => true,
+        }
+    }
+}
+
+fn add_fragment_siblings<'tcx>(this: &MoveData<'tcx>,
+                               tcx: &ty::ctxt<'tcx>,
+                               gathered_fragments: &mut Vec<Fragment>,
+                               lp: Rc<LoanPath<'tcx>>,
+                               origin_id: Option<ast::NodeId>) {
+    /*!
+     * Adds all of the precisely-tracked siblings of `lp` as
+     * potential move paths of interest. For example, if `lp`
+     * represents `s.x.j`, then adds moves paths for `s.x.i` and
+     * `s.x.k`, the siblings of `s.x.j`.
+     */
+
+    match lp.kind {
+        LpVar(_) | LpUpvar(..) => {} // Local variables have no siblings.
+
+        // Consuming a downcast is like consuming the original value, so propage inward.
+        LpDowncast(ref loan_parent, _) => {
+            add_fragment_siblings(this, tcx, gathered_fragments, loan_parent.clone(), origin_id);
+        }
+
+        // *LV for OwnedPtr consumes the contents of the box (at
+        // least when it is non-copy...), so propagate inward.
+        LpExtend(ref loan_parent, _, LpDeref(mc::OwnedPtr)) => {
+            add_fragment_siblings(this, tcx, gathered_fragments, loan_parent.clone(), origin_id);
+        }
+
+        // *LV for unsafe and borrowed pointers do not consume their loan path, so stop here.
+        LpExtend(_, _, LpDeref(mc::UnsafePtr(..)))   |
+        LpExtend(_, _, LpDeref(mc::Implicit(..)))    |
+        LpExtend(_, _, LpDeref(mc::BorrowedPtr(..))) => {}
+
+        // FIXME(pnkfelix): LV[j] should be tracked, at least in the
+        // sense of we will track the remaining drop obligation of the
+        // rest of the array.
+        //
+        // LV[j] is not tracked precisely
+        LpExtend(_, _, LpInterior(mc::InteriorElement(_))) => {
+            let mp = this.move_path(tcx, lp.clone());
+            gathered_fragments.push(AllButOneFrom(mp));
+        }
+
+        // field access LV.x and tuple access LV#k are the cases
+        // we are interested in
+        LpExtend(ref loan_parent, mc,
+                 LpInterior(mc::InteriorField(ref field_name))) => {
+            let enum_variant_info = match loan_parent.kind {
+                LpDowncast(ref loan_parent_2, variant_def_id) =>
+                    Some((variant_def_id, loan_parent_2.clone())),
+                LpExtend(..) | LpVar(..) | LpUpvar(..) =>
+                    None,
+            };
+            add_fragment_siblings_for_extension(
+                this,
+                tcx,
+                gathered_fragments,
+                loan_parent, mc, field_name, &lp, origin_id, enum_variant_info);
+        }
+    }
+}
+
+fn add_fragment_siblings_for_extension<'tcx>(this: &MoveData<'tcx>,
+                                             tcx: &ty::ctxt<'tcx>,
+                                             gathered_fragments: &mut Vec<Fragment>,
+                                             parent_lp: &Rc<LoanPath<'tcx>>,
+                                             mc: mc::MutabilityCategory,
+                                             origin_field_name: &mc::FieldName,
+                                             origin_lp: &Rc<LoanPath<'tcx>>,
+                                             origin_id: Option<ast::NodeId>,
+                                             enum_variant_info: Option<(ast::DefId,
+                                                                        Rc<LoanPath<'tcx>>)>) {
+    /*!
+     * We have determined that `origin_lp` destructures to
+     * LpExtend(parent, original_field_name). Based on this,
+     * add move paths for all of the siblings of `origin_lp`.
+     */
+
+    let parent_ty = parent_lp.to_type();
+
+    let add_fragment_sibling_local = |field_name| {
+        add_fragment_sibling_core(
+            this, tcx, gathered_fragments, parent_lp.clone(), mc, field_name, origin_lp);
+    };
+
+    match (&parent_ty.sty, enum_variant_info) {
+        (&ty::ty_tup(ref v), None) => {
+            let tuple_idx = match *origin_field_name {
+                mc::PositionalField(tuple_idx) => tuple_idx,
+                mc::NamedField(_) =>
+                    panic!("tuple type {} should not have named fields.",
+                           parent_ty.repr(tcx)),
+            };
+            let tuple_len = v.len();
+            for i in range(0, tuple_len) {
+                if i == tuple_idx { continue }
+                let field_name = mc::PositionalField(i);
+                add_fragment_sibling_local(field_name);
+            }
+        }
+
+        (&ty::ty_struct(def_id, ref _substs), None) => {
+            let fields = ty::lookup_struct_fields(tcx, def_id);
+            match *origin_field_name {
+                mc::NamedField(ast_name) => {
+                    for f in fields.iter() {
+                        if f.name == ast_name {
+                            continue;
+                        }
+                        let field_name = mc::NamedField(f.name);
+                        add_fragment_sibling_local(field_name);
+                    }
+                }
+                mc::PositionalField(tuple_idx) => {
+                    for (i, _f) in fields.iter().enumerate() {
+                        if i == tuple_idx {
+                            continue
+                        }
+                        let field_name = mc::PositionalField(i);
+                        add_fragment_sibling_local(field_name);
+                    }
+                }
+            }
+        }
+
+        (&ty::ty_enum(enum_def_id, ref substs), ref enum_variant_info) => {
+            let variant_info = {
+                let mut variants = ty::substd_enum_variants(tcx, enum_def_id, substs);
+                match *enum_variant_info {
+                    Some((variant_def_id, ref _lp2)) =>
+                        variants.iter()
+                        .find(|variant| variant.id == variant_def_id)
+                        .expect("enum_variant_with_id(): no variant exists with that ID")
+                        .clone(),
+                    None => {
+                        assert_eq!(variants.len(), 1);
+                        variants.pop().unwrap()
+                    }
+                }
+            };
+            match *origin_field_name {
+                mc::NamedField(ast_name) => {
+                    let variant_arg_names = variant_info.arg_names.as_ref().unwrap();
+                    for variant_arg_ident in variant_arg_names.iter() {
+                        if variant_arg_ident.name == ast_name {
+                            continue;
+                        }
+                        let field_name = mc::NamedField(variant_arg_ident.name);
+                        add_fragment_sibling_local(field_name);
+                    }
+                }
+                mc::PositionalField(tuple_idx) => {
+                    let variant_arg_types = &variant_info.args;
+                    for (i, _variant_arg_ty) in variant_arg_types.iter().enumerate() {
+                        if tuple_idx == i {
+                            continue;
+                        }
+                        let field_name = mc::PositionalField(i);
+                        add_fragment_sibling_local(field_name);
+                    }
+                }
+            }
+        }
+
+        ref sty_and_variant_info => {
+            let msg = format!("type {} ({}) is not fragmentable",
+                              parent_ty.repr(tcx), sty_and_variant_info);
+            let opt_span = origin_id.and_then(|id|tcx.map.opt_span(id));
+            tcx.sess.opt_span_bug(opt_span, msg.as_slice())
+        }
+    }
+}
+
+fn add_fragment_sibling_core<'tcx>(this: &MoveData<'tcx>,
+                                   tcx: &ty::ctxt<'tcx>,
+                                   gathered_fragments: &mut Vec<Fragment>,
+                                   parent: Rc<LoanPath<'tcx>>,
+                                   mc: mc::MutabilityCategory,
+                                   new_field_name: mc::FieldName,
+                                   origin_lp: &Rc<LoanPath<'tcx>>) -> MovePathIndex {
+    /*!
+     * Adds the single sibling `LpExtend(parent, new_field_name)`
+     * of `origin_lp` (the original loan-path).
+     */
+    let opt_variant_did = match parent.kind {
+        LpDowncast(_, variant_did) => Some(variant_did),
+        LpVar(..) | LpUpvar(..) | LpExtend(..) => None,
+    };
+
+    let loan_path_elem = LpInterior(mc::InteriorField(new_field_name));
+    let new_lp_type = match new_field_name {
+        mc::NamedField(ast_name) =>
+            ty::named_element_ty(tcx, parent.to_type(), ast_name, opt_variant_did),
+        mc::PositionalField(idx) =>
+            ty::positional_element_ty(tcx, parent.to_type(), idx, opt_variant_did),
+    };
+    let new_lp_variant = LpExtend(parent, mc, loan_path_elem);
+    let new_lp = LoanPath::new(new_lp_variant, new_lp_type.unwrap());
+    debug!("add_fragment_sibling_core(new_lp={}, origin_lp={})",
+           new_lp.repr(tcx), origin_lp.repr(tcx));
+    let mp = this.move_path(tcx, Rc::new(new_lp));
+
+    // Do not worry about checking for duplicates here; we will sort
+    // and dedup after all are added.
+    gathered_fragments.push(Just(mp));
+
+    mp
+}
diff --git a/src/librustc/middle/borrowck/gather_loans/gather_moves.rs b/src/librustc/middle/borrowck/gather_loans/gather_moves.rs
index 5aeeb3566fd..1d0b0558bb1 100644
--- a/src/librustc/middle/borrowck/gather_loans/gather_moves.rs
+++ b/src/librustc/middle/borrowck/gather_loans/gather_moves.rs
@@ -62,6 +62,37 @@ pub fn gather_move_from_expr<'a, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
     gather_move(bccx, move_data, move_error_collector, move_info);
 }
 
+pub fn gather_match_variant<'a, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
+                                      move_data: &MoveData<'tcx>,
+                                      _move_error_collector: &MoveErrorCollector<'tcx>,
+                                      move_pat: &ast::Pat,
+                                      cmt: mc::cmt<'tcx>,
+                                      mode: euv::MatchMode) {
+    let tcx = bccx.tcx;
+    debug!("gather_match_variant(move_pat={}, cmt={}, mode={})",
+           move_pat.id, cmt.repr(tcx), mode);
+
+    let opt_lp = opt_loan_path(&cmt);
+    match opt_lp {
+        Some(lp) => {
+            match lp.kind {
+                LpDowncast(ref base_lp, _) =>
+                    move_data.add_variant_match(
+                        tcx, lp.clone(), move_pat.id, base_lp.clone(), mode),
+                _ => panic!("should only call gather_match_variant \
+                             for cat_downcast cmt"),
+            }
+        }
+        None => {
+            // We get None when input to match is non-path (e.g.
+            // temporary result like a function call). Since no
+            // loan-path is being matched, no need to record a
+            // downcast.
+            return;
+        }
+    }
+}
+
 pub fn gather_move_from_pat<'a, 'tcx>(bccx: &BorrowckCtxt<'a, 'tcx>,
                                       move_data: &MoveData<'tcx>,
                                       move_error_collector: &MoveErrorCollector<'tcx>,
diff --git a/src/librustc/middle/borrowck/gather_loans/mod.rs b/src/librustc/middle/borrowck/gather_loans/mod.rs
index 6950c117179..088b62a12cf 100644
--- a/src/librustc/middle/borrowck/gather_loans/mod.rs
+++ b/src/librustc/middle/borrowck/gather_loans/mod.rs
@@ -96,6 +96,14 @@ impl<'a, 'tcx> euv::Delegate<'tcx> for GatherLoanCtxt<'a, 'tcx> {
                matched_pat.repr(self.tcx()),
                cmt.repr(self.tcx()),
                mode);
+
+        match cmt.cat {
+            mc::cat_downcast(..) =>
+                gather_moves::gather_match_variant(
+                    self.bccx, &self.move_data, &self.move_error_collector,
+                    matched_pat, cmt, mode),
+            _ => {}
+        }
     }
 
     fn consume_pat(&mut self,
diff --git a/src/librustc/middle/borrowck/mod.rs b/src/librustc/middle/borrowck/mod.rs
index 62ea02540e1..45040cd7b10 100644
--- a/src/librustc/middle/borrowck/mod.rs
+++ b/src/librustc/middle/borrowck/mod.rs
@@ -143,6 +143,9 @@ fn borrowck_fn(this: &mut BorrowckCtxt,
                        move_data:flowed_moves } =
         build_borrowck_dataflow_data(this, fk, decl, &cfg, body, sp, id);
 
+    move_data::fragments::instrument_move_fragments(&flowed_moves.move_data,
+                                                    this.tcx, sp, id);
+
     check_loans::check_loans(this, &loan_dfcx, flowed_moves,
                              all_loans.as_slice(), decl, body);
 
@@ -322,8 +325,14 @@ impl<'tcx> LoanPath<'tcx> {
         LoanPath { kind: kind, ty: ty }
     }
 
+    fn to_type(&self) -> ty::Ty<'tcx> { self.ty }
 }
 
+// FIXME (pnkfelix): See discussion here
+// https://github.com/pnkfelix/rust/commit/
+//     b2b39e8700e37ad32b486b9a8409b50a8a53aa51#commitcomment-7892003
+static DOWNCAST_PRINTED_OPERATOR : &'static str = " as ";
+
 #[deriving(PartialEq, Eq, Hash, Show)]
 pub enum LoanPathElem {
     LpDeref(mc::PointerKind),    // `*LV` in doc.rs
@@ -927,7 +936,7 @@ impl<'a, 'tcx> BorrowckCtxt<'a, 'tcx> {
             LpDowncast(ref lp_base, variant_def_id) => {
                 out.push('(');
                 self.append_loan_path_to_string(&**lp_base, out);
-                out.push_str("->");
+                out.push_str(DOWNCAST_PRINTED_OPERATOR);
                 out.push_str(ty::item_path_str(self.tcx, variant_def_id).as_slice());
                 out.push(')');
             }
@@ -1051,7 +1060,7 @@ impl<'tcx> Repr<'tcx> for LoanPath<'tcx> {
                 } else {
                     variant_def_id.repr(tcx)
                 };
-                format!("({}->{})", lp.repr(tcx), variant_str)
+                format!("({}{}{})", lp.repr(tcx), DOWNCAST_PRINTED_OPERATOR, variant_str)
             }
 
             LpExtend(ref lp, _, LpDeref(_)) => {
@@ -1064,3 +1073,35 @@ impl<'tcx> Repr<'tcx> for LoanPath<'tcx> {
         }
     }
 }
+
+impl<'tcx> UserString<'tcx> for LoanPath<'tcx> {
+    fn user_string(&self, tcx: &ty::ctxt<'tcx>) -> String {
+        match self.kind {
+            LpVar(id) => {
+                format!("$({})", tcx.map.node_to_user_string(id))
+            }
+
+            LpUpvar(ty::UpvarId{ var_id, closure_expr_id: _ }) => {
+                let s = tcx.map.node_to_user_string(var_id);
+                format!("$({} captured by closure)", s)
+            }
+
+            LpDowncast(ref lp, variant_def_id) => {
+                let variant_str = if variant_def_id.krate == ast::LOCAL_CRATE {
+                    ty::item_path_str(tcx, variant_def_id)
+                } else {
+                    variant_def_id.repr(tcx)
+                };
+                format!("({}{}{})", lp.user_string(tcx), DOWNCAST_PRINTED_OPERATOR, variant_str)
+            }
+
+            LpExtend(ref lp, _, LpDeref(_)) => {
+                format!("{}.*", lp.user_string(tcx))
+            }
+
+            LpExtend(ref lp, _, LpInterior(ref interior)) => {
+                format!("{}.{}", lp.user_string(tcx), interior.repr(tcx))
+            }
+        }
+    }
+}
diff --git a/src/librustc/middle/borrowck/move_data.rs b/src/librustc/middle/borrowck/move_data.rs
index 53e5d36836e..dc9516ccc5d 100644
--- a/src/librustc/middle/borrowck/move_data.rs
+++ b/src/librustc/middle/borrowck/move_data.rs
@@ -11,7 +11,7 @@
 /*!
 
 Data structures used for tracking moves. Please see the extensive
-comments in the section "Moves and initialization" and in `doc.rs`.
+comments in the section "Moves and initialization" in `doc.rs`.
 
 */
 
@@ -36,6 +36,9 @@ use syntax::codemap::Span;
 use util::nodemap::{FnvHashMap, NodeSet};
 use util::ppaux::Repr;
 
+#[path="fragments.rs"]
+pub mod fragments;
+
 pub struct MoveData<'tcx> {
     /// Move paths. See section "Move paths" in `doc.rs`.
     pub paths: RefCell<Vec<MovePath<'tcx>>>,
@@ -56,8 +59,15 @@ pub struct MoveData<'tcx> {
     /// kill move bits.
     pub path_assignments: RefCell<Vec<Assignment>>,
 
+    /// Enum variant matched within a pattern on some match arm, like
+    /// `SomeStruct{ f: Variant1(x, y) } => ...`
+    pub variant_matches: RefCell<Vec<VariantMatch>>,
+
     /// Assignments to a variable or path, like `x = foo`, but not `x += foo`.
     pub assignee_ids: RefCell<NodeSet>,
+
+    /// Path-fragments from moves in to or out of parts of structured data.
+    pub fragments: RefCell<fragments::FragmentSets>,
 }
 
 pub struct FlowedMoveData<'a, 'tcx: 'a> {
@@ -72,7 +82,7 @@ pub struct FlowedMoveData<'a, 'tcx: 'a> {
 }
 
 /// Index into `MoveData.paths`, used like a pointer
-#[deriving(PartialEq, Show)]
+#[deriving(PartialEq, Eq, PartialOrd, Ord, Show)]
 pub struct MovePathIndex(uint);
 
 impl MovePathIndex {
@@ -157,6 +167,20 @@ pub struct Assignment {
     pub span: Span,
 }
 
+pub struct VariantMatch {
+    /// downcast to the variant.
+    pub path: MovePathIndex,
+
+    /// path being downcast to the variant.
+    pub base_path: MovePathIndex,
+
+    /// id where variant's pattern occurs
+    pub id: ast::NodeId,
+
+    /// says if variant established by move (and why), by copy, or by borrow.
+    pub mode: euv::MatchMode
+}
+
 #[deriving(Clone)]
 pub struct MoveDataFlowOperator;
 
@@ -184,6 +208,37 @@ fn loan_path_is_precise(loan_path: &LoanPath) -> bool {
     }
 }
 
+impl Move {
+    pub fn to_string<'tcx>(&self, move_data: &MoveData<'tcx>, tcx: &ty::ctxt<'tcx>) -> String {
+        format!("Move{} path: {}, id: {}, kind: {} {}",
+                "{",
+                move_data.path_loan_path(self.path).repr(tcx),
+                self.id,
+                self.kind,
+                "}")
+    }
+}
+
+impl Assignment {
+    pub fn to_string<'tcx>(&self, move_data: &MoveData<'tcx>, tcx: &ty::ctxt<'tcx>) -> String {
+        format!("Assignment{} path: {}, id: {} {}",
+                "{",
+                move_data.path_loan_path(self.path).repr(tcx),
+                self.id,
+                "}")
+    }
+}
+
+impl VariantMatch {
+    pub fn to_string<'tcx>(&self, move_data: &MoveData<'tcx>, tcx: &ty::ctxt<'tcx>) -> String {
+        format!("VariantMatch{} path: {}, id: {} {}",
+                "{",
+                move_data.path_loan_path(self.path).repr(tcx),
+                self.id,
+                "}")
+    }
+}
+
 impl<'tcx> MoveData<'tcx> {
     pub fn new() -> MoveData<'tcx> {
         MoveData {
@@ -192,7 +247,9 @@ impl<'tcx> MoveData<'tcx> {
             moves: RefCell::new(Vec::new()),
             path_assignments: RefCell::new(Vec::new()),
             var_assignments: RefCell::new(Vec::new()),
+            variant_matches: RefCell::new(Vec::new()),
             assignee_ids: RefCell::new(NodeSet::new()),
+            fragments: RefCell::new(fragments::FragmentSets::new()),
         }
     }
 
@@ -208,6 +265,8 @@ impl<'tcx> MoveData<'tcx> {
         (*self.paths.borrow())[index.get()].first_move
     }
 
+    /// Returns the index of first child, or `InvalidMovePathIndex` if
+    /// `index` is leaf.
     fn path_first_child(&self, index: MovePathIndex) -> MovePathIndex {
         (*self.paths.borrow())[index.get()].first_child
     }
@@ -353,9 +412,11 @@ impl<'tcx> MoveData<'tcx> {
                id,
                kind);
 
-        let path_index = self.move_path(tcx, lp);
+        let path_index = self.move_path(tcx, lp.clone());
         let move_index = MoveIndex(self.moves.borrow().len());
 
+        self.fragments.borrow_mut().add_move(path_index);
+
         let next_move = self.path_first_move(path_index);
         self.set_path_first_move(path_index, move_index);
 
@@ -384,6 +445,8 @@ impl<'tcx> MoveData<'tcx> {
 
         let path_index = self.move_path(tcx, lp.clone());
 
+        self.fragments.borrow_mut().add_assignment(path_index);
+
         match mode {
             euv::Init | euv::JustWrite => {
                 self.assignee_ids.borrow_mut().insert(assignee_id);
@@ -410,6 +473,40 @@ impl<'tcx> MoveData<'tcx> {
         }
     }
 
+    pub fn add_variant_match(&self,
+                             tcx: &ty::ctxt<'tcx>,
+                             lp: Rc<LoanPath<'tcx>>,
+                             pattern_id: ast::NodeId,
+                             base_lp: Rc<LoanPath<'tcx>>,
+                             mode: euv::MatchMode) {
+        /*!
+         * Adds a new record for a match of `base_lp`, downcast to
+         * variant `lp`, that occurs at location `pattern_id`.  (One
+         * should be able to recover the span info from the
+         * `pattern_id` and the ast_map, I think.)
+         */
+        debug!("add_variant_match(lp={}, pattern_id={})",
+               lp.repr(tcx), pattern_id);
+
+        let path_index = self.move_path(tcx, lp.clone());
+        let base_path_index = self.move_path(tcx, base_lp.clone());
+
+        self.fragments.borrow_mut().add_assignment(path_index);
+
+        let variant_match = VariantMatch {
+            path: path_index,
+            base_path: base_path_index,
+            id: pattern_id,
+            mode: mode,
+        };
+
+        self.variant_matches.borrow_mut().push(variant_match);
+    }
+
+    fn fixup_fragment_sets(&self, tcx: &ty::ctxt<'tcx>) {
+        fragments::fixup_fragment_sets(self, tcx)
+    }
+
     fn add_gen_kills(&self,
                      tcx: &ty::ctxt<'tcx>,
                      dfcx_moves: &mut MoveDataFlow,
@@ -435,8 +532,8 @@ impl<'tcx> MoveData<'tcx> {
             self.kill_moves(assignment.path, assignment.id, dfcx_moves);
         }
 
-        // Kill all moves related to a variable `x` when it goes out
-        // of scope:
+        // Kill all moves related to a variable `x` when
+        // it goes out of scope:
         for path in self.paths.borrow().iter() {
             match path.loan_path.kind {
                 LpVar(..) | LpUpvar(..) | LpDowncast(..) => {
@@ -556,9 +653,16 @@ impl<'a, 'tcx> FlowedMoveData<'a, 'tcx> {
                                  AssignDataFlowOperator,
                                  id_range,
                                  move_data.var_assignments.borrow().len());
-        move_data.add_gen_kills(tcx, &mut dfcx_moves, &mut dfcx_assign);
+
+        move_data.fixup_fragment_sets(tcx);
+
+        move_data.add_gen_kills(tcx,
+                                &mut dfcx_moves,
+                                &mut dfcx_assign);
+
         dfcx_moves.add_kills_from_flow_exits(cfg);
         dfcx_assign.add_kills_from_flow_exits(cfg);
+
         dfcx_moves.propagate(cfg, body);
         dfcx_assign.propagate(cfg, body);
 
diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs
index 47b296e46cd..98b958749d5 100644
--- a/src/librustc/middle/ty.rs
+++ b/src/librustc/middle/ty.rs
@@ -3442,6 +3442,62 @@ pub fn array_element_ty<'tcx>(ty: Ty<'tcx>) -> Option<Ty<'tcx>> {
     }
 }
 
+/// Returns the type of element at index `i` in tuple or tuple-like type `t`.
+/// For an enum `t`, `variant` is None only if `t` is a univariant enum.
+pub fn positional_element_ty<'tcx>(cx: &ctxt<'tcx>,
+                                   ty: Ty<'tcx>,
+                                   i: uint,
+                                   variant: Option<ast::DefId>) -> Option<Ty<'tcx>> {
+
+    match (&ty.sty, variant) {
+        (&ty_tup(ref v), None) => v.as_slice().get(i).map(|&t| t),
+
+
+        (&ty_struct(def_id, ref substs), None) => lookup_struct_fields(cx, def_id)
+            .as_slice().get(i)
+            .map(|&t|lookup_item_type(cx, t.id).ty.subst(cx, substs)),
+
+        (&ty_enum(def_id, ref substs), Some(variant_def_id)) => {
+            let variant_info = enum_variant_with_id(cx, def_id, variant_def_id);
+            variant_info.args.as_slice().get(i).map(|t|t.subst(cx, substs))
+        }
+
+        (&ty_enum(def_id, ref substs), None) => {
+            assert!(enum_is_univariant(cx, def_id));
+            let enum_variants = enum_variants(cx, def_id);
+            let variant_info = &(*enum_variants)[0];
+            variant_info.args.as_slice().get(i).map(|t|t.subst(cx, substs))
+        }
+
+        _ => None
+    }
+}
+
+/// Returns the type of element at field `n` in struct or struct-like type `t`.
+/// For an enum `t`, `variant` must be some def id.
+pub fn named_element_ty<'tcx>(cx: &ctxt<'tcx>,
+                              ty: Ty<'tcx>,
+                              n: ast::Name,
+                              variant: Option<ast::DefId>) -> Option<Ty<'tcx>> {
+
+    match (&ty.sty, variant) {
+        (&ty_struct(def_id, ref substs), None) => {
+            let r = lookup_struct_fields(cx, def_id);
+            r.iter().find(|f| f.name == n)
+                .map(|&f| lookup_field_type(cx, def_id, f.id, substs))
+        }
+        (&ty_enum(def_id, ref substs), Some(variant_def_id)) => {
+            let variant_info = enum_variant_with_id(cx, def_id, variant_def_id);
+            variant_info.arg_names.as_ref()
+                .expect("must have struct enum variant if accessing a named fields")
+                .iter().zip(variant_info.args.iter())
+                .find(|&(ident, _)| ident.name == n)
+                .map(|(_ident, arg_t)| arg_t.subst(cx, substs))
+        }
+        _ => None
+    }
+}
+
 pub fn node_id_to_trait_ref<'tcx>(cx: &ctxt<'tcx>, id: ast::NodeId)
                                   -> Rc<ty::TraitRef<'tcx>> {
     match cx.trait_refs.borrow().get(&id) {
diff --git a/src/librustc/session/config.rs b/src/librustc/session/config.rs
index e10a1a4342c..82cf8f28e3d 100644
--- a/src/librustc/session/config.rs
+++ b/src/librustc/session/config.rs
@@ -208,6 +208,7 @@ debugging_opts!(
         AST_JSON_NOEXPAND,
         LS,
         SAVE_ANALYSIS,
+        PRINT_MOVE_FRAGMENTS,
         FLOWGRAPH_PRINT_LOANS,
         FLOWGRAPH_PRINT_MOVES,
         FLOWGRAPH_PRINT_ASSIGNS,
@@ -246,6 +247,8 @@ pub fn debugging_opts_map() -> Vec<(&'static str, &'static str, u64)> {
      ("ls", "List the symbols defined by a library crate", LS),
      ("save-analysis", "Write syntax and type analysis information \
                         in addition to normal output", SAVE_ANALYSIS),
+     ("print-move-fragments", "Print out move-fragment data for every fn",
+      PRINT_MOVE_FRAGMENTS),
      ("flowgraph-print-loans", "Include loan analysis data in \
                        --pretty flowgraph output", FLOWGRAPH_PRINT_LOANS),
      ("flowgraph-print-moves", "Include move analysis data in \
diff --git a/src/librustc/session/mod.rs b/src/librustc/session/mod.rs
index 72a9f23aa1f..89f6cda64d9 100644
--- a/src/librustc/session/mod.rs
+++ b/src/librustc/session/mod.rs
@@ -90,6 +90,12 @@ impl Session {
     pub fn warn(&self, msg: &str) {
         self.diagnostic().handler().warn(msg)
     }
+    pub fn opt_span_warn(&self, opt_sp: Option<Span>, msg: &str) {
+        match opt_sp {
+            Some(sp) => self.span_warn(sp, msg),
+            None => self.warn(msg),
+        }
+    }
     pub fn span_note(&self, sp: Span, msg: &str) {
         self.diagnostic().span_note(sp, msg)
     }
@@ -108,6 +114,12 @@ impl Session {
     pub fn help(&self, msg: &str) {
         self.diagnostic().handler().note(msg)
     }
+    pub fn opt_span_bug(&self, opt_sp: Option<Span>, msg: &str) -> ! {
+        match opt_sp {
+            Some(sp) => self.span_bug(sp, msg),
+            None => self.bug(msg),
+        }
+    }
     pub fn span_bug(&self, sp: Span, msg: &str) -> ! {
         self.diagnostic().span_bug(sp, msg)
     }