src/librustc_mir/borrow_check/constraints/mod.rs

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