src/librustc_borrowck/borrowck/mir/mod.rs

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