src/librustc_infer/infer/region_constraints/leak_check.rs

   1 use super::*;
   2 use crate::infer::{CombinedSnapshot, PlaceholderMap};
   3 use rustc_data_structures::undo_log::UndoLogs;
   4 use rustc_middle::ty::error::TypeError;
   5 use rustc_middle::ty::relate::RelateResult;
   6
   7 impl<'tcx> RegionConstraintCollector<'_, 'tcx> {
   8     /// Searches region constraints created since `snapshot` that
   9     /// affect one of the placeholders in `placeholder_map`, returning
  10     /// an error if any of the placeholders are related to another
  11     /// placeholder or would have to escape into some parent universe
  12     /// that cannot name them.
  13     ///
  14     /// This is a temporary backwards compatibility measure to try and
  15     /// retain the older (arguably incorrect) behavior of the
  16     /// compiler.
  17     ///
  18     /// NB. Although `_snapshot` isn't used, it's passed in to prove
  19     /// that we are in a snapshot, which guarantees that we can just
  20     /// search the "undo log" for edges. This is mostly an efficiency
  21     /// thing -- we could search *all* region constraints, but that'd be
  22     /// a bigger set and the data structures are not setup for that. If
  23     /// we wind up keeping some form of this check long term, it would
  24     /// probably be better to remove the snapshot parameter and to
  25     /// refactor the constraint set.
  26     pub fn leak_check(
  27         &mut self,
  28         tcx: TyCtxt<'tcx>,
  29         overly_polymorphic: bool,
  30         placeholder_map: &PlaceholderMap<'tcx>,
  31         _snapshot: &CombinedSnapshot<'_, 'tcx>,
  32     ) -> RelateResult<'tcx, ()> {
  33         debug!("leak_check(placeholders={:?})", placeholder_map);
  34
  35         assert!(UndoLogs::<super::UndoLog<'_>>::in_snapshot(&self.undo_log));
  36
  37         // Go through each placeholder that we created.
  38         for &placeholder_region in placeholder_map.values() {
  39             // Find the universe this placeholder inhabits.
  40             let placeholder = match placeholder_region {
  41                 ty::RePlaceholder(p) => p,
  42                 _ => bug!("leak_check: expected placeholder found {:?}", placeholder_region,),
  43             };
  44
  45             // Find all regions that this placeholder `!p` must outlive -- i.e.,
  46             // any region `r` where `!p: r` must hold. It is an error if any
  47             // such region `r` is another placeholder or in a universe that
  48             // can't see the placeholder. (This is actually incorrect, because
  49             // we don't take into account the possibility of bounds in
  50             // environment that tell us that the placeholder may be related to
  51             // other regions).
  52             //
  53             // Note that we *don't* look for cases like `r: !p`. This is
  54             // because:
  55             //
  56             // * If `r` is some other placeholder `!p1`, then we'll find the
  57             //   error when we search the regions that `!p1` must outlive.
  58             // * If `r` is a variable in some outer universe, then it can
  59             //   potentially be assigned to `'static`, so this relation could
  60             //   hold.
  61             let mut taint_set = TaintSet::new(TaintDirections::outgoing(), placeholder_region);
  62             taint_set.fixed_point(
  63                 tcx,
  64                 self.undo_log.region_constraints(),
  65                 &self.storage.data.verifys,
  66             );
  67             let tainted_regions = taint_set.into_set();
  68
  69             // Report an error if two placeholders in the same universe
  70             // are related to one another, or if a placeholder is related
  71             // to something from a parent universe.
  72             for &tainted_region in &tainted_regions {
  73                 if let ty::RePlaceholder(_) = tainted_region {
  74                     // Two placeholders cannot be related:
  75                     if tainted_region == placeholder_region {
  76                         continue;
  77                     }
  78                 } else if self.universe(tainted_region).can_name(placeholder.universe) {
  79                     continue;
  80                 }
  81
  82                 return Err(if overly_polymorphic {
  83                     debug!("overly polymorphic!");
  84                     TypeError::RegionsOverlyPolymorphic(placeholder.name, tainted_region)
  85                 } else {
  86                     debug!("not as polymorphic!");
  87                     TypeError::RegionsInsufficientlyPolymorphic(placeholder.name, tainted_region)
  88                 });
  89             }
  90         }
  91
  92         Ok(())
  93     }
  94 }
  95
  96 #[derive(Debug)]
  97 struct TaintSet<'tcx> {
  98     directions: TaintDirections,
  99     regions: FxHashSet<ty::Region<'tcx>>,
 100 }
 101
 102 impl<'tcx> TaintSet<'tcx> {
 103     fn new(directions: TaintDirections, initial_region: ty::Region<'tcx>) -> Self {
 104         let mut regions = FxHashSet::default();
 105         regions.insert(initial_region);
 106         TaintSet { directions, regions }
 107     }
 108
 109     fn fixed_point<'a>(
 110         &mut self,
 111         tcx: TyCtxt<'tcx>,
 112         undo_log: impl IntoIterator<Item = &'a UndoLog<'tcx>> + Clone,
 113         verifys: &[Verify<'tcx>],
 114     ) where
 115         'tcx: 'a,
 116     {
 117         let mut prev_len = 0;
 118         while prev_len < self.len() {
 119             debug!("tainted: prev_len = {:?} new_len = {:?}", prev_len, self.len());
 120
 121             prev_len = self.len();
 122
 123             for undo_entry in undo_log.clone() {
 124                 match undo_entry {
 125                     &AddConstraint(Constraint::VarSubVar(a, b)) => {
 126                         self.add_edge(tcx.mk_region(ReVar(a)), tcx.mk_region(ReVar(b)));
 127                     }
 128                     &AddConstraint(Constraint::RegSubVar(a, b)) => {
 129                         self.add_edge(a, tcx.mk_region(ReVar(b)));
 130                     }
 131                     &AddConstraint(Constraint::VarSubReg(a, b)) => {
 132                         self.add_edge(tcx.mk_region(ReVar(a)), b);
 133                     }
 134                     &AddConstraint(Constraint::RegSubReg(a, b)) => {
 135                         self.add_edge(a, b);
 136                     }
 137                     &AddGiven(a, b) => {
 138                         self.add_edge(a, tcx.mk_region(ReVar(b)));
 139                     }
 140                     &AddVerify(i) => span_bug!(
 141                         verifys[i].origin.span(),
 142                         "we never add verifications while doing higher-ranked things",
 143                     ),
 144                     &AddCombination(..) | &AddVar(..) => {}
 145                 }
 146             }
 147         }
 148     }
 149
 150     fn into_set(self) -> FxHashSet<ty::Region<'tcx>> {
 151         self.regions
 152     }
 153
 154     fn len(&self) -> usize {
 155         self.regions.len()
 156     }
 157
 158     fn add_edge(&mut self, source: ty::Region<'tcx>, target: ty::Region<'tcx>) {
 159         if self.directions.incoming {
 160             if self.regions.contains(&target) {
 161                 self.regions.insert(source);
 162             }
 163         }
 164
 165         if self.directions.outgoing {
 166             if self.regions.contains(&source) {
 167                 self.regions.insert(target);
 168             }
 169         }
 170     }
 171 }