diff options
34 files changed, 431 insertions, 335 deletions
diff --git a/src/librustc/metadata/csearch.rs b/src/librustc/metadata/csearch.rs index 93056d949db..7132ac4895a 100644 --- a/src/librustc/metadata/csearch.rs +++ b/src/librustc/metadata/csearch.rs @@ -283,7 +283,7 @@ pub fn get_impl_polarity<'tcx>(tcx: &ty::ctxt<'tcx>, // if there is one. pub fn get_impl_trait<'tcx>(tcx: &ty::ctxt<'tcx>, def: ast::DefId) - -> Option<Rc<ty::TraitRef<'tcx>>> { + -> Option<ty::TraitRef<'tcx>> { let cstore = &tcx.sess.cstore; let cdata = cstore.get_crate_data(def.krate); decoder::get_impl_trait(&*cdata, def.node, tcx) diff --git a/src/librustc/metadata/decoder.rs b/src/librustc/metadata/decoder.rs index f03a2d342d7..00fc42341c3 100644 --- a/src/librustc/metadata/decoder.rs +++ b/src/librustc/metadata/decoder.rs @@ -30,7 +30,9 @@ use middle::subst; use middle::ty::{ImplContainer, TraitContainer}; use middle::ty::{self, Ty}; use middle::astencode::vtable_decoder_helpers; +use util::nodemap::FnvHashMap; +use std::cell::{Cell, RefCell}; use std::collections::HashMap; use std::hash::{self, Hash, SipHasher}; use std::io::prelude::*; @@ -247,13 +249,13 @@ pub fn item_type<'tcx>(_item_id: ast::DefId, item: rbml::Doc, } fn doc_trait_ref<'tcx>(doc: rbml::Doc, tcx: &ty::ctxt<'tcx>, cdata: Cmd) - -> Rc<ty::TraitRef<'tcx>> { + -> ty::TraitRef<'tcx> { parse_trait_ref_data(doc.data, cdata.cnum, doc.start, tcx, |_, did| translate_def_id(cdata, did)) } fn item_trait_ref<'tcx>(doc: rbml::Doc, tcx: &ty::ctxt<'tcx>, cdata: Cmd) - -> Rc<ty::TraitRef<'tcx>> { + -> ty::TraitRef<'tcx> { let tp = reader::get_doc(doc, tag_item_trait_ref); doc_trait_ref(tp, tcx, cdata) } @@ -420,6 +422,9 @@ pub fn get_trait_def<'tcx>(cdata: Cmd, generics: generics, trait_ref: item_trait_ref(item_doc, tcx, cdata), associated_type_names: associated_type_names, + nonblanket_impls: RefCell::new(FnvHashMap()), + blanket_impls: RefCell::new(vec![]), + flags: Cell::new(ty::TraitFlags::NO_TRAIT_FLAGS) } } @@ -490,7 +495,7 @@ pub fn get_impl_polarity<'tcx>(cdata: Cmd, pub fn get_impl_trait<'tcx>(cdata: Cmd, id: ast::NodeId, tcx: &ty::ctxt<'tcx>) - -> Option<Rc<ty::TraitRef<'tcx>>> + -> Option<ty::TraitRef<'tcx>> { let item_doc = lookup_item(id, cdata.data()); let fam = item_family(item_doc); diff --git a/src/librustc/metadata/encoder.rs b/src/librustc/metadata/encoder.rs index bcbb350fc34..90dd452e06b 100644 --- a/src/librustc/metadata/encoder.rs +++ b/src/librustc/metadata/encoder.rs @@ -103,7 +103,7 @@ struct entry<T> { fn encode_trait_ref<'a, 'tcx>(rbml_w: &mut Encoder, ecx: &EncodeContext<'a, 'tcx>, - trait_ref: &ty::TraitRef<'tcx>, + trait_ref: ty::TraitRef<'tcx>, tag: usize) { let ty_str_ctxt = &tyencode::ctxt { diag: ecx.diag, @@ -191,7 +191,7 @@ pub fn write_trait_ref<'a, 'tcx>(ecx: &EncodeContext<'a, 'tcx>, tcx: ecx.tcx, abbrevs: &ecx.type_abbrevs }; - tyencode::enc_trait_ref(rbml_w, ty_str_ctxt, trait_ref); + tyencode::enc_trait_ref(rbml_w, ty_str_ctxt, *trait_ref); } pub fn write_region(ecx: &EncodeContext, @@ -974,16 +974,14 @@ fn encode_inherent_implementations(ecx: &EncodeContext, fn encode_extension_implementations(ecx: &EncodeContext, rbml_w: &mut Encoder, trait_def_id: DefId) { - match ecx.tcx.trait_impls.borrow().get(&trait_def_id) { - None => {} - Some(implementations) => { - for &impl_def_id in &*implementations.borrow() { - rbml_w.start_tag(tag_items_data_item_extension_impl); - encode_def_id(rbml_w, impl_def_id); - rbml_w.end_tag(); - } - } - } + assert!(ast_util::is_local(trait_def_id)); + let def = ty::lookup_trait_def(ecx.tcx, trait_def_id); + + def.for_each_impl(ecx.tcx, |impl_def_id| { + rbml_w.start_tag(tag_items_data_item_extension_impl); + encode_def_id(rbml_w, impl_def_id); + rbml_w.end_tag(); + }); } fn encode_stability(rbml_w: &mut Encoder, stab_opt: Option<attr::Stability>) { @@ -1201,7 +1199,7 @@ fn encode_info_for_item(ecx: &EncodeContext, encode_unsafety(rbml_w, unsafety); let trait_ref = ty::impl_id_to_trait_ref(tcx, item.id); - encode_trait_ref(rbml_w, ecx, &*trait_ref, tag_item_trait_ref); + encode_trait_ref(rbml_w, ecx, trait_ref, tag_item_trait_ref); rbml_w.end_tag(); } ast::ItemImpl(unsafety, polarity, _, ref opt_trait, ref ty, ref ast_items) => { @@ -1246,7 +1244,7 @@ fn encode_info_for_item(ecx: &EncodeContext, } if opt_trait.is_some() { let trait_ref = ty::impl_id_to_trait_ref(tcx, item.id); - encode_trait_ref(rbml_w, ecx, &*trait_ref, tag_item_trait_ref); + encode_trait_ref(rbml_w, ecx, trait_ref, tag_item_trait_ref); } encode_path(rbml_w, path.clone()); encode_stability(rbml_w, stab); @@ -1314,7 +1312,7 @@ fn encode_info_for_item(ecx: &EncodeContext, tag_item_generics); encode_predicates(rbml_w, ecx, &ty::lookup_super_predicates(tcx, def_id), tag_item_super_predicates); - encode_trait_ref(rbml_w, ecx, &*trait_def.trait_ref, tag_item_trait_ref); + encode_trait_ref(rbml_w, ecx, trait_def.trait_ref, tag_item_trait_ref); encode_name(rbml_w, item.ident.name); encode_attributes(rbml_w, &item.attrs); encode_visibility(rbml_w, vis); diff --git a/src/librustc/metadata/tydecode.rs b/src/librustc/metadata/tydecode.rs index 955905ee263..223a5eef614 100644 --- a/src/librustc/metadata/tydecode.rs +++ b/src/librustc/metadata/tydecode.rs @@ -23,7 +23,6 @@ use middle::subst; use middle::subst::VecPerParamSpace; use middle::ty::{self, AsPredicate, Ty}; -use std::rc::Rc; use std::str; use syntax::abi; use syntax::ast; @@ -182,7 +181,7 @@ pub fn parse_bare_fn_ty_data<'tcx, F>(data: &[u8], crate_num: ast::CrateNum, pos pub fn parse_trait_ref_data<'tcx, F>(data: &[u8], crate_num: ast::CrateNum, pos: usize, tcx: &ty::ctxt<'tcx>, conv: F) - -> Rc<ty::TraitRef<'tcx>> where + -> ty::TraitRef<'tcx> where F: FnMut(DefIdSource, ast::DefId) -> ast::DefId, { debug!("parse_trait_ref_data {}", data_log_string(data, pos)); @@ -434,19 +433,19 @@ fn parse_str(st: &mut PState, term: char) -> String { } fn parse_trait_ref<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, mut conv: F) - -> Rc<ty::TraitRef<'tcx>> where + -> ty::TraitRef<'tcx> where F: FnMut(DefIdSource, ast::DefId) -> ast::DefId, { parse_trait_ref_(st, &mut conv) } fn parse_trait_ref_<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, conv: &mut F) - -> Rc<ty::TraitRef<'tcx>> where + -> ty::TraitRef<'tcx> where F: FnMut(DefIdSource, ast::DefId) -> ast::DefId, { let def = parse_def_(st, NominalType, conv); let substs = st.tcx.mk_substs(parse_substs_(st, conv)); - Rc::new(ty::TraitRef {def_id: def, substs: substs}) + ty::TraitRef {def_id: def, substs: substs} } fn parse_ty<'a, 'tcx, F>(st: &mut PState<'a, 'tcx>, mut conv: F) -> Ty<'tcx> where diff --git a/src/librustc/metadata/tyencode.rs b/src/librustc/metadata/tyencode.rs index 8a278811282..f5f520720c6 100644 --- a/src/librustc/metadata/tyencode.rs +++ b/src/librustc/metadata/tyencode.rs @@ -94,7 +94,7 @@ pub fn enc_ty<'a, 'tcx>(w: &mut Encoder, cx: &ctxt<'a, 'tcx>, t: Ty<'tcx>) { ty::ty_trait(box ty::TyTrait { ref principal, ref bounds }) => { mywrite!(w, "x["); - enc_trait_ref(w, cx, &*principal.0); + enc_trait_ref(w, cx, principal.0); enc_existential_bounds(w, cx, bounds); mywrite!(w, "]"); } @@ -149,7 +149,7 @@ pub fn enc_ty<'a, 'tcx>(w: &mut Encoder, cx: &ctxt<'a, 'tcx>, t: Ty<'tcx>) { } ty::ty_projection(ref data) => { mywrite!(w, "P["); - enc_trait_ref(w, cx, &*data.trait_ref); + enc_trait_ref(w, cx, data.trait_ref); mywrite!(w, "{}]", token::get_name(data.item_name)); } ty::ty_err => { @@ -309,7 +309,7 @@ fn enc_bound_region(w: &mut Encoder, cx: &ctxt, br: ty::BoundRegion) { } pub fn enc_trait_ref<'a, 'tcx>(w: &mut Encoder, cx: &ctxt<'a, 'tcx>, - s: &ty::TraitRef<'tcx>) { + s: ty::TraitRef<'tcx>) { mywrite!(w, "{}|", (cx.ds)(s.def_id)); enc_substs(w, cx, s.substs); } @@ -394,7 +394,7 @@ pub fn enc_bounds<'a, 'tcx>(w: &mut Encoder, cx: &ctxt<'a, 'tcx>, for tp in &bs.trait_bounds { mywrite!(w, "I"); - enc_trait_ref(w, cx, &*tp.0); + enc_trait_ref(w, cx, tp.0); } for tp in &bs.projection_bounds { @@ -446,7 +446,7 @@ pub fn enc_predicate<'a, 'tcx>(w: &mut Encoder, match *p { ty::Predicate::Trait(ref trait_ref) => { mywrite!(w, "t"); - enc_trait_ref(w, cx, &*trait_ref.0.trait_ref); + enc_trait_ref(w, cx, trait_ref.0.trait_ref); } ty::Predicate::Equate(ty::Binder(ty::EquatePredicate(a, b))) => { mywrite!(w, "e"); @@ -473,7 +473,7 @@ pub fn enc_predicate<'a, 'tcx>(w: &mut Encoder, fn enc_projection_predicate<'a, 'tcx>(w: &mut Encoder, cx: &ctxt<'a, 'tcx>, data: &ty::ProjectionPredicate<'tcx>) { - enc_trait_ref(w, cx, &*data.projection_ty.trait_ref); + enc_trait_ref(w, cx, data.projection_ty.trait_ref); mywrite!(w, "{}|", token::get_name(data.projection_ty.item_name)); enc_ty(w, cx, data.ty); } diff --git a/src/librustc/middle/astencode.rs b/src/librustc/middle/astencode.rs index 3ef22ba8158..4bfc4c5b850 100644 --- a/src/librustc/middle/astencode.rs +++ b/src/librustc/middle/astencode.rs @@ -41,7 +41,6 @@ use syntax; use std::cell::Cell; use std::io::SeekFrom; use std::io::prelude::*; -use std::rc::Rc; use std::fmt::Debug; use rbml::reader; @@ -890,7 +889,7 @@ impl<'a, 'tcx> rbml_writer_helpers<'tcx> for Encoder<'a> { this.emit_enum_variant("MethodTypeParam", 2, 1, |this| { this.emit_struct("MethodParam", 2, |this| { try!(this.emit_struct_field("trait_ref", 0, |this| { - Ok(this.emit_trait_ref(ecx, &*p.trait_ref)) + Ok(this.emit_trait_ref(ecx, &p.trait_ref)) })); try!(this.emit_struct_field("method_num", 0, |this| { this.emit_uint(p.method_num) @@ -914,7 +913,7 @@ impl<'a, 'tcx> rbml_writer_helpers<'tcx> for Encoder<'a> { this.emit_enum_variant("MethodTraitObject", 3, 1, |this| { this.emit_struct("MethodObject", 2, |this| { try!(this.emit_struct_field("trait_ref", 0, |this| { - Ok(this.emit_trait_ref(ecx, &*o.trait_ref)) + Ok(this.emit_trait_ref(ecx, &o.trait_ref)) })); try!(this.emit_struct_field("object_trait_id", 0, |this| { Ok(this.emit_def_id(o.object_trait_id)) @@ -1208,7 +1207,7 @@ fn encode_side_tables_for_id(ecx: &e::EncodeContext, if let Some(trait_ref) = tcx.object_cast_map.borrow().get(&id) { rbml_w.tag(c::tag_table_object_cast_map, |rbml_w| { rbml_w.id(id); - rbml_w.emit_trait_ref(ecx, &*trait_ref.0); + rbml_w.emit_trait_ref(ecx, &trait_ref.0); }) } @@ -1275,7 +1274,7 @@ trait rbml_decoder_decoder_helpers<'tcx> { fn read_ty<'a, 'b>(&mut self, dcx: &DecodeContext<'a, 'b, 'tcx>) -> Ty<'tcx>; fn read_tys<'a, 'b>(&mut self, dcx: &DecodeContext<'a, 'b, 'tcx>) -> Vec<Ty<'tcx>>; fn read_trait_ref<'a, 'b>(&mut self, dcx: &DecodeContext<'a, 'b, 'tcx>) - -> Rc<ty::TraitRef<'tcx>>; + -> ty::TraitRef<'tcx>; fn read_poly_trait_ref<'a, 'b>(&mut self, dcx: &DecodeContext<'a, 'b, 'tcx>) -> ty::PolyTraitRef<'tcx>; fn read_type_param_def<'a, 'b>(&mut self, dcx: &DecodeContext<'a, 'b, 'tcx>) @@ -1469,7 +1468,7 @@ impl<'a, 'tcx> rbml_decoder_decoder_helpers<'tcx> for reader::Decoder<'a> { } fn read_trait_ref<'b, 'c>(&mut self, dcx: &DecodeContext<'b, 'c, 'tcx>) - -> Rc<ty::TraitRef<'tcx>> { + -> ty::TraitRef<'tcx> { self.read_opaque(|this, doc| { let ty = tydecode::parse_trait_ref_data( doc.data, diff --git a/src/librustc/middle/const_eval.rs b/src/librustc/middle/const_eval.rs index 916874f1c51..091092e3b60 100644 --- a/src/librustc/middle/const_eval.rs +++ b/src/librustc/middle/const_eval.rs @@ -942,8 +942,8 @@ fn resolve_trait_associated_const<'a, 'tcx: 'a>(tcx: &'a ty::ctxt<'tcx>, let trait_substs = tcx.mk_substs(trait_substs); debug!("resolve_trait_associated_const: trait_substs={}", trait_substs.repr(tcx)); - let trait_ref = ty::Binder(Rc::new(ty::TraitRef { def_id: trait_id, - substs: trait_substs })); + let trait_ref = ty::Binder(ty::TraitRef { def_id: trait_id, + substs: trait_substs }); ty::populate_implementations_for_trait_if_necessary(tcx, trait_ref.def_id()); let infcx = infer::new_infer_ctxt(tcx); diff --git a/src/librustc/middle/implicator.rs b/src/librustc/middle/implicator.rs index 0d6a1df7237..86deca0c144 100644 --- a/src/librustc/middle/implicator.rs +++ b/src/librustc/middle/implicator.rs @@ -16,7 +16,6 @@ use middle::traits; use middle::ty::{self, RegionEscape, ToPolyTraitRef, Ty}; use middle::ty_fold::{TypeFoldable, TypeFolder}; -use std::rc::Rc; use syntax::ast; use syntax::codemap::Span; @@ -324,7 +323,7 @@ impl<'a, 'tcx> Implicator<'a, 'tcx> { } fn accumulate_from_assoc_types(&mut self, - trait_ref: Rc<ty::TraitRef<'tcx>>) + trait_ref: ty::TraitRef<'tcx>) { debug!("accumulate_from_assoc_types({})", trait_ref.repr(self.tcx())); @@ -442,7 +441,7 @@ pub fn object_region_bounds<'tcx>( // Note that we preserve the overall binding levels here. assert!(!open_ty.has_escaping_regions()); let substs = tcx.mk_substs(principal.0.substs.with_self_ty(open_ty)); - let trait_refs = vec!(ty::Binder(Rc::new(ty::TraitRef::new(principal.0.def_id, substs)))); + let trait_refs = vec!(ty::Binder(ty::TraitRef::new(principal.0.def_id, substs))); let param_bounds = ty::ParamBounds { region_bounds: Vec::new(), diff --git a/src/librustc/middle/infer/error_reporting.rs b/src/librustc/middle/infer/error_reporting.rs index 22e3376e09e..8aca64484bf 100644 --- a/src/librustc/middle/infer/error_reporting.rs +++ b/src/librustc/middle/infer/error_reporting.rs @@ -79,7 +79,6 @@ use middle::ty::{self, Ty}; use middle::ty::{Region, ReFree}; use std::cell::{Cell, RefCell}; use std::char::from_u32; -use std::rc::Rc; use std::string::String; use syntax::ast; use syntax::ast_map; @@ -1680,13 +1679,13 @@ impl<'tcx> Resolvable<'tcx> for Ty<'tcx> { } } -impl<'tcx> Resolvable<'tcx> for Rc<ty::TraitRef<'tcx>> { +impl<'tcx> Resolvable<'tcx> for ty::TraitRef<'tcx> { fn resolve<'a>(&self, infcx: &InferCtxt<'a, 'tcx>) - -> Rc<ty::TraitRef<'tcx>> { - Rc::new(infcx.resolve_type_vars_if_possible(&**self)) + -> ty::TraitRef<'tcx> { + infcx.resolve_type_vars_if_possible(self) } fn contains_error(&self) -> bool { - ty::trait_ref_contains_error(&**self) + ty::trait_ref_contains_error(self) } } @@ -1699,7 +1698,7 @@ impl<'tcx> Resolvable<'tcx> for ty::PolyTraitRef<'tcx> { } fn contains_error(&self) -> bool { - ty::trait_ref_contains_error(&*self.0) + ty::trait_ref_contains_error(&self.0) } } diff --git a/src/librustc/middle/infer/mod.rs b/src/librustc/middle/infer/mod.rs index 63e4a5c8a2a..b802f46e285 100644 --- a/src/librustc/middle/infer/mod.rs +++ b/src/librustc/middle/infer/mod.rs @@ -33,7 +33,6 @@ use middle::ty_relate::{Relate, RelateResult, TypeRelation}; use rustc_data_structures::unify::{self, UnificationTable}; use std::cell::{RefCell}; use std::fmt; -use std::rc::Rc; use syntax::ast; use syntax::codemap; use syntax::codemap::Span; @@ -155,7 +154,7 @@ impl fmt::Display for TypeOrigin { #[derive(Clone, Debug)] pub enum ValuePairs<'tcx> { Types(ty::expected_found<Ty<'tcx>>), - TraitRefs(ty::expected_found<Rc<ty::TraitRef<'tcx>>>), + TraitRefs(ty::expected_found<ty::TraitRef<'tcx>>), PolyTraitRefs(ty::expected_found<ty::PolyTraitRef<'tcx>>), } @@ -663,8 +662,8 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> { pub fn sub_trait_refs(&self, a_is_expected: bool, origin: TypeOrigin, - a: Rc<ty::TraitRef<'tcx>>, - b: Rc<ty::TraitRef<'tcx>>) + a: ty::TraitRef<'tcx>, + b: ty::TraitRef<'tcx>) -> UnitResult<'tcx> { debug!("sub_trait_refs({} <: {})", @@ -675,7 +674,7 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> { origin: origin, values: TraitRefs(expected_found(a_is_expected, a.clone(), b.clone())) }; - self.sub(a_is_expected, trace).relate(&*a, &*b).map(|_| ()) + self.sub(a_is_expected, trace).relate(&a, &b).map(|_| ()) }) } @@ -873,8 +872,8 @@ impl<'a, 'tcx> InferCtxt<'a, 'tcx> { format!("({})", tstrs.connect(", ")) } - pub fn trait_ref_to_string(&self, t: &Rc<ty::TraitRef<'tcx>>) -> String { - let t = self.resolve_type_vars_if_possible(&**t); + pub fn trait_ref_to_string(&self, t: &ty::TraitRef<'tcx>) -> String { + let t = self.resolve_type_vars_if_possible(t); t.user_string(self.tcx) } diff --git a/src/librustc/middle/traits/coherence.rs b/src/librustc/middle/traits/coherence.rs index d21891ab23f..d9f8a88fddc 100644 --- a/src/librustc/middle/traits/coherence.rs +++ b/src/librustc/middle/traits/coherence.rs @@ -20,7 +20,6 @@ use super::util; use middle::subst::{Subst, Substs, TypeSpace}; use middle::ty::{self, ToPolyTraitRef, Ty}; use middle::infer::{self, InferCtxt}; -use std::rc::Rc; use syntax::ast; use syntax::codemap::{DUMMY_SP, Span}; use util::ppaux::Repr; @@ -139,7 +138,7 @@ type SubstsFn = for<'a,'tcx> fn(infcx: &InferCtxt<'a, 'tcx>, fn impl_trait_ref_and_oblig<'a,'tcx>(selcx: &mut SelectionContext<'a,'tcx>, impl_def_id: ast::DefId, substs_fn: SubstsFn) - -> (Rc<ty::TraitRef<'tcx>>, + -> (ty::TraitRef<'tcx>, Vec<PredicateObligation<'tcx>>) { let impl_substs = @@ -341,5 +340,3 @@ fn ty_is_local_constructor<'tcx>(tcx: &ty::ctxt<'tcx>, } } } - - diff --git a/src/librustc/middle/traits/error_reporting.rs b/src/librustc/middle/traits/error_reporting.rs index d10ff060418..1b5719d3d42 100644 --- a/src/librustc/middle/traits/error_reporting.rs +++ b/src/librustc/middle/traits/error_reporting.rs @@ -191,7 +191,7 @@ pub fn report_selection_error<'a, 'tcx>(infcx: &InferCtxt<'a, 'tcx>, trait_ref.self_ty().user_string(infcx.tcx)); // Check if it has a custom "#[rustc_on_unimplemented]" // error message, report with that message if it does - let custom_note = report_on_unimplemented(infcx, &*trait_ref.0, + let custom_note = report_on_unimplemented(infcx, &trait_ref.0, obligation.cause.span); if let Some(s) = custom_note { infcx.tcx.sess.span_note(obligation.cause.span, diff --git a/src/librustc/middle/traits/object_safety.rs b/src/librustc/middle/traits/object_safety.rs index 3d6ed3c3440..ac3c9dfbb46 100644 --- a/src/librustc/middle/traits/object_safety.rs +++ b/src/librustc/middle/traits/object_safety.rs @@ -57,20 +57,18 @@ pub fn is_object_safe<'tcx>(tcx: &ty::ctxt<'tcx>, -> bool { // Because we query yes/no results frequently, we keep a cache: - let cached_result = - tcx.object_safety_cache.borrow().get(&trait_def_id).cloned(); + let def = ty::lookup_trait_def(tcx, trait_def_id); - let result = - cached_result.unwrap_or_else(|| { - let result = object_safety_violations(tcx, trait_def_id).is_empty(); + let result = def.object_safety().unwrap_or_else(|| { + let result = object_safety_violations(tcx, trait_def_id).is_empty(); - // Record just a yes/no result in the cache; this is what is - // queried most frequently. Note that this may overwrite a - // previous result, but always with the same thing. - tcx.object_safety_cache.borrow_mut().insert(trait_def_id, result); + // Record just a yes/no result in the cache; this is what is + // queried most frequently. Note that this may overwrite a + // previous result, but always with the same thing. + def.set_object_safety(result); - result - }); + result + }); debug!("is_object_safe({}) = {}", trait_def_id.repr(tcx), result); diff --git a/src/librustc/middle/traits/project.rs b/src/librustc/middle/traits/project.rs index 9cdae21868e..8ae7ad029ac 100644 --- a/src/librustc/middle/traits/project.rs +++ b/src/librustc/middle/traits/project.rs @@ -25,7 +25,6 @@ use middle::subst::{Subst, Substs}; use middle::ty::{self, AsPredicate, ReferencesError, RegionEscape, HasProjectionTypes, ToPolyTraitRef, Ty}; use middle::ty_fold::{self, TypeFoldable, TypeFolder}; -use std::rc::Rc; use syntax::ast; use syntax::parse::token; use util::common::FN_OUTPUT_NAME; @@ -525,7 +524,7 @@ fn project_type<'cx,'tcx>( fn assemble_candidates_from_param_env<'cx,'tcx>( selcx: &mut SelectionContext<'cx,'tcx>, obligation: &ProjectionTyObligation<'tcx>, - obligation_trait_ref: &Rc<ty::TraitRef<'tcx>>, + obligation_trait_ref: &ty::TraitRef<'tcx>, candidate_set: &mut ProjectionTyCandidateSet<'tcx>) { let env_predicates = selcx.param_env().caller_bounds.clone(); @@ -546,7 +545,7 @@ fn assemble_candidates_from_param_env<'cx,'tcx>( fn assemble_candidates_from_trait_def<'cx,'tcx>( selcx: &mut SelectionContext<'cx,'tcx>, obligation: &ProjectionTyObligation<'tcx>, - obligation_trait_ref: &Rc<ty::TraitRef<'tcx>>, + obligation_trait_ref: &ty::TraitRef<'tcx>, candidate_set: &mut ProjectionTyCandidateSet<'tcx>) { // Check whether the self-type is itself a projection. @@ -571,7 +570,7 @@ fn assemble_candidates_from_trait_def<'cx,'tcx>( fn assemble_candidates_from_predicates<'cx,'tcx>( selcx: &mut SelectionContext<'cx,'tcx>, obligation: &ProjectionTyObligation<'tcx>, - obligation_trait_ref: &Rc<ty::TraitRef<'tcx>>, + obligation_trait_ref: &ty::TraitRef<'tcx>, candidate_set: &mut ProjectionTyCandidateSet<'tcx>, env_predicates: Vec<ty::Predicate<'tcx>>) { @@ -614,7 +613,7 @@ fn assemble_candidates_from_predicates<'cx,'tcx>( fn assemble_candidates_from_object_type<'cx,'tcx>( selcx: &mut SelectionContext<'cx,'tcx>, obligation: &ProjectionTyObligation<'tcx>, - obligation_trait_ref: &Rc<ty::TraitRef<'tcx>>, + obligation_trait_ref: &ty::TraitRef<'tcx>, candidate_set: &mut ProjectionTyCandidateSet<'tcx>, object_ty: Ty<'tcx>) { @@ -641,7 +640,7 @@ fn assemble_candidates_from_object_type<'cx,'tcx>( fn assemble_candidates_from_impls<'cx,'tcx>( selcx: &mut SelectionContext<'cx,'tcx>, obligation: &ProjectionTyObligation<'tcx>, - obligation_trait_ref: &Rc<ty::TraitRef<'tcx>>, + obligation_trait_ref: &ty::TraitRef<'tcx>, candidate_set: &mut ProjectionTyCandidateSet<'tcx>) -> Result<(), SelectionError<'tcx>> { diff --git a/src/librustc/middle/traits/select.rs b/src/librustc/middle/traits/select.rs index 153ec0ab2b3..49371eae265 100644 --- a/src/librustc/middle/traits/select.rs +++ b/src/librustc/middle/traits/select.rs @@ -89,7 +89,7 @@ struct TraitObligationStack<'prev, 'tcx: 'prev> { #[derive(Clone)] pub struct SelectionCache<'tcx> { - hashmap: RefCell<FnvHashMap<Rc<ty::TraitRef<'tcx>>, + hashmap: RefCell<FnvHashMap<ty::TraitRef<'tcx>, SelectionResult<'tcx, SelectionCandidate<'tcx>>>>, } @@ -988,7 +988,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { fn match_projection(&mut self, obligation: &TraitObligation<'tcx>, trait_bound: ty::PolyTraitRef<'tcx>, - skol_trait_ref: Rc<ty::TraitRef<'tcx>>, + skol_trait_ref: ty::TraitRef<'tcx>, skol_map: &infer::SkolemizationMap, snapshot: &infer::CombinedSnapshot) -> bool @@ -1153,18 +1153,19 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { { debug!("assemble_candidates_from_impls(obligation={})", obligation.repr(self.tcx())); - let def_id = obligation.predicate.def_id(); - let all_impls = self.all_impls(def_id); - for &impl_def_id in &all_impls { - self.infcx.probe(|snapshot| { - match self.match_impl(impl_def_id, obligation, snapshot) { - Ok(_) => { + let def = ty::lookup_trait_def(self.tcx(), obligation.predicate.def_id()); + + def.for_each_relevant_impl( + self.tcx(), + obligation.predicate.0.trait_ref.self_ty(), + |impl_def_id| { + self.infcx.probe(|snapshot| { + if let Ok(_) = self.match_impl(impl_def_id, obligation, snapshot) { candidates.vec.push(ImplCandidate(impl_def_id)); } - Err(()) => { } - } - }); - } + }); + } + ); Ok(()) } @@ -2324,7 +2325,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // Before we create the substitutions and everything, first // consider a "quick reject". This avoids creating more types // and so forth that we need to. - if self.fast_reject_trait_refs(obligation, &*impl_trait_ref) { + if self.fast_reject_trait_refs(obligation, &impl_trait_ref) { return Err(()); } @@ -2529,16 +2530,6 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } } - /// Returns set of all impls for a given trait. - fn all_impls(&self, trait_def_id: ast::DefId) -> Vec<ast::DefId> { - ty::populate_implementations_for_trait_if_necessary(self.tcx(), trait_def_id); - - match self.tcx().trait_impls.borrow().get(&trait_def_id) { - None => Vec::new(), - Some(impls) => impls.borrow().clone(), - } - } - fn closure_trait_ref(&self, obligation: &TraitObligation<'tcx>, closure_def_id: ast::DefId, diff --git a/src/librustc/middle/traits/util.rs b/src/librustc/middle/traits/util.rs index 6ecff3b7faa..a6b2359c2b8 100644 --- a/src/librustc/middle/traits/util.rs +++ b/src/librustc/middle/traits/util.rs @@ -12,7 +12,6 @@ use middle::subst::{Substs, VecPerParamSpace}; use middle::infer::InferCtxt; use middle::ty::{self, Ty, AsPredicate, ToPolyTraitRef}; use std::fmt; -use std::rc::Rc; use syntax::ast; use syntax::codemap::Span; use util::common::ErrorReported; @@ -336,14 +335,14 @@ pub fn trait_ref_for_builtin_bound<'tcx>( tcx: &ty::ctxt<'tcx>, builtin_bound: ty::BuiltinBound, param_ty: Ty<'tcx>) - -> Result<Rc<ty::TraitRef<'tcx>>, ErrorReported> + -> Result<ty::TraitRef<'tcx>, ErrorReported> { match tcx.lang_items.from_builtin_kind(builtin_bound) { Ok(def_id) => { - Ok(Rc::new(ty::TraitRef { + Ok(ty::TraitRef { def_id: def_id, substs: tcx.mk_substs(Substs::empty().with_self_ty(param_ty)) - })) + }) } Err(e) => { tcx.sess.err(&e); @@ -355,7 +354,7 @@ pub fn trait_ref_for_builtin_bound<'tcx>( pub fn predicate_for_trait_ref<'tcx>( cause: ObligationCause<'tcx>, - trait_ref: Rc<ty::TraitRef<'tcx>>, + trait_ref: ty::TraitRef<'tcx>, recursion_depth: usize) -> Result<PredicateObligation<'tcx>, ErrorReported> { @@ -374,10 +373,10 @@ pub fn predicate_for_trait_def<'tcx>( param_ty: Ty<'tcx>) -> Result<PredicateObligation<'tcx>, ErrorReported> { - let trait_ref = Rc::new(ty::TraitRef { + let trait_ref = ty::TraitRef { def_id: trait_def_id, substs: tcx.mk_substs(Substs::empty().with_self_ty(param_ty)) - }); + }; predicate_for_trait_ref(cause, trait_ref, recursion_depth) } @@ -466,17 +465,17 @@ pub fn closure_trait_ref_and_return_type<'tcx>( self_ty: Ty<'tcx>, sig: &ty::PolyFnSig<'tcx>, tuple_arguments: TupleArgumentsFlag) - -> ty::Binder<(Rc<ty::TraitRef<'tcx>>, Ty<'tcx>)> + -> ty::Binder<(ty::TraitRef<'tcx>, Ty<'tcx>)> { let arguments_tuple = match tuple_arguments { TupleArgumentsFlag::No => sig.0.inputs[0], TupleArgumentsFlag::Yes => ty::mk_tup(tcx, sig.0.inputs.to_vec()), }; let trait_substs = Substs::new_trait(vec![arguments_tuple], vec![], self_ty); - let trait_ref = Rc::new(ty::TraitRef { + let trait_ref = ty::TraitRef { def_id: fn_trait_def_id, substs: tcx.mk_substs(trait_substs), - }); + }; ty::Binder((trait_ref, sig.0.output.unwrap_or(ty::mk_nil(tcx)))) } diff --git a/src/librustc/middle/ty.rs b/src/librustc/middle/ty.rs index 5f9e282bc53..41bd52dc25c 100644 --- a/src/librustc/middle/ty.rs +++ b/src/librustc/middle/ty.rs @@ -45,6 +45,7 @@ use middle::check_const; use middle::const_eval; use middle::def::{self, DefMap, ExportMap}; use middle::dependency_format; +use middle::fast_reject; use middle::free_region::FreeRegionMap; use middle::lang_items::{FnTraitLangItem, FnMutTraitLangItem, FnOnceTraitLangItem}; use middle::mem_categorization as mc; @@ -433,7 +434,7 @@ pub struct MethodParam<'tcx> { // be a supertrait of what the user actually typed. Note that it // never contains bound regions; those regions should have been // instantiated with fresh variables at this point. - pub trait_ref: Rc<ty::TraitRef<'tcx>>, + pub trait_ref: ty::TraitRef<'tcx>, // index of usize in the list of trait items. Note that this is NOT // the index into the vtable, because the list of trait items @@ -451,7 +452,7 @@ pub struct MethodParam<'tcx> { #[derive(Clone, Debug)] pub struct MethodObject<'tcx> { // the (super)trait containing the method to be invoked - pub trait_ref: Rc<ty::TraitRef<'tcx>>, + pub trait_ref: TraitRef<'tcx>, // the actual base trait id of the object pub object_trait_id: ast::DefId, @@ -588,10 +589,14 @@ pub struct TransmuteRestriction<'tcx> { /// Internal storage pub struct CtxtArenas<'tcx> { + // internings type_: TypedArena<TyS<'tcx>>, substs: TypedArena<Substs<'tcx>>, bare_fn: TypedArena<BareFnTy<'tcx>>, region: TypedArena<Region>, + + // references + trait_defs: TypedArena<TraitDef<'tcx>> } impl<'tcx> CtxtArenas<'tcx> { @@ -601,6 +606,8 @@ impl<'tcx> CtxtArenas<'tcx> { substs: TypedArena::new(), bare_fn: TypedArena::new(), region: TypedArena::new(), + + trait_defs: TypedArena::new() } } } @@ -678,10 +685,10 @@ pub struct ctxt<'tcx> { /// A cache for the trait_items() routine pub trait_items_cache: RefCell<DefIdMap<Rc<Vec<ImplOrTraitItem<'tcx>>>>>, - pub impl_trait_cache: RefCell<DefIdMap<Option<Rc<ty::TraitRef<'tcx>>>>>, + pub impl_trait_cache: RefCell<DefIdMap<Option<TraitRef<'tcx>>>>, - pub impl_trait_refs: RefCell<NodeMap<Rc<TraitRef<'tcx>>>>, - pub trait_defs: RefCell<DefIdMap<Rc<TraitDef<'tcx>>>>, + pub impl_trait_refs: RefCell<NodeMap<TraitRef<'tcx>>>, + pub trait_defs: RefCell<DefIdMap<&'tcx TraitDef<'tcx>>>, /// Maps from the def-id of an item (trait/struct/enum/fn) to its /// associated predicates. @@ -731,12 +738,6 @@ pub struct ctxt<'tcx> { /// A method will be in this list if and only if it is a destructor. pub destructors: RefCell<DefIdSet>, - /// Maps a trait onto a list of impls of that trait. - pub trait_impls: RefCell<DefIdMap<Rc<RefCell<Vec<ast::DefId>>>>>, - - /// A set of traits that have a default impl - traits_with_default_impls: RefCell<DefIdMap<()>>, - /// Maps a DefId of a type to a list of its inherent impls. /// Contains implementations of methods that are inherent to a type. /// Methods in these implementations don't need to be exported. @@ -760,12 +761,8 @@ pub struct ctxt<'tcx> { /// The set of external nominal types whose implementations have been read. /// This is used for lazy resolution of methods. pub populated_external_types: RefCell<DefIdSet>, - - /// The set of external traits whose implementations have been read. This - /// is used for lazy resolution of traits. - pub populated_external_traits: RefCell<DefIdSet>, - - /// The set of external primitive inherent implementations that have been read. + /// The set of external primitive types whose implementations have been read. + /// FIXME(arielb1): why is this separate from populated_external_types? pub populated_external_primitive_impls: RefCell<DefIdSet>, /// Borrows @@ -819,9 +816,6 @@ pub struct ctxt<'tcx> { /// results are dependent on the parameter environment. pub type_impls_sized_cache: RefCell<HashMap<Ty<'tcx>,bool>>, - /// Caches whether traits are object safe - pub object_safety_cache: RefCell<DefIdMap<bool>>, - /// Maps Expr NodeId's to their constant qualification. pub const_qualif_map: RefCell<NodeMap<check_const::ConstQualif>>, } @@ -832,6 +826,13 @@ impl<'tcx> ctxt<'tcx> { self.node_types.borrow_mut().insert(id, ty); } + pub fn intern_trait_def(&self, def: TraitDef<'tcx>) -> &'tcx TraitDef<'tcx> { + let did = def.trait_ref.def_id; + let interned = self.arenas.trait_defs.alloc(def); + self.trait_defs.borrow_mut().insert(did, interned); + interned + } + pub fn store_free_region_map(&self, id: NodeId, map: FreeRegionMap) { self.free_region_maps.borrow_mut() .insert(id, map); @@ -953,6 +954,7 @@ impl fmt::Debug for TypeFlags { } impl<'tcx> PartialEq for TyS<'tcx> { + #[inline] fn eq(&self, other: &TyS<'tcx>) -> bool { // (self as *const _) == (other as *const _) (self as *const TyS<'tcx>) == (other as *const TyS<'tcx>) @@ -1414,10 +1416,10 @@ impl<'tcx> TyTrait<'tcx> { // otherwise the escaping regions would be captured by the binder assert!(!self_ty.has_escaping_regions()); - ty::Binder(Rc::new(ty::TraitRef { + ty::Binder(TraitRef { def_id: self.principal.0.def_id, substs: tcx.mk_substs(self.principal.0.substs.with_self_ty(self_ty)), - })) + }) } pub fn projection_bounds_with_self_ty(&self, @@ -1432,9 +1434,8 @@ impl<'tcx> TyTrait<'tcx> { .map(|in_poly_projection_predicate| { let in_projection_ty = &in_poly_projection_predicate.0.projection_ty; let substs = tcx.mk_substs(in_projection_ty.trait_ref.substs.with_self_ty(self_ty)); - let trait_ref = - Rc::new(ty::TraitRef::new(in_projection_ty.trait_ref.def_id, - substs)); + let trait_ref = ty::TraitRef::new(in_projection_ty.trait_ref.def_id, + substs); let projection_ty = ty::ProjectionTy { trait_ref: trait_ref, item_name: in_projection_ty.item_name @@ -1463,13 +1464,13 @@ impl<'tcx> TyTrait<'tcx> { /// Note that a `TraitRef` introduces a level of region binding, to /// account for higher-ranked trait bounds like `T : for<'a> Foo<&'a /// U>` or higher-ranked object types. -#[derive(Clone, PartialEq, Eq, Hash, Debug)] +#[derive(Copy, Clone, PartialEq, Eq, Hash, Debug)] pub struct TraitRef<'tcx> { pub def_id: DefId, pub substs: &'tcx Substs<'tcx>, } -pub type PolyTraitRef<'tcx> = Binder<Rc<TraitRef<'tcx>>>; +pub type PolyTraitRef<'tcx> = Binder<TraitRef<'tcx>>; impl<'tcx> PolyTraitRef<'tcx> { pub fn self_ty(&self) -> Ty<'tcx> { @@ -1995,7 +1996,7 @@ impl<'tcx> Predicate<'tcx> { #[derive(Clone, PartialEq, Eq, Hash, Debug)] pub struct TraitPredicate<'tcx> { - pub trait_ref: Rc<TraitRef<'tcx>> + pub trait_ref: TraitRef<'tcx> } pub type PolyTraitPredicate<'tcx> = ty::Binder<TraitPredicate<'tcx>>; @@ -2064,7 +2065,7 @@ impl<'tcx> PolyProjectionPredicate<'tcx> { #[derive(Clone, PartialEq, Eq, Hash, Debug)] pub struct ProjectionTy<'tcx> { /// The trait reference `T as Trait<..>`. - pub trait_ref: Rc<ty::TraitRef<'tcx>>, + pub trait_ref: ty::TraitRef<'tcx>, /// The name `N` of the associated type. pub item_name: ast::Name, @@ -2080,7 +2081,7 @@ pub trait ToPolyTraitRef<'tcx> { fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx>; } -impl<'tcx> ToPolyTraitRef<'tcx> for Rc<TraitRef<'tcx>> { +impl<'tcx> ToPolyTraitRef<'tcx> for TraitRef<'tcx> { fn to_poly_trait_ref(&self) -> PolyTraitRef<'tcx> { assert!(!self.has_escaping_regions()); ty::Binder(self.clone()) @@ -2108,7 +2109,7 @@ pub trait AsPredicate<'tcx> { fn as_predicate(&self) -> Predicate<'tcx>; } -impl<'tcx> AsPredicate<'tcx> for Rc<TraitRef<'tcx>> { +impl<'tcx> AsPredicate<'tcx> for TraitRef<'tcx> { fn as_predicate(&self) -> Predicate<'tcx> { // we're about to add a binder, so let's check that we don't // accidentally capture anything, or else that might be some @@ -2488,6 +2489,16 @@ pub struct TypeScheme<'tcx> { pub ty: Ty<'tcx>, } +bitflags! { + flags TraitFlags: u32 { + const NO_TRAIT_FLAGS = 0, + const HAS_DEFAULT_IMPL = 1 << 0, + const IS_OBJECT_SAFE = 1 << 1, + const OBJECT_SAFETY_VALID = 1 << 2, + const IMPLS_VALID = 1 << 3, + } +} + /// As `TypeScheme` but for a trait ref. pub struct TraitDef<'tcx> { pub unsafety: ast::Unsafety, @@ -2505,11 +2516,117 @@ pub struct TraitDef<'tcx> { /// implements the trait. pub generics: Generics<'tcx>, - pub trait_ref: Rc<ty::TraitRef<'tcx>>, + pub trait_ref: TraitRef<'tcx>, /// A list of the associated types defined in this trait. Useful /// for resolving `X::Foo` type markers. pub associated_type_names: Vec<ast::Name>, + + // Impls of this trait. To allow for quicker lookup, the impls are indexed + // by a simplified version of their Self type: impls with a simplifiable + // Self are stored in nonblanket_impls keyed by it, while all other impls + // are stored in blanket_impls. + + /// Impls of the trait. + pub nonblanket_impls: RefCell< + FnvHashMap<fast_reject::SimplifiedType, Vec<DefId>> + >, + + /// Blanket impls associated with the trait. + pub blanket_impls: RefCell<Vec<DefId>>, + + /// Various flags + pub flags: Cell<TraitFlags> +} + +impl<'tcx> TraitDef<'tcx> { + // returns None if not yet calculated + pub fn object_safety(&self) -> Option<bool> { + if self.flags.get().intersects(TraitFlags::OBJECT_SAFETY_VALID) { + Some(self.flags.get().intersects(TraitFlags::IS_OBJECT_SAFE)) + } else { + None + } + } + + pub fn set_object_safety(&self, is_safe: bool) { + assert!(self.object_safety().map(|cs| cs == is_safe).unwrap_or(true)); + self.flags.set( + self.flags.get() | if is_safe { + TraitFlags::OBJECT_SAFETY_VALID | TraitFlags::IS_OBJECT_SAFE + } else { + TraitFlags::OBJECT_SAFETY_VALID + } + ); + } + + /// Records a trait-to-implementation mapping. + pub fn record_impl(&self, + tcx: &ctxt<'tcx>, + impl_def_id: DefId, + impl_trait_ref: TraitRef<'tcx>) { + // We don't want to borrow_mut after we already populated all impls, + // so check if an impl is present with an immutable borrow first. + + if let Some(sty) = fast_reject::simplify_type(tcx, + impl_trait_ref.self_ty(), false) { + if let Some(is) = self.nonblanket_impls.borrow().get(&sty) { + if is.contains(&impl_def_id) { + return // duplicate - skip + } + } + + self.nonblanket_impls.borrow_mut().entry(sty).or_insert(vec![]).push(impl_def_id) + } else { + if self.blanket_impls.borrow().contains(&impl_def_id) { + return // duplicate - skip + } + self.blanket_impls.borrow_mut().push(impl_def_id) + } + } + + + pub fn for_each_impl<F: FnMut(DefId)>(&self, tcx: &ctxt<'tcx>, mut f: F) { + ty::populate_implementations_for_trait_if_necessary(tcx, self.trait_ref.def_id); + + for &impl_def_id in self.blanket_impls.borrow().iter() { + f(impl_def_id); + } + + for v in self.nonblanket_impls.borrow().values() { + for &impl_def_id in v { + f(impl_def_id); + } + } + } + + pub fn for_each_relevant_impl<F: FnMut(DefId)>(&self, + tcx: &ctxt<'tcx>, + self_ty: Ty<'tcx>, + mut f: F) + { + ty::populate_implementations_for_trait_if_necessary(tcx, self.trait_ref.def_id); + + for &impl_def_id in self.blanket_impls.borrow().iter() { + f(impl_def_id); + } + + if let Some(simp) = fast_reject::simplify_type(tcx, self_ty, false) { + if let Some(impls) = self.nonblanket_impls.borrow().get(&simp) { + for &impl_def_id in impls { + f(impl_def_id); + } + return; // we don't need to process the other non-blanket impls + } + } + + for v in self.nonblanket_impls.borrow().values() { + for &impl_def_id in v { + f(impl_def_id); + } + } + } + } /// Records the substitutions used to translate the polytype for an @@ -2669,14 +2786,11 @@ pub fn mk_ctxt<'tcx>(s: Session, struct_fields: RefCell::new(DefIdMap()), destructor_for_type: RefCell::new(DefIdMap()), destructors: RefCell::new(DefIdSet()), - trait_impls: RefCell::new(DefIdMap()), - traits_with_default_impls: RefCell::new(DefIdMap()), inherent_impls: RefCell::new(DefIdMap()), impl_items: RefCell::new(DefIdMap()), used_unsafe: RefCell::new(NodeSet()), used_mut_nodes: RefCell::new(NodeSet()), populated_external_types: RefCell::new(DefIdSet()), - populated_external_traits: RefCell::new(DefIdSet()), populated_external_primitive_impls: RefCell::new(DefIdSet()), upvar_capture_map: RefCell::new(FnvHashMap()), extern_const_statics: RefCell::new(DefIdMap()), @@ -2693,7 +2807,6 @@ pub fn mk_ctxt<'tcx>(s: Session, repr_hint_cache: RefCell::new(DefIdMap()), type_impls_copy_cache: RefCell::new(HashMap::new()), type_impls_sized_cache: RefCell::new(HashMap::new()), - object_safety_cache: RefCell::new(DefIdMap()), const_qualif_map: RefCell::new(NodeMap()), } } @@ -3132,7 +3245,7 @@ pub fn sort_bounds_list(bounds: &mut [ty::PolyProjectionPredicate]) { } pub fn mk_projection<'tcx>(cx: &ctxt<'tcx>, - trait_ref: Rc<ty::TraitRef<'tcx>>, + trait_ref: TraitRef<'tcx>, item_name: ast::Name) -> Ty<'tcx> { // take a copy of substs so that we own the vectors inside @@ -4398,9 +4511,9 @@ pub fn named_element_ty<'tcx>(cx: &ctxt<'tcx>, } pub fn impl_id_to_trait_ref<'tcx>(cx: &ctxt<'tcx>, id: ast::NodeId) - -> Rc<ty::TraitRef<'tcx>> { + -> ty::TraitRef<'tcx> { match cx.impl_trait_refs.borrow().get(&id) { - Some(ty) => ty.clone(), + Some(ty) => *ty, None => cx.sess.bug( &format!("impl_id_to_trait_ref: no trait ref for impl `{}`", cx.map.node_to_string(id))) @@ -5313,7 +5426,7 @@ pub fn trait_item_def_ids(cx: &ctxt, id: ast::DefId) } pub fn impl_trait_ref<'tcx>(cx: &ctxt<'tcx>, id: ast::DefId) - -> Option<Rc<TraitRef<'tcx>>> { + -> Option<TraitRef<'tcx>> { memoized(&cx.impl_trait_cache, id, |id: ast::DefId| { if id.krate == ast::LOCAL_CRATE { debug!("(impl_trait_ref) searching for trait impl {:?}", id); @@ -5821,10 +5934,10 @@ pub fn lookup_item_type<'tcx>(cx: &ctxt<'tcx>, /// Given the did of a trait, returns its canonical trait ref. pub fn lookup_trait_def<'tcx>(cx: &ctxt<'tcx>, did: ast::DefId) - -> Rc<TraitDef<'tcx>> { + -> &'tcx TraitDef<'tcx> { memoized(&cx.trait_defs, did, |did: DefId| { assert!(did.krate != ast::LOCAL_CRATE); - Rc::new(csearch::get_trait_def(cx, did)) + cx.arenas.trait_defs.alloc(csearch::get_trait_def(cx, did)) }) } @@ -6213,50 +6326,36 @@ pub fn item_variances(tcx: &ctxt, item_id: ast::DefId) -> Rc<ItemVariances> { pub fn trait_has_default_impl(tcx: &ctxt, trait_def_id: DefId) -> bool { populate_implementations_for_trait_if_necessary(tcx, trait_def_id); - tcx.traits_with_default_impls.borrow().contains_key(&trait_def_id) -} -/// Records a trait-to-implementation mapping. -pub fn record_trait_has_default_impl(tcx: &ctxt, trait_def_id: DefId) { - // We're using the latest implementation found as the reference one. - // Duplicated implementations are caught and reported in the coherence - // step. - tcx.traits_with_default_impls.borrow_mut().insert(trait_def_id, ()); + let def = lookup_trait_def(tcx, trait_def_id); + def.flags.get().intersects(TraitFlags::HAS_DEFAULT_IMPL) } /// Records a trait-to-implementation mapping. -pub fn record_trait_implementation(tcx: &ctxt, - trait_def_id: DefId, - impl_def_id: DefId) { - - match tcx.trait_impls.borrow().get(&trait_def_id) { - Some(impls_for_trait) => { - impls_for_trait.borrow_mut().push(impl_def_id); - return; - } - None => {} - } - - tcx.trait_impls.borrow_mut().insert(trait_def_id, Rc::new(RefCell::new(vec!(impl_def_id)))); +pub fn record_trait_has_default_impl(tcx: &ctxt, trait_def_id: DefId) { + let def = lookup_trait_def(tcx, trait_def_id); + def.flags.set(def.flags.get() | TraitFlags::HAS_DEFAULT_IMPL) } /// Load primitive inherent implementations if necessary -pub fn populate_implementations_for_primitive_if_necessary(tcx: &ctxt, lang_def_id: ast::DefId) { - if lang_def_id.krate == LOCAL_CRATE { +pub fn populate_implementations_for_primitive_if_necessary(tcx: &ctxt, + primitive_def_id: ast::DefId) { + if primitive_def_id.krate == LOCAL_CRATE { return } - if tcx.populated_external_primitive_impls.borrow().contains(&lang_def_id) { + + if tcx.populated_external_primitive_impls.borrow().contains(&primitive_def_id) { return } - debug!("populate_implementations_for_primitive_if_necessary: searching for {:?}", lang_def_id); + debug!("populate_implementations_for_primitive_if_necessary: searching for {:?}", + primitive_def_id); - let impl_items = csearch::get_impl_items(&tcx.sess.cstore, lang_def_id); + let impl_items = csearch::get_impl_items(&tcx.sess.cstore, primitive_def_id); // Store the implementation info. - tcx.impl_items.borrow_mut().insert(lang_def_id, impl_items); - - tcx.populated_external_primitive_impls.borrow_mut().insert(lang_def_id); + tcx.impl_items.borrow_mut().insert(primitive_def_id, impl_items); + tcx.populated_external_primitive_impls.borrow_mut().insert(primitive_def_id); } /// Populates the type context with all the implementations for the given type @@ -6266,6 +6365,7 @@ pub fn populate_implementations_for_type_if_necessary(tcx: &ctxt, if type_id.krate == LOCAL_CRATE { return } + if tcx.populated_external_types.borrow().contains(&type_id) { return } @@ -6276,10 +6376,12 @@ pub fn populate_implementations_for_type_if_necessary(tcx: &ctxt, csearch::each_implementation_for_type(&tcx.sess.cstore, type_id, |impl_def_id| { let impl_items = csearch::get_impl_items(&tcx.sess.cstore, impl_def_id); - // Record the trait->implementation mappings, if applicable. - let associated_traits = csearch::get_impl_trait(tcx, impl_def_id); - if let Some(ref trait_ref) = associated_traits { - record_trait_implementation(tcx, trait_ref.def_id, impl_def_id); + // Record the implementation, if needed + if let Some(trait_ref) = csearch::get_impl_trait(tcx, impl_def_id) { + let trait_def = lookup_trait_def(tcx, trait_ref.def_id); + trait_def.record_impl(tcx, impl_def_id, trait_ref); + } else { + inherent_impls.push(impl_def_id); } // For any methods that use a default implementation, add them to @@ -6300,11 +6402,6 @@ pub fn populate_implementations_for_type_if_necessary(tcx: &ctxt, // Store the implementation info. tcx.impl_items.borrow_mut().insert(impl_def_id, impl_items); - - // If this is an inherent implementation, record it. - if associated_traits.is_none() { - inherent_impls.push(impl_def_id); - } }); tcx.inherent_impls.borrow_mut().insert(type_id, Rc::new(inherent_impls)); @@ -6320,7 +6417,8 @@ pub fn populate_implementations_for_trait_if_necessary( return } - if tcx.populated_external_traits.borrow().contains(&trait_id) { + let def = lookup_trait_def(tcx, trait_id); + if def.flags.get().intersects(TraitFlags::IMPLS_VALID) { return } @@ -6330,9 +6428,9 @@ pub fn populate_implementations_for_trait_if_necessary( csearch::each_implementation_for_trait(&tcx.sess.cstore, trait_id, |implementation_def_id| { let impl_items = csearch::get_impl_items(&tcx.sess.cstore, implementation_def_id); - + let trait_ref = impl_trait_ref(tcx, implementation_def_id).unwrap(); // Record the trait->implementation mapping. - record_trait_implementation(tcx, trait_id, implementation_def_id); + def.record_impl(tcx, implementation_def_id, trait_ref); // For any methods that use a default implementation, add them to // the map. This is a bit unfortunate. @@ -6354,7 +6452,7 @@ pub fn populate_implementations_for_trait_if_necessary( tcx.impl_items.borrow_mut().insert(implementation_def_id, impl_items); }); - tcx.populated_external_traits.borrow_mut().insert(trait_id); + def.flags.set(def.flags.get() | TraitFlags::IMPLS_VALID); } /// Given the def_id of an impl, return the def_id of the trait it implements. diff --git a/src/librustc/middle/ty_relate/mod.rs b/src/librustc/middle/ty_relate/mod.rs index 1c414d3d5f3..0ef7b5be1fb 100644 --- a/src/librustc/middle/ty_relate/mod.rs +++ b/src/librustc/middle/ty_relate/mod.rs @@ -321,8 +321,8 @@ impl<'a,'tcx:'a> Relate<'a,'tcx> for ty::ProjectionTy<'tcx> { Err(ty::terr_projection_name_mismatched( expected_found(relation, &a.item_name, &b.item_name))) } else { - let trait_ref = try!(relation.relate(&*a.trait_ref, &*b.trait_ref)); - Ok(ty::ProjectionTy { trait_ref: Rc::new(trait_ref), item_name: a.item_name }) + let trait_ref = try!(relation.relate(&a.trait_ref, &b.trait_ref)); + Ok(ty::ProjectionTy { trait_ref: trait_ref, item_name: a.item_name }) } } } @@ -652,4 +652,3 @@ pub fn expected_found_bool<T>(a_is_expected: bool, ty::expected_found {expected: b, found: a} } } - diff --git a/src/librustc/util/ppaux.rs b/src/librustc/util/ppaux.rs index 3d56371dd52..aa89c1943a2 100644 --- a/src/librustc/util/ppaux.rs +++ b/src/librustc/util/ppaux.rs @@ -671,7 +671,7 @@ impl<'tcx> Repr<'tcx> for def::Def { /// projection bounds, so we just stuff them altogether. But in /// reality we should eventually sort things out better. type TraitAndProjections<'tcx> = - (Rc<ty::TraitRef<'tcx>>, Vec<ty::ProjectionPredicate<'tcx>>); + (ty::TraitRef<'tcx>, Vec<ty::ProjectionPredicate<'tcx>>); impl<'tcx> UserString<'tcx> for TraitAndProjections<'tcx> { fn user_string(&self, tcx: &ctxt<'tcx>) -> String { diff --git a/src/librustc_lint/builtin.rs b/src/librustc_lint/builtin.rs index cc2c9b735ea..19e71d6e40d 100644 --- a/src/librustc_lint/builtin.rs +++ b/src/librustc_lint/builtin.rs @@ -1745,17 +1745,16 @@ impl LintPass for MissingDebugImplementations { }; if self.impling_types.is_none() { - let impls = cx.tcx.trait_impls.borrow(); - let impls = match impls.get(&debug) { - Some(impls) => { - impls.borrow().iter() - .filter(|d| d.krate == ast::LOCAL_CRATE) - .filter_map(|d| ty::ty_to_def_id(ty::node_id_to_type(cx.tcx, d.node))) - .map(|d| d.node) - .collect() + let debug_def = ty::lookup_trait_def(cx.tcx, debug); + let mut impls = NodeSet(); + debug_def.for_each_impl(cx.tcx, |d| { + if d.krate == ast::LOCAL_CRATE { + if let Some(ty_def) = ty::ty_to_def_id(ty::node_id_to_type(cx.tcx, d.node)) { + impls.insert(ty_def.node); + } } - None => NodeSet(), - }; + }); + self.impling_types = Some(impls); debug!("{:?}", self.impling_types); } diff --git a/src/librustc_trans/trans/callee.rs b/src/librustc_trans/trans/callee.rs index 0e468072307..e87c058faf9 100644 --- a/src/librustc_trans/trans/callee.rs +++ b/src/librustc_trans/trans/callee.rs @@ -452,7 +452,7 @@ pub fn trans_fn_ref_with_substs<'a, 'tcx>( // Compute the first substitution let first_subst = - ty::make_substs_for_receiver_types(tcx, &*trait_ref, &*method) + ty::make_substs_for_receiver_types(tcx, &trait_ref, &*method) .erase_regions(); // And compose them diff --git a/src/librustc_trans/trans/expr.rs b/src/librustc_trans/trans/expr.rs index f5ee44d69cc..7be1f3813d7 100644 --- a/src/librustc_trans/trans/expr.rs +++ b/src/librustc_trans/trans/expr.rs @@ -86,7 +86,6 @@ use syntax::ptr::P; use syntax::parse::token; use std::iter::repeat; use std::mem; -use std::rc::Rc; // Destinations @@ -320,8 +319,8 @@ pub fn unsized_info<'ccx, 'tcx>(ccx: &CrateContext<'ccx, 'tcx>, // Note that we preserve binding levels here: let substs = principal.0.substs.with_self_ty(source).erase_regions(); let substs = ccx.tcx().mk_substs(substs); - let trait_ref = ty::Binder(Rc::new(ty::TraitRef { def_id: principal.def_id(), - substs: substs })); + let trait_ref = ty::Binder(ty::TraitRef { def_id: principal.def_id(), + substs: substs }); consts::ptrcast(meth::get_vtable(ccx, trait_ref, param_substs), Type::vtable_ptr(ccx)) } diff --git a/src/librustc_trans/trans/meth.rs b/src/librustc_trans/trans/meth.rs index fda931fde6e..7039968b029 100644 --- a/src/librustc_trans/trans/meth.rs +++ b/src/librustc_trans/trans/meth.rs @@ -40,7 +40,6 @@ use middle::ty::{self, Ty}; use middle::ty::MethodCall; use util::ppaux::Repr; -use std::rc::Rc; use syntax::abi::{Rust, RustCall}; use syntax::parse::token; use syntax::{ast, ast_map, attr, visit}; @@ -232,8 +231,8 @@ pub fn trans_static_method_callee<'a, 'tcx>(ccx: &CrateContext<'a, 'tcx>, Vec::new())); let trait_substs = tcx.mk_substs(trait_substs); debug!("trait_substs={}", trait_substs.repr(tcx)); - let trait_ref = ty::Binder(Rc::new(ty::TraitRef { def_id: trait_id, - substs: trait_substs })); + let trait_ref = ty::Binder(ty::TraitRef { def_id: trait_id, + substs: trait_substs }); let vtbl = fulfill_obligation(ccx, DUMMY_SP, trait_ref); diff --git a/src/librustc_typeck/astconv.rs b/src/librustc_typeck/astconv.rs index 9dbf918ddb5..694993cdc0a 100644 --- a/src/librustc_typeck/astconv.rs +++ b/src/librustc_typeck/astconv.rs @@ -64,7 +64,6 @@ use util::nodemap::FnvHashSet; use util::ppaux::{self, Repr, UserString}; use std::iter::repeat; -use std::rc::Rc; use std::slice; use syntax::{abi, ast, ast_util}; use syntax::codemap::{Span, Pos}; @@ -83,7 +82,7 @@ pub trait AstConv<'tcx> { /// Returns the `TraitDef` for a given trait. This allows you to /// figure out the set of type parameters defined on the trait. fn get_trait_def(&self, span: Span, id: ast::DefId) - -> Result<Rc<ty::TraitDef<'tcx>>, ErrorReported>; + -> Result<&'tcx ty::TraitDef<'tcx>, ErrorReported>; /// Ensure that the super-predicates for the trait with the given /// id are available and also for the transitive set of @@ -140,7 +139,7 @@ pub trait AstConv<'tcx> { /// This is fairly straightforward and can be accommodated in any context. fn projected_ty(&self, span: Span, - _trait_ref: Rc<ty::TraitRef<'tcx>>, + _trait_ref: ty::TraitRef<'tcx>, _item_name: ast::Name) -> Ty<'tcx>; } @@ -633,7 +632,7 @@ pub fn instantiate_mono_trait_ref<'tcx>( rscope: &RegionScope, trait_ref: &ast::TraitRef, self_ty: Option<Ty<'tcx>>) - -> Rc<ty::TraitRef<'tcx>> + -> ty::TraitRef<'tcx> { let trait_def_id = trait_def_id(this, trait_ref); ast_path_to_mono_trait_ref(this, @@ -702,7 +701,7 @@ fn ast_path_to_poly_trait_ref<'a,'tcx>( trait_def_id, self_ty, trait_segment); - let poly_trait_ref = ty::Binder(Rc::new(ty::TraitRef::new(trait_def_id, substs))); + let poly_trait_ref = ty::Binder(ty::TraitRef::new(trait_def_id, substs)); { let converted_bindings = @@ -730,7 +729,7 @@ fn ast_path_to_mono_trait_ref<'a,'tcx>(this: &AstConv<'tcx>, trait_def_id: ast::DefId, self_ty: Option<Ty<'tcx>>, trait_segment: &ast::PathSegment) - -> Rc<ty::TraitRef<'tcx>> + -> ty::TraitRef<'tcx> { let (substs, assoc_bindings) = create_substs_for_ast_trait_ref(this, @@ -741,7 +740,7 @@ fn ast_path_to_mono_trait_ref<'a,'tcx>(this: &AstConv<'tcx>, self_ty, trait_segment); prohibit_projections(this.tcx(), &assoc_bindings); - Rc::new(ty::TraitRef::new(trait_def_id, substs)) + ty::TraitRef::new(trait_def_id, substs) } fn create_substs_for_ast_trait_ref<'a,'tcx>(this: &AstConv<'tcx>, @@ -856,8 +855,8 @@ fn ast_type_binding_to_poly_projection_predicate<'tcx>( let mut dummy_substs = trait_ref.skip_binder().substs.clone(); // binder moved here -+ assert!(dummy_substs.self_ty().is_none()); // | dummy_substs.types.push(SelfSpace, dummy_self_ty); // | - trait_ref = ty::Binder(Rc::new(ty::TraitRef::new(trait_ref.def_id(), // <------------+ - tcx.mk_substs(dummy_substs)))); + trait_ref = ty::Binder(ty::TraitRef::new(trait_ref.def_id(), // <------------+ + tcx.mk_substs(dummy_substs))); } try!(this.ensure_super_predicates(binding.span, trait_ref.def_id())); @@ -874,8 +873,8 @@ fn ast_type_binding_to_poly_projection_predicate<'tcx>( let mut dummy_substs = candidate.0.substs.clone(); assert!(dummy_substs.self_ty() == Some(dummy_self_ty)); dummy_substs.types.pop(SelfSpace); - *candidate = ty::Binder(Rc::new(ty::TraitRef::new(candidate.def_id(), - tcx.mk_substs(dummy_substs)))); + *candidate = ty::Binder(ty::TraitRef::new(candidate.def_id(), + tcx.mk_substs(dummy_substs))); } } diff --git a/src/librustc_typeck/check/method/confirm.rs b/src/librustc_typeck/check/method/confirm.rs index cf1323e71bd..c068bfaa82e 100644 --- a/src/librustc_typeck/check/method/confirm.rs +++ b/src/librustc_typeck/check/method/confirm.rs @@ -23,7 +23,6 @@ use middle::infer; use middle::infer::InferCtxt; use syntax::ast; use syntax::codemap::Span; -use std::rc::Rc; use std::iter::repeat; use util::ppaux::Repr; @@ -276,7 +275,7 @@ impl<'a,'tcx> ConfirmContext<'a,'tcx> { self.infcx().next_ty_var()); let trait_ref = - Rc::new(ty::TraitRef::new(trait_def_id, self.tcx().mk_substs(substs.clone()))); + ty::TraitRef::new(trait_def_id, self.tcx().mk_substs(substs.clone())); let origin = MethodTypeParam(MethodParam { trait_ref: trait_ref, method_num: method_num, impl_def_id: None }); diff --git a/src/librustc_typeck/check/method/mod.rs b/src/librustc_typeck/check/method/mod.rs index c5d8e2758ba..c070df6b593 100644 --- a/src/librustc_typeck/check/method/mod.rs +++ b/src/librustc_typeck/check/method/mod.rs @@ -170,7 +170,7 @@ pub fn lookup_in_trait_adjusted<'a, 'tcx>(fcx: &FnCtxt<'a, 'tcx>, // Construct a trait-reference `self_ty : Trait<input_tys>` let substs = subst::Substs::new_trait(input_types, Vec::new(), self_ty); - let trait_ref = Rc::new(ty::TraitRef::new(trait_def_id, fcx.tcx().mk_substs(substs))); + let trait_ref = ty::TraitRef::new(trait_def_id, fcx.tcx().mk_substs(substs)); // Construct an obligation let poly_trait_ref = trait_ref.to_poly_trait_ref(); diff --git a/src/librustc_typeck/check/method/probe.rs b/src/librustc_typeck/check/method/probe.rs index 7ff1355184b..c94fa037026 100644 --- a/src/librustc_typeck/check/method/probe.rs +++ b/src/librustc_typeck/check/method/probe.rs @@ -61,7 +61,7 @@ struct Candidate<'tcx> { enum CandidateKind<'tcx> { InherentImplCandidate(/* Impl */ ast::DefId, subst::Substs<'tcx>), ObjectCandidate(/* Trait */ ast::DefId, /* method_num */ usize, /* vtable index */ usize), - ExtensionImplCandidate(/* Impl */ ast::DefId, Rc<ty::TraitRef<'tcx>>, + ExtensionImplCandidate(/* Impl */ ast::DefId, ty::TraitRef<'tcx>, subst::Substs<'tcx>, ItemIndex), ClosureCandidate(/* Trait */ ast::DefId, ItemIndex), WhereClauseCandidate(ty::PolyTraitRef<'tcx>, ItemIndex), @@ -624,23 +624,16 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> { item: ty::ImplOrTraitItem<'tcx>, item_index: usize) { - ty::populate_implementations_for_trait_if_necessary(self.tcx(), - trait_def_id); - - let trait_impls = self.tcx().trait_impls.borrow(); - let impl_def_ids = trait_impls.get(&trait_def_id); - let impl_def_ids = match impl_def_ids { - None => { return; } - Some(impls) => impls, - }; + let trait_def = ty::lookup_trait_def(self.tcx(), trait_def_id); - for &impl_def_id in &*impl_def_ids.borrow() { + // FIXME(arielb1): can we use for_each_relevant_impl here? + trait_def.for_each_impl(self.tcx(), |impl_def_id| { debug!("assemble_extension_candidates_for_trait_impl: trait_def_id={} impl_def_id={}", trait_def_id.repr(self.tcx()), impl_def_id.repr(self.tcx())); if !self.impl_can_possibly_match(impl_def_id) { - continue; + return; } let (_, impl_substs) = self.impl_ty_and_substs(impl_def_id); @@ -667,7 +660,7 @@ impl<'a,'tcx> ProbeContext<'a,'tcx> { item: item.clone(), kind: ExtensionImplCandidate(impl_def_id, impl_trait_ref, impl_substs, item_index) }); - } + }); } fn impl_can_possibly_match(&self, impl_def_id: ast::DefId) -> bool { diff --git a/src/librustc_typeck/check/mod.rs b/src/librustc_typeck/check/mod.rs index cb5b569fd79..ad1042c068a 100644 --- a/src/librustc_typeck/check/mod.rs +++ b/src/librustc_typeck/check/mod.rs @@ -112,7 +112,6 @@ use util::lev_distance::lev_distance; use std::cell::{Cell, Ref, RefCell}; use std::mem::replace; -use std::rc::Rc; use std::iter::repeat; use std::slice; use syntax::{self, abi, attr}; @@ -747,7 +746,7 @@ pub fn check_item_type<'a,'tcx>(ccx: &CrateCtxt<'a,'tcx>, it: &'tcx ast::Item) { Some(impl_trait_ref) => { check_impl_items_against_trait(ccx, it.span, - &*impl_trait_ref, + &impl_trait_ref, impl_items); } None => { } @@ -1174,7 +1173,7 @@ impl<'a, 'tcx> AstConv<'tcx> for FnCtxt<'a, 'tcx> { } fn get_trait_def(&self, _: Span, id: ast::DefId) - -> Result<Rc<ty::TraitDef<'tcx>>, ErrorReported> + -> Result<&'tcx ty::TraitDef<'tcx>, ErrorReported> { Ok(ty::lookup_trait_def(self.tcx(), id)) } @@ -1244,7 +1243,7 @@ impl<'a, 'tcx> AstConv<'tcx> for FnCtxt<'a, 'tcx> { fn projected_ty(&self, span: Span, - trait_ref: Rc<ty::TraitRef<'tcx>>, + trait_ref: ty::TraitRef<'tcx>, item_name: ast::Name) -> Ty<'tcx> { @@ -1457,7 +1456,7 @@ impl<'a, 'tcx> FnCtxt<'a, 'tcx> { fn normalize_associated_type(&self, span: Span, - trait_ref: Rc<ty::TraitRef<'tcx>>, + trait_ref: ty::TraitRef<'tcx>, item_name: ast::Name) -> Ty<'tcx> { diff --git a/src/librustc_typeck/check/wf.rs b/src/librustc_typeck/check/wf.rs index 83e0c398590..c2209ba2dc6 100644 --- a/src/librustc_typeck/check/wf.rs +++ b/src/librustc_typeck/check/wf.rs @@ -252,7 +252,7 @@ impl<'ccx, 'tcx> CheckTypeWellFormedVisitor<'ccx, 'tcx> { // trait reference. Instead, this is done at the impl site. // Arguably this is wrong and we should treat the trait-reference // the same way as we treat the self-type. - bounds_checker.check_trait_ref(&*trait_ref); + bounds_checker.check_trait_ref(&trait_ref); let cause = traits::ObligationCause::new( diff --git a/src/librustc_typeck/coherence/mod.rs b/src/librustc_typeck/coherence/mod.rs index fbfe73674e1..05b74a5cc22 100644 --- a/src/librustc_typeck/coherence/mod.rs +++ b/src/librustc_typeck/coherence/mod.rs @@ -163,7 +163,7 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> { enforce_trait_manually_implementable(self.crate_context.tcx, item.span, trait_ref.def_id); - self.add_trait_impl(trait_ref.def_id, impl_did); + self.add_trait_impl(trait_ref, impl_did); } // Add the implementation to the mapping from implementation to base @@ -259,12 +259,12 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> { Rc::new(RefCell::new(vec!(impl_def_id)))); } - fn add_trait_impl(&self, base_def_id: DefId, impl_def_id: DefId) { - debug!("add_trait_impl: base_def_id={:?} impl_def_id={:?}", - base_def_id, impl_def_id); - ty::record_trait_implementation(self.crate_context.tcx, - base_def_id, - impl_def_id); + fn add_trait_impl(&self, impl_trait_ref: ty::TraitRef<'tcx>, impl_def_id: DefId) { + debug!("add_trait_impl: impl_trait_ref={:?} impl_def_id={:?}", + impl_trait_ref, impl_def_id); + let trait_def = ty::lookup_trait_def(self.crate_context.tcx, + impl_trait_ref.def_id); + trait_def.record_impl(self.crate_context.tcx, impl_def_id, impl_trait_ref); } fn get_self_type_for_implementation(&self, impl_did: DefId) @@ -300,7 +300,7 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> { item.id); self.instantiate_default_methods(local_def(item.id), - &*trait_ref, + &trait_ref, &mut items); } @@ -337,7 +337,7 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> { // Record all the trait items. if let Some(trait_ref) = associated_traits { - self.add_trait_impl(trait_ref.def_id, impl_def_id); + self.add_trait_impl(trait_ref, impl_def_id); } // For any methods that use a default implementation, add them to @@ -382,18 +382,16 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> { let drop_trait = match tcx.lang_items.drop_trait() { Some(id) => id, None => { return } }; + ty::populate_implementations_for_trait_if_necessary(tcx, drop_trait); + let drop_trait = ty::lookup_trait_def(tcx, drop_trait); let impl_items = tcx.impl_items.borrow(); - let trait_impls = match tcx.trait_impls.borrow().get(&drop_trait).cloned() { - None => return, // No types with (new-style) dtors present. - Some(found_impls) => found_impls - }; - for &impl_did in &*trait_impls.borrow() { + drop_trait.for_each_impl(tcx, |impl_did| { let items = impl_items.get(&impl_did).unwrap(); if items.is_empty() { // We'll error out later. For now, just don't ICE. - continue; + return; } let method_def_id = items[0]; @@ -430,7 +428,7 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> { } } } - } + }); } /// Ensures that implementations of the built-in trait `Copy` are legal. @@ -440,30 +438,17 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> { Some(id) => id, None => return, }; + ty::populate_implementations_for_trait_if_necessary(tcx, copy_trait); + let copy_trait = ty::lookup_trait_def(tcx, copy_trait); - let trait_impls = match tcx.trait_impls - .borrow() - .get(©_trait) - .cloned() { - None => { - debug!("check_implementations_of_copy(): no types with \ - implementations of `Copy` found"); - return - } - Some(found_impls) => found_impls - }; - - // Clone first to avoid a double borrow error. - let trait_impls = trait_impls.borrow().clone(); - - for &impl_did in &trait_impls { + copy_trait.for_each_impl(tcx, |impl_did| { debug!("check_implementations_of_copy: impl_did={}", impl_did.repr(tcx)); if impl_did.krate != ast::LOCAL_CRATE { debug!("check_implementations_of_copy(): impl not in this \ crate"); - continue + return } let self_type = self.get_self_type_for_implementation(impl_did); @@ -506,7 +491,7 @@ impl<'a, 'tcx> CoherenceChecker<'a, 'tcx> { the type has a destructor"); } } - } + }); } } diff --git a/src/librustc_typeck/coherence/overlap.rs b/src/librustc_typeck/coherence/overlap.rs index 99b6d4154e9..46cce543011 100644 --- a/src/librustc_typeck/coherence/overlap.rs +++ b/src/librustc_typeck/coherence/overlap.rs @@ -48,59 +48,104 @@ impl<'cx, 'tcx> OverlapChecker<'cx, 'tcx> { // check_for_overlapping_impls_of_trait() check, since that // check can populate this table further with impls from other // crates. - let trait_def_ids: Vec<(ast::DefId, Vec<ast::DefId>)> = - self.tcx.trait_impls.borrow().iter().map(|(&k, v)| { - // FIXME -- it seems like this method actually pushes - // duplicate impls onto the list - ty::populate_implementations_for_trait_if_necessary(self.tcx, k); - (k, v.borrow().clone()) - }).collect(); - - for &(trait_def_id, ref impls) in &trait_def_ids { - self.check_for_overlapping_impls_of_trait(trait_def_id, impls); + let trait_defs : Vec<&ty::TraitDef> = { + let d = self.tcx.trait_defs.borrow(); + d.values().map(|&v|v).collect() + }; + + for trait_def in trait_defs { + // FIXME -- it seems like this method actually pushes + // duplicate impls onto the list + ty::populate_implementations_for_trait_if_necessary( + self.tcx, + trait_def.trait_ref.def_id); + self.check_for_overlapping_impls_of_trait(trait_def); } } fn check_for_overlapping_impls_of_trait(&self, - trait_def_id: ast::DefId, - trait_impls: &Vec<ast::DefId>) + trait_def: &'tcx ty::TraitDef<'tcx>) { - debug!("check_for_overlapping_impls_of_trait(trait_def_id={})", - trait_def_id.repr(self.tcx)); + debug!("check_for_overlapping_impls_of_trait(trait_def={})", + trait_def.repr(self.tcx)); - for (i, &impl1_def_id) in trait_impls.iter().enumerate() { - if impl1_def_id.krate != ast::LOCAL_CRATE { - // we don't need to check impls if both are external; - // that's the other crate's job. - continue; - } + // We should already know all impls of this trait, so these + // borrows are safe. + let blanket_impls = trait_def.blanket_impls.borrow(); + let nonblanket_impls = trait_def.nonblanket_impls.borrow(); + let trait_def_id = trait_def.trait_ref.def_id; - for &impl2_def_id in &trait_impls[(i+1)..] { + // Conflicts can only occur between a blanket impl and another impl, + // or between 2 non-blanket impls of the same kind. + + for (i, &impl1_def_id) in blanket_impls.iter().enumerate() { + for &impl2_def_id in &blanket_impls[(i+1)..] { self.check_if_impls_overlap(trait_def_id, impl1_def_id, impl2_def_id); } + + for v in nonblanket_impls.values() { + for &impl2_def_id in v { + self.check_if_impls_overlap(trait_def_id, + impl1_def_id, + impl2_def_id); + } + } + } + + for impl_group in nonblanket_impls.values() { + for (i, &impl1_def_id) in impl_group.iter().enumerate() { + for &impl2_def_id in &impl_group[(i+1)..] { + self.check_if_impls_overlap(trait_def_id, + impl1_def_id, + impl2_def_id); + } + } } } + // We need to coherently pick which impl will be displayed + // as causing the error message, and it must be the in the current + // crate. Just pick the smaller impl in the file. + fn order_impls(&self, impl1_def_id: ast::DefId, impl2_def_id: ast::DefId) + -> Option<(ast::DefId, ast::DefId)> { + if impl1_def_id.krate != ast::LOCAL_CRATE { + if impl2_def_id.krate != ast::LOCAL_CRATE { + // we don't need to check impls if both are external; + // that's the other crate's job. + None + } else { + Some((impl2_def_id, impl1_def_id)) + } + } else if impl2_def_id.krate != ast::LOCAL_CRATE { + Some((impl1_def_id, impl2_def_id)) + } else if impl1_def_id.node < impl2_def_id.node { + Some((impl1_def_id, impl2_def_id)) + } else { + Some((impl2_def_id, impl1_def_id)) + } + } + + fn check_if_impls_overlap(&self, trait_def_id: ast::DefId, impl1_def_id: ast::DefId, impl2_def_id: ast::DefId) { - assert_eq!(impl1_def_id.krate, ast::LOCAL_CRATE); - - debug!("check_if_impls_overlap({}, {}, {})", - trait_def_id.repr(self.tcx), - impl1_def_id.repr(self.tcx), - impl2_def_id.repr(self.tcx)); - - let infcx = infer::new_infer_ctxt(self.tcx); - if !traits::overlapping_impls(&infcx, impl1_def_id, impl2_def_id) { - return; + if let Some((impl1_def_id, impl2_def_id)) = self.order_impls( + impl1_def_id, impl2_def_id) + { + debug!("check_if_impls_overlap({}, {}, {})", + trait_def_id.repr(self.tcx), + impl1_def_id.repr(self.tcx), + impl2_def_id.repr(self.tcx)); + + let infcx = infer::new_infer_ctxt(self.tcx); + if traits::overlapping_impls(&infcx, impl1_def_id, impl2_def_id) { + self.report_overlap_error(trait_def_id, impl1_def_id, impl2_def_id); + } } - - self.report_overlap_error(trait_def_id, impl1_def_id, impl2_def_id); } fn report_overlap_error(&self, trait_def_id: ast::DefId, diff --git a/src/librustc_typeck/collect.rs b/src/librustc_typeck/collect.rs index 6cb6df008c1..6f78e853ebe 100644 --- a/src/librustc_typeck/collect.rs +++ b/src/librustc_typeck/collect.rs @@ -83,7 +83,7 @@ use util::ppaux; use util::ppaux::{Repr,UserString}; use write_ty_to_tcx; -use std::cell::RefCell; +use std::cell::{Cell, RefCell}; use std::collections::HashSet; use std::rc::Rc; @@ -309,7 +309,7 @@ impl<'a,'tcx> CrateCtxt<'a,'tcx> { /// Loads the trait def for a given trait, returning ErrorReported if a cycle arises. fn get_trait_def(&self, trait_id: ast::DefId) - -> Rc<ty::TraitDef<'tcx>> + -> &'tcx ty::TraitDef<'tcx> { let tcx = self.tcx; @@ -361,7 +361,7 @@ impl<'a, 'tcx> AstConv<'tcx> for ItemCtxt<'a, 'tcx> { } fn get_trait_def(&self, span: Span, id: ast::DefId) - -> Result<Rc<ty::TraitDef<'tcx>>, ErrorReported> + -> Result<&'tcx ty::TraitDef<'tcx>, ErrorReported> { self.ccx.cycle_check(span, AstConvRequest::GetTraitDef(id), || { Ok(self.ccx.get_trait_def(id)) @@ -415,7 +415,7 @@ impl<'a, 'tcx> AstConv<'tcx> for ItemCtxt<'a, 'tcx> { fn projected_ty(&self, _span: Span, - trait_ref: Rc<ty::TraitRef<'tcx>>, + trait_ref: ty::TraitRef<'tcx>, item_name: ast::Name) -> Ty<'tcx> { @@ -1210,7 +1210,7 @@ fn ensure_super_predicates_step(ccx: &CrateCtxt, fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, it: &ast::Item) - -> Rc<ty::TraitDef<'tcx>> + -> &'tcx ty::TraitDef<'tcx> { let def_id = local_def(it.id); let tcx = ccx.tcx; @@ -1246,22 +1246,23 @@ fn trait_def_of_item<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, } }).collect(); - let trait_ref = Rc::new(ty::TraitRef { + let trait_ref = ty::TraitRef { def_id: def_id, substs: substs, - }); + }; - let trait_def = Rc::new(ty::TraitDef { + let trait_def = ty::TraitDef { paren_sugar: paren_sugar, unsafety: unsafety, generics: ty_generics, trait_ref: trait_ref, associated_type_names: associated_type_names, - }); - - tcx.trait_defs.borrow_mut().insert(def_id, trait_def.clone()); + nonblanket_impls: RefCell::new(FnvHashMap()), + blanket_impls: RefCell::new(vec![]), + flags: Cell::new(ty::TraitFlags::NO_TRAIT_FLAGS) + }; - return trait_def; + return tcx.intern_trait_def(trait_def); fn mk_trait_substs<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, generics: &ast::Generics) @@ -1357,7 +1358,7 @@ fn convert_trait_predicates<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, it: &ast::Item) let assoc_predicates = predicates_for_associated_types(ccx, generics, &trait_predicates, - &trait_def.trait_ref, + trait_def.trait_ref, items); trait_predicates.predicates.extend(TypeSpace, assoc_predicates.into_iter()); @@ -1369,7 +1370,7 @@ fn convert_trait_predicates<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, it: &ast::Item) fn predicates_for_associated_types<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, ast_generics: &ast::Generics, trait_predicates: &ty::GenericPredicates<'tcx>, - self_trait_ref: &Rc<ty::TraitRef<'tcx>>, + self_trait_ref: ty::TraitRef<'tcx>, trait_items: &[P<ast::TraitItem>]) -> Vec<ty::Predicate<'tcx>> { @@ -1382,7 +1383,7 @@ fn convert_trait_predicates<'a, 'tcx>(ccx: &CrateCtxt<'a, 'tcx>, it: &ast::Item) }; let assoc_ty = ty::mk_projection(ccx.tcx, - self_trait_ref.clone(), + self_trait_ref, trait_item.ident.name); let bounds = compute_bounds(&ccx.icx(&(ast_generics, trait_predicates)), diff --git a/src/librustc_typeck/constrained_type_params.rs b/src/librustc_typeck/constrained_type_params.rs index fad8fbef2a4..3c8aab8447a 100644 --- a/src/librustc_typeck/constrained_type_params.rs +++ b/src/librustc_typeck/constrained_type_params.rs @@ -12,7 +12,6 @@ use middle::subst; use middle::ty::{self, Ty}; use std::collections::HashSet; -use std::rc::Rc; #[derive(Clone, PartialEq, Eq, Hash, Debug)] pub enum Parameter { @@ -26,7 +25,7 @@ pub fn parameters_for_type<'tcx>(ty: Ty<'tcx>) -> Vec<Parameter> { .collect() } -pub fn parameters_for_trait_ref<'tcx>(trait_ref: &Rc<ty::TraitRef<'tcx>>) -> Vec<Parameter> { +pub fn parameters_for_trait_ref<'tcx>(trait_ref: &ty::TraitRef<'tcx>) -> Vec<Parameter> { let mut region_parameters = parameters_for_regions_in_substs(&trait_ref.substs); @@ -71,7 +70,7 @@ fn parameters_for_region(region: &ty::Region) -> Option<Parameter> { pub fn identify_constrained_type_params<'tcx>(_tcx: &ty::ctxt<'tcx>, predicates: &[ty::Predicate<'tcx>], - impl_trait_ref: Option<Rc<ty::TraitRef<'tcx>>>, + impl_trait_ref: Option<ty::TraitRef<'tcx>>, input_parameters: &mut HashSet<Parameter>) { loop { diff --git a/src/librustc_typeck/variance.rs b/src/librustc_typeck/variance.rs index 7575f12878a..9e8c23734e3 100644 --- a/src/librustc_typeck/variance.rs +++ b/src/librustc_typeck/variance.rs @@ -654,7 +654,7 @@ impl<'a, 'tcx, 'v> Visitor<'v> for ConstraintContext<'a, 'tcx> { ast::ItemTrait(..) => { let trait_def = ty::lookup_trait_def(tcx, did); self.add_constraints_from_trait_ref(&trait_def.generics, - &trait_def.trait_ref, + trait_def.trait_ref, self.invariant); } @@ -844,7 +844,7 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> { fn add_constraints_from_trait_ref(&mut self, generics: &ty::Generics<'tcx>, - trait_ref: &ty::TraitRef<'tcx>, + trait_ref: ty::TraitRef<'tcx>, variance: VarianceTermPtr<'a>) { debug!("add_constraints_from_trait_ref: trait_ref={} variance={:?}", trait_ref.repr(self.tcx()), @@ -946,7 +946,7 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> { self.add_constraints_from_region(generics, data.bounds.region_bound, contra); // Ignore the SelfSpace, it is erased. - self.add_constraints_from_trait_ref(generics, &*poly_trait_ref.0, variance); + self.add_constraints_from_trait_ref(generics, poly_trait_ref.0, variance); let projections = data.projection_bounds_with_self_ty(self.tcx(), self.tcx().types.err); |