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::ParamEnv<'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     // 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();
  67
  68     let param_env = tcx.parameter_environment(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());
  72     let flow_inits =
  73         do_dataflow(tcx, mir, id, attributes, &dead_unwinds,
  74                     MaybeInitializedLvals::new(tcx, mir, &mdpe),
  75                     |bd, i| &bd.move_data().move_paths[i]);
  76     let flow_uninits =
  77         do_dataflow(tcx, mir, id, attributes, &dead_unwinds,
  78                     MaybeUninitializedLvals::new(tcx, mir, &mdpe),
  79                     |bd, i| &bd.move_data().move_paths[i]);
  80     let flow_def_inits =
  81         do_dataflow(tcx, mir, id, attributes, &dead_unwinds,
  82                     DefinitelyInitializedLvals::new(tcx, mir, &mdpe),
  83                     |bd, i| &bd.move_data().move_paths[i]);
  84
  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);
  87     }
  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);
  90     }
  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);
  93     }
  94
  95     if has_rustc_mir_with(attributes, "stop_after_dataflow").is_some() {
  96         bcx.tcx.sess.fatal("stop_after_dataflow ended compilation");
  97     }
  98
  99     let mut mbcx = MirBorrowckCtxt {
 100         bcx: bcx,
 101         mir: mir,
 102         node_id: id,
 103         move_data: &mdpe.move_data,
 104         flow_inits: flow_inits,
 105         flow_uninits: flow_uninits,
 106     };
 107
 108     for bb in mir.basic_blocks().indices() {
 109         mbcx.process_basic_block(bb);
 110     }
 111
 112     debug!("borrowck_mir done");
 113 }
 114
 115 fn do_dataflow<'a, 'tcx, BD, P>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 116                                 mir: &Mir<'tcx>,
 117                                 node_id: ast::NodeId,
 118                                 attributes: &[ast::Attribute],
 119                                 dead_unwinds: &IdxSet<BasicBlock>,
 120                                 bd: BD,
 121                                 p: P)
 122                                 -> DataflowResults<BD>
 123     where BD: BitDenotation<Idx=MovePathIndex> + DataflowOperator,
 124           P: Fn(&BD, BD::Idx) -> &fmt::Debug
 125 {
 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())
 130             } else {
 131                 sess.span_err(
 132                     item.span,
 133                     &format!("{} attribute requires a path", item.name()));
 134                 return None;
 135             }
 136         }
 137         return None;
 138     };
 139
 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");
 144
 145     let mut mbcx = MirBorrowckCtxtPreDataflow {
 146         node_id: node_id,
 147         print_preflow_to: print_preflow_to,
 148         print_postflow_to: print_postflow_to,
 149         flow_state: DataflowAnalysis::new(tcx, mir, dead_unwinds, bd),
 150     };
 151
 152     mbcx.dataflow(p);
 153     mbcx.flow_state.results()
 154 }
 155
 156
 157 pub struct MirBorrowckCtxtPreDataflow<'a, 'tcx: 'a, BD> where BD: BitDenotation
 158 {
 159     node_id: ast::NodeId,
 160     flow_state: DataflowAnalysis<'a, 'tcx, BD>,
 161     print_preflow_to: Option<String>,
 162     print_postflow_to: Option<String>,
 163 }
 164
 165 #[allow(dead_code)]
 166 pub struct MirBorrowckCtxt<'b, 'a: 'b, 'tcx: 'a> {
 167     bcx: &'b mut BorrowckCtxt<'a, 'tcx>,
 168     mir: &'b Mir<'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>>
 173 }
 174
 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: _ } =
 178             self.mir[bb];
 179         for stmt in statements {
 180             self.process_statement(bb, stmt);
 181         }
 182
 183         self.process_terminator(bb, terminator);
 184     }
 185
 186     fn process_statement(&mut self, bb: BasicBlock, stmt: &Statement<'tcx>) {
 187         debug!("MirBorrowckCtxt::process_statement({:?}, {:?}", bb, stmt);
 188     }
 189
 190     fn process_terminator(&mut self, bb: BasicBlock, term: &Option<Terminator<'tcx>>) {
 191         debug!("MirBorrowckCtxt::process_terminator({:?}, {:?})", bb, term);
 192     }
 193 }
 194
 195 fn move_path_children_matching<'tcx, F>(move_data: &MoveData<'tcx>,
 196                                         path: MovePathIndex,
 197                                         mut cond: F)
 198                                         -> Option<MovePathIndex>
 199     where F: FnMut(&mir::LvalueProjection<'tcx>) -> bool
 200 {
 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) => {
 205                 if cond(proj) {
 206                     return Some(child_index)
 207                 }
 208             }
 209             _ => {}
 210         }
 211         next_child = move_data.move_paths[child_index].next_sibling;
 212     }
 213
 214     None
 215 }
 216
 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`.
 220 ///
 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.
 225 ///
 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.
 229 ///
 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.
 233 ///
 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>,
 236                                                       mir: &Mir<'tcx>,
 237                                                       lv: &mir::Lvalue<'tcx>) -> bool {
 238     let ty = lv.ty(mir, tcx).to_ty(tcx);
 239     match ty.sty {
 240         ty::TyArray(..) | ty::TySlice(..) | ty::TyRef(..) | ty::TyRawPtr(..) => {
 241             debug!("lvalue_contents_drop_state_cannot_differ lv: {:?} ty: {:?} refd => true",
 242                    lv, ty);
 243             true
 244         }
 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",
 247                    lv, ty);
 248             true
 249         }
 250         _ => {
 251             false
 252         }
 253     }
 254 }
 255
 256 fn on_lookup_result_bits<'a, 'tcx, F>(
 257     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 258     mir: &Mir<'tcx>,
 259     move_data: &MoveData<'tcx>,
 260     lookup_result: LookupResult,
 261     each_child: F)
 262     where F: FnMut(MovePathIndex)
 263 {
 264     match lookup_result {
 265         LookupResult::Parent(..) => {
 266             // access to untracked value - do not touch children
 267         }
 268         LookupResult::Exact(e) => {
 269             on_all_children_bits(tcx, mir, move_data, e, each_child)
 270         }
 271     }
 272 }
 273
 274 fn on_all_children_bits<'a, 'tcx, F>(
 275     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 276     mir: &Mir<'tcx>,
 277     move_data: &MoveData<'tcx>,
 278     move_path_index: MovePathIndex,
 279     mut each_child: F)
 280     where F: FnMut(MovePathIndex)
 281 {
 282     fn is_terminal_path<'a, 'tcx>(
 283         tcx: TyCtxt<'a, 'tcx, 'tcx>,
 284         mir: &Mir<'tcx>,
 285         move_data: &MoveData<'tcx>,
 286         path: MovePathIndex) -> bool
 287     {
 288         lvalue_contents_drop_state_cannot_differ(
 289             tcx, mir, &move_data.move_paths[path].lvalue)
 290     }
 291
 292     fn on_all_children_bits<'a, 'tcx, F>(
 293         tcx: TyCtxt<'a, 'tcx, 'tcx>,
 294         mir: &Mir<'tcx>,
 295         move_data: &MoveData<'tcx>,
 296         move_path_index: MovePathIndex,
 297         each_child: &mut F)
 298         where F: FnMut(MovePathIndex)
 299     {
 300         each_child(move_path_index);
 301
 302         if is_terminal_path(tcx, mir, move_data, move_path_index) {
 303             return
 304         }
 305
 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;
 310         }
 311     }
 312     on_all_children_bits(tcx, mir, move_data, move_path_index, &mut each_child);
 313 }
 314
 315 fn on_all_drop_children_bits<'a, 'tcx, F>(
 316     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 317     mir: &Mir<'tcx>,
 318     ctxt: &MoveDataParamEnv<'tcx>,
 319     path: MovePathIndex,
 320     mut each_child: F)
 321     where F: FnMut(MovePathIndex)
 322 {
 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);
 327
 328         if ty.needs_drop(tcx, ctxt.param_env) {
 329             each_child(child);
 330         } else {
 331             debug!("on_all_drop_children_bits - skipping")
 332         }
 333     })
 334 }
 335
 336 fn drop_flag_effects_for_function_entry<'a, 'tcx, F>(
 337     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 338     mir: &Mir<'tcx>,
 339     ctxt: &MoveDataParamEnv<'tcx>,
 340     mut callback: F)
 341     where F: FnMut(MovePathIndex, DropFlagState)
 342 {
 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,
 348                               lookup_result,
 349                               |moi| callback(moi, DropFlagState::Present));
 350     }
 351 }
 352
 353 fn drop_flag_effects_for_location<'a, 'tcx, F>(
 354     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 355     mir: &Mir<'tcx>,
 356     ctxt: &MoveDataParamEnv<'tcx>,
 357     loc: Location,
 358     mut callback: F)
 359     where F: FnMut(MovePathIndex, DropFlagState)
 360 {
 361     let move_data = &ctxt.move_data;
 362     let param_env = ctxt.param_env;
 363     debug!("drop_flag_effects_for_location({:?})", loc);
 364
 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]);
 369
 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) {
 374             continue;
 375         }
 376
 377         on_all_children_bits(tcx, mir, move_data,
 378                              path,
 379                              |moi| callback(moi, DropFlagState::Absent))
 380     }
 381
 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");
 387             }
 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))
 393             }
 394             mir::StatementKind::StorageLive(_) |
 395             mir::StatementKind::StorageDead(_) |
 396             mir::StatementKind::InlineAsm { .. } |
 397             mir::StatementKind::Nop => {}
 398         },
 399         None => {
 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))
 406                 }
 407                 _ => {
 408                     // other terminators do not contain move-ins
 409                 }
 410             }
 411         }
 412     }
 413 }