src/librustc_mir/borrow_check/nll/mod.rs

   1 use crate::borrow_check::borrow_set::BorrowSet;
   2 use crate::borrow_check::location::{LocationIndex, LocationTable};
   3 use crate::borrow_check::nll::facts::AllFactsExt;
   4 use crate::borrow_check::nll::type_check::{MirTypeckResults, MirTypeckRegionConstraints};
   5 use crate::borrow_check::nll::region_infer::values::RegionValueElements;
   6 use crate::dataflow::indexes::BorrowIndex;
   7 use crate::dataflow::move_paths::MoveData;
   8 use crate::dataflow::FlowAtLocation;
   9 use crate::dataflow::MaybeInitializedPlaces;
  10 use crate::transform::MirSource;
  11 use crate::borrow_check::Upvar;
  12 use rustc::hir::def_id::DefId;
  13 use rustc::infer::InferCtxt;
  14 use rustc::mir::{ClosureOutlivesSubject, ClosureRegionRequirements, Local, Body};
  15 use rustc::ty::{self, RegionKind, RegionVid};
  16 use rustc_errors::Diagnostic;
  17 use std::fmt::Debug;
  18 use std::env;
  19 use std::io;
  20 use std::path::PathBuf;
  21 use std::rc::Rc;
  22 use std::str::FromStr;
  23 use syntax::symbol::sym;
  24
  25 use self::mir_util::PassWhere;
  26 use polonius_engine::{Algorithm, Output};
  27 use crate::util as mir_util;
  28 use crate::util::pretty;
  29
  30 mod constraint_generation;
  31 pub mod explain_borrow;
  32 mod facts;
  33 mod invalidation;
  34 crate mod region_infer;
  35 mod renumber;
  36 crate mod type_check;
  37 mod universal_regions;
  38
  39 mod constraints;
  40 mod member_constraints;
  41
  42 use self::facts::AllFacts;
  43 use self::region_infer::RegionInferenceContext;
  44 use self::universal_regions::UniversalRegions;
  45
  46 /// Rewrites the regions in the MIR to use NLL variables, also
  47 /// scraping out the set of universal regions (e.g., region parameters)
  48 /// declared on the function. That set will need to be given to
  49 /// `compute_regions`.
  50 pub(in crate::borrow_check) fn replace_regions_in_mir<'cx, 'tcx>(
  51     infcx: &InferCtxt<'cx, 'tcx>,
  52     def_id: DefId,
  53     param_env: ty::ParamEnv<'tcx>,
  54     body: &mut Body<'tcx>,
  55 ) -> UniversalRegions<'tcx> {
  56     debug!("replace_regions_in_mir(def_id={:?})", def_id);
  57
  58     // Compute named region information. This also renumbers the inputs/outputs.
  59     let universal_regions = UniversalRegions::new(infcx, def_id, param_env);
  60
  61     // Replace all remaining regions with fresh inference variables.
  62     renumber::renumber_mir(infcx, body);
  63
  64     let source = MirSource::item(def_id);
  65     mir_util::dump_mir(infcx.tcx, None, "renumber", &0, source, body, |_, _| Ok(()));
  66
  67     universal_regions
  68 }
  69
  70 /// Computes the (non-lexical) regions from the input MIR.
  71 ///
  72 /// This may result in errors being reported.
  73 pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
  74     infcx: &InferCtxt<'cx, 'tcx>,
  75     def_id: DefId,
  76     universal_regions: UniversalRegions<'tcx>,
  77     body: &Body<'tcx>,
  78     upvars: &[Upvar],
  79     location_table: &LocationTable,
  80     param_env: ty::ParamEnv<'tcx>,
  81     flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'cx, 'tcx>>,
  82     move_data: &MoveData<'tcx>,
  83     borrow_set: &BorrowSet<'tcx>,
  84     errors_buffer: &mut Vec<Diagnostic>,
  85 ) -> (
  86     RegionInferenceContext<'tcx>,
  87     Option<Rc<Output<RegionVid, BorrowIndex, LocationIndex, Local>>>,
  88     Option<ClosureRegionRequirements<'tcx>>,
  89 ) {
  90     let mut all_facts = if AllFacts::enabled(infcx.tcx) {
  91         Some(AllFacts::default())
  92     } else {
  93         None
  94     };
  95
  96     let universal_regions = Rc::new(universal_regions);
  97
  98     let elements = &Rc::new(RegionValueElements::new(body));
  99
 100     // Run the MIR type-checker.
 101     let MirTypeckResults {
 102         constraints,
 103         universal_region_relations,
 104     } = type_check::type_check(
 105         infcx,
 106         param_env,
 107         body,
 108         def_id,
 109         &universal_regions,
 110         location_table,
 111         borrow_set,
 112         &mut all_facts,
 113         flow_inits,
 114         move_data,
 115         elements,
 116     );
 117
 118     if let Some(all_facts) = &mut all_facts {
 119         all_facts
 120             .universal_region
 121             .extend(universal_regions.universal_regions());
 122     }
 123
 124     // Create the region inference context, taking ownership of the
 125     // region inference data that was contained in `infcx`, and the
 126     // base constraints generated by the type-check.
 127     let var_origins = infcx.take_region_var_origins();
 128     let MirTypeckRegionConstraints {
 129         placeholder_indices,
 130         placeholder_index_to_region: _,
 131         mut liveness_constraints,
 132         outlives_constraints,
 133         member_constraints,
 134         closure_bounds_mapping,
 135         type_tests,
 136     } = constraints;
 137     let placeholder_indices = Rc::new(placeholder_indices);
 138
 139     constraint_generation::generate_constraints(
 140         infcx,
 141         &mut liveness_constraints,
 142         &mut all_facts,
 143         location_table,
 144         &body,
 145         borrow_set,
 146     );
 147
 148     let mut regioncx = RegionInferenceContext::new(
 149         var_origins,
 150         universal_regions,
 151         placeholder_indices,
 152         universal_region_relations,
 153         body,
 154         outlives_constraints,
 155         member_constraints,
 156         closure_bounds_mapping,
 157         type_tests,
 158         liveness_constraints,
 159         elements,
 160     );
 161
 162     // Generate various additional constraints.
 163     invalidation::generate_invalidates(
 164         infcx.tcx,
 165         &mut all_facts,
 166         location_table,
 167         &body,
 168         borrow_set,
 169     );
 170
 171     // Dump facts if requested.
 172     let polonius_output = all_facts.and_then(|all_facts| {
 173         if infcx.tcx.sess.opts.debugging_opts.nll_facts {
 174             let def_path = infcx.tcx.hir().def_path(def_id);
 175             let dir_path =
 176                 PathBuf::from("nll-facts").join(def_path.to_filename_friendly_no_crate());
 177             all_facts.write_to_dir(dir_path, location_table).unwrap();
 178         }
 179
 180         if infcx.tcx.sess.opts.debugging_opts.polonius {
 181             let algorithm = env::var("POLONIUS_ALGORITHM")
 182                 .unwrap_or_else(|_| String::from("Hybrid"));
 183             let algorithm = Algorithm::from_str(&algorithm).unwrap();
 184             debug!("compute_regions: using polonius algorithm {:?}", algorithm);
 185             Some(Rc::new(Output::compute(
 186                 &all_facts,
 187                 algorithm,
 188                 false,
 189             )))
 190         } else {
 191             None
 192         }
 193     });
 194
 195     // Solve the region constraints.
 196     let closure_region_requirements =
 197         regioncx.solve(infcx, &body, upvars, def_id, errors_buffer);
 198
 199     // Dump MIR results into a file, if that is enabled. This let us
 200     // write unit-tests, as well as helping with debugging.
 201     dump_mir_results(
 202         infcx,
 203         MirSource::item(def_id),
 204         &body,
 205         &regioncx,
 206         &closure_region_requirements,
 207     );
 208
 209     // We also have a `#[rustc_nll]` annotation that causes us to dump
 210     // information
 211     dump_annotation(infcx, &body, def_id, &regioncx, &closure_region_requirements, errors_buffer);
 212
 213     (regioncx, polonius_output, closure_region_requirements)
 214 }
 215
 216 fn dump_mir_results<'a, 'tcx>(
 217     infcx: &InferCtxt<'a, 'tcx>,
 218     source: MirSource<'tcx>,
 219     body: &Body<'tcx>,
 220     regioncx: &RegionInferenceContext<'_>,
 221     closure_region_requirements: &Option<ClosureRegionRequirements<'_>>,
 222 ) {
 223     if !mir_util::dump_enabled(infcx.tcx, "nll", source) {
 224         return;
 225     }
 226
 227     mir_util::dump_mir(
 228         infcx.tcx,
 229         None,
 230         "nll",
 231         &0,
 232         source,
 233         body,
 234         |pass_where, out| {
 235             match pass_where {
 236                 // Before the CFG, dump out the values for each region variable.
 237                 PassWhere::BeforeCFG => {
 238                     regioncx.dump_mir(out)?;
 239                     writeln!(out, "|")?;
 240
 241                     if let Some(closure_region_requirements) = closure_region_requirements {
 242                         writeln!(out, "| Free Region Constraints")?;
 243                         for_each_region_constraint(closure_region_requirements, &mut |msg| {
 244                             writeln!(out, "| {}", msg)
 245                         })?;
 246                         writeln!(out, "|")?;
 247                     }
 248                 }
 249
 250                 PassWhere::BeforeLocation(_) => {
 251                 }
 252
 253                 PassWhere::AfterTerminator(_) => {
 254                 }
 255
 256                 PassWhere::BeforeBlock(_) | PassWhere::AfterLocation(_) | PassWhere::AfterCFG => {}
 257             }
 258             Ok(())
 259         },
 260     );
 261
 262     // Also dump the inference graph constraints as a graphviz file.
 263     let _: io::Result<()> = try {
 264         let mut file =
 265             pretty::create_dump_file(infcx.tcx, "regioncx.all.dot", None, "nll", &0, source)?;
 266         regioncx.dump_graphviz_raw_constraints(&mut file)?;
 267     };
 268
 269     // Also dump the inference graph constraints as a graphviz file.
 270     let _: io::Result<()> = try {
 271         let mut file =
 272             pretty::create_dump_file(infcx.tcx, "regioncx.scc.dot", None, "nll", &0, source)?;
 273         regioncx.dump_graphviz_scc_constraints(&mut file)?;
 274     };
 275 }
 276
 277 fn dump_annotation<'a, 'tcx>(
 278     infcx: &InferCtxt<'a, 'tcx>,
 279     body: &Body<'tcx>,
 280     mir_def_id: DefId,
 281     regioncx: &RegionInferenceContext<'tcx>,
 282     closure_region_requirements: &Option<ClosureRegionRequirements<'_>>,
 283     errors_buffer: &mut Vec<Diagnostic>,
 284 ) {
 285     let tcx = infcx.tcx;
 286     let base_def_id = tcx.closure_base_def_id(mir_def_id);
 287     if !tcx.has_attr(base_def_id, sym::rustc_regions) {
 288         return;
 289     }
 290
 291     // When the enclosing function is tagged with `#[rustc_regions]`,
 292     // we dump out various bits of state as warnings. This is useful
 293     // for verifying that the compiler is behaving as expected.  These
 294     // warnings focus on the closure region requirements -- for
 295     // viewing the intraprocedural state, the -Zdump-mir output is
 296     // better.
 297
 298     if let Some(closure_region_requirements) = closure_region_requirements {
 299         let mut err = tcx
 300             .sess
 301             .diagnostic()
 302             .span_note_diag(body.span, "External requirements");
 303
 304         regioncx.annotate(tcx, &mut err);
 305
 306         err.note(&format!(
 307             "number of external vids: {}",
 308             closure_region_requirements.num_external_vids
 309         ));
 310
 311         // Dump the region constraints we are imposing *between* those
 312         // newly created variables.
 313         for_each_region_constraint(closure_region_requirements, &mut |msg| {
 314             err.note(msg);
 315             Ok(())
 316         }).unwrap();
 317
 318         err.buffer(errors_buffer);
 319     } else {
 320         let mut err = tcx
 321             .sess
 322             .diagnostic()
 323             .span_note_diag(body.span, "No external requirements");
 324         regioncx.annotate(tcx, &mut err);
 325
 326         err.buffer(errors_buffer);
 327     }
 328 }
 329
 330 fn for_each_region_constraint(
 331     closure_region_requirements: &ClosureRegionRequirements<'_>,
 332     with_msg: &mut dyn FnMut(&str) -> io::Result<()>,
 333 ) -> io::Result<()> {
 334     for req in &closure_region_requirements.outlives_requirements {
 335         let subject: &dyn Debug = match &req.subject {
 336             ClosureOutlivesSubject::Region(subject) => subject,
 337             ClosureOutlivesSubject::Ty(ty) => ty,
 338         };
 339         with_msg(&format!(
 340             "where {:?}: {:?}",
 341             subject, req.outlived_free_region,
 342         ))?;
 343     }
 344     Ok(())
 345 }
 346
 347 /// Right now, we piggy back on the `ReVar` to store our NLL inference
 348 /// regions. These are indexed with `RegionVid`. This method will
 349 /// assert that the region is a `ReVar` and extract its internal index.
 350 /// This is reasonable because in our MIR we replace all universal regions
 351 /// with inference variables.
 352 pub trait ToRegionVid {
 353     fn to_region_vid(self) -> RegionVid;
 354 }
 355
 356 impl<'tcx> ToRegionVid for &'tcx RegionKind {
 357     fn to_region_vid(self) -> RegionVid {
 358         if let ty::ReVar(vid) = self {
 359             *vid
 360         } else {
 361             bug!("region is not an ReVar: {:?}", self)
 362         }
 363     }
 364 }
 365
 366 impl ToRegionVid for RegionVid {
 367     fn to_region_vid(self) -> RegionVid {
 368         self
 369     }
 370 }
 371
 372 crate trait ConstraintDescription {
 373     fn description(&self) -> &'static str;
 374 }