src/librustc_mir/borrow_check/nll/type_check/liveness/mod.rs

   1 use crate::borrow_check::location::LocationTable;
   2 use crate::borrow_check::nll::region_infer::values::RegionValueElements;
   3 use crate::borrow_check::nll::constraints::ConstraintSet;
   4 use crate::borrow_check::nll::NllLivenessMap;
   5 use crate::borrow_check::nll::universal_regions::UniversalRegions;
   6 use crate::dataflow::move_paths::MoveData;
   7 use crate::dataflow::MaybeInitializedPlaces;
   8 use crate::dataflow::FlowAtLocation;
   9 use rustc::mir::Mir;
  10 use rustc::ty::RegionVid;
  11 use rustc_data_structures::fx::FxHashSet;
  12 use std::rc::Rc;
  13
  14 use super::TypeChecker;
  15
  16 crate mod liveness_map;
  17 mod local_use_map;
  18 mod trace;
  19
  20 /// Combines liveness analysis with initialization analysis to
  21 /// determine which variables are live at which points, both due to
  22 /// ordinary uses and drops. Returns a set of (ty, location) pairs
  23 /// that indicate which types must be live at which point in the CFG.
  24 /// This vector is consumed by `constraint_generation`.
  25 ///
  26 /// N.B., this computation requires normalization; therefore, it must be
  27 /// performed before
  28 pub(super) fn generate<'gcx, 'tcx>(
  29     typeck: &mut TypeChecker<'_, 'gcx, 'tcx>,
  30     mir: &Mir<'tcx>,
  31     elements: &Rc<RegionValueElements>,
  32     flow_inits: &mut FlowAtLocation<'tcx, MaybeInitializedPlaces<'_, 'gcx, 'tcx>>,
  33     move_data: &MoveData<'tcx>,
  34     location_table: &LocationTable,
  35 ) {
  36     debug!("liveness::generate");
  37     let free_regions = {
  38         let borrowck_context = typeck.borrowck_context.as_ref().unwrap();
  39         regions_that_outlive_free_regions(
  40             typeck.infcx.num_region_vars(),
  41             &borrowck_context.universal_regions,
  42             &borrowck_context.constraints.outlives_constraints,
  43         )
  44     };
  45     let liveness_map = NllLivenessMap::compute(typeck.tcx(), &free_regions, mir);
  46     trace::trace(typeck, mir, elements, flow_inits, move_data, &liveness_map, location_table);
  47 }
  48
  49 /// Computes all regions that are (currently) known to outlive free
  50 /// regions. For these regions, we do not need to compute
  51 /// liveness, since the outlives constraints will ensure that they
  52 /// are live over the whole fn body anyhow.
  53 fn regions_that_outlive_free_regions(
  54     num_region_vars: usize,
  55     universal_regions: &UniversalRegions<'tcx>,
  56     constraint_set: &ConstraintSet,
  57 ) -> FxHashSet<RegionVid> {
  58     // Build a graph of the outlives constraints thus far. This is
  59     // a reverse graph, so for each constraint `R1: R2` we have an
  60     // edge `R2 -> R1`. Therefore, if we find all regions
  61     // reachable from each free region, we will have all the
  62     // regions that are forced to outlive some free region.
  63     let rev_constraint_graph = constraint_set.reverse_graph(num_region_vars);
  64     let fr_static = universal_regions.fr_static;
  65     let rev_region_graph = rev_constraint_graph.region_graph(constraint_set, fr_static);
  66
  67     // Stack for the depth-first search. Start out with all the free regions.
  68     let mut stack: Vec<_> = universal_regions.universal_regions().collect();
  69
  70     // Set of all free regions, plus anything that outlives them. Initially
  71     // just contains the free regions.
  72     let mut outlives_free_region: FxHashSet<_> = stack.iter().cloned().collect();
  73
  74     // Do the DFS -- for each thing in the stack, find all things
  75     // that outlive it and add them to the set. If they are not,
  76     // push them onto the stack for later.
  77     while let Some(sub_region) = stack.pop() {
  78         stack.extend(
  79             rev_region_graph
  80                 .outgoing_regions(sub_region)
  81                 .filter(|&r| outlives_free_region.insert(r)),
  82         );
  83     }
  84
  85     // Return the final set of things we visited.
  86     outlives_free_region
  87 }