src/librustc_mir/borrow_check/nll/constraints/mod.rs

   1 use rustc::mir::ConstraintCategory;
   2 use rustc::ty::RegionVid;
   3 use rustc_data_structures::graph::scc::Sccs;
   4 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
   5 use borrow_check::nll::type_check::Locations;
   6
   7 use std::fmt;
   8 use std::ops::Deref;
   9
  10 crate mod graph;
  11
  12 #[derive(Clone, Default)]
  13 crate struct ConstraintSet {
  14     constraints: IndexVec<ConstraintIndex, OutlivesConstraint>,
  15 }
  16
  17 impl ConstraintSet {
  18     crate fn push(&mut self, constraint: OutlivesConstraint) {
  19         debug!(
  20             "ConstraintSet::push({:?}: {:?} @ {:?}",
  21             constraint.sup, constraint.sub, constraint.locations
  22         );
  23         if constraint.sup == constraint.sub {
  24             // 'a: 'a is pretty uninteresting
  25             return;
  26         }
  27         self.constraints.push(constraint);
  28     }
  29
  30     /// Constructs a "normal" graph from the constraint set; the graph makes it
  31     /// easy to find the constraints affecting a particular region.
  32     ///
  33     /// N.B., this graph contains a "frozen" view of the current
  34     /// constraints.  any new constraints added to the `ConstraintSet`
  35     /// after the graph is built will not be present in the graph.
  36     crate fn graph(&self, num_region_vars: usize) -> graph::NormalConstraintGraph {
  37         graph::ConstraintGraph::new(graph::Normal, self, num_region_vars)
  38     }
  39
  40     /// Like `graph`, but constraints a reverse graph where `R1: R2`
  41     /// represents an edge `R2 -> R1`.
  42     crate fn reverse_graph(&self, num_region_vars: usize) -> graph::ReverseConstraintGraph {
  43         graph::ConstraintGraph::new(graph::Reverse, self, num_region_vars)
  44     }
  45
  46     /// Compute cycles (SCCs) in the graph of regions. In particular,
  47     /// find all regions R1, R2 such that R1: R2 and R2: R1 and group
  48     /// them into an SCC, and find the relationships between SCCs.
  49     crate fn compute_sccs(
  50         &self,
  51         constraint_graph: &graph::NormalConstraintGraph,
  52         static_region: RegionVid,
  53     ) -> Sccs<RegionVid, ConstraintSccIndex> {
  54         let region_graph = &constraint_graph.region_graph(self, static_region);
  55         Sccs::new(region_graph)
  56     }
  57 }
  58
  59 impl Deref for ConstraintSet {
  60     type Target = IndexVec<ConstraintIndex, OutlivesConstraint>;
  61
  62     fn deref(&self) -> &Self::Target {
  63         &self.constraints
  64     }
  65 }
  66
  67 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
  68 pub struct OutlivesConstraint {
  69     // NB. The ordering here is not significant for correctness, but
  70     // it is for convenience. Before we dump the constraints in the
  71     // debugging logs, we sort them, and we'd like the "super region"
  72     // to be first, etc. (In particular, span should remain last.)
  73     /// The region SUP must outlive SUB...
  74     pub sup: RegionVid,
  75
  76     /// Region that must be outlived.
  77     pub sub: RegionVid,
  78
  79     /// Where did this constraint arise?
  80     pub locations: Locations,
  81
  82     /// What caused this constraint?
  83     pub category: ConstraintCategory,
  84 }
  85
  86 impl fmt::Debug for OutlivesConstraint {
  87     fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
  88         write!(
  89             formatter,
  90             "({:?}: {:?}) due to {:?}",
  91             self.sup, self.sub, self.locations
  92         )
  93     }
  94 }
  95
  96 newtype_index! {
  97     pub struct ConstraintIndex {
  98         DEBUG_FORMAT = "ConstraintIndex({})"
  99     }
 100 }
 101
 102 newtype_index! {
 103     pub struct ConstraintSccIndex {
 104         DEBUG_FORMAT = "ConstraintSccIndex({})"
 105     }
 106 }