src/librustc_mir/borrow_check/constraints/mod.rs

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