diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/librustc/middle/traits/doc.rs | 128 | ||||
| -rw-r--r-- | src/librustc/middle/traits/select.rs | 51 | ||||
| -rw-r--r-- | src/librustc/middle/ty.rs | 65 | ||||
| -rw-r--r-- | src/test/run-pass/trait-cache-issue-18209.rs | 27 |
4 files changed, 212 insertions, 59 deletions
diff --git a/src/librustc/middle/traits/doc.rs b/src/librustc/middle/traits/doc.rs index f24121d9a3a..a8fcdb36054 100644 --- a/src/librustc/middle/traits/doc.rs +++ b/src/librustc/middle/traits/doc.rs @@ -279,4 +279,132 @@ selection. This is because it must account for the transformed self type of the receiver and various other complications. The procedure is described in `select.rs` in the "METHOD MATCHING" section. +# Caching and subtle considerations therewith + +In general we attempt to cache the results of trait selection. This +is a somewhat complex process. Part of the reason for this is that we +want to be able to cache results even when all the types in the trait +reference are not fully known. In that case, it may happen that the +trait selection process is also influencing type variables, so we have +to be able to not only cache the *result* of the selection process, +but *reply* its effects on the type variables. + +## An example + +The high-level idea of how the cache works is that we first replace +all unbound inference variables with skolemized versions. Therefore, +if we had a trait reference `uint : Foo<$1>`, where `$n` is an unbound +inference variable, we might replace it with `uint : Foo<%0>`, where +`%n` is a skolemized type. We would then look this up in the cache. +If we found a hit, the hit would tell us the immediate next step to +take in the selection process: i.e., apply impl #22, or apply where +clause `X : Foo<Y>`. Let's say in this case there is no hit. +Therefore, we search through impls and where clauses and so forth, and +we come to the conclusion that the only possible impl is this one, +with def-id 22: + + impl Foo<int> for uint { ... } // Impl #22 + +We would then record in the cache `uint : Foo<%0> ==> +ImplCandidate(22)`. Next we would confirm `ImplCandidate(22)`, which +would (as a side-effect) unify `$1` with `int`. + +Now, at some later time, we might come along and see a `uint : +Foo<$3>`. When skolemized, this would yield `uint : Foo<%0>`, just as +before, and hence the cache lookup would succeed, yielding +`ImplCandidate(22)`. We would confirm `ImplCandidate(22)` which would +(as a side-effect) unify `$3` with `int`. + +## Where clauses and the local vs global cache + +One subtle interaction is that the results of trait lookup will vary +depending on what where clauses are in scope. Therefore, we actually +have *two* caches, a local and a global cache. The local cache is +attached to the `ParameterEnvironment` and the global cache attached +to the `tcx`. We use the local cache whenever the result might depend +on the where clauses that are in scope. The determination of which +cache to use is done by the method `pick_candidate_cache` in +`select.rs`. + +There are two cases where we currently use the local cache. The +current rules are probably more conservative than necessary. + +### Trait references that involve parameter types + +The most obvious case where you need the local environment is +when the trait reference includes parameter types. For example, +consider the following function: + + impl<T> Vec<T> { + fn foo(x: T) + where T : Foo + { ... } + + fn bar(x: T) + { ... } + } + +If there is an obligation `T : Foo`, or `int : Bar<T>`, or whatever, +clearly the results from `foo` and `bar` are potentially different, +since the set of where clauses in scope are different. + +### Trait references with unbound variables when where clauses are in scope + +There is another less obvious interaction which involves unbound variables +where *only* where clauses are in scope (no impls). This manifested as +issue #18209 (`run-pass/trait-cache-issue-18209.rs`). Consider +this snippet: + +``` +pub trait Foo { + fn load_from() -> Box<Self>; + fn load() -> Box<Self> { + Foo::load_from() + } +} +``` + +The default method will incur an obligation `$0 : Foo` from the call +to `load_from`. If there are no impls, this can be eagerly resolved to +`VtableParam(Self : Foo)` and cached. Because the trait reference +doesn't involve any parameters types (only the resolution does), this +result was stored in the global cache, causing later calls to +`Foo::load_from()` to get nonsense. + +To fix this, we always use the local cache if there are unbound +variables and where clauses in scope. This is more conservative than +necessary as far as I can tell. However, it still seems to be a simple +rule and I observe ~99% hit rate on rustc, so it doesn't seem to hurt +us in particular. + +Here is an example of the kind of subtle case that I would be worried +about with a more complex rule (although this particular case works +out ok). Imagine the trait reference doesn't directly reference a +where clause, but the where clause plays a role in the winnowing +phase. Something like this: + +``` +pub trait Foo<T> { ... } +pub trait Bar { ... } +impl<U,T:Bar> Foo<U> for T { ... } // Impl A +impl Foo<char> for uint { ... } // Impl B +``` + +Now, in some function, we have no where clauses in scope, and we have +an obligation `$1 : Foo<$0>`. We might then conclude that `$0=char` +and `$1=uint`: this is because for impl A to apply, `uint:Bar` would +have to hold, and we know it does not or else the coherence check +would have failed. So we might enter into our global cache: `$1 : +Foo<$0> => Impl B`. Then we come along in a different scope, where a +generic type `A` is around with the bound `A:Bar`. Now suddenly the +impl is viable. + +The flaw in this imaginary DOOMSDAY SCENARIO is that we would not +currently conclude that `$1 : Foo<$0>` implies that `$0 == uint` and +`$1 == char`, even though it is true that (absent type parameters) +there is no other type the user could enter. However, it is not +*completely* implausible that we *could* draw this conclusion in the +future; we wouldn't have to guess types, in particular, we could be +led by the impls. + */ diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs index f923cf1e590..aa183dabaa0 100644 --- a/src/librustc/middle/traits/select.rs +++ b/src/librustc/middle/traits/select.rs @@ -844,19 +844,36 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { cache_skol_trait_ref: &Rc<ty::TraitRef>) -> &SelectionCache { + // High-level idea: we have to decide whether to consult the + // cache that is specific to this scope, or to consult the + // global cache. We want the cache that is specific to this + // scope whenever where clauses might affect the result. + // If the trait refers to any parameters in scope, then use - // the cache of the param-environment. This is because the - // result will depend on the where clauses that are in - // scope. Otherwise, use the generic tcx cache, since the - // result holds across all environments. + // the cache of the param-environment. if cache_skol_trait_ref.input_types().iter().any( |&t| ty::type_has_self(t) || ty::type_has_params(t)) { - &self.param_env.selection_cache - } else { - &self.tcx().selection_cache + return &self.param_env.selection_cache; } + + // If the trait refers to unbound type variables, and there + // are where clauses in scope, then use the local environment. + // If there are no where clauses in scope, which is a very + // common case, then we can use the global environment. + // See the discussion in doc.rs for more details. + if + !self.param_env.caller_obligations.is_empty() + && + cache_skol_trait_ref.input_types().iter().any( + |&t| ty::type_has_ty_infer(t)) + { + return &self.param_env.selection_cache; + } + + // Otherwise, we can use the global cache. + &self.tcx().selection_cache } fn check_candidate_cache(&mut self, @@ -1935,26 +1952,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { util::obligations_for_generics(self.tcx(), cause, recursion_depth, &impl_generics, impl_substs) } - - fn contains_skolemized_types(&self, - ty: ty::t) - -> bool - { - /*! - * True if the type contains skolemized variables. - */ - - let mut found_skol = false; - - ty::walk_ty(ty, |t| { - match ty::get(t).sty { - ty::ty_infer(ty::SkolemizedTy(_)) => { found_skol = true; } - _ => { } - } - }); - - found_skol - } } impl Repr for Candidate { diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs index a7ce93279bd..52ec97ab647 100644 --- a/src/librustc/middle/ty.rs +++ b/src/librustc/middle/ty.rs @@ -585,18 +585,18 @@ pub struct ctxt<'tcx> { pub repr_hint_cache: RefCell<DefIdMap<Rc<Vec<attr::ReprAttr>>>>, } -pub enum tbox_flag { - has_params = 1, - has_self = 2, - needs_infer = 4, - has_regions = 8, - has_ty_err = 16, - has_ty_bot = 32, - - // a meta-pub flag: subst may be required if the type has parameters, a self - // type, or references bound regions - needs_subst = 1 | 2 | 8 -} +// Flags that we track on types. These flags are propagated upwards +// through the type during type construction, so that we can quickly +// check whether the type has various kinds of types in it without +// recursing over the type itself. +const HAS_PARAMS: uint = 1; +const HAS_SELF: uint = 2; +const HAS_TY_INFER: uint = 4; +const HAS_RE_INFER: uint = 8; +const HAS_REGIONS: uint = 16; +const HAS_TY_ERR: uint = 32; +const HAS_TY_BOT: uint = 64; +const NEEDS_SUBST: uint = HAS_PARAMS | HAS_SELF | HAS_REGIONS; pub type t_box = &'static t_box_; @@ -631,15 +631,16 @@ pub fn get(t: t) -> t_box { } } -pub fn tbox_has_flag(tb: t_box, flag: tbox_flag) -> bool { - (tb.flags & (flag as uint)) != 0u +fn tbox_has_flag(tb: t_box, flag: uint) -> bool { + (tb.flags & flag) != 0u } pub fn type_has_params(t: t) -> bool { - tbox_has_flag(get(t), has_params) + tbox_has_flag(get(t), HAS_PARAMS) } -pub fn type_has_self(t: t) -> bool { tbox_has_flag(get(t), has_self) } +pub fn type_has_self(t: t) -> bool { tbox_has_flag(get(t), HAS_SELF) } +pub fn type_has_ty_infer(t: t) -> bool { tbox_has_flag(get(t), HAS_TY_INFER) } pub fn type_needs_infer(t: t) -> bool { - tbox_has_flag(get(t), needs_infer) + tbox_has_flag(get(t), HAS_TY_INFER | HAS_RE_INFER) } pub fn type_id(t: t) -> uint { get(t).id } @@ -910,13 +911,13 @@ mod primitives { pub static TY_BOT: t_box_ = t_box_ { sty: super::ty_bot, id: 16, - flags: super::has_ty_bot as uint, + flags: super::HAS_TY_BOT, }; pub static TY_ERR: t_box_ = t_box_ { sty: super::ty_err, id: 17, - flags: super::has_ty_err as uint, + flags: super::HAS_TY_ERR, }; pub const LAST_PRIMITIVE_ID: uint = 18; @@ -1579,9 +1580,9 @@ pub fn mk_t(cx: &ctxt, st: sty) -> t { let mut flags = 0u; fn rflags(r: Region) -> uint { - (has_regions as uint) | { + HAS_REGIONS | { match r { - ty::ReInfer(_) => needs_infer as uint, + ty::ReInfer(_) => HAS_RE_INFER, _ => 0u } } @@ -1610,22 +1611,22 @@ pub fn mk_t(cx: &ctxt, st: sty) -> t { &ty_str => {} // You might think that we could just return ty_err for // any type containing ty_err as a component, and get - // rid of the has_ty_err flag -- likewise for ty_bot (with + // rid of the HAS_TY_ERR flag -- likewise for ty_bot (with // the exception of function types that return bot). // But doing so caused sporadic memory corruption, and // neither I (tjc) nor nmatsakis could figure out why, // so we're doing it this way. - &ty_bot => flags |= has_ty_bot as uint, - &ty_err => flags |= has_ty_err as uint, + &ty_bot => flags |= HAS_TY_BOT, + &ty_err => flags |= HAS_TY_ERR, &ty_param(ref p) => { if p.space == subst::SelfSpace { - flags |= has_self as uint; + flags |= HAS_SELF; } else { - flags |= has_params as uint; + flags |= HAS_PARAMS; } } &ty_unboxed_closure(_, ref region) => flags |= rflags(*region), - &ty_infer(_) => flags |= needs_infer as uint, + &ty_infer(_) => flags |= HAS_TY_INFER, &ty_enum(_, ref substs) | &ty_struct(_, ref substs) => { flags |= sflags(substs); } @@ -1648,7 +1649,7 @@ pub fn mk_t(cx: &ctxt, st: sty) -> t { for a in f.sig.inputs.iter() { flags |= get(*a).flags; } flags |= get(f.sig.output).flags; // T -> _|_ is *not* _|_ ! - flags &= !(has_ty_bot as uint); + flags &= !HAS_TY_BOT; } &ty_closure(ref f) => { match f.store { @@ -1660,7 +1661,7 @@ pub fn mk_t(cx: &ctxt, st: sty) -> t { for a in f.sig.inputs.iter() { flags |= get(*a).flags; } flags |= get(f.sig.output).flags; // T -> _|_ is *not* _|_ ! - flags &= !(has_ty_bot as uint); + flags &= !HAS_TY_BOT; flags |= flags_for_bounds(&f.bounds); } } @@ -1979,15 +1980,15 @@ impl ItemSubsts { pub fn type_is_nil(ty: t) -> bool { get(ty).sty == ty_nil } pub fn type_is_bot(ty: t) -> bool { - (get(ty).flags & (has_ty_bot as uint)) != 0 + (get(ty).flags & HAS_TY_BOT) != 0 } pub fn type_is_error(ty: t) -> bool { - (get(ty).flags & (has_ty_err as uint)) != 0 + (get(ty).flags & HAS_TY_ERR) != 0 } pub fn type_needs_subst(ty: t) -> bool { - tbox_has_flag(get(ty), needs_subst) + tbox_has_flag(get(ty), NEEDS_SUBST) } pub fn trait_ref_contains_error(tref: &ty::TraitRef) -> bool { diff --git a/src/test/run-pass/trait-cache-issue-18209.rs b/src/test/run-pass/trait-cache-issue-18209.rs new file mode 100644 index 00000000000..a5efb32079d --- /dev/null +++ b/src/test/run-pass/trait-cache-issue-18209.rs @@ -0,0 +1,27 @@ +// 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. + +// Test that the cache results from the default method do not pollute +// the cache for the later call in `load()`. +// +// See issue #18209. + +pub trait Foo { + fn load_from() -> Box<Self>; + fn load() -> Box<Self> { + Foo::load_from() + } +} + +pub fn load<M: Foo>() -> Box<M> { + Foo::load() +} + +fn main() { } |