]>
Commit | Line | Data |
---|---|---|
3b2f2976 XL |
1 | // Copyright 2017 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 | use rustc::ty::{self, TyCtxt}; | |
12 | use rustc::mir::*; | |
13 | use rustc::mir::tcx::RvalueInitializationState; | |
14 | use rustc::util::nodemap::FxHashMap; | |
15 | use rustc_data_structures::indexed_vec::{IndexVec}; | |
16 | ||
3b2f2976 XL |
17 | use std::collections::hash_map::Entry; |
18 | use std::mem; | |
19 | ||
20 | use super::abs_domain::Lift; | |
21 | ||
22 | use super::{LocationMap, MoveData, MovePath, MovePathLookup, MovePathIndex, MoveOut, MoveOutIndex}; | |
ff7c6d11 | 23 | use super::{MoveError, InitIndex, Init, LookupResult, InitKind}; |
ea8adc8c | 24 | use super::IllegalMoveOriginKind::*; |
3b2f2976 | 25 | |
abe05a73 | 26 | struct MoveDataBuilder<'a, 'gcx: 'tcx, 'tcx: 'a> { |
3b2f2976 | 27 | mir: &'a Mir<'tcx>, |
abe05a73 | 28 | tcx: TyCtxt<'a, 'gcx, 'tcx>, |
3b2f2976 | 29 | data: MoveData<'tcx>, |
ea8adc8c | 30 | errors: Vec<MoveError<'tcx>>, |
3b2f2976 XL |
31 | } |
32 | ||
abe05a73 | 33 | impl<'a, 'gcx, 'tcx> MoveDataBuilder<'a, 'gcx, 'tcx> { |
ff7c6d11 | 34 | fn new(mir: &'a Mir<'tcx>, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Self { |
3b2f2976 XL |
35 | let mut move_paths = IndexVec::new(); |
36 | let mut path_map = IndexVec::new(); | |
ff7c6d11 | 37 | let mut init_path_map = IndexVec::new(); |
3b2f2976 XL |
38 | |
39 | MoveDataBuilder { | |
40 | mir, | |
41 | tcx, | |
ea8adc8c | 42 | errors: Vec::new(), |
3b2f2976 XL |
43 | data: MoveData { |
44 | moves: IndexVec::new(), | |
45 | loc_map: LocationMap::new(mir), | |
46 | rev_lookup: MovePathLookup { | |
ff7c6d11 XL |
47 | locals: mir.local_decls.indices().map(Place::Local).map(|v| { |
48 | Self::new_move_path( | |
49 | &mut move_paths, | |
50 | &mut path_map, | |
51 | &mut init_path_map, | |
52 | None, | |
53 | v, | |
54 | ) | |
3b2f2976 XL |
55 | }).collect(), |
56 | projections: FxHashMap(), | |
57 | }, | |
58 | move_paths, | |
59 | path_map, | |
ff7c6d11 XL |
60 | inits: IndexVec::new(), |
61 | init_loc_map: LocationMap::new(mir), | |
62 | init_path_map, | |
3b2f2976 XL |
63 | } |
64 | } | |
65 | } | |
66 | ||
67 | fn new_move_path(move_paths: &mut IndexVec<MovePathIndex, MovePath<'tcx>>, | |
68 | path_map: &mut IndexVec<MovePathIndex, Vec<MoveOutIndex>>, | |
ff7c6d11 | 69 | init_path_map: &mut IndexVec<MovePathIndex, Vec<InitIndex>>, |
3b2f2976 | 70 | parent: Option<MovePathIndex>, |
ff7c6d11 | 71 | place: Place<'tcx>) |
3b2f2976 XL |
72 | -> MovePathIndex |
73 | { | |
74 | let move_path = move_paths.push(MovePath { | |
75 | next_sibling: None, | |
76 | first_child: None, | |
77 | parent, | |
ff7c6d11 | 78 | place, |
3b2f2976 XL |
79 | }); |
80 | ||
81 | if let Some(parent) = parent { | |
82 | let next_sibling = | |
83 | mem::replace(&mut move_paths[parent].first_child, Some(move_path)); | |
84 | move_paths[move_path].next_sibling = next_sibling; | |
85 | } | |
86 | ||
87 | let path_map_ent = path_map.push(vec![]); | |
88 | assert_eq!(path_map_ent, move_path); | |
ff7c6d11 XL |
89 | |
90 | let init_path_map_ent = init_path_map.push(vec![]); | |
91 | assert_eq!(init_path_map_ent, move_path); | |
92 | ||
3b2f2976 XL |
93 | move_path |
94 | } | |
ea8adc8c | 95 | } |
3b2f2976 | 96 | |
abe05a73 | 97 | impl<'b, 'a, 'gcx, 'tcx> Gatherer<'b, 'a, 'gcx, 'tcx> { |
ff7c6d11 XL |
98 | /// This creates a MovePath for a given place, returning an `MovePathError` |
99 | /// if that place can't be moved from. | |
3b2f2976 | 100 | /// |
ff7c6d11 | 101 | /// NOTE: places behind references *do not* get a move path, which is |
3b2f2976 XL |
102 | /// problematic for borrowck. |
103 | /// | |
104 | /// Maybe we should have separate "borrowck" and "moveck" modes. | |
ff7c6d11 | 105 | fn move_path_for(&mut self, place: &Place<'tcx>) |
ea8adc8c | 106 | -> Result<MovePathIndex, MoveError<'tcx>> |
3b2f2976 | 107 | { |
ff7c6d11 XL |
108 | debug!("lookup({:?})", place); |
109 | match *place { | |
110 | Place::Local(local) => Ok(self.builder.data.rev_lookup.locals[local]), | |
111 | Place::Static(..) => { | |
ea8adc8c XL |
112 | let span = self.builder.mir.source_info(self.loc).span; |
113 | Err(MoveError::cannot_move_out_of(span, Static)) | |
114 | } | |
ff7c6d11 XL |
115 | Place::Projection(ref proj) => { |
116 | self.move_path_for_projection(place, proj) | |
3b2f2976 XL |
117 | } |
118 | } | |
119 | } | |
120 | ||
ff7c6d11 | 121 | fn create_move_path(&mut self, place: &Place<'tcx>) { |
3b2f2976 XL |
122 | // This is an assignment, not a move, so this not being a valid |
123 | // move path is OK. | |
ff7c6d11 | 124 | let _ = self.move_path_for(place); |
3b2f2976 XL |
125 | } |
126 | ||
127 | fn move_path_for_projection(&mut self, | |
ff7c6d11 XL |
128 | place: &Place<'tcx>, |
129 | proj: &PlaceProjection<'tcx>) | |
ea8adc8c | 130 | -> Result<MovePathIndex, MoveError<'tcx>> |
3b2f2976 XL |
131 | { |
132 | let base = try!(self.move_path_for(&proj.base)); | |
ea8adc8c XL |
133 | let mir = self.builder.mir; |
134 | let tcx = self.builder.tcx; | |
ff7c6d11 XL |
135 | let place_ty = proj.base.ty(mir, tcx).to_ty(tcx); |
136 | match place_ty.sty { | |
ea8adc8c XL |
137 | ty::TyRef(..) | ty::TyRawPtr(..) => |
138 | return Err(MoveError::cannot_move_out_of(mir.source_info(self.loc).span, | |
139 | BorrowedContent)), | |
140 | ty::TyAdt(adt, _) if adt.has_dtor(tcx) && !adt.is_box() => | |
141 | return Err(MoveError::cannot_move_out_of(mir.source_info(self.loc).span, | |
142 | InteriorOfTypeWithDestructor { | |
ff7c6d11 | 143 | container_ty: place_ty |
ea8adc8c | 144 | })), |
3b2f2976 XL |
145 | // move out of union - always move the entire union |
146 | ty::TyAdt(adt, _) if adt.is_union() => | |
ea8adc8c | 147 | return Err(MoveError::UnionMove { path: base }), |
abe05a73 | 148 | ty::TySlice(_) => |
ea8adc8c XL |
149 | return Err(MoveError::cannot_move_out_of( |
150 | mir.source_info(self.loc).span, | |
abe05a73 | 151 | InteriorOfSliceOrArray { |
ff7c6d11 | 152 | ty: place_ty, is_index: match proj.elem { |
ea8adc8c XL |
153 | ProjectionElem::Index(..) => true, |
154 | _ => false | |
155 | }, | |
156 | })), | |
abe05a73 | 157 | ty::TyArray(..) => match proj.elem { |
ea8adc8c XL |
158 | ProjectionElem::Index(..) => |
159 | return Err(MoveError::cannot_move_out_of( | |
160 | mir.source_info(self.loc).span, | |
abe05a73 | 161 | InteriorOfSliceOrArray { |
ff7c6d11 | 162 | ty: place_ty, is_index: true |
ea8adc8c | 163 | })), |
3b2f2976 XL |
164 | _ => { |
165 | // FIXME: still badly broken | |
166 | } | |
167 | }, | |
168 | _ => {} | |
169 | }; | |
ea8adc8c | 170 | match self.builder.data.rev_lookup.projections.entry((base, proj.elem.lift())) { |
3b2f2976 XL |
171 | Entry::Occupied(ent) => Ok(*ent.get()), |
172 | Entry::Vacant(ent) => { | |
ea8adc8c XL |
173 | let path = MoveDataBuilder::new_move_path( |
174 | &mut self.builder.data.move_paths, | |
175 | &mut self.builder.data.path_map, | |
ff7c6d11 | 176 | &mut self.builder.data.init_path_map, |
3b2f2976 | 177 | Some(base), |
ff7c6d11 | 178 | place.clone() |
3b2f2976 XL |
179 | ); |
180 | ent.insert(path); | |
181 | Ok(path) | |
182 | } | |
183 | } | |
184 | } | |
ea8adc8c | 185 | } |
3b2f2976 | 186 | |
abe05a73 | 187 | impl<'a, 'gcx, 'tcx> MoveDataBuilder<'a, 'gcx, 'tcx> { |
ea8adc8c | 188 | fn finalize(self) -> Result<MoveData<'tcx>, (MoveData<'tcx>, Vec<MoveError<'tcx>>)> { |
3b2f2976 XL |
189 | debug!("{}", { |
190 | debug!("moves for {:?}:", self.mir.span); | |
191 | for (j, mo) in self.data.moves.iter_enumerated() { | |
192 | debug!(" {:?} = {:?}", j, mo); | |
193 | } | |
194 | debug!("move paths for {:?}:", self.mir.span); | |
195 | for (j, path) in self.data.move_paths.iter_enumerated() { | |
196 | debug!(" {:?} = {:?}", j, path); | |
197 | } | |
198 | "done dumping moves" | |
199 | }); | |
ea8adc8c XL |
200 | |
201 | if self.errors.len() > 0 { | |
202 | Err((self.data, self.errors)) | |
203 | } else { | |
204 | Ok(self.data) | |
205 | } | |
3b2f2976 XL |
206 | } |
207 | } | |
208 | ||
ff7c6d11 | 209 | pub(super) fn gather_moves<'a, 'gcx, 'tcx>(mir: &Mir<'tcx>, tcx: TyCtxt<'a, 'gcx, 'tcx>) |
abe05a73 XL |
210 | -> Result<MoveData<'tcx>, |
211 | (MoveData<'tcx>, Vec<MoveError<'tcx>>)> { | |
ff7c6d11 XL |
212 | let mut builder = MoveDataBuilder::new(mir, tcx); |
213 | ||
214 | builder.gather_args(); | |
3b2f2976 XL |
215 | |
216 | for (bb, block) in mir.basic_blocks().iter_enumerated() { | |
217 | for (i, stmt) in block.statements.iter().enumerate() { | |
218 | let source = Location { block: bb, statement_index: i }; | |
219 | builder.gather_statement(source, stmt); | |
220 | } | |
221 | ||
222 | let terminator_loc = Location { | |
223 | block: bb, | |
224 | statement_index: block.statements.len() | |
225 | }; | |
226 | builder.gather_terminator(terminator_loc, block.terminator()); | |
227 | } | |
228 | ||
229 | builder.finalize() | |
230 | } | |
231 | ||
abe05a73 | 232 | impl<'a, 'gcx, 'tcx> MoveDataBuilder<'a, 'gcx, 'tcx> { |
ff7c6d11 XL |
233 | fn gather_args(&mut self) { |
234 | for arg in self.mir.args_iter() { | |
235 | let path = self.data.rev_lookup.locals[arg]; | |
236 | let span = self.mir.local_decls[arg].source_info.span; | |
237 | ||
238 | let init = self.data.inits.push(Init { | |
239 | path, span, kind: InitKind::Deep | |
240 | }); | |
241 | ||
242 | debug!("gather_args: adding init {:?} of {:?} for argument {:?}", | |
243 | init, path, arg); | |
244 | ||
245 | self.data.init_path_map[path].push(init); | |
246 | } | |
247 | } | |
248 | ||
3b2f2976 XL |
249 | fn gather_statement(&mut self, loc: Location, stmt: &Statement<'tcx>) { |
250 | debug!("gather_statement({:?}, {:?})", loc, stmt); | |
ea8adc8c XL |
251 | (Gatherer { builder: self, loc }).gather_statement(stmt); |
252 | } | |
253 | ||
254 | fn gather_terminator(&mut self, loc: Location, term: &Terminator<'tcx>) { | |
255 | debug!("gather_terminator({:?}, {:?})", loc, term); | |
256 | (Gatherer { builder: self, loc }).gather_terminator(term); | |
257 | } | |
258 | } | |
259 | ||
abe05a73 XL |
260 | struct Gatherer<'b, 'a: 'b, 'gcx: 'tcx, 'tcx: 'a> { |
261 | builder: &'b mut MoveDataBuilder<'a, 'gcx, 'tcx>, | |
ea8adc8c XL |
262 | loc: Location, |
263 | } | |
264 | ||
abe05a73 | 265 | impl<'b, 'a, 'gcx, 'tcx> Gatherer<'b, 'a, 'gcx, 'tcx> { |
ea8adc8c | 266 | fn gather_statement(&mut self, stmt: &Statement<'tcx>) { |
3b2f2976 | 267 | match stmt.kind { |
ff7c6d11 XL |
268 | StatementKind::Assign(ref place, ref rval) => { |
269 | self.create_move_path(place); | |
3b2f2976 XL |
270 | if let RvalueInitializationState::Shallow = rval.initialization_state() { |
271 | // Box starts out uninitialized - need to create a separate | |
272 | // move-path for the interior so it will be separate from | |
273 | // the exterior. | |
ff7c6d11 XL |
274 | self.create_move_path(&place.clone().deref()); |
275 | self.gather_init(place, InitKind::Shallow); | |
276 | } else { | |
277 | self.gather_init(place, InitKind::Deep); | |
3b2f2976 | 278 | } |
ea8adc8c | 279 | self.gather_rvalue(rval); |
3b2f2976 | 280 | } |
ff7c6d11 XL |
281 | StatementKind::InlineAsm { ref outputs, ref inputs, ref asm } => { |
282 | for (output, kind) in outputs.iter().zip(&asm.outputs) { | |
283 | if !kind.is_indirect { | |
284 | self.gather_init(output, InitKind::Deep); | |
285 | } | |
286 | } | |
287 | for input in inputs { | |
288 | self.gather_operand(input); | |
289 | } | |
290 | } | |
abe05a73 XL |
291 | StatementKind::StorageLive(_) => {} |
292 | StatementKind::StorageDead(local) => { | |
ff7c6d11 | 293 | self.gather_move(&Place::Local(local)); |
abe05a73 | 294 | } |
3b2f2976 XL |
295 | StatementKind::SetDiscriminant{ .. } => { |
296 | span_bug!(stmt.source_info.span, | |
297 | "SetDiscriminant should not exist during borrowck"); | |
298 | } | |
3b2f2976 XL |
299 | StatementKind::EndRegion(_) | |
300 | StatementKind::Validate(..) | | |
301 | StatementKind::Nop => {} | |
302 | } | |
303 | } | |
304 | ||
ea8adc8c | 305 | fn gather_rvalue(&mut self, rvalue: &Rvalue<'tcx>) { |
3b2f2976 XL |
306 | match *rvalue { |
307 | Rvalue::Use(ref operand) | | |
308 | Rvalue::Repeat(ref operand, _) | | |
309 | Rvalue::Cast(_, ref operand, _) | | |
310 | Rvalue::UnaryOp(_, ref operand) => { | |
ea8adc8c | 311 | self.gather_operand(operand) |
3b2f2976 XL |
312 | } |
313 | Rvalue::BinaryOp(ref _binop, ref lhs, ref rhs) | | |
314 | Rvalue::CheckedBinaryOp(ref _binop, ref lhs, ref rhs) => { | |
ea8adc8c XL |
315 | self.gather_operand(lhs); |
316 | self.gather_operand(rhs); | |
3b2f2976 XL |
317 | } |
318 | Rvalue::Aggregate(ref _kind, ref operands) => { | |
319 | for operand in operands { | |
ea8adc8c | 320 | self.gather_operand(operand); |
3b2f2976 XL |
321 | } |
322 | } | |
323 | Rvalue::Ref(..) | | |
324 | Rvalue::Discriminant(..) | | |
325 | Rvalue::Len(..) | | |
326 | Rvalue::NullaryOp(NullOp::SizeOf, _) | | |
327 | Rvalue::NullaryOp(NullOp::Box, _) => { | |
328 | // This returns an rvalue with uninitialized contents. We can't | |
329 | // move out of it here because it is an rvalue - assignments always | |
ff7c6d11 | 330 | // completely initialize their place. |
3b2f2976 XL |
331 | // |
332 | // However, this does not matter - MIR building is careful to | |
333 | // only emit a shallow free for the partially-initialized | |
334 | // temporary. | |
335 | // | |
336 | // In any case, if we want to fix this, we have to register a | |
337 | // special move and change the `statement_effect` functions. | |
338 | } | |
339 | } | |
340 | } | |
341 | ||
ea8adc8c | 342 | fn gather_terminator(&mut self, term: &Terminator<'tcx>) { |
3b2f2976 XL |
343 | match term.kind { |
344 | TerminatorKind::Goto { target: _ } | | |
345 | TerminatorKind::Resume | | |
ff7c6d11 | 346 | TerminatorKind::Abort | |
ea8adc8c | 347 | TerminatorKind::GeneratorDrop | |
abe05a73 | 348 | TerminatorKind::FalseEdges { .. } | |
2c00a5a8 | 349 | TerminatorKind::FalseUnwind { .. } | |
3b2f2976 XL |
350 | TerminatorKind::Unreachable => { } |
351 | ||
352 | TerminatorKind::Return => { | |
ff7c6d11 | 353 | self.gather_move(&Place::Local(RETURN_PLACE)); |
3b2f2976 XL |
354 | } |
355 | ||
356 | TerminatorKind::Assert { .. } | | |
357 | TerminatorKind::SwitchInt { .. } => { | |
358 | // branching terminators - these don't move anything | |
359 | } | |
360 | ||
ea8adc8c XL |
361 | TerminatorKind::Yield { ref value, .. } => { |
362 | self.gather_operand(value); | |
363 | } | |
364 | ||
3b2f2976 | 365 | TerminatorKind::Drop { ref location, target: _, unwind: _ } => { |
ff7c6d11 | 366 | self.gather_move(location); |
3b2f2976 XL |
367 | } |
368 | TerminatorKind::DropAndReplace { ref location, ref value, .. } => { | |
369 | self.create_move_path(location); | |
ea8adc8c | 370 | self.gather_operand(value); |
ff7c6d11 | 371 | self.gather_init(location, InitKind::Deep); |
3b2f2976 XL |
372 | } |
373 | TerminatorKind::Call { ref func, ref args, ref destination, cleanup: _ } => { | |
ea8adc8c | 374 | self.gather_operand(func); |
3b2f2976 | 375 | for arg in args { |
ea8adc8c | 376 | self.gather_operand(arg); |
3b2f2976 XL |
377 | } |
378 | if let Some((ref destination, _bb)) = *destination { | |
379 | self.create_move_path(destination); | |
ff7c6d11 | 380 | self.gather_init(destination, InitKind::NonPanicPathOnly); |
3b2f2976 XL |
381 | } |
382 | } | |
383 | } | |
384 | } | |
385 | ||
ea8adc8c | 386 | fn gather_operand(&mut self, operand: &Operand<'tcx>) { |
3b2f2976 | 387 | match *operand { |
ff7c6d11 XL |
388 | Operand::Constant(..) | |
389 | Operand::Copy(..) => {} // not-a-move | |
390 | Operand::Move(ref place) => { // a move | |
391 | self.gather_move(place); | |
3b2f2976 XL |
392 | } |
393 | } | |
394 | } | |
395 | ||
ff7c6d11 XL |
396 | fn gather_move(&mut self, place: &Place<'tcx>) { |
397 | debug!("gather_move({:?}, {:?})", self.loc, place); | |
3b2f2976 | 398 | |
ff7c6d11 | 399 | let path = match self.move_path_for(place) { |
ea8adc8c XL |
400 | Ok(path) | Err(MoveError::UnionMove { path }) => path, |
401 | Err(error @ MoveError::IllegalMove { .. }) => { | |
402 | self.builder.errors.push(error); | |
403 | return; | |
3b2f2976 XL |
404 | } |
405 | }; | |
ea8adc8c | 406 | let move_out = self.builder.data.moves.push(MoveOut { path: path, source: self.loc }); |
3b2f2976 XL |
407 | |
408 | debug!("gather_move({:?}, {:?}): adding move {:?} of {:?}", | |
ff7c6d11 | 409 | self.loc, place, move_out, path); |
3b2f2976 | 410 | |
ea8adc8c XL |
411 | self.builder.data.path_map[path].push(move_out); |
412 | self.builder.data.loc_map[self.loc].push(move_out); | |
3b2f2976 | 413 | } |
ff7c6d11 XL |
414 | |
415 | fn gather_init(&mut self, place: &Place<'tcx>, kind: InitKind) { | |
416 | debug!("gather_init({:?}, {:?})", self.loc, place); | |
417 | ||
418 | if let LookupResult::Exact(path) = self.builder.data.rev_lookup.find(place) { | |
419 | let init = self.builder.data.inits.push(Init { | |
420 | span: self.builder.mir.source_info(self.loc).span, | |
421 | path, | |
422 | kind, | |
423 | }); | |
424 | ||
425 | debug!("gather_init({:?}, {:?}): adding init {:?} of {:?}", | |
426 | self.loc, place, init, path); | |
427 | ||
428 | self.builder.data.init_path_map[path].push(init); | |
429 | self.builder.data.init_loc_map[self.loc].push(init); | |
430 | } | |
431 | } | |
3b2f2976 | 432 | } |