src/librustc_mir/dataflow/drop_flag_effects.rs

   1 // Copyright 2012-2017 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 syntax::ast::{self, MetaItem};
  12 use syntax_pos::DUMMY_SP;
  13
  14
  15 use rustc::mir::{self, Mir, BasicBlock, Location};
  16 use rustc::session::Session;
  17 use rustc::ty::{self, TyCtxt};
  18 use util::elaborate_drops::DropFlagState;
  19 use rustc_data_structures::indexed_set::{IdxSet};
  20
  21 use std::fmt;
  22
  23 use super::{Dataflow, DataflowBuilder, DataflowAnalysis};
  24 use super::{BitDenotation, DataflowOperator, DataflowResults};
  25 use super::indexes::MovePathIndex;
  26 use super::move_paths::{MoveData, LookupResult};
  27
  28 pub(crate) fn has_rustc_mir_with(attrs: &[ast::Attribute], name: &str) -> Option<MetaItem> {
  29     for attr in attrs {
  30         if attr.check_name("rustc_mir") {
  31             let items = attr.meta_item_list();
  32             for item in items.iter().flat_map(|l| l.iter()) {
  33                 match item.meta_item() {
  34                     Some(mi) if mi.check_name(name) => return Some(mi.clone()),
  35                     _ => continue
  36                 }
  37             }
  38         }
  39     }
  40     return None;
  41 }
  42
  43 pub struct MoveDataParamEnv<'tcx> {
  44     pub(crate) move_data: MoveData<'tcx>,
  45     pub(crate) param_env: ty::ParamEnv<'tcx>,
  46 }
  47
  48 pub(crate) fn do_dataflow<'a, 'tcx, BD, P>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
  49                                 mir: &Mir<'tcx>,
  50                                 node_id: ast::NodeId,
  51                                 attributes: &[ast::Attribute],
  52                                 dead_unwinds: &IdxSet<BasicBlock>,
  53                                 bd: BD,
  54                                 p: P)
  55                                 -> DataflowResults<BD>
  56     where BD: BitDenotation<Idx=MovePathIndex> + DataflowOperator,
  57           P: Fn(&BD, BD::Idx) -> &fmt::Debug
  58 {
  59     let name_found = |sess: &Session, attrs: &[ast::Attribute], name| -> Option<String> {
  60         if let Some(item) = has_rustc_mir_with(attrs, name) {
  61             if let Some(s) = item.value_str() {
  62                 return Some(s.to_string())
  63             } else {
  64                 sess.span_err(
  65                     item.span,
  66                     &format!("{} attribute requires a path", item.name()));
  67                 return None;
  68             }
  69         }
  70         return None;
  71     };
  72
  73     let print_preflow_to =
  74         name_found(tcx.sess, attributes, "borrowck_graphviz_preflow");
  75     let print_postflow_to =
  76         name_found(tcx.sess, attributes, "borrowck_graphviz_postflow");
  77
  78     let mut mbcx = DataflowBuilder {
  79         node_id: node_id,
  80         print_preflow_to: print_preflow_to,
  81         print_postflow_to: print_postflow_to,
  82         flow_state: DataflowAnalysis::new(tcx, mir, dead_unwinds, bd),
  83     };
  84
  85     mbcx.dataflow(p);
  86     mbcx.flow_state.results()
  87 }
  88
  89 pub fn move_path_children_matching<'tcx, F>(move_data: &MoveData<'tcx>,
  90                                         path: MovePathIndex,
  91                                         mut cond: F)
  92                                         -> Option<MovePathIndex>
  93     where F: FnMut(&mir::LvalueProjection<'tcx>) -> bool
  94 {
  95     let mut next_child = move_data.move_paths[path].first_child;
  96     while let Some(child_index) = next_child {
  97         match move_data.move_paths[child_index].lvalue {
  98             mir::Lvalue::Projection(ref proj) => {
  99                 if cond(proj) {
 100                     return Some(child_index)
 101                 }
 102             }
 103             _ => {}
 104         }
 105         next_child = move_data.move_paths[child_index].next_sibling;
 106     }
 107
 108     None
 109 }
 110
 111 /// When enumerating the child fragments of a path, don't recurse into
 112 /// paths (1.) past arrays, slices, and pointers, nor (2.) into a type
 113 /// that implements `Drop`.
 114 ///
 115 /// Lvalues behind references or arrays are not tracked by elaboration
 116 /// and are always assumed to be initialized when accessible. As
 117 /// references and indexes can be reseated, trying to track them can
 118 /// only lead to trouble.
 119 ///
 120 /// Lvalues behind ADT's with a Drop impl are not tracked by
 121 /// elaboration since they can never have a drop-flag state that
 122 /// differs from that of the parent with the Drop impl.
 123 ///
 124 /// In both cases, the contents can only be accessed if and only if
 125 /// their parents are initialized. This implies for example that there
 126 /// is no need to maintain separate drop flags to track such state.
 127 ///
 128 /// FIXME: we have to do something for moving slice patterns.
 129 fn lvalue_contents_drop_state_cannot_differ<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>,
 130                                                       mir: &Mir<'tcx>,
 131                                                       lv: &mir::Lvalue<'tcx>) -> bool {
 132     let ty = lv.ty(mir, tcx).to_ty(tcx);
 133     match ty.sty {
 134         ty::TyArray(..) | ty::TySlice(..) | ty::TyRef(..) | ty::TyRawPtr(..) => {
 135             debug!("lvalue_contents_drop_state_cannot_differ lv: {:?} ty: {:?} refd => true",
 136                    lv, ty);
 137             true
 138         }
 139         ty::TyAdt(def, _) if (def.has_dtor(tcx) && !def.is_box()) || def.is_union() => {
 140             debug!("lvalue_contents_drop_state_cannot_differ lv: {:?} ty: {:?} Drop => true",
 141                    lv, ty);
 142             true
 143         }
 144         _ => {
 145             false
 146         }
 147     }
 148 }
 149
 150 pub(crate) fn on_lookup_result_bits<'a, 'tcx, F>(
 151     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 152     mir: &Mir<'tcx>,
 153     move_data: &MoveData<'tcx>,
 154     lookup_result: LookupResult,
 155     each_child: F)
 156     where F: FnMut(MovePathIndex)
 157 {
 158     match lookup_result {
 159         LookupResult::Parent(..) => {
 160             // access to untracked value - do not touch children
 161         }
 162         LookupResult::Exact(e) => {
 163             on_all_children_bits(tcx, mir, move_data, e, each_child)
 164         }
 165     }
 166 }
 167
 168 pub(crate) fn on_all_children_bits<'a, 'tcx, F>(
 169     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 170     mir: &Mir<'tcx>,
 171     move_data: &MoveData<'tcx>,
 172     move_path_index: MovePathIndex,
 173     mut each_child: F)
 174     where F: FnMut(MovePathIndex)
 175 {
 176     fn is_terminal_path<'a, 'tcx>(
 177         tcx: TyCtxt<'a, 'tcx, 'tcx>,
 178         mir: &Mir<'tcx>,
 179         move_data: &MoveData<'tcx>,
 180         path: MovePathIndex) -> bool
 181     {
 182         lvalue_contents_drop_state_cannot_differ(
 183             tcx, mir, &move_data.move_paths[path].lvalue)
 184     }
 185
 186     fn on_all_children_bits<'a, 'tcx, F>(
 187         tcx: TyCtxt<'a, 'tcx, 'tcx>,
 188         mir: &Mir<'tcx>,
 189         move_data: &MoveData<'tcx>,
 190         move_path_index: MovePathIndex,
 191         each_child: &mut F)
 192         where F: FnMut(MovePathIndex)
 193     {
 194         each_child(move_path_index);
 195
 196         if is_terminal_path(tcx, mir, move_data, move_path_index) {
 197             return
 198         }
 199
 200         let mut next_child_index = move_data.move_paths[move_path_index].first_child;
 201         while let Some(child_index) = next_child_index {
 202             on_all_children_bits(tcx, mir, move_data, child_index, each_child);
 203             next_child_index = move_data.move_paths[child_index].next_sibling;
 204         }
 205     }
 206     on_all_children_bits(tcx, mir, move_data, move_path_index, &mut each_child);
 207 }
 208
 209 pub(crate) fn on_all_drop_children_bits<'a, 'tcx, F>(
 210     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 211     mir: &Mir<'tcx>,
 212     ctxt: &MoveDataParamEnv<'tcx>,
 213     path: MovePathIndex,
 214     mut each_child: F)
 215     where F: FnMut(MovePathIndex)
 216 {
 217     on_all_children_bits(tcx, mir, &ctxt.move_data, path, |child| {
 218         let lvalue = &ctxt.move_data.move_paths[path].lvalue;
 219         let ty = lvalue.ty(mir, tcx).to_ty(tcx);
 220         debug!("on_all_drop_children_bits({:?}, {:?} : {:?})", path, lvalue, ty);
 221
 222         if ty.needs_drop(tcx, ctxt.param_env) {
 223             each_child(child);
 224         } else {
 225             debug!("on_all_drop_children_bits - skipping")
 226         }
 227     })
 228 }
 229
 230 pub(crate) fn drop_flag_effects_for_function_entry<'a, 'tcx, F>(
 231     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 232     mir: &Mir<'tcx>,
 233     ctxt: &MoveDataParamEnv<'tcx>,
 234     mut callback: F)
 235     where F: FnMut(MovePathIndex, DropFlagState)
 236 {
 237     let move_data = &ctxt.move_data;
 238     for arg in mir.args_iter() {
 239         let lvalue = mir::Lvalue::Local(arg);
 240         let lookup_result = move_data.rev_lookup.find(&lvalue);
 241         on_lookup_result_bits(tcx, mir, move_data,
 242                               lookup_result,
 243                               |moi| callback(moi, DropFlagState::Present));
 244     }
 245 }
 246
 247 pub(crate) fn drop_flag_effects_for_location<'a, 'tcx, F>(
 248     tcx: TyCtxt<'a, 'tcx, 'tcx>,
 249     mir: &Mir<'tcx>,
 250     ctxt: &MoveDataParamEnv<'tcx>,
 251     loc: Location,
 252     mut callback: F)
 253     where F: FnMut(MovePathIndex, DropFlagState)
 254 {
 255     let move_data = &ctxt.move_data;
 256     let param_env = ctxt.param_env;
 257     debug!("drop_flag_effects_for_location({:?})", loc);
 258
 259     // first, move out of the RHS
 260     for mi in &move_data.loc_map[loc] {
 261         let path = mi.move_path_index(move_data);
 262         debug!("moving out of path {:?}", move_data.move_paths[path]);
 263
 264         // don't move out of non-Copy things
 265         let lvalue = &move_data.move_paths[path].lvalue;
 266         let ty = lvalue.ty(mir, tcx).to_ty(tcx);
 267         if !ty.moves_by_default(tcx, param_env, DUMMY_SP) {
 268             continue;
 269         }
 270
 271         on_all_children_bits(tcx, mir, move_data,
 272                              path,
 273                              |moi| callback(moi, DropFlagState::Absent))
 274     }
 275
 276     let block = &mir[loc.block];
 277     match block.statements.get(loc.statement_index) {
 278         Some(stmt) => match stmt.kind {
 279             mir::StatementKind::SetDiscriminant{ .. } => {
 280                 span_bug!(stmt.source_info.span, "SetDiscrimant should not exist during borrowck");
 281             }
 282             mir::StatementKind::Assign(ref lvalue, _) => {
 283                 debug!("drop_flag_effects: assignment {:?}", stmt);
 284                  on_lookup_result_bits(tcx, mir, move_data,
 285                                        move_data.rev_lookup.find(lvalue),
 286                                        |moi| callback(moi, DropFlagState::Present))
 287             }
 288             mir::StatementKind::StorageLive(_) |
 289             mir::StatementKind::StorageDead(_) |
 290             mir::StatementKind::InlineAsm { .. } |
 291             mir::StatementKind::EndRegion(_) |
 292             mir::StatementKind::Nop => {}
 293         },
 294         None => {
 295             debug!("drop_flag_effects: replace {:?}", block.terminator());
 296             match block.terminator().kind {
 297                 mir::TerminatorKind::DropAndReplace { ref location, .. } => {
 298                     on_lookup_result_bits(tcx, mir, move_data,
 299                                           move_data.rev_lookup.find(location),
 300                                           |moi| callback(moi, DropFlagState::Present))
 301                 }
 302                 _ => {
 303                     // other terminators do not contain move-ins
 304                 }
 305             }
 306         }
 307     }
 308 }