1 // Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
13 pub use self::Constraint::*;
14 pub use self::Verify::*;
15 pub use self::UndoLogEntry::*;
16 pub use self::CombineMapType::*;
17 pub use self::RegionResolutionError::*;
18 pub use self::VarValue::*;
19 use self::Classification::*;
22 use super::{RegionVariableOrigin, SubregionOrigin, TypeTrace, MiscVariable};
25 use middle::ty::{self, Ty};
26 use middle::ty::{BoundRegion, FreeRegion, Region, RegionVid};
27 use middle::ty::{ReEmpty, ReStatic, ReInfer, ReFree, ReEarlyBound};
28 use middle::ty::{ReLateBound, ReScope, ReVar, ReSkolemized, BrFresh};
30 use middle::graph::{Direction, NodeIndex};
31 use util::common::indenter;
32 use util::nodemap::{FnvHashMap, FnvHashSet};
33 use util::ppaux::{Repr, UserString};
35 use std::cell::{Cell, RefCell};
36 use std::cmp::Ordering::{self, Less, Greater, Equal};
37 use std::iter::repeat;
44 // A constraint that influences the inference process.
45 #[derive(Clone, Copy, PartialEq, Eq, Hash, Show)]
47 // One region variable is subregion of another
48 ConstrainVarSubVar(RegionVid, RegionVid),
50 // Concrete region is subregion of region variable
51 ConstrainRegSubVar(Region, RegionVid),
53 // Region variable is subregion of concrete region
54 ConstrainVarSubReg(RegionVid, Region),
57 // Something we have to verify after region inference is done, but
58 // which does not directly influence the inference process
59 pub enum Verify<'tcx> {
60 // VerifyRegSubReg(a, b): Verify that `a <= b`. Neither `a` nor
61 // `b` are inference variables.
62 VerifyRegSubReg(SubregionOrigin<'tcx>, Region, Region),
64 // VerifyGenericBound(T, _, R, RS): The parameter type `T` (or
65 // associated type) must outlive the region `R`. `T` is known to
66 // outlive `RS`. Therefore verify that `R <= RS[i]` for some
67 // `i`. Inference variables may be involved (but this verification
68 // step doesn't influence inference).
69 VerifyGenericBound(GenericKind<'tcx>, SubregionOrigin<'tcx>, Region, Vec<Region>),
72 #[derive(Clone, Show, PartialEq, Eq)]
73 pub enum GenericKind<'tcx> {
75 Projection(ty::ProjectionTy<'tcx>),
78 #[derive(Copy, PartialEq, Eq, Hash)]
79 pub struct TwoRegions {
84 #[derive(Copy, PartialEq)]
85 pub enum UndoLogEntry {
89 AddConstraint(Constraint),
91 AddGiven(ty::FreeRegion, ty::RegionVid),
92 AddCombination(CombineMapType, TwoRegions)
95 #[derive(Copy, PartialEq)]
96 pub enum CombineMapType {
100 #[derive(Clone, Show)]
101 pub enum RegionResolutionError<'tcx> {
102 /// `ConcreteFailure(o, a, b)`:
104 /// `o` requires that `a <= b`, but this does not hold
105 ConcreteFailure(SubregionOrigin<'tcx>, Region, Region),
107 /// `GenericBoundFailure(p, s, a, bs)
109 /// The parameter/associated-type `p` must be known to outlive the lifetime
110 /// `a`, but it is only known to outlive `bs` (and none of the
111 /// regions in `bs` outlive `a`).
112 GenericBoundFailure(SubregionOrigin<'tcx>, GenericKind<'tcx>, Region, Vec<Region>),
114 /// `SubSupConflict(v, sub_origin, sub_r, sup_origin, sup_r)`:
116 /// Could not infer a value for `v` because `sub_r <= v` (due to
117 /// `sub_origin`) but `v <= sup_r` (due to `sup_origin`) and
118 /// `sub_r <= sup_r` does not hold.
119 SubSupConflict(RegionVariableOrigin<'tcx>,
120 SubregionOrigin<'tcx>, Region,
121 SubregionOrigin<'tcx>, Region),
123 /// `SupSupConflict(v, origin1, r1, origin2, r2)`:
125 /// Could not infer a value for `v` because `v <= r1` (due to
126 /// `origin1`) and `v <= r2` (due to `origin2`) and
127 /// `r1` and `r2` have no intersection.
128 SupSupConflict(RegionVariableOrigin<'tcx>,
129 SubregionOrigin<'tcx>, Region,
130 SubregionOrigin<'tcx>, Region),
132 /// For subsets of `ConcreteFailure` and `SubSupConflict`, we can derive
133 /// more specific errors message by suggesting to the user where they
134 /// should put a lifetime. In those cases we process and put those errors
135 /// into `ProcessedErrors` before we do any reporting.
136 ProcessedErrors(Vec<RegionVariableOrigin<'tcx>>,
137 Vec<(TypeTrace<'tcx>, ty::type_err<'tcx>)>,
141 /// SameRegions is used to group regions that we think are the same and would
142 /// like to indicate so to the user.
143 /// For example, the following function
145 /// struct Foo { bar: int }
146 /// fn foo2<'a, 'b>(x: &'a Foo) -> &'b int {
150 /// would report an error because we expect 'a and 'b to match, and so we group
151 /// 'a and 'b together inside a SameRegions struct
152 #[derive(Clone, Show)]
153 pub struct SameRegions {
154 pub scope_id: ast::NodeId,
155 pub regions: Vec<BoundRegion>
159 pub fn contains(&self, other: &BoundRegion) -> bool {
160 self.regions.contains(other)
163 pub fn push(&mut self, other: BoundRegion) {
164 self.regions.push(other);
168 pub type CombineMap = FnvHashMap<TwoRegions, RegionVid>;
170 pub struct RegionVarBindings<'a, 'tcx: 'a> {
171 tcx: &'a ty::ctxt<'tcx>,
172 var_origins: RefCell<Vec<RegionVariableOrigin<'tcx>>>,
174 // Constraints of the form `A <= B` introduced by the region
175 // checker. Here at least one of `A` and `B` must be a region
177 constraints: RefCell<FnvHashMap<Constraint, SubregionOrigin<'tcx>>>,
179 // A "verify" is something that we need to verify after inference is
180 // done, but which does not directly affect inference in any way.
182 // An example is a `A <= B` where neither `A` nor `B` are
183 // inference variables.
184 verifys: RefCell<Vec<Verify<'tcx>>>,
186 // A "given" is a relationship that is known to hold. In particular,
187 // we often know from closure fn signatures that a particular free
188 // region must be a subregion of a region variable:
190 // foo.iter().filter(<'a> |x: &'a &'b T| ...)
192 // In situations like this, `'b` is in fact a region variable
193 // introduced by the call to `iter()`, and `'a` is a bound region
194 // on the closure (as indicated by the `<'a>` prefix). If we are
195 // naive, we wind up inferring that `'b` must be `'static`,
196 // because we require that it be greater than `'a` and we do not
197 // know what `'a` is precisely.
199 // This hashmap is used to avoid that naive scenario. Basically we
200 // record the fact that `'a <= 'b` is implied by the fn signature,
201 // and then ignore the constraint when solving equations. This is
202 // a bit of a hack but seems to work.
203 givens: RefCell<FnvHashSet<(ty::FreeRegion, ty::RegionVid)>>,
205 lubs: RefCell<CombineMap>,
206 glbs: RefCell<CombineMap>,
207 skolemization_count: Cell<u32>,
208 bound_count: Cell<u32>,
210 // The undo log records actions that might later be undone.
212 // Note: when the undo_log is empty, we are not actively
213 // snapshotting. When the `start_snapshot()` method is called, we
214 // push an OpenSnapshot entry onto the list to indicate that we
215 // are now actively snapshotting. The reason for this is that
216 // otherwise we end up adding entries for things like the lower
217 // bound on a variable and so forth, which can never be rolled
219 undo_log: RefCell<Vec<UndoLogEntry>>,
221 // This contains the results of inference. It begins as an empty
222 // option and only acquires a value after inference is complete.
223 values: RefCell<Option<Vec<VarValue>>>,
227 #[allow(missing_copy_implementations)]
228 pub struct RegionSnapshot {
230 skolemization_count: u32,
233 impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
234 pub fn new(tcx: &'a ty::ctxt<'tcx>) -> RegionVarBindings<'a, 'tcx> {
237 var_origins: RefCell::new(Vec::new()),
238 values: RefCell::new(None),
239 constraints: RefCell::new(FnvHashMap()),
240 verifys: RefCell::new(Vec::new()),
241 givens: RefCell::new(FnvHashSet()),
242 lubs: RefCell::new(FnvHashMap()),
243 glbs: RefCell::new(FnvHashMap()),
244 skolemization_count: Cell::new(0),
245 bound_count: Cell::new(0),
246 undo_log: RefCell::new(Vec::new())
250 fn in_snapshot(&self) -> bool {
251 self.undo_log.borrow().len() > 0
254 pub fn start_snapshot(&self) -> RegionSnapshot {
255 let length = self.undo_log.borrow().len();
256 debug!("RegionVarBindings: start_snapshot({})", length);
257 self.undo_log.borrow_mut().push(OpenSnapshot);
258 RegionSnapshot { length: length, skolemization_count: self.skolemization_count.get() }
261 pub fn commit(&self, snapshot: RegionSnapshot) {
262 debug!("RegionVarBindings: commit({})", snapshot.length);
263 assert!(self.undo_log.borrow().len() > snapshot.length);
264 assert!((*self.undo_log.borrow())[snapshot.length] == OpenSnapshot);
266 let mut undo_log = self.undo_log.borrow_mut();
267 if snapshot.length == 0 {
268 undo_log.truncate(0);
270 (*undo_log)[snapshot.length] = CommitedSnapshot;
272 self.skolemization_count.set(snapshot.skolemization_count);
275 pub fn rollback_to(&self, snapshot: RegionSnapshot) {
276 debug!("RegionVarBindings: rollback_to({:?})", snapshot);
277 let mut undo_log = self.undo_log.borrow_mut();
278 assert!(undo_log.len() > snapshot.length);
279 assert!((*undo_log)[snapshot.length] == OpenSnapshot);
280 while undo_log.len() > snapshot.length + 1 {
281 match undo_log.pop().unwrap() {
283 panic!("Failure to observe stack discipline");
285 CommitedSnapshot => { }
287 let mut var_origins = self.var_origins.borrow_mut();
288 var_origins.pop().unwrap();
289 assert_eq!(var_origins.len(), vid.index as uint);
291 AddConstraint(ref constraint) => {
292 self.constraints.borrow_mut().remove(constraint);
294 AddVerify(index) => {
295 self.verifys.borrow_mut().pop();
296 assert_eq!(self.verifys.borrow().len(), index);
298 AddGiven(sub, sup) => {
299 self.givens.borrow_mut().remove(&(sub, sup));
301 AddCombination(Glb, ref regions) => {
302 self.glbs.borrow_mut().remove(regions);
304 AddCombination(Lub, ref regions) => {
305 self.lubs.borrow_mut().remove(regions);
309 let c = undo_log.pop().unwrap();
310 assert!(c == OpenSnapshot);
311 self.skolemization_count.set(snapshot.skolemization_count);
314 pub fn num_vars(&self) -> u32 {
315 let len = self.var_origins.borrow().len();
316 // enforce no overflow
317 assert!(len as u32 as uint == len);
321 pub fn new_region_var(&self, origin: RegionVariableOrigin<'tcx>) -> RegionVid {
322 let id = self.num_vars();
323 self.var_origins.borrow_mut().push(origin.clone());
324 let vid = RegionVid { index: id };
325 if self.in_snapshot() {
326 self.undo_log.borrow_mut().push(AddVar(vid));
328 debug!("created new region variable {:?} with origin {}",
329 vid, origin.repr(self.tcx));
333 /// Creates a new skolemized region. Skolemized regions are fresh
334 /// regions used when performing higher-ranked computations. They
335 /// must be used in a very particular way and are never supposed
336 /// to "escape" out into error messages or the code at large.
338 /// The idea is to always create a snapshot. Skolemized regions
339 /// can be created in the context of this snapshot, but once the
340 /// snapshot is committed or rolled back, their numbers will be
341 /// recycled, so you must be finished with them. See the extensive
342 /// comments in `higher_ranked.rs` to see how it works (in
343 /// particular, the subtyping comparison).
345 /// The `snapshot` argument to this function is not really used;
346 /// it's just there to make it explicit which snapshot bounds the
347 /// skolemized region that results.
348 pub fn new_skolemized(&self, br: ty::BoundRegion, snapshot: &RegionSnapshot) -> Region {
349 assert!(self.in_snapshot());
350 assert!(self.undo_log.borrow()[snapshot.length] == OpenSnapshot);
352 let sc = self.skolemization_count.get();
353 self.skolemization_count.set(sc + 1);
354 ReInfer(ReSkolemized(sc, br))
357 pub fn new_bound(&self, debruijn: ty::DebruijnIndex) -> Region {
358 // Creates a fresh bound variable for use in GLB computations.
359 // See discussion of GLB computation in the large comment at
360 // the top of this file for more details.
362 // This computation is potentially wrong in the face of
363 // rollover. It's conceivable, if unlikely, that one might
364 // wind up with accidental capture for nested functions in
365 // that case, if the outer function had bound regions created
366 // a very long time before and the inner function somehow
367 // wound up rolling over such that supposedly fresh
368 // identifiers were in fact shadowed. For now, we just assert
369 // that there is no rollover -- eventually we should try to be
370 // robust against this possibility, either by checking the set
371 // of bound identifiers that appear in a given expression and
372 // ensure that we generate one that is distinct, or by
373 // changing the representation of bound regions in a fn
376 let sc = self.bound_count.get();
377 self.bound_count.set(sc + 1);
379 if sc >= self.bound_count.get() {
380 self.tcx.sess.bug("rollover in RegionInference new_bound()");
383 ReLateBound(debruijn, BrFresh(sc))
386 fn values_are_none(&self) -> bool {
387 self.values.borrow().is_none()
390 fn add_constraint(&self,
391 constraint: Constraint,
392 origin: SubregionOrigin<'tcx>) {
393 // cannot add constraints once regions are resolved
394 assert!(self.values_are_none());
396 debug!("RegionVarBindings: add_constraint({})",
397 constraint.repr(self.tcx));
399 if self.constraints.borrow_mut().insert(constraint, origin).is_none() {
400 if self.in_snapshot() {
401 self.undo_log.borrow_mut().push(AddConstraint(constraint));
407 verify: Verify<'tcx>) {
408 // cannot add verifys once regions are resolved
409 assert!(self.values_are_none());
411 debug!("RegionVarBindings: add_verify({})",
412 verify.repr(self.tcx));
414 let mut verifys = self.verifys.borrow_mut();
415 let index = verifys.len();
416 verifys.push(verify);
417 if self.in_snapshot() {
418 self.undo_log.borrow_mut().push(AddVerify(index));
422 pub fn add_given(&self,
424 sup: ty::RegionVid) {
425 // cannot add givens once regions are resolved
426 assert!(self.values_are_none());
428 let mut givens = self.givens.borrow_mut();
429 if givens.insert((sub, sup)) {
430 debug!("add_given({} <= {:?})",
434 self.undo_log.borrow_mut().push(AddGiven(sub, sup));
438 pub fn make_eqregion(&self,
439 origin: SubregionOrigin<'tcx>,
443 // Eventually, it would be nice to add direct support for
445 self.make_subregion(origin.clone(), sub, sup);
446 self.make_subregion(origin, sup, sub);
450 pub fn make_subregion(&self,
451 origin: SubregionOrigin<'tcx>,
454 // cannot add constraints once regions are resolved
455 assert!(self.values_are_none());
457 debug!("RegionVarBindings: make_subregion({}, {}) due to {}",
460 origin.repr(self.tcx));
463 (ReEarlyBound(..), ReEarlyBound(..)) => {
464 // This case is used only to make sure that explicitly-specified
465 // `Self` types match the real self type in implementations.
467 // FIXME(NDM) -- we really shouldn't be comparing bound things
468 self.add_verify(VerifyRegSubReg(origin, sub, sup));
470 (ReEarlyBound(..), _) |
471 (ReLateBound(..), _) |
472 (_, ReEarlyBound(..)) |
473 (_, ReLateBound(..)) => {
474 self.tcx.sess.span_bug(
476 &format!("cannot relate bound region: {} <= {}",
478 sup.repr(self.tcx))[]);
481 // all regions are subregions of static, so we can ignore this
483 (ReInfer(ReVar(sub_id)), ReInfer(ReVar(sup_id))) => {
484 self.add_constraint(ConstrainVarSubVar(sub_id, sup_id), origin);
486 (r, ReInfer(ReVar(sup_id))) => {
487 self.add_constraint(ConstrainRegSubVar(r, sup_id), origin);
489 (ReInfer(ReVar(sub_id)), r) => {
490 self.add_constraint(ConstrainVarSubReg(sub_id, r), origin);
493 self.add_verify(VerifyRegSubReg(origin, sub, sup));
498 /// See `Verify::VerifyGenericBound`
499 pub fn verify_generic_bound(&self,
500 origin: SubregionOrigin<'tcx>,
501 kind: GenericKind<'tcx>,
504 self.add_verify(VerifyGenericBound(kind, origin, sub, sups));
507 pub fn lub_regions(&self,
508 origin: SubregionOrigin<'tcx>,
512 // cannot add constraints once regions are resolved
513 assert!(self.values_are_none());
515 debug!("RegionVarBindings: lub_regions({}, {})",
519 (ReStatic, _) | (_, ReStatic) => {
520 ReStatic // nothing lives longer than static
525 Lub, a, b, origin.clone(),
527 this.make_subregion(origin.clone(), old_r, new_r))
532 pub fn glb_regions(&self,
533 origin: SubregionOrigin<'tcx>,
537 // cannot add constraints once regions are resolved
538 assert!(self.values_are_none());
540 debug!("RegionVarBindings: glb_regions({}, {})",
544 (ReStatic, r) | (r, ReStatic) => {
545 // static lives longer than everything else
551 Glb, a, b, origin.clone(),
553 this.make_subregion(origin.clone(), new_r, old_r))
558 pub fn resolve_var(&self, rid: RegionVid) -> ty::Region {
559 match *self.values.borrow() {
561 self.tcx.sess.span_bug(
562 (*self.var_origins.borrow())[rid.index as uint].span(),
563 "attempt to resolve region variable before values have \
566 Some(ref values) => {
567 let r = lookup(values, rid);
568 debug!("resolve_var({:?}) = {}", rid, r.repr(self.tcx));
574 fn combine_map(&self, t: CombineMapType)
575 -> &RefCell<CombineMap> {
582 pub fn combine_vars<F>(&self,
586 origin: SubregionOrigin<'tcx>,
589 F: FnMut(&RegionVarBindings<'a, 'tcx>, Region, Region),
591 let vars = TwoRegions { a: a, b: b };
592 match self.combine_map(t).borrow().get(&vars) {
594 return ReInfer(ReVar(c));
598 let c = self.new_region_var(MiscVariable(origin.span()));
599 self.combine_map(t).borrow_mut().insert(vars, c);
600 if self.in_snapshot() {
601 self.undo_log.borrow_mut().push(AddCombination(t, vars));
603 relate(self, a, ReInfer(ReVar(c)));
604 relate(self, b, ReInfer(ReVar(c)));
605 debug!("combine_vars() c={:?}", c);
609 pub fn vars_created_since_snapshot(&self, mark: &RegionSnapshot)
612 self.undo_log.borrow()[mark.length..]
614 .filter_map(|&elt| match elt {
615 AddVar(vid) => Some(vid),
621 /// Computes all regions that have been related to `r0` in any way since the mark `mark` was
622 /// made---`r0` itself will be the first entry. This is used when checking whether skolemized
623 /// regions are being improperly related to other regions.
624 pub fn tainted(&self, mark: &RegionSnapshot, r0: Region) -> Vec<Region> {
625 debug!("tainted(mark={:?}, r0={})", mark, r0.repr(self.tcx));
626 let _indenter = indenter();
628 // `result_set` acts as a worklist: we explore all outgoing
629 // edges and add any new regions we find to result_set. This
630 // is not a terribly efficient implementation.
631 let mut result_set = vec!(r0);
632 let mut result_index = 0;
633 while result_index < result_set.len() {
634 // nb: can't use uint::range() here because result_set grows
635 let r = result_set[result_index];
636 debug!("result_index={}, r={:?}", result_index, r);
639 self.undo_log.borrow()[mark.length..].iter()
642 &AddConstraint(ConstrainVarSubVar(a, b)) => {
643 consider_adding_bidirectional_edges(
645 ReInfer(ReVar(a)), ReInfer(ReVar(b)));
647 &AddConstraint(ConstrainRegSubVar(a, b)) => {
648 consider_adding_bidirectional_edges(
650 a, ReInfer(ReVar(b)));
652 &AddConstraint(ConstrainVarSubReg(a, b)) => {
653 consider_adding_bidirectional_edges(
655 ReInfer(ReVar(a)), b);
658 consider_adding_bidirectional_edges(
660 ReFree(a), ReInfer(ReVar(b)));
663 match (*self.verifys.borrow())[i] {
664 VerifyRegSubReg(_, a, b) => {
665 consider_adding_bidirectional_edges(
669 VerifyGenericBound(_, _, a, ref bs) => {
670 for &b in bs.iter() {
671 consider_adding_bidirectional_edges(
678 &AddCombination(..) |
681 &CommitedSnapshot => {
691 fn consider_adding_bidirectional_edges(result_set: &mut Vec<Region>,
695 consider_adding_directed_edge(result_set, r, r1, r2);
696 consider_adding_directed_edge(result_set, r, r2, r1);
699 fn consider_adding_directed_edge(result_set: &mut Vec<Region>,
704 // Clearly, this is potentially inefficient.
705 if !result_set.iter().any(|x| *x == r2) {
712 /// This function performs the actual region resolution. It must be
713 /// called after all constraints have been added. It performs a
714 /// fixed-point iteration to find region values which satisfy all
715 /// constraints, assuming such values can be found; if they cannot,
716 /// errors are reported.
717 pub fn resolve_regions(&self, subject_node: ast::NodeId) -> Vec<RegionResolutionError<'tcx>> {
718 debug!("RegionVarBindings: resolve_regions()");
719 let mut errors = vec!();
720 let v = self.infer_variable_values(&mut errors, subject_node);
721 *self.values.borrow_mut() = Some(v);
725 fn is_subregion_of(&self, sub: Region, sup: Region) -> bool {
726 self.tcx.region_maps.is_subregion_of(sub, sup)
729 fn lub_concrete_regions(&self, a: Region, b: Region) -> Region {
731 (ReLateBound(..), _) |
732 (_, ReLateBound(..)) |
733 (ReEarlyBound(..), _) |
734 (_, ReEarlyBound(..)) => {
736 &format!("cannot relate bound region: LUB({}, {})",
738 b.repr(self.tcx))[]);
741 (ReStatic, _) | (_, ReStatic) => {
742 ReStatic // nothing lives longer than static
745 (ReEmpty, r) | (r, ReEmpty) => {
746 r // everything lives longer than empty
749 (ReInfer(ReVar(v_id)), _) | (_, ReInfer(ReVar(v_id))) => {
750 self.tcx.sess.span_bug(
751 (*self.var_origins.borrow())[v_id.index as uint].span(),
752 &format!("lub_concrete_regions invoked with \
753 non-concrete regions: {:?}, {:?}",
758 (ReFree(ref fr), ReScope(s_id)) |
759 (ReScope(s_id), ReFree(ref fr)) => {
761 // A "free" region can be interpreted as "some region
762 // at least as big as the block fr.scope_id". So, we can
763 // reasonably compare free regions and scopes:
764 match self.tcx.region_maps.nearest_common_ancestor(fr.scope, s_id) {
765 // if the free region's scope `fr.scope_id` is bigger than
766 // the scope region `s_id`, then the LUB is the free
768 Some(r_id) if r_id == fr.scope => f,
770 // otherwise, we don't know what the free region is,
771 // so we must conservatively say the LUB is static:
776 (ReScope(a_id), ReScope(b_id)) => {
777 // The region corresponding to an outer block is a
778 // subtype of the region corresponding to an inner
780 match self.tcx.region_maps.nearest_common_ancestor(a_id, b_id) {
781 Some(r_id) => ReScope(r_id),
786 (ReFree(ref a_fr), ReFree(ref b_fr)) => {
787 self.lub_free_regions(a_fr, b_fr)
790 // For these types, we cannot define any additional
792 (ReInfer(ReSkolemized(..)), _) |
793 (_, ReInfer(ReSkolemized(..))) => {
794 if a == b {a} else {ReStatic}
799 /// Computes a region that encloses both free region arguments. Guarantee that if the same two
800 /// regions are given as argument, in any order, a consistent result is returned.
801 fn lub_free_regions(&self,
803 b: &FreeRegion) -> ty::Region
805 return match a.cmp(b) {
806 Less => helper(self, a, b),
807 Greater => helper(self, b, a),
808 Equal => ty::ReFree(*a)
811 fn helper(this: &RegionVarBindings,
813 b: &FreeRegion) -> ty::Region
815 if this.tcx.region_maps.sub_free_region(*a, *b) {
817 } else if this.tcx.region_maps.sub_free_region(*b, *a) {
825 fn glb_concrete_regions(&self,
828 -> cres<'tcx, Region> {
829 debug!("glb_concrete_regions({:?}, {:?})", a, b);
831 (ReLateBound(..), _) |
832 (_, ReLateBound(..)) |
833 (ReEarlyBound(..), _) |
834 (_, ReEarlyBound(..)) => {
836 &format!("cannot relate bound region: GLB({}, {})",
838 b.repr(self.tcx))[]);
841 (ReStatic, r) | (r, ReStatic) => {
842 // static lives longer than everything else
846 (ReEmpty, _) | (_, ReEmpty) => {
847 // nothing lives shorter than everything else
851 (ReInfer(ReVar(v_id)), _) |
852 (_, ReInfer(ReVar(v_id))) => {
853 self.tcx.sess.span_bug(
854 (*self.var_origins.borrow())[v_id.index as uint].span(),
855 &format!("glb_concrete_regions invoked with \
856 non-concrete regions: {:?}, {:?}",
861 (ReFree(ref fr), ReScope(s_id)) |
862 (ReScope(s_id), ReFree(ref fr)) => {
863 let s = ReScope(s_id);
864 // Free region is something "at least as big as
865 // `fr.scope_id`." If we find that the scope `fr.scope_id` is bigger
866 // than the scope `s_id`, then we can say that the GLB
867 // is the scope `s_id`. Otherwise, as we do not know
868 // big the free region is precisely, the GLB is undefined.
869 match self.tcx.region_maps.nearest_common_ancestor(fr.scope, s_id) {
870 Some(r_id) if r_id == fr.scope => Ok(s),
871 _ => Err(ty::terr_regions_no_overlap(b, a))
875 (ReScope(a_id), ReScope(b_id)) => {
876 self.intersect_scopes(a, b, a_id, b_id)
879 (ReFree(ref a_fr), ReFree(ref b_fr)) => {
880 self.glb_free_regions(a_fr, b_fr)
883 // For these types, we cannot define any additional
885 (ReInfer(ReSkolemized(..)), _) |
886 (_, ReInfer(ReSkolemized(..))) => {
890 Err(ty::terr_regions_no_overlap(b, a))
896 /// Computes a region that is enclosed by both free region arguments, if any. Guarantees that
897 /// if the same two regions are given as argument, in any order, a consistent result is
899 fn glb_free_regions(&self,
901 b: &FreeRegion) -> cres<'tcx, ty::Region>
903 return match a.cmp(b) {
904 Less => helper(self, a, b),
905 Greater => helper(self, b, a),
906 Equal => Ok(ty::ReFree(*a))
909 fn helper<'a, 'tcx>(this: &RegionVarBindings<'a, 'tcx>,
911 b: &FreeRegion) -> cres<'tcx, ty::Region>
913 if this.tcx.region_maps.sub_free_region(*a, *b) {
915 } else if this.tcx.region_maps.sub_free_region(*b, *a) {
918 this.intersect_scopes(ty::ReFree(*a), ty::ReFree(*b),
924 fn intersect_scopes(&self,
925 region_a: ty::Region,
926 region_b: ty::Region,
927 scope_a: region::CodeExtent,
928 scope_b: region::CodeExtent) -> cres<'tcx, Region>
930 // We want to generate the intersection of two
931 // scopes or two free regions. So, if one of
932 // these scopes is a subscope of the other, return
933 // it. Otherwise fail.
934 debug!("intersect_scopes(scope_a={:?}, scope_b={:?}, region_a={:?}, region_b={:?})",
935 scope_a, scope_b, region_a, region_b);
936 match self.tcx.region_maps.nearest_common_ancestor(scope_a, scope_b) {
937 Some(r_id) if scope_a == r_id => Ok(ReScope(scope_b)),
938 Some(r_id) if scope_b == r_id => Ok(ReScope(scope_a)),
939 _ => Err(ty::terr_regions_no_overlap(region_a, region_b))
944 // ______________________________________________________________________
946 #[derive(Copy, PartialEq, Show)]
947 enum Classification { Expanding, Contracting }
950 pub enum VarValue { NoValue, Value(Region), ErrorValue }
953 classification: Classification,
957 struct RegionAndOrigin<'tcx> {
959 origin: SubregionOrigin<'tcx>,
962 type RegionGraph = graph::Graph<(), Constraint>;
964 impl<'a, 'tcx> RegionVarBindings<'a, 'tcx> {
965 fn infer_variable_values(&self,
966 errors: &mut Vec<RegionResolutionError<'tcx>>,
967 subject: ast::NodeId) -> Vec<VarValue>
969 let mut var_data = self.construct_var_data();
971 // Dorky hack to cause `dump_constraints` to only get called
972 // if debug mode is enabled:
973 debug!("----() End constraint listing {:?}---", self.dump_constraints());
974 graphviz::maybe_print_constraints_for(self, subject);
976 self.expansion(var_data.as_mut_slice());
977 self.contraction(var_data.as_mut_slice());
979 self.extract_values_and_collect_conflicts(&var_data[],
981 self.collect_concrete_region_errors(&values, errors);
985 fn construct_var_data(&self) -> Vec<VarData> {
986 range(0, self.num_vars() as uint).map(|_| {
988 // All nodes are initially classified as contracting; during
989 // the expansion phase, we will shift the classification for
990 // those nodes that have a concrete region predecessor to
992 classification: Contracting,
998 fn dump_constraints(&self) {
999 debug!("----() Start constraint listing ()----");
1000 for (idx, (constraint, _)) in self.constraints.borrow().iter().enumerate() {
1001 debug!("Constraint {} => {}", idx, constraint.repr(self.tcx));
1005 fn expansion(&self, var_data: &mut [VarData]) {
1006 self.iterate_until_fixed_point("Expansion", |constraint| {
1007 debug!("expansion: constraint={} origin={}",
1008 constraint.repr(self.tcx),
1009 self.constraints.borrow()
1014 ConstrainRegSubVar(a_region, b_vid) => {
1015 let b_data = &mut var_data[b_vid.index as uint];
1016 self.expand_node(a_region, b_vid, b_data)
1018 ConstrainVarSubVar(a_vid, b_vid) => {
1019 match var_data[a_vid.index as uint].value {
1020 NoValue | ErrorValue => false,
1021 Value(a_region) => {
1022 let b_node = &mut var_data[b_vid.index as uint];
1023 self.expand_node(a_region, b_vid, b_node)
1027 ConstrainVarSubReg(..) => {
1028 // This is a contraction constraint. Ignore it.
1035 fn expand_node(&self,
1038 b_data: &mut VarData)
1041 debug!("expand_node({}, {:?} == {})",
1042 a_region.repr(self.tcx),
1044 b_data.value.repr(self.tcx));
1046 // Check if this relationship is implied by a given.
1049 if self.givens.borrow().contains(&(fr, b_vid)) {
1057 b_data.classification = Expanding;
1058 match b_data.value {
1060 debug!("Setting initial value of {:?} to {}",
1061 b_vid, a_region.repr(self.tcx));
1063 b_data.value = Value(a_region);
1067 Value(cur_region) => {
1068 let lub = self.lub_concrete_regions(a_region, cur_region);
1069 if lub == cur_region {
1073 debug!("Expanding value of {:?} from {} to {}",
1075 cur_region.repr(self.tcx),
1076 lub.repr(self.tcx));
1078 b_data.value = Value(lub);
1088 fn contraction(&self,
1089 var_data: &mut [VarData]) {
1090 self.iterate_until_fixed_point("Contraction", |constraint| {
1091 debug!("contraction: constraint={} origin={}",
1092 constraint.repr(self.tcx),
1093 self.constraints.borrow()
1098 ConstrainRegSubVar(..) => {
1099 // This is an expansion constraint. Ignore.
1102 ConstrainVarSubVar(a_vid, b_vid) => {
1103 match var_data[b_vid.index as uint].value {
1104 NoValue | ErrorValue => false,
1105 Value(b_region) => {
1106 let a_data = &mut var_data[a_vid.index as uint];
1107 self.contract_node(a_vid, a_data, b_region)
1111 ConstrainVarSubReg(a_vid, b_region) => {
1112 let a_data = &mut var_data[a_vid.index as uint];
1113 self.contract_node(a_vid, a_data, b_region)
1119 fn contract_node(&self,
1121 a_data: &mut VarData,
1124 debug!("contract_node({:?} == {}/{:?}, {})",
1125 a_vid, a_data.value.repr(self.tcx),
1126 a_data.classification, b_region.repr(self.tcx));
1128 return match a_data.value {
1130 assert_eq!(a_data.classification, Contracting);
1131 a_data.value = Value(b_region);
1139 Value(a_region) => {
1140 match a_data.classification {
1142 check_node(self, a_vid, a_data, a_region, b_region)
1145 adjust_node(self, a_vid, a_data, a_region, b_region)
1151 fn check_node(this: &RegionVarBindings,
1153 a_data: &mut VarData,
1157 if !this.is_subregion_of(a_region, b_region) {
1158 debug!("Setting {:?} to ErrorValue: {} not subregion of {}",
1160 a_region.repr(this.tcx),
1161 b_region.repr(this.tcx));
1162 a_data.value = ErrorValue;
1167 fn adjust_node(this: &RegionVarBindings,
1169 a_data: &mut VarData,
1173 match this.glb_concrete_regions(a_region, b_region) {
1175 if glb == a_region {
1178 debug!("Contracting value of {:?} from {} to {}",
1180 a_region.repr(this.tcx),
1181 glb.repr(this.tcx));
1182 a_data.value = Value(glb);
1187 debug!("Setting {:?} to ErrorValue: no glb of {}, {}",
1189 a_region.repr(this.tcx),
1190 b_region.repr(this.tcx));
1191 a_data.value = ErrorValue;
1198 fn collect_concrete_region_errors(&self,
1199 values: &Vec<VarValue>,
1200 errors: &mut Vec<RegionResolutionError<'tcx>>)
1202 let mut reg_reg_dups = FnvHashSet();
1203 for verify in self.verifys.borrow().iter() {
1205 VerifyRegSubReg(ref origin, sub, sup) => {
1206 if self.is_subregion_of(sub, sup) {
1210 if !reg_reg_dups.insert((sub, sup)) {
1214 debug!("ConcreteFailure: !(sub <= sup): sub={}, sup={}",
1216 sup.repr(self.tcx));
1217 errors.push(ConcreteFailure((*origin).clone(), sub, sup));
1220 VerifyGenericBound(ref kind, ref origin, sub, ref sups) => {
1221 let sub = normalize(values, sub);
1223 .map(|&sup| normalize(values, sup))
1224 .any(|sup| self.is_subregion_of(sub, sup))
1229 let sups = sups.iter().map(|&sup| normalize(values, sup))
1232 GenericBoundFailure(
1233 (*origin).clone(), kind.clone(), sub, sups));
1239 fn extract_values_and_collect_conflicts(
1241 var_data: &[VarData],
1242 errors: &mut Vec<RegionResolutionError<'tcx>>)
1245 debug!("extract_values_and_collect_conflicts()");
1247 // This is the best way that I have found to suppress
1248 // duplicate and related errors. Basically we keep a set of
1249 // flags for every node. Whenever an error occurs, we will
1250 // walk some portion of the graph looking to find pairs of
1251 // conflicting regions to report to the user. As we walk, we
1252 // trip the flags from false to true, and if we find that
1253 // we've already reported an error involving any particular
1254 // node we just stop and don't report the current error. The
1255 // idea is to report errors that derive from independent
1256 // regions of the graph, but not those that derive from
1257 // overlapping locations.
1258 let mut dup_vec: Vec<_> = repeat(u32::MAX).take(self.num_vars() as uint).collect();
1260 let mut opt_graph = None;
1262 for idx in range(0u, self.num_vars() as uint) {
1263 match var_data[idx].value {
1265 /* Inference successful */
1268 /* Unconstrained inference: do not report an error
1269 until the value of this variable is requested.
1270 After all, sometimes we make region variables but never
1271 really use their values. */
1274 /* Inference impossible, this value contains
1275 inconsistent constraints.
1277 I think that in this case we should report an
1278 error now---unlike the case above, we can't
1279 wait to see whether the user needs the result
1280 of this variable. The reason is that the mere
1281 existence of this variable implies that the
1282 region graph is inconsistent, whether or not it
1285 For example, we may have created a region
1286 variable that is the GLB of two other regions
1287 which do not have a GLB. Even if that variable
1288 is not used, it implies that those two regions
1289 *should* have a GLB.
1291 At least I think this is true. It may be that
1292 the mere existence of a conflict in a region variable
1293 that is not used is not a problem, so if this rule
1294 starts to create problems we'll have to revisit
1295 this portion of the code and think hard about it. =) */
1297 if opt_graph.is_none() {
1298 opt_graph = Some(self.construct_graph());
1300 let graph = opt_graph.as_ref().unwrap();
1302 let node_vid = RegionVid { index: idx as u32 };
1303 match var_data[idx].classification {
1305 self.collect_error_for_expanding_node(
1306 graph, var_data, dup_vec.as_mut_slice(),
1310 self.collect_error_for_contracting_node(
1311 graph, var_data, dup_vec.as_mut_slice(),
1319 range(0, self.num_vars() as uint).map(|idx| var_data[idx].value).collect()
1322 fn construct_graph(&self) -> RegionGraph {
1323 let num_vars = self.num_vars();
1325 let constraints = self.constraints.borrow();
1326 let num_edges = constraints.len();
1328 let mut graph = graph::Graph::with_capacity(num_vars as uint + 1,
1331 for _ in range(0, num_vars) {
1334 let dummy_idx = graph.add_node(());
1336 for (constraint, _) in constraints.iter() {
1338 ConstrainVarSubVar(a_id, b_id) => {
1339 graph.add_edge(NodeIndex(a_id.index as uint),
1340 NodeIndex(b_id.index as uint),
1343 ConstrainRegSubVar(_, b_id) => {
1344 graph.add_edge(dummy_idx,
1345 NodeIndex(b_id.index as uint),
1348 ConstrainVarSubReg(a_id, _) => {
1349 graph.add_edge(NodeIndex(a_id.index as uint),
1359 fn collect_error_for_expanding_node(
1361 graph: &RegionGraph,
1362 var_data: &[VarData],
1363 dup_vec: &mut [u32],
1364 node_idx: RegionVid,
1365 errors: &mut Vec<RegionResolutionError<'tcx>>)
1367 // Errors in expanding nodes result from a lower-bound that is
1368 // not contained by an upper-bound.
1369 let (mut lower_bounds, lower_dup) =
1370 self.collect_concrete_regions(graph, var_data, node_idx,
1371 graph::Incoming, dup_vec);
1372 let (mut upper_bounds, upper_dup) =
1373 self.collect_concrete_regions(graph, var_data, node_idx,
1374 graph::Outgoing, dup_vec);
1376 if lower_dup || upper_dup {
1380 // We place free regions first because we are special casing
1381 // SubSupConflict(ReFree, ReFree) when reporting error, and so
1382 // the user will more likely get a specific suggestion.
1383 fn free_regions_first(a: &RegionAndOrigin,
1384 b: &RegionAndOrigin)
1386 match (a.region, b.region) {
1387 (ReFree(..), ReFree(..)) => Equal,
1388 (ReFree(..), _) => Less,
1389 (_, ReFree(..)) => Greater,
1393 lower_bounds.sort_by(|a, b| { free_regions_first(a, b) });
1394 upper_bounds.sort_by(|a, b| { free_regions_first(a, b) });
1396 for lower_bound in lower_bounds.iter() {
1397 for upper_bound in upper_bounds.iter() {
1398 if !self.is_subregion_of(lower_bound.region,
1399 upper_bound.region) {
1400 errors.push(SubSupConflict(
1401 (*self.var_origins.borrow())[node_idx.index as uint].clone(),
1402 lower_bound.origin.clone(),
1404 upper_bound.origin.clone(),
1405 upper_bound.region));
1411 self.tcx.sess.span_bug(
1412 (*self.var_origins.borrow())[node_idx.index as uint].span(),
1413 &format!("collect_error_for_expanding_node() could not find error \
1414 for var {:?}, lower_bounds={}, upper_bounds={}",
1416 lower_bounds.repr(self.tcx),
1417 upper_bounds.repr(self.tcx))[]);
1420 fn collect_error_for_contracting_node(
1422 graph: &RegionGraph,
1423 var_data: &[VarData],
1424 dup_vec: &mut [u32],
1425 node_idx: RegionVid,
1426 errors: &mut Vec<RegionResolutionError<'tcx>>)
1428 // Errors in contracting nodes result from two upper-bounds
1429 // that have no intersection.
1430 let (upper_bounds, dup_found) =
1431 self.collect_concrete_regions(graph, var_data, node_idx,
1432 graph::Outgoing, dup_vec);
1438 for upper_bound_1 in upper_bounds.iter() {
1439 for upper_bound_2 in upper_bounds.iter() {
1440 match self.glb_concrete_regions(upper_bound_1.region,
1441 upper_bound_2.region) {
1444 errors.push(SupSupConflict(
1445 (*self.var_origins.borrow())[node_idx.index as uint].clone(),
1446 upper_bound_1.origin.clone(),
1447 upper_bound_1.region,
1448 upper_bound_2.origin.clone(),
1449 upper_bound_2.region));
1456 self.tcx.sess.span_bug(
1457 (*self.var_origins.borrow())[node_idx.index as uint].span(),
1458 &format!("collect_error_for_contracting_node() could not find error \
1459 for var {:?}, upper_bounds={}",
1461 upper_bounds.repr(self.tcx))[]);
1464 fn collect_concrete_regions(&self,
1465 graph: &RegionGraph,
1466 var_data: &[VarData],
1467 orig_node_idx: RegionVid,
1469 dup_vec: &mut [u32])
1470 -> (Vec<RegionAndOrigin<'tcx>>, bool) {
1471 struct WalkState<'tcx> {
1472 set: FnvHashSet<RegionVid>,
1473 stack: Vec<RegionVid>,
1474 result: Vec<RegionAndOrigin<'tcx>>,
1477 let mut state = WalkState {
1479 stack: vec!(orig_node_idx),
1483 state.set.insert(orig_node_idx);
1485 // to start off the process, walk the source node in the
1486 // direction specified
1487 process_edges(self, &mut state, graph, orig_node_idx, dir);
1489 while !state.stack.is_empty() {
1490 let node_idx = state.stack.pop().unwrap();
1491 let classification = var_data[node_idx.index as uint].classification;
1493 // check whether we've visited this node on some previous walk
1494 if dup_vec[node_idx.index as uint] == u32::MAX {
1495 dup_vec[node_idx.index as uint] = orig_node_idx.index;
1496 } else if dup_vec[node_idx.index as uint] != orig_node_idx.index {
1497 state.dup_found = true;
1500 debug!("collect_concrete_regions(orig_node_idx={:?}, node_idx={:?}, \
1501 classification={:?})",
1502 orig_node_idx, node_idx, classification);
1504 // figure out the direction from which this node takes its
1505 // values, and search for concrete regions etc in that direction
1506 let dir = match classification {
1507 Expanding => graph::Incoming,
1508 Contracting => graph::Outgoing,
1511 process_edges(self, &mut state, graph, node_idx, dir);
1514 let WalkState {result, dup_found, ..} = state;
1515 return (result, dup_found);
1517 fn process_edges<'a, 'tcx>(this: &RegionVarBindings<'a, 'tcx>,
1518 state: &mut WalkState<'tcx>,
1519 graph: &RegionGraph,
1520 source_vid: RegionVid,
1522 debug!("process_edges(source_vid={:?}, dir={:?})", source_vid, dir);
1524 let source_node_index = NodeIndex(source_vid.index as uint);
1525 graph.each_adjacent_edge(source_node_index, dir, |_, edge| {
1527 ConstrainVarSubVar(from_vid, to_vid) => {
1529 if from_vid == source_vid {to_vid} else {from_vid};
1530 if state.set.insert(opp_vid) {
1531 state.stack.push(opp_vid);
1535 ConstrainRegSubVar(region, _) |
1536 ConstrainVarSubReg(_, region) => {
1537 state.result.push(RegionAndOrigin {
1539 origin: this.constraints.borrow()[edge.data].clone()
1548 fn iterate_until_fixed_point<F>(&self, tag: &str, mut body: F) where
1549 F: FnMut(&Constraint) -> bool,
1551 let mut iteration = 0u;
1552 let mut changed = true;
1556 debug!("---- {} Iteration {}{}", "#", tag, iteration);
1557 for (constraint, _) in self.constraints.borrow().iter() {
1558 let edge_changed = body(constraint);
1560 debug!("Updated due to constraint {}",
1561 constraint.repr(self.tcx));
1566 debug!("---- {} Complete after {} iteration(s)", tag, iteration);
1571 impl<'tcx> Repr<'tcx> for Constraint {
1572 fn repr(&self, tcx: &ty::ctxt) -> String {
1574 ConstrainVarSubVar(a, b) => {
1575 format!("ConstrainVarSubVar({}, {})", a.repr(tcx), b.repr(tcx))
1577 ConstrainRegSubVar(a, b) => {
1578 format!("ConstrainRegSubVar({}, {})", a.repr(tcx), b.repr(tcx))
1580 ConstrainVarSubReg(a, b) => {
1581 format!("ConstrainVarSubReg({}, {})", a.repr(tcx), b.repr(tcx))
1587 impl<'tcx> Repr<'tcx> for Verify<'tcx> {
1588 fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1590 VerifyRegSubReg(_, ref a, ref b) => {
1591 format!("VerifyRegSubReg({}, {})", a.repr(tcx), b.repr(tcx))
1593 VerifyGenericBound(_, ref p, ref a, ref bs) => {
1594 format!("VerifyGenericBound({}, {}, {})",
1595 p.repr(tcx), a.repr(tcx), bs.repr(tcx))
1601 fn normalize(values: &Vec<VarValue>, r: ty::Region) -> ty::Region {
1603 ty::ReInfer(ReVar(rid)) => lookup(values, rid),
1608 fn lookup(values: &Vec<VarValue>, rid: ty::RegionVid) -> ty::Region {
1609 match values[rid.index as uint] {
1611 NoValue => ReEmpty, // No constraints, return ty::ReEmpty
1612 ErrorValue => ReStatic, // Previously reported error.
1616 impl<'tcx> Repr<'tcx> for VarValue {
1617 fn repr(&self, tcx: &ty::ctxt) -> String {
1619 NoValue => format!("NoValue"),
1620 Value(r) => format!("Value({})", r.repr(tcx)),
1621 ErrorValue => format!("ErrorValue"),
1626 impl<'tcx> Repr<'tcx> for RegionAndOrigin<'tcx> {
1627 fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1628 format!("RegionAndOrigin({},{})",
1629 self.region.repr(tcx),
1630 self.origin.repr(tcx))
1634 impl<'tcx> Repr<'tcx> for GenericKind<'tcx> {
1635 fn repr(&self, tcx: &ty::ctxt<'tcx>) -> String {
1637 GenericKind::Param(ref p) => p.repr(tcx),
1638 GenericKind::Projection(ref p) => p.repr(tcx),
1643 impl<'tcx> UserString<'tcx> for GenericKind<'tcx> {
1644 fn user_string(&self, tcx: &ty::ctxt<'tcx>) -> String {
1646 GenericKind::Param(ref p) => p.user_string(tcx),
1647 GenericKind::Projection(ref p) => p.user_string(tcx),
1652 impl<'tcx> GenericKind<'tcx> {
1653 pub fn to_ty(&self, tcx: &ty::ctxt<'tcx>) -> Ty<'tcx> {
1655 GenericKind::Param(ref p) =>
1657 GenericKind::Projection(ref p) =>
1658 ty::mk_projection(tcx, p.trait_ref.clone(), p.item_name),