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.
4 //
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.
10
11 /*! See doc.rs */
12
13
14 use middle::ty;
15 use middle::ty::{BoundRegion, FreeRegion, Region, RegionVid, Vid};
16 use middle::ty::{ReEmpty, ReStatic, ReInfer, ReFree, ReEarlyBound,
17 ReLateBound};
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;
22 use middle::graph;
23 use middle::graph::{Direction, NodeIndex};
24 use util::common::indenter;
25 use util::ppaux::{Repr};
26
27 use std::cell::{Cell, RefCell};
28 use std::uint;
29 use collections::{HashMap, HashSet};
30 use syntax::ast;
31
32 mod doc;
33
34 #[deriving(Eq, TotalEq, Hash)]
35 pub enum Constraint {
36 ConstrainVarSubVar(RegionVid, RegionVid),
37 ConstrainRegSubVar(Region, RegionVid),
38 ConstrainVarSubReg(RegionVid, Region),
39 ConstrainRegSubReg(Region, Region),
40 }
41
42 #[deriving(Eq, TotalEq, Hash)]
43 pub struct TwoRegions {
44 a: Region,
45 b: Region,
46 }
47
48 pub enum UndoLogEntry {
49 Snapshot,
50 AddVar(RegionVid),
51 AddConstraint(Constraint),
52 AddCombination(CombineMapType, TwoRegions)
53 }
54
55 pub enum CombineMapType {
56 Lub, Glb
57 }
58
59 #[deriving(Clone)]
60 pub enum RegionResolutionError {
61 /// `ConcreteFailure(o, a, b)`:
62 ///
63 /// `o` requires that `a <= b`, but this does not hold
64 ConcreteFailure(SubregionOrigin, Region, Region),
65
66 /// `SubSupConflict(v, sub_origin, sub_r, sup_origin, sup_r)`:
67 ///
68 /// Could not infer a value for `v` because `sub_r <= v` (due to
69 /// `sub_origin`) but `v <= sup_r` (due to `sup_origin`) and
70 /// `sub_r <= sup_r` does not hold.
71 SubSupConflict(RegionVariableOrigin,
72 SubregionOrigin, Region,
73 SubregionOrigin, Region),
74
75 /// `SupSupConflict(v, origin1, r1, origin2, r2)`:
76 ///
77 /// Could not infer a value for `v` because `v <= r1` (due to
78 /// `origin1`) and `v <= r2` (due to `origin2`) and
79 /// `r1` and `r2` have no intersection.
80 SupSupConflict(RegionVariableOrigin,
81 SubregionOrigin, Region,
82 SubregionOrigin, Region),
83
84 /// For subsets of `ConcreteFailure` and `SubSupConflict`, we can derive
85 /// more specific errors message by suggesting to the user where they
86 /// should put a lifetime. In those cases we process and put those errors
87 /// into `ProcessedErrors` before we do any reporting.
88 ProcessedErrors(Vec<RegionVariableOrigin>,
89 Vec<(TypeTrace, ty::type_err)>,
90 Vec<SameRegions>),
91 }
92
93 /// SameRegions is used to group regions that we think are the same and would
94 /// like to indicate so to the user.
95 /// For example, the following function
96 /// ```
97 /// struct Foo { bar: int }
98 /// fn foo2<'a, 'b>(x: &'a Foo) -> &'b int {
99 /// &x.bar
100 /// }
101 /// ```
102 /// would report an error because we expect 'a and 'b to match, and so we group
103 /// 'a and 'b together inside a SameRegions struct
104 #[deriving(Clone)]
105 pub struct SameRegions {
106 pub scope_id: ast::NodeId,
107 pub regions: Vec<BoundRegion>
108 }
109
110 impl SameRegions {
111 pub fn contains(&self, other: &BoundRegion) -> bool {
112 self.regions.contains(other)
113 }
114
115 pub fn push(&mut self, other: BoundRegion) {
116 self.regions.push(other);
117 }
118 }
119
120 pub type CombineMap = HashMap<TwoRegions, RegionVid>;
121
122 pub struct RegionVarBindings<'a> {
123 tcx: &'a ty::ctxt,
124 var_origins: RefCell<Vec<RegionVariableOrigin>>,
125 constraints: RefCell<HashMap<Constraint, SubregionOrigin>>,
126 lubs: RefCell<CombineMap>,
127 glbs: RefCell<CombineMap>,
128 skolemization_count: Cell<uint>,
129 bound_count: Cell<uint>,
130
131 // The undo log records actions that might later be undone.
132 //
133 // Note: when the undo_log is empty, we are not actively
134 // snapshotting. When the `start_snapshot()` method is called, we
135 // push a Snapshot entry onto the list to indicate that we are now
136 // actively snapshotting. The reason for this is that otherwise
137 // we end up adding entries for things like the lower bound on
138 // a variable and so forth, which can never be rolled back.
139 undo_log: RefCell<Vec<UndoLogEntry> >,
140
141 // This contains the results of inference. It begins as an empty
142 // option and only acquires a value after inference is complete.
143 values: RefCell<Option<Vec<VarValue> >>,
144 }
145
146 pub fn RegionVarBindings<'a>(tcx: &'a ty::ctxt) -> RegionVarBindings<'a> {
147 RegionVarBindings {
148 tcx: tcx,
149 var_origins: RefCell::new(Vec::new()),
150 values: RefCell::new(None),
151 constraints: RefCell::new(HashMap::new()),
152 lubs: RefCell::new(HashMap::new()),
153 glbs: RefCell::new(HashMap::new()),
154 skolemization_count: Cell::new(0),
155 bound_count: Cell::new(0),
156 undo_log: RefCell::new(Vec::new())
157 }
158 }
159
160 impl<'a> RegionVarBindings<'a> {
161 pub fn in_snapshot(&self) -> bool {
162 self.undo_log.borrow().len() > 0
163 }
164
165 pub fn start_snapshot(&self) -> uint {
166 debug!("RegionVarBindings: start_snapshot()");
167 if self.in_snapshot() {
168 self.undo_log.borrow().len()
169 } else {
170 self.undo_log.borrow_mut().push(Snapshot);
171 0
172 }
173 }
174
175 pub fn commit(&self) {
176 debug!("RegionVarBindings: commit()");
177 let mut undo_log = self.undo_log.borrow_mut();
178 while undo_log.len() > 0 {
179 undo_log.pop().unwrap();
180 }
181 }
182
183 pub fn rollback_to(&self, snapshot: uint) {
184 debug!("RegionVarBindings: rollback_to({})", snapshot);
185 let mut undo_log = self.undo_log.borrow_mut();
186 while undo_log.len() > snapshot {
187 let undo_item = undo_log.pop().unwrap();
188 debug!("undo_item={:?}", undo_item);
189 match undo_item {
190 Snapshot => {}
191 AddVar(vid) => {
192 let mut var_origins = self.var_origins.borrow_mut();
193 assert_eq!(var_origins.len(), vid.to_uint() + 1);
194 var_origins.pop().unwrap();
195 }
196 AddConstraint(ref constraint) => {
197 self.constraints.borrow_mut().remove(constraint);
198 }
199 AddCombination(Glb, ref regions) => {
200 self.glbs.borrow_mut().remove(regions);
201 }
202 AddCombination(Lub, ref regions) => {
203 self.lubs.borrow_mut().remove(regions);
204 }
205 }
206 }
207 }
208
209 pub fn num_vars(&self) -> uint {
210 self.var_origins.borrow().len()
211 }
212
213 pub fn new_region_var(&self, origin: RegionVariableOrigin) -> RegionVid {
214 let id = self.num_vars();
215 self.var_origins.borrow_mut().push(origin.clone());
216 let vid = RegionVid { id: id };
217 if self.in_snapshot() {
218 self.undo_log.borrow_mut().push(AddVar(vid));
219 }
220 debug!("created new region variable {:?} with origin {:?}",
221 vid, origin.repr(self.tcx));
222 return vid;
223 }
224
225 pub fn new_skolemized(&self, br: ty::BoundRegion) -> Region {
226 let sc = self.skolemization_count.get();
227 self.skolemization_count.set(sc + 1);
228 ReInfer(ReSkolemized(sc, br))
229 }
230
231 pub fn new_bound(&self, binder_id: ast::NodeId) -> Region {
232 // Creates a fresh bound variable for use in GLB computations.
233 // See discussion of GLB computation in the large comment at
234 // the top of this file for more details.
235 //
236 // This computation is potentially wrong in the face of
237 // rollover. It's conceivable, if unlikely, that one might
238 // wind up with accidental capture for nested functions in
239 // that case, if the outer function had bound regions created
240 // a very long time before and the inner function somehow
241 // wound up rolling over such that supposedly fresh
242 // identifiers were in fact shadowed. For now, we just assert
243 // that there is no rollover -- eventually we should try to be
244 // robust against this possibility, either by checking the set
245 // of bound identifiers that appear in a given expression and
246 // ensure that we generate one that is distinct, or by
247 // changing the representation of bound regions in a fn
248 // declaration
249
250 let sc = self.bound_count.get();
251 self.bound_count.set(sc + 1);
252
253 if sc >= self.bound_count.get() {
254 self.tcx.sess.bug("rollover in RegionInference new_bound()");
255 }
256
257 ReLateBound(binder_id, BrFresh(sc))
258 }
259
260 fn values_are_none(&self) -> bool {
261 self.values.borrow().is_none()
262 }
263
264 pub fn add_constraint(&self,
265 constraint: Constraint,
266 origin: SubregionOrigin) {
267 // cannot add constraints once regions are resolved
268 assert!(self.values_are_none());
269
270 debug!("RegionVarBindings: add_constraint({:?})", constraint);
271
272 if self.constraints.borrow_mut().insert(constraint, origin) {
273 if self.in_snapshot() {
274 self.undo_log.borrow_mut().push(AddConstraint(constraint));
275 }
276 }
277 }
278
279 pub fn make_subregion(&self,
280 origin: SubregionOrigin,
281 sub: Region,
282 sup: Region) {
283 // cannot add constraints once regions are resolved
284 assert!(self.values_are_none());
285
286 debug!("RegionVarBindings: make_subregion({}, {}) due to {}",
287 sub.repr(self.tcx),
288 sup.repr(self.tcx),
289 origin.repr(self.tcx));
290
291 match (sub, sup) {
292 (ReEarlyBound(..), _) |
293 (ReLateBound(..), _) |
294 (_, ReEarlyBound(..)) |
295 (_, ReLateBound(..)) => {
296 self.tcx.sess.span_bug(
297 origin.span(),
298 format!("cannot relate bound region: {} <= {}",
299 sub.repr(self.tcx),
300 sup.repr(self.tcx)));
301 }
302 (ReInfer(ReVar(sub_id)), ReInfer(ReVar(sup_id))) => {
303 self.add_constraint(ConstrainVarSubVar(sub_id, sup_id), origin);
304 }
305 (r, ReInfer(ReVar(sup_id))) => {
306 self.add_constraint(ConstrainRegSubVar(r, sup_id), origin);
307 }
308 (ReInfer(ReVar(sub_id)), r) => {
309 self.add_constraint(ConstrainVarSubReg(sub_id, r), origin);
310 }
311 _ => {
312 self.add_constraint(ConstrainRegSubReg(sub, sup), origin);
313 }
314 }
315 }
316
317 pub fn lub_regions(&self,
318 origin: SubregionOrigin,
319 a: Region,
320 b: Region)
321 -> Region {
322 // cannot add constraints once regions are resolved
323 assert!(self.values_are_none());
324
325 debug!("RegionVarBindings: lub_regions({:?}, {:?})", a, b);
326 match (a, b) {
327 (ReStatic, _) | (_, ReStatic) => {
328 ReStatic // nothing lives longer than static
329 }
330
331 _ => {
332 self.combine_vars(
333 Lub, a, b, origin.clone(),
334 |this, old_r, new_r|
335 this.make_subregion(origin.clone(), old_r, new_r))
336 }
337 }
338 }
339
340 pub fn glb_regions(&self,
341 origin: SubregionOrigin,
342 a: Region,
343 b: Region)
344 -> Region {
345 // cannot add constraints once regions are resolved
346 assert!(self.values_are_none());
347
348 debug!("RegionVarBindings: glb_regions({:?}, {:?})", a, b);
349 match (a, b) {
350 (ReStatic, r) | (r, ReStatic) => {
351 // static lives longer than everything else
352 r
353 }
354
355 _ => {
356 self.combine_vars(
357 Glb, a, b, origin.clone(),
358 |this, old_r, new_r|
359 this.make_subregion(origin.clone(), new_r, old_r))
360 }
361 }
362 }
363
364 pub fn resolve_var(&self, rid: RegionVid) -> ty::Region {
365 let v = match *self.values.borrow() {
366 None => {
367 self.tcx.sess.span_bug(
368 self.var_origins.borrow().get(rid.to_uint()).span(),
369 format!("attempt to resolve region variable before \
370 values have been computed!"))
371 }
372 Some(ref values) => *values.get(rid.to_uint())
373 };
374
375 debug!("RegionVarBindings: resolve_var({:?}={})={:?}",
376 rid, rid.to_uint(), v);
377 match v {
378 Value(r) => r,
379
380 NoValue => {
381 // No constraints, return ty::ReEmpty
382 ReEmpty
383 }
384
385 ErrorValue => {
386 // An error that has previously been reported.
387 ReStatic
388 }
389 }
390 }
391
392 fn combine_map<'a>(&'a self, t: CombineMapType)
393 -> &'a RefCell<CombineMap> {
394 match t {
395 Glb => &self.glbs,
396 Lub => &self.lubs,
397 }
398 }
399
400 pub fn combine_vars(&self,
401 t: CombineMapType,
402 a: Region,
403 b: Region,
404 origin: SubregionOrigin,
405 relate: |this: &RegionVarBindings,
406 old_r: Region,
407 new_r: Region|)
408 -> Region {
409 let vars = TwoRegions { a: a, b: b };
410 match self.combine_map(t).borrow().find(&vars) {
411 Some(&c) => {
412 return ReInfer(ReVar(c));
413 }
414 None => {}
415 }
416 let c = self.new_region_var(infer::MiscVariable(origin.span()));
417 self.combine_map(t).borrow_mut().insert(vars, c);
418 if self.in_snapshot() {
419 self.undo_log.borrow_mut().push(AddCombination(t, vars));
420 }
421 relate(self, a, ReInfer(ReVar(c)));
422 relate(self, b, ReInfer(ReVar(c)));
423 debug!("combine_vars() c={:?}", c);
424 ReInfer(ReVar(c))
425 }
426
427 pub fn vars_created_since_snapshot(&self, snapshot: uint)
428 -> Vec<RegionVid> {
429 self.undo_log.borrow().slice_from(snapshot).iter()
430 .filter_map(|&elt| match elt {
431 AddVar(vid) => Some(vid),
432 _ => None
433 })
434 .collect()
435 }
436
437 pub fn tainted(&self, snapshot: uint, r0: Region) -> Vec<Region> {
438 /*!
439 * Computes all regions that have been related to `r0` in any
440 * way since the snapshot `snapshot` was taken---`r0` itself
441 * will be the first entry. This is used when checking whether
442 * skolemized regions are being improperly related to other
443 * regions.
444 */
445
446 debug!("tainted(snapshot={}, r0={:?})", snapshot, r0);
447 let _indenter = indenter();
448
449 let undo_len = self.undo_log.borrow().len();
450
451 // `result_set` acts as a worklist: we explore all outgoing
452 // edges and add any new regions we find to result_set. This
453 // is not a terribly efficient implementation.
454 let mut result_set = vec!(r0);
455 let mut result_index = 0;
456 while result_index < result_set.len() {
457 // nb: can't use uint::range() here because result_set grows
458 let r = *result_set.get(result_index);
459
460 debug!("result_index={}, r={:?}", result_index, r);
461
462 let mut undo_index = snapshot;
463 while undo_index < undo_len {
464 // nb: can't use uint::range() here as we move result_set
465 let regs = match self.undo_log.borrow().get(undo_index) {
466 &AddConstraint(ConstrainVarSubVar(ref a, ref b)) => {
467 Some((ReInfer(ReVar(*a)),
468 ReInfer(ReVar(*b))))
469 }
470 &AddConstraint(ConstrainRegSubVar(ref a, ref b)) => {
471 Some((*a, ReInfer(ReVar(*b))))
472 }
473 &AddConstraint(ConstrainVarSubReg(ref a, ref b)) => {
474 Some((ReInfer(ReVar(*a)), *b))
475 }
476 &AddConstraint(ConstrainRegSubReg(a, b)) => {
477 Some((a, b))
478 }
479 _ => {
480 None
481 }
482 };
483
484 match regs {
485 None => {}
486 Some((r1, r2)) => {
487 result_set =
488 consider_adding_edge(result_set, r, r1, r2);
489 result_set =
490 consider_adding_edge(result_set, r, r2, r1);
491 }
492 }
493
494 undo_index += 1;
495 }
496
497 result_index += 1;
498 }
499
500 return result_set;
501
502 fn consider_adding_edge(result_set: Vec<Region> ,
503 r: Region,
504 r1: Region,
505 r2: Region) -> Vec<Region> {
506 let mut result_set = result_set;
507 if r == r1 { // Clearly, this is potentially inefficient.
508 if !result_set.iter().any(|x| *x == r2) {
509 result_set.push(r2);
510 }
511 }
512 return result_set;
513 }
514 }
515
516 /**
517 This function performs the actual region resolution. It must be
518 called after all constraints have been added. It performs a
519 fixed-point iteration to find region values which satisfy all
520 constraints, assuming such values can be found; if they cannot,
521 errors are reported.
522 */
523 pub fn resolve_regions(&self) -> Vec<RegionResolutionError> {
524 debug!("RegionVarBindings: resolve_regions()");
525 let mut errors = vec!();
526 let v = self.infer_variable_values(&mut errors);
527 *self.values.borrow_mut() = Some(v);
528 errors
529 }
530 }
531
532 impl<'a> RegionVarBindings<'a> {
533 fn is_subregion_of(&self, sub: Region, sup: Region) -> bool {
534 self.tcx.region_maps.is_subregion_of(sub, sup)
535 }
536
537 fn lub_concrete_regions(&self, a: Region, b: Region) -> Region {
538 match (a, b) {
539 (ReLateBound(..), _) |
540 (_, ReLateBound(..)) |
541 (ReEarlyBound(..), _) |
542 (_, ReEarlyBound(..)) => {
543 self.tcx.sess.bug(
544 format!("cannot relate bound region: LUB({}, {})",
545 a.repr(self.tcx),
546 b.repr(self.tcx)));
547 }
548
549 (ReStatic, _) | (_, ReStatic) => {
550 ReStatic // nothing lives longer than static
551 }
552
553 (ReEmpty, r) | (r, ReEmpty) => {
554 r // everything lives longer than empty
555 }
556
557 (ReInfer(ReVar(v_id)), _) | (_, ReInfer(ReVar(v_id))) => {
558 self.tcx.sess.span_bug(
559 self.var_origins.borrow().get(v_id.to_uint()).span(),
560 format!("lub_concrete_regions invoked with \
561 non-concrete regions: {:?}, {:?}", a, b));
562 }
563
564 (f @ ReFree(ref fr), ReScope(s_id)) |
565 (ReScope(s_id), f @ ReFree(ref fr)) => {
566 // A "free" region can be interpreted as "some region
567 // at least as big as the block fr.scope_id". So, we can
568 // reasonably compare free regions and scopes:
569 match self.tcx.region_maps.nearest_common_ancestor(fr.scope_id, s_id) {
570 // if the free region's scope `fr.scope_id` is bigger than
571 // the scope region `s_id`, then the LUB is the free
572 // region itself:
573 Some(r_id) if r_id == fr.scope_id => f,
574
575 // otherwise, we don't know what the free region is,
576 // so we must conservatively say the LUB is static:
577 _ => ReStatic
578 }
579 }
580
581 (ReScope(a_id), ReScope(b_id)) => {
582 // The region corresponding to an outer block is a
583 // subtype of the region corresponding to an inner
584 // block.
585 match self.tcx.region_maps.nearest_common_ancestor(a_id, b_id) {
586 Some(r_id) => ReScope(r_id),
587 _ => ReStatic
588 }
589 }
590
591 (ReFree(ref a_fr), ReFree(ref b_fr)) => {
592 self.lub_free_regions(a_fr, b_fr)
593 }
594
595 // For these types, we cannot define any additional
596 // relationship:
597 (ReInfer(ReSkolemized(..)), _) |
598 (_, ReInfer(ReSkolemized(..))) => {
599 if a == b {a} else {ReStatic}
600 }
601 }
602 }
603
604 fn lub_free_regions(&self,
605 a: &FreeRegion,
606 b: &FreeRegion) -> ty::Region
607 {
608 /*!
609 * Computes a region that encloses both free region arguments.
610 * Guarantee that if the same two regions are given as argument,
611 * in any order, a consistent result is returned.
612 */
613
614 return match a.cmp(b) {
615 Less => helper(self, a, b),
616 Greater => helper(self, b, a),
617 Equal => ty::ReFree(*a)
618 };
619
620 fn helper(this: &RegionVarBindings,
621 a: &FreeRegion,
622 b: &FreeRegion) -> ty::Region
623 {
624 if this.tcx.region_maps.sub_free_region(*a, *b) {
625 ty::ReFree(*b)
626 } else if this.tcx.region_maps.sub_free_region(*b, *a) {
627 ty::ReFree(*a)
628 } else {
629 ty::ReStatic
630 }
631 }
632 }
633
634 fn glb_concrete_regions(&self,
635 a: Region,
636 b: Region)
637 -> cres<Region> {
638 debug!("glb_concrete_regions({:?}, {:?})", a, b);
639 match (a, b) {
640 (ReLateBound(..), _) |
641 (_, ReLateBound(..)) |
642 (ReEarlyBound(..), _) |
643 (_, ReEarlyBound(..)) => {
644 self.tcx.sess.bug(
645 format!("cannot relate bound region: GLB({}, {})",
646 a.repr(self.tcx),
647 b.repr(self.tcx)));
648 }
649
650 (ReStatic, r) | (r, ReStatic) => {
651 // static lives longer than everything else
652 Ok(r)
653 }
654
655 (ReEmpty, _) | (_, ReEmpty) => {
656 // nothing lives shorter than everything else
657 Ok(ReEmpty)
658 }
659
660 (ReInfer(ReVar(v_id)), _) |
661 (_, ReInfer(ReVar(v_id))) => {
662 self.tcx.sess.span_bug(
663 self.var_origins.borrow().get(v_id.to_uint()).span(),
664 format!("glb_concrete_regions invoked with \
665 non-concrete regions: {:?}, {:?}", a, b));
666 }
667
668 (ReFree(ref fr), s @ ReScope(s_id)) |
669 (s @ ReScope(s_id), ReFree(ref fr)) => {
670 // Free region is something "at least as big as
671 // `fr.scope_id`." If we find that the scope `fr.scope_id` is bigger
672 // than the scope `s_id`, then we can say that the GLB
673 // is the scope `s_id`. Otherwise, as we do not know
674 // big the free region is precisely, the GLB is undefined.
675 match self.tcx.region_maps.nearest_common_ancestor(fr.scope_id, s_id) {
676 Some(r_id) if r_id == fr.scope_id => Ok(s),
677 _ => Err(ty::terr_regions_no_overlap(b, a))
678 }
679 }
680
681 (ReScope(a_id), ReScope(b_id)) => {
682 self.intersect_scopes(a, b, a_id, b_id)
683 }
684
685 (ReFree(ref a_fr), ReFree(ref b_fr)) => {
686 self.glb_free_regions(a_fr, b_fr)
687 }
688
689 // For these types, we cannot define any additional
690 // relationship:
691 (ReInfer(ReSkolemized(..)), _) |
692 (_, ReInfer(ReSkolemized(..))) => {
693 if a == b {
694 Ok(a)
695 } else {
696 Err(ty::terr_regions_no_overlap(b, a))
697 }
698 }
699 }
700 }
701
702 fn glb_free_regions(&self,
703 a: &FreeRegion,
704 b: &FreeRegion) -> cres<ty::Region>
705 {
706 /*!
707 * Computes a region that is enclosed by both free region arguments,
708 * if any. Guarantees that if the same two regions are given as argument,
709 * in any order, a consistent result is returned.
710 */
711
712 return match a.cmp(b) {
713 Less => helper(self, a, b),
714 Greater => helper(self, b, a),
715 Equal => Ok(ty::ReFree(*a))
716 };
717
718 fn helper(this: &RegionVarBindings,
719 a: &FreeRegion,
720 b: &FreeRegion) -> cres<ty::Region>
721 {
722 if this.tcx.region_maps.sub_free_region(*a, *b) {
723 Ok(ty::ReFree(*a))
724 } else if this.tcx.region_maps.sub_free_region(*b, *a) {
725 Ok(ty::ReFree(*b))
726 } else {
727 this.intersect_scopes(ty::ReFree(*a), ty::ReFree(*b),
728 a.scope_id, b.scope_id)
729 }
730 }
731 }
732
733 fn intersect_scopes(&self,
734 region_a: ty::Region,
735 region_b: ty::Region,
736 scope_a: ast::NodeId,
737 scope_b: ast::NodeId) -> cres<Region>
738 {
739 // We want to generate the intersection of two
740 // scopes or two free regions. So, if one of
741 // these scopes is a subscope of the other, return
742 // it. Otherwise fail.
743 debug!("intersect_scopes(scope_a={:?}, scope_b={:?}, region_a={:?}, region_b={:?})",
744 scope_a, scope_b, region_a, region_b);
745 match self.tcx.region_maps.nearest_common_ancestor(scope_a, scope_b) {
746 Some(r_id) if scope_a == r_id => Ok(ReScope(scope_b)),
747 Some(r_id) if scope_b == r_id => Ok(ReScope(scope_a)),
748 _ => Err(ty::terr_regions_no_overlap(region_a, region_b))
749 }
750 }
751 }
752
753 // ______________________________________________________________________
754
755 #[deriving(Eq, Show)]
756 enum Classification { Expanding, Contracting }
757
758 pub enum VarValue { NoValue, Value(Region), ErrorValue }
759
760 struct VarData {
761 classification: Classification,
762 value: VarValue,
763 }
764
765 struct RegionAndOrigin {
766 region: Region,
767 origin: SubregionOrigin,
768 }
769
770 type RegionGraph = graph::Graph<(), Constraint>;
771
772 impl<'a> RegionVarBindings<'a> {
773 fn infer_variable_values(&self,
774 errors: &mut Vec<RegionResolutionError>)
775 -> Vec<VarValue> {
776 let mut var_data = self.construct_var_data();
777 self.expansion(var_data.as_mut_slice());
778 self.contraction(var_data.as_mut_slice());
779 self.collect_concrete_region_errors(&mut *errors);
780 self.extract_values_and_collect_conflicts(var_data.as_slice(), errors)
781 }
782
783 fn construct_var_data(&self) -> Vec<VarData> {
784 Vec::from_fn(self.num_vars(), |_| {
785 VarData {
786 // All nodes are initially classified as contracting; during
787 // the expansion phase, we will shift the classification for
788 // those nodes that have a concrete region predecessor to
789 // Expanding.
790 classification: Contracting,
791 value: NoValue,
792 }
793 })
794 }
795
796 fn expansion(&self, var_data: &mut [VarData]) {
797 self.iterate_until_fixed_point("Expansion", |constraint| {
798 match *constraint {
799 ConstrainRegSubVar(a_region, b_vid) => {
800 let b_data = &mut var_data[b_vid.to_uint()];
801 self.expand_node(a_region, b_vid, b_data)
802 }
803 ConstrainVarSubVar(a_vid, b_vid) => {
804 match var_data[a_vid.to_uint()].value {
805 NoValue | ErrorValue => false,
806 Value(a_region) => {
807 let b_node = &mut var_data[b_vid.to_uint()];
808 self.expand_node(a_region, b_vid, b_node)
809 }
810 }
811 }
812 ConstrainVarSubReg(..) => {
813 // This is a contraction constraint. Ignore it.
814 false
815 }
816 ConstrainRegSubReg(..) => {
817 // No region variables involved. Ignore.
818 false
819 }
820 }
821 })
822 }
823
824 fn expand_node(&self,
825 a_region: Region,
826 b_vid: RegionVid,
827 b_data: &mut VarData)
828 -> bool {
829 debug!("expand_node({:?}, {:?} == {:?})",
830 a_region, b_vid, b_data.value);
831
832 b_data.classification = Expanding;
833 match b_data.value {
834 NoValue => {
835 debug!("Setting initial value of {:?} to {:?}", b_vid, a_region);
836
837 b_data.value = Value(a_region);
838 return true;
839 }
840
841 Value(cur_region) => {
842 let lub = self.lub_concrete_regions(a_region, cur_region);
843 if lub == cur_region {
844 return false;
845 }
846
847 debug!("Expanding value of {:?} from {:?} to {:?}",
848 b_vid, cur_region, lub);
849
850 b_data.value = Value(lub);
851 return true;
852 }
853
854 ErrorValue => {
855 return false;
856 }
857 }
858 }
859
860 fn contraction(&self,
861 var_data: &mut [VarData]) {
862 self.iterate_until_fixed_point("Contraction", |constraint| {
863 match *constraint {
864 ConstrainRegSubVar(..) => {
865 // This is an expansion constraint. Ignore.
866 false
867 }
868 ConstrainVarSubVar(a_vid, b_vid) => {
869 match var_data[b_vid.to_uint()].value {
870 NoValue | ErrorValue => false,
871 Value(b_region) => {
872 let a_data = &mut var_data[a_vid.to_uint()];
873 self.contract_node(a_vid, a_data, b_region)
874 }
875 }
876 }
877 ConstrainVarSubReg(a_vid, b_region) => {
878 let a_data = &mut var_data[a_vid.to_uint()];
879 self.contract_node(a_vid, a_data, b_region)
880 }
881 ConstrainRegSubReg(..) => {
882 // No region variables involved. Ignore.
883 false
884 }
885 }
886 })
887 }
888
889 fn contract_node(&self,
890 a_vid: RegionVid,
891 a_data: &mut VarData,
892 b_region: Region)
893 -> bool {
894 debug!("contract_node({:?} == {:?}/{:?}, {:?})",
895 a_vid, a_data.value, a_data.classification, b_region);
896
897 return match a_data.value {
898 NoValue => {
899 assert_eq!(a_data.classification, Contracting);
900 a_data.value = Value(b_region);
901 true // changed
902 }
903
904 ErrorValue => {
905 false // no change
906 }
907
908 Value(a_region) => {
909 match a_data.classification {
910 Expanding => {
911 check_node(self, a_vid, a_data, a_region, b_region)
912 }
913 Contracting => {
914 adjust_node(self, a_vid, a_data, a_region, b_region)
915 }
916 }
917 }
918 };
919
920 fn check_node(this: &RegionVarBindings,
921 a_vid: RegionVid,
922 a_data: &mut VarData,
923 a_region: Region,
924 b_region: Region)
925 -> bool {
926 if !this.is_subregion_of(a_region, b_region) {
927 debug!("Setting {:?} to ErrorValue: {:?} not subregion of {:?}",
928 a_vid, a_region, b_region);
929 a_data.value = ErrorValue;
930 }
931 false
932 }
933
934 fn adjust_node(this: &RegionVarBindings,
935 a_vid: RegionVid,
936 a_data: &mut VarData,
937 a_region: Region,
938 b_region: Region)
939 -> bool {
940 match this.glb_concrete_regions(a_region, b_region) {
941 Ok(glb) => {
942 if glb == a_region {
943 false
944 } else {
945 debug!("Contracting value of {:?} from {:?} to {:?}",
946 a_vid, a_region, glb);
947 a_data.value = Value(glb);
948 true
949 }
950 }
951 Err(_) => {
952 debug!("Setting {:?} to ErrorValue: no glb of {:?}, {:?}",
953 a_vid, a_region, b_region);
954 a_data.value = ErrorValue;
955 false
956 }
957 }
958 }
959 }
960
961 fn collect_concrete_region_errors(
962 &self,
963 errors: &mut Vec<RegionResolutionError>)
964 {
965 for (constraint, _) in self.constraints.borrow().iter() {
966 let (sub, sup) = match *constraint {
967 ConstrainVarSubVar(..) |
968 ConstrainRegSubVar(..) |
969 ConstrainVarSubReg(..) => {
970 continue;
971 }
972 ConstrainRegSubReg(sub, sup) => {
973 (sub, sup)
974 }
975 };
976
977 if self.is_subregion_of(sub, sup) {
978 continue;
979 }
980
981 debug!("ConcreteFailure: !(sub <= sup): sub={:?}, sup={:?}",
982 sub, sup);
983 let origin = self.constraints.borrow().get_copy(constraint);
984 errors.push(ConcreteFailure(origin, sub, sup));
985 }
986 }
987
988 fn extract_values_and_collect_conflicts(
989 &self,
990 var_data: &[VarData],
991 errors: &mut Vec<RegionResolutionError>)
992 -> Vec<VarValue> {
993 debug!("extract_values_and_collect_conflicts()");
994
995 // This is the best way that I have found to suppress
996 // duplicate and related errors. Basically we keep a set of
997 // flags for every node. Whenever an error occurs, we will
998 // walk some portion of the graph looking to find pairs of
999 // conflicting regions to report to the user. As we walk, we
1000 // trip the flags from false to true, and if we find that
1001 // we've already reported an error involving any particular
1002 // node we just stop and don't report the current error. The
1003 // idea is to report errors that derive from independent
1004 // regions of the graph, but not those that derive from
1005 // overlapping locations.
1006 let mut dup_vec = Vec::from_elem(self.num_vars(), uint::MAX);
1007
1008 let mut opt_graph = None;
1009
1010 for idx in range(0u, self.num_vars()) {
1011 match var_data[idx].value {
1012 Value(_) => {
1013 /* Inference successful */
1014 }
1015 NoValue => {
1016 /* Unconstrained inference: do not report an error
1017 until the value of this variable is requested.
1018 After all, sometimes we make region variables but never
1019 really use their values. */
1020 }
1021 ErrorValue => {
1022 /* Inference impossible, this value contains
1023 inconsistent constraints.
1024
1025 I think that in this case we should report an
1026 error now---unlike the case above, we can't
1027 wait to see whether the user needs the result
1028 of this variable. The reason is that the mere
1029 existence of this variable implies that the
1030 region graph is inconsistent, whether or not it
1031 is used.
1032
1033 For example, we may have created a region
1034 variable that is the GLB of two other regions
1035 which do not have a GLB. Even if that variable
1036 is not used, it implies that those two regions
1037 *should* have a GLB.
1038
1039 At least I think this is true. It may be that
1040 the mere existence of a conflict in a region variable
1041 that is not used is not a problem, so if this rule
1042 starts to create problems we'll have to revisit
1043 this portion of the code and think hard about it. =) */
1044
1045 if opt_graph.is_none() {
1046 opt_graph = Some(self.construct_graph());
1047 }
1048 let graph = opt_graph.get_ref();
1049
1050 let node_vid = RegionVid { id: idx };
1051 match var_data[idx].classification {
1052 Expanding => {
1053 self.collect_error_for_expanding_node(
1054 graph, var_data, dup_vec.as_mut_slice(),
1055 node_vid, errors);
1056 }
1057 Contracting => {
1058 self.collect_error_for_contracting_node(
1059 graph, var_data, dup_vec.as_mut_slice(),
1060 node_vid, errors);
1061 }
1062 }
1063 }
1064 }
1065 }
1066
1067 Vec::from_fn(self.num_vars(), |idx| var_data[idx].value)
1068 }
1069
1070 fn construct_graph(&self) -> RegionGraph {
1071 let num_vars = self.num_vars();
1072
1073 let constraints = self.constraints.borrow();
1074 let num_edges = constraints.len();
1075
1076 let mut graph = graph::Graph::with_capacity(num_vars + 1,
1077 num_edges);
1078
1079 for _ in range(0u, num_vars) {
1080 graph.add_node(());
1081 }
1082 let dummy_idx = graph.add_node(());
1083
1084 for (constraint, _) in constraints.iter() {
1085 match *constraint {
1086 ConstrainVarSubVar(a_id, b_id) => {
1087 graph.add_edge(NodeIndex(a_id.to_uint()),
1088 NodeIndex(b_id.to_uint()),
1089 *constraint);
1090 }
1091 ConstrainRegSubVar(_, b_id) => {
1092 graph.add_edge(dummy_idx,
1093 NodeIndex(b_id.to_uint()),
1094 *constraint);
1095 }
1096 ConstrainVarSubReg(a_id, _) => {
1097 graph.add_edge(NodeIndex(a_id.to_uint()),
1098 dummy_idx,
1099 *constraint);
1100 }
1101 ConstrainRegSubReg(..) => {
1102 // Relations between two concrete regions do not
1103 // require an edge in the graph.
1104 }
1105 }
1106 }
1107
1108 return graph;
1109 }
1110
1111 fn collect_error_for_expanding_node(
1112 &self,
1113 graph: &RegionGraph,
1114 var_data: &[VarData],
1115 dup_vec: &mut [uint],
1116 node_idx: RegionVid,
1117 errors: &mut Vec<RegionResolutionError>)
1118 {
1119 // Errors in expanding nodes result from a lower-bound that is
1120 // not contained by an upper-bound.
1121 let (mut lower_bounds, lower_dup) =
1122 self.collect_concrete_regions(graph, var_data, node_idx,
1123 graph::Incoming, dup_vec);
1124 let (mut upper_bounds, upper_dup) =
1125 self.collect_concrete_regions(graph, var_data, node_idx,
1126 graph::Outgoing, dup_vec);
1127
1128 if lower_dup || upper_dup {
1129 return;
1130 }
1131
1132 // We place free regions first because we are special casing
1133 // SubSupConflict(ReFree, ReFree) when reporting error, and so
1134 // the user will more likely get a specific suggestion.
1135 fn free_regions_first(a: &RegionAndOrigin,
1136 b: &RegionAndOrigin)
1137 -> Ordering {
1138 match (a.region, b.region) {
1139 (ReFree(..), ReFree(..)) => Equal,
1140 (ReFree(..), _) => Less,
1141 (_, ReFree(..)) => Greater,
1142 (_, _) => Equal,
1143 }
1144 }
1145 lower_bounds.sort_by(|a, b| { free_regions_first(a, b) });
1146 upper_bounds.sort_by(|a, b| { free_regions_first(a, b) });
1147
1148 for lower_bound in lower_bounds.iter() {
1149 for upper_bound in upper_bounds.iter() {
1150 if !self.is_subregion_of(lower_bound.region,
1151 upper_bound.region) {
1152 errors.push(SubSupConflict(
1153 self.var_origins.borrow().get(node_idx.to_uint()).clone(),
1154 lower_bound.origin.clone(),
1155 lower_bound.region,
1156 upper_bound.origin.clone(),
1157 upper_bound.region));
1158 return;
1159 }
1160 }
1161 }
1162
1163 self.tcx.sess.span_bug(
1164 self.var_origins.borrow().get(node_idx.to_uint()).span(),
1165 format!("collect_error_for_expanding_node() could not find error \
1166 for var {:?}, lower_bounds={}, upper_bounds={}",
1167 node_idx,
1168 lower_bounds.iter()
1169 .map(|x| x.region)
1170 .collect::<Vec<ty::Region>>()
1171 .repr(self.tcx),
1172 upper_bounds.iter()
1173 .map(|x| x.region)
1174 .collect::<Vec<ty::Region>>()
1175 .repr(self.tcx)));
1176 }
1177
1178 fn collect_error_for_contracting_node(
1179 &self,
1180 graph: &RegionGraph,
1181 var_data: &[VarData],
1182 dup_vec: &mut [uint],
1183 node_idx: RegionVid,
1184 errors: &mut Vec<RegionResolutionError>)
1185 {
1186 // Errors in contracting nodes result from two upper-bounds
1187 // that have no intersection.
1188 let (upper_bounds, dup_found) =
1189 self.collect_concrete_regions(graph, var_data, node_idx,
1190 graph::Outgoing, dup_vec);
1191
1192 if dup_found {
1193 return;
1194 }
1195
1196 for upper_bound_1 in upper_bounds.iter() {
1197 for upper_bound_2 in upper_bounds.iter() {
1198 match self.glb_concrete_regions(upper_bound_1.region,
1199 upper_bound_2.region) {
1200 Ok(_) => {}
1201 Err(_) => {
1202 errors.push(SupSupConflict(
1203 self.var_origins.borrow().get(node_idx.to_uint()).clone(),
1204 upper_bound_1.origin.clone(),
1205 upper_bound_1.region,
1206 upper_bound_2.origin.clone(),
1207 upper_bound_2.region));
1208 return;
1209 }
1210 }
1211 }
1212 }
1213
1214 self.tcx.sess.span_bug(
1215 self.var_origins.borrow().get(node_idx.to_uint()).span(),
1216 format!("collect_error_for_contracting_node() could not find error \
1217 for var {:?}, upper_bounds={}",
1218 node_idx,
1219 upper_bounds.iter()
1220 .map(|x| x.region)
1221 .collect::<Vec<ty::Region>>()
1222 .repr(self.tcx)));
1223 }
1224
1225 fn collect_concrete_regions(&self,
1226 graph: &RegionGraph,
1227 var_data: &[VarData],
1228 orig_node_idx: RegionVid,
1229 dir: Direction,
1230 dup_vec: &mut [uint])
1231 -> (Vec<RegionAndOrigin> , bool) {
1232 struct WalkState {
1233 set: HashSet<RegionVid>,
1234 stack: Vec<RegionVid> ,
1235 result: Vec<RegionAndOrigin> ,
1236 dup_found: bool
1237 }
1238 let mut state = WalkState {
1239 set: HashSet::new(),
1240 stack: vec!(orig_node_idx),
1241 result: Vec::new(),
1242 dup_found: false
1243 };
1244 state.set.insert(orig_node_idx);
1245
1246 // to start off the process, walk the source node in the
1247 // direction specified
1248 process_edges(self, &mut state, graph, orig_node_idx, dir);
1249
1250 while !state.stack.is_empty() {
1251 let node_idx = state.stack.pop().unwrap();
1252 let classification = var_data[node_idx.to_uint()].classification;
1253
1254 // check whether we've visited this node on some previous walk
1255 if dup_vec[node_idx.to_uint()] == uint::MAX {
1256 dup_vec[node_idx.to_uint()] = orig_node_idx.to_uint();
1257 } else if dup_vec[node_idx.to_uint()] != orig_node_idx.to_uint() {
1258 state.dup_found = true;
1259 }
1260
1261 debug!("collect_concrete_regions(orig_node_idx={:?}, node_idx={:?}, \
1262 classification={:?})",
1263 orig_node_idx, node_idx, classification);
1264
1265 // figure out the direction from which this node takes its
1266 // values, and search for concrete regions etc in that direction
1267 let dir = match classification {
1268 Expanding => graph::Incoming,
1269 Contracting => graph::Outgoing,
1270 };
1271
1272 process_edges(self, &mut state, graph, node_idx, dir);
1273 }
1274
1275 let WalkState {result, dup_found, ..} = state;
1276 return (result, dup_found);
1277
1278 fn process_edges(this: &RegionVarBindings,
1279 state: &mut WalkState,
1280 graph: &RegionGraph,
1281 source_vid: RegionVid,
1282 dir: Direction) {
1283 debug!("process_edges(source_vid={:?}, dir={:?})", source_vid, dir);
1284
1285 let source_node_index = NodeIndex(source_vid.to_uint());
1286 graph.each_adjacent_edge(source_node_index, dir, |_, edge| {
1287 match edge.data {
1288 ConstrainVarSubVar(from_vid, to_vid) => {
1289 let opp_vid =
1290 if from_vid == source_vid {to_vid} else {from_vid};
1291 if state.set.insert(opp_vid) {
1292 state.stack.push(opp_vid);
1293 }
1294 }
1295
1296 ConstrainRegSubVar(region, _) |
1297 ConstrainVarSubReg(_, region) => {
1298 state.result.push(RegionAndOrigin {
1299 region: region,
1300 origin: this.constraints.borrow().get_copy(&edge.data)
1301 });
1302 }
1303
1304 ConstrainRegSubReg(..) => {}
1305 }
1306 true
1307 });
1308 }
1309 }
1310
1311 fn iterate_until_fixed_point(&self,
1312 tag: &str,
1313 body: |constraint: &Constraint| -> bool) {
1314 let mut iteration = 0;
1315 let mut changed = true;
1316 while changed {
1317 changed = false;
1318 iteration += 1;
1319 debug!("---- {} Iteration \\#{}", tag, iteration);
1320 for (constraint, _) in self.constraints.borrow().iter() {
1321 let edge_changed = body(constraint);
1322 if edge_changed {
1323 debug!("Updated due to constraint {}",
1324 constraint.repr(self.tcx));
1325 changed = true;
1326 }
1327 }
1328 }
1329 debug!("---- {} Complete after {} iteration(s)", tag, iteration);
1330 }
1331
1332 }
1333
1334 impl Repr for Constraint {
1335 fn repr(&self, tcx: &ty::ctxt) -> ~str {
1336 match *self {
1337 ConstrainVarSubVar(a, b) => format!("ConstrainVarSubVar({}, {})",
1338 a.repr(tcx), b.repr(tcx)),
1339 ConstrainRegSubVar(a, b) => format!("ConstrainRegSubVar({}, {})",
1340 a.repr(tcx), b.repr(tcx)),
1341 ConstrainVarSubReg(a, b) => format!("ConstrainVarSubReg({}, {})",
1342 a.repr(tcx), b.repr(tcx)),
1343 ConstrainRegSubReg(a, b) => format!("ConstrainRegSubReg({}, {})",
1344 a.repr(tcx), b.repr(tcx)),
1345 }
1346 }
1347 }
librustc/middle/typeck/infer/region_inference/mod.rs:769:1-769:1 -NK_AS_STR_TODO- definition:
type RegionGraph = graph::Graph<(), Constraint>;
impl<'a> RegionVarBindings<'a> {
fn infer_variable_values(&self,
references:- 51112: &self,
1113: graph: &RegionGraph,
1114: var_data: &[VarData],
--
1179: &self,
1180: graph: &RegionGraph,
1181: var_data: &[VarData],
--
1225: fn collect_concrete_regions(&self,
1226: graph: &RegionGraph,
1227: var_data: &[VarData],
--
1279: state: &mut WalkState,
1280: graph: &RegionGraph,
1281: source_vid: RegionVid,
librustc/middle/typeck/infer/region_inference/mod.rs:757:1-757:1 -enum- definition:
pub enum VarValue { NoValue, Value(Region), ErrorValue }
struct VarData {
classification: Classification,
references:- 4774: errors: &mut Vec<RegionResolutionError>)
775: -> Vec<VarValue> {
776: let mut var_data = self.construct_var_data();
--
991: errors: &mut Vec<RegionResolutionError>)
992: -> Vec<VarValue> {
993: debug!("extract_values_and_collect_conflicts()");
librustc/middle/typeck/infer/region_inference/mod.rs:34:31-34:31 -enum- definition:
pub enum Constraint {
ConstrainVarSubVar(RegionVid, RegionVid),
ConstrainRegSubVar(Region, RegionVid),
references:- 11264: pub fn add_constraint(&self,
265: constraint: Constraint,
266: origin: SubregionOrigin) {
--
1334: impl Repr for Constraint {
1335: fn repr(&self, tcx: &ty::ctxt) -> ~str {
librustc/middle/typeck/infer/region_inference/mod.rs:119:1-119:1 -NK_AS_STR_TODO- definition:
pub type CombineMap = HashMap<TwoRegions, RegionVid>;
pub struct RegionVarBindings<'a> {
tcx: &'a ty::ctxt,
references:- 3126: lubs: RefCell<CombineMap>,
127: glbs: RefCell<CombineMap>,
128: skolemization_count: Cell<uint>,
--
392: fn combine_map<'a>(&'a self, t: CombineMapType)
393: -> &'a RefCell<CombineMap> {
394: match t {
librustc/middle/typeck/infer/region_inference/mod.rs:121:1-121:1 -struct- definition:
pub struct RegionVarBindings<'a> {
tcx: &'a ty::ctxt,
var_origins: RefCell<Vec<RegionVariableOrigin>>,
references:- 12146: pub fn RegionVarBindings<'a>(tcx: &'a ty::ctxt) -> RegionVarBindings<'a> {
147: RegionVarBindings {
148: tcx: tcx,
--
404: origin: SubregionOrigin,
405: relate: |this: &RegionVarBindings,
406: old_r: Region,
--
934: fn adjust_node(this: &RegionVarBindings,
935: a_vid: RegionVid,
--
1278: fn process_edges(this: &RegionVarBindings,
1279: state: &mut WalkState,
librustc/middle/typeck/infer/mod.rs:
96: // For region variables.
97: pub region_vars: RegionVarBindings<'a>,
98: }
librustc/middle/typeck/infer/region_inference/mod.rs:
620: fn helper(this: &RegionVarBindings,
621: a: &FreeRegion,
librustc/middle/typeck/infer/region_inference/mod.rs:1135:8-1135:8 -fn- definition:
fn free_regions_first(a: &RegionAndOrigin,
b: &RegionAndOrigin)
-> Ordering {
references:- 21145: lower_bounds.sort_by(|a, b| { free_regions_first(a, b) });
1146: upper_bounds.sort_by(|a, b| { free_regions_first(a, b) });
librustc/middle/typeck/infer/region_inference/mod.rs:620:8-620:8 -fn- definition:
fn helper(this: &RegionVarBindings,
a: &FreeRegion,
b: &FreeRegion) -> ty::Region
references:- 2615: Less => helper(self, a, b),
616: Greater => helper(self, b, a),
617: Equal => ty::ReFree(*a)
librustc/middle/typeck/infer/region_inference/mod.rs:764:1-764:1 -struct- definition:
struct RegionAndOrigin {
region: Region,
origin: SubregionOrigin,
references:- 51234: stack: Vec<RegionVid> ,
1235: result: Vec<RegionAndOrigin> ,
1236: dup_found: bool
--
1297: ConstrainVarSubReg(_, region) => {
1298: state.result.push(RegionAndOrigin {
1299: region: region,
librustc/middle/typeck/infer/region_inference/mod.rs:54:1-54:1 -enum- definition:
pub enum CombineMapType {
Lub, Glb
}
references:- 3400: pub fn combine_vars(&self,
401: t: CombineMapType,
402: a: Region,
librustc/middle/typeck/infer/region_inference/mod.rs:59:19-59:19 -enum- definition:
pub enum RegionResolutionError {
/// `ConcreteFailure(o, a, b)`:
///
references:- 14990: var_data: &[VarData],
991: errors: &mut Vec<RegionResolutionError>)
992: -> Vec<VarValue> {
--
1183: node_idx: RegionVid,
1184: errors: &mut Vec<RegionResolutionError>)
1185: {
librustc/middle/typeck/infer/error_reporting.rs:
97: fn process_errors(&self, errors: &Vec<RegionResolutionError>)
98: -> Vec<RegionResolutionError>;
--
202: fn process_errors(&self, errors: &Vec<RegionResolutionError>)
203: -> Vec<RegionResolutionError> {
204: debug!("process_errors()");
librustc/middle/typeck/infer/region_inference/mod.rs:
522: */
523: pub fn resolve_regions(&self) -> Vec<RegionResolutionError> {
524: debug!("RegionVarBindings: resolve_regions()");
librustc/middle/typeck/infer/region_inference/mod.rs:42:31-42:31 -struct- definition:
pub struct TwoRegions {
a: Region,
b: Region,
references:- 14408: -> Region {
409: let vars = TwoRegions { a: a, b: b };
410: match self.combine_map(t).borrow().find(&vars) {
librustc/middle/typeck/infer/region_inference/mod.rs:718:8-718:8 -fn- definition:
fn helper(this: &RegionVarBindings,
a: &FreeRegion,
b: &FreeRegion) -> cres<ty::Region>
references:- 2712: return match a.cmp(b) {
713: Less => helper(self, a, b),
714: Greater => helper(self, b, a),
715: Equal => Ok(ty::ReFree(*a))
librustc/middle/typeck/infer/region_inference/mod.rs:759:1-759:1 -struct- definition:
struct VarData {
classification: Classification,
value: VarValue,
references:- 12784: Vec::from_fn(self.num_vars(), |_| {
785: VarData {
786: // All nodes are initially classified as contracting; during
--
890: a_vid: RegionVid,
891: a_data: &mut VarData,
892: b_region: Region)
--
1113: graph: &RegionGraph,
1114: var_data: &[VarData],
1115: dup_vec: &mut [uint],
--
1180: graph: &RegionGraph,
1181: var_data: &[VarData],
1182: dup_vec: &mut [uint],
--
1226: graph: &RegionGraph,
1227: var_data: &[VarData],
1228: orig_node_idx: RegionVid,
librustc/middle/typeck/infer/region_inference/mod.rs:502:8-502:8 -fn- definition:
fn consider_adding_edge(result_set: Vec<Region> ,
r: Region,
r1: Region,
references:- 2489: result_set =
490: consider_adding_edge(result_set, r, r2, r1);
491: }
librustc/middle/typeck/infer/region_inference/mod.rs:104:19-104:19 -struct- definition:
pub struct SameRegions {
pub scope_id: ast::NodeId,
pub regions: Vec<BoundRegion>
references:- 15103: /// 'a and 'b together inside a SameRegions struct
105: pub struct SameRegions {
librustc/middle/typeck/infer/error_reporting.rs:
327: }
328: same_regions.push(SameRegions {
329: scope_id: scope_id,
librustc/middle/typeck/infer/region_inference/mod.rs:
103: /// 'a and 'b together inside a SameRegions struct
105: pub struct SameRegions {
--
110: impl SameRegions {
111: pub fn contains(&self, other: &BoundRegion) -> bool {
librustc/middle/typeck/infer/error_reporting.rs:
317: fn append_to_same_regions(same_regions: &mut Vec<SameRegions>,
318: same_frs: &FreeRegionsFromSameFn) {
--
661: trace_origins: &[(TypeTrace, ty::type_err)],
662: same_regions: &[SameRegions]) {
663: self.give_suggestion(same_regions);
--
721: generics: &'a ast::Generics,
722: same_regions: &'a [SameRegions],
723: life_giver: &'a LifeGiver,
--
737: generics: &'a ast::Generics,
738: same_regions: &'a [SameRegions],
739: life_giver: &'a LifeGiver)
--
814: fn extract_anon_nums_and_names(&self, same_regions: &SameRegions)
815: -> (HashSet<uint>, HashSet<ast::Name>) {
librustc/middle/typeck/infer/region_inference/mod.rs:1232:8-1232:8 -struct- definition:
struct WalkState {
set: HashSet<RegionVid>,
stack: Vec<RegionVid> ,
references:- 31237: }
1238: let mut state = WalkState {
1239: set: HashSet::new(),
--
1275: let WalkState {result, dup_found, ..} = state;
1276: return (result, dup_found);
--
1278: fn process_edges(this: &RegionVarBindings,
1279: state: &mut WalkState,
1280: graph: &RegionGraph,
librustc/middle/typeck/infer/region_inference/mod.rs:1278:8-1278:8 -fn- definition:
fn process_edges(this: &RegionVarBindings,
state: &mut WalkState,
graph: &RegionGraph,
references:- 21272: process_edges(self, &mut state, graph, node_idx, dir);
1273: }
librustc/middle/typeck/infer/region_inference/mod.rs:755:22-755:22 -enum- definition:
enum Classification { Expanding, Contracting }
pub enum VarValue { NoValue, Value(Region), ErrorValue }
struct VarData {
references:- 5756: enum Classification { Expanding, Contracting }
--
760: struct VarData {
761: classification: Classification,
762: value: VarValue,