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