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