compiler/rustc_borrowck/src/constraints/mod.rs

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