diff options
| -rw-r--r-- | src/librustc/middle/check_const.rs | 2 | ||||
| -rw-r--r-- | src/librustc/middle/traits/fulfill.rs | 72 | ||||
| -rw-r--r-- | src/librustc/middle/traits/mod.rs | 6 | ||||
| -rw-r--r-- | src/librustc/middle/traits/select.rs | 8 | ||||
| -rw-r--r-- | src/librustc/middle/ty.rs | 57 | ||||
| -rw-r--r-- | src/librustc_trans/trans/common.rs | 4 | ||||
| -rw-r--r-- | src/librustc_trans/trans/monomorphize.rs | 2 | ||||
| -rw-r--r-- | src/librustc_typeck/check/compare_method.rs | 4 | ||||
| -rw-r--r-- | src/librustc_typeck/check/mod.rs | 2 | ||||
| -rw-r--r-- | src/librustc_typeck/coherence/mod.rs | 2 |
10 files changed, 142 insertions, 17 deletions
diff --git a/src/librustc/middle/check_const.rs b/src/librustc/middle/check_const.rs index 125de300db1..d80eedf354a 100644 --- a/src/librustc/middle/check_const.rs +++ b/src/librustc/middle/check_const.rs @@ -285,7 +285,7 @@ impl<'a, 'tcx> CheckCrateVisitor<'a, 'tcx> { fn check_static_type(&self, e: &ast::Expr) { let ty = ty::node_id_to_type(self.tcx, e.id); let infcx = infer::new_infer_ctxt(self.tcx); - let mut fulfill_cx = traits::FulfillmentContext::new(); + let mut fulfill_cx = traits::FulfillmentContext::new(false); let cause = traits::ObligationCause::new(e.span, e.id, traits::SharedStatic); fulfill_cx.register_builtin_bound(&infcx, ty, ty::BoundSync, cause); let env = ty::empty_parameter_environment(self.tcx); diff --git a/src/librustc/middle/traits/fulfill.rs b/src/librustc/middle/traits/fulfill.rs index 80acb9bcc13..b9117745db2 100644 --- a/src/librustc/middle/traits/fulfill.rs +++ b/src/librustc/middle/traits/fulfill.rs @@ -28,6 +28,10 @@ use super::select::SelectionContext; use super::Unimplemented; use super::util::predicate_for_builtin_bound; +pub struct FulfilledPredicates<'tcx> { + set: HashSet<ty::Predicate<'tcx>> +} + /// The fulfillment context is used to drive trait resolution. It /// consists of a list of obligations that must be (eventually) /// satisfied. The job is to track which are satisfied, which yielded @@ -44,7 +48,7 @@ pub struct FulfillmentContext<'tcx> { // than the `SelectionCache`: it avoids duplicate errors and // permits recursive obligations, which are often generated from // traits like `Send` et al. - duplicate_set: HashSet<ty::Predicate<'tcx>>, + duplicate_set: FulfilledPredicates<'tcx>, // A list of all obligations that have been registered with this // fulfillment context. @@ -80,6 +84,8 @@ pub struct FulfillmentContext<'tcx> { // obligations (otherwise, it's easy to fail to walk to a // particular node-id). region_obligations: NodeMap<Vec<RegionObligation<'tcx>>>, + + errors_will_be_reported: bool, } #[derive(Clone)] @@ -90,12 +96,30 @@ pub struct RegionObligation<'tcx> { } impl<'tcx> FulfillmentContext<'tcx> { - pub fn new() -> FulfillmentContext<'tcx> { + /// Creates a new fulfillment context. + /// + /// `errors_will_be_reported` indicates whether ALL errors that + /// are generated by this fulfillment context will be reported to + /// the end user. This is used to inform caching, because it + /// allows us to conclude that traits that resolve successfully + /// will in fact always resolve successfully (in particular, it + /// guarantees that if some dependent obligation encounters a + /// problem, compilation will be aborted). If you're not sure of + /// the right value here, pass `false`, as that is the more + /// conservative option. + /// + /// FIXME -- a better option would be to hold back on modifying + /// the global cache until we know that all dependent obligations + /// are also satisfied. In that case, we could actually remove + /// this boolean flag, and we'd also avoid the problem of squelching + /// duplicate errors that occur across fns. + pub fn new(errors_will_be_reported: bool) -> FulfillmentContext<'tcx> { FulfillmentContext { - duplicate_set: HashSet::new(), + duplicate_set: FulfilledPredicates::new(), predicates: Vec::new(), attempted_mark: 0, region_obligations: NodeMap(), + errors_will_be_reported: errors_will_be_reported, } } @@ -165,7 +189,7 @@ impl<'tcx> FulfillmentContext<'tcx> { assert!(!obligation.has_escaping_regions()); - if !self.duplicate_set.insert(obligation.predicate.clone()) { + if self.is_duplicate_or_add(infcx.tcx, &obligation.predicate) { debug!("register_predicate({}) -- already seen, skip", obligation.repr(infcx.tcx)); return; } @@ -231,6 +255,28 @@ impl<'tcx> FulfillmentContext<'tcx> { &self.predicates } + fn is_duplicate_or_add(&mut self, tcx: &ty::ctxt<'tcx>, + predicate: &ty::Predicate<'tcx>) + -> bool { + // This is a kind of dirty hack to allow us to avoid "rederiving" + // things that we have already proven in other methods. + // + // The idea is that any predicate that doesn't involve type + // parameters and which only involves the 'static region (and + // no other regions) is universally solvable, since impls are global. + // + // This is particularly important since even if we have a + // cache hit in the selection context, we still wind up + // evaluating the 'nested obligations'. This cache lets us + // skip those. + + if self.errors_will_be_reported && predicate.is_global() { + tcx.fulfilled_predicates.borrow_mut().is_duplicate_or_add(predicate) + } else { + self.duplicate_set.is_duplicate_or_add(predicate) + } + } + /// 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<'a>(&mut self, @@ -442,3 +488,21 @@ fn register_region_obligation<'tcx>(tcx: &ty::ctxt<'tcx>, .push(region_obligation); } + +impl<'tcx> FulfilledPredicates<'tcx> { + pub fn new() -> FulfilledPredicates<'tcx> { + FulfilledPredicates { + set: HashSet::new() + } + } + + pub fn is_duplicate(&self, p: &ty::Predicate<'tcx>) -> bool { + self.set.contains(p) + } + + fn is_duplicate_or_add(&mut self, p: &ty::Predicate<'tcx>) -> bool { + !self.set.insert(p.clone()) + } +} + + diff --git a/src/librustc/middle/traits/mod.rs b/src/librustc/middle/traits/mod.rs index b371ede0397..138231b5995 100644 --- a/src/librustc/middle/traits/mod.rs +++ b/src/librustc/middle/traits/mod.rs @@ -32,7 +32,7 @@ pub use self::error_reporting::suggest_new_overflow_limit; pub use self::coherence::orphan_check; pub use self::coherence::overlapping_impls; pub use self::coherence::OrphanCheckErr; -pub use self::fulfill::{FulfillmentContext, RegionObligation}; +pub use self::fulfill::{FulfillmentContext, FulfilledPredicates, RegionObligation}; pub use self::project::MismatchedProjectionTypes; pub use self::project::normalize; pub use self::project::Normalized; @@ -315,7 +315,7 @@ pub fn evaluate_builtin_bound<'a,'tcx>(infcx: &InferCtxt<'a,'tcx>, ty.repr(infcx.tcx), bound); - let mut fulfill_cx = FulfillmentContext::new(); + let mut fulfill_cx = FulfillmentContext::new(false); // We can use a dummy node-id here because we won't pay any mind // to region obligations that arise (there shouldn't really be any @@ -460,7 +460,7 @@ pub fn fully_normalize<'a,'tcx,T>(infcx: &InferCtxt<'a,'tcx>, debug!("normalize_param_env(value={})", value.repr(tcx)); let mut selcx = &mut SelectionContext::new(infcx, closure_typer); - let mut fulfill_cx = FulfillmentContext::new(); + let mut fulfill_cx = FulfillmentContext::new(false); let Normalized { value: normalized_value, obligations } = project::normalize(selcx, cause, value); debug!("normalize_param_env: normalized_value={} obligations={}", diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs index 5d8cdd44eaa..307242d18df 100644 --- a/src/librustc/middle/traits/select.rs +++ b/src/librustc/middle/traits/select.rs @@ -435,6 +435,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { debug!("evaluate_predicate_recursively({})", obligation.repr(self.tcx())); + // Check the cache from the tcx of predicates that we know + // have been proven elsewhere. This cache only contains + // predicates that are global in scope and hence unaffected by + // the current environment. + if self.tcx().fulfilled_predicates.borrow().is_duplicate(&obligation.predicate) { + return EvaluatedToOk; + } + match obligation.predicate { ty::Predicate::Trait(ref t) => { assert!(!t.has_escaping_regions()); diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs index c24f1d3e7be..edd8f5ea6ea 100644 --- a/src/librustc/middle/ty.rs +++ b/src/librustc/middle/ty.rs @@ -753,6 +753,11 @@ pub struct ctxt<'tcx> { /// for things that do not have to do with the parameters in scope. pub selection_cache: traits::SelectionCache<'tcx>, + /// A set of predicates that have been fulfilled *somewhere*. + /// This is used to avoid duplicate work. Predicates are only + /// added to this set when they + pub fulfilled_predicates: RefCell<traits::FulfilledPredicates<'tcx>>, + /// Caches the representation hints for struct definitions. pub repr_hint_cache: RefCell<DefIdMap<Rc<Vec<attr::ReprAttr>>>>, @@ -815,6 +820,11 @@ bitflags! { const HAS_TY_ERR = 1 << 6, const HAS_PROJECTION = 1 << 7, const HAS_TY_CLOSURE = 1 << 8, + + // true if there are "names" of types and regions and so forth + // that are local to a particular fn + const HAS_LOCAL_NAMES = 1 << 8, + const NEEDS_SUBST = TypeFlags::HAS_PARAMS.bits | TypeFlags::HAS_SELF.bits | TypeFlags::HAS_RE_EARLY_BOUND.bits, @@ -830,7 +840,8 @@ bitflags! { TypeFlags::HAS_FREE_REGIONS.bits | TypeFlags::HAS_TY_ERR.bits | TypeFlags::HAS_PROJECTION.bits | - TypeFlags::HAS_TY_CLOSURE.bits, + TypeFlags::HAS_TY_CLOSURE.bits | + TypeFlags::HAS_LOCAL_NAMES.bits, // Caches for type_is_sized, type_moves_by_default const SIZEDNESS_CACHED = 1 << 16, @@ -986,6 +997,9 @@ pub fn type_has_ty_infer(ty: Ty) -> bool { pub fn type_needs_infer(ty: Ty) -> bool { ty.flags.get().intersects(TypeFlags::HAS_TY_INFER | TypeFlags::HAS_RE_INFER) } +pub fn type_is_global(ty: Ty) -> bool { + !ty.flags.get().intersects(TypeFlags::HAS_LOCAL_NAMES) +} pub fn type_has_projection(ty: Ty) -> bool { ty.flags.get().intersects(TypeFlags::HAS_PROJECTION) } @@ -1288,6 +1302,15 @@ pub struct UpvarBorrow { pub type UpvarCaptureMap = FnvHashMap<UpvarId, UpvarCapture>; impl Region { + pub fn is_global(&self) -> bool { + // does this represent a region that can be named in a global + // way? used in fulfillment caching. + match *self { + ty::ReStatic | ty::ReEmpty => true, + _ => false, + } + } + pub fn is_bound(&self) -> bool { match *self { ty::ReEarlyBound(..) => true, @@ -2022,6 +2045,29 @@ impl<'tcx> Predicate<'tcx> { Predicate::Projection(ty::Binder(data.subst(tcx, substs))), } } + + // Indicates whether this predicate references only 'global' + // types/lifetimes that are the same regardless of what fn we are + // in. This is used for caching. Errs on the side of returning + // false. + pub fn is_global(&self) -> bool { + match *self { + ty::Predicate::Trait(ref data) => { + let substs = data.skip_binder().trait_ref.substs; + + substs.types.iter().all(|t| ty::type_is_global(t)) && { + match substs.regions { + subst::ErasedRegions => true, + subst::NonerasedRegions(ref r) => r.iter().all(|r| r.is_global()), + } + } + } + + _ => { + false + } + } + } } #[derive(Clone, PartialEq, Eq, Hash, Debug)] @@ -2798,6 +2844,7 @@ pub fn mk_ctxt<'tcx>(s: Session, trait_defs: RefCell::new(DefIdMap()), predicates: RefCell::new(DefIdMap()), super_predicates: RefCell::new(DefIdMap()), + fulfilled_predicates: RefCell::new(traits::FulfilledPredicates::new()), map: map, freevars: freevars, tcache: RefCell::new(DefIdMap()), @@ -3010,6 +3057,7 @@ impl FlagComputation { } &TyParam(ref p) => { + self.add_flags(TypeFlags::HAS_LOCAL_NAMES); if p.space == subst::SelfSpace { self.add_flags(TypeFlags::HAS_SELF); } else { @@ -3018,11 +3066,12 @@ impl FlagComputation { } &TyClosure(_, substs) => { - self.add_flags(TypeFlags::HAS_TY_CLOSURE); + self.add_flags(TypeFlags::HAS_LOCAL_NAMES); self.add_substs(substs); } &TyInfer(_) => { + self.add_flags(TypeFlags::HAS_LOCAL_NAMES); // it might, right? self.add_flags(TypeFlags::HAS_TY_INFER) } @@ -3102,6 +3151,10 @@ impl FlagComputation { ty::ReStatic => {} _ => { self.add_flags(TypeFlags::HAS_FREE_REGIONS); } } + + if !r.is_global() { + self.add_flags(TypeFlags::HAS_LOCAL_NAMES); + } } fn add_projection_predicate(&mut self, projection_predicate: &ProjectionPredicate) { diff --git a/src/librustc_trans/trans/common.rs b/src/librustc_trans/trans/common.rs index 0f8fd45b05a..1cabeb26856 100644 --- a/src/librustc_trans/trans/common.rs +++ b/src/librustc_trans/trans/common.rs @@ -1041,7 +1041,7 @@ pub fn fulfill_obligation<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, // Currently, we use a fulfillment context to completely resolve // all nested obligations. This is because they can inform the // inference of the impl's type parameters. - let mut fulfill_cx = traits::FulfillmentContext::new(); + let mut fulfill_cx = traits::FulfillmentContext::new(true); let vtable = selection.map(|predicate| { fulfill_cx.register_predicate_obligation(&infcx, predicate); }); @@ -1069,7 +1069,7 @@ pub fn normalize_and_test_predicates<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, let infcx = infer::new_infer_ctxt(tcx); let typer = NormalizingClosureTyper::new(tcx); let mut selcx = traits::SelectionContext::new(&infcx, &typer); - let mut fulfill_cx = traits::FulfillmentContext::new(); + let mut fulfill_cx = traits::FulfillmentContext::new(false); let cause = traits::ObligationCause::dummy(); let traits::Normalized { value: predicates, obligations } = traits::normalize(&mut selcx, cause.clone(), &predicates); diff --git a/src/librustc_trans/trans/monomorphize.rs b/src/librustc_trans/trans/monomorphize.rs index b736ec3ccf4..e28dd77d5e5 100644 --- a/src/librustc_trans/trans/monomorphize.rs +++ b/src/librustc_trans/trans/monomorphize.rs @@ -337,7 +337,7 @@ pub fn normalize_associated_type<'tcx,T>(tcx: &ty::ctxt<'tcx>, value: &T) -> T result.repr(tcx), obligations.repr(tcx)); - let mut fulfill_cx = traits::FulfillmentContext::new(); + let mut fulfill_cx = traits::FulfillmentContext::new(true); for obligation in obligations { fulfill_cx.register_predicate_obligation(&infcx, obligation); } diff --git a/src/librustc_typeck/check/compare_method.rs b/src/librustc_typeck/check/compare_method.rs index b3267a5be49..c5861be2716 100644 --- a/src/librustc_typeck/check/compare_method.rs +++ b/src/librustc_typeck/check/compare_method.rs @@ -45,7 +45,7 @@ pub fn compare_impl_method<'tcx>(tcx: &ty::ctxt<'tcx>, impl_trait_ref.repr(tcx)); let infcx = infer::new_infer_ctxt(tcx); - let mut fulfillment_cx = traits::FulfillmentContext::new(); + let mut fulfillment_cx = traits::FulfillmentContext::new(true); let trait_to_impl_substs = &impl_trait_ref.substs; @@ -422,7 +422,7 @@ pub fn compare_const_impl<'tcx>(tcx: &ty::ctxt<'tcx>, impl_trait_ref.repr(tcx)); let infcx = infer::new_infer_ctxt(tcx); - let mut fulfillment_cx = traits::FulfillmentContext::new(); + let mut fulfillment_cx = traits::FulfillmentContext::new(true); // The below is for the most part highly similar to the procedure // for methods above. It is simpler in many respects, especially diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs index 69f1b5091df..9df0d4aa56b 100644 --- a/src/librustc_typeck/check/mod.rs +++ b/src/librustc_typeck/check/mod.rs @@ -386,7 +386,7 @@ impl<'a, 'tcx> Inherited<'a, 'tcx> { closure_tys: RefCell::new(DefIdMap()), closure_kinds: RefCell::new(DefIdMap()), fn_sig_map: RefCell::new(NodeMap()), - fulfillment_cx: RefCell::new(traits::FulfillmentContext::new()), + fulfillment_cx: RefCell::new(traits::FulfillmentContext::new(true)), deferred_call_resolutions: RefCell::new(DefIdMap()), deferred_cast_checks: RefCell::new(Vec::new()), } diff --git a/src/librustc_typeck/coherence/mod.rs b/src/librustc_typeck/coherence/mod.rs index f6a40eec582..cd7be46f9e0 100644 --- a/src/librustc_typeck/coherence/mod.rs +++ b/src/librustc_typeck/coherence/mod.rs @@ -539,7 +539,7 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> { } }; - let mut fulfill_cx = traits::FulfillmentContext::new(); + let mut fulfill_cx = traits::FulfillmentContext::new(true); // Register an obligation for `A: Trait<B>`. let cause = traits::ObligationCause::misc(span, impl_did.node); |