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.
15 use middle::ty::{BoundRegion, FreeRegion, Region, RegionVid, Vid};
16 use middle::ty::{ReEmpty, ReStatic, ReInfer, ReFree, ReEarlyBound,
18 use middle::ty::{ReScope, ReVar, ReSkolemized, BrFresh};
19 use middle::typeck::infer::cres;
20 use middle::typeck::infer::{RegionVariableOrigin, SubregionOrigin, TypeTrace};
21 use middle::typeck::infer;
23 use middle::graph::{Direction, NodeIndex};
24 use util::common::indenter;
25 use util::ppaux::{Repr};
27 use std::cell::{Cell, RefCell};
30 use collections::{HashMap, HashSet};
37 ConstrainVarSubVar(RegionVid, RegionVid),
38 ConstrainRegSubVar(Region, RegionVid),
39 ConstrainVarSubReg(RegionVid, Region),
40 ConstrainRegSubReg(Region, Region),
44 pub struct TwoRegions {
49 pub enum UndoLogEntry {
52 AddConstraint(Constraint),
53 AddCombination(CombineMapType, TwoRegions)
56 pub enum CombineMapType {
61 pub enum RegionResolutionError {
62 /// `ConcreteFailure(o, a, b)`:
64 /// `o` requires that `a <= b`, but this does not hold
65 ConcreteFailure(SubregionOrigin, Region, Region),
67 /// `SubSupConflict(v, sub_origin, sub_r, sup_origin, sup_r)`:
69 /// Could not infer a value for `v` because `sub_r <= v` (due to
70 /// `sub_origin`) but `v <= sup_r` (due to `sup_origin`) and
71 /// `sub_r <= sup_r` does not hold.
72 SubSupConflict(RegionVariableOrigin,
73 SubregionOrigin, Region,
74 SubregionOrigin, Region),
76 /// `SupSupConflict(v, origin1, r1, origin2, r2)`:
78 /// Could not infer a value for `v` because `v <= r1` (due to
79 /// `origin1`) and `v <= r2` (due to `origin2`) and
80 /// `r1` and `r2` have no intersection.
81 SupSupConflict(RegionVariableOrigin,
82 SubregionOrigin, Region,
83 SubregionOrigin, Region),
85 /// For subsets of `ConcreteFailure` and `SubSupConflict`, we can derive
86 /// more specific errors message by suggesting to the user where they
87 /// should put a lifetime. In those cases we process and put those errors
88 /// into `ProcessedErrors` before we do any reporting.
89 ProcessedErrors(Vec<RegionVariableOrigin>,
90 Vec<(TypeTrace, ty::type_err)>,
94 /// SameRegions is used to group regions that we think are the same and would
95 /// like to indicate so to the user.
96 /// For example, the following function
98 /// struct Foo { bar: int }
99 /// fn foo2<'a, 'b>(x: &'a Foo) -> &'b int {
103 /// would report an error because we expect 'a and 'b to match, and so we group
104 /// 'a and 'b together inside a SameRegions struct
106 pub struct SameRegions {
107 scope_id: ast::NodeId,
108 regions: Vec<BoundRegion>
112 pub fn contains(&self, other: &BoundRegion) -> bool {
113 self.regions.contains(other)
116 pub fn push(&mut self, other: BoundRegion) {
117 self.regions.push(other);
121 pub type CombineMap = HashMap<TwoRegions, RegionVid>;
123 pub struct RegionVarBindings<'a> {
125 var_origins: RefCell<Vec<RegionVariableOrigin>>,
126 constraints: RefCell<HashMap<Constraint, SubregionOrigin>>,
127 lubs: RefCell<CombineMap>,
128 glbs: RefCell<CombineMap>,
129 skolemization_count: Cell<uint>,
130 bound_count: Cell<uint>,
132 // The undo log records actions that might later be undone.
134 // Note: when the undo_log is empty, we are not actively
135 // snapshotting. When the `start_snapshot()` method is called, we
136 // push a Snapshot entry onto the list to indicate that we are now
137 // actively snapshotting. The reason for this is that otherwise
138 // we end up adding entries for things like the lower bound on
139 // a variable and so forth, which can never be rolled back.
140 undo_log: RefCell<Vec<UndoLogEntry> >,
142 // This contains the results of inference. It begins as an empty
143 // option and only acquires a value after inference is complete.
144 values: RefCell<Option<Vec<VarValue> >>,
147 pub fn RegionVarBindings<'a>(tcx: &'a ty::ctxt) -> RegionVarBindings<'a> {
150 var_origins: RefCell::new(Vec::new()),
151 values: RefCell::new(None),
152 constraints: RefCell::new(HashMap::new()),
153 lubs: RefCell::new(HashMap::new()),
154 glbs: RefCell::new(HashMap::new()),
155 skolemization_count: Cell::new(0),
156 bound_count: Cell::new(0),
157 undo_log: RefCell::new(Vec::new())
161 impl<'a> RegionVarBindings<'a> {
162 pub fn in_snapshot(&self) -> bool {
163 self.undo_log.borrow().len() > 0
166 pub fn start_snapshot(&self) -> uint {
167 debug!("RegionVarBindings: start_snapshot()");
168 if self.in_snapshot() {
169 self.undo_log.borrow().len()
171 self.undo_log.borrow_mut().push(Snapshot);
176 pub fn commit(&self) {
177 debug!("RegionVarBindings: commit()");
178 let mut undo_log = self.undo_log.borrow_mut();
179 while undo_log.len() > 0 {
180 undo_log.pop().unwrap();
184 pub fn rollback_to(&self, snapshot: uint) {
185 debug!("RegionVarBindings: rollback_to({})", snapshot);
186 let mut undo_log = self.undo_log.borrow_mut();
187 while undo_log.len() > snapshot {
188 let undo_item = undo_log.pop().unwrap();
189 debug!("undo_item={:?}", undo_item);
193 let mut var_origins = self.var_origins.borrow_mut();
194 assert_eq!(var_origins.len(), vid.to_uint() + 1);
195 var_origins.pop().unwrap();
197 AddConstraint(ref constraint) => {
198 self.constraints.borrow_mut().remove(constraint);
200 AddCombination(Glb, ref regions) => {
201 self.glbs.borrow_mut().remove(regions);
203 AddCombination(Lub, ref regions) => {
204 self.lubs.borrow_mut().remove(regions);
210 pub fn num_vars(&self) -> uint {
211 self.var_origins.borrow().len()
214 pub fn new_region_var(&self, origin: RegionVariableOrigin) -> RegionVid {
215 let id = self.num_vars();
216 self.var_origins.borrow_mut().push(origin);
217 let vid = RegionVid { id: id };
218 if self.in_snapshot() {
219 self.undo_log.borrow_mut().push(AddVar(vid));
221 debug!("created new region variable {:?} with origin {:?}",
222 vid, origin.repr(self.tcx));
226 pub fn new_skolemized(&self, br: ty::BoundRegion) -> Region {
227 let sc = self.skolemization_count.get();
228 self.skolemization_count.set(sc + 1);
229 ReInfer(ReSkolemized(sc, br))
232 pub fn new_bound(&self, binder_id: ast::NodeId) -> Region {
233 // Creates a fresh bound variable for use in GLB computations.
234 // See discussion of GLB computation in the large comment at
235 // the top of this file for more details.
237 // This computation is potentially wrong in the face of
238 // rollover. It's conceivable, if unlikely, that one might
239 // wind up with accidental capture for nested functions in
240 // that case, if the outer function had bound regions created
241 // a very long time before and the inner function somehow
242 // wound up rolling over such that supposedly fresh
243 // identifiers were in fact shadowed. For now, we just assert
244 // that there is no rollover -- eventually we should try to be
245 // robust against this possibility, either by checking the set
246 // of bound identifiers that appear in a given expression and
247 // ensure that we generate one that is distinct, or by
248 // changing the representation of bound regions in a fn
251 let sc = self.bound_count.get();
252 self.bound_count.set(sc + 1);
254 if sc >= self.bound_count.get() {
255 self.tcx.sess.bug("rollover in RegionInference new_bound()");
258 ReLateBound(binder_id, BrFresh(sc))
261 fn values_are_none(&self) -> bool {
262 self.values.borrow().is_none()
265 pub fn add_constraint(&self,
266 constraint: Constraint,
267 origin: SubregionOrigin) {
268 // cannot add constraints once regions are resolved
269 assert!(self.values_are_none());
271 debug!("RegionVarBindings: add_constraint({:?})", constraint);
273 if self.constraints.borrow_mut().insert(constraint, origin) {
274 if self.in_snapshot() {
275 self.undo_log.borrow_mut().push(AddConstraint(constraint));
280 pub fn make_subregion(&self,
281 origin: SubregionOrigin,
284 // cannot add constraints once regions are resolved
285 assert!(self.values_are_none());
287 debug!("RegionVarBindings: make_subregion({}, {}) due to {}",
290 origin.repr(self.tcx));
293 (ReEarlyBound(..), _) |
294 (ReLateBound(..), _) |
295 (_, ReEarlyBound(..)) |
296 (_, ReLateBound(..)) => {
297 self.tcx.sess.span_bug(
299 format!("cannot relate bound region: {} <= {}",
301 sup.repr(self.tcx)));
303 (ReInfer(ReVar(sub_id)), ReInfer(ReVar(sup_id))) => {
304 self.add_constraint(ConstrainVarSubVar(sub_id, sup_id), origin);
306 (r, ReInfer(ReVar(sup_id))) => {
307 self.add_constraint(ConstrainRegSubVar(r, sup_id), origin);
309 (ReInfer(ReVar(sub_id)), r) => {
310 self.add_constraint(ConstrainVarSubReg(sub_id, r), origin);
313 self.add_constraint(ConstrainRegSubReg(sub, sup), origin);
318 pub fn lub_regions(&self,
319 origin: SubregionOrigin,
323 // cannot add constraints once regions are resolved
324 assert!(self.values_are_none());
326 debug!("RegionVarBindings: lub_regions({:?}, {:?})", a, b);
328 (ReStatic, _) | (_, ReStatic) => {
329 ReStatic // nothing lives longer than static
336 this.make_subregion(origin, old_r, new_r))
341 pub fn glb_regions(&self,
342 origin: SubregionOrigin,
346 // cannot add constraints once regions are resolved
347 assert!(self.values_are_none());
349 debug!("RegionVarBindings: glb_regions({:?}, {:?})", a, b);
351 (ReStatic, r) | (r, ReStatic) => {
352 // static lives longer than everything else
360 this.make_subregion(origin, new_r, old_r))
365 pub fn resolve_var(&self, rid: RegionVid) -> ty::Region {
366 let v = match *self.values.borrow() {
368 self.tcx.sess.span_bug(
369 self.var_origins.borrow().get(rid.to_uint()).span(),
370 format!("attempt to resolve region variable before \
371 values have been computed!"))
373 Some(ref values) => *values.get(rid.to_uint())
376 debug!("RegionVarBindings: resolve_var({:?}={})={:?}",
377 rid, rid.to_uint(), v);
382 // No constraints, return ty::ReEmpty
387 // An error that has previously been reported.
393 fn combine_map<'a>(&'a self, t: CombineMapType)
394 -> &'a RefCell<CombineMap> {
401 pub fn combine_vars(&self,
405 origin: SubregionOrigin,
406 relate: |this: &RegionVarBindings,
410 let vars = TwoRegions { a: a, b: b };
411 match self.combine_map(t).borrow().find(&vars) {
413 return ReInfer(ReVar(c));
417 let c = self.new_region_var(infer::MiscVariable(origin.span()));
418 self.combine_map(t).borrow_mut().insert(vars, c);
419 if self.in_snapshot() {
420 self.undo_log.borrow_mut().push(AddCombination(t, vars));
422 relate(self, a, ReInfer(ReVar(c)));
423 relate(self, b, ReInfer(ReVar(c)));
424 debug!("combine_vars() c={:?}", c);
428 pub fn vars_created_since_snapshot(&self, snapshot: uint)
430 self.undo_log.borrow().slice_from(snapshot).iter()
431 .filter_map(|&elt| match elt {
432 AddVar(vid) => Some(vid),
438 pub fn tainted(&self, snapshot: uint, r0: Region) -> Vec<Region> {
440 * Computes all regions that have been related to `r0` in any
441 * way since the snapshot `snapshot` was taken---`r0` itself
442 * will be the first entry. This is used when checking whether
443 * skolemized regions are being improperly related to other
447 debug!("tainted(snapshot={}, r0={:?})", snapshot, r0);
448 let _indenter = indenter();
450 let undo_len = self.undo_log.borrow().len();
452 // `result_set` acts as a worklist: we explore all outgoing
453 // edges and add any new regions we find to result_set. This
454 // is not a terribly efficient implementation.
455 let mut result_set = vec!(r0);
456 let mut result_index = 0;
457 while result_index < result_set.len() {
458 // nb: can't use uint::range() here because result_set grows
459 let r = *result_set.get(result_index);
461 debug!("result_index={}, r={:?}", result_index, r);
463 let mut undo_index = snapshot;
464 while undo_index < undo_len {
465 // nb: can't use uint::range() here as we move result_set
466 let regs = match self.undo_log.borrow().get(undo_index) {
467 &AddConstraint(ConstrainVarSubVar(ref a, ref b)) => {
468 Some((ReInfer(ReVar(*a)),
471 &AddConstraint(ConstrainRegSubVar(ref a, ref b)) => {
472 Some((*a, ReInfer(ReVar(*b))))
474 &AddConstraint(ConstrainVarSubReg(ref a, ref b)) => {
475 Some((ReInfer(ReVar(*a)), *b))
477 &AddConstraint(ConstrainRegSubReg(a, b)) => {
489 consider_adding_edge(result_set, r, r1, r2);
491 consider_adding_edge(result_set, r, r2, r1);
503 fn consider_adding_edge(result_set: Vec<Region> ,
506 r2: Region) -> Vec<Region> {
507 let mut result_set = result_set;
508 if r == r1 { // Clearly, this is potentially inefficient.
509 if !result_set.iter().any(|x| *x == r2) {
518 This function performs the actual region resolution. It must be
519 called after all constraints have been added. It performs a
520 fixed-point iteration to find region values which satisfy all
521 constraints, assuming such values can be found; if they cannot,
524 pub fn resolve_regions(&self) -> Vec<RegionResolutionError> {
525 debug!("RegionVarBindings: resolve_regions()");
526 let mut errors = vec!();
527 let v = self.infer_variable_values(&mut errors);
528 *self.values.borrow_mut() = Some(v);
533 impl<'a> RegionVarBindings<'a> {
534 fn is_subregion_of(&self, sub: Region, sup: Region) -> bool {
535 self.tcx.region_maps.is_subregion_of(sub, sup)
538 fn lub_concrete_regions(&self, a: Region, b: Region) -> Region {
540 (ReLateBound(..), _) |
541 (_, ReLateBound(..)) |
542 (ReEarlyBound(..), _) |
543 (_, ReEarlyBound(..)) => {
545 format!("cannot relate bound region: LUB({}, {})",
550 (ReStatic, _) | (_, ReStatic) => {
551 ReStatic // nothing lives longer than static
554 (ReEmpty, r) | (r, ReEmpty) => {
555 r // everything lives longer than empty
558 (ReInfer(ReVar(v_id)), _) | (_, ReInfer(ReVar(v_id))) => {
559 self.tcx.sess.span_bug(
560 self.var_origins.borrow().get(v_id.to_uint()).span(),
561 format!("lub_concrete_regions invoked with \
562 non-concrete regions: {:?}, {:?}", a, b));
565 (f @ ReFree(ref fr), ReScope(s_id)) |
566 (ReScope(s_id), f @ ReFree(ref fr)) => {
567 // A "free" region can be interpreted as "some region
568 // at least as big as the block fr.scope_id". So, we can
569 // reasonably compare free regions and scopes:
570 match self.tcx.region_maps.nearest_common_ancestor(fr.scope_id, s_id) {
571 // if the free region's scope `fr.scope_id` is bigger than
572 // the scope region `s_id`, then the LUB is the free
574 Some(r_id) if r_id == fr.scope_id => f,
576 // otherwise, we don't know what the free region is,
577 // so we must conservatively say the LUB is static:
582 (ReScope(a_id), ReScope(b_id)) => {
583 // The region corresponding to an outer block is a
584 // subtype of the region corresponding to an inner
586 match self.tcx.region_maps.nearest_common_ancestor(a_id, b_id) {
587 Some(r_id) => ReScope(r_id),
592 (ReFree(ref a_fr), ReFree(ref b_fr)) => {
593 self.lub_free_regions(a_fr, b_fr)
596 // For these types, we cannot define any additional
598 (ReInfer(ReSkolemized(..)), _) |
599 (_, ReInfer(ReSkolemized(..))) => {
600 if a == b {a} else {ReStatic}
605 fn lub_free_regions(&self,
607 b: &FreeRegion) -> ty::Region
610 * Computes a region that encloses both free region arguments.
611 * Guarantee that if the same two regions are given as argument,
612 * in any order, a consistent result is returned.
615 return match a.cmp(b) {
616 Less => helper(self, a, b),
617 Greater => helper(self, b, a),
618 Equal => ty::ReFree(*a)
621 fn helper(this: &RegionVarBindings,
623 b: &FreeRegion) -> ty::Region
625 if this.tcx.region_maps.sub_free_region(*a, *b) {
627 } else if this.tcx.region_maps.sub_free_region(*b, *a) {
635 fn glb_concrete_regions(&self,
639 debug!("glb_concrete_regions({:?}, {:?})", a, b);
641 (ReLateBound(..), _) |
642 (_, ReLateBound(..)) |
643 (ReEarlyBound(..), _) |
644 (_, ReEarlyBound(..)) => {
646 format!("cannot relate bound region: GLB({}, {})",
651 (ReStatic, r) | (r, ReStatic) => {
652 // static lives longer than everything else
656 (ReEmpty, _) | (_, ReEmpty) => {
657 // nothing lives shorter than everything else
661 (ReInfer(ReVar(v_id)), _) |
662 (_, ReInfer(ReVar(v_id))) => {
663 self.tcx.sess.span_bug(
664 self.var_origins.borrow().get(v_id.to_uint()).span(),
665 format!("glb_concrete_regions invoked with \
666 non-concrete regions: {:?}, {:?}", a, b));
669 (ReFree(ref fr), s @ ReScope(s_id)) |
670 (s @ ReScope(s_id), ReFree(ref fr)) => {
671 // Free region is something "at least as big as
672 // `fr.scope_id`." If we find that the scope `fr.scope_id` is bigger
673 // than the scope `s_id`, then we can say that the GLB
674 // is the scope `s_id`. Otherwise, as we do not know
675 // big the free region is precisely, the GLB is undefined.
676 match self.tcx.region_maps.nearest_common_ancestor(fr.scope_id, s_id) {
677 Some(r_id) if r_id == fr.scope_id => Ok(s),
678 _ => Err(ty::terr_regions_no_overlap(b, a))
682 (ReScope(a_id), ReScope(b_id)) => {
683 self.intersect_scopes(a, b, a_id, b_id)
686 (ReFree(ref a_fr), ReFree(ref b_fr)) => {
687 self.glb_free_regions(a_fr, b_fr)
690 // For these types, we cannot define any additional
692 (ReInfer(ReSkolemized(..)), _) |
693 (_, ReInfer(ReSkolemized(..))) => {
697 Err(ty::terr_regions_no_overlap(b, a))
703 fn glb_free_regions(&self,
705 b: &FreeRegion) -> cres<ty::Region>
708 * Computes a region that is enclosed by both free region arguments,
709 * if any. Guarantees that if the same two regions are given as argument,
710 * in any order, a consistent result is returned.
713 return match a.cmp(b) {
714 Less => helper(self, a, b),
715 Greater => helper(self, b, a),
716 Equal => Ok(ty::ReFree(*a))
719 fn helper(this: &RegionVarBindings,
721 b: &FreeRegion) -> cres<ty::Region>
723 if this.tcx.region_maps.sub_free_region(*a, *b) {
725 } else if this.tcx.region_maps.sub_free_region(*b, *a) {
728 this.intersect_scopes(ty::ReFree(*a), ty::ReFree(*b),
729 a.scope_id, b.scope_id)
734 fn intersect_scopes(&self,
735 region_a: ty::Region,
736 region_b: ty::Region,
737 scope_a: ast::NodeId,
738 scope_b: ast::NodeId) -> cres<Region>
740 // We want to generate the intersection of two
741 // scopes or two free regions. So, if one of
742 // these scopes is a subscope of the other, return
743 // it. Otherwise fail.
744 debug!("intersect_scopes(scope_a={:?}, scope_b={:?}, region_a={:?}, region_b={:?})",
745 scope_a, scope_b, region_a, region_b);
746 match self.tcx.region_maps.nearest_common_ancestor(scope_a, scope_b) {
747 Some(r_id) if scope_a == r_id => Ok(ReScope(scope_b)),
748 Some(r_id) if scope_b == r_id => Ok(ReScope(scope_a)),
749 _ => Err(ty::terr_regions_no_overlap(region_a, region_b))
754 // ______________________________________________________________________
756 #[deriving(Eq, Show)]
757 enum Classification { Expanding, Contracting }
759 pub enum VarValue { NoValue, Value(Region), ErrorValue }
762 classification: Classification,
766 struct RegionAndOrigin {
768 origin: SubregionOrigin,
771 type RegionGraph = graph::Graph<(), Constraint>;
773 impl<'a> RegionVarBindings<'a> {
774 fn infer_variable_values(&self,
775 errors: &mut Vec<RegionResolutionError>)
777 let mut var_data = self.construct_var_data();
778 self.expansion(var_data.as_mut_slice());
779 self.contraction(var_data.as_mut_slice());
780 self.collect_concrete_region_errors(&mut *errors);
781 self.extract_values_and_collect_conflicts(var_data.as_slice(), errors)
784 fn construct_var_data(&self) -> Vec<VarData> {
785 Vec::from_fn(self.num_vars(), |_| {
787 // All nodes are initially classified as contracting; during
788 // the expansion phase, we will shift the classification for
789 // those nodes that have a concrete region predecessor to
791 classification: Contracting,
797 fn expansion(&self, var_data: &mut [VarData]) {
798 self.iterate_until_fixed_point("Expansion", |constraint| {
800 ConstrainRegSubVar(a_region, b_vid) => {
801 let b_data = &mut var_data[b_vid.to_uint()];
802 self.expand_node(a_region, b_vid, b_data)
804 ConstrainVarSubVar(a_vid, b_vid) => {
805 match var_data[a_vid.to_uint()].value {
806 NoValue | ErrorValue => false,
808 let b_node = &mut var_data[b_vid.to_uint()];
809 self.expand_node(a_region, b_vid, b_node)
813 ConstrainVarSubReg(..) => {
814 // This is a contraction constraint. Ignore it.
817 ConstrainRegSubReg(..) => {
818 // No region variables involved. Ignore.
825 fn expand_node(&self,
828 b_data: &mut VarData)
830 debug!("expand_node({:?}, {:?} == {:?})",
831 a_region, b_vid, b_data.value);
833 b_data.classification = Expanding;
836 debug!("Setting initial value of {:?} to {:?}", b_vid, a_region);
838 b_data.value = Value(a_region);
842 Value(cur_region) => {
843 let lub = self.lub_concrete_regions(a_region, cur_region);
844 if lub == cur_region {
848 debug!("Expanding value of {:?} from {:?} to {:?}",
849 b_vid, cur_region, lub);
851 b_data.value = Value(lub);
861 fn contraction(&self,
862 var_data: &mut [VarData]) {
863 self.iterate_until_fixed_point("Contraction", |constraint| {
865 ConstrainRegSubVar(..) => {
866 // This is an expansion constraint. Ignore.
869 ConstrainVarSubVar(a_vid, b_vid) => {
870 match var_data[b_vid.to_uint()].value {
871 NoValue | ErrorValue => false,
873 let a_data = &mut var_data[a_vid.to_uint()];
874 self.contract_node(a_vid, a_data, b_region)
878 ConstrainVarSubReg(a_vid, b_region) => {
879 let a_data = &mut var_data[a_vid.to_uint()];
880 self.contract_node(a_vid, a_data, b_region)
882 ConstrainRegSubReg(..) => {
883 // No region variables involved. Ignore.
890 fn contract_node(&self,
892 a_data: &mut VarData,
895 debug!("contract_node({:?} == {:?}/{:?}, {:?})",
896 a_vid, a_data.value, a_data.classification, b_region);
898 return match a_data.value {
900 assert_eq!(a_data.classification, Contracting);
901 a_data.value = Value(b_region);
910 match a_data.classification {
912 check_node(self, a_vid, a_data, a_region, b_region)
915 adjust_node(self, a_vid, a_data, a_region, b_region)
921 fn check_node(this: &RegionVarBindings,
923 a_data: &mut VarData,
927 if !this.is_subregion_of(a_region, b_region) {
928 debug!("Setting {:?} to ErrorValue: {:?} not subregion of {:?}",
929 a_vid, a_region, b_region);
930 a_data.value = ErrorValue;
935 fn adjust_node(this: &RegionVarBindings,
937 a_data: &mut VarData,
941 match this.glb_concrete_regions(a_region, b_region) {
946 debug!("Contracting value of {:?} from {:?} to {:?}",
947 a_vid, a_region, glb);
948 a_data.value = Value(glb);
953 debug!("Setting {:?} to ErrorValue: no glb of {:?}, {:?}",
954 a_vid, a_region, b_region);
955 a_data.value = ErrorValue;
962 fn collect_concrete_region_errors(
964 errors: &mut Vec<RegionResolutionError>)
966 for (constraint, _) in self.constraints.borrow().iter() {
967 let (sub, sup) = match *constraint {
968 ConstrainVarSubVar(..) |
969 ConstrainRegSubVar(..) |
970 ConstrainVarSubReg(..) => {
973 ConstrainRegSubReg(sub, sup) => {
978 if self.is_subregion_of(sub, sup) {
982 debug!("ConcreteFailure: !(sub <= sup): sub={:?}, sup={:?}",
984 let origin = self.constraints.borrow().get_copy(constraint);
985 errors.push(ConcreteFailure(origin, sub, sup));
989 fn extract_values_and_collect_conflicts(
991 var_data: &[VarData],
992 errors: &mut Vec<RegionResolutionError>)
994 debug!("extract_values_and_collect_conflicts()");
996 // This is the best way that I have found to suppress
997 // duplicate and related errors. Basically we keep a set of
998 // flags for every node. Whenever an error occurs, we will
999 // walk some portion of the graph looking to find pairs of
1000 // conflicting regions to report to the user. As we walk, we
1001 // trip the flags from false to true, and if we find that
1002 // we've already reported an error involving any particular
1003 // node we just stop and don't report the current error. The
1004 // idea is to report errors that derive from independent
1005 // regions of the graph, but not those that derive from
1006 // overlapping locations.
1007 let mut dup_vec = slice::from_elem(self.num_vars(), uint::MAX);
1009 let mut opt_graph = None;
1011 for idx in range(0u, self.num_vars()) {
1012 match var_data[idx].value {
1014 /* Inference successful */
1017 /* Unconstrained inference: do not report an error
1018 until the value of this variable is requested.
1019 After all, sometimes we make region variables but never
1020 really use their values. */
1023 /* Inference impossible, this value contains
1024 inconsistent constraints.
1026 I think that in this case we should report an
1027 error now---unlike the case above, we can't
1028 wait to see whether the user needs the result
1029 of this variable. The reason is that the mere
1030 existence of this variable implies that the
1031 region graph is inconsistent, whether or not it
1034 For example, we may have created a region
1035 variable that is the GLB of two other regions
1036 which do not have a GLB. Even if that variable
1037 is not used, it implies that those two regions
1038 *should* have a GLB.
1040 At least I think this is true. It may be that
1041 the mere existence of a conflict in a region variable
1042 that is not used is not a problem, so if this rule
1043 starts to create problems we'll have to revisit
1044 this portion of the code and think hard about it. =) */
1046 if opt_graph.is_none() {
1047 opt_graph = Some(self.construct_graph());
1049 let graph = opt_graph.get_ref();
1051 let node_vid = RegionVid { id: idx };
1052 match var_data[idx].classification {
1054 self.collect_error_for_expanding_node(
1055 graph, var_data, dup_vec, node_vid, errors);
1058 self.collect_error_for_contracting_node(
1059 graph, var_data, dup_vec, node_vid, errors);
1066 Vec::from_fn(self.num_vars(), |idx| var_data[idx].value)
1069 fn construct_graph(&self) -> RegionGraph {
1070 let num_vars = self.num_vars();
1072 let constraints = self.constraints.borrow();
1073 let num_edges = constraints.len();
1075 let mut graph = graph::Graph::with_capacity(num_vars + 1,
1078 for _ in range(0u, num_vars) {
1081 let dummy_idx = graph.add_node(());
1083 for (constraint, _) in constraints.iter() {
1085 ConstrainVarSubVar(a_id, b_id) => {
1086 graph.add_edge(NodeIndex(a_id.to_uint()),
1087 NodeIndex(b_id.to_uint()),
1090 ConstrainRegSubVar(_, b_id) => {
1091 graph.add_edge(dummy_idx,
1092 NodeIndex(b_id.to_uint()),
1095 ConstrainVarSubReg(a_id, _) => {
1096 graph.add_edge(NodeIndex(a_id.to_uint()),
1100 ConstrainRegSubReg(..) => {
1101 // Relations between two concrete regions do not
1102 // require an edge in the graph.
1110 fn collect_error_for_expanding_node(
1112 graph: &RegionGraph,
1113 var_data: &[VarData],
1114 dup_vec: &mut [uint],
1115 node_idx: RegionVid,
1116 errors: &mut Vec<RegionResolutionError>)
1118 // Errors in expanding nodes result from a lower-bound that is
1119 // not contained by an upper-bound.
1120 let (lower_bounds, lower_dup) =
1121 self.collect_concrete_regions(graph, var_data, node_idx,
1122 graph::Incoming, dup_vec);
1123 let (upper_bounds, upper_dup) =
1124 self.collect_concrete_regions(graph, var_data, node_idx,
1125 graph::Outgoing, dup_vec);
1127 if lower_dup || upper_dup {
1131 for lower_bound in lower_bounds.iter() {
1132 for upper_bound in upper_bounds.iter() {
1133 if !self.is_subregion_of(lower_bound.region,
1134 upper_bound.region) {
1135 errors.push(SubSupConflict(
1136 *self.var_origins.borrow().get(node_idx.to_uint()),
1140 upper_bound.region));
1146 self.tcx.sess.span_bug(
1147 self.var_origins.borrow().get(node_idx.to_uint()).span(),
1148 format!("collect_error_for_expanding_node() could not find error \
1149 for var {:?}, lower_bounds={}, upper_bounds={}",
1151 lower_bounds.map(|x| x.region).repr(self.tcx),
1152 upper_bounds.map(|x| x.region).repr(self.tcx)));
1155 fn collect_error_for_contracting_node(
1157 graph: &RegionGraph,
1158 var_data: &[VarData],
1159 dup_vec: &mut [uint],
1160 node_idx: RegionVid,
1161 errors: &mut Vec<RegionResolutionError>)
1163 // Errors in contracting nodes result from two upper-bounds
1164 // that have no intersection.
1165 let (upper_bounds, dup_found) =
1166 self.collect_concrete_regions(graph, var_data, node_idx,
1167 graph::Outgoing, dup_vec);
1173 for upper_bound_1 in upper_bounds.iter() {
1174 for upper_bound_2 in upper_bounds.iter() {
1175 match self.glb_concrete_regions(upper_bound_1.region,
1176 upper_bound_2.region) {
1179 errors.push(SupSupConflict(
1180 *self.var_origins.borrow().get(node_idx.to_uint()),
1181 upper_bound_1.origin,
1182 upper_bound_1.region,
1183 upper_bound_2.origin,
1184 upper_bound_2.region));
1191 self.tcx.sess.span_bug(
1192 self.var_origins.borrow().get(node_idx.to_uint()).span(),
1193 format!("collect_error_for_contracting_node() could not find error \
1194 for var {:?}, upper_bounds={}",
1196 upper_bounds.map(|x| x.region).repr(self.tcx)));
1199 fn collect_concrete_regions(&self,
1200 graph: &RegionGraph,
1201 var_data: &[VarData],
1202 orig_node_idx: RegionVid,
1204 dup_vec: &mut [uint])
1205 -> (Vec<RegionAndOrigin> , bool) {
1207 set: HashSet<RegionVid>,
1208 stack: Vec<RegionVid> ,
1209 result: Vec<RegionAndOrigin> ,
1212 let mut state = WalkState {
1213 set: HashSet::new(),
1214 stack: vec!(orig_node_idx),
1218 state.set.insert(orig_node_idx);
1220 // to start off the process, walk the source node in the
1221 // direction specified
1222 process_edges(self, &mut state, graph, orig_node_idx, dir);
1224 while !state.stack.is_empty() {
1225 let node_idx = state.stack.pop().unwrap();
1226 let classification = var_data[node_idx.to_uint()].classification;
1228 // check whether we've visited this node on some previous walk
1229 if dup_vec[node_idx.to_uint()] == uint::MAX {
1230 dup_vec[node_idx.to_uint()] = orig_node_idx.to_uint();
1231 } else if dup_vec[node_idx.to_uint()] != orig_node_idx.to_uint() {
1232 state.dup_found = true;
1235 debug!("collect_concrete_regions(orig_node_idx={:?}, node_idx={:?}, \
1236 classification={:?})",
1237 orig_node_idx, node_idx, classification);
1239 // figure out the direction from which this node takes its
1240 // values, and search for concrete regions etc in that direction
1241 let dir = match classification {
1242 Expanding => graph::Incoming,
1243 Contracting => graph::Outgoing,
1246 process_edges(self, &mut state, graph, node_idx, dir);
1249 let WalkState {result, dup_found, ..} = state;
1250 return (result, dup_found);
1252 fn process_edges(this: &RegionVarBindings,
1253 state: &mut WalkState,
1254 graph: &RegionGraph,
1255 source_vid: RegionVid,
1257 debug!("process_edges(source_vid={:?}, dir={:?})", source_vid, dir);
1259 let source_node_index = NodeIndex(source_vid.to_uint());
1260 graph.each_adjacent_edge(source_node_index, dir, |_, edge| {
1262 ConstrainVarSubVar(from_vid, to_vid) => {
1264 if from_vid == source_vid {to_vid} else {from_vid};
1265 if state.set.insert(opp_vid) {
1266 state.stack.push(opp_vid);
1270 ConstrainRegSubVar(region, _) |
1271 ConstrainVarSubReg(_, region) => {
1272 state.result.push(RegionAndOrigin {
1274 origin: this.constraints.borrow().get_copy(&edge.data)
1278 ConstrainRegSubReg(..) => {}
1285 fn iterate_until_fixed_point(&self,
1287 body: |constraint: &Constraint| -> bool) {
1288 let mut iteration = 0;
1289 let mut changed = true;
1293 debug!("---- {} Iteration \\#{}", tag, iteration);
1294 for (constraint, _) in self.constraints.borrow().iter() {
1295 let edge_changed = body(constraint);
1297 debug!("Updated due to constraint {}",
1298 constraint.repr(self.tcx));
1303 debug!("---- {} Complete after {} iteration(s)", tag, iteration);
1308 impl Repr for Constraint {
1309 fn repr(&self, tcx: &ty::ctxt) -> ~str {
1311 ConstrainVarSubVar(a, b) => format!("ConstrainVarSubVar({}, {})",
1312 a.repr(tcx), b.repr(tcx)),
1313 ConstrainRegSubVar(a, b) => format!("ConstrainRegSubVar({}, {})",
1314 a.repr(tcx), b.repr(tcx)),
1315 ConstrainVarSubReg(a, b) => format!("ConstrainVarSubReg({}, {})",
1316 a.repr(tcx), b.repr(tcx)),
1317 ConstrainRegSubReg(a, b) => format!("ConstrainRegSubReg({}, {})",
1318 a.repr(tcx), b.repr(tcx)),