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