2 use crate::infer::{CombinedSnapshot, PlaceholderMap};
3 use rustc::ty::error::TypeError;
4 use rustc::ty::relate::RelateResult;
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.
13 /// This is a temporary backwards compatibility measure to try and
14 /// retain the older (arguably incorrect) behavior of the
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.
28 overly_polymorphic: bool,
29 placeholder_map: &PlaceholderMap<'tcx>,
30 _snapshot: &CombinedSnapshot<'_, 'tcx>,
31 ) -> RelateResult<'tcx, ()> {
32 debug!("leak_check(placeholders={:?})", placeholder_map);
34 assert!(self.in_snapshot());
36 // Go through each placeholder that we created.
37 for (_, &placeholder_region) in placeholder_map {
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,),
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();
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 {
60 } else if self.universe(tainted_region).can_name(placeholder.universe) {
64 return Err(if overly_polymorphic {
65 debug!("overly polymorphic!");
66 TypeError::RegionsOverlyPolymorphic(placeholder.name, tainted_region)
68 debug!("not as polymorphic!");
69 TypeError::RegionsInsufficientlyPolymorphic(placeholder.name, tainted_region)
79 struct TaintSet<'tcx> {
80 directions: TaintDirections,
81 regions: FxHashSet<ty::Region<'tcx>>,
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 }
94 undo_log: &[UndoLog<'tcx>],
95 verifys: &[Verify<'tcx>],
98 while prev_len < self.len() {
99 debug!("tainted: prev_len = {:?} new_len = {:?}", prev_len, self.len());
101 prev_len = self.len();
103 for undo_entry in undo_log {
105 &AddConstraint(Constraint::VarSubVar(a, b)) => {
106 self.add_edge(tcx.mk_region(ReVar(a)), tcx.mk_region(ReVar(b)));
108 &AddConstraint(Constraint::RegSubVar(a, b)) => {
109 self.add_edge(a, tcx.mk_region(ReVar(b)));
111 &AddConstraint(Constraint::VarSubReg(a, b)) => {
112 self.add_edge(tcx.mk_region(ReVar(a)), b);
114 &AddConstraint(Constraint::RegSubReg(a, b)) => {
118 self.add_edge(a, tcx.mk_region(ReVar(b)));
120 &AddVerify(i) => span_bug!(
121 verifys[i].origin.span(),
122 "we never add verifications while doing higher-ranked things",
124 &Purged | &AddCombination(..) | &AddVar(..) => {}
130 fn into_set(self) -> FxHashSet<ty::Region<'tcx>> {
134 fn len(&self) -> usize {
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);
145 if self.directions.outgoing {
146 if self.regions.contains(&source) {
147 self.regions.insert(target);