src/librustc_mir/transform/nll/mod.rs

   1 // Copyright 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 rustc::hir::def_id::DefId;
  12 use rustc::mir::Mir;
  13 use rustc::infer::InferCtxt;
  14 use rustc::ty::{self, RegionKind};
  15 use rustc::util::nodemap::FxHashMap;
  16 use rustc_data_structures::indexed_vec::Idx;
  17 use std::collections::BTreeSet;
  18 use transform::MirSource;
  19 use util::liveness::{self, LivenessMode, LivenessResult, LocalSet};
  20
  21 use util as mir_util;
  22 use self::mir_util::PassWhere;
  23
  24 mod constraint_generation;
  25 mod free_regions;
  26 mod subtype;
  27
  28 pub(crate) mod region_infer;
  29 use self::region_infer::RegionInferenceContext;
  30
  31 mod renumber;
  32
  33 /// Computes the (non-lexical) regions from the input MIR.
  34 ///
  35 /// This may result in errors being reported.
  36 pub fn compute_regions<'a, 'gcx, 'tcx>(
  37     infcx: &InferCtxt<'a, 'gcx, 'tcx>,
  38     def_id: DefId,
  39     mir: &mut Mir<'tcx>,
  40 ) -> RegionInferenceContext<'tcx> {
  41     // Compute named region information.
  42     let free_regions = &free_regions::free_regions(infcx, def_id);
  43
  44     // Replace all regions with fresh inference variables.
  45     let num_region_variables = renumber::renumber_mir(infcx, free_regions, mir);
  46
  47     // Compute what is live where.
  48     let liveness = &LivenessResults {
  49         regular: liveness::liveness_of_locals(
  50             &mir,
  51             LivenessMode {
  52                 include_regular_use: true,
  53                 include_drops: false,
  54             },
  55         ),
  56
  57         drop: liveness::liveness_of_locals(
  58             &mir,
  59             LivenessMode {
  60                 include_regular_use: false,
  61                 include_drops: true,
  62             },
  63         ),
  64     };
  65
  66     // Create the region inference context, generate the constraints,
  67     // and then solve them.
  68     let mut regioncx = RegionInferenceContext::new(free_regions, num_region_variables, mir);
  69     let param_env = infcx.tcx.param_env(def_id);
  70     constraint_generation::generate_constraints(infcx, &mut regioncx, &mir, param_env, liveness);
  71     regioncx.solve(infcx, &mir);
  72
  73     // Dump MIR results into a file, if that is enabled. This let us
  74     // write unit-tests.
  75     dump_mir_results(infcx, liveness, MirSource::item(def_id), &mir, &regioncx);
  76
  77     regioncx
  78 }
  79
  80 struct LivenessResults {
  81     regular: LivenessResult,
  82     drop: LivenessResult,
  83 }
  84
  85 fn dump_mir_results<'a, 'gcx, 'tcx>(
  86     infcx: &InferCtxt<'a, 'gcx, 'tcx>,
  87     liveness: &LivenessResults,
  88     source: MirSource,
  89     mir: &Mir<'tcx>,
  90     regioncx: &RegionInferenceContext,
  91 ) {
  92     if !mir_util::dump_enabled(infcx.tcx, "nll", source) {
  93         return;
  94     }
  95
  96     let regular_liveness_per_location: FxHashMap<_, _> = mir.basic_blocks()
  97         .indices()
  98         .flat_map(|bb| {
  99             let mut results = vec![];
 100             liveness
 101                 .regular
 102                 .simulate_block(&mir, bb, |location, local_set| {
 103                     results.push((location, local_set.clone()));
 104                 });
 105             results
 106         })
 107         .collect();
 108
 109     let drop_liveness_per_location: FxHashMap<_, _> = mir.basic_blocks()
 110         .indices()
 111         .flat_map(|bb| {
 112             let mut results = vec![];
 113             liveness
 114                 .drop
 115                 .simulate_block(&mir, bb, |location, local_set| {
 116                     results.push((location, local_set.clone()));
 117                 });
 118             results
 119         })
 120         .collect();
 121
 122     mir_util::dump_mir(infcx.tcx, None, "nll", &0, source, mir, |pass_where, out| {
 123         match pass_where {
 124             // Before the CFG, dump out the values for each region variable.
 125             PassWhere::BeforeCFG => for region in regioncx.regions() {
 126                 writeln!(
 127                     out,
 128                     "| {:?}: {:?}",
 129                     region,
 130                     regioncx.region_value(region)
 131                 )?;
 132             },
 133
 134             // Before each basic block, dump out the values
 135             // that are live on entry to the basic block.
 136             PassWhere::BeforeBlock(bb) => {
 137                 let s = live_variable_set(&liveness.regular.ins[bb], &liveness.drop.ins[bb]);
 138                 writeln!(out, "    | Live variables on entry to {:?}: {}", bb, s)?;
 139             }
 140
 141             PassWhere::InCFG(location) => {
 142                 let s = live_variable_set(
 143                     &regular_liveness_per_location[&location],
 144                     &drop_liveness_per_location[&location],
 145                 );
 146                 writeln!(out, "            | Live variables at {:?}: {}", location, s)?;
 147             }
 148
 149             PassWhere::AfterCFG => {}
 150         }
 151         Ok(())
 152     });
 153 }
 154
 155 newtype_index!(RegionIndex {
 156     DEBUG_FORMAT = "'_#{}r",
 157 });
 158
 159 /// Right now, we piggy back on the `ReVar` to store our NLL inference
 160 /// regions. These are indexed with `RegionIndex`. This method will
 161 /// assert that the region is a `ReVar` and convert the internal index
 162 /// into a `RegionIndex`. This is reasonable because in our MIR we
 163 /// replace all free regions with inference variables.
 164 pub trait ToRegionIndex {
 165     fn to_region_index(&self) -> RegionIndex;
 166 }
 167
 168 impl ToRegionIndex for RegionKind {
 169     fn to_region_index(&self) -> RegionIndex {
 170         if let &ty::ReVar(vid) = self {
 171             RegionIndex::new(vid.index as usize)
 172         } else {
 173             bug!("region is not an ReVar: {:?}", self)
 174         }
 175     }
 176 }
 177
 178 fn live_variable_set(regular: &LocalSet, drops: &LocalSet) -> String {
 179     // sort and deduplicate:
 180     let all_locals: BTreeSet<_> = regular.iter().chain(drops.iter()).collect();
 181
 182     // construct a string with each local, including `(drop)` if it is
 183     // only dropped, versus a regular use.
 184     let mut string = String::new();
 185     for local in all_locals {
 186         string.push_str(&format!("{:?}", local));
 187
 188         if !regular.contains(&local) {
 189             assert!(drops.contains(&local));
 190             string.push_str(" (drop)");
 191         }
 192
 193         string.push_str(", ");
 194     }
 195
 196     let len = if string.is_empty() {
 197         0
 198     } else {
 199         string.len() - 2
 200     };
 201
 202     format!("[{}]", &string[..len])
 203 }