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.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 use borrowck::BorrowckCtxt;
13 use syntax::ast::{self, MetaItem};
14 use syntax_pos::DUMMY_SP;
16 use rustc::mir::{self, BasicBlock, BasicBlockData, Mir, Statement, Terminator, Location};
17 use rustc::session::Session;
18 use rustc::ty::{self, TyCtxt};
19 use rustc_mir::util::elaborate_drops::DropFlagState;
20 use rustc_data_structures::indexed_set::{IdxSet, IdxSetBuf};
23 pub mod elaborate_drops;
28 use self::dataflow::{BitDenotation};
29 use self::dataflow::{DataflowOperator};
30 use self::dataflow::{Dataflow, DataflowAnalysis, DataflowResults};
31 use self::dataflow::{MaybeInitializedLvals, MaybeUninitializedLvals};
32 use self::dataflow::{DefinitelyInitializedLvals};
33 use self::gather_moves::{HasMoveData, MoveData, MovePathIndex, LookupResult};
37 fn has_rustc_mir_with(attrs: &[ast::Attribute], name: &str) -> Option<MetaItem> {
39 if attr.check_name("rustc_mir") {
40 let items = attr.meta_item_list();
41 for item in items.iter().flat_map(|l| l.iter()) {
42 match item.meta_item() {
43 Some(mi) if mi.check_name(name) => return Some(mi.clone()),
52 pub struct MoveDataParamEnv<'tcx> {
53 move_data: MoveData<'tcx>,
54 param_env: ty::ParamEnv<'tcx>,
57 pub fn borrowck_mir(bcx: &mut BorrowckCtxt,
59 attributes: &[ast::Attribute]) {
61 let def_id = tcx.hir.local_def_id(id);
62 debug!("borrowck_mir({}) UNIMPLEMENTED", tcx.item_path_str(def_id));
64 // It is safe for us to borrow `mir_validated()`: `optimized_mir`
65 // steals it, but it forces the `borrowck` query.
66 let mir = &tcx.mir_validated(def_id).borrow();
68 let param_env = tcx.param_env(def_id);
69 let move_data = MoveData::gather_moves(mir, tcx, param_env);
70 let mdpe = MoveDataParamEnv { move_data: move_data, param_env: param_env };
71 let dead_unwinds = IdxSetBuf::new_empty(mir.basic_blocks().len());
73 do_dataflow(tcx, mir, id, attributes, &dead_unwinds,
74 MaybeInitializedLvals::new(tcx, mir, &mdpe),
75 |bd, i| &bd.move_data().move_paths[i]);
77 do_dataflow(tcx, mir, id, attributes, &dead_unwinds,
78 MaybeUninitializedLvals::new(tcx, mir, &mdpe),
79 |bd, i| &bd.move_data().move_paths[i]);
81 do_dataflow(tcx, mir, id, attributes, &dead_unwinds,
82 DefinitelyInitializedLvals::new(tcx, mir, &mdpe),
83 |bd, i| &bd.move_data().move_paths[i]);
85 if has_rustc_mir_with(attributes, "rustc_peek_maybe_init").is_some() {
86 dataflow::sanity_check_via_rustc_peek(bcx.tcx, mir, id, attributes, &flow_inits);
88 if has_rustc_mir_with(attributes, "rustc_peek_maybe_uninit").is_some() {
89 dataflow::sanity_check_via_rustc_peek(bcx.tcx, mir, id, attributes, &flow_uninits);
91 if has_rustc_mir_with(attributes, "rustc_peek_definite_init").is_some() {
92 dataflow::sanity_check_via_rustc_peek(bcx.tcx, mir, id, attributes, &flow_def_inits);
95 if has_rustc_mir_with(attributes, "stop_after_dataflow").is_some() {
96 bcx.tcx.sess.fatal("stop_after_dataflow ended compilation");
99 let mut mbcx = MirBorrowckCtxt {
103 move_data: &mdpe.move_data,
104 flow_inits: flow_inits,
105 flow_uninits: flow_uninits,
108 for bb in mir.basic_blocks().indices() {
109 mbcx.process_basic_block(bb);
112 debug!("borrowck_mir done");
115 fn do_dataflow<'a, 'tcx, BD, P>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
117 node_id: ast::NodeId,
118 attributes: &[ast::Attribute],
119 dead_unwinds: &IdxSet<BasicBlock>,
122 -> DataflowResults<BD>
123 where BD: BitDenotation<Idx=MovePathIndex> + DataflowOperator,
124 P: Fn(&BD, BD::Idx) -> &fmt::Debug
126 let name_found = |sess: &Session, attrs: &[ast::Attribute], name| -> Option<String> {
127 if let Some(item) = has_rustc_mir_with(attrs, name) {
128 if let Some(s) = item.value_str() {
129 return Some(s.to_string())
133 &format!("{} attribute requires a path", item.name()));
140 let print_preflow_to =
141 name_found(tcx.sess, attributes, "borrowck_graphviz_preflow");
142 let print_postflow_to =
143 name_found(tcx.sess, attributes, "borrowck_graphviz_postflow");
145 let mut mbcx = MirBorrowckCtxtPreDataflow {
147 print_preflow_to: print_preflow_to,
148 print_postflow_to: print_postflow_to,
149 flow_state: DataflowAnalysis::new(tcx, mir, dead_unwinds, bd),
153 mbcx.flow_state.results()
157 pub struct MirBorrowckCtxtPreDataflow<'a, 'tcx: 'a, BD> where BD: BitDenotation
159 node_id: ast::NodeId,
160 flow_state: DataflowAnalysis<'a, 'tcx, BD>,
161 print_preflow_to: Option<String>,
162 print_postflow_to: Option<String>,
166 pub struct MirBorrowckCtxt<'b, 'a: 'b, 'tcx: 'a> {
167 bcx: &'b mut BorrowckCtxt<'a, 'tcx>,
169 node_id: ast::NodeId,
170 move_data: &'b MoveData<'tcx>,
171 flow_inits: DataflowResults<MaybeInitializedLvals<'b, 'tcx>>,
172 flow_uninits: DataflowResults<MaybeUninitializedLvals<'b, 'tcx>>
175 impl<'b, 'a: 'b, 'tcx: 'a> MirBorrowckCtxt<'b, 'a, 'tcx> {
176 fn process_basic_block(&mut self, bb: BasicBlock) {
177 let BasicBlockData { ref statements, ref terminator, is_cleanup: _ } =
179 for stmt in statements {
180 self.process_statement(bb, stmt);
183 self.process_terminator(bb, terminator);
186 fn process_statement(&mut self, bb: BasicBlock, stmt: &Statement<'tcx>) {
187 debug!("MirBorrowckCtxt::process_statement({:?}, {:?}", bb, stmt);
190 fn process_terminator(&mut self, bb: BasicBlock, term: &Option<Terminator<'tcx>>) {
191 debug!("MirBorrowckCtxt::process_terminator({:?}, {:?})", bb, term);
195 fn move_path_children_matching<'tcx, F>(move_data: &MoveData<'tcx>,
198 -> Option<MovePathIndex>
199 where F: FnMut(&mir::LvalueProjection<'tcx>) -> bool
201 let mut next_child = move_data.move_paths[path].first_child;
202 while let Some(child_index) = next_child {
203 match move_data.move_paths[child_index].lvalue {
204 mir::Lvalue::Projection(ref proj) => {
206 return Some(child_index)
211 next_child = move_data.move_paths[child_index].next_sibling;
217 /// When enumerating the child fragments of a path, don't recurse into
218 /// paths (1.) past arrays, slices, and pointers, nor (2.) into a type
219 /// that implements `Drop`.
221 /// Lvalues behind references or arrays are not tracked by elaboration
222 /// and are always assumed to be initialized when accessible. As
223 /// references and indexes can be reseated, trying to track them can
224 /// only lead to trouble.
226 /// Lvalues behind ADT's with a Drop impl are not tracked by
227 /// elaboration since they can never have a drop-flag state that
228 /// differs from that of the parent with the Drop impl.
230 /// In both cases, the contents can only be accessed if and only if
231 /// their parents are initialized. This implies for example that there
232 /// is no need to maintain separate drop flags to track such state.
234 /// FIXME: we have to do something for moving slice patterns.
235 fn lvalue_contents_drop_state_cannot_differ<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
237 lv: &mir::Lvalue<'tcx>) -> bool {
238 let ty = lv.ty(mir, tcx).to_ty(tcx);
240 ty::TyArray(..) | ty::TySlice(..) | ty::TyRef(..) | ty::TyRawPtr(..) => {
241 debug!("lvalue_contents_drop_state_cannot_differ lv: {:?} ty: {:?} refd => true",
245 ty::TyAdt(def, _) if (def.has_dtor(tcx) && !def.is_box()) || def.is_union() => {
246 debug!("lvalue_contents_drop_state_cannot_differ lv: {:?} ty: {:?} Drop => true",
256 fn on_lookup_result_bits<'a, 'tcx, F>(
257 tcx: TyCtxt<'a, 'tcx, 'tcx>,
259 move_data: &MoveData<'tcx>,
260 lookup_result: LookupResult,
262 where F: FnMut(MovePathIndex)
264 match lookup_result {
265 LookupResult::Parent(..) => {
266 // access to untracked value - do not touch children
268 LookupResult::Exact(e) => {
269 on_all_children_bits(tcx, mir, move_data, e, each_child)
274 fn on_all_children_bits<'a, 'tcx, F>(
275 tcx: TyCtxt<'a, 'tcx, 'tcx>,
277 move_data: &MoveData<'tcx>,
278 move_path_index: MovePathIndex,
280 where F: FnMut(MovePathIndex)
282 fn is_terminal_path<'a, 'tcx>(
283 tcx: TyCtxt<'a, 'tcx, 'tcx>,
285 move_data: &MoveData<'tcx>,
286 path: MovePathIndex) -> bool
288 lvalue_contents_drop_state_cannot_differ(
289 tcx, mir, &move_data.move_paths[path].lvalue)
292 fn on_all_children_bits<'a, 'tcx, F>(
293 tcx: TyCtxt<'a, 'tcx, 'tcx>,
295 move_data: &MoveData<'tcx>,
296 move_path_index: MovePathIndex,
298 where F: FnMut(MovePathIndex)
300 each_child(move_path_index);
302 if is_terminal_path(tcx, mir, move_data, move_path_index) {
306 let mut next_child_index = move_data.move_paths[move_path_index].first_child;
307 while let Some(child_index) = next_child_index {
308 on_all_children_bits(tcx, mir, move_data, child_index, each_child);
309 next_child_index = move_data.move_paths[child_index].next_sibling;
312 on_all_children_bits(tcx, mir, move_data, move_path_index, &mut each_child);
315 fn on_all_drop_children_bits<'a, 'tcx, F>(
316 tcx: TyCtxt<'a, 'tcx, 'tcx>,
318 ctxt: &MoveDataParamEnv<'tcx>,
321 where F: FnMut(MovePathIndex)
323 on_all_children_bits(tcx, mir, &ctxt.move_data, path, |child| {
324 let lvalue = &ctxt.move_data.move_paths[path].lvalue;
325 let ty = lvalue.ty(mir, tcx).to_ty(tcx);
326 debug!("on_all_drop_children_bits({:?}, {:?} : {:?})", path, lvalue, ty);
328 if ty.needs_drop(tcx, ctxt.param_env) {
331 debug!("on_all_drop_children_bits - skipping")
336 fn drop_flag_effects_for_function_entry<'a, 'tcx, F>(
337 tcx: TyCtxt<'a, 'tcx, 'tcx>,
339 ctxt: &MoveDataParamEnv<'tcx>,
341 where F: FnMut(MovePathIndex, DropFlagState)
343 let move_data = &ctxt.move_data;
344 for arg in mir.args_iter() {
345 let lvalue = mir::Lvalue::Local(arg);
346 let lookup_result = move_data.rev_lookup.find(&lvalue);
347 on_lookup_result_bits(tcx, mir, move_data,
349 |moi| callback(moi, DropFlagState::Present));
353 fn drop_flag_effects_for_location<'a, 'tcx, F>(
354 tcx: TyCtxt<'a, 'tcx, 'tcx>,
356 ctxt: &MoveDataParamEnv<'tcx>,
359 where F: FnMut(MovePathIndex, DropFlagState)
361 let move_data = &ctxt.move_data;
362 let param_env = ctxt.param_env;
363 debug!("drop_flag_effects_for_location({:?})", loc);
365 // first, move out of the RHS
366 for mi in &move_data.loc_map[loc] {
367 let path = mi.move_path_index(move_data);
368 debug!("moving out of path {:?}", move_data.move_paths[path]);
370 // don't move out of non-Copy things
371 let lvalue = &move_data.move_paths[path].lvalue;
372 let ty = lvalue.ty(mir, tcx).to_ty(tcx);
373 if !ty.moves_by_default(tcx, param_env, DUMMY_SP) {
377 on_all_children_bits(tcx, mir, move_data,
379 |moi| callback(moi, DropFlagState::Absent))
382 let block = &mir[loc.block];
383 match block.statements.get(loc.statement_index) {
384 Some(stmt) => match stmt.kind {
385 mir::StatementKind::SetDiscriminant{ .. } => {
386 span_bug!(stmt.source_info.span, "SetDiscrimant should not exist during borrowck");
388 mir::StatementKind::Assign(ref lvalue, _) => {
389 debug!("drop_flag_effects: assignment {:?}", stmt);
390 on_lookup_result_bits(tcx, mir, move_data,
391 move_data.rev_lookup.find(lvalue),
392 |moi| callback(moi, DropFlagState::Present))
394 mir::StatementKind::StorageLive(_) |
395 mir::StatementKind::StorageDead(_) |
396 mir::StatementKind::InlineAsm { .. } |
397 mir::StatementKind::Nop => {}
400 debug!("drop_flag_effects: replace {:?}", block.terminator());
401 match block.terminator().kind {
402 mir::TerminatorKind::DropAndReplace { ref location, .. } => {
403 on_lookup_result_bits(tcx, mir, move_data,
404 move_data.rev_lookup.find(location),
405 |moi| callback(moi, DropFlagState::Present))
408 // other terminators do not contain move-ins