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 are related to this placeholder
  46             // in some way. This means any region that either outlives
  47             // or is outlived by a placeholder.
  48             let mut taint_set = TaintSet::new(TaintDirections::both(), placeholder_region);
  49             taint_set.fixed_point(
  50                 tcx,
  51                 self.undo_log.region_constraints(),
  52                 &self.storage.data.verifys,
  53             );
  54             let tainted_regions = taint_set.into_set();
  55
  56             // Report an error if two placeholders in the same universe
  57             // are related to one another, or if a placeholder is related
  58             // to something from a parent universe.
  59             for &tainted_region in &tainted_regions {
  60                 if let ty::RePlaceholder(_) = tainted_region {
  61                     // Two placeholders cannot be related:
  62                     if tainted_region == placeholder_region {
  63                         continue;
  64                     }
  65                 } else if self.universe(tainted_region).can_name(placeholder.universe) {
  66                     continue;
  67                 }
  68
  69                 return Err(if overly_polymorphic {
  70                     debug!("overly polymorphic!");
  71                     TypeError::RegionsOverlyPolymorphic(placeholder.name, tainted_region)
  72                 } else {
  73                     debug!("not as polymorphic!");
  74                     TypeError::RegionsInsufficientlyPolymorphic(placeholder.name, tainted_region)
  75                 });
  76             }
  77         }
  78
  79         Ok(())
  80     }
  81 }
  82
  83 #[derive(Debug)]
  84 struct TaintSet<'tcx> {
  85     directions: TaintDirections,
  86     regions: FxHashSet<ty::Region<'tcx>>,
  87 }
  88
  89 impl<'tcx> TaintSet<'tcx> {
  90     fn new(directions: TaintDirections, initial_region: ty::Region<'tcx>) -> Self {
  91         let mut regions = FxHashSet::default();
  92         regions.insert(initial_region);
  93         TaintSet { directions, regions }
  94     }
  95
  96     fn fixed_point<'a>(
  97         &mut self,
  98         tcx: TyCtxt<'tcx>,
  99         undo_log: impl IntoIterator<Item = &'a UndoLog<'tcx>> + Clone,
 100         verifys: &[Verify<'tcx>],
 101     ) where
 102         'tcx: 'a,
 103     {
 104         let mut prev_len = 0;
 105         while prev_len < self.len() {
 106             debug!("tainted: prev_len = {:?} new_len = {:?}", prev_len, self.len());
 107
 108             prev_len = self.len();
 109
 110             for undo_entry in undo_log.clone() {
 111                 match undo_entry {
 112                     &AddConstraint(Constraint::VarSubVar(a, b)) => {
 113                         self.add_edge(tcx.mk_region(ReVar(a)), tcx.mk_region(ReVar(b)));
 114                     }
 115                     &AddConstraint(Constraint::RegSubVar(a, b)) => {
 116                         self.add_edge(a, tcx.mk_region(ReVar(b)));
 117                     }
 118                     &AddConstraint(Constraint::VarSubReg(a, b)) => {
 119                         self.add_edge(tcx.mk_region(ReVar(a)), b);
 120                     }
 121                     &AddConstraint(Constraint::RegSubReg(a, b)) => {
 122                         self.add_edge(a, b);
 123                     }
 124                     &AddGiven(a, b) => {
 125                         self.add_edge(a, tcx.mk_region(ReVar(b)));
 126                     }
 127                     &AddVerify(i) => span_bug!(
 128                         verifys[i].origin.span(),
 129                         "we never add verifications while doing higher-ranked things",
 130                     ),
 131                     &Purged | &AddCombination(..) | &AddVar(..) => {}
 132                 }
 133             }
 134         }
 135     }
 136
 137     fn into_set(self) -> FxHashSet<ty::Region<'tcx>> {
 138         self.regions
 139     }
 140
 141     fn len(&self) -> usize {
 142         self.regions.len()
 143     }
 144
 145     fn add_edge(&mut self, source: ty::Region<'tcx>, target: ty::Region<'tcx>) {
 146         if self.directions.incoming {
 147             if self.regions.contains(&target) {
 148                 self.regions.insert(source);
 149             }
 150         }
 151
 152         if self.directions.outgoing {
 153             if self.regions.contains(&source) {
 154                 self.regions.insert(target);
 155             }
 156         }
 157     }
 158 }