src/librustc_mir/borrow_check/nll.rs

   1 //! The entry point of the NLL borrow checker.
   2
   3 use rustc::infer::InferCtxt;
   4 use rustc::mir::{
   5     BasicBlock, Body, BodyAndCache, ClosureOutlivesSubject, ClosureRegionRequirements, LocalKind,
   6     Location, Promoted, ReadOnlyBodyAndCache,
   7 };
   8 use rustc::ty::{self, RegionKind, RegionVid};
   9 use rustc_errors::Diagnostic;
  10 use rustc_hir::def_id::DefId;
  11 use rustc_index::vec::IndexVec;
  12 use rustc_span::symbol::sym;
  13 use std::env;
  14 use std::fmt::Debug;
  15 use std::io;
  16 use std::path::PathBuf;
  17 use std::rc::Rc;
  18 use std::str::FromStr;
  19
  20 use self::mir_util::PassWhere;
  21 use polonius_engine::{Algorithm, Output};
  22
  23 use crate::dataflow::move_paths::{InitKind, InitLocation, MoveData};
  24 use crate::dataflow::FlowAtLocation;
  25 use crate::dataflow::MaybeInitializedPlaces;
  26 use crate::transform::MirSource;
  27 use crate::util as mir_util;
  28 use crate::util::pretty;
  29
  30 use crate::borrow_check::{
  31     borrow_set::BorrowSet,
  32     constraint_generation,
  33     diagnostics::RegionErrors,
  34     facts::{AllFacts, AllFactsExt, RustcFacts},
  35     invalidation,
  36     location::LocationTable,
  37     region_infer::{values::RegionValueElements, RegionInferenceContext},
  38     renumber,
  39     type_check::{self, MirTypeckRegionConstraints, MirTypeckResults},
  40     universal_regions::UniversalRegions,
  41 };
  42
  43 crate type PoloniusOutput = Output<RustcFacts>;
  44
  45 /// The output of `nll::compute_regions`. This includes the computed `RegionInferenceContext`, any
  46 /// closure requirements to propagate, and any generated errors.
  47 crate struct NllOutput<'tcx> {
  48     pub regioncx: RegionInferenceContext<'tcx>,
  49     pub polonius_output: Option<Rc<PoloniusOutput>>,
  50     pub opt_closure_req: Option<ClosureRegionRequirements<'tcx>>,
  51     pub nll_errors: RegionErrors<'tcx>,
  52 }
  53
  54 /// Rewrites the regions in the MIR to use NLL variables, also scraping out the set of universal
  55 /// regions (e.g., region parameters) declared on the function. That set will need to be given to
  56 /// `compute_regions`.
  57 pub(in crate::borrow_check) fn replace_regions_in_mir<'cx, 'tcx>(
  58     infcx: &InferCtxt<'cx, 'tcx>,
  59     def_id: DefId,
  60     param_env: ty::ParamEnv<'tcx>,
  61     body: &mut BodyAndCache<'tcx>,
  62     promoted: &mut IndexVec<Promoted, BodyAndCache<'tcx>>,
  63 ) -> UniversalRegions<'tcx> {
  64     debug!("replace_regions_in_mir(def_id={:?})", def_id);
  65
  66     // Compute named region information. This also renumbers the inputs/outputs.
  67     let universal_regions = UniversalRegions::new(infcx, def_id, param_env);
  68
  69     // Replace all remaining regions with fresh inference variables.
  70     renumber::renumber_mir(infcx, body, promoted);
  71
  72     let source = MirSource::item(def_id);
  73     mir_util::dump_mir(infcx.tcx, None, "renumber", &0, source, body, |_, _| Ok(()));
  74
  75     universal_regions
  76 }
  77
  78 // This function populates an AllFacts instance with base facts related to
  79 // MovePaths and needed for the move analysis.
  80 fn populate_polonius_move_facts(
  81     all_facts: &mut AllFacts,
  82     move_data: &MoveData<'_>,
  83     location_table: &LocationTable,
  84     body: &Body<'_>,
  85 ) {
  86     all_facts
  87         .path_belongs_to_var
  88         .extend(move_data.rev_lookup.iter_locals_enumerated().map(|(v, &m)| (m, v)));
  89
  90     for (child, move_path) in move_data.move_paths.iter_enumerated() {
  91         all_facts
  92             .child
  93             .extend(move_path.parents(&move_data.move_paths).iter().map(|&parent| (child, parent)));
  94     }
  95
  96     // initialized_at
  97     for init in move_data.inits.iter() {
  98         match init.location {
  99             InitLocation::Statement(location) => {
 100                 let block_data = &body[location.block];
 101                 let is_terminator = location.statement_index == block_data.statements.len();
 102
 103                 if is_terminator && init.kind == InitKind::NonPanicPathOnly {
 104                     // We are at the terminator of an init that has a panic path,
 105                     // and where the init should not happen on panic
 106
 107                     for &successor in block_data.terminator().successors() {
 108                         if body[successor].is_cleanup {
 109                             continue;
 110                         }
 111
 112                         // The initialization happened in (or rather, when arriving at)
 113                         // the successors, but not in the unwind block.
 114                         let first_statement = Location { block: successor, statement_index: 0 };
 115                         all_facts
 116                             .initialized_at
 117                             .push((init.path, location_table.start_index(first_statement)));
 118                     }
 119                 } else {
 120                     // In all other cases, the initialization just happens at the
 121                     // midpoint, like any other effect.
 122                     all_facts.initialized_at.push((init.path, location_table.mid_index(location)));
 123                 }
 124             }
 125             // Arguments are initialized on function entry
 126             InitLocation::Argument(local) => {
 127                 assert!(body.local_kind(local) == LocalKind::Arg);
 128                 let fn_entry = Location { block: BasicBlock::from_u32(0u32), statement_index: 0 };
 129                 all_facts.initialized_at.push((init.path, location_table.start_index(fn_entry)));
 130             }
 131         }
 132     }
 133
 134     // moved_out_at
 135     // deinitialisation is assumed to always happen!
 136     all_facts
 137         .moved_out_at
 138         .extend(move_data.moves.iter().map(|mo| (mo.path, location_table.mid_index(mo.source))));
 139 }
 140
 141 /// Computes the (non-lexical) regions from the input MIR.
 142 ///
 143 /// This may result in errors being reported.
 144 pub(in crate::borrow_check) fn compute_regions<'cx, 'tcx>(
 145     infcx: &InferCtxt<'cx, 'tcx>,
 146     def_id: DefId,
 147     universal_regions: UniversalRegions<'tcx>,
 148     body: ReadOnlyBodyAndCache<'_, 'tcx>,
 149     promoted: &IndexVec<Promoted, ReadOnlyBodyAndCache<'_, 'tcx>>,
 150     location_table: &LocationTable,
 151     param_env: ty::ParamEnv<'tcx>,
 152     flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'cx, 'tcx>>,
 153     move_data: &MoveData<'tcx>,
 154     borrow_set: &BorrowSet<'tcx>,
 155 ) -> NllOutput<'tcx> {
 156     let mut all_facts = AllFacts::enabled(infcx.tcx).then_some(AllFacts::default());
 157
 158     let universal_regions = Rc::new(universal_regions);
 159
 160     let elements = &Rc::new(RegionValueElements::new(&body));
 161
 162     // Run the MIR type-checker.
 163     let MirTypeckResults { constraints, universal_region_relations } = type_check::type_check(
 164         infcx,
 165         param_env,
 166         body,
 167         promoted,
 168         def_id,
 169         &universal_regions,
 170         location_table,
 171         borrow_set,
 172         &mut all_facts,
 173         flow_inits,
 174         move_data,
 175         elements,
 176     );
 177
 178     if let Some(all_facts) = &mut all_facts {
 179         let _prof_timer = infcx.tcx.prof.generic_activity("polonius_fact_generation");
 180         all_facts.universal_region.extend(universal_regions.universal_regions());
 181         populate_polonius_move_facts(all_facts, move_data, location_table, &body);
 182
 183         // Emit universal regions facts, and their relations, for Polonius.
 184         //
 185         // 1: universal regions are modeled in Polonius as a pair:
 186         // - the universal region vid itself.
 187         // - a "placeholder loan" associated to this universal region. Since they don't exist in
 188         //   the `borrow_set`, their `BorrowIndex` are synthesized as the universal region index
 189         //   added to the existing number of loans, as if they succeeded them in the set.
 190         //
 191         let borrow_count = borrow_set.borrows.len();
 192         debug!(
 193             "compute_regions: polonius placeholders, num_universals={}, borrow_count={}",
 194             universal_regions.len(),
 195             borrow_count
 196         );
 197
 198         for universal_region in universal_regions.universal_regions() {
 199             let universal_region_idx = universal_region.index();
 200             let placeholder_loan_idx = borrow_count + universal_region_idx;
 201             all_facts.placeholder.push((universal_region, placeholder_loan_idx.into()));
 202         }
 203
 204         // 2: the universal region relations `outlives` constraints are emitted as
 205         //  `known_subset` facts.
 206         for (fr1, fr2) in universal_region_relations.known_outlives() {
 207             if fr1 != fr2 {
 208                 debug!(
 209                     "compute_regions: emitting polonius `known_subset` fr1={:?}, fr2={:?}",
 210                     fr1, fr2
 211                 );
 212                 all_facts.known_subset.push((*fr1, *fr2));
 213             }
 214         }
 215     }
 216
 217     // Create the region inference context, taking ownership of the
 218     // region inference data that was contained in `infcx`, and the
 219     // base constraints generated by the type-check.
 220     let var_origins = infcx.take_region_var_origins();
 221     let MirTypeckRegionConstraints {
 222         placeholder_indices,
 223         placeholder_index_to_region: _,
 224         mut liveness_constraints,
 225         outlives_constraints,
 226         member_constraints,
 227         closure_bounds_mapping,
 228         type_tests,
 229     } = constraints;
 230     let placeholder_indices = Rc::new(placeholder_indices);
 231
 232     constraint_generation::generate_constraints(
 233         infcx,
 234         param_env,
 235         &mut liveness_constraints,
 236         &mut all_facts,
 237         location_table,
 238         &body,
 239         borrow_set,
 240     );
 241
 242     let mut regioncx = RegionInferenceContext::new(
 243         var_origins,
 244         universal_regions,
 245         placeholder_indices,
 246         universal_region_relations,
 247         outlives_constraints,
 248         member_constraints,
 249         closure_bounds_mapping,
 250         type_tests,
 251         liveness_constraints,
 252         elements,
 253     );
 254
 255     // Generate various additional constraints.
 256     invalidation::generate_invalidates(
 257         infcx.tcx,
 258         param_env,
 259         &mut all_facts,
 260         location_table,
 261         body,
 262         borrow_set,
 263     );
 264
 265     // Dump facts if requested.
 266     let polonius_output = all_facts.and_then(|all_facts| {
 267         if infcx.tcx.sess.opts.debugging_opts.nll_facts {
 268             let def_path = infcx.tcx.hir().def_path(def_id);
 269             let dir_path =
 270                 PathBuf::from("nll-facts").join(def_path.to_filename_friendly_no_crate());
 271             all_facts.write_to_dir(dir_path, location_table).unwrap();
 272         }
 273
 274         if infcx.tcx.sess.opts.debugging_opts.polonius {
 275             let algorithm =
 276                 env::var("POLONIUS_ALGORITHM").unwrap_or_else(|_| String::from("Naive"));
 277             let algorithm = Algorithm::from_str(&algorithm).unwrap();
 278             debug!("compute_regions: using polonius algorithm {:?}", algorithm);
 279             let _prof_timer = infcx.tcx.prof.generic_activity("polonius_analysis");
 280             Some(Rc::new(Output::compute(&all_facts, algorithm, false)))
 281         } else {
 282             None
 283         }
 284     });
 285
 286     // Solve the region constraints.
 287     let (closure_region_requirements, nll_errors) =
 288         regioncx.solve(infcx, &body, def_id, polonius_output.clone());
 289
 290     NllOutput {
 291         regioncx,
 292         polonius_output,
 293         opt_closure_req: closure_region_requirements,
 294         nll_errors,
 295     }
 296 }
 297
 298 pub(super) fn dump_mir_results<'a, 'tcx>(
 299     infcx: &InferCtxt<'a, 'tcx>,
 300     source: MirSource<'tcx>,
 301     body: &Body<'tcx>,
 302     regioncx: &RegionInferenceContext<'_>,
 303     closure_region_requirements: &Option<ClosureRegionRequirements<'_>>,
 304 ) {
 305     if !mir_util::dump_enabled(infcx.tcx, "nll", source) {
 306         return;
 307     }
 308
 309     mir_util::dump_mir(infcx.tcx, None, "nll", &0, source, body, |pass_where, out| {
 310         match pass_where {
 311             // Before the CFG, dump out the values for each region variable.
 312             PassWhere::BeforeCFG => {
 313                 regioncx.dump_mir(out)?;
 314                 writeln!(out, "|")?;
 315
 316                 if let Some(closure_region_requirements) = closure_region_requirements {
 317                     writeln!(out, "| Free Region Constraints")?;
 318                     for_each_region_constraint(closure_region_requirements, &mut |msg| {
 319                         writeln!(out, "| {}", msg)
 320                     })?;
 321                     writeln!(out, "|")?;
 322                 }
 323             }
 324
 325             PassWhere::BeforeLocation(_) => {}
 326
 327             PassWhere::AfterTerminator(_) => {}
 328
 329             PassWhere::BeforeBlock(_) | PassWhere::AfterLocation(_) | PassWhere::AfterCFG => {}
 330         }
 331         Ok(())
 332     });
 333
 334     // Also dump the inference graph constraints as a graphviz file.
 335     let _: io::Result<()> = try {
 336         let mut file =
 337             pretty::create_dump_file(infcx.tcx, "regioncx.all.dot", None, "nll", &0, source)?;
 338         regioncx.dump_graphviz_raw_constraints(&mut file)?;
 339     };
 340
 341     // Also dump the inference graph constraints as a graphviz file.
 342     let _: io::Result<()> = try {
 343         let mut file =
 344             pretty::create_dump_file(infcx.tcx, "regioncx.scc.dot", None, "nll", &0, source)?;
 345         regioncx.dump_graphviz_scc_constraints(&mut file)?;
 346     };
 347 }
 348
 349 pub(super) fn dump_annotation<'a, 'tcx>(
 350     infcx: &InferCtxt<'a, 'tcx>,
 351     body: &Body<'tcx>,
 352     mir_def_id: DefId,
 353     regioncx: &RegionInferenceContext<'tcx>,
 354     closure_region_requirements: &Option<ClosureRegionRequirements<'_>>,
 355     errors_buffer: &mut Vec<Diagnostic>,
 356 ) {
 357     let tcx = infcx.tcx;
 358     let base_def_id = tcx.closure_base_def_id(mir_def_id);
 359     if !tcx.has_attr(base_def_id, sym::rustc_regions) {
 360         return;
 361     }
 362
 363     // When the enclosing function is tagged with `#[rustc_regions]`,
 364     // we dump out various bits of state as warnings. This is useful
 365     // for verifying that the compiler is behaving as expected.  These
 366     // warnings focus on the closure region requirements -- for
 367     // viewing the intraprocedural state, the -Zdump-mir output is
 368     // better.
 369
 370     if let Some(closure_region_requirements) = closure_region_requirements {
 371         let mut err = tcx.sess.diagnostic().span_note_diag(body.span, "External requirements");
 372
 373         regioncx.annotate(tcx, &mut err);
 374
 375         err.note(&format!(
 376             "number of external vids: {}",
 377             closure_region_requirements.num_external_vids
 378         ));
 379
 380         // Dump the region constraints we are imposing *between* those
 381         // newly created variables.
 382         for_each_region_constraint(closure_region_requirements, &mut |msg| {
 383             err.note(msg);
 384             Ok(())
 385         })
 386         .unwrap();
 387
 388         err.buffer(errors_buffer);
 389     } else {
 390         let mut err = tcx.sess.diagnostic().span_note_diag(body.span, "No external requirements");
 391         regioncx.annotate(tcx, &mut err);
 392
 393         err.buffer(errors_buffer);
 394     }
 395 }
 396
 397 fn for_each_region_constraint(
 398     closure_region_requirements: &ClosureRegionRequirements<'_>,
 399     with_msg: &mut dyn FnMut(&str) -> io::Result<()>,
 400 ) -> io::Result<()> {
 401     for req in &closure_region_requirements.outlives_requirements {
 402         let subject: &dyn Debug = match &req.subject {
 403             ClosureOutlivesSubject::Region(subject) => subject,
 404             ClosureOutlivesSubject::Ty(ty) => ty,
 405         };
 406         with_msg(&format!("where {:?}: {:?}", subject, req.outlived_free_region,))?;
 407     }
 408     Ok(())
 409 }
 410
 411 /// Right now, we piggy back on the `ReVar` to store our NLL inference
 412 /// regions. These are indexed with `RegionVid`. This method will
 413 /// assert that the region is a `ReVar` and extract its internal index.
 414 /// This is reasonable because in our MIR we replace all universal regions
 415 /// with inference variables.
 416 pub trait ToRegionVid {
 417     fn to_region_vid(self) -> RegionVid;
 418 }
 419
 420 impl<'tcx> ToRegionVid for &'tcx RegionKind {
 421     fn to_region_vid(self) -> RegionVid {
 422         if let ty::ReVar(vid) = self { *vid } else { bug!("region is not an ReVar: {:?}", self) }
 423     }
 424 }
 425
 426 impl ToRegionVid for RegionVid {
 427     fn to_region_vid(self) -> RegionVid {
 428         self
 429     }
 430 }
 431
 432 crate trait ConstraintDescription {
 433     fn description(&self) -> &'static str;
 434 }