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