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.
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.
11 //! Helper routines used for fragmenting structural paths due to moves for
12 //! tracking drop obligations. Please see the extensive comments in the
13 //! section "Structural fragments" in `README.md`.
15 use self::Fragment
::*;
17 use borrowck
::InteriorKind
::{InteriorField, InteriorElement}
;
18 use borrowck
::{self, LoanPath}
;
19 use borrowck
::LoanPathKind
::{LpVar, LpUpvar, LpDowncast, LpExtend}
;
20 use borrowck
::LoanPathElem
::{LpDeref, LpInterior}
;
21 use borrowck
::move_data
::InvalidMovePathIndex
;
22 use borrowck
::move_data
::{MoveData, MovePathIndex}
;
23 use rustc
::hir
::def_id
::{DefId}
;
24 use rustc
::ty
::{self, TyCtxt}
;
25 use rustc
::middle
::mem_categorization
as mc
;
30 use syntax
::codemap
::{Span, DUMMY_SP}
;
31 use syntax
::attr
::AttrMetaMethods
;
33 #[derive(PartialEq, Eq, PartialOrd, Ord)]
35 // This represents the path described by the move path index
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 `&foo[..]`).
42 AllButOneFrom(MovePathIndex
),
46 fn loan_path_repr(&self, move_data
: &MoveData
) -> String
{
47 let lp
= |mpi
| move_data
.path_loan_path(mpi
);
49 Just(mpi
) => format
!("{:?}", lp(mpi
)),
50 AllButOneFrom(mpi
) => format
!("$(allbutone {:?})", lp(mpi
)),
54 fn loan_path_user_string(&self, move_data
: &MoveData
) -> String
{
55 let lp
= |mpi
| move_data
.path_loan_path(mpi
);
57 Just(mpi
) => lp(mpi
).to_string(),
58 AllButOneFrom(mpi
) => format
!("$(allbutone {})", lp(mpi
)),
63 pub fn build_unfragmented_map(this
: &mut borrowck
::BorrowckCtxt
,
66 let fr
= &move_data
.fragments
.borrow();
68 // For now, don't care about other kinds of fragments; the precise
69 // classfication of all paths for non-zeroing *drop* needs them,
70 // but the loose approximation used by non-zeroing moves does not.
71 let moved_leaf_paths
= fr
.moved_leaf_paths();
72 let assigned_leaf_paths
= fr
.assigned_leaf_paths();
74 let mut fragment_infos
= Vec
::with_capacity(moved_leaf_paths
.len());
76 let find_var_id
= |move_path_index
: MovePathIndex
| -> Option
<ast
::NodeId
> {
77 let lp
= move_data
.path_loan_path(move_path_index
);
79 LpVar(var_id
) => Some(var_id
),
80 LpUpvar(ty
::UpvarId { var_id, closure_expr_id }
) => {
81 // The `var_id` is unique *relative to* the current function.
82 // (Check that we are indeed talking about the same function.)
83 assert_eq
!(id
, closure_expr_id
);
86 LpDowncast(..) | LpExtend(..) => {
87 // This simple implementation of non-zeroing move does
88 // not attempt to deal with tracking substructure
89 // accurately in the general case.
95 let moves
= move_data
.moves
.borrow();
96 for &move_path_index
in moved_leaf_paths
{
97 let var_id
= match find_var_id(move_path_index
) {
99 Some(var_id
) => var_id
,
102 move_data
.each_applicable_move(move_path_index
, |move_index
| {
103 let info
= ty
::FragmentInfo
::Moved
{
105 move_expr
: moves
[move_index
.get()].id
,
107 debug
!("fragment_infos push({:?} \
108 due to move_path_index: {} move_index: {}",
109 info
, move_path_index
.get(), move_index
.get());
110 fragment_infos
.push(info
);
115 for &move_path_index
in assigned_leaf_paths
{
116 let var_id
= match find_var_id(move_path_index
) {
118 Some(var_id
) => var_id
,
121 let var_assigns
= move_data
.var_assignments
.borrow();
122 for var_assign
in var_assigns
.iter()
123 .filter(|&assign
| assign
.path
== move_path_index
)
125 let info
= ty
::FragmentInfo
::Assigned
{
127 assign_expr
: var_assign
.id
,
128 assignee_id
: var_assign
.assignee_id
,
130 debug
!("fragment_infos push({:?} due to var_assignment", info
);
131 fragment_infos
.push(info
);
135 let mut fraginfo_map
= this
.tcx
.fragment_infos
.borrow_mut();
136 let fn_did
= this
.tcx
.map
.local_def_id(id
);
137 let prev
= fraginfo_map
.insert(fn_did
, fragment_infos
);
138 assert
!(prev
.is_none());
141 pub struct FragmentSets
{
142 /// During move_data construction, `moved_leaf_paths` tracks paths
143 /// that have been used directly by being moved out of. When
144 /// move_data construction has been completed, `moved_leaf_paths`
145 /// tracks such paths that are *leaf fragments* (e.g. `a.j` if we
146 /// never move out any child like `a.j.x`); any parent paths
147 /// (e.g. `a` for the `a.j` example) are moved over to
148 /// `parents_of_fragments`.
149 moved_leaf_paths
: Vec
<MovePathIndex
>,
151 /// `assigned_leaf_paths` tracks paths that have been used
152 /// directly by being overwritten, but is otherwise much like
153 /// `moved_leaf_paths`.
154 assigned_leaf_paths
: Vec
<MovePathIndex
>,
156 /// `parents_of_fragments` tracks paths that are definitely
157 /// parents of paths that have been moved.
159 /// FIXME(pnkfelix) probably do not want/need
160 /// `parents_of_fragments` at all, if we can avoid it.
162 /// Update: I do not see a way to avoid it. Maybe just remove
163 /// above fixme, or at least document why doing this may be hard.
164 parents_of_fragments
: Vec
<MovePathIndex
>,
166 /// During move_data construction (specifically the
167 /// fixup_fragment_sets call), `unmoved_fragments` tracks paths
168 /// that have been "left behind" after a sibling has been moved or
169 /// assigned. When move_data construction has been completed,
170 /// `unmoved_fragments` tracks paths that were *only* results of
171 /// being left-behind, and never directly moved themselves.
172 unmoved_fragments
: Vec
<Fragment
>,
176 pub fn new() -> FragmentSets
{
178 unmoved_fragments
: Vec
::new(),
179 moved_leaf_paths
: Vec
::new(),
180 assigned_leaf_paths
: Vec
::new(),
181 parents_of_fragments
: Vec
::new(),
185 pub fn moved_leaf_paths(&self) -> &[MovePathIndex
] {
186 &self.moved_leaf_paths
189 pub fn assigned_leaf_paths(&self) -> &[MovePathIndex
] {
190 &self.assigned_leaf_paths
193 pub fn add_move(&mut self, path_index
: MovePathIndex
) {
194 self.moved_leaf_paths
.push(path_index
);
197 pub fn add_assignment(&mut self, path_index
: MovePathIndex
) {
198 self.assigned_leaf_paths
.push(path_index
);
202 pub fn instrument_move_fragments
<'tcx
>(this
: &MoveData
<'tcx
>,
206 let span_err
= tcx
.map
.attrs(id
).iter()
207 .any(|a
| a
.check_name("rustc_move_fragments"));
208 let print
= tcx
.sess
.opts
.debugging_opts
.print_move_fragments
;
210 if !span_err
&& !print { return; }
212 let instrument_all_paths
= |kind
, vec_rc
: &Vec
<MovePathIndex
>| {
213 for (i
, mpi
) in vec_rc
.iter().enumerate() {
214 let lp
= || this
.path_loan_path(*mpi
);
216 tcx
.sess
.span_err(sp
, &format
!("{}: `{}`", kind
, lp()));
219 println
!("id:{} {}[{}] `{}`", id
, kind
, i
, lp());
224 let instrument_all_fragments
= |kind
, vec_rc
: &Vec
<Fragment
>| {
225 for (i
, f
) in vec_rc
.iter().enumerate() {
226 let render
= || f
.loan_path_user_string(this
);
228 tcx
.sess
.span_err(sp
, &format
!("{}: `{}`", kind
, render()));
231 println
!("id:{} {}[{}] `{}`", id
, kind
, i
, render());
236 let fragments
= this
.fragments
.borrow();
237 instrument_all_paths("moved_leaf_path", &fragments
.moved_leaf_paths
);
238 instrument_all_fragments("unmoved_fragment", &fragments
.unmoved_fragments
);
239 instrument_all_paths("parent_of_fragments", &fragments
.parents_of_fragments
);
240 instrument_all_paths("assigned_leaf_path", &fragments
.assigned_leaf_paths
);
243 /// Normalizes the fragment sets in `this`; i.e., removes duplicate entries, constructs the set of
244 /// parents, and constructs the left-over fragments.
246 /// Note: "left-over fragments" means paths that were not directly referenced in moves nor
247 /// assignments, but must nonetheless be tracked as potential drop obligations.
248 pub fn fixup_fragment_sets
<'tcx
>(this
: &MoveData
<'tcx
>, tcx
: &TyCtxt
<'tcx
>) {
250 let mut fragments
= this
.fragments
.borrow_mut();
252 // Swap out contents of fragments so that we can modify the fields
253 // without borrowing the common fragments.
254 let mut unmoved
= mem
::replace(&mut fragments
.unmoved_fragments
, vec
![]);
255 let mut parents
= mem
::replace(&mut fragments
.parents_of_fragments
, vec
![]);
256 let mut moved
= mem
::replace(&mut fragments
.moved_leaf_paths
, vec
![]);
257 let mut assigned
= mem
::replace(&mut fragments
.assigned_leaf_paths
, vec
![]);
259 let path_lps
= |mpis
: &[MovePathIndex
]| -> Vec
<String
> {
260 mpis
.iter().map(|mpi
| format
!("{:?}", this
.path_loan_path(*mpi
))).collect()
263 let frag_lps
= |fs
: &[Fragment
]| -> Vec
<String
> {
264 fs
.iter().map(|f
| f
.loan_path_repr(this
)).collect()
267 // First, filter out duplicates
270 debug
!("fragments 1 moved: {:?}", path_lps(&moved
[..]));
274 debug
!("fragments 1 assigned: {:?}", path_lps(&assigned
[..]));
276 // Second, build parents from the moved and assigned.
278 let mut p
= this
.path_parent(*m
);
279 while p
!= InvalidMovePathIndex
{
281 p
= this
.path_parent(p
);
285 let mut p
= this
.path_parent(*a
);
286 while p
!= InvalidMovePathIndex
{
288 p
= this
.path_parent(p
);
294 debug
!("fragments 2 parents: {:?}", path_lps(&parents
[..]));
296 // Third, filter the moved and assigned fragments down to just the non-parents
297 moved
.retain(|f
| non_member(*f
, &parents
[..]));
298 debug
!("fragments 3 moved: {:?}", path_lps(&moved
[..]));
300 assigned
.retain(|f
| non_member(*f
, &parents
[..]));
301 debug
!("fragments 3 assigned: {:?}", path_lps(&assigned
[..]));
303 // Fourth, build the leftover from the moved, assigned, and parents.
305 let lp
= this
.path_loan_path(*m
);
306 add_fragment_siblings(this
, tcx
, &mut unmoved
, lp
, None
);
309 let lp
= this
.path_loan_path(*a
);
310 add_fragment_siblings(this
, tcx
, &mut unmoved
, lp
, None
);
313 let lp
= this
.path_loan_path(*p
);
314 add_fragment_siblings(this
, tcx
, &mut unmoved
, lp
, None
);
319 debug
!("fragments 4 unmoved: {:?}", frag_lps(&unmoved
[..]));
321 // Fifth, filter the leftover fragments down to its core.
322 unmoved
.retain(|f
| match *f
{
323 AllButOneFrom(_
) => true,
324 Just(mpi
) => non_member(mpi
, &parents
[..]) &&
325 non_member(mpi
, &moved
[..]) &&
326 non_member(mpi
, &assigned
[..])
328 debug
!("fragments 5 unmoved: {:?}", frag_lps(&unmoved
[..]));
330 // Swap contents back in.
331 fragments
.unmoved_fragments
= unmoved
;
332 fragments
.parents_of_fragments
= parents
;
333 fragments
.moved_leaf_paths
= moved
;
334 fragments
.assigned_leaf_paths
= assigned
;
338 fn non_member(elem
: MovePathIndex
, set
: &[MovePathIndex
]) -> bool
{
339 match set
.binary_search(&elem
) {
346 /// Adds all of the precisely-tracked siblings of `lp` as potential move paths of interest. For
347 /// example, if `lp` represents `s.x.j`, then adds moves paths for `s.x.i` and `s.x.k`, the
348 /// siblings of `s.x.j`.
349 fn add_fragment_siblings
<'tcx
>(this
: &MoveData
<'tcx
>,
351 gathered_fragments
: &mut Vec
<Fragment
>,
352 lp
: Rc
<LoanPath
<'tcx
>>,
353 origin_id
: Option
<ast
::NodeId
>) {
355 LpVar(_
) | LpUpvar(..) => {}
// Local variables have no siblings.
357 // Consuming a downcast is like consuming the original value, so propage inward.
358 LpDowncast(ref loan_parent
, _
) => {
359 add_fragment_siblings(this
, tcx
, gathered_fragments
, loan_parent
.clone(), origin_id
);
362 // *LV for Unique consumes the contents of the box (at
363 // least when it is non-copy...), so propagate inward.
364 LpExtend(ref loan_parent
, _
, LpDeref(mc
::Unique
)) => {
365 add_fragment_siblings(this
, tcx
, gathered_fragments
, loan_parent
.clone(), origin_id
);
368 // *LV for unsafe and borrowed pointers do not consume their loan path, so stop here.
369 LpExtend(_
, _
, LpDeref(mc
::UnsafePtr(..))) |
370 LpExtend(_
, _
, LpDeref(mc
::Implicit(..))) |
371 LpExtend(_
, _
, LpDeref(mc
::BorrowedPtr(..))) => {}
373 // FIXME (pnkfelix): LV[j] should be tracked, at least in the
374 // sense of we will track the remaining drop obligation of the
375 // rest of the array.
377 // Well, either that or LV[j] should be made illegal.
378 // But even then, we will need to deal with destructuring
381 // Anyway, for now: LV[j] is not tracked precisely
382 LpExtend(_
, _
, LpInterior(_
, InteriorElement(..))) => {
383 let mp
= this
.move_path(tcx
, lp
.clone());
384 gathered_fragments
.push(AllButOneFrom(mp
));
387 // field access LV.x and tuple access LV#k are the cases
388 // we are interested in
389 LpExtend(ref loan_parent
, mc
,
390 LpInterior(_
, InteriorField(ref field_name
))) => {
391 let enum_variant_info
= match loan_parent
.kind
{
392 LpDowncast(ref loan_parent_2
, variant_def_id
) =>
393 Some((variant_def_id
, loan_parent_2
.clone())),
394 LpExtend(..) | LpVar(..) | LpUpvar(..) =>
397 add_fragment_siblings_for_extension(
401 loan_parent
, mc
, field_name
, &lp
, origin_id
, enum_variant_info
);
406 /// We have determined that `origin_lp` destructures to LpExtend(parent, original_field_name).
407 /// Based on this, add move paths for all of the siblings of `origin_lp`.
408 fn add_fragment_siblings_for_extension
<'tcx
>(this
: &MoveData
<'tcx
>,
410 gathered_fragments
: &mut Vec
<Fragment
>,
411 parent_lp
: &Rc
<LoanPath
<'tcx
>>,
412 mc
: mc
::MutabilityCategory
,
413 origin_field_name
: &mc
::FieldName
,
414 origin_lp
: &Rc
<LoanPath
<'tcx
>>,
415 origin_id
: Option
<ast
::NodeId
>,
416 enum_variant_info
: Option
<(DefId
,
417 Rc
<LoanPath
<'tcx
>>)>) {
418 let parent_ty
= parent_lp
.to_type();
420 let mut add_fragment_sibling_local
= |field_name
, variant_did
| {
421 add_fragment_sibling_core(
422 this
, tcx
, gathered_fragments
, parent_lp
.clone(), mc
, field_name
, origin_lp
,
426 match (&parent_ty
.sty
, enum_variant_info
) {
427 (&ty
::TyTuple(ref v
), None
) => {
428 let tuple_idx
= match *origin_field_name
{
429 mc
::PositionalField(tuple_idx
) => tuple_idx
,
431 bug
!("tuple type {:?} should not have named fields.",
434 let tuple_len
= v
.len();
435 for i
in 0..tuple_len
{
436 if i
== tuple_idx { continue }
437 let field_name
= mc
::PositionalField(i
);
438 add_fragment_sibling_local(field_name
, None
);
442 (&ty
::TyStruct(def
, _
), None
) => {
443 match *origin_field_name
{
444 mc
::NamedField(ast_name
) => {
445 for f
in &def
.struct_variant().fields
{
446 if f
.name
== ast_name
{
449 let field_name
= mc
::NamedField(f
.name
);
450 add_fragment_sibling_local(field_name
, None
);
453 mc
::PositionalField(tuple_idx
) => {
454 for (i
, _f
) in def
.struct_variant().fields
.iter().enumerate() {
458 let field_name
= mc
::PositionalField(i
);
459 add_fragment_sibling_local(field_name
, None
);
465 (&ty
::TyEnum(def
, _
), ref enum_variant_info
) => {
466 let variant
= match *enum_variant_info
{
467 Some((vid
, ref _lp2
)) => def
.variant_with_id(vid
),
469 assert
!(def
.is_univariant());
473 match *origin_field_name
{
474 mc
::NamedField(ast_name
) => {
475 for field
in &variant
.fields
{
476 if field
.name
== ast_name
{
479 let field_name
= mc
::NamedField(field
.name
);
480 add_fragment_sibling_local(field_name
, Some(variant
.did
));
483 mc
::PositionalField(tuple_idx
) => {
484 for (i
, _f
) in variant
.fields
.iter().enumerate() {
488 let field_name
= mc
::PositionalField(i
);
489 add_fragment_sibling_local(field_name
, None
);
495 ref sty_and_variant_info
=> {
496 let opt_span
= origin_id
.and_then(|id
|tcx
.map
.opt_span(id
));
497 span_bug
!(opt_span
.unwrap_or(DUMMY_SP
),
498 "type {:?} ({:?}) is not fragmentable",
500 sty_and_variant_info
);
505 /// Adds the single sibling `LpExtend(parent, new_field_name)` of `origin_lp` (the original
507 fn add_fragment_sibling_core
<'tcx
>(this
: &MoveData
<'tcx
>,
509 gathered_fragments
: &mut Vec
<Fragment
>,
510 parent
: Rc
<LoanPath
<'tcx
>>,
511 mc
: mc
::MutabilityCategory
,
512 new_field_name
: mc
::FieldName
,
513 origin_lp
: &Rc
<LoanPath
<'tcx
>>,
514 enum_variant_did
: Option
<DefId
>) -> MovePathIndex
{
515 let opt_variant_did
= match parent
.kind
{
516 LpDowncast(_
, variant_did
) => Some(variant_did
),
517 LpVar(..) | LpUpvar(..) | LpExtend(..) => enum_variant_did
,
520 let loan_path_elem
= LpInterior(opt_variant_did
, InteriorField(new_field_name
));
521 let new_lp_type
= match new_field_name
{
522 mc
::NamedField(ast_name
) =>
523 tcx
.named_element_ty(parent
.to_type(), ast_name
, opt_variant_did
),
524 mc
::PositionalField(idx
) =>
525 tcx
.positional_element_ty(parent
.to_type(), idx
, opt_variant_did
),
527 let new_lp_variant
= LpExtend(parent
, mc
, loan_path_elem
);
528 let new_lp
= LoanPath
::new(new_lp_variant
, new_lp_type
.unwrap());
529 debug
!("add_fragment_sibling_core(new_lp={:?}, origin_lp={:?})",
531 let mp
= this
.move_path(tcx
, Rc
::new(new_lp
));
533 // Do not worry about checking for duplicates here; we will sort
534 // and dedup after all are added.
535 gathered_fragments
.push(Just(mp
));