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::ty::RegionVid;
  12 use rustc_data_structures::indexed_vec::{Idx, IndexVec};
  13 use borrow_check::nll::type_check::Locations;
  14
  15 use std::fmt;
  16 use std::ops::Deref;
  17
  18 #[derive(Clone, Default)]
  19 crate struct ConstraintSet {
  20     constraints: IndexVec<ConstraintIndex, OutlivesConstraint>,
  21 }
  22
  23 impl ConstraintSet {
  24     pub fn push(&mut self, constraint: OutlivesConstraint) {
  25         debug!(
  26             "ConstraintSet::push({:?}: {:?} @ {:?}",
  27             constraint.sup, constraint.sub, constraint.locations
  28         );
  29         if constraint.sup == constraint.sub {
  30             // 'a: 'a is pretty uninteresting
  31             return;
  32         }
  33         self.constraints.push(constraint);
  34     }
  35 }
  36
  37 impl Deref for ConstraintSet {
  38     type Target = IndexVec<ConstraintIndex, OutlivesConstraint>;
  39
  40     fn deref(&self) -> &Self::Target { &self.constraints }
  41 }
  42
  43 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
  44 pub struct OutlivesConstraint {
  45     // NB. The ordering here is not significant for correctness, but
  46     // it is for convenience. Before we dump the constraints in the
  47     // debugging logs, we sort them, and we'd like the "super region"
  48     // to be first, etc. (In particular, span should remain last.)
  49     /// The region SUP must outlive SUB...
  50     pub sup: RegionVid,
  51
  52     /// Region that must be outlived.
  53     pub sub: RegionVid,
  54
  55     /// Where did this constraint arise?
  56     pub locations: Locations,
  57 }
  58
  59 impl fmt::Debug for OutlivesConstraint {
  60     fn fmt(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
  61         write!(
  62             formatter,
  63             "({:?}: {:?}) due to {:?}",
  64             self.sup, self.sub, self.locations
  65         )
  66     }
  67 }
  68
  69 newtype_index!(ConstraintIndex { DEBUG_FORMAT = "ConstraintIndex({})" });
  70
  71 crate struct ConstraintGraph {
  72     first_constraints: IndexVec<RegionVid, Option<ConstraintIndex>>,
  73     next_constraints: IndexVec<ConstraintIndex, Option<ConstraintIndex>>,
  74 }
  75
  76 impl ConstraintGraph {
  77     /// Constraint a graph where each region constraint `R1: R2` is
  78     /// treated as an edge `R2 -> R1`. This is useful for cheaply
  79     /// finding dirty constraints.
  80     crate fn new(set: &ConstraintSet, num_region_vars: usize) -> Self {
  81         let mut first_constraints = IndexVec::from_elem_n(None, num_region_vars);
  82         let mut next_constraints = IndexVec::from_elem(None, &set.constraints);
  83
  84         for (idx, constraint) in set.constraints.iter_enumerated().rev() {
  85             let mut head = &mut first_constraints[constraint.sub];
  86             let mut next = &mut next_constraints[idx];
  87             debug_assert!(next.is_none());
  88             *next = *head;
  89             *head = Some(idx);
  90         }
  91
  92         ConstraintGraph { first_constraints, next_constraints }
  93     }
  94
  95     /// Invokes `op` with the index of any constraints of the form
  96     /// `region_sup: region_sub`.  These are the constraints that must
  97     /// be reprocessed when the value of `R1` changes. If you think of
  98     /// each constraint `R1: R2` as an edge `R2 -> R1`, then this
  99     /// gives the set of successors to R2.
 100     crate fn for_each_dependent(
 101         &self,
 102         region_sub: RegionVid,
 103         mut op: impl FnMut(ConstraintIndex),
 104     ) {
 105         let mut p = self.first_constraints[region_sub];
 106         while let Some(dep_idx) = p {
 107             op(dep_idx);
 108             p = self.next_constraints[dep_idx];
 109         }
 110     }
 111 }
 112