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. The use of snapshot here is mostly an efficiency thing --
  18     /// we could search *all* region constraints, but that'd be a
  19     /// bigger set and the data structures are not setup for that. If
  20     /// we wind up keeping some form of this check long term, it would
  21     /// probably be better to remove the snapshot parameter and to
  22     /// refactor the constraint set.
  23     pub fn leak_check(
  24         &mut self,
  25         tcx: TyCtxt<'_, '_, 'tcx>,
  26         overly_polymorphic: bool,
  27         placeholder_map: &PlaceholderMap<'tcx>,
  28         _snapshot: &CombinedSnapshot<'_, 'tcx>,
  29     ) -> RelateResult<'tcx, ()> {
  30         debug!("leak_check(placeholders={:?})", placeholder_map);
  31
  32         assert!(self.in_snapshot());
  33
  34         // If the user gave `-Zno-leak-check`, then skip the leak
  35         // check completely. This is wildly unsound and also not
  36         // unlikely to cause an ICE or two. It is intended for use
  37         // only during a transition period, in which the MIR typeck
  38         // uses the "universe-style" check, and the rest of typeck
  39         // uses the more conservative leak check.  Since the leak
  40         // check is more conservative, we can't test the
  41         // universe-style check without disabling it.
  42         if tcx.sess.opts.debugging_opts.no_leak_check {
  43             return Ok(());
  44         }
  45
  46         // Go through each placeholder that we created.
  47         for (_, &placeholder_region) in placeholder_map {
  48             // Find the universe this placeholder inhabits.
  49             let placeholder = match placeholder_region {
  50                 ty::RePlaceholder(p) => p,
  51                 _ => bug!(
  52                     "leak_check: expected placeholder found {:?}",
  53                     placeholder_region,
  54                 ),
  55             };
  56
  57             // Find all regions that are related to this placeholder
  58             // in some way. This means any region that either outlives
  59             // or is outlived by a placeholder.
  60             let mut taint_set = TaintSet::new(
  61                 TaintDirections::both(),
  62                 placeholder_region,
  63             );
  64             taint_set.fixed_point(tcx, &self.undo_log, &self.data.verifys);
  65             let tainted_regions = taint_set.into_set();
  66
  67             // Report an error if two placeholders in the same universe
  68             // are related to one another, or if a placeholder is related
  69             // to something from a parent universe.
  70             for &tainted_region in &tainted_regions {
  71                 if let ty::RePlaceholder(_) = tainted_region {
  72                     // Two placeholders cannot be related:
  73                     if tainted_region == placeholder_region {
  74                         continue;
  75                     }
  76                 } else if self.universe(tainted_region).can_name(placeholder.universe) {
  77                     continue;
  78                 }
  79
  80                 return Err(if overly_polymorphic {
  81                     debug!("Overly polymorphic!");
  82                     TypeError::RegionsOverlyPolymorphic(placeholder.name, tainted_region)
  83                 } else {
  84                     debug!("Not as polymorphic!");
  85                     TypeError::RegionsInsufficientlyPolymorphic(placeholder.name, tainted_region)
  86                 });
  87             }
  88         }
  89
  90         Ok(())
  91     }
  92 }
  93
  94 #[derive(Debug)]
  95 struct TaintSet<'tcx> {
  96     directions: TaintDirections,
  97     regions: FxHashSet<ty::Region<'tcx>>,
  98 }
  99
 100 impl<'tcx> TaintSet<'tcx> {
 101     fn new(directions: TaintDirections, initial_region: ty::Region<'tcx>) -> Self {
 102         let mut regions = FxHashSet::default();
 103         regions.insert(initial_region);
 104         TaintSet {
 105             directions: directions,
 106             regions: regions,
 107         }
 108     }
 109
 110     fn fixed_point(
 111         &mut self,
 112         tcx: TyCtxt<'_, '_, 'tcx>,
 113         undo_log: &[UndoLog<'tcx>],
 114         verifys: &[Verify<'tcx>],
 115     ) {
 116         let mut prev_len = 0;
 117         while prev_len < self.len() {
 118             debug!(
 119                 "tainted: prev_len = {:?} new_len = {:?}",
 120                 prev_len,
 121                 self.len()
 122             );
 123
 124             prev_len = self.len();
 125
 126             for undo_entry in undo_log {
 127                 match undo_entry {
 128                     &AddConstraint(Constraint::VarSubVar(a, b)) => {
 129                         self.add_edge(tcx.mk_region(ReVar(a)), tcx.mk_region(ReVar(b)));
 130                     }
 131                     &AddConstraint(Constraint::RegSubVar(a, b)) => {
 132                         self.add_edge(a, tcx.mk_region(ReVar(b)));
 133                     }
 134                     &AddConstraint(Constraint::VarSubReg(a, b)) => {
 135                         self.add_edge(tcx.mk_region(ReVar(a)), b);
 136                     }
 137                     &AddConstraint(Constraint::RegSubReg(a, b)) => {
 138                         self.add_edge(a, b);
 139                     }
 140                     &AddGiven(a, b) => {
 141                         self.add_edge(a, tcx.mk_region(ReVar(b)));
 142                     }
 143                     &AddVerify(i) => span_bug!(
 144                         verifys[i].origin.span(),
 145                         "we never add verifications while doing higher-ranked things",
 146                     ),
 147                     &Purged | &AddCombination(..) | &AddVar(..) => {}
 148                 }
 149             }
 150         }
 151     }
 152
 153     fn into_set(self) -> FxHashSet<ty::Region<'tcx>> {
 154         self.regions
 155     }
 156
 157     fn len(&self) -> usize {
 158         self.regions.len()
 159     }
 160
 161     fn add_edge(&mut self, source: ty::Region<'tcx>, target: ty::Region<'tcx>) {
 162         if self.directions.incoming {
 163             if self.regions.contains(&target) {
 164                 self.regions.insert(source);
 165             }
 166         }
 167
 168         if self.directions.outgoing {
 169             if self.regions.contains(&source) {
 170                 self.regions.insert(target);
 171             }
 172         }
 173     }
 174 }