]>
Commit | Line | Data |
---|---|---|
1a4d82fc JJ |
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 | //! Data structures used for tracking moves. Please see the extensive | |
c34b1796 | 12 | //! comments in the section "Moves and initialization" in `README.md`. |
1a4d82fc JJ |
13 | |
14 | pub use self::MoveKind::*; | |
15 | ||
16 | use borrowck::*; | |
54a0048b | 17 | use rustc::cfg; |
1a4d82fc JJ |
18 | use rustc::middle::dataflow::DataFlowContext; |
19 | use rustc::middle::dataflow::BitwiseOperator; | |
20 | use rustc::middle::dataflow::DataFlowOperator; | |
9346a6ac | 21 | use rustc::middle::dataflow::KillFrom; |
1a4d82fc | 22 | use rustc::middle::expr_use_visitor as euv; |
9cc50fc6 | 23 | use rustc::middle::expr_use_visitor::MutateMode; |
9e0c209e SL |
24 | use rustc::middle::mem_categorization as mc; |
25 | use rustc::ty::{self, TyCtxt}; | |
476ff2be | 26 | use rustc::util::nodemap::{FxHashMap, NodeSet}; |
62682a34 | 27 | |
1a4d82fc JJ |
28 | use std::cell::RefCell; |
29 | use std::rc::Rc; | |
85aaf69f | 30 | use std::usize; |
1a4d82fc | 31 | use syntax::ast; |
3157f602 | 32 | use syntax_pos::Span; |
54a0048b SL |
33 | use rustc::hir; |
34 | use rustc::hir::intravisit::IdRange; | |
1a4d82fc | 35 | |
1a4d82fc | 36 | pub struct MoveData<'tcx> { |
c34b1796 | 37 | /// Move paths. See section "Move paths" in `README.md`. |
1a4d82fc JJ |
38 | pub paths: RefCell<Vec<MovePath<'tcx>>>, |
39 | ||
40 | /// Cache of loan path to move path index, for easy lookup. | |
476ff2be | 41 | pub path_map: RefCell<FxHashMap<Rc<LoanPath<'tcx>>, MovePathIndex>>, |
1a4d82fc JJ |
42 | |
43 | /// Each move or uninitialized variable gets an entry here. | |
44 | pub moves: RefCell<Vec<Move>>, | |
45 | ||
46 | /// Assignments to a variable, like `x = foo`. These are assigned | |
47 | /// bits for dataflow, since we must track them to ensure that | |
48 | /// immutable variables are assigned at most once along each path. | |
49 | pub var_assignments: RefCell<Vec<Assignment>>, | |
50 | ||
51 | /// Assignments to a path, like `x.f = foo`. These are not | |
52 | /// assigned dataflow bits, but we track them because they still | |
53 | /// kill move bits. | |
54 | pub path_assignments: RefCell<Vec<Assignment>>, | |
55 | ||
56 | /// Enum variant matched within a pattern on some match arm, like | |
57 | /// `SomeStruct{ f: Variant1(x, y) } => ...` | |
58 | pub variant_matches: RefCell<Vec<VariantMatch>>, | |
59 | ||
60 | /// Assignments to a variable or path, like `x = foo`, but not `x += foo`. | |
61 | pub assignee_ids: RefCell<NodeSet>, | |
1a4d82fc JJ |
62 | } |
63 | ||
64 | pub struct FlowedMoveData<'a, 'tcx: 'a> { | |
65 | pub move_data: MoveData<'tcx>, | |
66 | ||
67 | pub dfcx_moves: MoveDataFlow<'a, 'tcx>, | |
68 | ||
69 | // We could (and maybe should, for efficiency) combine both move | |
70 | // and assign data flow into one, but this way it's easier to | |
71 | // distinguish the bits that correspond to moves and assignments. | |
72 | pub dfcx_assign: AssignDataFlow<'a, 'tcx> | |
73 | } | |
74 | ||
75 | /// Index into `MoveData.paths`, used like a pointer | |
85aaf69f | 76 | #[derive(Copy, PartialEq, Eq, PartialOrd, Ord, Debug)] |
c34b1796 | 77 | pub struct MovePathIndex(usize); |
1a4d82fc JJ |
78 | |
79 | impl MovePathIndex { | |
c34b1796 | 80 | fn get(&self) -> usize { |
1a4d82fc JJ |
81 | let MovePathIndex(v) = *self; v |
82 | } | |
83 | } | |
84 | ||
85 | impl Clone for MovePathIndex { | |
86 | fn clone(&self) -> MovePathIndex { | |
87 | MovePathIndex(self.get()) | |
88 | } | |
89 | } | |
90 | ||
91 | #[allow(non_upper_case_globals)] | |
c34b1796 | 92 | const InvalidMovePathIndex: MovePathIndex = MovePathIndex(usize::MAX); |
1a4d82fc JJ |
93 | |
94 | /// Index into `MoveData.moves`, used like a pointer | |
c34b1796 AL |
95 | #[derive(Copy, Clone, PartialEq)] |
96 | pub struct MoveIndex(usize); | |
1a4d82fc JJ |
97 | |
98 | impl MoveIndex { | |
c34b1796 | 99 | fn get(&self) -> usize { |
1a4d82fc JJ |
100 | let MoveIndex(v) = *self; v |
101 | } | |
102 | } | |
103 | ||
104 | #[allow(non_upper_case_globals)] | |
c34b1796 | 105 | const InvalidMoveIndex: MoveIndex = MoveIndex(usize::MAX); |
1a4d82fc JJ |
106 | |
107 | pub struct MovePath<'tcx> { | |
108 | /// Loan path corresponding to this move path | |
109 | pub loan_path: Rc<LoanPath<'tcx>>, | |
110 | ||
111 | /// Parent pointer, `InvalidMovePathIndex` if root | |
112 | pub parent: MovePathIndex, | |
113 | ||
114 | /// Head of linked list of moves to this path, | |
115 | /// `InvalidMoveIndex` if not moved | |
116 | pub first_move: MoveIndex, | |
117 | ||
118 | /// First node in linked list of children, `InvalidMovePathIndex` if leaf | |
119 | pub first_child: MovePathIndex, | |
120 | ||
121 | /// Next node in linked list of parent's children (siblings), | |
122 | /// `InvalidMovePathIndex` if none. | |
123 | pub next_sibling: MovePathIndex, | |
124 | } | |
125 | ||
c34b1796 | 126 | #[derive(Copy, Clone, PartialEq, Debug)] |
1a4d82fc JJ |
127 | pub enum MoveKind { |
128 | Declared, // When declared, variables start out "moved". | |
129 | MoveExpr, // Expression or binding that moves a variable | |
130 | MovePat, // By-move binding | |
131 | Captured // Closure creation that moves a value | |
132 | } | |
133 | ||
c34b1796 | 134 | #[derive(Copy, Clone)] |
1a4d82fc JJ |
135 | pub struct Move { |
136 | /// Path being moved. | |
137 | pub path: MovePathIndex, | |
138 | ||
139 | /// id of node that is doing the move. | |
140 | pub id: ast::NodeId, | |
141 | ||
142 | /// Kind of move, for error messages. | |
143 | pub kind: MoveKind, | |
144 | ||
145 | /// Next node in linked list of moves from `path`, or `InvalidMoveIndex` | |
146 | pub next_move: MoveIndex | |
147 | } | |
148 | ||
c34b1796 | 149 | #[derive(Copy, Clone)] |
1a4d82fc JJ |
150 | pub struct Assignment { |
151 | /// Path being assigned. | |
152 | pub path: MovePathIndex, | |
153 | ||
154 | /// id where assignment occurs | |
155 | pub id: ast::NodeId, | |
156 | ||
157 | /// span of node where assignment occurs | |
158 | pub span: Span, | |
c1a9b12d SL |
159 | |
160 | /// id for l-value expression on lhs of assignment | |
161 | pub assignee_id: ast::NodeId, | |
1a4d82fc JJ |
162 | } |
163 | ||
c34b1796 | 164 | #[derive(Copy, Clone)] |
1a4d82fc JJ |
165 | pub struct VariantMatch { |
166 | /// downcast to the variant. | |
167 | pub path: MovePathIndex, | |
168 | ||
169 | /// path being downcast to the variant. | |
170 | pub base_path: MovePathIndex, | |
171 | ||
172 | /// id where variant's pattern occurs | |
173 | pub id: ast::NodeId, | |
174 | ||
175 | /// says if variant established by move (and why), by copy, or by borrow. | |
176 | pub mode: euv::MatchMode | |
177 | } | |
178 | ||
179 | #[derive(Clone, Copy)] | |
180 | pub struct MoveDataFlowOperator; | |
181 | ||
182 | pub type MoveDataFlow<'a, 'tcx> = DataFlowContext<'a, 'tcx, MoveDataFlowOperator>; | |
183 | ||
184 | #[derive(Clone, Copy)] | |
185 | pub struct AssignDataFlowOperator; | |
186 | ||
187 | pub type AssignDataFlow<'a, 'tcx> = DataFlowContext<'a, 'tcx, AssignDataFlowOperator>; | |
188 | ||
189 | fn loan_path_is_precise(loan_path: &LoanPath) -> bool { | |
190 | match loan_path.kind { | |
191 | LpVar(_) | LpUpvar(_) => { | |
192 | true | |
193 | } | |
7cac9316 | 194 | LpExtend(.., LpInterior(_, InteriorKind::InteriorElement)) => { |
85aaf69f | 195 | // Paths involving element accesses a[i] do not refer to a unique |
1a4d82fc | 196 | // location, as there is no accurate tracking of the indices. |
85aaf69f SL |
197 | // |
198 | // (Paths involving element accesses via slice pattern bindings | |
199 | // can in principle be tracked precisely, but that is future | |
200 | // work. For now, continue claiming that they are imprecise.) | |
1a4d82fc JJ |
201 | false |
202 | } | |
203 | LpDowncast(ref lp_base, _) | | |
9e0c209e | 204 | LpExtend(ref lp_base, ..) => { |
7453a54e | 205 | loan_path_is_precise(&lp_base) |
1a4d82fc JJ |
206 | } |
207 | } | |
208 | } | |
209 | ||
a7813a04 | 210 | impl<'a, 'tcx> MoveData<'tcx> { |
1a4d82fc JJ |
211 | pub fn new() -> MoveData<'tcx> { |
212 | MoveData { | |
213 | paths: RefCell::new(Vec::new()), | |
476ff2be | 214 | path_map: RefCell::new(FxHashMap()), |
1a4d82fc JJ |
215 | moves: RefCell::new(Vec::new()), |
216 | path_assignments: RefCell::new(Vec::new()), | |
217 | var_assignments: RefCell::new(Vec::new()), | |
218 | variant_matches: RefCell::new(Vec::new()), | |
85aaf69f | 219 | assignee_ids: RefCell::new(NodeSet()), |
1a4d82fc JJ |
220 | } |
221 | } | |
222 | ||
223 | pub fn path_loan_path(&self, index: MovePathIndex) -> Rc<LoanPath<'tcx>> { | |
224 | (*self.paths.borrow())[index.get()].loan_path.clone() | |
225 | } | |
226 | ||
227 | fn path_parent(&self, index: MovePathIndex) -> MovePathIndex { | |
228 | (*self.paths.borrow())[index.get()].parent | |
229 | } | |
230 | ||
231 | fn path_first_move(&self, index: MovePathIndex) -> MoveIndex { | |
232 | (*self.paths.borrow())[index.get()].first_move | |
233 | } | |
234 | ||
235 | /// Returns the index of first child, or `InvalidMovePathIndex` if | |
236 | /// `index` is leaf. | |
237 | fn path_first_child(&self, index: MovePathIndex) -> MovePathIndex { | |
238 | (*self.paths.borrow())[index.get()].first_child | |
239 | } | |
240 | ||
241 | fn path_next_sibling(&self, index: MovePathIndex) -> MovePathIndex { | |
242 | (*self.paths.borrow())[index.get()].next_sibling | |
243 | } | |
244 | ||
245 | fn set_path_first_move(&self, | |
246 | index: MovePathIndex, | |
247 | first_move: MoveIndex) { | |
248 | (*self.paths.borrow_mut())[index.get()].first_move = first_move | |
249 | } | |
250 | ||
251 | fn set_path_first_child(&self, | |
252 | index: MovePathIndex, | |
253 | first_child: MovePathIndex) { | |
254 | (*self.paths.borrow_mut())[index.get()].first_child = first_child | |
255 | } | |
256 | ||
257 | fn move_next_move(&self, index: MoveIndex) -> MoveIndex { | |
258 | //! Type safe indexing operator | |
259 | (*self.moves.borrow())[index.get()].next_move | |
260 | } | |
261 | ||
262 | fn is_var_path(&self, index: MovePathIndex) -> bool { | |
263 | //! True if `index` refers to a variable | |
264 | self.path_parent(index) == InvalidMovePathIndex | |
265 | } | |
266 | ||
267 | /// Returns the existing move path index for `lp`, if any, and otherwise adds a new index for | |
268 | /// `lp` and any of its base paths that do not yet have an index. | |
a7813a04 | 269 | pub fn move_path(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, |
1a4d82fc | 270 | lp: Rc<LoanPath<'tcx>>) -> MovePathIndex { |
3157f602 XL |
271 | if let Some(&index) = self.path_map.borrow().get(&lp) { |
272 | return index; | |
1a4d82fc JJ |
273 | } |
274 | ||
275 | let index = match lp.kind { | |
276 | LpVar(..) | LpUpvar(..) => { | |
277 | let index = MovePathIndex(self.paths.borrow().len()); | |
278 | ||
279 | self.paths.borrow_mut().push(MovePath { | |
280 | loan_path: lp.clone(), | |
281 | parent: InvalidMovePathIndex, | |
282 | first_move: InvalidMoveIndex, | |
283 | first_child: InvalidMovePathIndex, | |
284 | next_sibling: InvalidMovePathIndex, | |
285 | }); | |
286 | ||
287 | index | |
288 | } | |
289 | ||
290 | LpDowncast(ref base, _) | | |
9e0c209e | 291 | LpExtend(ref base, ..) => { |
1a4d82fc JJ |
292 | let parent_index = self.move_path(tcx, base.clone()); |
293 | ||
294 | let index = MovePathIndex(self.paths.borrow().len()); | |
295 | ||
296 | let next_sibling = self.path_first_child(parent_index); | |
297 | self.set_path_first_child(parent_index, index); | |
298 | ||
299 | self.paths.borrow_mut().push(MovePath { | |
300 | loan_path: lp.clone(), | |
301 | parent: parent_index, | |
302 | first_move: InvalidMoveIndex, | |
303 | first_child: InvalidMovePathIndex, | |
304 | next_sibling: next_sibling, | |
305 | }); | |
306 | ||
307 | index | |
308 | } | |
309 | }; | |
310 | ||
62682a34 SL |
311 | debug!("move_path(lp={:?}, index={:?})", |
312 | lp, | |
1a4d82fc JJ |
313 | index); |
314 | ||
315 | assert_eq!(index.get(), self.paths.borrow().len() - 1); | |
316 | self.path_map.borrow_mut().insert(lp, index); | |
317 | return index; | |
318 | } | |
319 | ||
320 | fn existing_move_path(&self, lp: &Rc<LoanPath<'tcx>>) | |
321 | -> Option<MovePathIndex> { | |
322 | self.path_map.borrow().get(lp).cloned() | |
323 | } | |
324 | ||
325 | fn existing_base_paths(&self, lp: &Rc<LoanPath<'tcx>>) | |
326 | -> Vec<MovePathIndex> { | |
c30ab7b3 | 327 | let mut result = vec![]; |
1a4d82fc JJ |
328 | self.add_existing_base_paths(lp, &mut result); |
329 | result | |
330 | } | |
331 | ||
332 | /// Adds any existing move path indices for `lp` and any base paths of `lp` to `result`, but | |
333 | /// does not add new move paths | |
334 | fn add_existing_base_paths(&self, lp: &Rc<LoanPath<'tcx>>, | |
335 | result: &mut Vec<MovePathIndex>) { | |
336 | match self.path_map.borrow().get(lp).cloned() { | |
337 | Some(index) => { | |
338 | self.each_base_path(index, |p| { | |
339 | result.push(p); | |
340 | true | |
341 | }); | |
342 | } | |
343 | None => { | |
344 | match lp.kind { | |
345 | LpVar(..) | LpUpvar(..) => { } | |
346 | LpDowncast(ref b, _) | | |
9e0c209e | 347 | LpExtend(ref b, ..) => { |
1a4d82fc JJ |
348 | self.add_existing_base_paths(b, result); |
349 | } | |
350 | } | |
351 | } | |
352 | } | |
353 | ||
354 | } | |
355 | ||
356 | /// Adds a new move entry for a move of `lp` that occurs at location `id` with kind `kind`. | |
a7813a04 | 357 | pub fn add_move(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, |
cc61c64b | 358 | orig_lp: Rc<LoanPath<'tcx>>, |
1a4d82fc JJ |
359 | id: ast::NodeId, |
360 | kind: MoveKind) { | |
cc61c64b XL |
361 | // Moving one union field automatically moves all its fields. Also move siblings of |
362 | // all parent union fields, moves do not propagate upwards automatically. | |
363 | let mut lp = orig_lp.clone(); | |
364 | while let LpExtend(ref base_lp, mutbl, lp_elem) = lp.clone().kind { | |
365 | if let (&ty::TyAdt(adt_def, _), LpInterior(opt_variant_id, interior)) | |
366 | = (&base_lp.ty.sty, lp_elem) { | |
9e0c209e SL |
367 | if adt_def.is_union() { |
368 | for field in &adt_def.struct_variant().fields { | |
369 | let field = InteriorKind::InteriorField(mc::NamedField(field.name)); | |
cc61c64b XL |
370 | if field != interior { |
371 | let sibling_lp_kind = | |
372 | LpExtend(base_lp.clone(), mutbl, LpInterior(opt_variant_id, field)); | |
373 | let sibling_lp = Rc::new(LoanPath::new(sibling_lp_kind, tcx.types.err)); | |
374 | self.add_move_helper(tcx, sibling_lp, id, kind); | |
375 | } | |
9e0c209e | 376 | } |
9e0c209e SL |
377 | } |
378 | } | |
cc61c64b | 379 | lp = base_lp.clone(); |
9e0c209e SL |
380 | } |
381 | ||
cc61c64b | 382 | self.add_move_helper(tcx, orig_lp.clone(), id, kind); |
9e0c209e SL |
383 | } |
384 | ||
385 | fn add_move_helper(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
386 | lp: Rc<LoanPath<'tcx>>, | |
387 | id: ast::NodeId, | |
388 | kind: MoveKind) { | |
62682a34 SL |
389 | debug!("add_move(lp={:?}, id={}, kind={:?})", |
390 | lp, | |
1a4d82fc JJ |
391 | id, |
392 | kind); | |
393 | ||
394 | let path_index = self.move_path(tcx, lp.clone()); | |
395 | let move_index = MoveIndex(self.moves.borrow().len()); | |
396 | ||
1a4d82fc JJ |
397 | let next_move = self.path_first_move(path_index); |
398 | self.set_path_first_move(path_index, move_index); | |
399 | ||
400 | self.moves.borrow_mut().push(Move { | |
401 | path: path_index, | |
402 | id: id, | |
403 | kind: kind, | |
404 | next_move: next_move | |
405 | }); | |
406 | } | |
407 | ||
408 | /// Adds a new record for an assignment to `lp` that occurs at location `id` with the given | |
409 | /// `span`. | |
a7813a04 | 410 | pub fn add_assignment(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, |
1a4d82fc JJ |
411 | lp: Rc<LoanPath<'tcx>>, |
412 | assign_id: ast::NodeId, | |
413 | span: Span, | |
414 | assignee_id: ast::NodeId, | |
415 | mode: euv::MutateMode) { | |
9e0c209e SL |
416 | // Assigning to one union field automatically assigns to all its fields. |
417 | if let LpExtend(ref base_lp, mutbl, LpInterior(opt_variant_id, interior)) = lp.kind { | |
418 | if let ty::TyAdt(adt_def, _) = base_lp.ty.sty { | |
419 | if adt_def.is_union() { | |
420 | for field in &adt_def.struct_variant().fields { | |
421 | let field = InteriorKind::InteriorField(mc::NamedField(field.name)); | |
422 | let field_ty = if field == interior { | |
423 | lp.ty | |
424 | } else { | |
425 | tcx.types.err // Doesn't matter | |
426 | }; | |
427 | let sibling_lp_kind = LpExtend(base_lp.clone(), mutbl, | |
428 | LpInterior(opt_variant_id, field)); | |
429 | let sibling_lp = Rc::new(LoanPath::new(sibling_lp_kind, field_ty)); | |
430 | self.add_assignment_helper(tcx, sibling_lp, assign_id, | |
431 | span, assignee_id, mode); | |
432 | } | |
433 | return; | |
434 | } | |
435 | } | |
436 | } | |
437 | ||
438 | self.add_assignment_helper(tcx, lp.clone(), assign_id, span, assignee_id, mode); | |
439 | } | |
440 | ||
441 | fn add_assignment_helper(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
442 | lp: Rc<LoanPath<'tcx>>, | |
443 | assign_id: ast::NodeId, | |
444 | span: Span, | |
445 | assignee_id: ast::NodeId, | |
446 | mode: euv::MutateMode) { | |
62682a34 SL |
447 | debug!("add_assignment(lp={:?}, assign_id={}, assignee_id={}", |
448 | lp, assign_id, assignee_id); | |
1a4d82fc JJ |
449 | |
450 | let path_index = self.move_path(tcx, lp.clone()); | |
451 | ||
1a4d82fc | 452 | match mode { |
9cc50fc6 | 453 | MutateMode::Init | MutateMode::JustWrite => { |
1a4d82fc JJ |
454 | self.assignee_ids.borrow_mut().insert(assignee_id); |
455 | } | |
9cc50fc6 | 456 | MutateMode::WriteAndRead => { } |
1a4d82fc JJ |
457 | } |
458 | ||
459 | let assignment = Assignment { | |
460 | path: path_index, | |
461 | id: assign_id, | |
462 | span: span, | |
c1a9b12d | 463 | assignee_id: assignee_id, |
1a4d82fc JJ |
464 | }; |
465 | ||
466 | if self.is_var_path(path_index) { | |
62682a34 SL |
467 | debug!("add_assignment[var](lp={:?}, assignment={}, path_index={:?})", |
468 | lp, self.var_assignments.borrow().len(), path_index); | |
1a4d82fc JJ |
469 | |
470 | self.var_assignments.borrow_mut().push(assignment); | |
471 | } else { | |
62682a34 SL |
472 | debug!("add_assignment[path](lp={:?}, path_index={:?})", |
473 | lp, path_index); | |
1a4d82fc JJ |
474 | |
475 | self.path_assignments.borrow_mut().push(assignment); | |
476 | } | |
477 | } | |
478 | ||
479 | /// Adds a new record for a match of `base_lp`, downcast to | |
480 | /// variant `lp`, that occurs at location `pattern_id`. (One | |
481 | /// should be able to recover the span info from the | |
32a655c1 | 482 | /// `pattern_id` and the hir_map, I think.) |
a7813a04 | 483 | pub fn add_variant_match(&self, tcx: TyCtxt<'a, 'tcx, 'tcx>, |
1a4d82fc JJ |
484 | lp: Rc<LoanPath<'tcx>>, |
485 | pattern_id: ast::NodeId, | |
486 | base_lp: Rc<LoanPath<'tcx>>, | |
487 | mode: euv::MatchMode) { | |
62682a34 SL |
488 | debug!("add_variant_match(lp={:?}, pattern_id={})", |
489 | lp, pattern_id); | |
1a4d82fc JJ |
490 | |
491 | let path_index = self.move_path(tcx, lp.clone()); | |
492 | let base_path_index = self.move_path(tcx, base_lp.clone()); | |
493 | ||
1a4d82fc JJ |
494 | let variant_match = VariantMatch { |
495 | path: path_index, | |
496 | base_path: base_path_index, | |
497 | id: pattern_id, | |
498 | mode: mode, | |
499 | }; | |
500 | ||
501 | self.variant_matches.borrow_mut().push(variant_match); | |
502 | } | |
503 | ||
1a4d82fc JJ |
504 | /// Adds the gen/kills for the various moves and |
505 | /// assignments into the provided data flow contexts. | |
506 | /// Moves are generated by moves and killed by assignments and | |
507 | /// scoping. Assignments are generated by assignment to variables and | |
c34b1796 | 508 | /// killed by scoping. See `README.md` for more details. |
7cac9316 XL |
509 | fn add_gen_kills(&self, |
510 | bccx: &BorrowckCtxt<'a, 'tcx>, | |
1a4d82fc JJ |
511 | dfcx_moves: &mut MoveDataFlow, |
512 | dfcx_assign: &mut AssignDataFlow) { | |
513 | for (i, the_move) in self.moves.borrow().iter().enumerate() { | |
514 | dfcx_moves.add_gen(the_move.id, i); | |
515 | } | |
516 | ||
517 | for (i, assignment) in self.var_assignments.borrow().iter().enumerate() { | |
518 | dfcx_assign.add_gen(assignment.id, i); | |
9346a6ac AL |
519 | self.kill_moves(assignment.path, assignment.id, |
520 | KillFrom::Execution, dfcx_moves); | |
1a4d82fc JJ |
521 | } |
522 | ||
62682a34 | 523 | for assignment in self.path_assignments.borrow().iter() { |
9346a6ac AL |
524 | self.kill_moves(assignment.path, assignment.id, |
525 | KillFrom::Execution, dfcx_moves); | |
1a4d82fc JJ |
526 | } |
527 | ||
528 | // Kill all moves related to a variable `x` when | |
529 | // it goes out of scope: | |
62682a34 | 530 | for path in self.paths.borrow().iter() { |
1a4d82fc JJ |
531 | match path.loan_path.kind { |
532 | LpVar(..) | LpUpvar(..) | LpDowncast(..) => { | |
7cac9316 | 533 | let kill_scope = path.loan_path.kill_scope(bccx); |
c34b1796 | 534 | let path = *self.path_map.borrow().get(&path.loan_path).unwrap(); |
7cac9316 | 535 | self.kill_moves(path, kill_scope.node_id(), |
9346a6ac | 536 | KillFrom::ScopeEnd, dfcx_moves); |
1a4d82fc JJ |
537 | } |
538 | LpExtend(..) => {} | |
539 | } | |
540 | } | |
541 | ||
542 | // Kill all assignments when the variable goes out of scope: | |
543 | for (assignment_index, assignment) in | |
544 | self.var_assignments.borrow().iter().enumerate() { | |
545 | let lp = self.path_loan_path(assignment.path); | |
546 | match lp.kind { | |
547 | LpVar(..) | LpUpvar(..) | LpDowncast(..) => { | |
7cac9316 | 548 | let kill_scope = lp.kill_scope(bccx); |
9346a6ac | 549 | dfcx_assign.add_kill(KillFrom::ScopeEnd, |
7cac9316 | 550 | kill_scope.node_id(), |
9346a6ac | 551 | assignment_index); |
1a4d82fc JJ |
552 | } |
553 | LpExtend(..) => { | |
54a0048b | 554 | bug!("var assignment for non var path"); |
1a4d82fc JJ |
555 | } |
556 | } | |
557 | } | |
558 | } | |
559 | ||
560 | fn each_base_path<F>(&self, index: MovePathIndex, mut f: F) -> bool where | |
561 | F: FnMut(MovePathIndex) -> bool, | |
562 | { | |
563 | let mut p = index; | |
564 | while p != InvalidMovePathIndex { | |
565 | if !f(p) { | |
566 | return false; | |
567 | } | |
568 | p = self.path_parent(p); | |
569 | } | |
570 | return true; | |
571 | } | |
572 | ||
573 | // FIXME(#19596) This is a workaround, but there should be better way to do this | |
574 | fn each_extending_path_<F>(&self, index: MovePathIndex, f: &mut F) -> bool where | |
575 | F: FnMut(MovePathIndex) -> bool, | |
576 | { | |
577 | if !(*f)(index) { | |
578 | return false; | |
579 | } | |
580 | ||
581 | let mut p = self.path_first_child(index); | |
582 | while p != InvalidMovePathIndex { | |
583 | if !self.each_extending_path_(p, f) { | |
584 | return false; | |
585 | } | |
586 | p = self.path_next_sibling(p); | |
587 | } | |
588 | ||
589 | return true; | |
590 | } | |
591 | ||
592 | fn each_extending_path<F>(&self, index: MovePathIndex, mut f: F) -> bool where | |
593 | F: FnMut(MovePathIndex) -> bool, | |
594 | { | |
595 | self.each_extending_path_(index, &mut f) | |
596 | } | |
597 | ||
598 | fn each_applicable_move<F>(&self, index0: MovePathIndex, mut f: F) -> bool where | |
599 | F: FnMut(MoveIndex) -> bool, | |
600 | { | |
601 | let mut ret = true; | |
602 | self.each_extending_path(index0, |index| { | |
603 | let mut p = self.path_first_move(index); | |
604 | while p != InvalidMoveIndex { | |
605 | if !f(p) { | |
606 | ret = false; | |
607 | break; | |
608 | } | |
609 | p = self.move_next_move(p); | |
610 | } | |
611 | ret | |
612 | }); | |
613 | ret | |
614 | } | |
615 | ||
616 | fn kill_moves(&self, | |
617 | path: MovePathIndex, | |
618 | kill_id: ast::NodeId, | |
9346a6ac | 619 | kill_kind: KillFrom, |
1a4d82fc JJ |
620 | dfcx_moves: &mut MoveDataFlow) { |
621 | // We can only perform kills for paths that refer to a unique location, | |
622 | // since otherwise we may kill a move from one location with an | |
623 | // assignment referring to another location. | |
624 | ||
625 | let loan_path = self.path_loan_path(path); | |
7453a54e | 626 | if loan_path_is_precise(&loan_path) { |
1a4d82fc | 627 | self.each_applicable_move(path, |move_index| { |
9346a6ac AL |
628 | debug!("kill_moves add_kill {:?} kill_id={} move_index={}", |
629 | kill_kind, kill_id, move_index.get()); | |
630 | dfcx_moves.add_kill(kill_kind, kill_id, move_index.get()); | |
1a4d82fc JJ |
631 | true |
632 | }); | |
633 | } | |
634 | } | |
635 | } | |
636 | ||
637 | impl<'a, 'tcx> FlowedMoveData<'a, 'tcx> { | |
638 | pub fn new(move_data: MoveData<'tcx>, | |
7cac9316 | 639 | bccx: &BorrowckCtxt<'a, 'tcx>, |
1a4d82fc | 640 | cfg: &cfg::CFG, |
54a0048b | 641 | id_range: IdRange, |
32a655c1 | 642 | body: &hir::Body) |
1a4d82fc | 643 | -> FlowedMoveData<'a, 'tcx> { |
7cac9316 XL |
644 | let tcx = bccx.tcx; |
645 | ||
1a4d82fc JJ |
646 | let mut dfcx_moves = |
647 | DataFlowContext::new(tcx, | |
648 | "flowed_move_data_moves", | |
32a655c1 | 649 | Some(body), |
1a4d82fc JJ |
650 | cfg, |
651 | MoveDataFlowOperator, | |
652 | id_range, | |
653 | move_data.moves.borrow().len()); | |
654 | let mut dfcx_assign = | |
655 | DataFlowContext::new(tcx, | |
656 | "flowed_move_data_assigns", | |
32a655c1 | 657 | Some(body), |
1a4d82fc JJ |
658 | cfg, |
659 | AssignDataFlowOperator, | |
660 | id_range, | |
661 | move_data.var_assignments.borrow().len()); | |
662 | ||
7cac9316 | 663 | move_data.add_gen_kills(bccx, |
1a4d82fc JJ |
664 | &mut dfcx_moves, |
665 | &mut dfcx_assign); | |
666 | ||
667 | dfcx_moves.add_kills_from_flow_exits(cfg); | |
668 | dfcx_assign.add_kills_from_flow_exits(cfg); | |
669 | ||
670 | dfcx_moves.propagate(cfg, body); | |
671 | dfcx_assign.propagate(cfg, body); | |
672 | ||
673 | FlowedMoveData { | |
674 | move_data: move_data, | |
675 | dfcx_moves: dfcx_moves, | |
676 | dfcx_assign: dfcx_assign, | |
677 | } | |
678 | } | |
679 | ||
680 | pub fn kind_of_move_of_path(&self, | |
681 | id: ast::NodeId, | |
682 | loan_path: &Rc<LoanPath<'tcx>>) | |
683 | -> Option<MoveKind> { | |
684 | //! Returns the kind of a move of `loan_path` by `id`, if one exists. | |
685 | ||
686 | let mut ret = None; | |
85aaf69f | 687 | if let Some(loan_path_index) = self.move_data.path_map.borrow().get(&*loan_path) { |
1a4d82fc JJ |
688 | self.dfcx_moves.each_gen_bit(id, |move_index| { |
689 | let the_move = self.move_data.moves.borrow(); | |
690 | let the_move = (*the_move)[move_index]; | |
85aaf69f | 691 | if the_move.path == *loan_path_index { |
1a4d82fc JJ |
692 | ret = Some(the_move.kind); |
693 | false | |
694 | } else { | |
695 | true | |
696 | } | |
697 | }); | |
698 | } | |
699 | ret | |
700 | } | |
701 | ||
702 | /// Iterates through each move of `loan_path` (or some base path of `loan_path`) that *may* | |
703 | /// have occurred on entry to `id` without an intervening assignment. In other words, any moves | |
704 | /// that would invalidate a reference to `loan_path` at location `id`. | |
705 | pub fn each_move_of<F>(&self, | |
706 | id: ast::NodeId, | |
707 | loan_path: &Rc<LoanPath<'tcx>>, | |
708 | mut f: F) | |
709 | -> bool where | |
710 | F: FnMut(&Move, &LoanPath<'tcx>) -> bool, | |
711 | { | |
712 | // Bad scenarios: | |
713 | // | |
714 | // 1. Move of `a.b.c`, use of `a.b.c` | |
715 | // 2. Move of `a.b.c`, use of `a.b.c.d` | |
716 | // 3. Move of `a.b.c`, use of `a` or `a.b` | |
717 | // | |
718 | // OK scenario: | |
719 | // | |
720 | // 4. move of `a.b.c`, use of `a.b.d` | |
721 | ||
722 | let base_indices = self.move_data.existing_base_paths(loan_path); | |
723 | if base_indices.is_empty() { | |
724 | return true; | |
725 | } | |
726 | ||
727 | let opt_loan_path_index = self.move_data.existing_move_path(loan_path); | |
728 | ||
729 | let mut ret = true; | |
730 | ||
731 | self.dfcx_moves.each_bit_on_entry(id, |index| { | |
732 | let the_move = self.move_data.moves.borrow(); | |
733 | let the_move = &(*the_move)[index]; | |
734 | let moved_path = the_move.path; | |
735 | if base_indices.iter().any(|x| x == &moved_path) { | |
736 | // Scenario 1 or 2: `loan_path` or some base path of | |
737 | // `loan_path` was moved. | |
7453a54e | 738 | if !f(the_move, &self.move_data.path_loan_path(moved_path)) { |
1a4d82fc JJ |
739 | ret = false; |
740 | } | |
741 | } else { | |
85aaf69f | 742 | if let Some(loan_path_index) = opt_loan_path_index { |
1a4d82fc JJ |
743 | let cont = self.move_data.each_base_path(moved_path, |p| { |
744 | if p == loan_path_index { | |
745 | // Scenario 3: some extension of `loan_path` | |
746 | // was moved | |
747 | f(the_move, | |
7453a54e | 748 | &self.move_data.path_loan_path(moved_path)) |
1a4d82fc JJ |
749 | } else { |
750 | true | |
751 | } | |
752 | }); | |
85aaf69f | 753 | if !cont { ret = false; } |
1a4d82fc JJ |
754 | } |
755 | } | |
756 | ret | |
757 | }) | |
758 | } | |
759 | ||
760 | /// Iterates through every assignment to `loan_path` that may have occurred on entry to `id`. | |
761 | /// `loan_path` must be a single variable. | |
762 | pub fn each_assignment_of<F>(&self, | |
763 | id: ast::NodeId, | |
764 | loan_path: &Rc<LoanPath<'tcx>>, | |
765 | mut f: F) | |
766 | -> bool where | |
767 | F: FnMut(&Assignment) -> bool, | |
768 | { | |
769 | let loan_path_index = { | |
770 | match self.move_data.existing_move_path(loan_path) { | |
771 | Some(i) => i, | |
772 | None => { | |
773 | // if there were any assignments, it'd have an index | |
774 | return true; | |
775 | } | |
776 | } | |
777 | }; | |
778 | ||
779 | self.dfcx_assign.each_bit_on_entry(id, |index| { | |
780 | let assignment = self.move_data.var_assignments.borrow(); | |
781 | let assignment = &(*assignment)[index]; | |
782 | if assignment.path == loan_path_index && !f(assignment) { | |
783 | false | |
784 | } else { | |
785 | true | |
786 | } | |
787 | }) | |
788 | } | |
789 | } | |
790 | ||
791 | impl BitwiseOperator for MoveDataFlowOperator { | |
792 | #[inline] | |
c34b1796 | 793 | fn join(&self, succ: usize, pred: usize) -> usize { |
1a4d82fc JJ |
794 | succ | pred // moves from both preds are in scope |
795 | } | |
796 | } | |
797 | ||
798 | impl DataFlowOperator for MoveDataFlowOperator { | |
799 | #[inline] | |
800 | fn initial_value(&self) -> bool { | |
801 | false // no loans in scope by default | |
802 | } | |
803 | } | |
804 | ||
805 | impl BitwiseOperator for AssignDataFlowOperator { | |
806 | #[inline] | |
c34b1796 | 807 | fn join(&self, succ: usize, pred: usize) -> usize { |
1a4d82fc JJ |
808 | succ | pred // moves from both preds are in scope |
809 | } | |
810 | } | |
811 | ||
812 | impl DataFlowOperator for AssignDataFlowOperator { | |
813 | #[inline] | |
814 | fn initial_value(&self) -> bool { | |
815 | false // no assignments in scope by default | |
816 | } | |
817 | } |