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
  21 mod abs_domain;
  22 pub mod elaborate_drops;
  23 mod dataflow;
  24 mod gather_moves;
  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 fn move_path_children_matching<'tcx, F>(move_data: &MoveData<'tcx>,
 187                                         path: MovePathIndex,
 188                                         mut cond: F)
 189                                         -> Option<MovePathIndex>
 190     where F: FnMut(&mir::LvalueProjection<'tcx>) -> bool
 191 {
 192     let mut next_child = move_data.move_paths[path].first_child;
 193     while let Some(child_index) = next_child {
 194         match move_data.move_paths[child_index].lvalue {
 195             mir::Lvalue::Projection(ref proj) => {
 196                 if cond(proj) {
 197                     return Some(child_index)
 198                 }
 199             }
 200             _ => {}
 201         }
 202         next_child = move_data.move_paths[child_index].next_sibling;
 203     }
 204
 205     None
 206 }
 207
 208 /// When enumerating the child fragments of a path, don't recurse into
 209 /// paths (1.) past arrays, slices, and pointers, nor (2.) into a type
 210 /// that implements `Drop`.
 211 ///
 212 /// Lvalues behind references or arrays are not tracked by elaboration
 213 /// and are always assumed to be initialized when accessible. As
 214 /// references and indexes can be reseated, trying to track them can
 215 /// only lead to trouble.
 216 ///
 217 /// Lvalues behind ADT's with a Drop impl are not tracked by
 218 /// elaboration since they can never have a drop-flag state that
 219 /// differs from that of the parent with the Drop impl.
 220 ///
 221 /// In both cases, the contents can only be accessed if and only if
 222 /// their parents are initialized. This implies for example that there
 223 /// is no need to maintain separate drop flags to track such state.
 224 ///
 225 /// FIXME: we have to do something for moving slice patterns.
 226 fn lvalue_contents_drop_state_cannot_differ<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 227                                                       mir: &Mir<'tcx>,
 228                                                       lv: &mir::Lvalue<'tcx>) -> bool {
 229     let ty = lv.ty(mir, tcx).to_ty(tcx);
 230     match ty.sty {
 231         ty::TyArray(..) | ty::TySlice(..) | ty::TyRef(..) | ty::TyRawPtr(..) => {
 232             debug!("lvalue_contents_drop_state_cannot_differ lv: {:?} ty: {:?} refd => true",
 233                    lv, ty);
 234             true
 235         }
 236         ty::TyAdt(def, _) if (def.has_dtor(tcx) && !def.is_box()) || def.is_union() => {
 237             debug!("lvalue_contents_drop_state_cannot_differ lv: {:?} ty: {:?} Drop => true",
 238                    lv, ty);
 239             true
 240         }
 241         _ => {
 242             false
 243         }
 244     }
 245 }
 246
 247 fn on_lookup_result_bits<'a, 'tcx, F>(
 248     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 249     mir: &Mir<'tcx>,
 250     move_data: &MoveData<'tcx>,
 251     lookup_result: LookupResult,
 252     each_child: F)
 253     where F: FnMut(MovePathIndex)
 254 {
 255     match lookup_result {
 256         LookupResult::Parent(..) => {
 257             // access to untracked value - do not touch children
 258         }
 259         LookupResult::Exact(e) => {
 260             on_all_children_bits(tcx, mir, move_data, e, each_child)
 261         }
 262     }
 263 }
 264
 265 fn on_all_children_bits<'a, 'tcx, F>(
 266     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 267     mir: &Mir<'tcx>,
 268     move_data: &MoveData<'tcx>,
 269     move_path_index: MovePathIndex,
 270     mut each_child: F)
 271     where F: FnMut(MovePathIndex)
 272 {
 273     fn is_terminal_path<'a, 'tcx>(
 274         tcx: TyCtxt<'a, 'tcx, 'tcx>,
 275         mir: &Mir<'tcx>,
 276         move_data: &MoveData<'tcx>,
 277         path: MovePathIndex) -> bool
 278     {
 279         lvalue_contents_drop_state_cannot_differ(
 280             tcx, mir, &move_data.move_paths[path].lvalue)
 281     }
 282
 283     fn on_all_children_bits<'a, 'tcx, F>(
 284         tcx: TyCtxt<'a, 'tcx, 'tcx>,
 285         mir: &Mir<'tcx>,
 286         move_data: &MoveData<'tcx>,
 287         move_path_index: MovePathIndex,
 288         each_child: &mut F)
 289         where F: FnMut(MovePathIndex)
 290     {
 291         each_child(move_path_index);
 292
 293         if is_terminal_path(tcx, mir, move_data, move_path_index) {
 294             return
 295         }
 296
 297         let mut next_child_index = move_data.move_paths[move_path_index].first_child;
 298         while let Some(child_index) = next_child_index {
 299             on_all_children_bits(tcx, mir, move_data, child_index, each_child);
 300             next_child_index = move_data.move_paths[child_index].next_sibling;
 301         }
 302     }
 303     on_all_children_bits(tcx, mir, move_data, move_path_index, &mut each_child);
 304 }
 305
 306 fn drop_flag_effects_for_function_entry<'a, 'tcx, F>(
 307     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 308     mir: &Mir<'tcx>,
 309     ctxt: &MoveDataParamEnv<'tcx>,
 310     mut callback: F)
 311     where F: FnMut(MovePathIndex, DropFlagState)
 312 {
 313     let move_data = &ctxt.move_data;
 314     for arg in mir.args_iter() {
 315         let lvalue = mir::Lvalue::Local(arg);
 316         let lookup_result = move_data.rev_lookup.find(&lvalue);
 317         on_lookup_result_bits(tcx, mir, move_data,
 318                               lookup_result,
 319                               |moi| callback(moi, DropFlagState::Present));
 320     }
 321 }
 322
 323 fn drop_flag_effects_for_location<'a, 'tcx, F>(
 324     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 325     mir: &Mir<'tcx>,
 326     ctxt: &MoveDataParamEnv<'tcx>,
 327     loc: Location,
 328     mut callback: F)
 329     where F: FnMut(MovePathIndex, DropFlagState)
 330 {
 331     let move_data = &ctxt.move_data;
 332     let param_env = &ctxt.param_env;
 333     debug!("drop_flag_effects_for_location({:?})", loc);
 334
 335     // first, move out of the RHS
 336     for mi in &move_data.loc_map[loc] {
 337         let path = mi.move_path_index(move_data);
 338         debug!("moving out of path {:?}", move_data.move_paths[path]);
 339
 340         // don't move out of non-Copy things
 341         let lvalue = &move_data.move_paths[path].lvalue;
 342         let ty = lvalue.ty(mir, tcx).to_ty(tcx);
 343         if !ty.moves_by_default(tcx, param_env, DUMMY_SP) {
 344             continue;
 345         }
 346
 347         on_all_children_bits(tcx, mir, move_data,
 348                              path,
 349                              |moi| callback(moi, DropFlagState::Absent))
 350     }
 351
 352     let block = &mir[loc.block];
 353     match block.statements.get(loc.statement_index) {
 354         Some(stmt) => match stmt.kind {
 355             mir::StatementKind::SetDiscriminant{ .. } => {
 356                 span_bug!(stmt.source_info.span, "SetDiscrimant should not exist during borrowck");
 357             }
 358             mir::StatementKind::Assign(ref lvalue, _) => {
 359                 debug!("drop_flag_effects: assignment {:?}", stmt);
 360                  on_lookup_result_bits(tcx, mir, move_data,
 361                                        move_data.rev_lookup.find(lvalue),
 362                                        |moi| callback(moi, DropFlagState::Present))
 363             }
 364             mir::StatementKind::StorageLive(_) |
 365             mir::StatementKind::StorageDead(_) |
 366             mir::StatementKind::InlineAsm { .. } |
 367             mir::StatementKind::Nop => {}
 368         },
 369         None => {
 370             debug!("drop_flag_effects: replace {:?}", block.terminator());
 371             match block.terminator().kind {
 372                 mir::TerminatorKind::DropAndReplace { ref location, .. } => {
 373                     on_lookup_result_bits(tcx, mir, move_data,
 374                                           move_data.rev_lookup.find(location),
 375                                           |moi| callback(moi, DropFlagState::Present))
 376                 }
 377                 _ => {
 378                     // other terminators do not contain move-ins
 379                 }
 380             }
 381         }
 382     }
 383 }