diff options
50 files changed, 3139 insertions, 1767 deletions
diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs index 3a152ccd0c9..33322993b1d 100644 --- a/src/librustc/dep_graph/dep_node.rs +++ b/src/librustc/dep_graph/dep_node.rs @@ -70,9 +70,12 @@ use rustc_data_structures::stable_hasher::{StableHasher, HashStable}; use std::fmt; use std::hash::Hash; use syntax_pos::symbol::InternedString; -use traits::query::{CanonicalProjectionGoal, - CanonicalTyGoal, CanonicalPredicateGoal}; -use ty::{TyCtxt, Instance, InstanceDef, ParamEnv, ParamEnvAnd, PolyTraitRef, Ty}; +use traits::query::{ + CanonicalProjectionGoal, CanonicalTyGoal, CanonicalTypeOpEqGoal, CanonicalTypeOpSubtypeGoal, + CanonicalPredicateGoal, CanonicalTypeOpProvePredicateGoal, CanonicalTypeOpNormalizeGoal, +}; +use ty::{TyCtxt, FnSig, Instance, InstanceDef, + ParamEnv, ParamEnvAnd, Predicate, PolyFnSig, PolyTraitRef, Ty}; use ty::subst::Substs; // erase!() just makes tokens go away. It's used to specify which macro argument @@ -647,6 +650,13 @@ define_dep_nodes!( <'tcx> [] NormalizeTyAfterErasingRegions(ParamEnvAnd<'tcx, Ty<'tcx>>), [] DropckOutlives(CanonicalTyGoal<'tcx>), [] EvaluateObligation(CanonicalPredicateGoal<'tcx>), + [] TypeOpEq(CanonicalTypeOpEqGoal<'tcx>), + [] TypeOpSubtype(CanonicalTypeOpSubtypeGoal<'tcx>), + [] TypeOpProvePredicate(CanonicalTypeOpProvePredicateGoal<'tcx>), + [] TypeOpNormalizeTy(CanonicalTypeOpNormalizeGoal<'tcx, Ty<'tcx>>), + [] TypeOpNormalizePredicate(CanonicalTypeOpNormalizeGoal<'tcx, Predicate<'tcx>>), + [] TypeOpNormalizePolyFnSig(CanonicalTypeOpNormalizeGoal<'tcx, PolyFnSig<'tcx>>), + [] TypeOpNormalizeFnSig(CanonicalTypeOpNormalizeGoal<'tcx, FnSig<'tcx>>), [] SubstituteNormalizeAndTestPredicates { key: (DefId, &'tcx Substs<'tcx>) }, diff --git a/src/librustc/infer/canonical.rs b/src/librustc/infer/canonical.rs deleted file mode 100644 index ef11cc0f493..00000000000 --- a/src/librustc/infer/canonical.rs +++ /dev/null @@ -1,925 +0,0 @@ -// Copyright 2014 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -//! **Canonicalization** is the key to constructing a query in the -//! middle of type inference. Ordinarily, it is not possible to store -//! types from type inference in query keys, because they contain -//! references to inference variables whose lifetimes are too short -//! and so forth. Canonicalizing a value T1 using `canonicalize_query` -//! produces two things: -//! -//! - a value T2 where each unbound inference variable has been -//! replaced with a **canonical variable**; -//! - a map M (of type `CanonicalVarValues`) from those canonical -//! variables back to the original. -//! -//! We can then do queries using T2. These will give back constriants -//! on the canonical variables which can be translated, using the map -//! M, into constraints in our source context. This process of -//! translating the results back is done by the -//! `instantiate_query_result` method. -//! -//! For a more detailed look at what is happening here, check -//! out the [chapter in the rustc guide][c]. -//! -//! [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html - -use infer::{InferCtxt, InferOk, InferResult, RegionVariableOrigin, TypeVariableOrigin}; -use rustc_data_structures::indexed_vec::Idx; -use serialize::UseSpecializedDecodable; -use std::fmt::Debug; -use std::ops::Index; -use std::sync::atomic::Ordering; -use syntax::codemap::Span; -use traits::{Obligation, ObligationCause, PredicateObligation}; -use ty::{self, CanonicalVar, Lift, Region, Slice, Ty, TyCtxt, TypeFlags}; -use ty::subst::{Kind, UnpackedKind}; -use ty::fold::{TypeFoldable, TypeFolder}; - -use rustc_data_structures::indexed_vec::IndexVec; -use rustc_data_structures::fx::FxHashMap; - -/// A "canonicalized" type `V` is one where all free inference -/// variables have been rewriten to "canonical vars". These are -/// numbered starting from 0 in order of first appearance. -#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)] -pub struct Canonical<'gcx, V> { - pub variables: CanonicalVarInfos<'gcx>, - pub value: V, -} - -pub type CanonicalVarInfos<'gcx> = &'gcx Slice<CanonicalVarInfo>; - -impl<'gcx> UseSpecializedDecodable for CanonicalVarInfos<'gcx> { } - -/// A set of values corresponding to the canonical variables from some -/// `Canonical`. You can give these values to -/// `canonical_value.substitute` to substitute them into the canonical -/// value at the right places. -/// -/// When you canonicalize a value `V`, you get back one of these -/// vectors with the original values that were replaced by canonical -/// variables. -/// -/// You can also use `infcx.fresh_inference_vars_for_canonical_vars` -/// to get back a `CanonicalVarValues` containing fresh inference -/// variables. -#[derive(Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)] -pub struct CanonicalVarValues<'tcx> { - pub var_values: IndexVec<CanonicalVar, Kind<'tcx>>, -} - -/// 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, -/// with fresh inference variables replacing the canonical values. -#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)] -pub struct CanonicalVarInfo { - pub kind: CanonicalVarKind, -} - -/// Describes the "kind" of the canonical variable. This is a "kind" -/// in the type-theory sense of the term -- i.e., a "meta" type system -/// that analyzes type-like values. -#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)] -pub enum CanonicalVarKind { - /// Some kind of type inference variable. - Ty(CanonicalTyVarKind), - - /// Region variable `'?R`. - Region, -} - -/// Rust actually has more than one category of type variables; -/// notably, the type variables we create for literals (e.g., 22 or -/// 22.) can only be instantiated with integral/float types (e.g., -/// usize or f32). In order to faithfully reproduce a type, we need to -/// know what set of types a given type variable can be unified with. -#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)] -pub enum CanonicalTyVarKind { - /// General type variable `?T` that can be unified with arbitrary types. - General, - - /// Integral type variable `?I` (that can only be unified with integral types). - Int, - - /// Floating-point type variable `?F` (that can only be unified with float types). - Float, -} - -/// After we execute a query with a canonicalized key, we get back a -/// `Canonical<QueryResult<..>>`. You can use -/// `instantiate_query_result` to access the data in this result. -#[derive(Clone, Debug)] -pub struct QueryResult<'tcx, R> { - pub var_values: CanonicalVarValues<'tcx>, - pub region_constraints: Vec<QueryRegionConstraint<'tcx>>, - pub certainty: Certainty, - pub value: R, -} - -/// Indicates whether or not we were able to prove the query to be -/// true. -#[derive(Copy, Clone, Debug)] -pub enum Certainty { - /// The query is known to be true, presuming that you apply the - /// given `var_values` and the region-constraints are satisfied. - Proven, - - /// The query is not known to be true, but also not known to be - /// false. The `var_values` represent *either* values that must - /// hold in order for the query to be true, or helpful tips that - /// *might* make it true. Currently rustc's trait solver cannot - /// distinguish the two (e.g., due to our preference for where - /// clauses over impls). - /// - /// After some unifiations and things have been done, it makes - /// sense to try and prove again -- of course, at that point, the - /// canonical form will be different, making this a distinct - /// query. - Ambiguous, -} - -impl Certainty { - pub fn is_proven(&self) -> bool { - match self { - Certainty::Proven => true, - Certainty::Ambiguous => false, - } - } - - pub fn is_ambiguous(&self) -> bool { - !self.is_proven() - } -} - -impl<'tcx, R> QueryResult<'tcx, R> { - pub fn is_proven(&self) -> bool { - self.certainty.is_proven() - } - - pub fn is_ambiguous(&self) -> bool { - !self.is_proven() - } -} - -impl<'tcx, R> Canonical<'tcx, QueryResult<'tcx, R>> { - pub fn is_proven(&self) -> bool { - self.value.is_proven() - } - - pub fn is_ambiguous(&self) -> bool { - !self.is_proven() - } -} - -pub type QueryRegionConstraint<'tcx> = ty::Binder<ty::OutlivesPredicate<Kind<'tcx>, Region<'tcx>>>; - -/// Trait implemented by values that can be canonicalized. It mainly -/// serves to identify the interning table we will use. -pub trait Canonicalize<'gcx: 'tcx, 'tcx>: TypeFoldable<'tcx> + Lift<'gcx> { - type Canonicalized: 'gcx + Debug; - - /// After a value has been fully canonicalized and lifted, this - /// method will allocate it in a global arena. - fn intern( - gcx: TyCtxt<'_, 'gcx, 'gcx>, - value: Canonical<'gcx, Self::Lifted>, - ) -> Self::Canonicalized; -} - -impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { - /// Creates a substitution S for the canonical value with fresh - /// inference variables and applies it to the canonical value. - /// Returns both the instantiated result *and* the substitution S. - /// - /// This is useful at the start of a query: it basically brings - /// the canonical value "into scope" within your new infcx. At the - /// end of processing, the substitution S (once canonicalized) - /// then represents the values that you computed for each of the - /// canonical inputs to your query. - pub fn instantiate_canonical_with_fresh_inference_vars<T>( - &self, - span: Span, - canonical: &Canonical<'tcx, T>, - ) -> (T, CanonicalVarValues<'tcx>) - where - T: TypeFoldable<'tcx>, - { - let canonical_inference_vars = - self.fresh_inference_vars_for_canonical_vars(span, canonical.variables); - 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. - pub fn fresh_inference_vars_for_canonical_vars( - &self, - span: Span, - variables: &Slice<CanonicalVarInfo>, - ) -> CanonicalVarValues<'tcx> { - let var_values: IndexVec<CanonicalVar, Kind<'tcx>> = variables - .iter() - .map(|info| self.fresh_inference_var_for_canonical_var(span, *info)) - .collect(); - - CanonicalVarValues { var_values } - } - - /// Given the "info" about a canonical variable, creates a fresh - /// inference variable with the same characteristics. - pub fn fresh_inference_var_for_canonical_var( - &self, - span: Span, - cv_info: CanonicalVarInfo, - ) -> Kind<'tcx> { - match cv_info.kind { - CanonicalVarKind::Ty(ty_kind) => { - let ty = match ty_kind { - CanonicalTyVarKind::General => { - self.next_ty_var( - TypeVariableOrigin::MiscVariable(span), - ) - } - - CanonicalTyVarKind::Int => self.tcx.mk_int_var(self.next_int_var_id()), - - CanonicalTyVarKind::Float => self.tcx.mk_float_var(self.next_float_var_id()), - }; - ty.into() - } - - CanonicalVarKind::Region => { - self.next_region_var(RegionVariableOrigin::MiscVariable(span)).into() - } - } - } - - /// Given the (canonicalized) result to a canonical query, - /// instantiates the result so it can be used, plugging in the - /// values from the canonical query. (Note that the result may - /// have been ambiguous; you should check the certainty level of - /// the query before applying this function.) - /// - /// To get a good understanding of what is happening here, check - /// out the [chapter in the rustc guide][c]. - /// - /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#processing-the-canonicalized-query-result - pub fn instantiate_query_result<R>( - &self, - cause: &ObligationCause<'tcx>, - param_env: ty::ParamEnv<'tcx>, - original_values: &CanonicalVarValues<'tcx>, - query_result: &Canonical<'tcx, QueryResult<'tcx, R>>, - ) -> InferResult<'tcx, R> - where - R: Debug + TypeFoldable<'tcx>, - { - debug!( - "instantiate_query_result(original_values={:#?}, query_result={:#?})", - original_values, query_result, - ); - - // 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 - // canonicalized. - let result_values = &query_result.value.var_values; - assert_eq!(original_values.len(), result_values.len()); - - // Quickly try to find initial values for the canonical - // variables in the result in terms of the query. We do this - // by iterating down the values that the query gave to each of - // the canonical inputs. If we find that one of those values - // is directly equal to one of the canonical variables in the - // result, then we can type the corresponding value from the - // input. See the example above. - let mut opt_values: IndexVec<CanonicalVar, Option<Kind<'tcx>>> = - IndexVec::from_elem_n(None, query_result.variables.len()); - - // In terms of our example above, we are iterating over pairs like: - // [(?A, Vec<?0>), ('static, '?1), (?B, ?0)] - for (original_value, result_value) in original_values.iter().zip(result_values) { - match result_value.unpack() { - UnpackedKind::Type(result_value) => { - // e.g., here `result_value` might be `?0` in the example above... - if let ty::TyInfer(ty::InferTy::CanonicalTy(index)) = result_value.sty { - // in which case we would set `canonical_vars[0]` to `Some(?U)`. - opt_values[index] = Some(original_value); - } - } - UnpackedKind::Lifetime(result_value) => { - // e.g., here `result_value` might be `'?1` in the example above... - if let &ty::RegionKind::ReCanonical(index) = result_value { - // in which case we would set `canonical_vars[0]` to `Some('static)`. - opt_values[index] = Some(original_value); - } - } - } - } - - // Create a result substitution: if we found a value for a - // given variable in the loop above, use that. Otherwise, use - // a fresh inference variable. - let result_subst = &CanonicalVarValues { - var_values: query_result - .variables - .iter() - .enumerate() - .map(|(index, info)| match opt_values[CanonicalVar::new(index)] { - Some(k) => k, - None => self.fresh_inference_var_for_canonical_var(cause.span, *info), - }) - .collect(), - }; - - // Unify the original values for the canonical variables in - // the input with the value found in the query - // post-substitution. Often, but not always, this is a no-op, - // because we already found the mapping in the first step. - let substituted_values = |index: CanonicalVar| -> Kind<'tcx> { - query_result.substitute_projected(self.tcx, result_subst, |v| &v.var_values[index]) - }; - let mut obligations = - self.unify_canonical_vars(cause, param_env, original_values, substituted_values)? - .into_obligations(); - - obligations.extend(self.query_region_constraints_into_obligations( - cause, - param_env, - &query_result.value.region_constraints, - result_subst, - )); - - let user_result: R = - query_result.substitute_projected(self.tcx, result_subst, |q_r| &q_r.value); - - Ok(InferOk { - value: user_result, - obligations, - }) - } - - /// Converts the region constraints resulting from a query into an - /// iterator of obligations. - fn query_region_constraints_into_obligations<'a>( - &'a self, - cause: &'a ObligationCause<'tcx>, - param_env: ty::ParamEnv<'tcx>, - unsubstituted_region_constraints: &'a [QueryRegionConstraint<'tcx>], - result_subst: &'a CanonicalVarValues<'tcx>, - ) -> impl Iterator<Item = PredicateObligation<'tcx>> + 'a { - Box::new(unsubstituted_region_constraints.iter().map(move |constraint| { - let ty::OutlivesPredicate(k1, r2) = constraint.skip_binder(); // restored below - let k1 = substitute_value(self.tcx, result_subst, k1); - let r2 = substitute_value(self.tcx, result_subst, r2); - match k1.unpack() { - UnpackedKind::Lifetime(r1) => - Obligation::new( - cause.clone(), - param_env, - ty::Predicate::RegionOutlives( - ty::Binder::dummy(ty::OutlivesPredicate(r1, r2))), - ), - - UnpackedKind::Type(t1) => - Obligation::new( - cause.clone(), - param_env, - ty::Predicate::TypeOutlives( - ty::Binder::dummy(ty::OutlivesPredicate(t1, r2))), - ), - } - })) as Box<dyn Iterator<Item = _>> - } - - /// Given two sets of values for the same set of canonical variables, unify them. - /// The second set is produced lazilly by supplying indices from the first set. - fn unify_canonical_vars( - &self, - cause: &ObligationCause<'tcx>, - param_env: ty::ParamEnv<'tcx>, - variables1: &CanonicalVarValues<'tcx>, - variables2: impl Fn(CanonicalVar) -> Kind<'tcx>, - ) -> InferResult<'tcx, ()> { - self.commit_if_ok(|_| { - let mut obligations = vec![]; - for (index, value1) in variables1.var_values.iter_enumerated() { - let value2 = variables2(index); - - match (value1.unpack(), value2.unpack()) { - (UnpackedKind::Type(v1), UnpackedKind::Type(v2)) => { - obligations - .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations()); - } - ( - UnpackedKind::Lifetime(ty::ReErased), - UnpackedKind::Lifetime(ty::ReErased), - ) => { - // no action needed - } - (UnpackedKind::Lifetime(v1), UnpackedKind::Lifetime(v2)) => { - obligations - .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations()); - } - _ => { - bug!("kind mismatch, cannot unify {:?} and {:?}", value1, value2,); - } - } - } - Ok(InferOk { - value: (), - obligations, - }) - }) - } - - /// Canonicalizes a query value `V`. When we canonicalize a query, - /// we not only canonicalize unbound inference variables, but we - /// *also* replace all free regions whatsoever. So for example a - /// query like `T: Trait<'static>` would be canonicalized to - /// - /// ```text - /// T: Trait<'?0> - /// ``` - /// - /// with a mapping M that maps `'?0` to `'static`. - /// - /// To get a good understanding of what is happening here, check - /// out the [chapter in the rustc guide][c]. - /// - /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#canonicalizing-the-query - pub fn canonicalize_query<V>(&self, value: &V) -> (V::Canonicalized, CanonicalVarValues<'tcx>) - where - V: Canonicalize<'gcx, 'tcx>, - { - self.tcx.sess.perf_stats.queries_canonicalized.fetch_add(1, Ordering::Relaxed); - - Canonicalizer::canonicalize( - value, - Some(self), - self.tcx, - CanonicalizeAllFreeRegions(true), - ) - } - - /// Canonicalizes a query *response* `V`. When we canonicalize a - /// query response, we only canonicalize unbound inference - /// variables, and we leave other free regions alone. So, - /// continuing with the example from `canonicalize_query`, if - /// there was an input query `T: Trait<'static>`, it would have - /// been canonicalized to - /// - /// ```text - /// T: Trait<'?0> - /// ``` - /// - /// with a mapping M that maps `'?0` to `'static`. But if we found that there - /// exists only one possible impl of `Trait`, and it looks like - /// - /// impl<T> Trait<'static> for T { .. } - /// - /// then we would prepare a query result R that (among other - /// things) includes a mapping to `'?0 := 'static`. When - /// canonicalizing this query result R, we would leave this - /// reference to `'static` alone. - /// - /// To get a good understanding of what is happening here, check - /// out the [chapter in the rustc guide][c]. - /// - /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#canonicalizing-the-query-result - pub fn canonicalize_response<V>( - &self, - value: &V, - ) -> (V::Canonicalized, CanonicalVarValues<'tcx>) - where - V: Canonicalize<'gcx, 'tcx>, - { - Canonicalizer::canonicalize( - value, - Some(self), - self.tcx, - CanonicalizeAllFreeRegions(false), - ) - } -} - -/// If this flag is true, then all free regions will be replaced with -/// a canonical var. This is used to make queries as generic as -/// possible. For example, the query `F: Foo<'static>` would be -/// canonicalized to `F: Foo<'0>`. -struct CanonicalizeAllFreeRegions(bool); - -struct Canonicalizer<'cx, 'gcx: 'tcx, 'tcx: 'cx> { - infcx: Option<&'cx InferCtxt<'cx, 'gcx, 'tcx>>, - tcx: TyCtxt<'cx, 'gcx, 'tcx>, - variables: IndexVec<CanonicalVar, CanonicalVarInfo>, - indices: FxHashMap<Kind<'tcx>, CanonicalVar>, - var_values: IndexVec<CanonicalVar, Kind<'tcx>>, - canonicalize_all_free_regions: CanonicalizeAllFreeRegions, - needs_canonical_flags: TypeFlags, -} - -impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for Canonicalizer<'cx, 'gcx, 'tcx> { - fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { - self.tcx - } - - fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { - match *r { - ty::ReLateBound(..) => { - // leave bound regions alone - r - } - - ty::ReVar(vid) => { - let r = self.infcx - .unwrap() - .borrow_region_constraints() - .opportunistic_resolve_var(self.tcx, vid); - let info = CanonicalVarInfo { - kind: CanonicalVarKind::Region, - }; - debug!( - "canonical: region var found with vid {:?}, \ - opportunistically resolved to {:?}", - vid, r - ); - let cvar = self.canonical_var(info, r.into()); - self.tcx().mk_region(ty::ReCanonical(cvar)) - } - - ty::ReStatic - | ty::ReEarlyBound(..) - | ty::ReFree(_) - | ty::ReScope(_) - | ty::ReSkolemized(..) - | ty::ReEmpty - | ty::ReErased => { - if self.canonicalize_all_free_regions.0 { - let info = CanonicalVarInfo { - kind: CanonicalVarKind::Region, - }; - let cvar = self.canonical_var(info, r.into()); - self.tcx().mk_region(ty::ReCanonical(cvar)) - } else { - r - } - } - - ty::ReClosureBound(..) | ty::ReCanonical(_) => { - bug!("canonical region encountered during canonicalization") - } - } - } - - fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { - match t.sty { - ty::TyInfer(ty::TyVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::General, t), - - ty::TyInfer(ty::IntVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Int, t), - - ty::TyInfer(ty::FloatVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Float, t), - - ty::TyInfer(ty::FreshTy(_)) - | ty::TyInfer(ty::FreshIntTy(_)) - | ty::TyInfer(ty::FreshFloatTy(_)) => { - bug!("encountered a fresh type during canonicalization") - } - - ty::TyInfer(ty::CanonicalTy(_)) => { - bug!("encountered a canonical type during canonicalization") - } - - ty::TyClosure(..) - | ty::TyGenerator(..) - | ty::TyGeneratorWitness(..) - | ty::TyBool - | ty::TyChar - | ty::TyInt(..) - | ty::TyUint(..) - | ty::TyFloat(..) - | ty::TyAdt(..) - | ty::TyStr - | ty::TyError - | ty::TyArray(..) - | ty::TySlice(..) - | ty::TyRawPtr(..) - | ty::TyRef(..) - | ty::TyFnDef(..) - | ty::TyFnPtr(_) - | ty::TyDynamic(..) - | ty::TyNever - | ty::TyTuple(..) - | ty::TyProjection(..) - | ty::TyForeign(..) - | ty::TyParam(..) - | ty::TyAnon(..) => { - if t.flags.intersects(self.needs_canonical_flags) { - t.super_fold_with(self) - } else { - t - } - } - } - } -} - -impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> { - /// The main `canonicalize` method, shared impl of - /// `canonicalize_query` and `canonicalize_response`. - fn canonicalize<V>( - value: &V, - infcx: Option<&'cx InferCtxt<'cx, 'gcx, 'tcx>>, - tcx: TyCtxt<'cx, 'gcx, 'tcx>, - canonicalize_all_free_regions: CanonicalizeAllFreeRegions, - ) -> (V::Canonicalized, CanonicalVarValues<'tcx>) - where - V: Canonicalize<'gcx, 'tcx>, - { - debug_assert!( - !value.has_type_flags(TypeFlags::HAS_CANONICAL_VARS), - "canonicalizing a canonical value: {:?}", - value, - ); - - let needs_canonical_flags = if canonicalize_all_free_regions.0 { - TypeFlags::HAS_FREE_REGIONS | TypeFlags::KEEP_IN_LOCAL_TCX - } else { - TypeFlags::KEEP_IN_LOCAL_TCX - }; - - let gcx = tcx.global_tcx(); - - // Fast path: nothing that needs to be canonicalized. - if !value.has_type_flags(needs_canonical_flags) { - let out_value = gcx.lift(value).unwrap(); - let canon_value = V::intern( - gcx, - Canonical { - variables: Slice::empty(), - value: out_value, - }, - ); - let values = CanonicalVarValues { - var_values: IndexVec::default(), - }; - return (canon_value, values); - } - - let mut canonicalizer = Canonicalizer { - infcx, - tcx, - canonicalize_all_free_regions, - needs_canonical_flags, - variables: IndexVec::default(), - indices: FxHashMap::default(), - var_values: IndexVec::default(), - }; - let out_value = value.fold_with(&mut canonicalizer); - - // Once we have canonicalized `out_value`, it should not - // contain anything that ties it to this inference context - // anymore, so it should live in the global arena. - let out_value = gcx.lift(&out_value).unwrap_or_else(|| { - bug!( - "failed to lift `{:?}`, canonicalized from `{:?}`", - out_value, - value - ) - }); - - let canonical_variables = tcx.intern_canonical_var_infos(&canonicalizer.variables.raw); - - let canonical_value = V::intern( - gcx, - Canonical { - variables: canonical_variables, - value: out_value, - }, - ); - let canonical_var_values = CanonicalVarValues { - var_values: canonicalizer.var_values, - }; - (canonical_value, canonical_var_values) - } - - /// Creates a canonical variable replacing `kind` from the input, - /// or returns an existing variable if `kind` has already been - /// seen. `kind` is expected to be an unbound variable (or - /// potentially a free region). - fn canonical_var(&mut self, info: CanonicalVarInfo, kind: Kind<'tcx>) -> CanonicalVar { - let Canonicalizer { - indices, - variables, - var_values, - .. - } = self; - - indices - .entry(kind) - .or_insert_with(|| { - let cvar1 = variables.push(info); - let cvar2 = var_values.push(kind); - assert_eq!(cvar1, cvar2); - cvar1 - }) - .clone() - } - - /// Given a type variable `ty_var` of the given kind, first check - /// if `ty_var` is bound to anything; if so, canonicalize - /// *that*. Otherwise, create a new canonical variable for - /// `ty_var`. - fn canonicalize_ty_var(&mut self, ty_kind: CanonicalTyVarKind, ty_var: Ty<'tcx>) -> Ty<'tcx> { - let infcx = self.infcx.expect("encountered ty-var without infcx"); - let bound_to = infcx.shallow_resolve(ty_var); - if bound_to != ty_var { - self.fold_ty(bound_to) - } else { - let info = CanonicalVarInfo { - kind: CanonicalVarKind::Ty(ty_kind), - }; - let cvar = self.canonical_var(info, ty_var.into()); - self.tcx().mk_infer(ty::InferTy::CanonicalTy(cvar)) - } - } -} - -impl<'tcx, V> Canonical<'tcx, V> { - /// Instantiate the wrapped value, replacing each canonical value - /// with the value given in `var_values`. - fn substitute(&self, tcx: TyCtxt<'_, '_, 'tcx>, var_values: &CanonicalVarValues<'tcx>) -> V - where - V: TypeFoldable<'tcx>, - { - self.substitute_projected(tcx, var_values, |value| value) - } - - /// Invoke `projection_fn` with `self.value` to get a value V that - /// is expressed in terms of the same canonical variables bound in - /// `self`. Apply the substitution `var_values` to this value V, - /// replacing each of the canonical variables. - fn substitute_projected<T>( - &self, - tcx: TyCtxt<'_, '_, 'tcx>, - var_values: &CanonicalVarValues<'tcx>, - projection_fn: impl FnOnce(&V) -> &T, - ) -> T - where - T: TypeFoldable<'tcx>, - { - assert_eq!(self.variables.len(), var_values.var_values.len()); - let value = projection_fn(&self.value); - substitute_value(tcx, var_values, value) - } -} - -/// Substitute the values from `var_values` into `value`. `var_values` -/// must be values for the set of cnaonical variables that appear in -/// `value`. -fn substitute_value<'a, 'tcx, T>( - tcx: TyCtxt<'_, '_, 'tcx>, - var_values: &CanonicalVarValues<'tcx>, - value: &'a T, -) -> T -where - T: TypeFoldable<'tcx>, -{ - if var_values.var_values.is_empty() { - debug_assert!(!value.has_type_flags(TypeFlags::HAS_CANONICAL_VARS)); - value.clone() - } else if !value.has_type_flags(TypeFlags::HAS_CANONICAL_VARS) { - value.clone() - } else { - value.fold_with(&mut CanonicalVarValuesSubst { tcx, var_values }) - } -} - -struct CanonicalVarValuesSubst<'cx, 'gcx: 'tcx, 'tcx: 'cx> { - tcx: TyCtxt<'cx, 'gcx, 'tcx>, - var_values: &'cx CanonicalVarValues<'tcx>, -} - -impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for CanonicalVarValuesSubst<'cx, 'gcx, 'tcx> { - fn tcx(&self) -> TyCtxt<'_, 'gcx, 'tcx> { - self.tcx - } - - fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { - match t.sty { - ty::TyInfer(ty::InferTy::CanonicalTy(c)) => { - match self.var_values.var_values[c].unpack() { - UnpackedKind::Type(ty) => ty, - r => bug!("{:?} is a type but value is {:?}", c, r), - } - } - _ => { - if !t.has_type_flags(TypeFlags::HAS_CANONICAL_VARS) { - t - } else { - t.super_fold_with(self) - } - } - } - } - - fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { - match r { - ty::RegionKind::ReCanonical(c) => match self.var_values.var_values[*c].unpack() { - UnpackedKind::Lifetime(l) => l, - r => bug!("{:?} is a region but value is {:?}", c, r), - }, - _ => r.super_fold_with(self), - } - } -} - -CloneTypeFoldableAndLiftImpls! { - ::infer::canonical::Certainty, - ::infer::canonical::CanonicalVarInfo, - ::infer::canonical::CanonicalVarKind, -} - -CloneTypeFoldableImpls! { - for <'tcx> { - ::infer::canonical::CanonicalVarInfos<'tcx>, - } -} - -BraceStructTypeFoldableImpl! { - impl<'tcx, C> TypeFoldable<'tcx> for Canonical<'tcx, C> { - variables, - value, - } where C: TypeFoldable<'tcx> -} - -BraceStructLiftImpl! { - impl<'a, 'tcx, T> Lift<'tcx> for Canonical<'a, T> { - type Lifted = Canonical<'tcx, T::Lifted>; - variables, value - } where T: Lift<'tcx> -} - -impl<'tcx> CanonicalVarValues<'tcx> { - fn iter<'a>(&'a self) -> impl Iterator<Item = Kind<'tcx>> + 'a { - self.var_values.iter().cloned() - } - - fn len(&self) -> usize { - self.var_values.len() - } -} - -impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> { - type Item = Kind<'tcx>; - type IntoIter = ::std::iter::Cloned<::std::slice::Iter<'a, Kind<'tcx>>>; - - fn into_iter(self) -> Self::IntoIter { - self.var_values.iter().cloned() - } -} - -BraceStructLiftImpl! { - impl<'a, 'tcx> Lift<'tcx> for CanonicalVarValues<'a> { - type Lifted = CanonicalVarValues<'tcx>; - var_values, - } -} - -BraceStructTypeFoldableImpl! { - impl<'tcx> TypeFoldable<'tcx> for CanonicalVarValues<'tcx> { - var_values, - } -} - -BraceStructTypeFoldableImpl! { - impl<'tcx, R> TypeFoldable<'tcx> for QueryResult<'tcx, R> { - var_values, region_constraints, certainty, value - } where R: TypeFoldable<'tcx>, -} - -BraceStructLiftImpl! { - impl<'a, 'tcx, R> Lift<'tcx> for QueryResult<'a, R> { - type Lifted = QueryResult<'tcx, R::Lifted>; - var_values, region_constraints, certainty, value - } where R: Lift<'tcx> -} - -impl<'tcx> Index<CanonicalVar> for CanonicalVarValues<'tcx> { - type Output = Kind<'tcx>; - - fn index(&self, value: CanonicalVar) -> &Kind<'tcx> { - &self.var_values[value] - } -} diff --git a/src/librustc/infer/canonical/canonicalizer.rs b/src/librustc/infer/canonical/canonicalizer.rs new file mode 100644 index 00000000000..8b67f04e020 --- /dev/null +++ b/src/librustc/infer/canonical/canonicalizer.rs @@ -0,0 +1,403 @@ +// Copyright 2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! This module contains the "canonicalizer" itself. +//! +//! For an overview of what canonicaliation is and how it fits into +//! rustc, check out the [chapter in the rustc guide][c]. +//! +//! [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html + +use infer::canonical::{ + Canonical, CanonicalTyVarKind, CanonicalVarInfo, CanonicalVarKind, CanonicalVarValues, + Canonicalized, +}; +use infer::InferCtxt; +use std::sync::atomic::Ordering; +use ty::fold::{TypeFoldable, TypeFolder}; +use ty::subst::Kind; +use ty::{self, CanonicalVar, Lift, Slice, Ty, TyCtxt, TypeFlags}; + +use rustc_data_structures::fx::FxHashMap; +use rustc_data_structures::indexed_vec::IndexVec; + +impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { + /// Canonicalizes a query value `V`. When we canonicalize a query, + /// we not only canonicalize unbound inference variables, but we + /// *also* replace all free regions whatsoever. So for example a + /// query like `T: Trait<'static>` would be canonicalized to + /// + /// ```text + /// T: Trait<'?0> + /// ``` + /// + /// with a mapping M that maps `'?0` to `'static`. + /// + /// To get a good understanding of what is happening here, check + /// out the [chapter in the rustc guide][c]. + /// + /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#canonicalizing-the-query + pub fn canonicalize_query<V>( + &self, + value: &V, + ) -> (Canonicalized<'gcx, V>, CanonicalVarValues<'tcx>) + where + V: TypeFoldable<'tcx> + Lift<'gcx>, + { + self.tcx + .sess + .perf_stats + .queries_canonicalized + .fetch_add(1, Ordering::Relaxed); + + Canonicalizer::canonicalize( + value, + Some(self), + self.tcx, + CanonicalizeRegionMode { + static_region: true, + other_free_regions: true, + }, + ) + } + + /// Canonicalizes a query *response* `V`. When we canonicalize a + /// query response, we only canonicalize unbound inference + /// variables, and we leave other free regions alone. So, + /// continuing with the example from `canonicalize_query`, if + /// there was an input query `T: Trait<'static>`, it would have + /// been canonicalized to + /// + /// ```text + /// T: Trait<'?0> + /// ``` + /// + /// with a mapping M that maps `'?0` to `'static`. But if we found that there + /// exists only one possible impl of `Trait`, and it looks like + /// + /// impl<T> Trait<'static> for T { .. } + /// + /// then we would prepare a query result R that (among other + /// things) includes a mapping to `'?0 := 'static`. When + /// canonicalizing this query result R, we would leave this + /// reference to `'static` alone. + /// + /// To get a good understanding of what is happening here, check + /// out the [chapter in the rustc guide][c]. + /// + /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#canonicalizing-the-query-result + pub fn canonicalize_response<V>( + &self, + value: &V, + ) -> (Canonicalized<'gcx, V>, CanonicalVarValues<'tcx>) + where + V: TypeFoldable<'tcx> + Lift<'gcx>, + { + Canonicalizer::canonicalize( + value, + Some(self), + self.tcx, + CanonicalizeRegionMode { + static_region: false, + other_free_regions: false, + }, + ) + } + + /// A hacky variant of `canonicalize_query` that does not + /// canonicalize `'static`. Unfortunately, the existing leak + /// check treaks `'static` differently in some cases (see also + /// #33684), so if we are performing an operation that may need to + /// prove "leak-check" related things, we leave `'static` + /// alone. + /// + /// FIXME(#48536) -- once we have universes, we can remove this and just use + /// `canonicalize_query`. + pub fn canonicalize_hr_query_hack<V>( + &self, + value: &V, + ) -> (Canonicalized<'gcx, V>, CanonicalVarValues<'tcx>) + where + V: TypeFoldable<'tcx> + Lift<'gcx>, + { + self.tcx + .sess + .perf_stats + .queries_canonicalized + .fetch_add(1, Ordering::Relaxed); + + Canonicalizer::canonicalize( + value, + Some(self), + self.tcx, + CanonicalizeRegionMode { + static_region: false, + other_free_regions: true, + }, + ) + } +} + +/// If this flag is true, then all free regions will be replaced with +/// a canonical var. This is used to make queries as generic as +/// possible. For example, the query `F: Foo<'static>` would be +/// canonicalized to `F: Foo<'0>`. +struct CanonicalizeRegionMode { + static_region: bool, + other_free_regions: bool, +} + +impl CanonicalizeRegionMode { + fn any(&self) -> bool { + self.static_region || self.other_free_regions + } +} + +struct Canonicalizer<'cx, 'gcx: 'tcx, 'tcx: 'cx> { + infcx: Option<&'cx InferCtxt<'cx, 'gcx, 'tcx>>, + tcx: TyCtxt<'cx, 'gcx, 'tcx>, + variables: IndexVec<CanonicalVar, CanonicalVarInfo>, + indices: FxHashMap<Kind<'tcx>, CanonicalVar>, + var_values: IndexVec<CanonicalVar, Kind<'tcx>>, + canonicalize_region_mode: CanonicalizeRegionMode, + needs_canonical_flags: TypeFlags, +} + +impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for Canonicalizer<'cx, 'gcx, 'tcx> { + fn tcx<'b>(&'b self) -> TyCtxt<'b, 'gcx, 'tcx> { + self.tcx + } + + fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { + match *r { + ty::ReLateBound(..) => { + // leave bound regions alone + r + } + + ty::ReVar(vid) => { + let r = self + .infcx + .unwrap() + .borrow_region_constraints() + .opportunistic_resolve_var(self.tcx, vid); + let info = CanonicalVarInfo { + kind: CanonicalVarKind::Region, + }; + debug!( + "canonical: region var found with vid {:?}, \ + opportunistically resolved to {:?}", + vid, r + ); + let cvar = self.canonical_var(info, r.into()); + self.tcx().mk_region(ty::ReCanonical(cvar)) + } + + ty::ReStatic => { + if self.canonicalize_region_mode.static_region { + let info = CanonicalVarInfo { + kind: CanonicalVarKind::Region, + }; + let cvar = self.canonical_var(info, r.into()); + self.tcx().mk_region(ty::ReCanonical(cvar)) + } else { + r + } + } + + ty::ReEarlyBound(..) + | ty::ReFree(_) + | ty::ReScope(_) + | ty::ReSkolemized(..) + | ty::ReEmpty + | ty::ReErased => { + if self.canonicalize_region_mode.other_free_regions { + let info = CanonicalVarInfo { + kind: CanonicalVarKind::Region, + }; + let cvar = self.canonical_var(info, r.into()); + self.tcx().mk_region(ty::ReCanonical(cvar)) + } else { + r + } + } + + ty::ReClosureBound(..) | ty::ReCanonical(_) => { + bug!("canonical region encountered during canonicalization") + } + } + } + + fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { + match t.sty { + ty::TyInfer(ty::TyVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::General, t), + + ty::TyInfer(ty::IntVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Int, t), + + ty::TyInfer(ty::FloatVar(_)) => self.canonicalize_ty_var(CanonicalTyVarKind::Float, t), + + ty::TyInfer(ty::FreshTy(_)) + | ty::TyInfer(ty::FreshIntTy(_)) + | ty::TyInfer(ty::FreshFloatTy(_)) => { + bug!("encountered a fresh type during canonicalization") + } + + ty::TyInfer(ty::CanonicalTy(_)) => { + bug!("encountered a canonical type during canonicalization") + } + + ty::TyClosure(..) + | ty::TyGenerator(..) + | ty::TyGeneratorWitness(..) + | ty::TyBool + | ty::TyChar + | ty::TyInt(..) + | ty::TyUint(..) + | ty::TyFloat(..) + | ty::TyAdt(..) + | ty::TyStr + | ty::TyError + | ty::TyArray(..) + | ty::TySlice(..) + | ty::TyRawPtr(..) + | ty::TyRef(..) + | ty::TyFnDef(..) + | ty::TyFnPtr(_) + | ty::TyDynamic(..) + | ty::TyNever + | ty::TyTuple(..) + | ty::TyProjection(..) + | ty::TyForeign(..) + | ty::TyParam(..) + | ty::TyAnon(..) => { + if t.flags.intersects(self.needs_canonical_flags) { + t.super_fold_with(self) + } else { + t + } + } + } + } +} + +impl<'cx, 'gcx, 'tcx> Canonicalizer<'cx, 'gcx, 'tcx> { + /// The main `canonicalize` method, shared impl of + /// `canonicalize_query` and `canonicalize_response`. + fn canonicalize<V>( + value: &V, + infcx: Option<&'cx InferCtxt<'cx, 'gcx, 'tcx>>, + tcx: TyCtxt<'cx, 'gcx, 'tcx>, + canonicalize_region_mode: CanonicalizeRegionMode, + ) -> (Canonicalized<'gcx, V>, CanonicalVarValues<'tcx>) + where + V: TypeFoldable<'tcx> + Lift<'gcx>, + { + debug_assert!( + !value.has_type_flags(TypeFlags::HAS_CANONICAL_VARS), + "canonicalizing a canonical value: {:?}", + value, + ); + + let needs_canonical_flags = if canonicalize_region_mode.any() { + TypeFlags::HAS_FREE_REGIONS | TypeFlags::KEEP_IN_LOCAL_TCX + } else { + TypeFlags::KEEP_IN_LOCAL_TCX + }; + + let gcx = tcx.global_tcx(); + + // Fast path: nothing that needs to be canonicalized. + if !value.has_type_flags(needs_canonical_flags) { + let out_value = gcx.lift(value).unwrap(); + let canon_value = Canonical { + variables: Slice::empty(), + value: out_value, + }; + let values = CanonicalVarValues { + var_values: IndexVec::default(), + }; + return (canon_value, values); + } + + let mut canonicalizer = Canonicalizer { + infcx, + tcx, + canonicalize_region_mode, + needs_canonical_flags, + variables: IndexVec::default(), + indices: FxHashMap::default(), + var_values: IndexVec::default(), + }; + let out_value = value.fold_with(&mut canonicalizer); + + // Once we have canonicalized `out_value`, it should not + // contain anything that ties it to this inference context + // anymore, so it should live in the global arena. + let out_value = gcx.lift(&out_value).unwrap_or_else(|| { + bug!( + "failed to lift `{:?}`, canonicalized from `{:?}`", + out_value, + value + ) + }); + + let canonical_variables = tcx.intern_canonical_var_infos(&canonicalizer.variables.raw); + + let canonical_value = Canonical { + variables: canonical_variables, + value: out_value, + }; + let canonical_var_values = CanonicalVarValues { + var_values: canonicalizer.var_values, + }; + (canonical_value, canonical_var_values) + } + + /// Creates a canonical variable replacing `kind` from the input, + /// or returns an existing variable if `kind` has already been + /// seen. `kind` is expected to be an unbound variable (or + /// potentially a free region). + fn canonical_var(&mut self, info: CanonicalVarInfo, kind: Kind<'tcx>) -> CanonicalVar { + let Canonicalizer { + indices, + variables, + var_values, + .. + } = self; + + indices + .entry(kind) + .or_insert_with(|| { + let cvar1 = variables.push(info); + let cvar2 = var_values.push(kind); + assert_eq!(cvar1, cvar2); + cvar1 + }) + .clone() + } + + /// Given a type variable `ty_var` of the given kind, first check + /// if `ty_var` is bound to anything; if so, canonicalize + /// *that*. Otherwise, create a new canonical variable for + /// `ty_var`. + fn canonicalize_ty_var(&mut self, ty_kind: CanonicalTyVarKind, ty_var: Ty<'tcx>) -> Ty<'tcx> { + let infcx = self.infcx.expect("encountered ty-var without infcx"); + let bound_to = infcx.shallow_resolve(ty_var); + if bound_to != ty_var { + self.fold_ty(bound_to) + } else { + let info = CanonicalVarInfo { + kind: CanonicalVarKind::Ty(ty_kind), + }; + let cvar = self.canonical_var(info, ty_var.into()); + self.tcx().mk_infer(ty::InferTy::CanonicalTy(cvar)) + } + } +} diff --git a/src/librustc/infer/canonical/mod.rs b/src/librustc/infer/canonical/mod.rs new file mode 100644 index 00000000000..62424ff9226 --- /dev/null +++ b/src/librustc/infer/canonical/mod.rs @@ -0,0 +1,334 @@ +// Copyright 2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! **Canonicalization** is the key to constructing a query in the +//! middle of type inference. Ordinarily, it is not possible to store +//! types from type inference in query keys, because they contain +//! references to inference variables whose lifetimes are too short +//! and so forth. Canonicalizing a value T1 using `canonicalize_query` +//! produces two things: +//! +//! - a value T2 where each unbound inference variable has been +//! replaced with a **canonical variable**; +//! - a map M (of type `CanonicalVarValues`) from those canonical +//! variables back to the original. +//! +//! We can then do queries using T2. These will give back constriants +//! on the canonical variables which can be translated, using the map +//! M, into constraints in our source context. This process of +//! translating the results back is done by the +//! `instantiate_query_result` method. +//! +//! For a more detailed look at what is happening here, check +//! out the [chapter in the rustc guide][c]. +//! +//! [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html + +use infer::{InferCtxt, RegionVariableOrigin, TypeVariableOrigin}; +use rustc_data_structures::indexed_vec::IndexVec; +use rustc_data_structures::sync::Lrc; +use serialize::UseSpecializedDecodable; +use std::ops::Index; +use syntax::codemap::Span; +use ty::fold::TypeFoldable; +use ty::subst::Kind; +use ty::{self, CanonicalVar, Lift, Region, Slice, TyCtxt}; + +mod canonicalizer; + +pub mod query_result; + +mod substitute; + +/// A "canonicalized" type `V` is one where all free inference +/// variables have been rewriten to "canonical vars". These are +/// numbered starting from 0 in order of first appearance. +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)] +pub struct Canonical<'gcx, V> { + pub variables: CanonicalVarInfos<'gcx>, + pub value: V, +} + +pub type CanonicalVarInfos<'gcx> = &'gcx Slice<CanonicalVarInfo>; + +impl<'gcx> UseSpecializedDecodable for CanonicalVarInfos<'gcx> {} + +/// A set of values corresponding to the canonical variables from some +/// `Canonical`. You can give these values to +/// `canonical_value.substitute` to substitute them into the canonical +/// value at the right places. +/// +/// When you canonicalize a value `V`, you get back one of these +/// vectors with the original values that were replaced by canonical +/// variables. You will need to supply it later to instantiate the +/// canonicalized query response. +#[derive(Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)] +pub struct CanonicalVarValues<'tcx> { + pub var_values: IndexVec<CanonicalVar, Kind<'tcx>>, +} + +/// 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, +/// with fresh inference variables replacing the canonical values. +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)] +pub struct CanonicalVarInfo { + pub kind: CanonicalVarKind, +} + +/// Describes the "kind" of the canonical variable. This is a "kind" +/// in the type-theory sense of the term -- i.e., a "meta" type system +/// that analyzes type-like values. +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)] +pub enum CanonicalVarKind { + /// Some kind of type inference variable. + Ty(CanonicalTyVarKind), + + /// Region variable `'?R`. + Region, +} + +/// Rust actually has more than one category of type variables; +/// notably, the type variables we create for literals (e.g., 22 or +/// 22.) can only be instantiated with integral/float types (e.g., +/// usize or f32). In order to faithfully reproduce a type, we need to +/// know what set of types a given type variable can be unified with. +#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcDecodable, RustcEncodable)] +pub enum CanonicalTyVarKind { + /// General type variable `?T` that can be unified with arbitrary types. + General, + + /// Integral type variable `?I` (that can only be unified with integral types). + Int, + + /// Floating-point type variable `?F` (that can only be unified with float types). + Float, +} + +/// After we execute a query with a canonicalized key, we get back a +/// `Canonical<QueryResult<..>>`. You can use +/// `instantiate_query_result` to access the data in this result. +#[derive(Clone, Debug)] +pub struct QueryResult<'tcx, R> { + pub var_values: CanonicalVarValues<'tcx>, + pub region_constraints: Vec<QueryRegionConstraint<'tcx>>, + pub certainty: Certainty, + pub value: R, +} + +pub type Canonicalized<'gcx, V> = Canonical<'gcx, <V as Lift<'gcx>>::Lifted>; + +pub type CanonicalizedQueryResult<'gcx, T> = + Lrc<Canonical<'gcx, QueryResult<'gcx, <T as Lift<'gcx>>::Lifted>>>; + +/// Indicates whether or not we were able to prove the query to be +/// true. +#[derive(Copy, Clone, Debug)] +pub enum Certainty { + /// The query is known to be true, presuming that you apply the + /// given `var_values` and the region-constraints are satisfied. + Proven, + + /// The query is not known to be true, but also not known to be + /// false. The `var_values` represent *either* values that must + /// hold in order for the query to be true, or helpful tips that + /// *might* make it true. Currently rustc's trait solver cannot + /// distinguish the two (e.g., due to our preference for where + /// clauses over impls). + /// + /// After some unifiations and things have been done, it makes + /// sense to try and prove again -- of course, at that point, the + /// canonical form will be different, making this a distinct + /// query. + Ambiguous, +} + +impl Certainty { + pub fn is_proven(&self) -> bool { + match self { + Certainty::Proven => true, + Certainty::Ambiguous => false, + } + } + + pub fn is_ambiguous(&self) -> bool { + !self.is_proven() + } +} + +impl<'tcx, R> QueryResult<'tcx, R> { + pub fn is_proven(&self) -> bool { + self.certainty.is_proven() + } + + pub fn is_ambiguous(&self) -> bool { + !self.is_proven() + } +} + +impl<'tcx, R> Canonical<'tcx, QueryResult<'tcx, R>> { + pub fn is_proven(&self) -> bool { + self.value.is_proven() + } + + pub fn is_ambiguous(&self) -> bool { + !self.is_proven() + } +} + +pub type QueryRegionConstraint<'tcx> = ty::Binder<ty::OutlivesPredicate<Kind<'tcx>, Region<'tcx>>>; + +impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { + /// Creates a substitution S for the canonical value with fresh + /// inference variables and applies it to the canonical value. + /// Returns both the instantiated result *and* the substitution S. + /// + /// This is useful at the start of a query: it basically brings + /// the canonical value "into scope" within your new infcx. At the + /// end of processing, the substitution S (once canonicalized) + /// then represents the values that you computed for each of the + /// canonical inputs to your query. + pub fn instantiate_canonical_with_fresh_inference_vars<T>( + &self, + span: Span, + canonical: &Canonical<'tcx, T>, + ) -> (T, CanonicalVarValues<'tcx>) + where + T: TypeFoldable<'tcx>, + { + let canonical_inference_vars = + self.fresh_inference_vars_for_canonical_vars(span, canonical.variables); + 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( + &self, + span: Span, + variables: &Slice<CanonicalVarInfo>, + ) -> CanonicalVarValues<'tcx> { + let var_values: IndexVec<CanonicalVar, Kind<'tcx>> = variables + .iter() + .map(|info| self.fresh_inference_var_for_canonical_var(span, *info)) + .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( + &self, + span: Span, + cv_info: CanonicalVarInfo, + ) -> Kind<'tcx> { + match cv_info.kind { + CanonicalVarKind::Ty(ty_kind) => { + let ty = match ty_kind { + CanonicalTyVarKind::General => { + self.next_ty_var(TypeVariableOrigin::MiscVariable(span)) + } + + CanonicalTyVarKind::Int => self.tcx.mk_int_var(self.next_int_var_id()), + + CanonicalTyVarKind::Float => self.tcx.mk_float_var(self.next_float_var_id()), + }; + ty.into() + } + + CanonicalVarKind::Region => self + .next_region_var(RegionVariableOrigin::MiscVariable(span)) + .into(), + } + } +} + +CloneTypeFoldableAndLiftImpls! { + ::infer::canonical::Certainty, + ::infer::canonical::CanonicalVarInfo, + ::infer::canonical::CanonicalVarKind, +} + +CloneTypeFoldableImpls! { + for <'tcx> { + ::infer::canonical::CanonicalVarInfos<'tcx>, + } +} + +BraceStructTypeFoldableImpl! { + impl<'tcx, C> TypeFoldable<'tcx> for Canonical<'tcx, C> { + variables, + value, + } where C: TypeFoldable<'tcx> +} + +BraceStructLiftImpl! { + impl<'a, 'tcx, T> Lift<'tcx> for Canonical<'a, T> { + type Lifted = Canonical<'tcx, T::Lifted>; + variables, value + } where T: Lift<'tcx> +} + +impl<'tcx> CanonicalVarValues<'tcx> { + fn iter<'a>(&'a self) -> impl Iterator<Item = Kind<'tcx>> + 'a { + self.var_values.iter().cloned() + } + + fn len(&self) -> usize { + self.var_values.len() + } +} + +impl<'a, 'tcx> IntoIterator for &'a CanonicalVarValues<'tcx> { + type Item = Kind<'tcx>; + type IntoIter = ::std::iter::Cloned<::std::slice::Iter<'a, Kind<'tcx>>>; + + fn into_iter(self) -> Self::IntoIter { + self.var_values.iter().cloned() + } +} + +BraceStructLiftImpl! { + impl<'a, 'tcx> Lift<'tcx> for CanonicalVarValues<'a> { + type Lifted = CanonicalVarValues<'tcx>; + var_values, + } +} + +BraceStructTypeFoldableImpl! { + impl<'tcx> TypeFoldable<'tcx> for CanonicalVarValues<'tcx> { + var_values, + } +} + +BraceStructTypeFoldableImpl! { + impl<'tcx, R> TypeFoldable<'tcx> for QueryResult<'tcx, R> { + var_values, region_constraints, certainty, value + } where R: TypeFoldable<'tcx>, +} + +BraceStructLiftImpl! { + impl<'a, 'tcx, R> Lift<'tcx> for QueryResult<'a, R> { + type Lifted = QueryResult<'tcx, R::Lifted>; + var_values, region_constraints, certainty, value + } where R: Lift<'tcx> +} + +impl<'tcx> Index<CanonicalVar> for CanonicalVarValues<'tcx> { + type Output = Kind<'tcx>; + + fn index(&self, value: CanonicalVar) -> &Kind<'tcx> { + &self.var_values[value] + } +} diff --git a/src/librustc/infer/canonical/query_result.rs b/src/librustc/infer/canonical/query_result.rs new file mode 100644 index 00000000000..b8b13e03afa --- /dev/null +++ b/src/librustc/infer/canonical/query_result.rs @@ -0,0 +1,605 @@ +// Copyright 2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! This module contains the code to instantiate a "query result", and +//! in particular to extract out the resulting region obligations and +//! encode them therein. +//! +//! For an overview of what canonicaliation is and how it fits into +//! rustc, check out the [chapter in the rustc guide][c]. +//! +//! [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html + +use infer::canonical::substitute::substitute_value; +use infer::canonical::{Canonical, CanonicalVarKind, CanonicalVarValues, CanonicalizedQueryResult, + Certainty, QueryRegionConstraint, QueryResult}; +use infer::region_constraints::{Constraint, RegionConstraintData}; +use infer::InferCtxtBuilder; +use infer::{InferCtxt, InferOk, InferResult, RegionObligation}; +use rustc_data_structures::indexed_vec::Idx; +use rustc_data_structures::indexed_vec::IndexVec; +use rustc_data_structures::sync::Lrc; +use std::fmt::Debug; +use syntax::ast; +use syntax_pos::DUMMY_SP; +use traits::query::{Fallible, NoSolution}; +use traits::{FulfillmentContext, TraitEngine}; +use traits::{Obligation, ObligationCause, PredicateObligation}; +use ty::fold::TypeFoldable; +use ty::subst::{Kind, UnpackedKind}; +use ty::{self, CanonicalVar, Lift, TyCtxt}; + +impl<'cx, 'gcx, 'tcx> InferCtxtBuilder<'cx, 'gcx, 'tcx> { + /// The "main method" for a canonicalized trait query. Given the + /// canonical key `canonical_key`, this method will create a new + /// inference context, instantiate the key, and run your operation + /// `op`. The operation should yield up a result (of type `R`) as + /// well as a set of trait obligations that must be fully + /// satisfied. These obligations will be processed and the + /// canonical result created. + /// + /// Returns `NoSolution` in the event of any error. + /// + /// (It might be mildly nicer to implement this on `TyCtxt`, and + /// not `InferCtxtBuilder`, but that is a bit tricky right now. + /// In part because we would need a `for<'gcx: 'tcx>` sort of + /// bound for the closure and in part because it is convenient to + /// have `'tcx` be free on this function so that we can talk about + /// `K: TypeFoldable<'tcx>`.) + pub fn enter_canonical_trait_query<K, R>( + &'tcx mut self, + canonical_key: &Canonical<'tcx, K>, + operation: impl FnOnce(&InferCtxt<'_, 'gcx, 'tcx>, &mut FulfillmentContext<'tcx>, K) + -> Fallible<R>, + ) -> Fallible<CanonicalizedQueryResult<'gcx, R>> + where + K: TypeFoldable<'tcx>, + R: Debug + Lift<'gcx> + TypeFoldable<'tcx>, + { + self.enter(|ref infcx| { + let (key, canonical_inference_vars) = + infcx.instantiate_canonical_with_fresh_inference_vars(DUMMY_SP, &canonical_key); + let fulfill_cx = &mut FulfillmentContext::new(); + let value = operation(infcx, fulfill_cx, key)?; + infcx.make_canonicalized_query_result(canonical_inference_vars, value, fulfill_cx) + }) + } +} + +impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { + /// This method is meant to be invoked as the final step of a canonical query + /// implementation. It is given: + /// + /// - the instantiated variables `inference_vars` created from the query key + /// - the result `answer` of the query + /// - a fulfillment context `fulfill_cx` that may contain various obligations which + /// have yet to be proven. + /// + /// Given this, the function will process the obligations pending + /// in `fulfill_cx`: + /// + /// - If all the obligations can be proven successfully, it will + /// package up any resulting region obligations (extracted from + /// `infcx`) along with the fully resolved value `answer` into a + /// query result (which is then itself canonicalized). + /// - If some obligations can be neither proven nor disproven, then + /// the same thing happens, but the resulting query is marked as ambiguous. + /// - Finally, if any of the obligations result in a hard error, + /// then `Err(NoSolution)` is returned. + pub fn make_canonicalized_query_result<T>( + &self, + inference_vars: CanonicalVarValues<'tcx>, + answer: T, + fulfill_cx: &mut FulfillmentContext<'tcx>, + ) -> Fallible<CanonicalizedQueryResult<'gcx, T>> + where + T: Debug + Lift<'gcx> + TypeFoldable<'tcx>, + { + let query_result = self.make_query_result(inference_vars, answer, fulfill_cx)?; + let (canonical_result, _) = self.canonicalize_response(&query_result); + + debug!( + "make_canonicalized_query_result: canonical_result = {:#?}", + canonical_result + ); + + Ok(Lrc::new(canonical_result)) + } + + /// Helper for `make_canonicalized_query_result` that does + /// everything up until the final canonicalization. + fn make_query_result<T>( + &self, + inference_vars: CanonicalVarValues<'tcx>, + answer: T, + fulfill_cx: &mut FulfillmentContext<'tcx>, + ) -> Result<QueryResult<'tcx, T>, NoSolution> + where + T: Debug + TypeFoldable<'tcx> + Lift<'gcx>, + { + let tcx = self.tcx; + + debug!( + "make_query_result(\ + inference_vars={:?}, \ + answer={:?})", + inference_vars, answer, + ); + + // Select everything, returning errors. + let true_errors = match fulfill_cx.select_where_possible(self) { + Ok(()) => vec![], + Err(errors) => errors, + }; + debug!("true_errors = {:#?}", true_errors); + + if !true_errors.is_empty() { + // FIXME -- we don't indicate *why* we failed to solve + debug!("make_query_result: true_errors={:#?}", true_errors); + return Err(NoSolution); + } + + // Anything left unselected *now* must be an ambiguity. + let ambig_errors = match fulfill_cx.select_all_or_error(self) { + Ok(()) => vec![], + Err(errors) => errors, + }; + debug!("ambig_errors = {:#?}", ambig_errors); + + let region_obligations = self.take_registered_region_obligations(); + let region_constraints = self.with_region_constraints(|region_constraints| { + make_query_outlives(tcx, region_obligations, region_constraints) + }); + + let certainty = if ambig_errors.is_empty() { + Certainty::Proven + } else { + Certainty::Ambiguous + }; + + Ok(QueryResult { + var_values: inference_vars, + region_constraints, + certainty, + value: answer, + }) + } + + /// Given the (canonicalized) result to a canonical query, + /// instantiates the result so it can be used, plugging in the + /// values from the canonical query. (Note that the result may + /// have been ambiguous; you should check the certainty level of + /// the query before applying this function.) + /// + /// To get a good understanding of what is happening here, check + /// out the [chapter in the rustc guide][c]. + /// + /// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html#processing-the-canonicalized-query-result + pub fn instantiate_query_result_and_region_obligations<R>( + &self, + cause: &ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + original_values: &CanonicalVarValues<'tcx>, + query_result: &Canonical<'tcx, QueryResult<'tcx, R>>, + ) -> InferResult<'tcx, R> + where + R: Debug + TypeFoldable<'tcx>, + { + let InferOk { + value: result_subst, + mut obligations, + } = self.query_result_substitution(cause, param_env, original_values, query_result)?; + + obligations.extend(self.query_region_constraints_into_obligations( + cause, + param_env, + &query_result.value.region_constraints, + &result_subst, + )); + + let user_result: R = + query_result.substitute_projected(self.tcx, &result_subst, |q_r| &q_r.value); + + Ok(InferOk { + value: user_result, + obligations, + }) + } + + /// An alternative to + /// `instantiate_query_result_and_region_obligations` that is more + /// efficient for NLL. NLL is a bit more advanced in the + /// "transition to chalk" than the rest of the compiler. During + /// the NLL type check, all of the "processing" of types and + /// things happens in queries -- the NLL checker itself is only + /// interested in the region obligations (`'a: 'b` or `T: 'b`) + /// that come out of these queries, which it wants to convert into + /// MIR-based constraints and solve. Therefore, it is most + /// convenient for the NLL Type Checker to **directly consume** + /// the `QueryRegionConstraint` values that arise from doing a + /// query. This is contrast to other parts of the compiler, which + /// would prefer for those `QueryRegionConstraint` to be converted + /// into the older infcx-style constraints (e.g., calls to + /// `sub_regions` or `register_region_obligation`). + /// + /// Therefore, `instantiate_nll_query_result_and_region_obligations` performs the same + /// basic operations as `instantiate_query_result_and_region_obligations` but + /// it returns its result differently: + /// + /// - It creates a substitution `S` that maps from the original + /// query variables to the values computed in the query + /// result. If any errors arise, they are propagated back as an + /// `Err` result. + /// - In the case of a successful substitution, we will append + /// `QueryRegionConstraint` values onto the + /// `output_query_region_constraints` vector for the solver to + /// use (if an error arises, some values may also be pushed, but + /// they should be ignored). + /// - It **can happen** (though it rarely does currently) that + /// equating types and things will give rise to subobligations + /// that must be processed. In this case, those subobligations + /// are propagated back in the return value. + /// - Finally, the query result (of type `R`) is propagated back, + /// after applying the substitution `S`. + pub fn instantiate_nll_query_result_and_region_obligations<R>( + &self, + cause: &ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + original_values: &CanonicalVarValues<'tcx>, + query_result: &Canonical<'tcx, QueryResult<'tcx, R>>, + output_query_region_constraints: &mut Vec<QueryRegionConstraint<'tcx>>, + ) -> InferResult<'tcx, R> + where + R: Debug + TypeFoldable<'tcx>, + { + // In an NLL query, there should be no type variables in the + // query, only region variables. + debug_assert!(query_result.variables.iter().all(|v| match v.kind { + CanonicalVarKind::Ty(_) => false, + CanonicalVarKind::Region => true, + })); + + let result_subst = + self.query_result_substitution_guess(cause, original_values, query_result); + + // Compute `QueryRegionConstraint` values that unify each of + // the original values `v_o` that was canonicalized into a + // variable... + let mut obligations = vec![]; + + for (index, original_value) in original_values.var_values.iter_enumerated() { + // ...with the value `v_r` of that variable from the query. + let result_value = query_result + .substitute_projected(self.tcx, &result_subst, |v| &v.var_values[index]); + match (original_value.unpack(), result_value.unpack()) { + (UnpackedKind::Lifetime(ty::ReErased), UnpackedKind::Lifetime(ty::ReErased)) => { + // no action needed + } + + (UnpackedKind::Lifetime(v_o), UnpackedKind::Lifetime(v_r)) => { + // To make `v_o = v_r`, we emit `v_o: v_r` and `v_r: v_o`. + if v_o != v_r { + output_query_region_constraints + .push(ty::Binder::dummy(ty::OutlivesPredicate(v_o.into(), v_r))); + output_query_region_constraints + .push(ty::Binder::dummy(ty::OutlivesPredicate(v_r.into(), v_o))); + } + } + + (UnpackedKind::Type(v1), UnpackedKind::Type(v2)) => { + let ok = self.at(cause, param_env).eq(v1, v2)?; + obligations.extend(ok.into_obligations()); + } + + _ => { + bug!( + "kind mismatch, cannot unify {:?} and {:?}", + original_value, + result_value + ); + } + } + } + + // ...also include the other query region constraints from the query. + output_query_region_constraints.reserve(query_result.value.region_constraints.len()); + for r_c in query_result.value.region_constraints.iter() { + output_query_region_constraints.push(r_c.map_bound(|ty::OutlivesPredicate(k1, r2)| { + let k1 = substitute_value(self.tcx, &result_subst, &k1); + let r2 = substitute_value(self.tcx, &result_subst, &r2); + ty::OutlivesPredicate(k1, r2) + })); + } + + let user_result: R = + query_result.substitute_projected(self.tcx, &result_subst, |q_r| &q_r.value); + + Ok(InferOk { + value: user_result, + obligations, + }) + } + + /// Given the original values and the (canonicalized) result from + /// computing a query, returns a substitution that can be applied + /// to the query result to convert the result back into the + /// original namespace. + /// + /// The substitution also comes accompanied with subobligations + /// that arose from unification; these might occur if (for + /// example) we are doing lazy normalization and the value + /// assigned to a type variable is unified with an unnormalized + /// projection. + fn query_result_substitution<R>( + &self, + cause: &ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + original_values: &CanonicalVarValues<'tcx>, + query_result: &Canonical<'tcx, QueryResult<'tcx, R>>, + ) -> InferResult<'tcx, CanonicalVarValues<'tcx>> + where + R: Debug + TypeFoldable<'tcx>, + { + debug!( + "query_result_substitution(original_values={:#?}, query_result={:#?})", + original_values, query_result, + ); + + let result_subst = + self.query_result_substitution_guess(cause, original_values, query_result); + + let obligations = self.unify_query_result_substitution_guess( + cause, + param_env, + original_values, + &result_subst, + query_result, + )? + .into_obligations(); + + Ok(InferOk { + value: result_subst, + obligations, + }) + } + + /// Given the original values and the (canonicalized) result from + /// computing a query, returns a **guess** at a substitution that + /// can be applied to the query result to convert the result back + /// into the original namespace. This is called a **guess** + /// because it uses a quick heuristic to find the values for each + /// canonical variable; if that quick heuristic fails, then we + /// will instantiate fresh inference variables for each canonical + /// variable instead. Therefore, the result of this method must be + /// properly unified + fn query_result_substitution_guess<R>( + &self, + cause: &ObligationCause<'tcx>, + original_values: &CanonicalVarValues<'tcx>, + query_result: &Canonical<'tcx, QueryResult<'tcx, R>>, + ) -> CanonicalVarValues<'tcx> + where + R: Debug + TypeFoldable<'tcx>, + { + debug!( + "query_result_substitution_guess(original_values={:#?}, query_result={:#?})", + original_values, query_result, + ); + + // 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 + // canonicalized. + let result_values = &query_result.value.var_values; + assert_eq!(original_values.len(), result_values.len()); + + // Quickly try to find initial values for the canonical + // variables in the result in terms of the query. We do this + // by iterating down the values that the query gave to each of + // the canonical inputs. If we find that one of those values + // is directly equal to one of the canonical variables in the + // result, then we can type the corresponding value from the + // input. See the example above. + let mut opt_values: IndexVec<CanonicalVar, Option<Kind<'tcx>>> = + IndexVec::from_elem_n(None, query_result.variables.len()); + + // In terms of our example above, we are iterating over pairs like: + // [(?A, Vec<?0>), ('static, '?1), (?B, ?0)] + for (original_value, result_value) in original_values.iter().zip(result_values) { + match result_value.unpack() { + UnpackedKind::Type(result_value) => { + // e.g., here `result_value` might be `?0` in the example above... + if let ty::TyInfer(ty::InferTy::CanonicalTy(index)) = result_value.sty { + // in which case we would set `canonical_vars[0]` to `Some(?U)`. + opt_values[index] = Some(original_value); + } + } + UnpackedKind::Lifetime(result_value) => { + // e.g., here `result_value` might be `'?1` in the example above... + if let &ty::RegionKind::ReCanonical(index) = result_value { + // in which case we would set `canonical_vars[0]` to `Some('static)`. + opt_values[index] = Some(original_value); + } + } + } + } + + // Create a result substitution: if we found a value for a + // given variable in the loop above, use that. Otherwise, use + // a fresh inference variable. + let result_subst = CanonicalVarValues { + var_values: query_result + .variables + .iter() + .enumerate() + .map(|(index, info)| match opt_values[CanonicalVar::new(index)] { + Some(k) => k, + None => self.fresh_inference_var_for_canonical_var(cause.span, *info), + }) + .collect(), + }; + + result_subst + } + + /// Given a "guess" at the values for the canonical variables in + /// the input, try to unify with the *actual* values found in the + /// query result. Often, but not always, this is a no-op, because + /// we already found the mapping in the "guessing" step. + /// + /// See also: `query_result_substitution_guess` + fn unify_query_result_substitution_guess<R>( + &self, + cause: &ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + original_values: &CanonicalVarValues<'tcx>, + result_subst: &CanonicalVarValues<'tcx>, + query_result: &Canonical<'tcx, QueryResult<'tcx, R>>, + ) -> InferResult<'tcx, ()> + where + R: Debug + TypeFoldable<'tcx>, + { + // A closure that yields the result value for the given + // canonical variable; this is taken from + // `query_result.var_values` after applying the substitution + // `result_subst`. + let substituted_query_result = |index: CanonicalVar| -> Kind<'tcx> { + query_result.substitute_projected(self.tcx, &result_subst, |v| &v.var_values[index]) + }; + + // Unify the original value for each variable with the value + // taken from `query_result` (after applying `result_subst`). + Ok(self.unify_canonical_vars(cause, param_env, original_values, substituted_query_result)?) + } + + /// Converts the region constraints resulting from a query into an + /// iterator of obligations. + fn query_region_constraints_into_obligations<'a>( + &'a self, + cause: &'a ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + unsubstituted_region_constraints: &'a [QueryRegionConstraint<'tcx>], + result_subst: &'a CanonicalVarValues<'tcx>, + ) -> impl Iterator<Item = PredicateObligation<'tcx>> + 'a { + Box::new( + unsubstituted_region_constraints + .iter() + .map(move |constraint| { + let ty::OutlivesPredicate(k1, r2) = constraint.skip_binder(); // restored below + let k1 = substitute_value(self.tcx, result_subst, k1); + let r2 = substitute_value(self.tcx, result_subst, r2); + match k1.unpack() { + UnpackedKind::Lifetime(r1) => Obligation::new( + cause.clone(), + param_env, + ty::Predicate::RegionOutlives(ty::Binder::dummy( + ty::OutlivesPredicate(r1, r2), + )), + ), + + UnpackedKind::Type(t1) => Obligation::new( + cause.clone(), + param_env, + ty::Predicate::TypeOutlives(ty::Binder::dummy(ty::OutlivesPredicate( + t1, r2, + ))), + ), + } + }), + ) as Box<dyn Iterator<Item = _>> + } + + /// Given two sets of values for the same set of canonical variables, unify them. + /// The second set is produced lazilly by supplying indices from the first set. + fn unify_canonical_vars( + &self, + cause: &ObligationCause<'tcx>, + param_env: ty::ParamEnv<'tcx>, + variables1: &CanonicalVarValues<'tcx>, + variables2: impl Fn(CanonicalVar) -> Kind<'tcx>, + ) -> InferResult<'tcx, ()> { + self.commit_if_ok(|_| { + let mut obligations = vec![]; + for (index, value1) in variables1.var_values.iter_enumerated() { + let value2 = variables2(index); + + match (value1.unpack(), value2.unpack()) { + (UnpackedKind::Type(v1), UnpackedKind::Type(v2)) => { + obligations + .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations()); + } + ( + UnpackedKind::Lifetime(ty::ReErased), + UnpackedKind::Lifetime(ty::ReErased), + ) => { + // no action needed + } + (UnpackedKind::Lifetime(v1), UnpackedKind::Lifetime(v2)) => { + obligations + .extend(self.at(cause, param_env).eq(v1, v2)?.into_obligations()); + } + _ => { + bug!("kind mismatch, cannot unify {:?} and {:?}", value1, value2,); + } + } + } + Ok(InferOk { + value: (), + obligations, + }) + }) + } +} + +/// Given the region obligations and constraints scraped from the infcx, +/// creates query region constraints. +pub fn make_query_outlives<'tcx>( + tcx: TyCtxt<'_, '_, 'tcx>, + region_obligations: Vec<(ast::NodeId, RegionObligation<'tcx>)>, + region_constraints: &RegionConstraintData<'tcx>, +) -> Vec<QueryRegionConstraint<'tcx>> { + let RegionConstraintData { + constraints, + verifys, + givens, + } = region_constraints; + + assert!(verifys.is_empty()); + assert!(givens.is_empty()); + + let mut outlives: Vec<_> = constraints + .into_iter() + .map(|(k, _)| match *k { + // Swap regions because we are going from sub (<=) to outlives + // (>=). + Constraint::VarSubVar(v1, v2) => ty::OutlivesPredicate( + tcx.mk_region(ty::ReVar(v2)).into(), + tcx.mk_region(ty::ReVar(v1)), + ), + Constraint::VarSubReg(v1, r2) => { + ty::OutlivesPredicate(r2.into(), tcx.mk_region(ty::ReVar(v1))) + } + Constraint::RegSubVar(r1, v2) => { + ty::OutlivesPredicate(tcx.mk_region(ty::ReVar(v2)).into(), r1) + } + Constraint::RegSubReg(r1, r2) => ty::OutlivesPredicate(r2.into(), r1), + }) + .map(ty::Binder::dummy) // no bound regions in the code above + .collect(); + + outlives.extend( + region_obligations + .into_iter() + .map(|(_, r_o)| ty::OutlivesPredicate(r_o.sup_type.into(), r_o.sub_region)) + .map(ty::Binder::dummy), // no bound regions in the code above + ); + + outlives +} diff --git a/src/librustc/infer/canonical/substitute.rs b/src/librustc/infer/canonical/substitute.rs new file mode 100644 index 00000000000..5bc1ae689a5 --- /dev/null +++ b/src/librustc/infer/canonical/substitute.rs @@ -0,0 +1,113 @@ +// Copyright 2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! This module contains code to substitute new values into a +//! `Canonical<'tcx, T>`. +//! +//! For an overview of what canonicaliation is and how it fits into +//! rustc, check out the [chapter in the rustc guide][c]. +//! +//! [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html + +use infer::canonical::{Canonical, CanonicalVarValues}; +use ty::fold::{TypeFoldable, TypeFolder}; +use ty::subst::UnpackedKind; +use ty::{self, Ty, TyCtxt, TypeFlags}; + +impl<'tcx, V> Canonical<'tcx, V> { + /// Instantiate the wrapped value, replacing each canonical value + /// with the value given in `var_values`. + pub fn substitute(&self, tcx: TyCtxt<'_, '_, 'tcx>, var_values: &CanonicalVarValues<'tcx>) -> V + where + V: TypeFoldable<'tcx>, + { + self.substitute_projected(tcx, var_values, |value| value) + } + + /// Allows one to apply a substitute to some subset of + /// `self.value`. Invoke `projection_fn` with `self.value` to get + /// a value V that is expressed in terms of the same canonical + /// variables bound in `self` (usually this extracts from subset + /// of `self`). Apply the substitution `var_values` to this value + /// V, replacing each of the canonical variables. + pub fn substitute_projected<T>( + &self, + tcx: TyCtxt<'_, '_, 'tcx>, + var_values: &CanonicalVarValues<'tcx>, + projection_fn: impl FnOnce(&V) -> &T, + ) -> T + where + T: TypeFoldable<'tcx>, + { + assert_eq!(self.variables.len(), var_values.var_values.len()); + let value = projection_fn(&self.value); + substitute_value(tcx, var_values, value) + } +} + +/// Substitute the values from `var_values` into `value`. `var_values` +/// must be values for the set of canonical variables that appear in +/// `value`. +pub(super) fn substitute_value<'a, 'tcx, T>( + tcx: TyCtxt<'_, '_, 'tcx>, + var_values: &CanonicalVarValues<'tcx>, + value: &'a T, +) -> T +where + T: TypeFoldable<'tcx>, +{ + if var_values.var_values.is_empty() { + debug_assert!(!value.has_type_flags(TypeFlags::HAS_CANONICAL_VARS)); + value.clone() + } else if !value.has_type_flags(TypeFlags::HAS_CANONICAL_VARS) { + value.clone() + } else { + value.fold_with(&mut CanonicalVarValuesSubst { tcx, var_values }) + } +} + +struct CanonicalVarValuesSubst<'cx, 'gcx: 'tcx, 'tcx: 'cx> { + tcx: TyCtxt<'cx, 'gcx, 'tcx>, + var_values: &'cx CanonicalVarValues<'tcx>, +} + +impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for CanonicalVarValuesSubst<'cx, 'gcx, 'tcx> { + fn tcx(&self) -> TyCtxt<'_, 'gcx, 'tcx> { + self.tcx + } + + fn fold_ty(&mut self, t: Ty<'tcx>) -> Ty<'tcx> { + match t.sty { + ty::TyInfer(ty::InferTy::CanonicalTy(c)) => { + match self.var_values.var_values[c].unpack() { + UnpackedKind::Type(ty) => ty, + r => bug!("{:?} is a type but value is {:?}", c, r), + } + } + _ => { + if !t.has_type_flags(TypeFlags::HAS_CANONICAL_VARS) { + t + } else { + t.super_fold_with(self) + } + } + } + } + + fn fold_region(&mut self, r: ty::Region<'tcx>) -> ty::Region<'tcx> { + match r { + ty::RegionKind::ReCanonical(c) => match self.var_values.var_values[*c].unpack() { + UnpackedKind::Lifetime(l) => l, + r => bug!("{:?} is a region but value is {:?}", c, r), + }, + _ => r.super_fold_with(self), + } + } +} diff --git a/src/librustc/infer/mod.rs b/src/librustc/infer/mod.rs index 6b31f869ef9..5b5ae6473f8 100644 --- a/src/librustc/infer/mod.rs +++ b/src/librustc/infer/mod.rs @@ -27,7 +27,7 @@ use ty::{self, Ty, TyCtxt, GenericParamDefKind}; use ty::error::{ExpectedFound, TypeError, UnconstrainedNumeric}; use ty::fold::TypeFoldable; use ty::relate::RelateResult; -use traits::{self, ObligationCause, PredicateObligations}; +use traits::{self, ObligationCause, PredicateObligations, TraitEngine}; use rustc_data_structures::unify as ut; use std::cell::{Cell, RefCell, Ref, RefMut}; use std::collections::BTreeMap; @@ -485,6 +485,19 @@ impl<'tcx, T> InferOk<'tcx, T> { pub fn unit(self) -> InferOk<'tcx, ()> { InferOk { value: (), obligations: self.obligations } } + + /// Extract `value`, registering any obligations into `fulfill_cx` + pub fn into_value_registering_obligations( + self, + infcx: &InferCtxt<'_, '_, 'tcx>, + fulfill_cx: &mut impl TraitEngine<'tcx>, + ) -> T { + let InferOk { value, obligations } = self; + for obligation in obligations { + fulfill_cx.register_predicate_obligation(infcx, obligation); + } + value + } } impl<'tcx> InferOk<'tcx, ()> { diff --git a/src/librustc/infer/outlives/bounds.rs b/src/librustc/infer/outlives/bounds.rs index 4bc64acc763..57abdd18d35 100644 --- a/src/librustc/infer/outlives/bounds.rs +++ b/src/librustc/infer/outlives/bounds.rs @@ -11,7 +11,7 @@ use infer::InferCtxt; use syntax::ast; use syntax::codemap::Span; -use traits::{FulfillmentContext, TraitEngine}; +use traits::{FulfillmentContext, TraitEngine, TraitEngineExt}; use ty::{self, Ty, TypeFoldable}; use ty::outlives::Component; use ty::wf; diff --git a/src/librustc/infer/outlives/mod.rs b/src/librustc/infer/outlives/mod.rs index 6aafebe79c6..93079b04669 100644 --- a/src/librustc/infer/outlives/mod.rs +++ b/src/librustc/infer/outlives/mod.rs @@ -13,4 +13,4 @@ pub mod env; pub mod free_region_map; pub mod bounds; -mod obligations; +pub mod obligations; diff --git a/src/librustc/infer/outlives/obligations.rs b/src/librustc/infer/outlives/obligations.rs index e5461685bd4..07286f1250c 100644 --- a/src/librustc/infer/outlives/obligations.rs +++ b/src/librustc/infer/outlives/obligations.rs @@ -71,11 +71,11 @@ use hir::def_id::DefId; use infer::{self, GenericKind, InferCtxt, RegionObligation, SubregionOrigin, VerifyBound}; +use syntax::ast; use traits; -use ty::{self, Ty, TyCtxt, TypeFoldable}; -use ty::subst::{Subst, Substs}; use ty::outlives::Component; -use syntax::ast; +use ty::subst::{Subst, Substs}; +use ty::{self, Ty, TyCtxt, TypeFoldable}; impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { /// Registers that the given region obligation must be resolved @@ -90,8 +90,7 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { ) { debug!( "register_region_obligation(body_id={:?}, obligation={:?})", - body_id, - obligation + body_id, obligation ); self.region_obligations @@ -100,13 +99,8 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { } /// Trait queries just want to pass back type obligations "as is" - pub fn take_registered_region_obligations( - &self, - ) -> Vec<(ast::NodeId, RegionObligation<'tcx>)> { - ::std::mem::replace( - &mut *self.region_obligations.borrow_mut(), - vec![], - ) + pub fn take_registered_region_obligations(&self) -> Vec<(ast::NodeId, RegionObligation<'tcx>)> { + ::std::mem::replace(&mut *self.region_obligations.borrow_mut(), vec![]) } /// Process the region obligations that must be proven (during @@ -165,8 +159,13 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { } } - let outlives = - TypeOutlives::new(self, region_bound_pairs, implicit_region_bound, param_env); + let outlives = &mut TypeOutlives::new( + self, + self.tcx, + region_bound_pairs, + implicit_region_bound, + param_env, + ); for RegionObligation { sup_type, @@ -176,16 +175,14 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { { debug!( "process_registered_region_obligations: sup_type={:?} sub_region={:?} cause={:?}", - sup_type, - sub_region, - cause + sup_type, sub_region, cause ); - let origin = SubregionOrigin::from_obligation_cause( - &cause, - || infer::RelateParamBound(cause.span, sup_type), - ); + let origin = SubregionOrigin::from_obligation_cause(&cause, || { + infer::RelateParamBound(cause.span, sup_type) + }); + let sup_type = self.resolve_type_vars_if_possible(&sup_type); outlives.type_must_outlive(origin, sup_type, sub_region); } } @@ -201,31 +198,68 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { ty: Ty<'tcx>, region: ty::Region<'tcx>, ) { - let outlives = - TypeOutlives::new(self, region_bound_pairs, implicit_region_bound, param_env); + let outlives = &mut TypeOutlives::new( + self, + self.tcx, + region_bound_pairs, + implicit_region_bound, + param_env, + ); + let ty = self.resolve_type_vars_if_possible(&ty); outlives.type_must_outlive(origin, ty, region); } } -#[must_use] // you ought to invoke `into_accrued_obligations` when you are done =) -struct TypeOutlives<'cx, 'gcx: 'tcx, 'tcx: 'cx> { +/// The `TypeOutlives` struct has the job of "lowering" a `T: 'a` +/// obligation into a series of `'a: 'b` constraints and "verifys", as +/// described on the module comment. The final constraints are emitted +/// via a "delegate" of type `D` -- this is usually the `infcx`, which +/// accrues them into the `region_obligations` code, but for NLL we +/// use something else. +pub struct TypeOutlives<'cx, 'gcx: 'tcx, 'tcx: 'cx, D> +where + D: TypeOutlivesDelegate<'tcx>, +{ // See the comments on `process_registered_region_obligations` for the meaning // of these fields. - infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>, + delegate: D, + tcx: TyCtxt<'cx, 'gcx, 'tcx>, region_bound_pairs: &'cx [(ty::Region<'tcx>, GenericKind<'tcx>)], implicit_region_bound: Option<ty::Region<'tcx>>, param_env: ty::ParamEnv<'tcx>, } -impl<'cx, 'gcx, 'tcx> TypeOutlives<'cx, 'gcx, 'tcx> { - fn new( - infcx: &'cx InferCtxt<'cx, 'gcx, 'tcx>, +pub trait TypeOutlivesDelegate<'tcx> { + fn push_sub_region_constraint( + &mut self, + origin: SubregionOrigin<'tcx>, + a: ty::Region<'tcx>, + b: ty::Region<'tcx>, + ); + + fn push_verify( + &mut self, + origin: SubregionOrigin<'tcx>, + kind: GenericKind<'tcx>, + a: ty::Region<'tcx>, + bound: VerifyBound<'tcx>, + ); +} + +impl<'cx, 'gcx, 'tcx, D> TypeOutlives<'cx, 'gcx, 'tcx, D> +where + D: TypeOutlivesDelegate<'tcx>, +{ + pub fn new( + delegate: D, + tcx: TyCtxt<'cx, 'gcx, 'tcx>, region_bound_pairs: &'cx [(ty::Region<'tcx>, GenericKind<'tcx>)], implicit_region_bound: Option<ty::Region<'tcx>>, param_env: ty::ParamEnv<'tcx>, ) -> Self { Self { - infcx, + delegate, + tcx, region_bound_pairs, implicit_region_bound, param_env, @@ -240,33 +274,25 @@ impl<'cx, 'gcx, 'tcx> TypeOutlives<'cx, 'gcx, 'tcx> { /// - `origin`, the reason we need this constraint /// - `ty`, the type `T` /// - `region`, the region `'a` - fn type_must_outlive( - &self, + pub fn type_must_outlive( + &mut self, origin: infer::SubregionOrigin<'tcx>, ty: Ty<'tcx>, region: ty::Region<'tcx>, ) { - let ty = self.infcx.resolve_type_vars_if_possible(&ty); - debug!( "type_must_outlive(ty={:?}, region={:?}, origin={:?})", - ty, - region, - origin + ty, region, origin ); assert!(!ty.has_escaping_regions()); - let components = self.tcx().outlives_components(ty); + let components = self.tcx.outlives_components(ty); self.components_must_outlive(origin, components, region); } - fn tcx(&self) -> TyCtxt<'cx, 'gcx, 'tcx> { - self.infcx.tcx - } - fn components_must_outlive( - &self, + &mut self, origin: infer::SubregionOrigin<'tcx>, components: Vec<Component<'tcx>>, region: ty::Region<'tcx>, @@ -275,7 +301,7 @@ impl<'cx, 'gcx, 'tcx> TypeOutlives<'cx, 'gcx, 'tcx> { let origin = origin.clone(); match component { Component::Region(region1) => { - self.infcx.sub_regions(origin, region, region1); + self.delegate.push_sub_region_constraint(origin, region, region1); } Component::Param(param_ty) => { self.param_ty_must_outlive(origin, region, param_ty); @@ -290,7 +316,7 @@ impl<'cx, 'gcx, 'tcx> TypeOutlives<'cx, 'gcx, 'tcx> { // ignore this, we presume it will yield an error // later, since if a type variable is not resolved by // this point it never will be - self.infcx.tcx.sess.delay_span_bug( + self.tcx.sess.delay_span_bug( origin.span(), &format!("unresolved inference variable in outlives: {:?}", v), ); @@ -300,35 +326,31 @@ impl<'cx, 'gcx, 'tcx> TypeOutlives<'cx, 'gcx, 'tcx> { } fn param_ty_must_outlive( - &self, + &mut self, origin: infer::SubregionOrigin<'tcx>, region: ty::Region<'tcx>, param_ty: ty::ParamTy, ) { debug!( "param_ty_must_outlive(region={:?}, param_ty={:?}, origin={:?})", - region, - param_ty, - origin + region, param_ty, origin ); let verify_bound = self.param_bound(param_ty); let generic = GenericKind::Param(param_ty); - self.infcx - .verify_generic_bound(origin, generic, region, verify_bound); + self.delegate + .push_verify(origin, generic, region, verify_bound); } fn projection_must_outlive( - &self, + &mut self, origin: infer::SubregionOrigin<'tcx>, region: ty::Region<'tcx>, projection_ty: ty::ProjectionTy<'tcx>, ) { debug!( "projection_must_outlive(region={:?}, projection_ty={:?}, origin={:?})", - region, - projection_ty, - origin + region, projection_ty, origin ); // This case is thorny for inference. The fundamental problem is @@ -382,7 +404,7 @@ impl<'cx, 'gcx, 'tcx> TypeOutlives<'cx, 'gcx, 'tcx> { } for r in projection_ty.substs.regions() { - self.infcx.sub_regions(origin.clone(), region, r); + self.delegate.push_sub_region_constraint(origin.clone(), region, r); } return; @@ -408,7 +430,8 @@ impl<'cx, 'gcx, 'tcx> TypeOutlives<'cx, 'gcx, 'tcx> { .any(|r| env_bounds.contains(&r)) { debug!("projection_must_outlive: unique declared bound appears in trait ref"); - self.infcx.sub_regions(origin.clone(), region, unique_bound); + self.delegate + .push_sub_region_constraint(origin.clone(), region, unique_bound); return; } } @@ -420,8 +443,8 @@ impl<'cx, 'gcx, 'tcx> TypeOutlives<'cx, 'gcx, 'tcx> { // even though a satisfactory solution exists. let verify_bound = self.projection_bound(env_bounds, projection_ty); let generic = GenericKind::Projection(projection_ty); - self.infcx - .verify_generic_bound(origin, generic.clone(), region, verify_bound); + self.delegate + .push_verify(origin, generic.clone(), region, verify_bound); } fn type_bound(&self, ty: Ty<'tcx>) -> VerifyBound<'tcx> { @@ -469,12 +492,11 @@ impl<'cx, 'gcx, 'tcx> TypeOutlives<'cx, 'gcx, 'tcx> { ) -> VerifyBound<'tcx> { debug!( "projection_bound(declared_bounds={:?}, projection_ty={:?})", - declared_bounds, - projection_ty + declared_bounds, projection_ty ); // see the extensive comment in projection_must_outlive - let ty = self.infcx + let ty = self .tcx .mk_projection(projection_ty.item_def_id, projection_ty.substs); let recursive_bound = self.recursive_type_bound(ty); @@ -507,7 +529,7 @@ impl<'cx, 'gcx, 'tcx> TypeOutlives<'cx, 'gcx, 'tcx> { &self, generic: GenericKind<'tcx>, ) -> Vec<ty::Region<'tcx>> { - let tcx = self.tcx(); + let tcx = self.tcx; // To start, collect bounds from user environment. Note that // parameter environments are already elaborated, so we don't @@ -559,7 +581,7 @@ impl<'cx, 'gcx, 'tcx> TypeOutlives<'cx, 'gcx, 'tcx> { debug!("projection_bounds(projection_ty={:?})", projection_ty); let mut bounds = self.region_bounds_declared_on_associated_item(projection_ty.item_def_id); for r in &mut bounds { - *r = r.subst(self.tcx(), projection_ty.substs); + *r = r.subst(self.tcx, projection_ty.substs); } bounds } @@ -598,7 +620,7 @@ impl<'cx, 'gcx, 'tcx> TypeOutlives<'cx, 'gcx, 'tcx> { &self, assoc_item_def_id: DefId, ) -> Vec<ty::Region<'tcx>> { - let tcx = self.tcx(); + let tcx = self.tcx; let assoc_item = tcx.associated_item(assoc_item_def_id); let trait_def_id = assoc_item.container.assert_trait(); let trait_predicates = tcx.predicates_of(trait_def_id); @@ -634,3 +656,25 @@ impl<'cx, 'gcx, 'tcx> TypeOutlives<'cx, 'gcx, 'tcx> { .collect() } } + +impl<'cx, 'gcx, 'tcx> TypeOutlivesDelegate<'tcx> for &'cx InferCtxt<'cx, 'gcx, 'tcx> { + fn push_sub_region_constraint( + &mut self, + origin: SubregionOrigin<'tcx>, + a: ty::Region<'tcx>, + b: ty::Region<'tcx>, + ) { + self.sub_regions(origin, a, b) + } + + fn push_verify( + &mut self, + origin: SubregionOrigin<'tcx>, + kind: GenericKind<'tcx>, + a: ty::Region<'tcx>, + bound: VerifyBound<'tcx>, + ) { + self.verify_generic_bound(origin, kind, a, bound) + } +} + diff --git a/src/librustc/traits/engine.rs b/src/librustc/traits/engine.rs index 40d54885619..acbf5392cf5 100644 --- a/src/librustc/traits/engine.rs +++ b/src/librustc/traits/engine.rs @@ -16,56 +16,64 @@ use super::{FulfillmentContext, FulfillmentError}; use super::{ObligationCause, PredicateObligation}; pub trait TraitEngine<'tcx>: 'tcx { - fn normalize_projection_type<'a, 'gcx>( + fn normalize_projection_type( &mut self, - infcx: &InferCtxt<'a, 'gcx, 'tcx>, + infcx: &InferCtxt<'_, 'gcx, 'tcx>, param_env: ty::ParamEnv<'tcx>, projection_ty: ty::ProjectionTy<'tcx>, cause: ObligationCause<'tcx>, ) -> Ty<'tcx>; - fn register_bound<'a, 'gcx>( + fn register_bound( &mut self, - infcx: &InferCtxt<'a, 'gcx, 'tcx>, + infcx: &InferCtxt<'_, 'gcx, 'tcx>, param_env: ty::ParamEnv<'tcx>, ty: Ty<'tcx>, def_id: DefId, cause: ObligationCause<'tcx>, ); - fn register_predicate_obligation<'a, 'gcx>( + fn register_predicate_obligation( &mut self, - infcx: &InferCtxt<'a, 'gcx, 'tcx>, + infcx: &InferCtxt<'_, 'gcx, 'tcx>, obligation: PredicateObligation<'tcx>, ); - fn select_all_or_error<'a, 'gcx>( + fn select_all_or_error( &mut self, - infcx: &InferCtxt<'a, 'gcx, 'tcx>, + infcx: &InferCtxt<'_, 'gcx, 'tcx>, ) -> Result<(), Vec<FulfillmentError<'tcx>>>; - fn select_where_possible<'a, 'gcx>( + fn select_where_possible( &mut self, - infcx: &InferCtxt<'a, 'gcx, 'tcx>, + infcx: &InferCtxt<'_, 'gcx, 'tcx>, ) -> Result<(), Vec<FulfillmentError<'tcx>>>; fn pending_obligations(&self) -> Vec<PredicateObligation<'tcx>>; } -impl<'a, 'gcx, 'tcx> dyn TraitEngine<'tcx> { - pub fn new(_tcx: TyCtxt<'_, '_, 'tcx>) -> Box<Self> { - Box::new(FulfillmentContext::new()) - } +pub trait TraitEngineExt<'tcx> { + fn register_predicate_obligations( + &mut self, + infcx: &InferCtxt<'_, 'gcx, 'tcx>, + obligations: impl IntoIterator<Item = PredicateObligation<'tcx>>, + ); +} - pub fn register_predicate_obligations<I>( +impl<T: ?Sized + TraitEngine<'tcx>> TraitEngineExt<'tcx> for T { + fn register_predicate_obligations( &mut self, - infcx: &InferCtxt<'a, 'gcx, 'tcx>, - obligations: I, - ) where - I: IntoIterator<Item = PredicateObligation<'tcx>>, - { + infcx: &InferCtxt<'_, 'gcx, 'tcx>, + obligations: impl IntoIterator<Item = PredicateObligation<'tcx>>, + ) { for obligation in obligations { self.register_predicate_obligation(infcx, obligation); } } } + +impl dyn TraitEngine<'tcx> { + pub fn new(_tcx: TyCtxt<'_, '_, 'tcx>) -> Box<Self> { + Box::new(FulfillmentContext::new()) + } +} diff --git a/src/librustc/traits/fulfill.rs b/src/librustc/traits/fulfill.rs index 04396d73df6..b3f56d4de65 100644 --- a/src/librustc/traits/fulfill.rs +++ b/src/librustc/traits/fulfill.rs @@ -21,7 +21,7 @@ use middle::const_val::{ConstEvalErr, ErrKind}; use super::CodeAmbiguity; use super::CodeProjectionError; use super::CodeSelectionError; -use super::engine::TraitEngine; +use super::engine::{TraitEngine, TraitEngineExt}; use super::{FulfillmentError, FulfillmentErrorCode}; use super::{ObligationCause, PredicateObligation, Obligation}; use super::project; @@ -86,16 +86,6 @@ impl<'a, 'gcx, 'tcx> FulfillmentContext<'tcx> { } } - pub fn register_predicate_obligations<I>(&mut self, - infcx: &InferCtxt<'a, 'gcx, 'tcx>, - obligations: I) - where I: IntoIterator<Item = PredicateObligation<'tcx>> - { - for obligation in obligations { - self.register_predicate_obligation(infcx, obligation); - } - } - /// Attempts to select obligations using `selcx`. If `only_new_obligations` is true, then it /// only attempts to select obligations that haven't been seen before. fn select(&mut self, selcx: &mut SelectionContext<'a, 'gcx, 'tcx>) diff --git a/src/librustc/traits/mod.rs b/src/librustc/traits/mod.rs index 15f0b8eebc1..c7e55fa574f 100644 --- a/src/librustc/traits/mod.rs +++ b/src/librustc/traits/mod.rs @@ -27,7 +27,6 @@ use ty::subst::Substs; use ty::{self, AdtKind, Slice, Ty, TyCtxt, GenericParamDefKind, ToPredicate}; use ty::error::{ExpectedFound, TypeError}; use ty::fold::{TypeFolder, TypeFoldable, TypeVisitor}; -use infer::canonical::{Canonical, Canonicalize}; use infer::{InferCtxt}; use rustc_data_structures::sync::Lrc; @@ -48,7 +47,7 @@ pub use self::select::{EvaluationCache, SelectionContext, SelectionCache}; pub use self::select::{EvaluationResult, IntercrateAmbiguityCause, OverflowError}; pub use self::specialize::{OverlapError, specialization_graph, translate_substs}; pub use self::specialize::{SpecializesCache, find_associated_item}; -pub use self::engine::TraitEngine; +pub use self::engine::{TraitEngine, TraitEngineExt}; pub use self::util::elaborate_predicates; pub use self::util::supertraits; pub use self::util::Supertraits; @@ -1015,18 +1014,6 @@ pub fn provide(providers: &mut ty::query::Providers) { }; } -impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for ty::ParamEnvAnd<'tcx, Goal<'tcx>> { - // we ought to intern this, but I'm too lazy just now - type Canonicalized = Canonical<'gcx, ty::ParamEnvAnd<'gcx, Goal<'gcx>>>; - - fn intern( - _gcx: TyCtxt<'_, 'gcx, 'gcx>, - value: Canonical<'gcx, Self::Lifted>, - ) -> Self::Canonicalized { - value - } -} - pub trait ExClauseFold<'tcx> where Self: chalk_engine::context::Context + Clone, @@ -1053,20 +1040,3 @@ where tcx: TyCtxt<'a, 'gcx, 'tcx>, ) -> Option<Self::LiftedExClause>; } - -impl<'gcx: 'tcx, 'tcx, C> Canonicalize<'gcx, 'tcx> for chalk_engine::ExClause<C> -where - C: chalk_engine::context::Context + Clone, - C: ExClauseLift<'gcx> + ExClauseFold<'tcx>, - C::Substitution: Clone, - C::RegionConstraint: Clone, -{ - type Canonicalized = Canonical<'gcx, C::LiftedExClause>; - - fn intern( - _gcx: TyCtxt<'_, 'gcx, 'gcx>, - value: Canonical<'gcx, Self::Lifted>, - ) -> Self::Canonicalized { - value - } -} diff --git a/src/librustc/traits/query/dropck_outlives.rs b/src/librustc/traits/query/dropck_outlives.rs index af1d2c77c28..2aaa32aa032 100644 --- a/src/librustc/traits/query/dropck_outlives.rs +++ b/src/librustc/traits/query/dropck_outlives.rs @@ -9,13 +9,11 @@ // except according to those terms. use infer::at::At; -use infer::canonical::{Canonical, Canonicalize, QueryResult}; use infer::InferOk; use std::iter::FromIterator; -use traits::query::CanonicalTyGoal; -use ty::{self, Ty, TyCtxt}; +use syntax::codemap::Span; use ty::subst::Kind; -use rustc_data_structures::sync::Lrc; +use ty::{self, Ty, TyCtxt}; impl<'cx, 'gcx, 'tcx> At<'cx, 'gcx, 'tcx> { /// Given a type `ty` of some value being dropped, computes a set @@ -45,7 +43,10 @@ impl<'cx, 'gcx, 'tcx> At<'cx, 'gcx, 'tcx> { // any destructor. let tcx = self.infcx.tcx; if trivial_dropck_outlives(tcx, ty) { - return InferOk { value: vec![], obligations: vec![] }; + return InferOk { + value: vec![], + obligations: vec![], + }; } let gcx = tcx.global_tcx(); @@ -54,28 +55,15 @@ impl<'cx, 'gcx, 'tcx> At<'cx, 'gcx, 'tcx> { debug!("c_ty = {:?}", c_ty); match &gcx.dropck_outlives(c_ty) { Ok(result) if result.is_proven() => { - match self.infcx.instantiate_query_result( + match self.infcx.instantiate_query_result_and_region_obligations( self.cause, self.param_env, &orig_values, result, ) { - Ok(InferOk { - value: DropckOutlivesResult { kinds, overflows }, - obligations, - }) => { - for overflow_ty in overflows.into_iter().take(1) { - let mut err = struct_span_err!( - tcx.sess, - span, - E0320, - "overflow while adding drop-check rules for {}", - self.infcx.resolve_type_vars_if_possible(&ty), - ); - err.note(&format!("overflowed on {}", overflow_ty)); - err.emit(); - } - + Ok(InferOk { value, obligations }) => { + let ty = self.infcx.resolve_type_vars_if_possible(&ty); + let kinds = value.into_kinds_reporting_overflows(tcx, span, ty); return InferOk { value: kinds, obligations, @@ -102,12 +90,44 @@ impl<'cx, 'gcx, 'tcx> At<'cx, 'gcx, 'tcx> { } } -#[derive(Clone, Debug)] +#[derive(Clone, Debug, Default)] pub struct DropckOutlivesResult<'tcx> { pub kinds: Vec<Kind<'tcx>>, pub overflows: Vec<Ty<'tcx>>, } +impl<'tcx> DropckOutlivesResult<'tcx> { + pub fn report_overflows( + &self, + tcx: TyCtxt<'_, '_, 'tcx>, + span: Span, + ty: Ty<'tcx>, + ) { + for overflow_ty in self.overflows.iter().take(1) { + let mut err = struct_span_err!( + tcx.sess, + span, + E0320, + "overflow while adding drop-check rules for {}", + ty, + ); + err.note(&format!("overflowed on {}", overflow_ty)); + err.emit(); + } + } + + pub fn into_kinds_reporting_overflows( + self, + tcx: TyCtxt<'_, '_, 'tcx>, + span: Span, + ty: Ty<'tcx>, + ) -> Vec<Kind<'tcx>> { + self.report_overflows(tcx, span, ty); + let DropckOutlivesResult { kinds, overflows: _ } = self; + kinds + } +} + /// A set of constraints that need to be satisfied in order for /// a type to be valid for destruction. #[derive(Clone, Debug)] @@ -153,17 +173,6 @@ impl<'tcx> FromIterator<DtorckConstraint<'tcx>> for DtorckConstraint<'tcx> { result } } -impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for ty::ParamEnvAnd<'tcx, Ty<'tcx>> { - type Canonicalized = CanonicalTyGoal<'gcx>; - - fn intern( - _gcx: TyCtxt<'_, 'gcx, 'gcx>, - value: Canonical<'gcx, Self::Lifted>, - ) -> Self::Canonicalized { - value - } -} - BraceStructTypeFoldableImpl! { impl<'tcx> TypeFoldable<'tcx> for DropckOutlivesResult<'tcx> { kinds, overflows @@ -181,18 +190,6 @@ impl_stable_hash_for!(struct DropckOutlivesResult<'tcx> { kinds, overflows }); -impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for QueryResult<'tcx, DropckOutlivesResult<'tcx>> { - // we ought to intern this, but I'm too lazy just now - type Canonicalized = Lrc<Canonical<'gcx, QueryResult<'gcx, DropckOutlivesResult<'gcx>>>>; - - fn intern( - _gcx: TyCtxt<'_, 'gcx, 'gcx>, - value: Canonical<'gcx, Self::Lifted>, - ) -> Self::Canonicalized { - Lrc::new(value) - } -} - impl_stable_hash_for!(struct DtorckConstraint<'tcx> { outlives, dtorck_types, @@ -210,7 +207,7 @@ impl_stable_hash_for!(struct DtorckConstraint<'tcx> { /// /// Note also that `needs_drop` requires a "global" type (i.e., one /// with erased regions), but this funtcion does not. -fn trivial_dropck_outlives<'cx, 'tcx>(tcx: TyCtxt<'cx, '_, 'tcx>, ty: Ty<'tcx>) -> bool { +pub fn trivial_dropck_outlives<'tcx>(tcx: TyCtxt<'_, '_, 'tcx>, ty: Ty<'tcx>) -> bool { match ty.sty { // None of these types have a destructor and hence they do not // require anything in particular to outlive the dtor's diff --git a/src/librustc/traits/query/evaluate_obligation.rs b/src/librustc/traits/query/evaluate_obligation.rs index 4e028cac49a..c81d1123d42 100644 --- a/src/librustc/traits/query/evaluate_obligation.rs +++ b/src/librustc/traits/query/evaluate_obligation.rs @@ -9,11 +9,8 @@ // except according to those terms. use infer::InferCtxt; -use infer::canonical::{Canonical, Canonicalize}; use traits::{EvaluationResult, PredicateObligation, SelectionContext, TraitQueryMode, OverflowError}; -use traits::query::CanonicalPredicateGoal; -use ty::{ParamEnvAnd, Predicate, TyCtxt}; impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { /// Evaluates whether the predicate can be satisfied (by any means) @@ -57,14 +54,3 @@ impl<'cx, 'gcx, 'tcx> InferCtxt<'cx, 'gcx, 'tcx> { } } } - -impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for ParamEnvAnd<'tcx, Predicate<'tcx>> { - type Canonicalized = CanonicalPredicateGoal<'gcx>; - - fn intern( - _gcx: TyCtxt<'_, 'gcx, 'gcx>, - value: Canonical<'gcx, Self::Lifted>, - ) -> Self::Canonicalized { - value - } -} diff --git a/src/librustc/traits/query/mod.rs b/src/librustc/traits/query/mod.rs index 096633ddab2..54b67edb136 100644 --- a/src/librustc/traits/query/mod.rs +++ b/src/librustc/traits/query/mod.rs @@ -16,12 +16,14 @@ //! `librustc_traits`. use infer::canonical::Canonical; +use ty::error::TypeError; use ty::{self, Ty}; pub mod dropck_outlives; pub mod evaluate_obligation; pub mod normalize; pub mod normalize_erasing_regions; +pub mod type_op; pub type CanonicalProjectionGoal<'tcx> = Canonical<'tcx, ty::ParamEnvAnd<'tcx, ty::ProjectionTy<'tcx>>>; @@ -31,9 +33,27 @@ pub type CanonicalTyGoal<'tcx> = Canonical<'tcx, ty::ParamEnvAnd<'tcx, Ty<'tcx>> pub type CanonicalPredicateGoal<'tcx> = Canonical<'tcx, ty::ParamEnvAnd<'tcx, ty::Predicate<'tcx>>>; +pub type CanonicalTypeOpEqGoal<'tcx> = + Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::eq::Eq<'tcx>>>; + +pub type CanonicalTypeOpSubtypeGoal<'tcx> = + Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::subtype::Subtype<'tcx>>>; + +pub type CanonicalTypeOpProvePredicateGoal<'tcx> = + Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::prove_predicate::ProvePredicate<'tcx>>>; + +pub type CanonicalTypeOpNormalizeGoal<'tcx, T> = + Canonical<'tcx, ty::ParamEnvAnd<'tcx, type_op::normalize::Normalize<T>>>; + #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)] pub struct NoSolution; pub type Fallible<T> = Result<T, NoSolution>; +impl<'tcx> From<TypeError<'tcx>> for NoSolution { + fn from(_: TypeError<'tcx>) -> NoSolution { + NoSolution + } +} + impl_stable_hash_for!(struct NoSolution { }); diff --git a/src/librustc/traits/query/normalize.rs b/src/librustc/traits/query/normalize.rs index 6d2df4c2018..8d10195941e 100644 --- a/src/librustc/traits/query/normalize.rs +++ b/src/librustc/traits/query/normalize.rs @@ -14,12 +14,9 @@ use infer::{InferCtxt, InferOk}; use infer::at::At; -use infer::canonical::{Canonical, Canonicalize, QueryResult}; use middle::const_val::ConstVal; use mir::interpret::GlobalId; -use rustc_data_structures::sync::Lrc; use traits::{Obligation, ObligationCause, PredicateObligation, Reveal}; -use traits::query::CanonicalProjectionGoal; use traits::project::Normalized; use ty::{self, Ty, TyCtxt}; use ty::fold::{TypeFoldable, TypeFolder}; @@ -163,7 +160,7 @@ impl<'cx, 'gcx, 'tcx> TypeFolder<'gcx, 'tcx> for QueryNormalizer<'cx, 'gcx, 'tcx return ty; } - match self.infcx.instantiate_query_result( + match self.infcx.instantiate_query_result_and_region_obligations( self.cause, self.param_env, &orig_values, @@ -251,29 +248,6 @@ BraceStructLiftImpl! { } } -impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for ty::ParamEnvAnd<'tcx, ty::ProjectionTy<'tcx>> { - type Canonicalized = CanonicalProjectionGoal<'gcx>; - - fn intern( - _gcx: TyCtxt<'_, 'gcx, 'gcx>, - value: Canonical<'gcx, Self::Lifted>, - ) -> Self::Canonicalized { - value - } -} - -impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for QueryResult<'tcx, NormalizationResult<'tcx>> { - // we ought to intern this, but I'm too lazy just now - type Canonicalized = Lrc<Canonical<'gcx, QueryResult<'gcx, NormalizationResult<'gcx>>>>; - - fn intern( - _gcx: TyCtxt<'_, 'gcx, 'gcx>, - value: Canonical<'gcx, Self::Lifted>, - ) -> Self::Canonicalized { - Lrc::new(value) - } -} - impl_stable_hash_for!(struct NormalizationResult<'tcx> { normalized_ty }); diff --git a/src/librustc/traits/query/type_op/custom.rs b/src/librustc/traits/query/type_op/custom.rs new file mode 100644 index 00000000000..3d10ce80585 --- /dev/null +++ b/src/librustc/traits/query/type_op/custom.rs @@ -0,0 +1,100 @@ +// Copyright 2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use infer::{InferCtxt, InferOk}; +use std::fmt; +use traits::query::Fallible; + +use infer::canonical::query_result; +use infer::canonical::QueryRegionConstraint; +use std::rc::Rc; +use syntax::codemap::DUMMY_SP; +use traits::{ObligationCause, TraitEngine, TraitEngineExt}; + +pub struct CustomTypeOp<F, G> { + closure: F, + description: G, +} + +impl<F, G> CustomTypeOp<F, G> { + pub fn new<'gcx, 'tcx, R>(closure: F, description: G) -> Self + where + F: FnOnce(&InferCtxt<'_, 'gcx, 'tcx>) -> Fallible<InferOk<'tcx, R>>, + G: Fn() -> String, + { + CustomTypeOp { + closure, + description, + } + } +} + +impl<'gcx, 'tcx, F, R, G> super::TypeOp<'gcx, 'tcx> for CustomTypeOp<F, G> +where + F: for<'a, 'cx> FnOnce(&'a InferCtxt<'cx, 'gcx, 'tcx>) -> Fallible<InferOk<'tcx, R>>, + G: Fn() -> String, +{ + type Output = R; + + /// Processes the operation and all resulting obligations, + /// returning the final result along with any region constraints + /// (they will be given over to the NLL region solver). + fn fully_perform( + self, + infcx: &InferCtxt<'_, 'gcx, 'tcx>, + ) -> Fallible<(Self::Output, Option<Rc<Vec<QueryRegionConstraint<'tcx>>>>)> { + if cfg!(debug_assertions) { + info!("fully_perform({:?})", self); + } + + scrape_region_constraints(infcx, || Ok((self.closure)(infcx)?)) + } +} + +impl<F, G> fmt::Debug for CustomTypeOp<F, G> +where + G: Fn() -> String, +{ + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + write!(f, "{}", (self.description)()) + } +} + +/// Executes `op` and then scrapes out all the "old style" region +/// constraints that result, creating query-region-constraints. +fn scrape_region_constraints<'gcx, 'tcx, R>( + infcx: &InferCtxt<'_, 'gcx, 'tcx>, + op: impl FnOnce() -> Fallible<InferOk<'tcx, R>>, +) -> Fallible<(R, Option<Rc<Vec<QueryRegionConstraint<'tcx>>>>)> { + let mut fulfill_cx = TraitEngine::new(infcx.tcx); + let dummy_body_id = ObligationCause::dummy().body_id; + let InferOk { value, obligations } = infcx.commit_if_ok(|_| op())?; + debug_assert!(obligations.iter().all(|o| o.cause.body_id == dummy_body_id)); + fulfill_cx.register_predicate_obligations(infcx, obligations); + if let Err(e) = fulfill_cx.select_all_or_error(infcx) { + infcx.tcx.sess.diagnostic().delay_span_bug( + DUMMY_SP, + &format!("errors selecting obligation during MIR typeck: {:?}", e), + ); + } + + let region_obligations = infcx.take_registered_region_obligations(); + + let region_constraint_data = infcx.take_and_reset_region_constraints(); + + let outlives = + query_result::make_query_outlives(infcx.tcx, region_obligations, ®ion_constraint_data); + + if outlives.is_empty() { + Ok((value, None)) + } else { + Ok((value, Some(Rc::new(outlives)))) + } +} diff --git a/src/librustc/traits/query/type_op/eq.rs b/src/librustc/traits/query/type_op/eq.rs new file mode 100644 index 00000000000..52a087cbc80 --- /dev/null +++ b/src/librustc/traits/query/type_op/eq.rs @@ -0,0 +1,72 @@ +// Copyright 2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use infer::canonical::{Canonical, Canonicalized, CanonicalizedQueryResult, QueryResult}; +use traits::query::Fallible; +use ty::{ParamEnvAnd, Ty, TyCtxt}; + +#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)] +pub struct Eq<'tcx> { + pub a: Ty<'tcx>, + pub b: Ty<'tcx>, +} + +impl<'tcx> Eq<'tcx> { + pub fn new(a: Ty<'tcx>, b: Ty<'tcx>) -> Self { + Self { a, b } + } +} + +impl<'gcx: 'tcx, 'tcx> super::QueryTypeOp<'gcx, 'tcx> for Eq<'tcx> { + type QueryResult = (); + + fn try_fast_path( + _tcx: TyCtxt<'_, 'gcx, 'tcx>, + key: &ParamEnvAnd<'tcx, Eq<'tcx>>, + ) -> Option<Self::QueryResult> { + if key.value.a == key.value.b { + Some(()) + } else { + None + } + } + + fn perform_query( + tcx: TyCtxt<'_, 'gcx, 'tcx>, + canonicalized: Canonicalized<'gcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalizedQueryResult<'gcx, ()>> { + tcx.type_op_eq(canonicalized) + } + + fn shrink_to_tcx_lifetime( + v: &'a CanonicalizedQueryResult<'gcx, ()>, + ) -> &'a Canonical<'tcx, QueryResult<'tcx, ()>> { + v + } +} + +BraceStructTypeFoldableImpl! { + impl<'tcx> TypeFoldable<'tcx> for Eq<'tcx> { + a, + b, + } +} + +BraceStructLiftImpl! { + impl<'a, 'tcx> Lift<'tcx> for Eq<'a> { + type Lifted = Eq<'tcx>; + a, + b, + } +} + +impl_stable_hash_for! { + struct Eq<'tcx> { a, b } +} diff --git a/src/librustc/traits/query/type_op/mod.rs b/src/librustc/traits/query/type_op/mod.rs new file mode 100644 index 00000000000..3dfa66cd41a --- /dev/null +++ b/src/librustc/traits/query/type_op/mod.rs @@ -0,0 +1,163 @@ +// Copyright 2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use infer::canonical::{Canonical, Canonicalized, CanonicalizedQueryResult, QueryRegionConstraint, + QueryResult}; +use infer::{InferCtxt, InferOk}; +use std::fmt; +use std::rc::Rc; +use traits::query::Fallible; +use traits::ObligationCause; +use ty::fold::TypeFoldable; +use ty::{Lift, ParamEnvAnd, TyCtxt}; + +pub mod custom; +pub mod eq; +pub mod normalize; +pub mod outlives; +pub mod prove_predicate; +use self::prove_predicate::ProvePredicate; +pub mod subtype; + +/// "Type ops" are used in NLL to perform some particular action and +/// extract out the resulting region constraints (or an error if it +/// cannot be completed). +pub trait TypeOp<'gcx, 'tcx>: Sized + fmt::Debug { + type Output; + + /// Processes the operation and all resulting obligations, + /// returning the final result along with any region constraints + /// (they will be given over to the NLL region solver). + fn fully_perform( + self, + infcx: &InferCtxt<'_, 'gcx, 'tcx>, + ) -> Fallible<(Self::Output, Option<Rc<Vec<QueryRegionConstraint<'tcx>>>>)>; +} + +/// "Query type ops" are type ops that are implemented using a +/// [canonical query][c]. The `Self` type here contains the kernel of +/// information needed to do the operation -- `TypeOp` is actually +/// implemented for `ParamEnvAnd<Self>`, since we always need to bring +/// along a parameter environment as well. For query type-ops, we will +/// first canonicalize the key and then invoke the query on the tcx, +/// which produces the resulting query region constraints. +/// +/// [c]: https://rust-lang-nursery.github.io/rustc-guide/traits/canonicalization.html +pub trait QueryTypeOp<'gcx: 'tcx, 'tcx>: + fmt::Debug + Sized + TypeFoldable<'tcx> + Lift<'gcx> +{ + type QueryResult: TypeFoldable<'tcx> + Lift<'gcx>; + + /// Give query the option for a simple fast path that never + /// actually hits the tcx cache lookup etc. Return `Some(r)` with + /// a final result or `None` to do the full path. + fn try_fast_path( + tcx: TyCtxt<'_, 'gcx, 'tcx>, + key: &ParamEnvAnd<'tcx, Self>, + ) -> Option<Self::QueryResult>; + + /// Performs the actual query with the canonicalized key -- the + /// real work happens here. This method is not given an `infcx` + /// because it shouldn't need one -- and if it had access to one, + /// it might do things like invoke `sub_regions`, which would be + /// bad, because it would create subregion relationships that are + /// not captured in the return value. + fn perform_query( + tcx: TyCtxt<'_, 'gcx, 'tcx>, + canonicalized: Canonicalized<'gcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalizedQueryResult<'gcx, Self::QueryResult>>; + + /// Casts a lifted query result (which is in the gcx lifetime) + /// into the tcx lifetime. This is always just an identity cast, + /// but the generic code doesn't realize it -- put another way, in + /// the generic code, we have a `Lifted<'gcx, Self::QueryResult>` + /// and we want to convert that to a `Self::QueryResult`. This is + /// not a priori valid, so we can't do it -- but in practice, it + /// is always a no-op (e.g., the lifted form of a type, + /// `Ty<'gcx>`, is a subtype of `Ty<'tcx>`). So we have to push + /// the operation into the impls that know more specifically what + /// `QueryResult` is. This operation would (maybe) be nicer with + /// something like HKTs or GATs, since then we could make + /// `QueryResult` parametric and `'gcx` and `'tcx` etc. + fn shrink_to_tcx_lifetime( + lifted_query_result: &'a CanonicalizedQueryResult<'gcx, Self::QueryResult>, + ) -> &'a Canonical<'tcx, QueryResult<'tcx, Self::QueryResult>>; + + fn fully_perform_into( + query_key: ParamEnvAnd<'tcx, Self>, + infcx: &InferCtxt<'_, 'gcx, 'tcx>, + output_query_region_constraints: &mut Vec<QueryRegionConstraint<'tcx>>, + ) -> Fallible<Self::QueryResult> { + if let Some(result) = QueryTypeOp::try_fast_path(infcx.tcx, &query_key) { + return Ok(result); + } + + // FIXME(#33684) -- We need to use + // `canonicalize_hr_query_hack` here because of things + // like the subtype query, which go awry around + // `'static` otherwise. + let (canonical_self, canonical_var_values) = infcx.canonicalize_hr_query_hack(&query_key); + let canonical_result = Self::perform_query(infcx.tcx, canonical_self)?; + let canonical_result = Self::shrink_to_tcx_lifetime(&canonical_result); + + let param_env = query_key.param_env; + + let InferOk { value, obligations } = infcx + .instantiate_nll_query_result_and_region_obligations( + &ObligationCause::dummy(), + param_env, + &canonical_var_values, + canonical_result, + output_query_region_constraints, + )?; + + // Typically, instantiating NLL query results does not + // create obligations. However, in some cases there + // are unresolved type variables, and unify them *can* + // create obligations. In that case, we have to go + // fulfill them. We do this via a (recursive) query. + for obligation in obligations { + let () = ProvePredicate::fully_perform_into( + obligation + .param_env + .and(ProvePredicate::new(obligation.predicate)), + infcx, + output_query_region_constraints, + )?; + } + + Ok(value) + } +} + +impl<'gcx: 'tcx, 'tcx, Q> TypeOp<'gcx, 'tcx> for ParamEnvAnd<'tcx, Q> +where + Q: QueryTypeOp<'gcx, 'tcx>, +{ + type Output = Q::QueryResult; + + fn fully_perform( + self, + infcx: &InferCtxt<'_, 'gcx, 'tcx>, + ) -> Fallible<(Self::Output, Option<Rc<Vec<QueryRegionConstraint<'tcx>>>>)> { + let mut qrc = vec![]; + let r = Q::fully_perform_into(self, infcx, &mut qrc)?; + + // Promote the final query-region-constraints into a + // (optional) ref-counted vector: + let opt_qrc = if qrc.is_empty() { + None + } else { + Some(Rc::new(qrc)) + }; + + Ok((r, opt_qrc)) + } +} diff --git a/src/librustc/traits/query/type_op/normalize.rs b/src/librustc/traits/query/type_op/normalize.rs new file mode 100644 index 00000000000..0c393fa4ca8 --- /dev/null +++ b/src/librustc/traits/query/type_op/normalize.rs @@ -0,0 +1,161 @@ +// Copyright 2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use infer::canonical::{Canonical, Canonicalized, CanonicalizedQueryResult, QueryResult}; +use std::fmt; +use traits::query::Fallible; +use ty::fold::TypeFoldable; +use ty::{self, Lift, ParamEnvAnd, Ty, TyCtxt}; + +#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)] +pub struct Normalize<T> { + pub value: T, +} + +impl<'tcx, T> Normalize<T> +where + T: fmt::Debug + TypeFoldable<'tcx>, +{ + pub fn new(value: T) -> Self { + Self { value } + } +} + +impl<'gcx: 'tcx, 'tcx, T> super::QueryTypeOp<'gcx, 'tcx> for Normalize<T> +where + T: Normalizable<'gcx, 'tcx>, +{ + type QueryResult = T; + + fn try_fast_path(_tcx: TyCtxt<'_, 'gcx, 'tcx>, key: &ParamEnvAnd<'tcx, Self>) -> Option<T> { + if !key.value.value.has_projections() { + Some(key.value.value) + } else { + None + } + } + + fn perform_query( + tcx: TyCtxt<'_, 'gcx, 'tcx>, + canonicalized: Canonicalized<'gcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalizedQueryResult<'gcx, Self::QueryResult>> { + T::type_op_method(tcx, canonicalized) + } + + fn shrink_to_tcx_lifetime( + v: &'a CanonicalizedQueryResult<'gcx, T>, + ) -> &'a Canonical<'tcx, QueryResult<'tcx, T>> { + T::shrink_to_tcx_lifetime(v) + } +} + +pub trait Normalizable<'gcx, 'tcx>: fmt::Debug + TypeFoldable<'tcx> + Lift<'gcx> + Copy { + fn type_op_method( + tcx: TyCtxt<'_, 'gcx, 'tcx>, + canonicalized: Canonicalized<'gcx, ParamEnvAnd<'tcx, Normalize<Self>>>, + ) -> Fallible<CanonicalizedQueryResult<'gcx, Self>>; + + /// Convert from the `'gcx` (lifted) form of `Self` into the `tcx` + /// form of `Self`. + fn shrink_to_tcx_lifetime( + v: &'a CanonicalizedQueryResult<'gcx, Self>, + ) -> &'a Canonical<'tcx, QueryResult<'tcx, Self>>; +} + +impl Normalizable<'gcx, 'tcx> for Ty<'tcx> +where + 'gcx: 'tcx, +{ + fn type_op_method( + tcx: TyCtxt<'_, 'gcx, 'tcx>, + canonicalized: Canonicalized<'gcx, ParamEnvAnd<'tcx, Normalize<Self>>>, + ) -> Fallible<CanonicalizedQueryResult<'gcx, Self>> { + tcx.type_op_normalize_ty(canonicalized) + } + + fn shrink_to_tcx_lifetime( + v: &'a CanonicalizedQueryResult<'gcx, Self>, + ) -> &'a Canonical<'tcx, QueryResult<'tcx, Self>> { + v + } +} + +impl Normalizable<'gcx, 'tcx> for ty::Predicate<'tcx> +where + 'gcx: 'tcx, +{ + fn type_op_method( + tcx: TyCtxt<'_, 'gcx, 'tcx>, + canonicalized: Canonicalized<'gcx, ParamEnvAnd<'tcx, Normalize<Self>>>, + ) -> Fallible<CanonicalizedQueryResult<'gcx, Self>> { + tcx.type_op_normalize_predicate(canonicalized) + } + + fn shrink_to_tcx_lifetime( + v: &'a CanonicalizedQueryResult<'gcx, Self>, + ) -> &'a Canonical<'tcx, QueryResult<'tcx, Self>> { + v + } +} + +impl Normalizable<'gcx, 'tcx> for ty::PolyFnSig<'tcx> +where + 'gcx: 'tcx, +{ + fn type_op_method( + tcx: TyCtxt<'_, 'gcx, 'tcx>, + canonicalized: Canonicalized<'gcx, ParamEnvAnd<'tcx, Normalize<Self>>>, + ) -> Fallible<CanonicalizedQueryResult<'gcx, Self>> { + tcx.type_op_normalize_poly_fn_sig(canonicalized) + } + + fn shrink_to_tcx_lifetime( + v: &'a CanonicalizedQueryResult<'gcx, Self>, + ) -> &'a Canonical<'tcx, QueryResult<'tcx, Self>> { + v + } +} + +impl Normalizable<'gcx, 'tcx> for ty::FnSig<'tcx> +where + 'gcx: 'tcx, +{ + fn type_op_method( + tcx: TyCtxt<'_, 'gcx, 'tcx>, + canonicalized: Canonicalized<'gcx, ParamEnvAnd<'tcx, Normalize<Self>>>, + ) -> Fallible<CanonicalizedQueryResult<'gcx, Self>> { + tcx.type_op_normalize_fn_sig(canonicalized) + } + + fn shrink_to_tcx_lifetime( + v: &'a CanonicalizedQueryResult<'gcx, Self>, + ) -> &'a Canonical<'tcx, QueryResult<'tcx, Self>> { + v + } +} + +BraceStructTypeFoldableImpl! { + impl<'tcx, T> TypeFoldable<'tcx> for Normalize<T> { + value, + } where T: TypeFoldable<'tcx>, +} + +BraceStructLiftImpl! { + impl<'tcx, T> Lift<'tcx> for Normalize<T> { + type Lifted = Normalize<T::Lifted>; + value, + } where T: Lift<'tcx>, +} + +impl_stable_hash_for! { + impl<'tcx, T> for struct Normalize<T> { + value + } +} diff --git a/src/librustc/traits/query/type_op/outlives.rs b/src/librustc/traits/query/type_op/outlives.rs new file mode 100644 index 00000000000..e41ae7a72f9 --- /dev/null +++ b/src/librustc/traits/query/type_op/outlives.rs @@ -0,0 +1,100 @@ +// Copyright 2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use infer::canonical::{Canonical, Canonicalized, CanonicalizedQueryResult, QueryResult}; +use traits::query::dropck_outlives::trivial_dropck_outlives; +use traits::query::dropck_outlives::DropckOutlivesResult; +use traits::query::Fallible; +use ty::{ParamEnvAnd, Ty, TyCtxt}; + +#[derive(Copy, Clone, Debug)] +pub struct DropckOutlives<'tcx> { + dropped_ty: Ty<'tcx>, +} + +impl<'tcx> DropckOutlives<'tcx> { + pub fn new(dropped_ty: Ty<'tcx>) -> Self { + DropckOutlives { dropped_ty } + } +} + +impl super::QueryTypeOp<'gcx, 'tcx> for DropckOutlives<'tcx> +where + 'gcx: 'tcx, +{ + type QueryResult = DropckOutlivesResult<'tcx>; + + fn try_fast_path( + tcx: TyCtxt<'_, 'gcx, 'tcx>, + key: &ParamEnvAnd<'tcx, Self>, + ) -> Option<Self::QueryResult> { + if trivial_dropck_outlives(tcx, key.value.dropped_ty) { + Some(DropckOutlivesResult::default()) + } else { + None + } + } + + fn perform_query( + tcx: TyCtxt<'_, 'gcx, 'tcx>, + canonicalized: Canonicalized<'gcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalizedQueryResult<'gcx, Self::QueryResult>> { + // Subtle: note that we are not invoking + // `infcx.at(...).dropck_outlives(...)` here, but rather the + // underlying `dropck_outlives` query. This same underlying + // query is also used by the + // `infcx.at(...).dropck_outlives(...)` fn. Avoiding the + // wrapper means we don't need an infcx in this code, which is + // good because the interface doesn't give us one (so that we + // know we are not registering any subregion relations or + // other things). + + // FIXME convert to the type expected by the `dropck_outlives` + // query. This should eventually be fixed by changing the + // *underlying query*. + let Canonical { + variables, + value: + ParamEnvAnd { + param_env, + value: DropckOutlives { dropped_ty }, + }, + } = canonicalized; + let canonicalized = Canonical { + variables, + value: param_env.and(dropped_ty), + }; + + tcx.dropck_outlives(canonicalized) + } + + fn shrink_to_tcx_lifetime( + lifted_query_result: &'a CanonicalizedQueryResult<'gcx, Self::QueryResult>, + ) -> &'a Canonical<'tcx, QueryResult<'tcx, Self::QueryResult>> { + lifted_query_result + } +} + +BraceStructTypeFoldableImpl! { + impl<'tcx> TypeFoldable<'tcx> for DropckOutlives<'tcx> { + dropped_ty + } +} + +BraceStructLiftImpl! { + impl<'a, 'tcx> Lift<'tcx> for DropckOutlives<'a> { + type Lifted = DropckOutlives<'tcx>; + dropped_ty + } +} + +impl_stable_hash_for! { + struct DropckOutlives<'tcx> { dropped_ty } +} diff --git a/src/librustc/traits/query/type_op/prove_predicate.rs b/src/librustc/traits/query/type_op/prove_predicate.rs new file mode 100644 index 00000000000..33dc3210f08 --- /dev/null +++ b/src/librustc/traits/query/type_op/prove_predicate.rs @@ -0,0 +1,65 @@ +// Copyright 2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use infer::canonical::{Canonical, Canonicalized, CanonicalizedQueryResult, QueryResult}; +use traits::query::Fallible; +use ty::{ParamEnvAnd, Predicate, TyCtxt}; + +#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)] +pub struct ProvePredicate<'tcx> { + pub predicate: Predicate<'tcx>, +} + +impl<'tcx> ProvePredicate<'tcx> { + pub fn new(predicate: Predicate<'tcx>) -> Self { + ProvePredicate { predicate } + } +} + +impl<'gcx: 'tcx, 'tcx> super::QueryTypeOp<'gcx, 'tcx> for ProvePredicate<'tcx> { + type QueryResult = (); + + fn try_fast_path( + _tcx: TyCtxt<'_, 'gcx, 'tcx>, + _key: &ParamEnvAnd<'tcx, Self>, + ) -> Option<Self::QueryResult> { + None + } + + fn perform_query( + tcx: TyCtxt<'_, 'gcx, 'tcx>, + canonicalized: Canonicalized<'gcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalizedQueryResult<'gcx, ()>> { + tcx.type_op_prove_predicate(canonicalized) + } + + fn shrink_to_tcx_lifetime( + v: &'a CanonicalizedQueryResult<'gcx, ()>, + ) -> &'a Canonical<'tcx, QueryResult<'tcx, ()>> { + v + } +} + +BraceStructTypeFoldableImpl! { + impl<'tcx> TypeFoldable<'tcx> for ProvePredicate<'tcx> { + predicate, + } +} + +BraceStructLiftImpl! { + impl<'a, 'tcx> Lift<'tcx> for ProvePredicate<'a> { + type Lifted = ProvePredicate<'tcx>; + predicate, + } +} + +impl_stable_hash_for! { + struct ProvePredicate<'tcx> { predicate } +} diff --git a/src/librustc/traits/query/type_op/subtype.rs b/src/librustc/traits/query/type_op/subtype.rs new file mode 100644 index 00000000000..dc41bb1d6ab --- /dev/null +++ b/src/librustc/traits/query/type_op/subtype.rs @@ -0,0 +1,72 @@ +// Copyright 2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use infer::canonical::{Canonical, Canonicalized, CanonicalizedQueryResult, QueryResult}; +use traits::query::Fallible; +use ty::{ParamEnvAnd, Ty, TyCtxt}; + +#[derive(Copy, Clone, Debug, Hash, PartialEq, Eq)] +pub struct Subtype<'tcx> { + pub sub: Ty<'tcx>, + pub sup: Ty<'tcx>, +} + +impl<'tcx> Subtype<'tcx> { + pub fn new(sub: Ty<'tcx>, sup: Ty<'tcx>) -> Self { + Self { + sub, + sup, + } + } +} + +impl<'gcx: 'tcx, 'tcx> super::QueryTypeOp<'gcx, 'tcx> for Subtype<'tcx> { + type QueryResult = (); + + fn try_fast_path(_tcx: TyCtxt<'_, 'gcx, 'tcx>, key: &ParamEnvAnd<'tcx, Self>) -> Option<()> { + if key.value.sub == key.value.sup { + Some(()) + } else { + None + } + } + + fn perform_query( + tcx: TyCtxt<'_, 'gcx, 'tcx>, + canonicalized: Canonicalized<'gcx, ParamEnvAnd<'tcx, Self>>, + ) -> Fallible<CanonicalizedQueryResult<'gcx, ()>> { + tcx.type_op_subtype(canonicalized) + } + + fn shrink_to_tcx_lifetime( + v: &'a CanonicalizedQueryResult<'gcx, ()>, + ) -> &'a Canonical<'tcx, QueryResult<'tcx, ()>> { + v + } +} + +BraceStructTypeFoldableImpl! { + impl<'tcx> TypeFoldable<'tcx> for Subtype<'tcx> { + sub, + sup, + } +} + +BraceStructLiftImpl! { + impl<'a, 'tcx> Lift<'tcx> for Subtype<'a> { + type Lifted = Subtype<'tcx>; + sub, + sup, + } +} + +impl_stable_hash_for! { + struct Subtype<'tcx> { sub, sup } +} diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs index 6cbf4fad02c..5142a30ae57 100644 --- a/src/librustc/ty/context.rs +++ b/src/librustc/ty/context.rs @@ -64,6 +64,7 @@ use std::borrow::Borrow; use std::cmp::Ordering; use std::collections::hash_map::{self, Entry}; use std::hash::{Hash, Hasher}; +use std::fmt; use std::mem; use std::ops::Deref; use std::iter; @@ -1503,8 +1504,8 @@ impl<'gcx: 'tcx, 'tcx> GlobalCtxt<'gcx> { /// contain the TypeVariants key or if the address of the interned /// pointer differs. The latter case is possible if a primitive type, /// e.g. `()` or `u8`, was interned in a different context. -pub trait Lift<'tcx> { - type Lifted: 'tcx; +pub trait Lift<'tcx>: fmt::Debug { + type Lifted: fmt::Debug + 'tcx; fn lift_to_tcx<'a, 'gcx>(&self, tcx: TyCtxt<'a, 'gcx, 'tcx>) -> Option<Self::Lifted>; } diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs index ce709831455..e89a022f818 100644 --- a/src/librustc/ty/mod.rs +++ b/src/librustc/ty/mod.rs @@ -21,7 +21,7 @@ use hir::map::DefPathData; use hir::svh::Svh; use ich::Fingerprint; use ich::StableHashingContext; -use infer::canonical::{Canonical, Canonicalize}; +use infer::canonical::Canonical; use middle::lang_items::{FnTraitLangItem, FnMutTraitLangItem, FnOnceTraitLangItem}; use middle::privacy::AccessLevels; use middle::resolve_lifetime::ObjectLifetimeDefault; @@ -591,15 +591,6 @@ impl<'tcx> serialize::UseSpecializedDecodable for Ty<'tcx> {} pub type CanonicalTy<'gcx> = Canonical<'gcx, Ty<'gcx>>; -impl <'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for Ty<'tcx> { - type Canonicalized = CanonicalTy<'gcx>; - - fn intern(_gcx: TyCtxt<'_, 'gcx, 'gcx>, - value: Canonical<'gcx, Self::Lifted>) -> Self::Canonicalized { - value - } -} - extern { /// A dummy type used to force Slice to by unsized without requiring fat pointers type OpaqueSliceContents; diff --git a/src/librustc/ty/query/config.rs b/src/librustc/ty/query/config.rs index cc00e9a00ab..eadfc62244f 100644 --- a/src/librustc/ty/query/config.rs +++ b/src/librustc/ty/query/config.rs @@ -12,7 +12,10 @@ use dep_graph::SerializedDepNodeIndex; use dep_graph::DepNode; use hir::def_id::{CrateNum, DefId, DefIndex}; use mir::interpret::{GlobalId, ConstValue}; -use traits::query::{CanonicalPredicateGoal, CanonicalProjectionGoal, CanonicalTyGoal}; +use traits::query::{ + CanonicalPredicateGoal, CanonicalProjectionGoal, CanonicalTyGoal, CanonicalTypeOpEqGoal, + CanonicalTypeOpNormalizeGoal, CanonicalTypeOpProvePredicateGoal, CanonicalTypeOpSubtypeGoal, +}; use ty::{self, ParamEnvAnd, Ty, TyCtxt}; use ty::subst::Substs; use ty::query::queries; @@ -102,6 +105,54 @@ impl<'tcx> QueryDescription<'tcx> for queries::evaluate_obligation<'tcx> { } } +impl<'tcx> QueryDescription<'tcx> for queries::type_op_eq<'tcx> { + fn describe(_tcx: TyCtxt, goal: CanonicalTypeOpEqGoal<'tcx>) -> String { + format!("evaluating `type_op_eq` `{:?}`", goal) + } +} + +impl<'tcx> QueryDescription<'tcx> for queries::type_op_subtype<'tcx> { + fn describe(_tcx: TyCtxt, goal: CanonicalTypeOpSubtypeGoal<'tcx>) -> String { + format!("evaluating `type_op_subtype` `{:?}`", goal) + } +} + +impl<'tcx> QueryDescription<'tcx> for queries::type_op_prove_predicate<'tcx> { + fn describe(_tcx: TyCtxt, goal: CanonicalTypeOpProvePredicateGoal<'tcx>) -> String { + format!("evaluating `type_op_prove_predicate` `{:?}`", goal) + } +} + +impl<'tcx> QueryDescription<'tcx> for queries::type_op_normalize_ty<'tcx> { + fn describe(_tcx: TyCtxt, goal: CanonicalTypeOpNormalizeGoal<'tcx, Ty<'tcx>>) -> String { + format!("normalizing `{:?}`", goal) + } +} + +impl<'tcx> QueryDescription<'tcx> for queries::type_op_normalize_predicate<'tcx> { + fn describe( + _tcx: TyCtxt, + goal: CanonicalTypeOpNormalizeGoal<'tcx, ty::Predicate<'tcx>>, + ) -> String { + format!("normalizing `{:?}`", goal) + } +} + +impl<'tcx> QueryDescription<'tcx> for queries::type_op_normalize_poly_fn_sig<'tcx> { + fn describe( + _tcx: TyCtxt, + goal: CanonicalTypeOpNormalizeGoal<'tcx, ty::PolyFnSig<'tcx>>, + ) -> String { + format!("normalizing `{:?}`", goal) + } +} + +impl<'tcx> QueryDescription<'tcx> for queries::type_op_normalize_fn_sig<'tcx> { + fn describe(_tcx: TyCtxt, goal: CanonicalTypeOpNormalizeGoal<'tcx, ty::FnSig<'tcx>>) -> String { + format!("normalizing `{:?}`", goal) + } +} + impl<'tcx> QueryDescription<'tcx> for queries::is_copy_raw<'tcx> { fn describe(_tcx: TyCtxt, env: ty::ParamEnvAnd<'tcx, Ty<'tcx>>) -> String { format!("computing whether `{}` is `Copy`", env.value) diff --git a/src/librustc/ty/query/keys.rs b/src/librustc/ty/query/keys.rs index 279d5ebb990..cad3a658682 100644 --- a/src/librustc/ty/query/keys.rs +++ b/src/librustc/ty/query/keys.rs @@ -10,8 +10,8 @@ //! Defines the set of legal keys that can be used in queries. +use infer::canonical::Canonical; use hir::def_id::{CrateNum, DefId, LOCAL_CRATE, DefIndex}; -use traits::query::{CanonicalPredicateGoal, CanonicalProjectionGoal, CanonicalTyGoal}; use ty::{self, Ty, TyCtxt}; use ty::subst::Substs; use ty::fast_reject::SimplifiedType; @@ -190,27 +190,12 @@ impl Key for InternedString { } } -impl<'tcx> Key for CanonicalProjectionGoal<'tcx> { - fn query_crate(&self) -> CrateNum { - LOCAL_CRATE - } - - fn default_span(&self, _tcx: TyCtxt) -> Span { - DUMMY_SP - } -} - -impl<'tcx> Key for CanonicalTyGoal<'tcx> { - fn query_crate(&self) -> CrateNum { - LOCAL_CRATE - } - - fn default_span(&self, _tcx: TyCtxt) -> Span { - DUMMY_SP - } -} - -impl<'tcx> Key for CanonicalPredicateGoal<'tcx> { +/// Canonical query goals correspond to abstract trait operations that +/// are not tied to any crate in particular. +impl<'tcx, T> Key for Canonical<'tcx, T> +where + T: Debug + Hash + Clone + Eq, +{ fn query_crate(&self) -> CrateNum { LOCAL_CRATE } diff --git a/src/librustc/ty/query/mod.rs b/src/librustc/ty/query/mod.rs index f19bc01e198..178ee7cf8e9 100644 --- a/src/librustc/ty/query/mod.rs +++ b/src/librustc/ty/query/mod.rs @@ -34,7 +34,8 @@ use session::{CompileResult, CrateDisambiguator}; use session::config::OutputFilenames; use traits::{self, Vtable}; use traits::query::{CanonicalPredicateGoal, CanonicalProjectionGoal, - CanonicalTyGoal, NoSolution}; + CanonicalTyGoal, CanonicalTypeOpEqGoal, CanonicalTypeOpSubtypeGoal, + CanonicalTypeOpProvePredicateGoal, CanonicalTypeOpNormalizeGoal, NoSolution}; use traits::query::dropck_outlives::{DtorckConstraint, DropckOutlivesResult}; use traits::query::normalize::NormalizationResult; use traits::specialization_graph; @@ -446,6 +447,62 @@ define_queries! { <'tcx> CanonicalPredicateGoal<'tcx> ) -> Result<traits::EvaluationResult, traits::OverflowError>, + /// Do not call this query directly: part of the `Eq` type-op + [] fn type_op_eq: TypeOpEq( + CanonicalTypeOpEqGoal<'tcx> + ) -> Result< + Lrc<Canonical<'tcx, canonical::QueryResult<'tcx, ()>>>, + NoSolution, + >, + + /// Do not call this query directly: part of the `Subtype` type-op + [] fn type_op_subtype: TypeOpSubtype( + CanonicalTypeOpSubtypeGoal<'tcx> + ) -> Result< + Lrc<Canonical<'tcx, canonical::QueryResult<'tcx, ()>>>, + NoSolution, + >, + + /// Do not call this query directly: part of the `ProvePredicate` type-op + [] fn type_op_prove_predicate: TypeOpProvePredicate( + CanonicalTypeOpProvePredicateGoal<'tcx> + ) -> Result< + Lrc<Canonical<'tcx, canonical::QueryResult<'tcx, ()>>>, + NoSolution, + >, + + /// Do not call this query directly: part of the `Normalize` type-op + [] fn type_op_normalize_ty: TypeOpNormalizeTy( + CanonicalTypeOpNormalizeGoal<'tcx, Ty<'tcx>> + ) -> Result< + Lrc<Canonical<'tcx, canonical::QueryResult<'tcx, Ty<'tcx>>>>, + NoSolution, + >, + + /// Do not call this query directly: part of the `Normalize` type-op + [] fn type_op_normalize_predicate: TypeOpNormalizePredicate( + CanonicalTypeOpNormalizeGoal<'tcx, ty::Predicate<'tcx>> + ) -> Result< + Lrc<Canonical<'tcx, canonical::QueryResult<'tcx, ty::Predicate<'tcx>>>>, + NoSolution, + >, + + /// Do not call this query directly: part of the `Normalize` type-op + [] fn type_op_normalize_poly_fn_sig: TypeOpNormalizePolyFnSig( + CanonicalTypeOpNormalizeGoal<'tcx, ty::PolyFnSig<'tcx>> + ) -> Result< + Lrc<Canonical<'tcx, canonical::QueryResult<'tcx, ty::PolyFnSig<'tcx>>>>, + NoSolution, + >, + + /// Do not call this query directly: part of the `Normalize` type-op + [] fn type_op_normalize_fn_sig: TypeOpNormalizeFnSig( + CanonicalTypeOpNormalizeGoal<'tcx, ty::FnSig<'tcx>> + ) -> Result< + Lrc<Canonical<'tcx, canonical::QueryResult<'tcx, ty::FnSig<'tcx>>>>, + NoSolution, + >, + [] fn substitute_normalize_and_test_predicates: substitute_normalize_and_test_predicates_node((DefId, &'tcx Substs<'tcx>)) -> bool, diff --git a/src/librustc/ty/query/plumbing.rs b/src/librustc/ty/query/plumbing.rs index 4679c265d58..e17c6fba74c 100644 --- a/src/librustc/ty/query/plumbing.rs +++ b/src/librustc/ty/query/plumbing.rs @@ -1028,6 +1028,13 @@ pub fn force_from_dep_node<'a, 'gcx, 'lcx>(tcx: TyCtxt<'a, 'gcx, 'lcx>, DepKind::NormalizeTyAfterErasingRegions | DepKind::DropckOutlives | DepKind::EvaluateObligation | + DepKind::TypeOpEq | + DepKind::TypeOpSubtype | + DepKind::TypeOpProvePredicate | + DepKind::TypeOpNormalizeTy | + DepKind::TypeOpNormalizePredicate | + DepKind::TypeOpNormalizePolyFnSig | + DepKind::TypeOpNormalizeFnSig | DepKind::SubstituteNormalizeAndTestPredicates | DepKind::InstanceDefSizeEstimate | DepKind::ProgramClausesForEnv | diff --git a/src/librustc_mir/borrow_check/mod.rs b/src/librustc_mir/borrow_check/mod.rs index ca0c259fb67..7b7568cfcfc 100644 --- a/src/librustc_mir/borrow_check/mod.rs +++ b/src/librustc_mir/borrow_check/mod.rs @@ -275,6 +275,7 @@ fn do_mir_borrowck<'a, 'gcx, 'tcx>( mir_def_id: def_id, move_data: &mdpe.move_data, param_env: param_env, + location_table, movable_generator, locals_are_invalidated_at_exit: match tcx.hir.body_owner_kind(id) { hir::BodyOwnerKind::Const | hir::BodyOwnerKind::Static(_) => false, @@ -362,6 +363,11 @@ pub struct MirBorrowckCtxt<'cx, 'gcx: 'tcx, 'tcx: 'cx> { mir: &'cx Mir<'tcx>, mir_def_id: DefId, move_data: &'cx MoveData<'tcx>, + + /// Map from MIR `Location` to `LocationIndex`; created + /// when MIR borrowck begins. + location_table: &'cx LocationTable, + param_env: ParamEnv<'gcx>, movable_generator: bool, /// This keeps track of whether local variables are free-ed when the function @@ -976,8 +982,7 @@ impl<'cx, 'gcx, 'tcx> MirBorrowckCtxt<'cx, 'gcx, 'tcx> { let mut error_reported = false; let tcx = self.tcx; let mir = self.mir; - let location_table = &LocationTable::new(mir); - let location = location_table.start_index(context.loc); + let location = self.location_table.start_index(context.loc); let borrow_set = self.borrow_set.clone(); each_borrow_involving_path( self, diff --git a/src/librustc_mir/borrow_check/nll/facts.rs b/src/librustc_mir/borrow_check/nll/facts.rs index 6cb8e64b9f5..2523711f936 100644 --- a/src/librustc_mir/borrow_check/nll/facts.rs +++ b/src/librustc_mir/borrow_check/nll/facts.rs @@ -12,7 +12,7 @@ use borrow_check::location::{LocationIndex, LocationTable}; use dataflow::indexes::BorrowIndex; use polonius_engine::AllFacts as PoloniusAllFacts; use polonius_engine::Atom; -use rustc::ty::RegionVid; +use rustc::ty::{RegionVid, TyCtxt}; use rustc_data_structures::indexed_vec::Idx; use std::error::Error; use std::fmt::Debug; @@ -23,6 +23,10 @@ use std::path::Path; crate type AllFacts = PoloniusAllFacts<RegionVid, BorrowIndex, LocationIndex>; crate trait AllFactsExt { + /// Returns true if there is a need to gather `AllFacts` given the + /// current `-Z` flags. + fn enabled(tcx: TyCtxt<'_, '_, '_>) -> bool; + fn write_to_dir( &self, dir: impl AsRef<Path>, @@ -31,6 +35,12 @@ crate trait AllFactsExt { } impl AllFactsExt for AllFacts { + /// Return + fn enabled(tcx: TyCtxt<'_, '_, '_>) -> bool { + tcx.sess.opts.debugging_opts.nll_facts + || tcx.sess.opts.debugging_opts.polonius + } + fn write_to_dir( &self, dir: impl AsRef<Path>, diff --git a/src/librustc_mir/borrow_check/nll/mod.rs b/src/librustc_mir/borrow_check/nll/mod.rs index dcb52a3b18a..e26665e8291 100644 --- a/src/librustc_mir/borrow_check/nll/mod.rs +++ b/src/librustc_mir/borrow_check/nll/mod.rs @@ -91,9 +91,7 @@ pub(in borrow_check) fn compute_regions<'cx, 'gcx, 'tcx>( Option<Rc<Output<RegionVid, BorrowIndex, LocationIndex>>>, Option<ClosureRegionRequirements<'gcx>>, ) { - let mut all_facts = if infcx.tcx.sess.opts.debugging_opts.nll_facts - || infcx.tcx.sess.opts.debugging_opts.polonius - { + let mut all_facts = if AllFacts::enabled(infcx.tcx) { Some(AllFacts::default()) } else { None diff --git a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs index 0eeacda467e..2e1f7fc9e70 100644 --- a/src/librustc_mir/borrow_check/nll/region_infer/mod.rs +++ b/src/librustc_mir/borrow_check/nll/region_infer/mod.rs @@ -11,25 +11,22 @@ use super::universal_regions::UniversalRegions; use borrow_check::nll::region_infer::values::ToElementIndex; use rustc::hir::def_id::DefId; +use rustc::infer::canonical::QueryRegionConstraint; use rustc::infer::error_reporting::nice_region_error::NiceRegionError; use rustc::infer::region_constraints::{GenericKind, VarInfos}; use rustc::infer::InferCtxt; use rustc::infer::NLLRegionVariableOrigin; -use rustc::infer::RegionObligation; use rustc::infer::RegionVariableOrigin; -use rustc::infer::SubregionOrigin; use rustc::mir::{ ClosureOutlivesRequirement, ClosureOutlivesSubject, ClosureRegionRequirements, Local, Location, Mir, }; -use rustc::traits::ObligationCause; -use rustc::ty::{self, RegionVid, Ty, TypeFoldable}; +use rustc::ty::{self, RegionVid, Ty, TyCtxt, TypeFoldable}; use rustc::util::common::{self, ErrorReported}; use rustc_data_structures::bitvec::BitVector; use rustc_data_structures::indexed_vec::{Idx, IndexVec}; use std::fmt; use std::rc::Rc; -use syntax::ast; use syntax_pos::Span; mod annotation; @@ -1162,16 +1159,15 @@ impl fmt::Debug for OutlivesConstraint { pub trait ClosureRegionRequirementsExt<'gcx, 'tcx> { fn apply_requirements( &self, - infcx: &InferCtxt<'_, 'gcx, 'tcx>, - body_id: ast::NodeId, + tcx: TyCtxt<'_, 'gcx, 'tcx>, location: Location, closure_def_id: DefId, closure_substs: ty::ClosureSubsts<'tcx>, - ); + ) -> Vec<QueryRegionConstraint<'tcx>>; fn subst_closure_mapping<T>( &self, - infcx: &InferCtxt<'_, 'gcx, 'tcx>, + tcx: TyCtxt<'_, 'gcx, 'tcx>, closure_mapping: &IndexVec<RegionVid, ty::Region<'tcx>>, value: &T, ) -> T @@ -1194,14 +1190,11 @@ impl<'gcx, 'tcx> ClosureRegionRequirementsExt<'gcx, 'tcx> for ClosureRegionRequi /// requirements. fn apply_requirements( &self, - infcx: &InferCtxt<'_, 'gcx, 'tcx>, - body_id: ast::NodeId, + tcx: TyCtxt<'_, 'gcx, 'tcx>, location: Location, closure_def_id: DefId, closure_substs: ty::ClosureSubsts<'tcx>, - ) { - let tcx = infcx.tcx; - + ) -> Vec<QueryRegionConstraint<'tcx>> { debug!( "apply_requirements(location={:?}, closure_def_id={:?}, closure_substs={:?})", location, closure_def_id, closure_substs @@ -1215,59 +1208,52 @@ impl<'gcx, 'tcx> ClosureRegionRequirementsExt<'gcx, 'tcx> for ClosureRegionRequi // into a vector. These are the regions that we will be // relating to one another. let closure_mapping = - &UniversalRegions::closure_mapping(infcx, user_closure_ty, self.num_external_vids); + &UniversalRegions::closure_mapping(tcx, user_closure_ty, self.num_external_vids); debug!("apply_requirements: closure_mapping={:?}", closure_mapping); // Create the predicates. - for outlives_requirement in &self.outlives_requirements { - let outlived_region = closure_mapping[outlives_requirement.outlived_free_region]; - - // FIXME, this origin is not entirely suitable. - let origin = SubregionOrigin::CallRcvr(outlives_requirement.blame_span); - - match outlives_requirement.subject { - ClosureOutlivesSubject::Region(region) => { - let region = closure_mapping[region]; - debug!( - "apply_requirements: region={:?} \ - outlived_region={:?} \ - outlives_requirement={:?}", - region, outlived_region, outlives_requirement, - ); - infcx.sub_regions(origin, outlived_region, region); - } + self.outlives_requirements + .iter() + .map(|outlives_requirement| { + let outlived_region = closure_mapping[outlives_requirement.outlived_free_region]; + + match outlives_requirement.subject { + ClosureOutlivesSubject::Region(region) => { + let region = closure_mapping[region]; + debug!( + "apply_requirements: region={:?} \ + outlived_region={:?} \ + outlives_requirement={:?}", + region, outlived_region, outlives_requirement, + ); + ty::Binder::dummy(ty::OutlivesPredicate(region.into(), outlived_region)) + } - ClosureOutlivesSubject::Ty(ty) => { - let ty = self.subst_closure_mapping(infcx, closure_mapping, &ty); - debug!( - "apply_requirements: ty={:?} \ - outlived_region={:?} \ - outlives_requirement={:?}", - ty, outlived_region, outlives_requirement, - ); - infcx.register_region_obligation( - body_id, - RegionObligation { - sup_type: ty, - sub_region: outlived_region, - cause: ObligationCause::misc(outlives_requirement.blame_span, body_id), - }, - ); + ClosureOutlivesSubject::Ty(ty) => { + let ty = self.subst_closure_mapping(tcx, closure_mapping, &ty); + debug!( + "apply_requirements: ty={:?} \ + outlived_region={:?} \ + outlives_requirement={:?}", + ty, outlived_region, outlives_requirement, + ); + ty::Binder::dummy(ty::OutlivesPredicate(ty.into(), outlived_region)) + } } - } - } + }) + .collect() } fn subst_closure_mapping<T>( &self, - infcx: &InferCtxt<'_, 'gcx, 'tcx>, + tcx: TyCtxt<'_, 'gcx, 'tcx>, closure_mapping: &IndexVec<RegionVid, ty::Region<'tcx>>, value: &T, ) -> T where T: TypeFoldable<'tcx>, { - infcx.tcx.fold_regions(value, &mut false, |r, _depth| { + tcx.fold_regions(value, &mut false, |r, _depth| { if let ty::ReClosureBound(vid) = r { closure_mapping[*vid] } else { diff --git a/src/librustc_mir/borrow_check/nll/type_check/constraint_conversion.rs b/src/librustc_mir/borrow_check/nll/type_check/constraint_conversion.rs index 06aaf6810fa..900899b9cde 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/constraint_conversion.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/constraint_conversion.rs @@ -13,127 +13,146 @@ use borrow_check::nll::facts::AllFacts; use borrow_check::nll::region_infer::{OutlivesConstraint, RegionTest, TypeTest}; use borrow_check::nll::type_check::Locations; use borrow_check::nll::universal_regions::UniversalRegions; -use rustc::infer::region_constraints::Constraint; -use rustc::infer::region_constraints::RegionConstraintData; -use rustc::infer::region_constraints::{Verify, VerifyBound}; +use rustc::infer::canonical::QueryRegionConstraint; +use rustc::infer::outlives::obligations::{TypeOutlives, TypeOutlivesDelegate}; +use rustc::infer::region_constraints::{GenericKind, VerifyBound}; +use rustc::infer::{self, SubregionOrigin}; use rustc::mir::{Location, Mir}; -use rustc::ty; +use rustc::ty::subst::UnpackedKind; +use rustc::ty::{self, TyCtxt}; use syntax::codemap::Span; -crate struct ConstraintConversion<'a, 'tcx: 'a> { +crate struct ConstraintConversion<'a, 'gcx: 'tcx, 'tcx: 'a> { + tcx: TyCtxt<'a, 'gcx, 'tcx>, mir: &'a Mir<'tcx>, universal_regions: &'a UniversalRegions<'tcx>, location_table: &'a LocationTable, + region_bound_pairs: &'a [(ty::Region<'tcx>, GenericKind<'tcx>)], + implicit_region_bound: Option<ty::Region<'tcx>>, + param_env: ty::ParamEnv<'tcx>, + locations: Locations, outlives_constraints: &'a mut Vec<OutlivesConstraint>, type_tests: &'a mut Vec<TypeTest<'tcx>>, all_facts: &'a mut Option<AllFacts>, - } -impl<'a, 'tcx> ConstraintConversion<'a, 'tcx> { +impl<'a, 'gcx, 'tcx> ConstraintConversion<'a, 'gcx, 'tcx> { crate fn new( + tcx: TyCtxt<'a, 'gcx, 'tcx>, mir: &'a Mir<'tcx>, universal_regions: &'a UniversalRegions<'tcx>, location_table: &'a LocationTable, + region_bound_pairs: &'a [(ty::Region<'tcx>, GenericKind<'tcx>)], + implicit_region_bound: Option<ty::Region<'tcx>>, + param_env: ty::ParamEnv<'tcx>, + locations: Locations, outlives_constraints: &'a mut Vec<OutlivesConstraint>, type_tests: &'a mut Vec<TypeTest<'tcx>>, all_facts: &'a mut Option<AllFacts>, ) -> Self { Self { + tcx, mir, universal_regions, location_table, + region_bound_pairs, + implicit_region_bound, + param_env, + locations, outlives_constraints, type_tests, all_facts, } } - crate fn convert( - &mut self, - locations: Locations, - data: &RegionConstraintData<'tcx>, - ) { - debug!("generate: constraints at: {:#?}", locations); - let RegionConstraintData { - constraints, - verifys, - givens, - } = data; - - let span = self - .mir - .source_info(locations.from_location().unwrap_or(Location::START)) - .span; - - let at_location = locations.at_location().unwrap_or(Location::START); - - for constraint in constraints.keys() { - debug!("generate: constraint: {:?}", constraint); - let (a_vid, b_vid) = match constraint { - Constraint::VarSubVar(a_vid, b_vid) => (*a_vid, *b_vid), - Constraint::RegSubVar(a_r, b_vid) => (self.to_region_vid(a_r), *b_vid), - Constraint::VarSubReg(a_vid, b_r) => (*a_vid, self.to_region_vid(b_r)), - Constraint::RegSubReg(a_r, b_r) => { - (self.to_region_vid(a_r), self.to_region_vid(b_r)) - } - }; - - // We have the constraint that `a_vid <= b_vid`. Add - // `b_vid: a_vid` to our region checker. Note that we - // reverse direction, because `regioncx` talks about - // "outlives" (`>=`) whereas the region constraints - // talk about `<=`. - self.add_outlives(span, b_vid, a_vid, at_location); - - // In the new analysis, all outlives relations etc - // "take effect" at the mid point of the statement - // that requires them, so ignore the `at_location`. - if let Some(all_facts) = &mut self.all_facts { - if let Some(from_location) = locations.from_location() { - all_facts.outlives.push(( - b_vid, - a_vid, - self.location_table.mid_index(from_location), - )); - } else { - for location in self.location_table.all_points() { - all_facts.outlives.push((b_vid, a_vid, location)); + pub(super) fn convert_all(&mut self, query_constraints: &[QueryRegionConstraint<'tcx>]) { + for query_constraint in query_constraints { + self.convert(query_constraint); + } + } + + pub(super) fn convert(&mut self, query_constraint: &QueryRegionConstraint<'tcx>) { + debug!("generate: constraints at: {:#?}", self.locations); + + // Extract out various useful fields we'll need below. + let ConstraintConversion { + tcx, + region_bound_pairs, + implicit_region_bound, + param_env, + .. + } = *self; + + // At the moment, we never generate any "higher-ranked" + // region constraints like `for<'a> 'a: 'b`. At some point + // when we move to universes, we will, and this assertion + // will start to fail. + let ty::OutlivesPredicate(k1, r2) = + query_constraint.no_late_bound_regions().unwrap_or_else(|| { + span_bug!( + self.span(), + "query_constraint {:?} contained bound regions", + query_constraint, + ); + }); + + match k1.unpack() { + UnpackedKind::Lifetime(r1) => { + let r1_vid = self.to_region_vid(r1); + let r2_vid = self.to_region_vid(r2); + self.add_outlives(r1_vid, r2_vid); + + // In the new analysis, all outlives relations etc + // "take effect" at the mid point of the statement + // that requires them, so ignore the `at_location`. + if let Some(all_facts) = &mut self.all_facts { + if let Some(from_location) = self.locations.from_location() { + all_facts.outlives.push(( + r1_vid, + r2_vid, + self.location_table.mid_index(from_location), + )); + } else { + for location in self.location_table.all_points() { + all_facts.outlives.push((r1_vid, r2_vid, location)); + } } } } - } - for verify in verifys { - let type_test = self.verify_to_type_test(verify, span, locations); - self.add_type_test(type_test); + UnpackedKind::Type(t1) => { + // we don't actually use this for anything, but + // the `TypeOutlives` code needs an origin. + let origin = infer::RelateParamBound(self.span(), t1); + + TypeOutlives::new( + &mut *self, + tcx, + region_bound_pairs, + implicit_region_bound, + param_env, + ).type_must_outlive(origin, t1, r2); + } } - - assert!( - givens.is_empty(), - "MIR type-checker does not use givens (thank goodness)" - ); } fn verify_to_type_test( &self, - verify: &Verify<'tcx>, - span: Span, - locations: Locations, + generic_kind: GenericKind<'tcx>, + region: ty::Region<'tcx>, + bound: VerifyBound<'tcx>, ) -> TypeTest<'tcx> { - let generic_kind = verify.kind; - - let lower_bound = self.to_region_vid(verify.region); + let lower_bound = self.to_region_vid(region); - let point = locations.at_location().unwrap_or(Location::START); + let point = self.locations.at_location().unwrap_or(Location::START); - let test = self.verify_bound_to_region_test(&verify.bound); + let test = self.verify_bound_to_region_test(&bound); TypeTest { generic_kind, lower_bound, point, - span, + span: self.span(), test, } } @@ -168,13 +187,16 @@ impl<'a, 'tcx> ConstraintConversion<'a, 'tcx> { self.universal_regions.to_region_vid(r) } - fn add_outlives( - &mut self, - span: Span, - sup: ty::RegionVid, - sub: ty::RegionVid, - point: Location, - ) { + fn span(&self) -> Span { + self.mir + .source_info(self.locations.from_location().unwrap_or(Location::START)) + .span + } + + fn add_outlives(&mut self, sup: ty::RegionVid, sub: ty::RegionVid) { + let span = self.span(); + let point = self.locations.at_location().unwrap_or(Location::START); + self.outlives_constraints.push(OutlivesConstraint { span, sub, @@ -188,3 +210,29 @@ impl<'a, 'tcx> ConstraintConversion<'a, 'tcx> { self.type_tests.push(type_test); } } + +impl<'a, 'b, 'gcx, 'tcx> TypeOutlivesDelegate<'tcx> + for &'a mut ConstraintConversion<'b, 'gcx, 'tcx> +{ + fn push_sub_region_constraint( + &mut self, + _origin: SubregionOrigin<'tcx>, + a: ty::Region<'tcx>, + b: ty::Region<'tcx>, + ) { + let b = self.universal_regions.to_region_vid(b); + let a = self.universal_regions.to_region_vid(a); + self.add_outlives(b, a); + } + + fn push_verify( + &mut self, + _origin: SubregionOrigin<'tcx>, + kind: GenericKind<'tcx>, + a: ty::Region<'tcx>, + bound: VerifyBound<'tcx>, + ) { + let type_test = self.verify_to_type_test(kind, a, bound); + self.add_type_test(type_test); + } +} diff --git a/src/librustc_mir/borrow_check/nll/type_check/input_output.rs b/src/librustc_mir/borrow_check/nll/type_check/input_output.rs index d44eed65201..770a0614811 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/input_output.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/input_output.rs @@ -23,6 +23,7 @@ use rustc::hir::def_id::DefId; use rustc::infer::InferOk; use rustc::mir::visit::TyContext; use rustc::mir::*; +use rustc::traits::query::type_op::custom::CustomTypeOp; use rustc::traits::{ObligationCause, PredicateObligations}; use rustc::ty::subst::Subst; use rustc::ty::Ty; @@ -50,7 +51,7 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { // Equate expected input tys with those in the MIR. let argument_locals = (1..).map(Local::new); for (&unnormalized_input_ty, local) in unnormalized_input_tys.iter().zip(argument_locals) { - let input_ty = self.normalize(&unnormalized_input_ty, Locations::All); + let input_ty = self.normalize(unnormalized_input_ty, Locations::All); let mir_input_ty = mir.local_decls[local].ty; self.equate_normalized_input_or_output(input_ty, mir_input_ty); } @@ -70,72 +71,76 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { "equate_inputs_and_outputs: unnormalized_output_ty={:?}", unnormalized_output_ty ); - let output_ty = self.normalize(&unnormalized_output_ty, Locations::All); + let output_ty = self.normalize(unnormalized_output_ty, Locations::All); debug!( "equate_inputs_and_outputs: normalized output_ty={:?}", output_ty ); + let param_env = self.param_env; let mir_output_ty = mir.local_decls[RETURN_PLACE].ty; let anon_type_map = self.fully_perform_op( Locations::All, - || format!("input_output"), - |cx| { - let mut obligations = ObligationAccumulator::default(); - - let dummy_body_id = ObligationCause::dummy().body_id; - let (output_ty, anon_type_map) = obligations.add(infcx.instantiate_anon_types( - mir_def_id, - dummy_body_id, - cx.param_env, - &output_ty, - )); - debug!( - "equate_inputs_and_outputs: instantiated output_ty={:?}", - output_ty - ); - debug!( - "equate_inputs_and_outputs: anon_type_map={:#?}", - anon_type_map - ); - - debug!( - "equate_inputs_and_outputs: mir_output_ty={:?}", - mir_output_ty - ); - obligations.add( - infcx - .at(&ObligationCause::dummy(), cx.param_env) - .eq(output_ty, mir_output_ty)?, - ); - - for (&anon_def_id, anon_decl) in &anon_type_map { - let anon_defn_ty = tcx.type_of(anon_def_id); - let anon_defn_ty = anon_defn_ty.subst(tcx, anon_decl.substs); - let anon_defn_ty = renumber::renumber_regions( - cx.infcx, - TyContext::Location(Location::START), - &anon_defn_ty, + CustomTypeOp::new( + |infcx| { + let mut obligations = ObligationAccumulator::default(); + + let dummy_body_id = ObligationCause::dummy().body_id; + let (output_ty, anon_type_map) = + obligations.add(infcx.instantiate_anon_types( + mir_def_id, + dummy_body_id, + param_env, + &output_ty, + )); + debug!( + "equate_inputs_and_outputs: instantiated output_ty={:?}", + output_ty ); debug!( - "equate_inputs_and_outputs: concrete_ty={:?}", - anon_decl.concrete_ty + "equate_inputs_and_outputs: anon_type_map={:#?}", + anon_type_map + ); + + debug!( + "equate_inputs_and_outputs: mir_output_ty={:?}", + mir_output_ty ); - debug!("equate_inputs_and_outputs: anon_defn_ty={:?}", anon_defn_ty); obligations.add( infcx - .at(&ObligationCause::dummy(), cx.param_env) - .eq(anon_decl.concrete_ty, anon_defn_ty)?, + .at(&ObligationCause::dummy(), param_env) + .eq(output_ty, mir_output_ty)?, ); - } - - debug!("equate_inputs_and_outputs: equated"); - Ok(InferOk { - value: Some(anon_type_map), - obligations: obligations.into_vec(), - }) - }, + for (&anon_def_id, anon_decl) in &anon_type_map { + let anon_defn_ty = tcx.type_of(anon_def_id); + let anon_defn_ty = anon_defn_ty.subst(tcx, anon_decl.substs); + let anon_defn_ty = renumber::renumber_regions( + infcx, + TyContext::Location(Location::START), + &anon_defn_ty, + ); + debug!( + "equate_inputs_and_outputs: concrete_ty={:?}", + anon_decl.concrete_ty + ); + debug!("equate_inputs_and_outputs: anon_defn_ty={:?}", anon_defn_ty); + obligations.add( + infcx + .at(&ObligationCause::dummy(), param_env) + .eq(anon_decl.concrete_ty, anon_defn_ty)?, + ); + } + + debug!("equate_inputs_and_outputs: equated"); + + Ok(InferOk { + value: Some(anon_type_map), + obligations: obligations.into_vec(), + }) + }, + || format!("input_output"), + ), ).unwrap_or_else(|terr| { span_mirbug!( self, @@ -155,14 +160,16 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { if let Some(anon_type_map) = anon_type_map { self.fully_perform_op( Locations::All, - || format!("anon_type_map"), - |_cx| { - infcx.constrain_anon_types(&anon_type_map, universal_regions); - Ok(InferOk { - value: (), - obligations: vec![], - }) - }, + CustomTypeOp::new( + |_cx| { + infcx.constrain_anon_types(&anon_type_map, universal_regions); + Ok(InferOk { + value: (), + obligations: vec![], + }) + }, + || format!("anon_type_map"), + ), ).unwrap(); } } diff --git a/src/librustc_mir/borrow_check/nll/type_check/liveness.rs b/src/librustc_mir/borrow_check/nll/type_check/liveness.rs index 80f5fe4184f..f27de92c621 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/liveness.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/liveness.rs @@ -13,11 +13,12 @@ use borrow_check::nll::type_check::AtLocation; use dataflow::move_paths::{HasMoveData, MoveData}; use dataflow::MaybeInitializedPlaces; use dataflow::{FlowAtLocation, FlowsAtLocation}; -use rustc::infer::region_constraints::RegionConstraintData; +use rustc::infer::canonical::QueryRegionConstraint; use rustc::mir::Local; use rustc::mir::{BasicBlock, Location, Mir}; -use rustc::traits::ObligationCause; -use rustc::ty::subst::Kind; +use rustc::traits::query::dropck_outlives::DropckOutlivesResult; +use rustc::traits::query::type_op::outlives::DropckOutlives; +use rustc::traits::query::type_op::TypeOp; use rustc::ty::{Ty, TypeFoldable}; use rustc_data_structures::fx::FxHashMap; use std::rc::Rc; @@ -70,8 +71,8 @@ where } struct DropData<'tcx> { - dropped_kinds: Vec<Kind<'tcx>>, - region_constraint_data: Option<Rc<RegionConstraintData<'tcx>>>, + dropck_result: DropckOutlivesResult<'tcx>, + region_constraint_data: Option<Rc<Vec<QueryRegionConstraint<'tcx>>>>, } impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flow, 'gcx, 'tcx> { @@ -170,8 +171,7 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo ); cx.tcx().for_each_free_region(&value, |live_region| { - cx - .constraints + cx.constraints .liveness_set .push((live_region, location, cause.clone())); }); @@ -199,14 +199,19 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo }); if let Some(data) = &drop_data.region_constraint_data { - self.cx - .push_region_constraints(location.at_self(), data.clone()); + self.cx.push_region_constraints(location.at_self(), data); } + drop_data.dropck_result.report_overflows( + self.cx.infcx.tcx, + self.mir.source_info(location).span, + dropped_ty, + ); + // All things in the `outlives` array may be touched by // the destructor and must be live at this point. let cause = Cause::DropVar(dropped_local, location); - for &kind in &drop_data.dropped_kinds { + for &kind in &drop_data.dropck_result.kinds { Self::push_type_live_constraint(&mut self.cx, kind, location, cause); } } @@ -217,19 +222,14 @@ impl<'gen, 'typeck, 'flow, 'gcx, 'tcx> TypeLivenessGenerator<'gen, 'typeck, 'flo ) -> DropData<'tcx> { debug!("compute_drop_data(dropped_ty={:?})", dropped_ty,); - let (dropped_kinds, region_constraint_data) = - cx.fully_perform_op_and_get_region_constraint_data( - || format!("compute_drop_data(dropped_ty={:?})", dropped_ty), - |cx| { - Ok(cx - .infcx - .at(&ObligationCause::dummy(), cx.param_env) - .dropck_outlives(dropped_ty)) - }, - ).unwrap(); + let param_env = cx.param_env; + let (dropck_result, region_constraint_data) = param_env + .and(DropckOutlives::new(dropped_ty)) + .fully_perform(cx.infcx) + .unwrap(); DropData { - dropped_kinds, + dropck_result, region_constraint_data, } } diff --git a/src/librustc_mir/borrow_check/nll/type_check/mod.rs b/src/librustc_mir/borrow_check/nll/type_check/mod.rs index 0e5597b036b..2da2b10edb8 100644 --- a/src/librustc_mir/borrow_check/nll/type_check/mod.rs +++ b/src/librustc_mir/borrow_check/nll/type_check/mod.rs @@ -20,19 +20,18 @@ use dataflow::move_paths::MoveData; use dataflow::FlowAtLocation; use dataflow::MaybeInitializedPlaces; use rustc::hir::def_id::DefId; -use rustc::infer::region_constraints::{GenericKind, RegionConstraintData}; -use rustc::infer::{InferCtxt, InferOk, InferResult, LateBoundRegionConversionTime, UnitResult}; +use rustc::infer::canonical::QueryRegionConstraint; +use rustc::infer::region_constraints::GenericKind; +use rustc::infer::{InferCtxt, LateBoundRegionConversionTime}; use rustc::mir::interpret::EvalErrorKind::BoundsCheck; use rustc::mir::tcx::PlaceTy; use rustc::mir::visit::{PlaceContext, Visitor}; use rustc::mir::*; -use rustc::traits::query::NoSolution; -use rustc::traits::{self, ObligationCause, Normalized, TraitEngine}; -use rustc::ty::error::TypeError; +use rustc::traits::query::type_op; +use rustc::traits::query::{Fallible, NoSolution}; use rustc::ty::fold::TypeFoldable; use rustc::ty::{self, ToPolyTraitRef, Ty, TyCtxt, TypeVariants}; use std::fmt; -use std::rc::Rc; use syntax_pos::{Span, DUMMY_SP}; use transform::{MirPass, MirSource}; use util::liveness::LivenessResults; @@ -286,9 +285,10 @@ impl<'a, 'b, 'gcx, 'tcx> TypeVerifier<'a, 'b, 'gcx, 'tcx> { let instantiated_predicates = tcx.predicates_of(def_id).instantiate(tcx, substs); - let predicates = - type_checker.normalize(&instantiated_predicates.predicates, location); - type_checker.prove_predicates(predicates, location); + type_checker.normalize_and_prove_instantiated_predicates( + instantiated_predicates, + location, + ); } value.ty @@ -344,7 +344,7 @@ impl<'a, 'b, 'gcx, 'tcx> TypeVerifier<'a, 'b, 'gcx, 'tcx> { Place::Static(box Static { def_id, ty: sty }) => { let sty = self.sanitize_type(place, sty); let ty = self.tcx().type_of(def_id); - let ty = self.cx.normalize(&ty, location); + let ty = self.cx.normalize(ty, location); if let Err(terr) = self.cx.eq_types(ty, sty, location.at_self()) { span_mirbug!( self, @@ -731,15 +731,11 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { fn fully_perform_op<R>( &mut self, locations: Locations, - describe_op: impl Fn() -> String, - op: impl FnOnce(&mut Self) -> InferResult<'tcx, R>, - ) -> Result<R, TypeError<'tcx>> { - let (r, opt_data) = self.fully_perform_op_and_get_region_constraint_data( - || format!("{} at {:?}", describe_op(), locations), - op, - )?; - - if let Some(data) = opt_data { + op: impl type_op::TypeOp<'gcx, 'tcx, Output = R>, + ) -> Fallible<R> { + let (r, opt_data) = op.fully_perform(self.infcx)?; + + if let Some(data) = &opt_data { self.push_region_constraints(locations, data); } @@ -749,7 +745,7 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { fn push_region_constraints( &mut self, locations: Locations, - data: Rc<RegionConstraintData<'tcx>>, + data: &[QueryRegionConstraint<'tcx>], ) { debug!( "push_region_constraints: constraints generated at {:?} are {:#?}", @@ -758,55 +754,18 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { if let Some(borrowck_context) = &mut self.borrowck_context { constraint_conversion::ConstraintConversion::new( + self.infcx.tcx, self.mir, borrowck_context.universal_regions, borrowck_context.location_table, + self.region_bound_pairs, + self.implicit_region_bound, + self.param_env, + locations, &mut self.constraints.outlives_constraints, &mut self.constraints.type_tests, &mut borrowck_context.all_facts, - ).convert(locations, &data); - } - } - - /// Helper for `fully_perform_op`, but also used on its own - /// sometimes to enable better caching: executes `op` fully (along - /// with resulting obligations) and returns the full set of region - /// obligations. If the same `op` were to be performed at some - /// other location, then the same set of region obligations would - /// be generated there, so this can be useful for caching. - fn fully_perform_op_and_get_region_constraint_data<R>( - &mut self, - describe_op: impl Fn() -> String, - op: impl FnOnce(&mut Self) -> InferResult<'tcx, R>, - ) -> Result<(R, Option<Rc<RegionConstraintData<'tcx>>>), TypeError<'tcx>> { - if cfg!(debug_assertions) { - info!( - "fully_perform_op_and_get_region_constraint_data({})", - describe_op(), - ); - } - - let mut fulfill_cx = TraitEngine::new(self.infcx.tcx); - let dummy_body_id = ObligationCause::dummy().body_id; - let InferOk { value, obligations } = self.infcx.commit_if_ok(|_| op(self))?; - debug_assert!(obligations.iter().all(|o| o.cause.body_id == dummy_body_id)); - fulfill_cx.register_predicate_obligations(self.infcx, obligations); - if let Err(e) = fulfill_cx.select_all_or_error(self.infcx) { - span_mirbug!(self, "", "errors selecting obligation: {:?}", e); - } - - self.infcx.process_registered_region_obligations( - self.region_bound_pairs, - self.implicit_region_bound, - self.param_env, - dummy_body_id, - ); - - let data = self.infcx.take_and_reset_region_constraints(); - if data.is_empty() { - Ok((value, None)) - } else { - Ok((value, Some(Rc::new(data)))) + ).convert_all(&data); } } @@ -815,38 +774,17 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { sub: Ty<'tcx>, sup: Ty<'tcx>, locations: Locations, - ) -> UnitResult<'tcx> { - // Micro-optimization. - if sub == sup { - return Ok(()); - } - + ) -> Fallible<()> { + let param_env = self.param_env; self.fully_perform_op( locations, - || format!("sub_types({:?} <: {:?})", sub, sup), - |this| { - this.infcx - .at(&ObligationCause::dummy(), this.param_env) - .sup(sup, sub) - }, + param_env.and(type_op::subtype::Subtype::new(sub, sup)), ) } - fn eq_types(&mut self, a: Ty<'tcx>, b: Ty<'tcx>, locations: Locations) -> UnitResult<'tcx> { - // Micro-optimization. - if a == b { - return Ok(()); - } - - self.fully_perform_op( - locations, - || format!("eq_types({:?} = {:?})", a, b), - |this| { - this.infcx - .at(&ObligationCause::dummy(), this.param_env) - .eq(b, a) - }, - ) + fn eq_types(&mut self, a: Ty<'tcx>, b: Ty<'tcx>, locations: Locations) -> Fallible<()> { + let param_env = self.param_env; + self.fully_perform_op(locations, param_env.and(type_op::eq::Eq::new(b, a))) } fn tcx(&self) -> TyCtxt<'a, 'gcx, 'tcx> { @@ -1040,7 +978,7 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { LateBoundRegionConversionTime::FnCall, &sig, ); - let sig = self.normalize(&sig, term_location); + let sig = self.normalize(sig, term_location); self.check_call_dest(mir, term, &sig, destination, term_location); self.prove_predicates( @@ -1328,7 +1266,7 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { let variant = &def.variants[variant_index]; let adj_field_index = active_field_index.unwrap_or(field_index); if let Some(field) = variant.fields.get(adj_field_index) { - Ok(self.normalize(&field.ty(tcx, substs), location)) + Ok(self.normalize(field.ty(tcx, substs), location)) } else { Err(FieldAccessError::OutOfRange { field_count: variant.fields.len(), @@ -1402,7 +1340,7 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { // function definition. When we extract the // signature, it comes from the `fn_sig` query, // and hence may contain unnormalized results. - let fn_sig = self.normalize(&fn_sig, location); + let fn_sig = self.normalize(fn_sig, location); let ty_fn_ptr_from = tcx.mk_fn_ptr(fn_sig); @@ -1447,7 +1385,7 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { // function definition. When we extract the // signature, it comes from the `fn_sig` query, // and hence may contain unnormalized results. - let fn_sig = self.normalize(&fn_sig, location); + let fn_sig = self.normalize(fn_sig, location); let ty_fn_ptr_from = tcx.safe_to_unsafe_fn_ty(fn_sig); @@ -1573,14 +1511,17 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { if let Some(closure_region_requirements) = tcx.mir_borrowck(*def_id).closure_requirements { - let dummy_body_id = ObligationCause::dummy().body_id; - closure_region_requirements.apply_requirements( - self.infcx, - dummy_body_id, + let closure_constraints = closure_region_requirements.apply_requirements( + self.infcx.tcx, location, *def_id, *substs, ); + + self.push_region_constraints( + location.at_self(), + &closure_constraints, + ); } tcx.predicates_of(*def_id).instantiate(tcx, substs.substs) @@ -1593,9 +1534,7 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { AggregateKind::Array(_) | AggregateKind::Tuple => ty::InstantiatedPredicates::empty(), }; - let predicates = self.normalize(&instantiated_predicates.predicates, location); - debug!("prove_aggregate_predicates: predicates={:?}", predicates); - self.prove_predicates(predicates, location); + self.normalize_and_prove_instantiated_predicates(instantiated_predicates, location); } fn prove_trait_ref(&mut self, trait_ref: ty::TraitRef<'tcx>, location: Location) { @@ -1607,46 +1546,45 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { ); } - fn prove_predicates<T>(&mut self, predicates: T, location: Location) - where - T: IntoIterator<Item = ty::Predicate<'tcx>> + Clone, - { - let cause = ObligationCause::dummy(); - let obligations: Vec<_> = predicates - .into_iter() - .map(|p| traits::Obligation::new(cause.clone(), self.param_env, p)) - .collect(); - - // Micro-optimization - if obligations.is_empty() { - return; + fn normalize_and_prove_instantiated_predicates( + &mut self, + instantiated_predicates: ty::InstantiatedPredicates<'tcx>, + location: Location, + ) { + for predicate in instantiated_predicates.predicates { + let predicate = self.normalize(predicate, location); + self.prove_predicate(predicate, location); } + } - // This intermediate vector is mildly unfortunate, in that we - // sometimes create it even when logging is disabled, but only - // if debug-info is enabled, and I doubt it is actually - // expensive. -nmatsakis - let predicates_vec: Vec<_> = if cfg!(debug_assertions) { - obligations.iter().map(|o| o.predicate).collect() - } else { - Vec::new() - }; + fn prove_predicates( + &mut self, + predicates: impl IntoIterator<Item = ty::Predicate<'tcx>>, + location: Location, + ) { + for predicate in predicates { + debug!( + "prove_predicates(predicate={:?}, location={:?})", + predicate, location, + ); + + self.prove_predicate(predicate, location); + } + } + fn prove_predicate(&mut self, predicate: ty::Predicate<'tcx>, location: Location) { debug!( - "prove_predicates(predicates={:?}, location={:?})", - predicates_vec, location, + "prove_predicate(predicate={:?}, location={:?})", + predicate, location, ); + let param_env = self.param_env; self.fully_perform_op( location.at_self(), - || format!("prove_predicates({:?})", predicates_vec), - |_this| { - Ok(InferOk { - value: (), - obligations, - }) - }, - ).unwrap() + param_env.and(type_op::prove_predicate::ProvePredicate::new(predicate)), + ).unwrap_or_else(|NoSolution| { + span_mirbug!(self, NoSolution, "could not prove {:?}", predicate); + }) } fn typeck_mir(&mut self, mir: &Mir<'tcx>) { @@ -1675,35 +1613,19 @@ impl<'a, 'gcx, 'tcx> TypeChecker<'a, 'gcx, 'tcx> { } } - fn normalize<T>(&mut self, value: &T, location: impl ToLocations) -> T + fn normalize<T>(&mut self, value: T, location: impl ToLocations) -> T where - T: fmt::Debug + TypeFoldable<'tcx>, + T: type_op::normalize::Normalizable<'gcx, 'tcx> + Copy, { - // Micro-optimization: avoid work when we don't have to - if !value.has_projections() { - return value.clone(); - } - debug!("normalize(value={:?}, location={:?})", value, location); + let param_env = self.param_env; self.fully_perform_op( location.to_locations(), - || format!("normalize(value={:?})", value), - |this| { - let Normalized { value, obligations } = this - .infcx - .at(&ObligationCause::dummy(), this.param_env) - .normalize(value) - .unwrap_or_else(|NoSolution| { - span_bug!( - this.last_span, - "normalization of `{:?}` failed at {:?}", - value, - location, - ); - }); - Ok(InferOk { value, obligations }) - }, - ).unwrap() + param_env.and(type_op::normalize::Normalize::new(value)), + ).unwrap_or_else(|NoSolution| { + span_mirbug!(self, NoSolution, "failed to normalize `{:?}`", value); + value + }) } } @@ -1735,16 +1657,8 @@ impl MirPass for TypeckMir { let param_env = tcx.param_env(def_id); tcx.infer_ctxt().enter(|infcx| { - let _ = type_check_internal( - &infcx, - def_id, - param_env, - mir, - &[], - None, - None, - &mut |_| (), - ); + let _ = + type_check_internal(&infcx, def_id, param_env, mir, &[], None, None, &mut |_| ()); // For verification purposes, we just ignore the resulting // region constraint sets. Not our problem. =) diff --git a/src/librustc_mir/borrow_check/nll/universal_regions.rs b/src/librustc_mir/borrow_check/nll/universal_regions.rs index 2bb96a856ce..ec8cd386679 100644 --- a/src/librustc_mir/borrow_check/nll/universal_regions.rs +++ b/src/librustc_mir/borrow_check/nll/universal_regions.rs @@ -238,13 +238,13 @@ impl<'tcx> UniversalRegions<'tcx> { /// `'1: '2`, then the caller would impose the constraint that /// `V[1]: V[2]`. pub fn closure_mapping( - infcx: &InferCtxt<'_, '_, 'tcx>, + tcx: TyCtxt<'_, '_, 'tcx>, closure_ty: Ty<'tcx>, expected_num_vars: usize, ) -> IndexVec<RegionVid, ty::Region<'tcx>> { let mut region_mapping = IndexVec::with_capacity(expected_num_vars); - region_mapping.push(infcx.tcx.types.re_static); - infcx.tcx.for_each_free_region(&closure_ty, |fr| { + region_mapping.push(tcx.types.re_static); + tcx.for_each_free_region(&closure_ty, |fr| { region_mapping.push(fr); }); diff --git a/src/librustc_traits/chalk_context.rs b/src/librustc_traits/chalk_context.rs index a1242621cb1..6062fe03e6a 100644 --- a/src/librustc_traits/chalk_context.rs +++ b/src/librustc_traits/chalk_context.rs @@ -10,9 +10,7 @@ use chalk_engine::fallible::Fallible as ChalkEngineFallible; use chalk_engine::{context, hh::HhGoal, DelayedLiteral, ExClause}; -use rustc::infer::canonical::{ - Canonical, CanonicalVarValues, Canonicalize, QueryRegionConstraint, QueryResult, -}; +use rustc::infer::canonical::{Canonical, CanonicalVarValues, QueryRegionConstraint, QueryResult}; use rustc::infer::{InferCtxt, InferOk, LateBoundRegionConversionTime}; use rustc::traits::{ WellFormed, @@ -519,14 +517,3 @@ BraceStructLiftImpl! { subst, constraints } } - -impl<'gcx: 'tcx, 'tcx> Canonicalize<'gcx, 'tcx> for ConstrainedSubst<'tcx> { - type Canonicalized = Canonical<'gcx, ConstrainedSubst<'gcx>>; - - fn intern( - _gcx: TyCtxt<'_, 'gcx, 'gcx>, - value: Canonical<'gcx, ConstrainedSubst<'gcx>>, - ) -> Self::Canonicalized { - value - } -} diff --git a/src/librustc_traits/dropck_outlives.rs b/src/librustc_traits/dropck_outlives.rs index 219c6b9aefb..5f9060b3623 100644 --- a/src/librustc_traits/dropck_outlives.rs +++ b/src/librustc_traits/dropck_outlives.rs @@ -8,19 +8,27 @@ // option. This file may not be copied, modified, or distributed // except according to those terms. -use rustc::infer::canonical::{Canonical, QueryResult}; use rustc::hir::def_id::DefId; -use rustc::traits::{FulfillmentContext, Normalized, ObligationCause}; +use rustc::infer::canonical::{Canonical, QueryResult}; +use rustc::traits::query::dropck_outlives::{DropckOutlivesResult, DtorckConstraint}; use rustc::traits::query::{CanonicalTyGoal, NoSolution}; -use rustc::traits::query::dropck_outlives::{DtorckConstraint, DropckOutlivesResult}; -use rustc::ty::{self, ParamEnvAnd, Ty, TyCtxt}; +use rustc::traits::{FulfillmentContext, Normalized, ObligationCause, TraitEngineExt}; +use rustc::ty::query::Providers; use rustc::ty::subst::{Subst, Substs}; +use rustc::ty::{self, ParamEnvAnd, Ty, TyCtxt}; use rustc::util::nodemap::FxHashSet; use rustc_data_structures::sync::Lrc; use syntax::codemap::{Span, DUMMY_SP}; -use util; -crate fn dropck_outlives<'tcx>( +crate fn provide(p: &mut Providers) { + *p = Providers { + dropck_outlives, + adt_dtorck_constraint, + ..*p + }; +} + +fn dropck_outlives<'tcx>( tcx: TyCtxt<'_, 'tcx, 'tcx>, goal: CanonicalTyGoal<'tcx>, ) -> Result<Lrc<Canonical<'tcx, QueryResult<'tcx, DropckOutlivesResult<'tcx>>>>, NoSolution> { @@ -36,7 +44,10 @@ crate fn dropck_outlives<'tcx>( canonical_inference_vars, ) = infcx.instantiate_canonical_with_fresh_inference_vars(DUMMY_SP, &goal); - let mut result = DropckOutlivesResult { kinds: vec![], overflows: vec![] }; + let mut result = DropckOutlivesResult { + kinds: vec![], + overflows: vec![], + }; // A stack of types left to process. Each round, we pop // something from the stack and invoke @@ -135,7 +146,7 @@ crate fn dropck_outlives<'tcx>( debug!("dropck_outlives: result = {:#?}", result); - util::make_query_response(infcx, canonical_inference_vars, result, fulfill_cx) + infcx.make_canonicalized_query_result(canonical_inference_vars, result, fulfill_cx) }) } @@ -184,7 +195,8 @@ fn dtorck_constraint_for_ty<'a, 'gcx, 'tcx>( dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ety) } - ty::TyTuple(tys) => tys.iter() + ty::TyTuple(tys) => tys + .iter() .map(|ty| dtorck_constraint_for_ty(tcx, span, for_ty, depth + 1, ty)) .collect(), @@ -222,7 +234,10 @@ fn dtorck_constraint_for_ty<'a, 'gcx, 'tcx>( dtorck_types: vec![], overflows: vec![], }; - debug!("dtorck_constraint: generator {:?} => {:?}", def_id, constraint); + debug!( + "dtorck_constraint: generator {:?} => {:?}", + def_id, constraint + ); Ok(constraint) } @@ -291,7 +306,8 @@ crate fn adt_dtorck_constraint<'a, 'tcx>( return Ok(result); } - let mut result = def.all_fields() + let mut result = def + .all_fields() .map(|field| tcx.type_of(field.did)) .map(|fty| dtorck_constraint_for_ty(tcx, span, fty, 0, fty)) .collect::<Result<DtorckConstraint, NoSolution>>()?; diff --git a/src/librustc_traits/evaluate_obligation.rs b/src/librustc_traits/evaluate_obligation.rs index 21259bbcd38..e8a3447902f 100644 --- a/src/librustc_traits/evaluate_obligation.rs +++ b/src/librustc_traits/evaluate_obligation.rs @@ -11,10 +11,18 @@ use rustc::traits::{EvaluationResult, Obligation, ObligationCause, OverflowError, SelectionContext, TraitQueryMode}; use rustc::traits::query::CanonicalPredicateGoal; +use rustc::ty::query::Providers; use rustc::ty::{ParamEnvAnd, TyCtxt}; use syntax::codemap::DUMMY_SP; -crate fn evaluate_obligation<'tcx>( +crate fn provide(p: &mut Providers) { + *p = Providers { + evaluate_obligation, + ..*p + }; +} + +fn evaluate_obligation<'tcx>( tcx: TyCtxt<'_, 'tcx, 'tcx>, goal: CanonicalPredicateGoal<'tcx>, ) -> Result<EvaluationResult, OverflowError> { diff --git a/src/librustc_traits/lib.rs b/src/librustc_traits/lib.rs index c3135439204..1da3907915a 100644 --- a/src/librustc_traits/lib.rs +++ b/src/librustc_traits/lib.rs @@ -33,21 +33,16 @@ mod dropck_outlives; mod evaluate_obligation; mod normalize_projection_ty; mod normalize_erasing_regions; -mod util; pub mod lowering; +mod type_op; use rustc::ty::query::Providers; pub fn provide(p: &mut Providers) { - *p = Providers { - dropck_outlives: dropck_outlives::dropck_outlives, - adt_dtorck_constraint: dropck_outlives::adt_dtorck_constraint, - normalize_projection_ty: normalize_projection_ty::normalize_projection_ty, - normalize_ty_after_erasing_regions: - normalize_erasing_regions::normalize_ty_after_erasing_regions, - program_clauses_for: lowering::program_clauses_for, - program_clauses_for_env: lowering::program_clauses_for_env, - evaluate_obligation: evaluate_obligation::evaluate_obligation, - ..*p - }; + dropck_outlives::provide(p); + evaluate_obligation::provide(p); + lowering::provide(p); + normalize_projection_ty::provide(p); + normalize_erasing_regions::provide(p); + type_op::provide(p); } diff --git a/src/librustc_traits/lowering.rs b/src/librustc_traits/lowering.rs index 0270e970976..16aa63d6999 100644 --- a/src/librustc_traits/lowering.rs +++ b/src/librustc_traits/lowering.rs @@ -14,6 +14,7 @@ use rustc::hir::map::definitions::DefPathData; use rustc::hir::{self, ImplPolarity}; use rustc::traits::{Clause, Clauses, DomainGoal, Goal, PolyDomainGoal, ProgramClause, WhereClause, FromEnv, WellFormed}; +use rustc::ty::query::Providers; use rustc::ty::subst::Substs; use rustc::ty::{self, Slice, TyCtxt}; use rustc_data_structures::fx::FxHashSet; @@ -22,6 +23,14 @@ use syntax::ast; use std::iter; +crate fn provide(p: &mut Providers) { + *p = Providers { + program_clauses_for, + program_clauses_for_env, + ..*p + }; +} + crate trait Lower<T> { /// Lower a rustc construct (e.g. `ty::TraitPredicate`) to a chalk-like type. fn lower(&self) -> T; diff --git a/src/librustc_traits/normalize_erasing_regions.rs b/src/librustc_traits/normalize_erasing_regions.rs index 299433d479d..a85983d0e9a 100644 --- a/src/librustc_traits/normalize_erasing_regions.rs +++ b/src/librustc_traits/normalize_erasing_regions.rs @@ -10,10 +10,18 @@ use rustc::traits::{Normalized, ObligationCause}; use rustc::traits::query::NoSolution; +use rustc::ty::query::Providers; use rustc::ty::{self, ParamEnvAnd, Ty, TyCtxt}; use std::sync::atomic::Ordering; -crate fn normalize_ty_after_erasing_regions<'tcx>( +crate fn provide(p: &mut Providers) { + *p = Providers { + normalize_ty_after_erasing_regions, + ..*p + }; +} + +fn normalize_ty_after_erasing_regions<'tcx>( tcx: TyCtxt<'_, 'tcx, 'tcx>, goal: ParamEnvAnd<'tcx, Ty<'tcx>>, ) -> Ty<'tcx> { diff --git a/src/librustc_traits/normalize_projection_ty.rs b/src/librustc_traits/normalize_projection_ty.rs index a9ac53972e4..1c0f677fbf3 100644 --- a/src/librustc_traits/normalize_projection_ty.rs +++ b/src/librustc_traits/normalize_projection_ty.rs @@ -9,45 +9,55 @@ // except according to those terms. use rustc::infer::canonical::{Canonical, QueryResult}; -use rustc::traits::{self, FulfillmentContext, ObligationCause, SelectionContext}; -use rustc::traits::query::{CanonicalProjectionGoal, NoSolution, normalize::NormalizationResult}; +use rustc::traits::query::{normalize::NormalizationResult, CanonicalProjectionGoal, NoSolution}; +use rustc::traits::{self, ObligationCause, SelectionContext, TraitEngineExt}; +use rustc::ty::query::Providers; use rustc::ty::{ParamEnvAnd, TyCtxt}; use rustc_data_structures::sync::Lrc; +use std::sync::atomic::Ordering; use syntax::ast::DUMMY_NODE_ID; use syntax_pos::DUMMY_SP; -use util; -use std::sync::atomic::Ordering; -crate fn normalize_projection_ty<'tcx>( +crate fn provide(p: &mut Providers) { + *p = Providers { + normalize_projection_ty, + ..*p + }; +} + +fn normalize_projection_ty<'tcx>( tcx: TyCtxt<'_, 'tcx, 'tcx>, goal: CanonicalProjectionGoal<'tcx>, ) -> Result<Lrc<Canonical<'tcx, QueryResult<'tcx, NormalizationResult<'tcx>>>>, NoSolution> { debug!("normalize_provider(goal={:#?})", goal); - tcx.sess.perf_stats.normalize_projection_ty.fetch_add(1, Ordering::Relaxed); - tcx.infer_ctxt().enter(|ref infcx| { - let ( - ParamEnvAnd { + tcx.sess + .perf_stats + .normalize_projection_ty + .fetch_add(1, Ordering::Relaxed); + tcx.infer_ctxt().enter_canonical_trait_query( + &goal, + |infcx, + fulfill_cx, + ParamEnvAnd { + param_env, + value: goal, + }| { + let selcx = &mut SelectionContext::new(infcx); + let cause = ObligationCause::misc(DUMMY_SP, DUMMY_NODE_ID); + let mut obligations = vec![]; + let answer = traits::normalize_projection_type( + selcx, param_env, - value: goal, - }, - canonical_inference_vars, - ) = infcx.instantiate_canonical_with_fresh_inference_vars(DUMMY_SP, &goal); - let fulfill_cx = &mut FulfillmentContext::new(); - let selcx = &mut SelectionContext::new(infcx); - let cause = ObligationCause::misc(DUMMY_SP, DUMMY_NODE_ID); - let mut obligations = vec![]; - let answer = - traits::normalize_projection_type(selcx, param_env, goal, cause, 0, &mut obligations); - fulfill_cx.register_predicate_obligations(infcx, obligations); - - // Now that we have fulfilled as much as we can, create a solution - // from what we've learned. - util::make_query_response( - infcx, - canonical_inference_vars, - NormalizationResult { normalized_ty: answer }, - fulfill_cx, - ) - }) + goal, + cause, + 0, + &mut obligations, + ); + fulfill_cx.register_predicate_obligations(infcx, obligations); + Ok(NormalizationResult { + normalized_ty: answer, + }) + }, + ) } diff --git a/src/librustc_traits/type_op.rs b/src/librustc_traits/type_op.rs new file mode 100644 index 00000000000..8fe4290528e --- /dev/null +++ b/src/librustc_traits/type_op.rs @@ -0,0 +1,127 @@ +// Copyright 2014 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +use rustc::infer::canonical::{Canonical, QueryResult}; +use rustc::infer::InferCtxt; +use rustc::traits::query::type_op::eq::Eq; +use rustc::traits::query::type_op::normalize::Normalize; +use rustc::traits::query::type_op::prove_predicate::ProvePredicate; +use rustc::traits::query::type_op::subtype::Subtype; +use rustc::traits::query::{Fallible, NoSolution}; +use rustc::traits::{FulfillmentContext, Normalized, Obligation, ObligationCause, TraitEngine, + TraitEngineExt}; +use rustc::ty::query::Providers; +use rustc::ty::{FnSig, Lift, ParamEnvAnd, PolyFnSig, Predicate, Ty, TyCtxt, TypeFoldable}; +use rustc_data_structures::sync::Lrc; +use std::fmt; + +crate fn provide(p: &mut Providers) { + *p = Providers { + type_op_eq, + type_op_prove_predicate, + type_op_subtype, + type_op_normalize_ty, + type_op_normalize_predicate, + type_op_normalize_fn_sig, + type_op_normalize_poly_fn_sig, + ..*p + }; +} + +fn type_op_eq<'tcx>( + tcx: TyCtxt<'_, 'tcx, 'tcx>, + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Eq<'tcx>>>, +) -> Result<Lrc<Canonical<'tcx, QueryResult<'tcx, ()>>>, NoSolution> { + tcx.infer_ctxt() + .enter_canonical_trait_query(&canonicalized, |infcx, fulfill_cx, key| { + let (param_env, Eq { a, b }) = key.into_parts(); + Ok(infcx + .at(&ObligationCause::dummy(), param_env) + .eq(a, b)? + .into_value_registering_obligations(infcx, fulfill_cx)) + }) +} + +fn type_op_normalize<T>( + infcx: &InferCtxt<'_, 'gcx, 'tcx>, + fulfill_cx: &mut FulfillmentContext<'tcx>, + key: ParamEnvAnd<'tcx, Normalize<T>>, +) -> Fallible<T> +where + T: fmt::Debug + TypeFoldable<'tcx> + Lift<'gcx>, +{ + let (param_env, Normalize { value }) = key.into_parts(); + let Normalized { value, obligations } = infcx + .at(&ObligationCause::dummy(), param_env) + .normalize(&value)?; + fulfill_cx.register_predicate_obligations(infcx, obligations); + Ok(value) +} + +fn type_op_normalize_ty( + tcx: TyCtxt<'_, 'tcx, 'tcx>, + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<Ty<'tcx>>>>, +) -> Result<Lrc<Canonical<'tcx, QueryResult<'tcx, Ty<'tcx>>>>, NoSolution> { + tcx.infer_ctxt() + .enter_canonical_trait_query(&canonicalized, type_op_normalize) +} + +fn type_op_normalize_predicate( + tcx: TyCtxt<'_, 'tcx, 'tcx>, + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<Predicate<'tcx>>>>, +) -> Result<Lrc<Canonical<'tcx, QueryResult<'tcx, Predicate<'tcx>>>>, NoSolution> { + tcx.infer_ctxt() + .enter_canonical_trait_query(&canonicalized, type_op_normalize) +} + +fn type_op_normalize_fn_sig( + tcx: TyCtxt<'_, 'tcx, 'tcx>, + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<FnSig<'tcx>>>>, +) -> Result<Lrc<Canonical<'tcx, QueryResult<'tcx, FnSig<'tcx>>>>, NoSolution> { + tcx.infer_ctxt() + .enter_canonical_trait_query(&canonicalized, type_op_normalize) +} + +fn type_op_normalize_poly_fn_sig( + tcx: TyCtxt<'_, 'tcx, 'tcx>, + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Normalize<PolyFnSig<'tcx>>>>, +) -> Result<Lrc<Canonical<'tcx, QueryResult<'tcx, PolyFnSig<'tcx>>>>, NoSolution> { + tcx.infer_ctxt() + .enter_canonical_trait_query(&canonicalized, type_op_normalize) +} + +fn type_op_subtype<'tcx>( + tcx: TyCtxt<'_, 'tcx, 'tcx>, + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, Subtype<'tcx>>>, +) -> Result<Lrc<Canonical<'tcx, QueryResult<'tcx, ()>>>, NoSolution> { + tcx.infer_ctxt() + .enter_canonical_trait_query(&canonicalized, |infcx, fulfill_cx, key| { + let (param_env, Subtype { sub, sup }) = key.into_parts(); + Ok(infcx + .at(&ObligationCause::dummy(), param_env) + .sup(sup, sub)? + .into_value_registering_obligations(infcx, fulfill_cx)) + }) +} + +fn type_op_prove_predicate<'tcx>( + tcx: TyCtxt<'_, 'tcx, 'tcx>, + canonicalized: Canonical<'tcx, ParamEnvAnd<'tcx, ProvePredicate<'tcx>>>, +) -> Result<Lrc<Canonical<'tcx, QueryResult<'tcx, ()>>>, NoSolution> { + tcx.infer_ctxt() + .enter_canonical_trait_query(&canonicalized, |infcx, fulfill_cx, key| { + let (param_env, ProvePredicate { predicate }) = key.into_parts(); + fulfill_cx.register_predicate_obligation( + infcx, + Obligation::new(ObligationCause::dummy(), param_env, predicate), + ); + Ok(()) + }) +} diff --git a/src/librustc_traits/util.rs b/src/librustc_traits/util.rs deleted file mode 100644 index cdf20bdafad..00000000000 --- a/src/librustc_traits/util.rs +++ /dev/null @@ -1,123 +0,0 @@ -// Copyright 2014 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -use rustc::infer::InferCtxt; -use rustc::infer::canonical::{CanonicalVarValues, Canonicalize, Certainty, QueryResult}; -use rustc::infer::region_constraints::{Constraint, RegionConstraintData}; -use rustc::traits::{FulfillmentContext, TraitEngine}; -use rustc::traits::query::NoSolution; -use rustc::ty; -use std::fmt::Debug; - -/// The canonicalization form of `QueryResult<'tcx, T>`. -type CanonicalizedQueryResult<'gcx, 'tcx, T> = - <QueryResult<'tcx, T> as Canonicalize<'gcx, 'tcx>>::Canonicalized; - -crate fn make_query_response<'gcx, 'tcx, T>( - infcx: &InferCtxt<'_, 'gcx, 'tcx>, - inference_vars: CanonicalVarValues<'tcx>, - answer: T, - fulfill_cx: &mut FulfillmentContext<'tcx>, -) -> Result<CanonicalizedQueryResult<'gcx, 'tcx, T>, NoSolution> -where - T: Debug, - QueryResult<'tcx, T>: Canonicalize<'gcx, 'tcx>, -{ - let tcx = infcx.tcx; - - debug!( - "make_query_response(\ - inference_vars={:?}, \ - answer={:?})", - inference_vars, answer, - ); - - // Select everything, returning errors. - let true_errors = match fulfill_cx.select_where_possible(infcx) { - Ok(()) => vec![], - Err(errors) => errors, - }; - debug!("true_errors = {:#?}", true_errors); - - if !true_errors.is_empty() { - // FIXME -- we don't indicate *why* we failed to solve - debug!("make_query_response: true_errors={:#?}", true_errors); - return Err(NoSolution); - } - - // Anything left unselected *now* must be an ambiguity. - let ambig_errors = match fulfill_cx.select_all_or_error(infcx) { - Ok(()) => vec![], - Err(errors) => errors, - }; - debug!("ambig_errors = {:#?}", ambig_errors); - - let region_obligations = infcx.take_registered_region_obligations(); - - let region_constraints = infcx.with_region_constraints(|region_constraints| { - let RegionConstraintData { - constraints, - verifys, - givens, - } = region_constraints; - - assert!(verifys.is_empty()); - assert!(givens.is_empty()); - - let mut outlives: Vec<_> = constraints - .into_iter() - .map(|(k, _)| match *k { - // Swap regions because we are going from sub (<=) to outlives - // (>=). - Constraint::VarSubVar(v1, v2) => ty::OutlivesPredicate( - tcx.mk_region(ty::ReVar(v2)).into(), - tcx.mk_region(ty::ReVar(v1)), - ), - Constraint::VarSubReg(v1, r2) => { - ty::OutlivesPredicate(r2.into(), tcx.mk_region(ty::ReVar(v1))) - } - Constraint::RegSubVar(r1, v2) => { - ty::OutlivesPredicate(tcx.mk_region(ty::ReVar(v2)).into(), r1) - } - Constraint::RegSubReg(r1, r2) => ty::OutlivesPredicate(r2.into(), r1), - }) - .map(ty::Binder::dummy) // no bound regions in the code above - .collect(); - - outlives.extend( - region_obligations - .into_iter() - .map(|(_, r_o)| ty::OutlivesPredicate(r_o.sup_type.into(), r_o.sub_region)) - .map(ty::Binder::dummy) // no bound regions in the code above - ); - - outlives - }); - - let certainty = if ambig_errors.is_empty() { - Certainty::Proven - } else { - Certainty::Ambiguous - }; - - let (canonical_result, _) = infcx.canonicalize_response(&QueryResult { - var_values: inference_vars, - region_constraints, - certainty, - value: answer, - }); - - debug!( - "make_query_response: canonical_result = {:#?}", - canonical_result - ); - - Ok(canonical_result) -} diff --git a/src/librustc_typeck/check/dropck.rs b/src/librustc_typeck/check/dropck.rs index b8aa39a202b..f9166851f6f 100644 --- a/src/librustc_typeck/check/dropck.rs +++ b/src/librustc_typeck/check/dropck.rs @@ -16,7 +16,7 @@ use rustc::infer::outlives::env::OutlivesEnvironment; use rustc::middle::region; use rustc::ty::subst::{Subst, Substs, UnpackedKind}; use rustc::ty::{self, Ty, TyCtxt}; -use rustc::traits::{ObligationCause, TraitEngine}; +use rustc::traits::{ObligationCause, TraitEngine, TraitEngineExt}; use util::common::ErrorReported; use syntax::ast; diff --git a/src/librustc_typeck/lib.rs b/src/librustc_typeck/lib.rs index dcc5fa53d2f..b18e5ca54ff 100644 --- a/src/librustc_typeck/lib.rs +++ b/src/librustc_typeck/lib.rs @@ -108,7 +108,7 @@ use rustc::infer::InferOk; use rustc::ty::subst::Substs; use rustc::ty::{self, Ty, TyCtxt}; use rustc::ty::query::Providers; -use rustc::traits::{ObligationCause, ObligationCauseCode, TraitEngine}; +use rustc::traits::{ObligationCause, ObligationCauseCode, TraitEngine, TraitEngineExt}; use session::{CompileIncomplete, config}; use util::common::time; |