diff options
| -rw-r--r-- | src/librustc/lib.rs | 1 | ||||
| -rw-r--r-- | src/librustc/middle/fast_reject.rs | 103 | ||||
| -rw-r--r-- | src/librustc/middle/typeck/check/method/probe.rs | 49 |
3 files changed, 148 insertions, 5 deletions
diff --git a/src/librustc/lib.rs b/src/librustc/lib.rs index ce736a344d5..c9a1d47f558 100644 --- a/src/librustc/lib.rs +++ b/src/librustc/lib.rs @@ -87,6 +87,7 @@ pub mod middle { pub mod effect; pub mod entry; pub mod expr_use_visitor; + pub mod fast_reject; pub mod graph; pub mod intrinsicck; pub mod lang_items; diff --git a/src/librustc/middle/fast_reject.rs b/src/librustc/middle/fast_reject.rs new file mode 100644 index 00000000000..915f12cd393 --- /dev/null +++ b/src/librustc/middle/fast_reject.rs @@ -0,0 +1,103 @@ +// 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 middle::ty; +use syntax::ast; + +/** See `simplify_type */ +#[deriving(Clone, PartialEq, Eq, Hash)] +pub enum SimplifiedType { + BoolSimplifiedType, + CharSimplifiedType, + IntSimplifiedType(ast::IntTy), + UintSimplifiedType(ast::UintTy), + FloatSimplifiedType(ast::FloatTy), + EnumSimplifiedType(ast::DefId), + StrSimplifiedType, + VecSimplifiedType, + PtrSimplifiedType, + TupleSimplifiedType(uint), + TraitSimplifiedType(ast::DefId), + StructSimplifiedType(ast::DefId), + UnboxedClosureSimplifiedType(ast::DefId), + FunctionSimplifiedType(uint), + ParameterSimplifiedType, +} + +pub fn simplify_type(tcx: &ty::ctxt, + ty: ty::t, + can_simplify_params: bool) + -> Option<SimplifiedType> +{ + /*! + * Tries to simplify a type by dropping type parameters, deref'ing + * away any reference types, etc. The idea is to get something + * simple that we can use to quickly decide if two types could + * unify during method lookup. + * + * If `can_simplify_params` is false, then we will fail to + * simplify type parameters entirely. This is useful when those + * type parameters would be instantiated with fresh type + * variables, since then we can't say much about whether two types + * would unify. Put another way, `can_simplify_params` should be + * true if type parameters appear free in `ty` and `false` if they + * are to be considered bound. + */ + + match ty::get(ty).sty { + ty::ty_bool => Some(BoolSimplifiedType), + ty::ty_char => Some(CharSimplifiedType), + ty::ty_int(int_type) => Some(IntSimplifiedType(int_type)), + ty::ty_uint(uint_type) => Some(UintSimplifiedType(uint_type)), + ty::ty_float(float_type) => Some(FloatSimplifiedType(float_type)), + ty::ty_enum(def_id, _) => Some(EnumSimplifiedType(def_id)), + ty::ty_str => Some(StrSimplifiedType), + ty::ty_vec(..) => Some(VecSimplifiedType), + ty::ty_ptr(_) => Some(PtrSimplifiedType), + ty::ty_trait(ref trait_info) => { + Some(TraitSimplifiedType(trait_info.principal.def_id)) + } + ty::ty_struct(def_id, _) => { + Some(StructSimplifiedType(def_id)) + } + ty::ty_rptr(_, mt) => { + // since we introduce auto-refs during method lookup, we + // just treat &T and T as equivalent from the point of + // view of possibly unifying + simplify_type(tcx, mt.ty, can_simplify_params) + } + ty::ty_uniq(_) => { + // treat like we would treat `Box` + let def_id = tcx.lang_items.owned_box().unwrap(); + Some(StructSimplifiedType(def_id)) + } + ty::ty_unboxed_closure(def_id, _, _) => { + Some(UnboxedClosureSimplifiedType(def_id)) + } + ty::ty_tup(ref tys) => { + Some(TupleSimplifiedType(tys.len())) + } + ty::ty_closure(ref f) => { + Some(FunctionSimplifiedType(f.sig.inputs.len())) + } + ty::ty_bare_fn(ref f) => { + Some(FunctionSimplifiedType(f.sig.inputs.len())) + } + ty::ty_param(_) => { + if can_simplify_params { + Some(ParameterSimplifiedType) + } else { + None + } + } + ty::ty_open(_) | ty::ty_infer(_) | ty::ty_err => None, + } +} + diff --git a/src/librustc/middle/typeck/check/method/probe.rs b/src/librustc/middle/typeck/check/method/probe.rs index d28402b0530..bc46b975cdb 100644 --- a/src/librustc/middle/typeck/check/method/probe.rs +++ b/src/librustc/middle/typeck/check/method/probe.rs @@ -16,6 +16,7 @@ use super::MethodIndex; use super::NoMatch; use super::TraitSource; +use middle::fast_reject; use middle::subst; use middle::subst::Subst; use middle::traits; @@ -36,6 +37,7 @@ struct ProbeContext<'a, 'tcx:'a> { span: Span, method_name: ast::Name, steps: Rc<Vec<CandidateStep>>, + opt_simplified_steps: Option<Vec<fast_reject::SimplifiedType>>, inherent_candidates: Vec<Candidate>, extension_candidates: Vec<Candidate>, impl_dups: HashSet<ast::DefId>, @@ -44,7 +46,7 @@ struct ProbeContext<'a, 'tcx:'a> { struct CandidateStep { self_ty: ty::t, - adjustment: PickAdjustment + adjustment: PickAdjustment, } struct Candidate { @@ -123,16 +125,31 @@ pub fn probe(fcx: &FnCtxt, // take place in the `fcx.infcx().probe` below. let steps = create_steps(fcx, span, self_ty); + // Create a list of simplified self types, if we can. + let mut simplified_steps = Vec::new(); + for step in steps.iter() { + match fast_reject::simplify_type(fcx.tcx(), step.self_ty, true) { + None => { break; } + Some(simplified_type) => { simplified_steps.push(simplified_type); } + } + } + let opt_simplified_steps = + if simplified_steps.len() < steps.len() { + None // failed to convert at least one of the steps + } else { + Some(simplified_steps) + }; + debug!("ProbeContext: steps for self_ty={} are {}", self_ty.repr(fcx.tcx()), steps.repr(fcx.tcx())); // this creates one big transaction so that all type variables etc // that we create during the probe process are removed later - let mut steps = Some(steps); // FIXME(#18101) need once closures + let mut dummy = Some((steps, opt_simplified_steps)); // FIXME(#18101) need once closures fcx.infcx().probe(|| { - let steps = steps.take().unwrap(); - let mut probe_cx = ProbeContext::new(fcx, span, method_name, steps); + let (steps, opt_simplified_steps) = dummy.take().unwrap(); + let mut probe_cx = ProbeContext::new(fcx, span, method_name, steps, opt_simplified_steps); probe_cx.assemble_inherent_candidates(); probe_cx.assemble_extension_candidates_for_traits_in_scope(call_expr_id); probe_cx.pick() @@ -177,7 +194,8 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> { fn new(fcx: &'a FnCtxt<'a,'tcx>, span: Span, method_name: ast::Name, - steps: Vec<CandidateStep>) + steps: Vec<CandidateStep>, + opt_simplified_steps: Option<Vec<fast_reject::SimplifiedType>>) -> ProbeContext<'a,'tcx> { ProbeContext { @@ -188,6 +206,7 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> { extension_candidates: Vec::new(), impl_dups: HashSet::new(), steps: Rc::new(steps), + opt_simplified_steps: opt_simplified_steps, static_candidates: Vec::new(), } } @@ -473,6 +492,10 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> { trait_def_id.repr(self.tcx()), impl_def_id.repr(self.tcx())); + if !self.impl_can_possibly_match(impl_def_id) { + continue; + } + let impl_pty = check::impl_self_ty(self.fcx, self.span, impl_def_id); let impl_substs = impl_pty.substs; @@ -499,6 +522,22 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> { } } + fn impl_can_possibly_match(&self, impl_def_id: ast::DefId) -> bool { + let simplified_steps = match self.opt_simplified_steps { + Some(ref simplified_steps) => simplified_steps, + None => { return true; } + }; + + let impl_type = ty::lookup_item_type(self.tcx(), impl_def_id); + let impl_simplified_type = + match fast_reject::simplify_type(self.tcx(), impl_type.ty, false) { + Some(simplified_type) => simplified_type, + None => { return true; } + }; + + simplified_steps.contains(&impl_simplified_type) + } + fn assemble_unboxed_closure_candidates(&mut self, trait_def_id: ast::DefId, method_ty: Rc<ty::Method>, |