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

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