diff options
| -rw-r--r-- | src/librustc/ich/impls_ty.rs | 1 | ||||
| -rw-r--r-- | src/librustc/infer/canonical/canonicalizer.rs | 35 | ||||
| -rw-r--r-- | src/librustc/infer/canonical/mod.rs | 102 | ||||
| -rw-r--r-- | src/librustc/infer/canonical/query_response.rs | 32 | ||||
| -rw-r--r-- | src/librustc/ty/mod.rs | 2 |
5 files changed, 144 insertions, 28 deletions
diff --git a/src/librustc/ich/impls_ty.rs b/src/librustc/ich/impls_ty.rs index 16a7f1425ab..2109c4950e5 100644 --- a/src/librustc/ich/impls_ty.rs +++ b/src/librustc/ich/impls_ty.rs @@ -1285,6 +1285,7 @@ impl_stable_hash_for!(struct infer::canonical::CanonicalVarInfo { impl_stable_hash_for!(enum infer::canonical::CanonicalVarKind { Ty(k), Region(ui), + PlaceholderRegion(placeholder), }); impl_stable_hash_for!(enum infer::canonical::CanonicalTyVarKind { diff --git a/src/librustc/infer/canonical/canonicalizer.rs b/src/librustc/infer/canonical/canonicalizer.rs index 536da55adc4..72bf8f96fe1 100644 --- a/src/librustc/infer/canonical/canonicalizer.rs +++ b/src/librustc/infer/canonical/canonicalizer.rs @@ -162,11 +162,18 @@ struct CanonicalizeQueryResponse; impl CanonicalizeRegionMode for CanonicalizeQueryResponse { fn canonicalize_free_region( &self, - _canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>, + canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>, r: ty::Region<'tcx>, ) -> ty::Region<'tcx> { match r { ty::ReFree(_) | ty::ReEmpty | ty::ReErased | ty::ReStatic | ty::ReEarlyBound(..) => r, + ty::RePlaceholder(placeholder) => { + let info = CanonicalVarInfo { + kind: CanonicalVarKind::PlaceholderRegion(*placeholder), + }; + let cvar = canonicalizer.canonical_var(info, r.into()); + canonicalizer.tcx.mk_region(ty::ReCanonical(cvar.var)) + } _ => { // Other than `'static` or `'empty`, the query // response should be executing in a fully @@ -190,7 +197,7 @@ impl CanonicalizeRegionMode for CanonicalizeAllFreeRegions { canonicalizer: &mut Canonicalizer<'_, '_, 'tcx>, r: ty::Region<'tcx>, ) -> ty::Region<'tcx> { - canonicalizer.canonical_var_for_region(r) + canonicalizer.canonical_var_for_region_in_root_universe(r) } fn any(&self) -> bool { @@ -209,7 +216,7 @@ impl CanonicalizeRegionMode for CanonicalizeFreeRegionsOtherThanStatic { if let ty::ReStatic = r { r } else { - canonicalizer.canonical_var_for_region(r) + canonicalizer.canonical_var_for_region_in_root_universe(r) } } @@ -252,7 +259,7 @@ impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for Canonicalizer<'cx, 'gcx, 'tcx> opportunistically resolved to {:?}", vid, r ); - self.canonical_var_for_region(r) + self.canonical_var_for_region_in_root_universe(r) } ty::ReStatic @@ -459,9 +466,23 @@ impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> { } } - fn canonical_var_for_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { - // TODO: root is not always what we want here, but we'll - // address that in a later commit. + /// Shorthand helper that creates a canonical region variable for + /// `r` (always in the root universe). The reason that we always + /// put these variables into the root universe is because this + /// method is used during **query construction:** in that case, we + /// are taking all the regions and just putting them into the most + /// generic context we can. This may generate solutions that don't + /// fit (e.g., that equate some region variable with a placeholder + /// it can't name) on the caller side, but that's ok, the caller + /// can figure that out. In the meantime, it maximizes our + /// caching. + /// + /// (This works because unification never fails -- and hence trait + /// selection is never affected -- due to a universe mismatch.) + fn canonical_var_for_region_in_root_universe( + &mut self, + r: ty::Region<'tcx>, + ) -> ty::Region<'tcx> { let info = CanonicalVarInfo { kind: CanonicalVarKind::Region(ty::UniverseIndex::ROOT), }; diff --git a/src/librustc/infer/canonical/mod.rs b/src/librustc/infer/canonical/mod.rs index 24864d77927..f2b7c6e0d0d 100644 --- a/src/librustc/infer/canonical/mod.rs +++ b/src/librustc/infer/canonical/mod.rs @@ -33,14 +33,14 @@ use infer::{InferCtxt, RegionVariableOrigin, TypeVariableOrigin}; use rustc_data_structures::indexed_vec::IndexVec; -use smallvec::SmallVec; use rustc_data_structures::sync::Lrc; use serialize::UseSpecializedDecodable; +use smallvec::SmallVec; use std::ops::Index; use syntax::source_map::Span; use ty::fold::TypeFoldable; use ty::subst::Kind; -use ty::{self, BoundTyIndex, Lift, Region, List, TyCtxt}; +use ty::{self, BoundTyIndex, Lift, List, Region, TyCtxt}; mod canonicalizer; @@ -80,13 +80,31 @@ pub struct CanonicalVarValues<'tcx> { /// various parts of it with canonical variables. This struct stores /// those replaced bits to remember for when we process the query /// result. -#[derive(Clone, Debug, Default, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)] +#[derive(Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)] pub struct OriginalQueryValues<'tcx> { + /// Map from the universes that appear in the query to the + /// universes in the caller context. For the time being, we only + /// ever put ROOT values into the query, so this map is very + /// simple. + pub universe_map: SmallVec<[ty::UniverseIndex; 4]>, + /// This is equivalent to `CanonicalVarValues`, but using a /// `SmallVec` yields a significant performance win. pub var_values: SmallVec<[Kind<'tcx>; 8]>, } +impl Default for OriginalQueryValues<'tcx> { + fn default() -> Self { + let mut universe_map = SmallVec::default(); + universe_map.push(ty::UniverseIndex::ROOT); + + Self { + universe_map, + var_values: SmallVec::default(), + } + } +} + /// Information about a canonical variable that is included with the /// canonical value. This is sufficient information for code to create /// a copy of the canonical value in some other inference context, @@ -97,9 +115,17 @@ pub struct CanonicalVarInfo { } impl CanonicalVarInfo { - pub fn universe(self) -> ty::UniverseIndex { + pub fn universe(&self) -> ty::UniverseIndex { self.kind.universe() } + + pub fn is_existential(&self) -> bool { + match self.kind { + CanonicalVarKind::Ty(_) => true, + CanonicalVarKind::Region(_) => true, + CanonicalVarKind::PlaceholderRegion(..) => false, + } + } } /// Describes the "kind" of the canonical variable. This is a "kind" @@ -112,8 +138,12 @@ pub enum CanonicalVarKind { /// Region variable `'?R`. Region(ty::UniverseIndex), -} + /// A "placeholder" that represents "any region". Created when you + /// are solving a goal like `for<'a> T: Foo<'a>` to represent the + /// bound region `'a`. + PlaceholderRegion(ty::Placeholder), +} impl CanonicalVarKind { pub fn universe(self) -> ty::UniverseIndex { @@ -125,6 +155,7 @@ impl CanonicalVarKind { // Region variables can be created in sub-universes. CanonicalVarKind::Region(ui) => ui, + CanonicalVarKind::PlaceholderRegion(placeholder) => placeholder.universe, } } } @@ -242,8 +273,16 @@ impl<'gcx, V> Canonical<'gcx, V> { /// let b: Canonical<'tcx, (T, Ty<'tcx>)> = a.unchecked_map(|v| (v, ty)); /// ``` pub fn unchecked_map<W>(self, map_op: impl FnOnce(V) -> W) -> Canonical<'gcx, W> { - let Canonical { max_universe, variables, value } = self; - Canonical { max_universe, variables, value: map_op(value) } + let Canonical { + max_universe, + variables, + value, + } = self; + Canonical { + max_universe, + variables, + value: map_op(value), + } } } @@ -271,35 +310,50 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { where T: TypeFoldable<'tcx>, { + // For each universe that is referred to in the incoming + // query, create a universe in our local inference context. In + // practice, as of this writing, all queries have no universes + // in them, so this code has no effect, but it is looking + // forward to the day when we *do* want to carry universes + // through into queries. + let universes: IndexVec<ty::UniverseIndex, _> = std::iter::once(ty::UniverseIndex::ROOT) + .chain((0..canonical.max_universe.as_u32()).map(|_| self.create_next_universe())) + .collect(); + let canonical_inference_vars = - self.fresh_inference_vars_for_canonical_vars(span, canonical.variables); + self.instantiate_canonical_vars(span, canonical.variables, |ui| universes[ui]); let result = canonical.substitute(self.tcx, &canonical_inference_vars); (result, canonical_inference_vars) } /// Given the "infos" about the canonical variables from some - /// canonical, creates fresh inference variables with the same - /// characteristics. You can then use `substitute` to instantiate - /// the canonical variable with these inference variables. - fn fresh_inference_vars_for_canonical_vars( + /// canonical, creates fresh variables with the same + /// characteristics (see `instantiate_canonical_var` for + /// details). You can then use `substitute` to instantiate the + /// canonical variable with these inference variables. + fn instantiate_canonical_vars( &self, span: Span, variables: &List<CanonicalVarInfo>, + universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex, ) -> CanonicalVarValues<'tcx> { let var_values: IndexVec<BoundTyIndex, Kind<'tcx>> = variables .iter() - .map(|info| self.fresh_inference_var_for_canonical_var(span, *info)) + .map(|info| self.instantiate_canonical_var(span, *info, &universe_map)) .collect(); CanonicalVarValues { var_values } } /// Given the "info" about a canonical variable, creates a fresh - /// inference variable with the same characteristics. - fn fresh_inference_var_for_canonical_var( + /// variable for it. If this is an existentially quantified + /// variable, then you'll get a new inference variable; if it is a + /// universally quantified variable, you get a placeholder. + fn instantiate_canonical_var( &self, span: Span, cv_info: CanonicalVarInfo, + universe_map: impl Fn(ty::UniverseIndex) -> ty::UniverseIndex, ) -> Kind<'tcx> { match cv_info.kind { CanonicalVarKind::Ty(ty_kind) => { @@ -315,9 +369,21 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { ty.into() } - CanonicalVarKind::Region(ui) => self - .next_region_var_in_universe(RegionVariableOrigin::MiscVariable(span), ui) - .into(), + CanonicalVarKind::Region(ui) => self.next_region_var_in_universe( + RegionVariableOrigin::MiscVariable(span), + universe_map(ui), + ).into(), + + CanonicalVarKind::PlaceholderRegion(ty::Placeholder { universe, name }) => { + let universe_mapped = universe_map(universe); + let placeholder_mapped = ty::Placeholder { + universe: universe_mapped, + name, + }; + self.tcx + .mk_region(ty::RePlaceholder(placeholder_mapped)) + .into() + } } } } diff --git a/src/librustc/infer/canonical/query_response.rs b/src/librustc/infer/canonical/query_response.rs index 38788186eb0..b3ce5eb7e56 100644 --- a/src/librustc/infer/canonical/query_response.rs +++ b/src/librustc/infer/canonical/query_response.rs @@ -394,6 +394,21 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { original_values, query_response, ); + // For each new universe created in the query result that did + // not appear in the original query, create a local + // superuniverse. + let mut universe_map = original_values.universe_map.clone(); + let num_universes_in_query = original_values.universe_map.len(); + let num_universes_in_response = query_response.max_universe.as_usize() + 1; + for _ in num_universes_in_query..num_universes_in_response { + universe_map.push(self.create_next_universe()); + } + assert!(universe_map.len() >= 1); // always have the root universe + assert_eq!( + universe_map[ty::UniverseIndex::ROOT.as_usize()], + ty::UniverseIndex::ROOT + ); + // Every canonical query result includes values for each of // the inputs to the query. Therefore, we begin by unifying // these values with the original inputs that were @@ -440,9 +455,20 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { .variables .iter() .enumerate() - .map(|(index, info)| opt_values[BoundTyIndex::new(index)].unwrap_or_else(|| - self.fresh_inference_var_for_canonical_var(cause.span, *info) - )) + .map(|(index, info)| { + if info.is_existential() { + match opt_values[BoundTyIndex::new(index)] { + Some(k) => k, + None => self.instantiate_canonical_var(cause.span, *info, |u| { + universe_map[u.as_usize()] + }), + } + } else { + self.instantiate_canonical_var(cause.span, *info, |u| { + universe_map[u.as_usize()] + }) + } + }) .collect(), }; diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs index 48ba69fee1c..4e214394399 100644 --- a/src/librustc/ty/mod.rs +++ b/src/librustc/ty/mod.rs @@ -1540,6 +1540,8 @@ pub struct Placeholder { pub name: BoundRegion, } +impl_stable_hash_for!(struct Placeholder { universe, name }); + /// When type checking, we use the `ParamEnv` to track /// details about the set of where-clauses that are in scope at this /// particular point. |