src/librustc/infer/region_constraints/leak_check.rs

   1 use super::*;
   2 use crate::infer::{CombinedSnapshot, PlaceholderMap};
   3 use crate::ty::error::TypeError;
   4 use crate::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         // If the user gave `-Zno-leak-check`, then skip the leak
  37         // check completely. This is wildly unsound and also not
  38         // unlikely to cause an ICE or two. It is intended for use
  39         // only during a transition period, in which the MIR typeck
  40         // uses the "universe-style" check, and the rest of typeck
  41         // uses the more conservative leak check.  Since the leak
  42         // check is more conservative, we can't test the
  43         // universe-style check without disabling it.
  44         if tcx.sess.opts.debugging_opts.no_leak_check {
  45             return Ok(());
  46         }
  47
  48         // Go through each placeholder that we created.
  49         for (_, &placeholder_region) in placeholder_map {
  50             // Find the universe this placeholder inhabits.
  51             let placeholder = match placeholder_region {
  52                 ty::RePlaceholder(p) => p,
  53                 _ => bug!(
  54                     "leak_check: expected placeholder found {:?}",
  55                     placeholder_region,
  56                 ),
  57             };
  58
  59             // Find all regions that are related to this placeholder
  60             // in some way. This means any region that either outlives
  61             // or is outlived by a placeholder.
  62             let mut taint_set = TaintSet::new(
  63                 TaintDirections::both(),
  64                 placeholder_region,
  65             );
  66             taint_set.fixed_point(tcx, &self.undo_log, &self.data.verifys);
  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 {
 107             directions: directions,
 108             regions: regions,
 109         }
 110     }
 111
 112     fn fixed_point(
 113         &mut self,
 114         tcx: TyCtxt<'tcx>,
 115         undo_log: &[UndoLog<'tcx>],
 116         verifys: &[Verify<'tcx>],
 117     ) {
 118         let mut prev_len = 0;
 119         while prev_len < self.len() {
 120             debug!(
 121                 "tainted: prev_len = {:?} new_len = {:?}",
 122                 prev_len,
 123                 self.len()
 124             );
 125
 126             prev_len = self.len();
 127
 128             for undo_entry in undo_log {
 129                 match undo_entry {
 130                     &AddConstraint(Constraint::VarSubVar(a, b)) => {
 131                         self.add_edge(tcx.mk_region(ReVar(a)), tcx.mk_region(ReVar(b)));
 132                     }
 133                     &AddConstraint(Constraint::RegSubVar(a, b)) => {
 134                         self.add_edge(a, tcx.mk_region(ReVar(b)));
 135                     }
 136                     &AddConstraint(Constraint::VarSubReg(a, b)) => {
 137                         self.add_edge(tcx.mk_region(ReVar(a)), b);
 138                     }
 139                     &AddConstraint(Constraint::RegSubReg(a, b)) => {
 140                         self.add_edge(a, b);
 141                     }
 142                     &AddGiven(a, b) => {
 143                         self.add_edge(a, tcx.mk_region(ReVar(b)));
 144                     }
 145                     &AddVerify(i) => span_bug!(
 146                         verifys[i].origin.span(),
 147                         "we never add verifications while doing higher-ranked things",
 148                     ),
 149                     &Purged | &AddCombination(..) | &AddVar(..) => {}
 150                 }
 151             }
 152         }
 153     }
 154
 155     fn into_set(self) -> FxHashSet<ty::Region<'tcx>> {
 156         self.regions
 157     }
 158
 159     fn len(&self) -> usize {
 160         self.regions.len()
 161     }
 162
 163     fn add_edge(&mut self, source: ty::Region<'tcx>, target: ty::Region<'tcx>) {
 164         if self.directions.incoming {
 165             if self.regions.contains(&target) {
 166                 self.regions.insert(source);
 167             }
 168         }
 169
 170         if self.directions.outgoing {
 171             if self.regions.contains(&source) {
 172                 self.regions.insert(target);
 173             }
 174         }
 175     }
 176 }