src/librustc_infer/infer/region_constraints/leak_check.rs

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