diff options
| -rw-r--r-- | src/librustc/infer/lexical_region_resolve/graphviz.rs | 20 | ||||
| -rw-r--r-- | src/librustc/infer/lexical_region_resolve/mod.rs | 10 | ||||
| -rw-r--r-- | src/librustc/infer/mod.rs | 9 | ||||
| -rw-r--r-- | src/librustc/infer/region_constraints/mod.rs | 203 |
4 files changed, 123 insertions, 119 deletions
diff --git a/src/librustc/infer/lexical_region_resolve/graphviz.rs b/src/librustc/infer/lexical_region_resolve/graphviz.rs index 880c0e22947..41209487395 100644 --- a/src/librustc/infer/lexical_region_resolve/graphviz.rs +++ b/src/librustc/infer/lexical_region_resolve/graphviz.rs @@ -25,7 +25,7 @@ use middle::free_region::RegionRelations; use middle::region; use super::Constraint; use infer::SubregionOrigin; -use infer::region_constraints::RegionConstraintCollector; +use infer::region_constraints::RegionConstraintData; use util::nodemap::{FxHashMap, FxHashSet}; use std::borrow::Cow; @@ -57,7 +57,7 @@ graphs will be printed. \n\ } pub fn maybe_print_constraints_for<'a, 'gcx, 'tcx>( - region_constraints: &RegionConstraintCollector<'tcx>, + region_data: &RegionConstraintData<'tcx>, region_rels: &RegionRelations<'a, 'gcx, 'tcx>) { let tcx = region_rels.tcx; @@ -113,7 +113,7 @@ pub fn maybe_print_constraints_for<'a, 'gcx, 'tcx>( } }; - match dump_region_constraints_to(region_rels, ®ion_constraints.constraints, &output_path) { + match dump_region_data_to(region_rels, ®ion_data.constraints, &output_path) { Ok(()) => {} Err(e) => { let msg = format!("io error dumping region constraints: {}", e); @@ -267,15 +267,15 @@ impl<'a, 'gcx, 'tcx> dot::GraphWalk<'a> for ConstraintGraph<'a, 'gcx, 'tcx> { pub type ConstraintMap<'tcx> = BTreeMap<Constraint<'tcx>, SubregionOrigin<'tcx>>; -fn dump_region_constraints_to<'a, 'gcx, 'tcx>(region_rels: &RegionRelations<'a, 'gcx, 'tcx>, - map: &ConstraintMap<'tcx>, - path: &str) - -> io::Result<()> { - debug!("dump_region_constraints map (len: {}) path: {}", +fn dump_region_data_to<'a, 'gcx, 'tcx>(region_rels: &RegionRelations<'a, 'gcx, 'tcx>, + map: &ConstraintMap<'tcx>, + path: &str) + -> io::Result<()> { + debug!("dump_region_data map (len: {}) path: {}", map.len(), path); - let g = ConstraintGraph::new(format!("region_constraints"), region_rels, map); - debug!("dump_region_constraints calling render"); + let g = ConstraintGraph::new(format!("region_data"), region_rels, map); + debug!("dump_region_data calling render"); let mut v = Vec::new(); dot::render(&g, &mut v).unwrap(); File::create(path).and_then(|mut f| f.write_all(&v)) diff --git a/src/librustc/infer/lexical_region_resolve/mod.rs b/src/librustc/infer/lexical_region_resolve/mod.rs index 9a02b274b5f..3522420a5dc 100644 --- a/src/librustc/infer/lexical_region_resolve/mod.rs +++ b/src/librustc/infer/lexical_region_resolve/mod.rs @@ -14,7 +14,7 @@ use infer::SubregionOrigin; use infer::RegionVariableOrigin; use infer::region_constraints::Constraint; use infer::region_constraints::GenericKind; -use infer::region_constraints::RegionConstraintCollector; +use infer::region_constraints::RegionConstraintData; use infer::region_constraints::VerifyBound; use middle::free_region::RegionRelations; use rustc_data_structures::fx::FxHashSet; @@ -73,20 +73,20 @@ struct RegionAndOrigin<'tcx> { type RegionGraph<'tcx> = graph::Graph<(), Constraint<'tcx>>; -impl<'tcx> RegionConstraintCollector<'tcx> { +impl<'tcx> RegionConstraintData<'tcx> { /// This function performs the actual region resolution. It must be /// called after all constraints have been added. It performs a /// fixed-point iteration to find region values which satisfy all /// constraints, assuming such values can be found; if they cannot, /// errors are reported. pub fn resolve_regions( - &mut self, + mut self, region_rels: &RegionRelations<'_, '_, 'tcx>, ) -> ( LexicalRegionResolutions<'tcx>, Vec<RegionResolutionError<'tcx>>, ) { - debug!("RegionConstraintCollector: resolve_regions()"); + debug!("RegionConstraintData: resolve_regions()"); let mut errors = vec![]; let values = self.infer_variable_values(region_rels, &mut errors); (values, errors) @@ -642,7 +642,7 @@ impl<'tcx> RegionConstraintCollector<'tcx> { return (result, dup_found); fn process_edges<'tcx>( - this: &RegionConstraintCollector<'tcx>, + this: &RegionConstraintData<'tcx>, state: &mut WalkState<'tcx>, graph: &RegionGraph<'tcx>, source_vid: RegionVid, diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs index a5cae839aa7..53112bcd880 100644 --- a/src/librustc/infer/mod.rs +++ b/src/librustc/infer/mod.rs @@ -1132,10 +1132,11 @@ impl<'a, 'gcx, 'tcx> InferCtxt<'a, 'gcx, 'tcx> { region_context, region_map, free_regions); - let mut region_constraints = self.region_constraints.borrow_mut() - .take() - .expect("regions already resolved"); - let (lexical_region_resolutions, errors) = region_constraints.resolve_regions(®ion_rels); + let region_data = self.region_constraints.borrow_mut() + .take() + .expect("regions already resolved") + .into_data(); + let (lexical_region_resolutions, errors) = region_data.resolve_regions(®ion_rels); let old_value = self.lexical_region_resolutions.replace(Some(lexical_region_resolutions)); assert!(old_value.is_none()); diff --git a/src/librustc/infer/region_constraints/mod.rs b/src/librustc/infer/region_constraints/mod.rs index 446acac4fd1..d2cd52c73e2 100644 --- a/src/librustc/infer/region_constraints/mod.rs +++ b/src/librustc/infer/region_constraints/mod.rs @@ -30,6 +30,69 @@ use std::u32; mod taint; +pub struct RegionConstraintCollector<'tcx> { + data: RegionConstraintData<'tcx>, + lubs: CombineMap<'tcx>, + glbs: CombineMap<'tcx>, + skolemization_count: u32, + bound_count: u32, + + /// The undo log records actions that might later be undone. + /// + /// Note: when the undo_log is empty, we are not actively + /// snapshotting. When the `start_snapshot()` method is called, we + /// push an OpenSnapshot entry onto the list to indicate that we + /// are now actively snapshotting. The reason for this is that + /// otherwise we end up adding entries for things like the lower + /// bound on a variable and so forth, which can never be rolled + /// back. + undo_log: Vec<UndoLogEntry<'tcx>>, + + unification_table: UnificationTable<ty::RegionVid>, +} + +/// The full set of region constraints gathered up by the collector. +/// Describes a set of region variables ranging from 0..N (where N is +/// the length of the `var_origins` vector), and various constraints +/// between them. +#[derive(Default)] +pub struct RegionConstraintData<'tcx> { + /// For each `RegionVid`, the corresponding `RegionVariableOrigin`. + pub var_origins: Vec<RegionVariableOrigin>, + + /// Constraints of the form `A <= B`, where either `A` or `B` can + /// be a region variable (or neither, as it happens). + pub constraints: BTreeMap<Constraint<'tcx>, SubregionOrigin<'tcx>>, + + /// A "verify" is something that we need to verify after inference + /// is done, but which does not directly affect inference in any + /// way. + /// + /// An example is a `A <= B` where neither `A` nor `B` are + /// inference variables. + pub verifys: Vec<Verify<'tcx>>, + + /// A "given" is a relationship that is known to hold. In + /// particular, we often know from closure fn signatures that a + /// particular free region must be a subregion of a region + /// variable: + /// + /// foo.iter().filter(<'a> |x: &'a &'b T| ...) + /// + /// In situations like this, `'b` is in fact a region variable + /// introduced by the call to `iter()`, and `'a` is a bound region + /// on the closure (as indicated by the `<'a>` prefix). If we are + /// naive, we wind up inferring that `'b` must be `'static`, + /// because we require that it be greater than `'a` and we do not + /// know what `'a` is precisely. + /// + /// This hashmap is used to avoid that naive scenario. Basically + /// we record the fact that `'a <= 'b` is implied by the fn + /// signature, and then ignore the constraint when solving + /// equations. This is a bit of a hack but seems to work. + pub givens: FxHashSet<(Region<'tcx>, ty::RegionVid)>, +} + /// A constraint that influences the inference process. #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, PartialOrd, Ord)] pub enum Constraint<'tcx> { @@ -143,65 +206,6 @@ enum CombineMapType { type CombineMap<'tcx> = FxHashMap<TwoRegions<'tcx>, RegionVid>; -pub struct RegionConstraintCollector<'tcx> { - pub(in infer) var_origins: Vec<RegionVariableOrigin>, - - /// Constraints of the form `A <= B` introduced by the region - /// checker. Here at least one of `A` and `B` must be a region - /// variable. - /// - /// Using `BTreeMap` because the order in which we iterate over - /// these constraints can affect the way we build the region graph, - /// which in turn affects the way that region errors are reported, - /// leading to small variations in error output across runs and - /// platforms. - pub(in infer) constraints: BTreeMap<Constraint<'tcx>, SubregionOrigin<'tcx>>, - - /// A "verify" is something that we need to verify after inference is - /// done, but which does not directly affect inference in any way. - /// - /// An example is a `A <= B` where neither `A` nor `B` are - /// inference variables. - pub(in infer) verifys: Vec<Verify<'tcx>>, - - /// A "given" is a relationship that is known to hold. In particular, - /// we often know from closure fn signatures that a particular free - /// region must be a subregion of a region variable: - /// - /// foo.iter().filter(<'a> |x: &'a &'b T| ...) - /// - /// In situations like this, `'b` is in fact a region variable - /// introduced by the call to `iter()`, and `'a` is a bound region - /// on the closure (as indicated by the `<'a>` prefix). If we are - /// naive, we wind up inferring that `'b` must be `'static`, - /// because we require that it be greater than `'a` and we do not - /// know what `'a` is precisely. - /// - /// This hashmap is used to avoid that naive scenario. Basically we - /// record the fact that `'a <= 'b` is implied by the fn signature, - /// and then ignore the constraint when solving equations. This is - /// a bit of a hack but seems to work. - pub(in infer) givens: FxHashSet<(Region<'tcx>, ty::RegionVid)>, - - lubs: CombineMap<'tcx>, - glbs: CombineMap<'tcx>, - skolemization_count: u32, - bound_count: u32, - - /// The undo log records actions that might later be undone. - /// - /// Note: when the undo_log is empty, we are not actively - /// snapshotting. When the `start_snapshot()` method is called, we - /// push an OpenSnapshot entry onto the list to indicate that we - /// are now actively snapshotting. The reason for this is that - /// otherwise we end up adding entries for things like the lower - /// bound on a variable and so forth, which can never be rolled - /// back. - undo_log: Vec<UndoLogEntry<'tcx>>, - - unification_table: UnificationTable<ty::RegionVid>, -} - pub struct RegionSnapshot { length: usize, region_snapshot: unify::Snapshot<ty::RegionVid>, @@ -245,10 +249,7 @@ impl TaintDirections { impl<'tcx> RegionConstraintCollector<'tcx> { pub fn new() -> RegionConstraintCollector<'tcx> { RegionConstraintCollector { - var_origins: Vec::new(), - constraints: BTreeMap::new(), - verifys: Vec::new(), - givens: FxHashSet(), + data: RegionConstraintData::default(), lubs: FxHashMap(), glbs: FxHashMap(), skolemization_count: 0, @@ -258,6 +259,11 @@ impl<'tcx> RegionConstraintCollector<'tcx> { } } + /// Once all the constraints have been gathered, extract out the final data. + pub fn into_data(self) -> RegionConstraintData<'tcx> { + self.data + } + fn in_snapshot(&self) -> bool { !self.undo_log.is_empty() } @@ -289,8 +295,7 @@ impl<'tcx> RegionConstraintCollector<'tcx> { } else { (*self.undo_log)[snapshot.length] = CommitedSnapshot; } - self.unification_table - .commit(snapshot.region_snapshot); + self.unification_table.commit(snapshot.region_snapshot); } pub fn rollback_to(&mut self, snapshot: RegionSnapshot) { @@ -304,8 +309,7 @@ impl<'tcx> RegionConstraintCollector<'tcx> { let c = self.undo_log.pop().unwrap(); assert!(c == OpenSnapshot); self.skolemization_count = snapshot.skolemization_count; - self.unification_table - .rollback_to(snapshot.region_snapshot); + self.unification_table.rollback_to(snapshot.region_snapshot); } fn rollback_undo_entry(&mut self, undo_entry: UndoLogEntry<'tcx>) { @@ -317,18 +321,18 @@ impl<'tcx> RegionConstraintCollector<'tcx> { // nothing to do here } AddVar(vid) => { - self.var_origins.pop().unwrap(); - assert_eq!(self.var_origins.len(), vid.index as usize); + self.data.var_origins.pop().unwrap(); + assert_eq!(self.data.var_origins.len(), vid.index as usize); } AddConstraint(ref constraint) => { - self.constraints.remove(constraint); + self.data.constraints.remove(constraint); } AddVerify(index) => { - self.verifys.pop(); - assert_eq!(self.verifys.len(), index); + self.data.verifys.pop(); + assert_eq!(self.data.verifys.len(), index); } AddGiven(sub, sup) => { - self.givens.remove(&(sub, sup)); + self.data.givens.remove(&(sub, sup)); } AddCombination(Glb, ref regions) => { self.glbs.remove(regions); @@ -339,18 +343,11 @@ impl<'tcx> RegionConstraintCollector<'tcx> { } } - pub fn num_vars(&self) -> u32 { - let len = self.var_origins.len(); - // enforce no overflow - assert!(len as u32 as usize == len); - len as u32 - } - pub fn new_region_var(&mut self, origin: RegionVariableOrigin) -> RegionVid { let vid = RegionVid { - index: self.num_vars(), + index: self.data.num_vars(), }; - self.var_origins.push(origin.clone()); + self.data.var_origins.push(origin.clone()); let u_vid = self.unification_table .new_key(unify_key::RegionVidKey { min_vid: vid }); @@ -367,7 +364,7 @@ impl<'tcx> RegionConstraintCollector<'tcx> { } pub fn var_origin(&self, vid: RegionVid) -> RegionVariableOrigin { - self.var_origins[vid.index as usize].clone() + self.data.var_origins[vid.index as usize].clone() } /// Creates a new skolemized region. Skolemized regions are fresh @@ -523,21 +520,22 @@ impl<'tcx> RegionConstraintCollector<'tcx> { fn add_constraint(&mut self, constraint: Constraint<'tcx>, origin: SubregionOrigin<'tcx>) { // cannot add constraints once regions are resolved - debug!("RegionConstraintCollector: add_constraint({:?})", constraint); + debug!( + "RegionConstraintCollector: add_constraint({:?})", + constraint + ); // never overwrite an existing (constraint, origin) - only insert one if it isn't // present in the map yet. This prevents origins from outside the snapshot being // replaced with "less informative" origins e.g. during calls to `can_eq` let in_snapshot = self.in_snapshot(); let undo_log = &mut self.undo_log; - self.constraints - .entry(constraint) - .or_insert_with(|| { - if in_snapshot { - undo_log.push(AddConstraint(constraint)); - } - origin - }); + self.data.constraints.entry(constraint).or_insert_with(|| { + if in_snapshot { + undo_log.push(AddConstraint(constraint)); + } + origin + }); } fn add_verify(&mut self, verify: Verify<'tcx>) { @@ -552,8 +550,8 @@ impl<'tcx> RegionConstraintCollector<'tcx> { _ => {} } - let index = self.verifys.len(); - self.verifys.push(verify); + let index = self.data.verifys.len(); + self.data.verifys.push(verify); if self.in_snapshot() { self.undo_log.push(AddVerify(index)); } @@ -561,7 +559,7 @@ impl<'tcx> RegionConstraintCollector<'tcx> { pub fn add_given(&mut self, sub: Region<'tcx>, sup: ty::RegionVid) { // cannot add givens once regions are resolved - if self.givens.insert((sub, sup)) { + if self.data.givens.insert((sub, sup)) { debug!("add_given({:?} <= {:?})", sub, sup); self.undo_log.push(AddGiven(sub, sup)); @@ -767,11 +765,7 @@ impl<'tcx> RegionConstraintCollector<'tcx> { // edges and add any new regions we find to result_set. This // is not a terribly efficient implementation. let mut taint_set = taint::TaintSet::new(directions, r0); - taint_set.fixed_point( - tcx, - &self.undo_log[mark.length..], - &self.verifys, - ); + taint_set.fixed_point(tcx, &self.undo_log[mark.length..], &self.data.verifys); debug!("tainted: result={:?}", taint_set); return taint_set.into_set(); } @@ -866,3 +860,12 @@ impl<'a, 'gcx, 'tcx> VerifyBound<'tcx> { } } } + +impl<'tcx> RegionConstraintData<'tcx> { + pub fn num_vars(&self) -> u32 { + let len = self.var_origins.len(); + // enforce no overflow + assert!(len as u32 as usize == len); + len as u32 + } +} |