]>
Commit | Line | Data |
---|---|---|
54a0048b SL |
1 | // Copyright 2012-2016 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 borrowck::BorrowckCtxt; | |
12 | ||
3157f602 | 13 | use syntax::ast::{self, MetaItem}; |
3157f602 XL |
14 | use syntax::ptr::P; |
15 | use syntax_pos::{Span, DUMMY_SP}; | |
54a0048b SL |
16 | |
17 | use rustc::hir; | |
18 | use rustc::hir::intravisit::{FnKind}; | |
19 | ||
c30ab7b3 | 20 | use rustc::mir::{self, BasicBlock, BasicBlockData, Mir, Statement, Terminator, Location}; |
3157f602 XL |
21 | use rustc::session::Session; |
22 | use rustc::ty::{self, TyCtxt}; | |
54a0048b SL |
23 | |
24 | mod abs_domain; | |
3157f602 | 25 | pub mod elaborate_drops; |
54a0048b SL |
26 | mod dataflow; |
27 | mod gather_moves; | |
3157f602 XL |
28 | mod patch; |
29 | // mod graphviz; | |
54a0048b | 30 | |
3157f602 XL |
31 | use self::dataflow::{BitDenotation}; |
32 | use self::dataflow::{DataflowOperator}; | |
33 | use self::dataflow::{Dataflow, DataflowAnalysis, DataflowResults}; | |
34 | use self::dataflow::{MaybeInitializedLvals, MaybeUninitializedLvals}; | |
35 | use self::dataflow::{DefinitelyInitializedLvals}; | |
9e0c209e | 36 | use self::gather_moves::{MoveData, MovePathIndex, LookupResult}; |
54a0048b | 37 | |
3157f602 XL |
38 | fn has_rustc_mir_with(attrs: &[ast::Attribute], name: &str) -> Option<P<MetaItem>> { |
39 | for attr in attrs { | |
40 | if attr.check_name("rustc_mir") { | |
41 | let items = attr.meta_item_list(); | |
42 | for item in items.iter().flat_map(|l| l.iter()) { | |
9e0c209e SL |
43 | match item.meta_item() { |
44 | Some(mi) if mi.check_name(name) => return Some(mi.clone()), | |
45 | _ => continue | |
3157f602 XL |
46 | } |
47 | } | |
48 | } | |
49 | } | |
50 | return None; | |
51 | } | |
52 | ||
53 | pub struct MoveDataParamEnv<'tcx> { | |
54 | move_data: MoveData<'tcx>, | |
55 | param_env: ty::ParameterEnvironment<'tcx>, | |
56 | } | |
57 | ||
c30ab7b3 SL |
58 | pub fn borrowck_mir(bcx: &mut BorrowckCtxt, |
59 | fk: FnKind, | |
60 | _decl: &hir::FnDecl, | |
61 | body: &hir::Block, | |
62 | _sp: Span, | |
63 | id: ast::NodeId, | |
64 | attributes: &[ast::Attribute]) { | |
54a0048b | 65 | match fk { |
9e0c209e SL |
66 | FnKind::ItemFn(name, ..) | |
67 | FnKind::Method(name, ..) => { | |
54a0048b SL |
68 | debug!("borrowck_mir({}) UNIMPLEMENTED", name); |
69 | } | |
70 | FnKind::Closure(_) => { | |
71 | debug!("borrowck_mir closure (body.id={}) UNIMPLEMENTED", body.id); | |
72 | } | |
73 | } | |
74 | ||
3157f602 | 75 | let tcx = bcx.tcx; |
3157f602 | 76 | let param_env = ty::ParameterEnvironment::for_item(tcx, id); |
c30ab7b3 SL |
77 | |
78 | let mir = &tcx.item_mir(tcx.map.local_def_id(id)); | |
79 | ||
9e0c209e | 80 | let move_data = MoveData::gather_moves(mir, tcx, ¶m_env); |
3157f602 XL |
81 | let mdpe = MoveDataParamEnv { move_data: move_data, param_env: param_env }; |
82 | let flow_inits = | |
83 | do_dataflow(tcx, mir, id, attributes, &mdpe, MaybeInitializedLvals::new(tcx, mir)); | |
84 | let flow_uninits = | |
85 | do_dataflow(tcx, mir, id, attributes, &mdpe, MaybeUninitializedLvals::new(tcx, mir)); | |
86 | let flow_def_inits = | |
87 | do_dataflow(tcx, mir, id, attributes, &mdpe, DefinitelyInitializedLvals::new(tcx, mir)); | |
88 | ||
89 | if has_rustc_mir_with(attributes, "rustc_peek_maybe_init").is_some() { | |
90 | dataflow::sanity_check_via_rustc_peek(bcx.tcx, mir, id, attributes, &mdpe, &flow_inits); | |
91 | } | |
92 | if has_rustc_mir_with(attributes, "rustc_peek_maybe_uninit").is_some() { | |
93 | dataflow::sanity_check_via_rustc_peek(bcx.tcx, mir, id, attributes, &mdpe, &flow_uninits); | |
94 | } | |
95 | if has_rustc_mir_with(attributes, "rustc_peek_definite_init").is_some() { | |
96 | dataflow::sanity_check_via_rustc_peek(bcx.tcx, mir, id, attributes, &mdpe, &flow_def_inits); | |
97 | } | |
98 | ||
99 | if has_rustc_mir_with(attributes, "stop_after_dataflow").is_some() { | |
100 | bcx.tcx.sess.fatal("stop_after_dataflow ended compilation"); | |
101 | } | |
102 | ||
54a0048b SL |
103 | let mut mbcx = MirBorrowckCtxt { |
104 | bcx: bcx, | |
105 | mir: mir, | |
106 | node_id: id, | |
3157f602 XL |
107 | move_data: mdpe.move_data, |
108 | flow_inits: flow_inits, | |
109 | flow_uninits: flow_uninits, | |
54a0048b SL |
110 | }; |
111 | ||
3157f602 | 112 | for bb in mir.basic_blocks().indices() { |
54a0048b SL |
113 | mbcx.process_basic_block(bb); |
114 | } | |
115 | ||
54a0048b SL |
116 | debug!("borrowck_mir done"); |
117 | } | |
118 | ||
3157f602 XL |
119 | fn do_dataflow<'a, 'tcx, BD>(tcx: TyCtxt<'a, 'tcx, 'tcx>, |
120 | mir: &Mir<'tcx>, | |
121 | node_id: ast::NodeId, | |
122 | attributes: &[ast::Attribute], | |
123 | ctxt: &BD::Ctxt, | |
124 | bd: BD) -> DataflowResults<BD> | |
125 | where BD: BitDenotation<Idx=MovePathIndex, Ctxt=MoveDataParamEnv<'tcx>> + DataflowOperator | |
126 | { | |
3157f602 XL |
127 | let name_found = |sess: &Session, attrs: &[ast::Attribute], name| -> Option<String> { |
128 | if let Some(item) = has_rustc_mir_with(attrs, name) { | |
129 | if let Some(s) = item.value_str() { | |
130 | return Some(s.to_string()) | |
131 | } else { | |
132 | sess.span_err( | |
133 | item.span, | |
134 | &format!("{} attribute requires a path", item.name())); | |
135 | return None; | |
136 | } | |
137 | } | |
138 | return None; | |
139 | }; | |
140 | ||
141 | let print_preflow_to = | |
142 | name_found(tcx.sess, attributes, "borrowck_graphviz_preflow"); | |
143 | let print_postflow_to = | |
144 | name_found(tcx.sess, attributes, "borrowck_graphviz_postflow"); | |
145 | ||
146 | let mut mbcx = MirBorrowckCtxtPreDataflow { | |
147 | node_id: node_id, | |
148 | print_preflow_to: print_preflow_to, | |
149 | print_postflow_to: print_postflow_to, | |
150 | flow_state: DataflowAnalysis::new(tcx, mir, ctxt, bd), | |
151 | }; | |
152 | ||
153 | mbcx.dataflow(|ctxt, i| &ctxt.move_data.move_paths[i]); | |
154 | mbcx.flow_state.results() | |
155 | } | |
156 | ||
157 | ||
158 | pub struct MirBorrowckCtxtPreDataflow<'a, 'tcx: 'a, BD> | |
159 | where BD: BitDenotation, BD::Ctxt: 'a | |
160 | { | |
161 | node_id: ast::NodeId, | |
162 | flow_state: DataflowAnalysis<'a, 'tcx, BD>, | |
163 | print_preflow_to: Option<String>, | |
164 | print_postflow_to: Option<String>, | |
165 | } | |
166 | ||
167 | #[allow(dead_code)] | |
54a0048b SL |
168 | pub struct MirBorrowckCtxt<'b, 'a: 'b, 'tcx: 'a> { |
169 | bcx: &'b mut BorrowckCtxt<'a, 'tcx>, | |
170 | mir: &'b Mir<'tcx>, | |
171 | node_id: ast::NodeId, | |
3157f602 | 172 | move_data: MoveData<'tcx>, |
c30ab7b3 SL |
173 | flow_inits: DataflowResults<MaybeInitializedLvals<'b, 'tcx>>, |
174 | flow_uninits: DataflowResults<MaybeUninitializedLvals<'b, 'tcx>> | |
54a0048b SL |
175 | } |
176 | ||
177 | impl<'b, 'a: 'b, 'tcx: 'a> MirBorrowckCtxt<'b, 'a, 'tcx> { | |
178 | fn process_basic_block(&mut self, bb: BasicBlock) { | |
3157f602 XL |
179 | let BasicBlockData { ref statements, ref terminator, is_cleanup: _ } = |
180 | self.mir[bb]; | |
54a0048b SL |
181 | for stmt in statements { |
182 | self.process_statement(bb, stmt); | |
183 | } | |
184 | ||
185 | self.process_terminator(bb, terminator); | |
186 | } | |
187 | ||
188 | fn process_statement(&mut self, bb: BasicBlock, stmt: &Statement<'tcx>) { | |
189 | debug!("MirBorrowckCtxt::process_statement({:?}, {:?}", bb, stmt); | |
190 | } | |
191 | ||
192 | fn process_terminator(&mut self, bb: BasicBlock, term: &Option<Terminator<'tcx>>) { | |
193 | debug!("MirBorrowckCtxt::process_terminator({:?}, {:?})", bb, term); | |
194 | } | |
195 | } | |
3157f602 XL |
196 | |
197 | #[derive(Debug, PartialEq, Eq, Copy, Clone)] | |
198 | enum DropFlagState { | |
199 | Present, // i.e. initialized | |
200 | Absent, // i.e. deinitialized or "moved" | |
201 | } | |
202 | ||
203 | impl DropFlagState { | |
204 | fn value(self) -> bool { | |
205 | match self { | |
206 | DropFlagState::Present => true, | |
207 | DropFlagState::Absent => false | |
208 | } | |
209 | } | |
210 | } | |
211 | ||
9e0c209e | 212 | fn move_path_children_matching<'tcx, F>(move_data: &MoveData<'tcx>, |
3157f602 XL |
213 | path: MovePathIndex, |
214 | mut cond: F) | |
215 | -> Option<MovePathIndex> | |
c30ab7b3 | 216 | where F: FnMut(&mir::LvalueProjection<'tcx>) -> bool |
3157f602 | 217 | { |
9e0c209e | 218 | let mut next_child = move_data.move_paths[path].first_child; |
3157f602 | 219 | while let Some(child_index) = next_child { |
9e0c209e | 220 | match move_data.move_paths[child_index].lvalue { |
c30ab7b3 | 221 | mir::Lvalue::Projection(ref proj) => { |
3157f602 XL |
222 | if cond(proj) { |
223 | return Some(child_index) | |
224 | } | |
225 | } | |
226 | _ => {} | |
227 | } | |
9e0c209e | 228 | next_child = move_data.move_paths[child_index].next_sibling; |
3157f602 XL |
229 | } |
230 | ||
231 | None | |
232 | } | |
233 | ||
234 | /// When enumerating the child fragments of a path, don't recurse into | |
235 | /// paths (1.) past arrays, slices, and pointers, nor (2.) into a type | |
236 | /// that implements `Drop`. | |
237 | /// | |
238 | /// Lvalues behind references or arrays are not tracked by elaboration | |
239 | /// and are always assumed to be initialized when accessible. As | |
240 | /// references and indexes can be reseated, trying to track them can | |
241 | /// only lead to trouble. | |
242 | /// | |
243 | /// Lvalues behind ADT's with a Drop impl are not tracked by | |
244 | /// elaboration since they can never have a drop-flag state that | |
245 | /// differs from that of the parent with the Drop impl. | |
246 | /// | |
247 | /// In both cases, the contents can only be accessed if and only if | |
248 | /// their parents are initialized. This implies for example that there | |
249 | /// is no need to maintain separate drop flags to track such state. | |
250 | /// | |
251 | /// FIXME: we have to do something for moving slice patterns. | |
252 | fn lvalue_contents_drop_state_cannot_differ<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
253 | mir: &Mir<'tcx>, | |
c30ab7b3 | 254 | lv: &mir::Lvalue<'tcx>) -> bool { |
5bcae85e | 255 | let ty = lv.ty(mir, tcx).to_ty(tcx); |
3157f602 XL |
256 | match ty.sty { |
257 | ty::TyArray(..) | ty::TySlice(..) | ty::TyRef(..) | ty::TyRawPtr(..) => { | |
9e0c209e | 258 | debug!("lvalue_contents_drop_state_cannot_differ lv: {:?} ty: {:?} refd => true", |
3157f602 XL |
259 | lv, ty); |
260 | true | |
261 | } | |
9e0c209e SL |
262 | ty::TyAdt(def, _) if def.has_dtor() || def.is_union() => { |
263 | debug!("lvalue_contents_drop_state_cannot_differ lv: {:?} ty: {:?} Drop => true", | |
3157f602 XL |
264 | lv, ty); |
265 | true | |
266 | } | |
267 | _ => { | |
268 | false | |
269 | } | |
270 | } | |
271 | } | |
272 | ||
9e0c209e SL |
273 | fn on_lookup_result_bits<'a, 'tcx, F>( |
274 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
275 | mir: &Mir<'tcx>, | |
276 | move_data: &MoveData<'tcx>, | |
277 | lookup_result: LookupResult, | |
278 | each_child: F) | |
279 | where F: FnMut(MovePathIndex) | |
280 | { | |
281 | match lookup_result { | |
282 | LookupResult::Parent(..) => { | |
283 | // access to untracked value - do not touch children | |
284 | } | |
285 | LookupResult::Exact(e) => { | |
286 | on_all_children_bits(tcx, mir, move_data, e, each_child) | |
287 | } | |
288 | } | |
289 | } | |
290 | ||
3157f602 XL |
291 | fn on_all_children_bits<'a, 'tcx, F>( |
292 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
293 | mir: &Mir<'tcx>, | |
294 | move_data: &MoveData<'tcx>, | |
295 | move_path_index: MovePathIndex, | |
296 | mut each_child: F) | |
297 | where F: FnMut(MovePathIndex) | |
298 | { | |
299 | fn is_terminal_path<'a, 'tcx>( | |
300 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
301 | mir: &Mir<'tcx>, | |
302 | move_data: &MoveData<'tcx>, | |
303 | path: MovePathIndex) -> bool | |
304 | { | |
9e0c209e SL |
305 | lvalue_contents_drop_state_cannot_differ( |
306 | tcx, mir, &move_data.move_paths[path].lvalue) | |
3157f602 XL |
307 | } |
308 | ||
309 | fn on_all_children_bits<'a, 'tcx, F>( | |
310 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
311 | mir: &Mir<'tcx>, | |
312 | move_data: &MoveData<'tcx>, | |
313 | move_path_index: MovePathIndex, | |
314 | each_child: &mut F) | |
315 | where F: FnMut(MovePathIndex) | |
316 | { | |
317 | each_child(move_path_index); | |
318 | ||
319 | if is_terminal_path(tcx, mir, move_data, move_path_index) { | |
320 | return | |
321 | } | |
322 | ||
323 | let mut next_child_index = move_data.move_paths[move_path_index].first_child; | |
324 | while let Some(child_index) = next_child_index { | |
325 | on_all_children_bits(tcx, mir, move_data, child_index, each_child); | |
326 | next_child_index = move_data.move_paths[child_index].next_sibling; | |
327 | } | |
328 | } | |
329 | on_all_children_bits(tcx, mir, move_data, move_path_index, &mut each_child); | |
330 | } | |
331 | ||
332 | fn drop_flag_effects_for_function_entry<'a, 'tcx, F>( | |
333 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
334 | mir: &Mir<'tcx>, | |
335 | ctxt: &MoveDataParamEnv<'tcx>, | |
336 | mut callback: F) | |
337 | where F: FnMut(MovePathIndex, DropFlagState) | |
338 | { | |
339 | let move_data = &ctxt.move_data; | |
c30ab7b3 SL |
340 | for arg in mir.args_iter() { |
341 | let lvalue = mir::Lvalue::Local(arg); | |
9e0c209e SL |
342 | let lookup_result = move_data.rev_lookup.find(&lvalue); |
343 | on_lookup_result_bits(tcx, mir, move_data, | |
344 | lookup_result, | |
345 | |moi| callback(moi, DropFlagState::Present)); | |
3157f602 XL |
346 | } |
347 | } | |
348 | ||
349 | fn drop_flag_effects_for_location<'a, 'tcx, F>( | |
350 | tcx: TyCtxt<'a, 'tcx, 'tcx>, | |
351 | mir: &Mir<'tcx>, | |
352 | ctxt: &MoveDataParamEnv<'tcx>, | |
353 | loc: Location, | |
354 | mut callback: F) | |
355 | where F: FnMut(MovePathIndex, DropFlagState) | |
356 | { | |
357 | let move_data = &ctxt.move_data; | |
358 | let param_env = &ctxt.param_env; | |
359 | debug!("drop_flag_effects_for_location({:?})", loc); | |
360 | ||
361 | // first, move out of the RHS | |
362 | for mi in &move_data.loc_map[loc] { | |
363 | let path = mi.move_path_index(move_data); | |
364 | debug!("moving out of path {:?}", move_data.move_paths[path]); | |
365 | ||
366 | // don't move out of non-Copy things | |
9e0c209e SL |
367 | let lvalue = &move_data.move_paths[path].lvalue; |
368 | let ty = lvalue.ty(mir, tcx).to_ty(tcx); | |
369 | if !ty.moves_by_default(tcx, param_env, DUMMY_SP) { | |
370 | continue; | |
3157f602 XL |
371 | } |
372 | ||
373 | on_all_children_bits(tcx, mir, move_data, | |
374 | path, | |
375 | |moi| callback(moi, DropFlagState::Absent)) | |
376 | } | |
377 | ||
378 | let block = &mir[loc.block]; | |
9e0c209e | 379 | match block.statements.get(loc.statement_index) { |
3157f602 | 380 | Some(stmt) => match stmt.kind { |
c30ab7b3 | 381 | mir::StatementKind::SetDiscriminant{ .. } => { |
5bcae85e SL |
382 | span_bug!(stmt.source_info.span, "SetDiscrimant should not exist during borrowck"); |
383 | } | |
c30ab7b3 | 384 | mir::StatementKind::Assign(ref lvalue, _) => { |
3157f602 | 385 | debug!("drop_flag_effects: assignment {:?}", stmt); |
9e0c209e SL |
386 | on_lookup_result_bits(tcx, mir, move_data, |
387 | move_data.rev_lookup.find(lvalue), | |
388 | |moi| callback(moi, DropFlagState::Present)) | |
3157f602 | 389 | } |
c30ab7b3 SL |
390 | mir::StatementKind::StorageLive(_) | |
391 | mir::StatementKind::StorageDead(_) | | |
392 | mir::StatementKind::Nop => {} | |
3157f602 XL |
393 | }, |
394 | None => { | |
395 | debug!("drop_flag_effects: replace {:?}", block.terminator()); | |
396 | match block.terminator().kind { | |
c30ab7b3 | 397 | mir::TerminatorKind::DropAndReplace { ref location, .. } => { |
9e0c209e SL |
398 | on_lookup_result_bits(tcx, mir, move_data, |
399 | move_data.rev_lookup.find(location), | |
400 | |moi| callback(moi, DropFlagState::Present)) | |
3157f602 XL |
401 | } |
402 | _ => { | |
403 | // other terminators do not contain move-ins | |
404 | } | |
405 | } | |
406 | } | |
407 | } | |
408 | } |