diff options
| -rw-r--r-- | src/librustc/ty/relate.rs | 6 | ||||
| -rw-r--r-- | src/librustc_metadata/encoder.rs | 31 | ||||
| -rw-r--r-- | src/librustc_typeck/variance/constraints.rs | 392 | ||||
| -rw-r--r-- | src/librustc_typeck/variance/mod.rs | 88 | ||||
| -rw-r--r-- | src/librustc_typeck/variance/solve.rs | 73 | ||||
| -rw-r--r-- | src/librustc_typeck/variance/terms.rs | 160 | ||||
| -rw-r--r-- | src/test/compile-fail/variance-region-bounds.rs | 25 | ||||
| -rw-r--r-- | src/test/compile-fail/variance-trait-bounds.rs | 20 | ||||
| -rw-r--r-- | src/test/compile-fail/variance-types-bounds.rs | 27 |
9 files changed, 317 insertions, 505 deletions
diff --git a/src/librustc/ty/relate.rs b/src/librustc/ty/relate.rs index 9345e504701..2e9780572c9 100644 --- a/src/librustc/ty/relate.rs +++ b/src/librustc/ty/relate.rs @@ -291,7 +291,7 @@ impl<'tcx> Relate<'tcx> for ty::TraitRef<'tcx> { if a.def_id != b.def_id { Err(TypeError::Traits(expected_found(relation, &a.def_id, &b.def_id))) } else { - let substs = relation.relate_item_substs(a.def_id, a.substs, b.substs)?; + let substs = relate_substs(relation, None, a.substs, b.substs)?; Ok(ty::TraitRef { def_id: a.def_id, substs: substs }) } } @@ -308,7 +308,7 @@ impl<'tcx> Relate<'tcx> for ty::ExistentialTraitRef<'tcx> { if a.def_id != b.def_id { Err(TypeError::Traits(expected_found(relation, &a.def_id, &b.def_id))) } else { - let substs = relation.relate_item_substs(a.def_id, a.substs, b.substs)?; + let substs = relate_substs(relation, None, a.substs, b.substs)?; Ok(ty::ExistentialTraitRef { def_id: a.def_id, substs: substs }) } } @@ -443,7 +443,7 @@ pub fn super_relate_tys<'a, 'gcx, 'tcx, R>(relation: &mut R, (&ty::TyFnDef(a_def_id, a_substs), &ty::TyFnDef(b_def_id, b_substs)) if a_def_id == b_def_id => { - let substs = relate_substs(relation, None, a_substs, b_substs)?; + let substs = relation.relate_item_substs(a_def_id, a_substs, b_substs)?; Ok(tcx.mk_fn_def(a_def_id, substs)) } diff --git a/src/librustc_metadata/encoder.rs b/src/librustc_metadata/encoder.rs index 34b25a4b7e4..e9701b95002 100644 --- a/src/librustc_metadata/encoder.rs +++ b/src/librustc_metadata/encoder.rs @@ -524,7 +524,11 @@ impl<'a, 'b: 'a, 'tcx: 'b> IsolatedEncoder<'a, 'b, 'tcx> { ty: Some(self.encode_item_type(def_id)), inherent_impls: LazySeq::empty(), - variances: LazySeq::empty(), + variances: if variant.ctor_kind == CtorKind::Fn { + self.encode_variances_of(def_id) + } else { + LazySeq::empty() + }, generics: Some(self.encode_generics(def_id)), predicates: Some(self.encode_predicates(def_id)), @@ -652,7 +656,11 @@ impl<'a, 'b: 'a, 'tcx: 'b> IsolatedEncoder<'a, 'b, 'tcx> { ty: Some(self.encode_item_type(def_id)), inherent_impls: LazySeq::empty(), - variances: LazySeq::empty(), + variances: if variant.ctor_kind == CtorKind::Fn { + self.encode_variances_of(def_id) + } else { + LazySeq::empty() + }, generics: Some(self.encode_generics(def_id)), predicates: Some(self.encode_predicates(def_id)), @@ -744,7 +752,11 @@ impl<'a, 'b: 'a, 'tcx: 'b> IsolatedEncoder<'a, 'b, 'tcx> { } }, inherent_impls: LazySeq::empty(), - variances: LazySeq::empty(), + variances: if trait_item.kind == ty::AssociatedKind::Method { + self.encode_variances_of(def_id) + } else { + LazySeq::empty() + }, generics: Some(self.encode_generics(def_id)), predicates: Some(self.encode_predicates(def_id)), @@ -821,7 +833,11 @@ impl<'a, 'b: 'a, 'tcx: 'b> IsolatedEncoder<'a, 'b, 'tcx> { ty: Some(self.encode_item_type(def_id)), inherent_impls: LazySeq::empty(), - variances: LazySeq::empty(), + variances: if impl_item.kind == ty::AssociatedKind::Method { + self.encode_variances_of(def_id) + } else { + LazySeq::empty() + }, generics: Some(self.encode_generics(def_id)), predicates: Some(self.encode_predicates(def_id)), @@ -1055,7 +1071,7 @@ impl<'a, 'b: 'a, 'tcx: 'b> IsolatedEncoder<'a, 'b, 'tcx> { hir::ItemEnum(..) | hir::ItemStruct(..) | hir::ItemUnion(..) | - hir::ItemTrait(..) => self.encode_variances_of(def_id), + hir::ItemFn(..) => self.encode_variances_of(def_id), _ => LazySeq::empty(), }, generics: match item.node { @@ -1400,7 +1416,10 @@ impl<'a, 'b: 'a, 'tcx: 'b> IsolatedEncoder<'a, 'b, 'tcx> { ty: Some(self.encode_item_type(def_id)), inherent_impls: LazySeq::empty(), - variances: LazySeq::empty(), + variances: match nitem.node { + hir::ForeignItemFn(..) => self.encode_variances_of(def_id), + _ => LazySeq::empty(), + }, generics: Some(self.encode_generics(def_id)), predicates: Some(self.encode_predicates(def_id)), diff --git a/src/librustc_typeck/variance/constraints.rs b/src/librustc_typeck/variance/constraints.rs index 4c09d90f853..f4963619370 100644 --- a/src/librustc_typeck/variance/constraints.rs +++ b/src/librustc_typeck/variance/constraints.rs @@ -14,11 +14,9 @@ //! We walk the set of items and, for each member, generate new constraints. use hir::def_id::DefId; -use middle::resolve_lifetime as rl; use rustc::dep_graph::{AssertDepGraphSafe, DepKind}; use rustc::ty::subst::Substs; use rustc::ty::{self, Ty, TyCtxt}; -use rustc::hir::map as hir_map; use syntax::ast; use rustc::hir; use rustc::hir::itemlikevisit::ItemLikeVisitor; @@ -61,10 +59,10 @@ pub struct Constraint<'a> { /// } /// /// then while we are visiting `Bar<T>`, the `CurrentItem` would have -/// the def-id and generics of `Foo`. -pub struct CurrentItem<'a> { +/// the def-id and the start of `Foo`'s inferreds. +pub struct CurrentItem { def_id: DefId, - generics: &'a ty::Generics, + inferred_start: InferredIndex, } pub fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>) @@ -91,8 +89,59 @@ pub fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>) impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for ConstraintContext<'a, 'tcx> { fn visit_item(&mut self, item: &hir::Item) { + match item.node { + hir::ItemStruct(ref struct_def, _) | + hir::ItemUnion(ref struct_def, _) => { + self.visit_node_helper(item.id); + + if let hir::VariantData::Tuple(..) = *struct_def { + self.visit_node_helper(struct_def.id()); + } + } + + hir::ItemEnum(ref enum_def, _) => { + self.visit_node_helper(item.id); + + for variant in &enum_def.variants { + if let hir::VariantData::Tuple(..) = variant.node.data { + self.visit_node_helper(variant.node.data.id()); + } + } + } + + hir::ItemFn(..) => { + self.visit_node_helper(item.id); + } + + hir::ItemForeignMod(ref foreign_mod) => { + for foreign_item in &foreign_mod.items { + if let hir::ForeignItemFn(..) = foreign_item.node { + self.visit_node_helper(foreign_item.id); + } + } + } + + _ => {} + } + } + + fn visit_trait_item(&mut self, trait_item: &hir::TraitItem) { + if let hir::TraitItemKind::Method(..) = trait_item.node { + self.visit_node_helper(trait_item.id); + } + } + + fn visit_impl_item(&mut self, impl_item: &hir::ImplItem) { + if let hir::ImplItemKind::Method(..) = impl_item.node { + self.visit_node_helper(impl_item.id); + } + } +} + +impl<'a, 'tcx> ConstraintContext<'a, 'tcx> { + fn visit_node_helper(&mut self, id: ast::NodeId) { let tcx = self.terms_cx.tcx; - let def_id = tcx.hir.local_def_id(item.id); + let def_id = tcx.hir.local_def_id(id); // Encapsulate constructing the constraints into a task we can // reference later. This can go away once the red-green @@ -100,20 +149,11 @@ impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for ConstraintContext<'a, 'tcx> { // // See README.md for a detailed discussion // on dep-graph management. - match item.node { - hir::ItemEnum(..) | - hir::ItemStruct(..) | - hir::ItemUnion(..) => { - let dep_node = def_id.to_dep_node(tcx, DepKind::ItemVarianceConstraints); - tcx.dep_graph.with_task(dep_node, - AssertDepGraphSafe(self), - def_id, - visit_item_task); - } - _ => { - // Nothing to do here, skip the task. - } - } + let dep_node = def_id.to_dep_node(tcx, DepKind::ItemVarianceConstraints); + tcx.dep_graph.with_task(dep_node, + AssertDepGraphSafe(self), + def_id, + visit_item_task); fn visit_item_task<'a, 'tcx>(ccx: AssertDepGraphSafe<&mut ConstraintContext<'a, 'tcx>>, def_id: DefId) @@ -122,197 +162,57 @@ impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for ConstraintContext<'a, 'tcx> { } } - fn visit_trait_item(&mut self, _trait_item: &hir::TraitItem) { - } - - fn visit_impl_item(&mut self, _impl_item: &hir::ImplItem) { - } -} - -/// Is `param_id` a lifetime according to `map`? -fn is_lifetime(map: &hir_map::Map, param_id: ast::NodeId) -> bool { - match map.find(param_id) { - Some(hir_map::NodeLifetime(..)) => true, - _ => false, - } -} - -impl<'a, 'tcx> ConstraintContext<'a, 'tcx> { fn tcx(&self) -> TyCtxt<'a, 'tcx, 'tcx> { self.terms_cx.tcx } fn build_constraints_for_item(&mut self, def_id: DefId) { let tcx = self.tcx(); - let id = self.tcx().hir.as_local_node_id(def_id).unwrap(); - let item = tcx.hir.expect_item(id); - debug!("visit_item item={}", tcx.hir.node_to_string(item.id)); + debug!("build_constraints_for_item({})", tcx.item_path_str(def_id)); - match item.node { - hir::ItemEnum(..) | - hir::ItemStruct(..) | - hir::ItemUnion(..) => { - let generics = tcx.generics_of(def_id); - let current_item = &CurrentItem { def_id, generics }; + // Skip items with no generics - there's nothing to infer in them. + if tcx.generics_of(def_id).count() == 0 { + return; + } + let id = tcx.hir.as_local_node_id(def_id).unwrap(); + let inferred_start = self.terms_cx.inferred_starts[&id]; + let current_item = &CurrentItem { def_id, inferred_start }; + match tcx.type_of(def_id).sty { + ty::TyAdt(def, _) => { // Not entirely obvious: constraints on structs/enums do not // affect the variance of their type parameters. See discussion // in comment at top of module. // // self.add_constraints_from_generics(generics); - for field in tcx.adt_def(def_id).all_fields() { + for field in def.all_fields() { self.add_constraints_from_ty(current_item, tcx.type_of(field.did), self.covariant); } } - hir::ItemTrait(..) | - hir::ItemExternCrate(_) | - hir::ItemUse(..) | - hir::ItemStatic(..) | - hir::ItemConst(..) | - hir::ItemFn(..) | - hir::ItemMod(..) | - hir::ItemForeignMod(..) | - hir::ItemGlobalAsm(..) | - hir::ItemTy(..) | - hir::ItemImpl(..) | - hir::ItemDefaultImpl(..) => { - span_bug!(item.span, "`build_constraints_for_item` invoked for non-type-def"); + ty::TyFnDef(..) => { + self.add_constraints_from_sig(current_item, + tcx.fn_sig(def_id), + self.covariant); } - } - } - - /// Load the generics for another item, adding a corresponding - /// relation into the dependencies to indicate that the variance - /// for `current` relies on `def_id`. - fn read_generics(&mut self, current: &CurrentItem, def_id: DefId) -> &'tcx ty::Generics { - let generics = self.tcx().generics_of(def_id); - if self.tcx().dep_graph.is_fully_enabled() { - self.dependencies.add(current.def_id, def_id); - } - generics - } - fn opt_inferred_index(&self, param_id: ast::NodeId) -> Option<&InferredIndex> { - self.terms_cx.inferred_map.get(¶m_id) - } - - fn find_binding_for_lifetime(&self, param_id: ast::NodeId) -> ast::NodeId { - let tcx = self.terms_cx.tcx; - assert!(is_lifetime(&tcx.hir, param_id)); - match tcx.named_region_map.defs.get(¶m_id) { - Some(&rl::Region::EarlyBound(_, lifetime_decl_id)) => lifetime_decl_id, - Some(_) => bug!("should not encounter non early-bound cases"), - - // The lookup should only fail when `param_id` is - // itself a lifetime binding: use it as the decl_id. - None => param_id, - } - - } - - /// Is `param_id` a type parameter for which we infer variance? - fn is_to_be_inferred(&self, param_id: ast::NodeId) -> bool { - let result = self.terms_cx.inferred_map.contains_key(¶m_id); - - // To safe-guard against invalid inferred_map constructions, - // double-check if variance is inferred at some use of a type - // parameter (by inspecting parent of its binding declaration - // to see if it is introduced by a type or by a fn/impl). - - let check_result = |this: &ConstraintContext| -> bool { - let tcx = this.terms_cx.tcx; - let decl_id = this.find_binding_for_lifetime(param_id); - // Currently only called on lifetimes; double-checking that. - assert!(is_lifetime(&tcx.hir, param_id)); - let parent_id = tcx.hir.get_parent(decl_id); - let parent = tcx.hir - .find(parent_id) - .unwrap_or_else(|| bug!("tcx.hir missing entry for id: {}", parent_id)); - - let is_inferred; - macro_rules! cannot_happen { () => { { - bug!("invalid parent: {} for {}", - tcx.hir.node_to_string(parent_id), - tcx.hir.node_to_string(param_id)); - } } } - - match parent { - hir_map::NodeItem(p) => { - match p.node { - hir::ItemTy(..) | - hir::ItemEnum(..) | - hir::ItemStruct(..) | - hir::ItemUnion(..) | - hir::ItemTrait(..) => is_inferred = true, - hir::ItemFn(..) => is_inferred = false, - _ => cannot_happen!(), - } - } - hir_map::NodeTraitItem(..) => is_inferred = false, - hir_map::NodeImplItem(..) => is_inferred = false, - _ => cannot_happen!(), - } - - return is_inferred; - }; - - assert_eq!(result, check_result(self)); - - return result; - } - - /// Returns a variance term representing the declared variance of the type/region parameter - /// with the given id. - fn declared_variance(&self, - param_def_id: DefId, - item_def_id: DefId, - index: usize) - -> VarianceTermPtr<'a> { - assert_eq!(param_def_id.krate, item_def_id.krate); - - if let Some(param_node_id) = self.tcx().hir.as_local_node_id(param_def_id) { - // Parameter on an item defined within current crate: - // variance not yet inferred, so return a symbolic - // variance. - if let Some(&InferredIndex(index)) = self.opt_inferred_index(param_node_id) { - self.terms_cx.inferred_infos[index].term - } else { - // If there is no inferred entry for a type parameter, - // it must be declared on a (locally defiend) trait -- they don't - // get inferreds because they are always invariant. - if cfg!(debug_assertions) { - let item_node_id = self.tcx().hir.as_local_node_id(item_def_id).unwrap(); - let item = self.tcx().hir.expect_item(item_node_id); - let success = match item.node { - hir::ItemTrait(..) => true, - _ => false, - }; - if !success { - bug!("parameter {:?} has no inferred, but declared on non-trait: {:?}", - item_def_id, - item); - } - } - self.invariant + _ => { + span_bug!(tcx.def_span(def_id), + "`build_constraints_for_item` unsupported for this item"); } - } else { - // Parameter on an item defined within another crate: - // variance already inferred, just look it up. - let variances = self.tcx().variances_of(item_def_id); - self.constant_term(variances[index]) } } fn add_constraint(&mut self, - InferredIndex(index): InferredIndex, + current: &CurrentItem, + index: u32, variance: VarianceTermPtr<'a>) { debug!("add_constraint(index={}, variance={:?})", index, variance); self.constraints.push(Constraint { - inferred: InferredIndex(index), + inferred: InferredIndex(current.inferred_start.0 + index as usize), variance: variance, }); } @@ -354,15 +254,26 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> { debug!("add_constraints_from_trait_ref: trait_ref={:?} variance={:?}", trait_ref, variance); + self.add_constraints_from_invariant_substs(current, trait_ref.substs, variance); + } - let trait_generics = self.tcx().generics_of(trait_ref.def_id); + fn add_constraints_from_invariant_substs(&mut self, + current: &CurrentItem, + substs: &Substs<'tcx>, + variance: VarianceTermPtr<'a>) { + debug!("add_constraints_from_invariant_substs: substs={:?} variance={:?}", + substs, + variance); - self.add_constraints_from_substs(current, - trait_ref.def_id, - &trait_generics.types, - &trait_generics.regions, - trait_ref.substs, - variance); + // Trait are always invariant so we can take advantage of that. + let variance_i = self.invariant(variance); + for ty in substs.types() { + self.add_constraints_from_ty(current, ty, variance_i); + } + + for region in substs.regions() { + self.add_constraints_from_region(current, region, variance_i); + } } /// Adds constraints appropriate for an instance of `ty` appearing @@ -383,8 +294,7 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> { } ty::TyFnDef(..) | - ty::TyClosure(..) | - ty::TyAnon(..) => { + ty::TyClosure(..) => { bug!("Unexpected closure type in variance computation"); } @@ -410,26 +320,15 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> { } ty::TyAdt(def, substs) => { - let adt_generics = self.read_generics(current, def.did); - - self.add_constraints_from_substs(current, - def.did, - &adt_generics.types, - &adt_generics.regions, - substs, - variance); + self.add_constraints_from_substs(current, def.did, substs, variance); } ty::TyProjection(ref data) => { - let trait_ref = &data.trait_ref; - let trait_generics = self.tcx().generics_of(trait_ref.def_id); - - self.add_constraints_from_substs(current, - trait_ref.def_id, - &trait_generics.types, - &trait_generics.regions, - trait_ref.substs, - variance); + self.add_constraints_from_trait_ref(current, data.trait_ref, variance); + } + + ty::TyAnon(_, substs) => { + self.add_constraints_from_invariant_substs(current, substs, variance); } ty::TyDynamic(ref data, r) => { @@ -448,23 +347,7 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> { } ty::TyParam(ref data) => { - assert_eq!(current.generics.parent, None); - let mut i = data.idx as usize; - if !current.generics.has_self || i > 0 { - i -= current.generics.regions.len(); - } - let def_id = current.generics.types[i].def_id; - let node_id = self.tcx().hir.as_local_node_id(def_id).unwrap(); - match self.terms_cx.inferred_map.get(&node_id) { - Some(&index) => { - self.add_constraint(index, variance); - } - None => { - // We do not infer variance for type parameters - // declared on methods. They will not be present - // in the inferred_map. - } - } + self.add_constraint(current, data.idx, variance); } ty::TyFnPtr(sig) => { @@ -489,8 +372,6 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> { fn add_constraints_from_substs(&mut self, current: &CurrentItem, def_id: DefId, - type_param_defs: &[ty::TypeParameterDef], - region_param_defs: &[ty::RegionParameterDef], substs: &Substs<'tcx>, variance: VarianceTermPtr<'a>) { debug!("add_constraints_from_substs(def_id={:?}, substs={:?}, variance={:?})", @@ -498,21 +379,45 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> { substs, variance); - for p in type_param_defs { - let variance_decl = self.declared_variance(p.def_id, def_id, p.index as usize); + // We don't record `inferred_starts` entries for empty generics. + if substs.is_empty() { + return; + } + + // Add a corresponding relation into the dependencies to + // indicate that the variance for `current` relies on `def_id`. + if self.tcx().dep_graph.is_fully_enabled() { + self.dependencies.add(current.def_id, def_id); + } + + let (local, remote) = if let Some(id) = self.tcx().hir.as_local_node_id(def_id) { + (Some(self.terms_cx.inferred_starts[&id]), None) + } else { + (None, Some(self.tcx().variances_of(def_id))) + }; + + for (i, k) in substs.iter().enumerate() { + let variance_decl = if let Some(InferredIndex(start)) = local { + // Parameter on an item defined within current crate: + // variance not yet inferred, so return a symbolic + // variance. + self.terms_cx.inferred_terms[start + i] + } else { + // Parameter on an item defined within another crate: + // variance already inferred, just look it up. + self.constant_term(remote.as_ref().unwrap()[i]) + }; let variance_i = self.xform(variance, variance_decl); - let substs_ty = substs.type_for_def(p); debug!("add_constraints_from_substs: variance_decl={:?} variance_i={:?}", variance_decl, variance_i); - self.add_constraints_from_ty(current, substs_ty, variance_i); - } - - for p in region_param_defs { - let variance_decl = self.declared_variance(p.def_id, def_id, p.index as usize); - let variance_i = self.xform(variance, variance_decl); - let substs_r = substs.region_for_def(p); - self.add_constraints_from_region(current, substs_r, variance_i); + if let Some(ty) = k.as_type() { + self.add_constraints_from_ty(current, ty, variance_i); + } else if let Some(r) = k.as_region() { + self.add_constraints_from_region(current, r, variance_i); + } else { + bug!(); + } } } @@ -537,21 +442,14 @@ impl<'a, 'tcx> ConstraintContext<'a, 'tcx> { variance: VarianceTermPtr<'a>) { match *region { ty::ReEarlyBound(ref data) => { - assert_eq!(current.generics.parent, None); - let i = data.index as usize - current.generics.has_self as usize; - let def_id = current.generics.regions[i].def_id; - let node_id = self.tcx().hir.as_local_node_id(def_id).unwrap(); - if self.is_to_be_inferred(node_id) { - let &index = self.opt_inferred_index(node_id).unwrap(); - self.add_constraint(index, variance); - } + self.add_constraint(current, data.index, variance); } ty::ReStatic => {} ty::ReLateBound(..) => { - // We do not infer variance for region parameters on - // methods or in fn types. + // Late-bound regions do not get substituted the same + // way early-bound regions do, so we skip them here. } ty::ReFree(..) | diff --git a/src/librustc_typeck/variance/mod.rs b/src/librustc_typeck/variance/mod.rs index 8f9f40ca40b..7a9f35545e2 100644 --- a/src/librustc_typeck/variance/mod.rs +++ b/src/librustc_typeck/variance/mod.rs @@ -54,45 +54,63 @@ fn crate_variances<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, crate_num: CrateNum) fn variances_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, item_def_id: DefId) -> Rc<Vec<ty::Variance>> { - let item_id = tcx.hir.as_local_node_id(item_def_id).expect("expected local def-id"); - let item = tcx.hir.expect_item(item_id); - match item.node { - hir::ItemTrait(..) => { - // Traits are always invariant. - let generics = tcx.generics_of(item_def_id); - assert!(generics.parent.is_none()); - Rc::new(vec![ty::Variance::Invariant; generics.count()]) - } + let id = tcx.hir.as_local_node_id(item_def_id).expect("expected local def-id"); + let unsupported = || { + // Variance not relevant. + span_bug!(tcx.hir.span(id), "asked to compute variance for wrong kind of item") + }; + match tcx.hir.get(id) { + hir::map::NodeItem(item) => match item.node { + hir::ItemEnum(..) | + hir::ItemStruct(..) | + hir::ItemUnion(..) | + hir::ItemFn(..) => {} - hir::ItemEnum(..) | - hir::ItemStruct(..) | - hir::ItemUnion(..) => { - // Everything else must be inferred. + _ => unsupported() + }, - // Lacking red/green, we read the variances for all items here - // but ignore the dependencies, then re-synthesize the ones we need. - let crate_map = tcx.dep_graph.with_ignore(|| tcx.crate_variances(LOCAL_CRATE)); - let dep_node = item_def_id.to_dep_node(tcx, DepKind::ItemVarianceConstraints); - tcx.dep_graph.read(dep_node); - for &dep_def_id in crate_map.dependencies.less_than(&item_def_id) { - if dep_def_id.is_local() { - let dep_node = dep_def_id.to_dep_node(tcx, DepKind::ItemVarianceConstraints); - tcx.dep_graph.read(dep_node); - } else { - let dep_node = dep_def_id.to_dep_node(tcx, DepKind::ItemVariances); - tcx.dep_graph.read(dep_node); - } - } - - crate_map.variances.get(&item_def_id) - .unwrap_or(&crate_map.empty_variance) - .clone() - } + hir::map::NodeTraitItem(item) => match item.node { + hir::TraitItemKind::Method(..) => {} + + _ => unsupported() + }, + + hir::map::NodeImplItem(item) => match item.node { + hir::ImplItemKind::Method(..) => {} + + _ => unsupported() + }, + + hir::map::NodeForeignItem(item) => match item.node { + hir::ForeignItemFn(..) => {} - _ => { - // Variance not relevant. - span_bug!(item.span, "asked to compute variance for wrong kind of item") + _ => unsupported() + }, + + hir::map::NodeVariant(_) | hir::map::NodeStructCtor(_) => {} + + _ => unsupported() + } + + // Everything else must be inferred. + + // Lacking red/green, we read the variances for all items here + // but ignore the dependencies, then re-synthesize the ones we need. + let crate_map = tcx.dep_graph.with_ignore(|| tcx.crate_variances(LOCAL_CRATE)); + let dep_node = item_def_id.to_dep_node(tcx, DepKind::ItemVarianceConstraints); + tcx.dep_graph.read(dep_node); + for &dep_def_id in crate_map.dependencies.less_than(&item_def_id) { + if dep_def_id.is_local() { + let dep_node = dep_def_id.to_dep_node(tcx, DepKind::ItemVarianceConstraints); + tcx.dep_graph.read(dep_node); + } else { + let dep_node = dep_def_id.to_dep_node(tcx, DepKind::ItemVariances); + tcx.dep_graph.read(dep_node); } } + + crate_map.variances.get(&item_def_id) + .unwrap_or(&crate_map.empty_variance) + .clone() } diff --git a/src/librustc_typeck/variance/solve.rs b/src/librustc_typeck/variance/solve.rs index af8ad491ec0..495eb95419a 100644 --- a/src/librustc_typeck/variance/solve.rs +++ b/src/librustc_typeck/variance/solve.rs @@ -36,15 +36,18 @@ struct SolveContext<'a, 'tcx: 'a> { pub fn solve_constraints(constraints_cx: ConstraintContext) -> ty::CrateVariancesMap { let ConstraintContext { terms_cx, dependencies, constraints, .. } = constraints_cx; - let solutions = terms_cx.inferred_infos - .iter() - .map(|ii| ii.initial_variance) - .collect(); + let mut solutions = vec![ty::Bivariant; terms_cx.inferred_terms.len()]; + for &(id, ref variances) in &terms_cx.lang_items { + let InferredIndex(start) = terms_cx.inferred_starts[&id]; + for (i, &variance) in variances.iter().enumerate() { + solutions[start + i] = variance; + } + } let mut solutions_cx = SolveContext { - terms_cx: terms_cx, - constraints: constraints, - solutions: solutions, + terms_cx, + constraints, + solutions, }; solutions_cx.solve(); let variances = solutions_cx.create_map(); @@ -71,12 +74,9 @@ impl<'a, 'tcx> SolveContext<'a, 'tcx> { let old_value = self.solutions[inferred]; let new_value = glb(variance, old_value); if old_value != new_value { - debug!("Updating inferred {} (node {}) \ + debug!("Updating inferred {} \ from {:?} to {:?} due to {:?}", inferred, - self.terms_cx - .inferred_infos[inferred] - .param_id, old_value, new_value, term); @@ -89,49 +89,28 @@ impl<'a, 'tcx> SolveContext<'a, 'tcx> { } fn create_map(&self) -> FxHashMap<DefId, Rc<Vec<ty::Variance>>> { - // Collect all the variances for a particular item and stick - // them into the variance map. We rely on the fact that we - // generate all the inferreds for a particular item - // consecutively (that is, we collect solutions for an item - // until we see a new item id, and we assume (1) the solutions - // are in the same order as the type parameters were declared - // and (2) all solutions or a given item appear before a new - // item id). - let tcx = self.terms_cx.tcx; - let mut map = FxHashMap(); - let solutions = &self.solutions; - let inferred_infos = &self.terms_cx.inferred_infos; - let mut index = 0; - let num_inferred = self.terms_cx.num_inferred(); - while index < num_inferred { - let item_id = inferred_infos[index].item_id; - - let mut item_variances = vec![]; - - while index < num_inferred && inferred_infos[index].item_id == item_id { - let info = &inferred_infos[index]; - let variance = solutions[index]; - debug!("Index {} Info {} Variance {:?}", - index, - info.index, - variance); - - assert_eq!(item_variances.len(), info.index); - item_variances.push(variance); - index += 1; - } + self.terms_cx.inferred_starts.iter().map(|(&id, &InferredIndex(start))| { + let def_id = tcx.hir.local_def_id(id); + let generics = tcx.generics_of(def_id); - debug!("item_id={} item_variances={:?}", item_id, item_variances); + let mut variances = solutions[start..start+generics.count()].to_vec(); - let item_def_id = tcx.hir.local_def_id(item_id); + debug!("id={} variances={:?}", id, variances); - map.insert(item_def_id, Rc::new(item_variances)); - } + // Functions can have unused type parameters: make those invariant. + if let ty::TyFnDef(..) = tcx.type_of(def_id).sty { + for variance in &mut variances { + if *variance == ty::Bivariant { + *variance = ty::Invariant; + } + } + } - map + (def_id, Rc::new(variances)) + }).collect() } fn evaluate(&self, term: VarianceTermPtr<'a>) -> ty::Variance { diff --git a/src/librustc_typeck/variance/terms.rs b/src/librustc_typeck/variance/terms.rs index ad787c57e76..38457146a97 100644 --- a/src/librustc_typeck/variance/terms.rs +++ b/src/librustc_typeck/variance/terms.rs @@ -22,7 +22,6 @@ use arena::TypedArena; use rustc::ty::{self, TyCtxt}; use std::fmt; -use std::rc::Rc; use syntax::ast; use rustc::hir; use rustc::hir::itemlikevisit::ItemLikeVisitor; @@ -63,31 +62,17 @@ pub struct TermsContext<'a, 'tcx: 'a> { pub tcx: TyCtxt<'a, 'tcx, 'tcx>, pub arena: &'a TypedArena<VarianceTerm<'a>>, - pub empty_variances: Rc<Vec<ty::Variance>>, - // For marker types, UnsafeCell, and other lang items where // variance is hardcoded, records the item-id and the hardcoded // variance. pub lang_items: Vec<(ast::NodeId, Vec<ty::Variance>)>, - // Maps from the node id of a type/generic parameter to the - // corresponding inferred index. - pub inferred_map: NodeMap<InferredIndex>, - - // Maps from an InferredIndex to the info for that variable. - pub inferred_infos: Vec<InferredInfo<'a>>, -} - -pub struct InferredInfo<'a> { - pub item_id: ast::NodeId, - pub index: usize, - pub param_id: ast::NodeId, - pub term: VarianceTermPtr<'a>, + // Maps from the node id of an item to the first inferred index + // used for its type & region parameters. + pub inferred_starts: NodeMap<InferredIndex>, - // Initial value to use for this parameter when inferring - // variance. For most parameters, this is Bivariant. But for lang - // items and input type parameters on traits, it is different. - pub initial_variance: ty::Variance, + // Maps from an InferredIndex to the term for that variable. + pub inferred_terms: Vec<VarianceTermPtr<'a>>, } pub fn determine_parameters_to_be_inferred<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, @@ -96,14 +81,10 @@ pub fn determine_parameters_to_be_inferred<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx> let mut terms_cx = TermsContext { tcx: tcx, arena: arena, - inferred_map: NodeMap(), - inferred_infos: Vec::new(), + inferred_starts: NodeMap(), + inferred_terms: vec![], lang_items: lang_items(tcx), - - // cache and share the variance struct used for items with - // no type/region parameters - empty_variances: Rc::new(vec![]), }; // See README.md for a discussion on dep-graph management. @@ -135,67 +116,28 @@ fn lang_items(tcx: TyCtxt) -> Vec<(ast::NodeId, Vec<ty::Variance>)> { } impl<'a, 'tcx> TermsContext<'a, 'tcx> { - fn add_inferreds_for_item(&mut self, - item_id: ast::NodeId, - generics: &hir::Generics) { - //! Add "inferreds" for the generic parameters declared on this - //! item. This has a lot of annoying parameters because we are - //! trying to drive this from the AST, rather than the - //! ty::Generics, so that we can get span info -- but this - //! means we must accommodate syntactic distinctions. - //! + fn add_inferreds_for_item(&mut self, id: ast::NodeId) { + let tcx = self.tcx; + let def_id = tcx.hir.local_def_id(id); + let count = tcx.generics_of(def_id).count(); - // NB: In the code below for writing the results back into the - // `CrateVariancesMap`, we rely on the fact that all inferreds - // for a particular item are assigned continuous indices. - - for (p, i) in generics.lifetimes.iter().zip(0..) { - let id = p.lifetime.id; - self.add_inferred(item_id, i, id); - } - - for (p, i) in generics.ty_params.iter().zip(generics.lifetimes.len()..) { - self.add_inferred(item_id, i, p.id); + if count == 0 { + return; } - } - fn add_inferred(&mut self, item_id: ast::NodeId, index: usize, param_id: ast::NodeId) { - let inf_index = InferredIndex(self.inferred_infos.len()); - let term = self.arena.alloc(InferredTerm(inf_index)); - let initial_variance = self.pick_initial_variance(item_id, index); - self.inferred_infos.push(InferredInfo { - item_id: item_id, - index: index, - param_id: param_id, - term: term, - initial_variance: initial_variance, - }); - let newly_added = self.inferred_map.insert(param_id, inf_index).is_none(); + // Record the start of this item's inferreds. + let start = self.inferred_terms.len(); + let newly_added = self.inferred_starts.insert(id, InferredIndex(start)).is_none(); assert!(newly_added); - debug!("add_inferred(item_path={}, \ - item_id={}, \ - index={}, \ - param_id={}, \ - inf_index={:?}, \ - initial_variance={:?})", - self.tcx.item_path_str(self.tcx.hir.local_def_id(item_id)), - item_id, - index, - param_id, - inf_index, - initial_variance); - } - - fn pick_initial_variance(&self, item_id: ast::NodeId, index: usize) -> ty::Variance { - match self.lang_items.iter().find(|&&(n, _)| n == item_id) { - Some(&(_, ref variances)) => variances[index], - None => ty::Bivariant, - } - } + // NB: In the code below for writing the results back into the + // `CrateVariancesMap`, we rely on the fact that all inferreds + // for a particular item are assigned continuous indices. - pub fn num_inferred(&self) -> usize { - self.inferred_infos.len() + let arena = self.arena; + self.inferred_terms.extend((start..start+count).map(|i| { + &*arena.alloc(InferredTerm(InferredIndex(i))) + })); } } @@ -205,30 +147,50 @@ impl<'a, 'tcx, 'v> ItemLikeVisitor<'v> for TermsContext<'a, 'tcx> { self.tcx.hir.node_to_string(item.id)); match item.node { - hir::ItemEnum(_, ref generics) | - hir::ItemStruct(_, ref generics) | - hir::ItemUnion(_, ref generics) => { - self.add_inferreds_for_item(item.id, generics); + hir::ItemStruct(ref struct_def, _) | + hir::ItemUnion(ref struct_def, _) => { + self.add_inferreds_for_item(item.id); + + if let hir::VariantData::Tuple(..) = *struct_def { + self.add_inferreds_for_item(struct_def.id()); + } + } + + hir::ItemEnum(ref enum_def, _) => { + self.add_inferreds_for_item(item.id); + + for variant in &enum_def.variants { + if let hir::VariantData::Tuple(..) = variant.node.data { + self.add_inferreds_for_item(variant.node.data.id()); + } + } + } + + hir::ItemFn(..) => { + self.add_inferreds_for_item(item.id); } - hir::ItemTrait(..) | - hir::ItemExternCrate(_) | - hir::ItemUse(..) | - hir::ItemDefaultImpl(..) | - hir::ItemImpl(..) | - hir::ItemStatic(..) | - hir::ItemConst(..) | - hir::ItemFn(..) | - hir::ItemMod(..) | - hir::ItemForeignMod(..) | - hir::ItemGlobalAsm(..) | - hir::ItemTy(..) => {} + hir::ItemForeignMod(ref foreign_mod) => { + for foreign_item in &foreign_mod.items { + if let hir::ForeignItemFn(..) = foreign_item.node { + self.add_inferreds_for_item(foreign_item.id); + } + } + } + + _ => {} } } - fn visit_trait_item(&mut self, _trait_item: &hir::TraitItem) { + fn visit_trait_item(&mut self, trait_item: &hir::TraitItem) { + if let hir::TraitItemKind::Method(..) = trait_item.node { + self.add_inferreds_for_item(trait_item.id); + } } - fn visit_impl_item(&mut self, _impl_item: &hir::ImplItem) { + fn visit_impl_item(&mut self, impl_item: &hir::ImplItem) { + if let hir::ImplItemKind::Method(..) = impl_item.node { + self.add_inferreds_for_item(impl_item.id); + } } } diff --git a/src/test/compile-fail/variance-region-bounds.rs b/src/test/compile-fail/variance-region-bounds.rs deleted file mode 100644 index 41d204a541b..00000000000 --- a/src/test/compile-fail/variance-region-bounds.rs +++ /dev/null @@ -1,25 +0,0 @@ -// Copyright 2014 The Rust Project Developers. See the COPYRIGHT -// file at the top-level directory of this distribution and at -// http://rust-lang.org/COPYRIGHT. -// -// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or -// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license -// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your -// option. This file may not be copied, modified, or distributed -// except according to those terms. - -// Check that `T:'a` is contravariant in T. - -#![feature(rustc_attrs)] - -#[rustc_variance] -trait Foo: 'static { //~ ERROR [o] -} - -#[rustc_variance] -trait Bar<T> { //~ ERROR [o, o] - fn do_it(&self) - where T: 'static; -} - -fn main() { } diff --git a/src/test/compile-fail/variance-trait-bounds.rs b/src/test/compile-fail/variance-trait-bounds.rs index 58fb785c48c..9b88e38e085 100644 --- a/src/test/compile-fail/variance-trait-bounds.rs +++ b/src/test/compile-fail/variance-trait-bounds.rs @@ -14,13 +14,11 @@ // Check that bounds on type parameters (other than `Self`) do not // influence variance. -#[rustc_variance] -trait Getter<T> { //~ ERROR [o, o] +trait Getter<T> { fn get(&self) -> T; } -#[rustc_variance] -trait Setter<T> { //~ ERROR [o, o] +trait Setter<T> { fn get(&self, T); } @@ -35,20 +33,6 @@ enum TestEnum<U,T:Setter<U>> { //~ ERROR [*, +] } #[rustc_variance] -trait TestTrait<U,T:Setter<U>> { //~ ERROR [o, o, o] - fn getter(&self, u: U) -> T; -} - -#[rustc_variance] -trait TestTrait2<U> : Getter<U> { //~ ERROR [o, o] -} - -#[rustc_variance] -trait TestTrait3<U> { //~ ERROR [o, o] - fn getter<T:Getter<U>>(&self); -} - -#[rustc_variance] struct TestContraStruct<U,T:Setter<U>> { //~ ERROR [*, +] t: T } diff --git a/src/test/compile-fail/variance-types-bounds.rs b/src/test/compile-fail/variance-types-bounds.rs index 2df94cc907a..5075dd2ceed 100644 --- a/src/test/compile-fail/variance-types-bounds.rs +++ b/src/test/compile-fail/variance-types-bounds.rs @@ -36,38 +36,15 @@ struct TestIndirect2<A:'static, B:'static> { //~ ERROR [o, o] m: TestMut<B, A> } -#[rustc_variance] -trait Getter<A> { //~ ERROR [o, o] +trait Getter<A> { fn get(&self) -> A; } -#[rustc_variance] -trait Setter<A> { //~ ERROR [o, o] - fn set(&mut self, a: A); -} - -#[rustc_variance] -trait GetterSetter<A> { //~ ERROR [o, o] - fn get(&self) -> A; +trait Setter<A> { fn set(&mut self, a: A); } #[rustc_variance] -trait GetterInTypeBound<A> { //~ ERROR [o, o] - // Here, the use of `A` in the method bound *does* affect - // variance. Think of it as if the method requested a dictionary - // for `T:Getter<A>`. Since this dictionary is an input, it is - // contravariant, and the Getter is covariant w/r/t A, yielding an - // overall contravariant result. - fn do_it<T:Getter<A>>(&self); -} - -#[rustc_variance] -trait SetterInTypeBound<A> { //~ ERROR [o, o] - fn do_it<T:Setter<A>>(&self); -} - -#[rustc_variance] struct TestObject<A, R> { //~ ERROR [o, o] n: Box<Setter<A>+Send>, m: Box<Getter<R>+Send>, |