From 4824a199ca3c6c1c12c90f0146db540045220c9a Mon Sep 17 00:00:00 2001 From: Niko Matsakis Date: Mon, 24 Apr 2017 11:15:12 -0400 Subject: [PATCH] factor variances into a proper query There are now two queries: crate and item. The crate one computes the variance of all items in the crate; it is sort of an implementation detail, and not meant to be used. The item one reads from the crate one, synthesizing correct deps in lieu of the red-green algorithm. At the same time, remove the `variance_computed` flag, which was a horrible hack used to force invariance early on (e.g. when type-checking constants). This is only needed because of trait applications, and traits are always invariant anyway. Therefore, we now change to take advantage of the query system: - When asked to compute variances for a trait, just return a vector saying 'all invariant'. - Remove the corresponding "inferreds" from traits, and tweak the constraint generation code to understand that traits are always inferred. --- src/librustc/dep_graph/dep_node.rs | 6 + src/librustc/ty/context.rs | 4 - src/librustc/ty/maps.rs | 16 +- src/librustc/ty/mod.rs | 22 +++ src/librustc/ty/relate.rs | 10 +- .../transitive_relation.rs | 14 ++ src/librustc_typeck/lib.rs | 4 +- src/librustc_typeck/variance/README.md | 68 +++---- src/librustc_typeck/variance/constraints.rs | 167 +++++++++++------- src/librustc_typeck/variance/mod.rs | 63 ++++++- src/librustc_typeck/variance/solve.rs | 24 +-- src/librustc_typeck/variance/terms.rs | 39 +--- .../compile-fail/dep-graph-variance-alias.rs | 32 ++++ 13 files changed, 295 insertions(+), 174 deletions(-) create mode 100644 src/test/compile-fail/dep-graph-variance-alias.rs diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs index 66505d9a06b..b4920f909cb 100644 --- a/src/librustc/dep_graph/dep_node.rs +++ b/src/librustc/dep_graph/dep_node.rs @@ -81,6 +81,7 @@ pub enum DepNode { TransCrateItem(D), TransInlinedItem(D), TransWriteMetadata, + CrateVariances, // Nodes representing bits of computed IR in the tcx. Each shared // table in the tcx (or elsewhere) maps to one of these @@ -89,6 +90,8 @@ pub enum DepNode { // predicates for an item wind up in `ItemSignature`). AssociatedItems(D), ItemSignature(D), + ItemVarianceConstraints(D), + ItemVariances(D), IsForeignItem(D), TypeParamPredicates((D, D)), SizedConstraint(D), @@ -199,6 +202,7 @@ pub fn map_def(&self, mut op: OP) -> Option> MirKrate => Some(MirKrate), TypeckBodiesKrate => Some(TypeckBodiesKrate), Coherence => Some(Coherence), + CrateVariances => Some(CrateVariances), Resolve => Some(Resolve), Variance => Some(Variance), PrivacyAccessLevels(k) => Some(PrivacyAccessLevels(k)), @@ -230,6 +234,8 @@ pub fn map_def(&self, mut op: OP) -> Option> TransInlinedItem(ref d) => op(d).map(TransInlinedItem), AssociatedItems(ref d) => op(d).map(AssociatedItems), ItemSignature(ref d) => op(d).map(ItemSignature), + ItemVariances(ref d) => op(d).map(ItemVariances), + ItemVarianceConstraints(ref d) => op(d).map(ItemVarianceConstraints), IsForeignItem(ref d) => op(d).map(IsForeignItem), TypeParamPredicates((ref item, ref param)) => { Some(TypeParamPredicates((try_opt!(op(item)), try_opt!(op(param))))) diff --git a/src/librustc/ty/context.rs b/src/librustc/ty/context.rs index 0dd23eb7e70..13295e4030d 100644 --- a/src/librustc/ty/context.rs +++ b/src/librustc/ty/context.rs @@ -468,9 +468,6 @@ pub struct GlobalCtxt<'tcx> { pub lang_items: middle::lang_items::LanguageItems, - /// True if the variance has been computed yet; false otherwise. - pub variance_computed: Cell, - /// Set of used unsafe nodes (functions or blocks). Unsafe nodes not /// present in this set can be warned about. pub used_unsafe: RefCell, @@ -753,7 +750,6 @@ pub fn create_and_enter(s: &'tcx Session, dep_graph: dep_graph.clone(), types: common_types, named_region_map: named_region_map, - variance_computed: Cell::new(false), trait_map: resolutions.trait_map, export_map: resolutions.export_map, fulfilled_predicates: RefCell::new(fulfilled_predicates), diff --git a/src/librustc/ty/maps.rs b/src/librustc/ty/maps.rs index 385abbd039e..3a2a6147345 100644 --- a/src/librustc/ty/maps.rs +++ b/src/librustc/ty/maps.rs @@ -265,6 +265,12 @@ fn describe(_: TyCtxt, _: CrateNum) -> String { } } +impl<'tcx> QueryDescription for queries::crate_variances<'tcx> { + fn describe(_tcx: TyCtxt, _: CrateNum) -> String { + format!("computing the variances for items in this crate") + } +} + impl<'tcx> QueryDescription for queries::mir_shims<'tcx> { fn describe(tcx: TyCtxt, def: ty::InstanceDef<'tcx>) -> String { format!("generating MIR shim for `{}`", @@ -673,9 +679,13 @@ fn default() -> Self { /// True if this is a foreign item (i.e., linked via `extern { ... }`). [] is_foreign_item: IsForeignItem(DefId) -> bool, + /// Get a map with the variance of every item; use `item_variance` + /// instead. + [] crate_variances: crate_variances(CrateNum) -> Rc, + /// Maps from def-id of a type or region parameter to its /// (inferred) variance. - [pub] variances_of: ItemSignature(DefId) -> Rc>, + [pub] variances_of: ItemVariances(DefId) -> Rc>, /// Maps from an impl/trait def-id to a list of the def-ids of its items [] associated_item_def_ids: AssociatedItemDefIds(DefId) -> Rc>, @@ -810,3 +820,7 @@ fn const_eval_dep_node((def_id, _): (DefId, &Substs)) -> DepNode { fn mir_keys(_: CrateNum) -> DepNode { DepNode::MirKeys } + +fn crate_variances(_: CrateNum) -> DepNode { + DepNode::CrateVariances +} diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs index 8191b392de5..481098450ed 100644 --- a/src/librustc/ty/mod.rs +++ b/src/librustc/ty/mod.rs @@ -55,6 +55,7 @@ use rustc_data_structures::accumulate_vec::IntoIter as AccIntoIter; use rustc_data_structures::stable_hasher::{StableHasher, StableHasherResult, HashStable}; +use rustc_data_structures::transitive_relation::TransitiveRelation; use hir; use hir::itemlikevisit::ItemLikeVisitor; @@ -309,6 +310,27 @@ pub enum Variance { Bivariant, // T <: T -- e.g., unused type parameter } +/// The crate variances map is computed during typeck and contains the +/// variance of every item in the local crate. You should not use it +/// directly, because to do so will make your pass dependent on the +/// HIR of every item in the local crate. Instead, use +/// `tcx.item_variances()` to get the variance for a *particular* +/// item. +pub struct CrateVariancesMap { + /// This relation tracks the dependencies between the variance of + /// various items. In particular, if `a < b`, then the variance of + /// `a` depends on the sources of `b`. + pub dependencies: TransitiveRelation, + + /// For each item with generics, maps to a vector of the variance + /// of its generics. If an item has no generics, it will have no + /// entry. + pub variances: FxHashMap>>, + + /// An empty vector, useful for cloning. + pub empty_variance: Rc>, +} + #[derive(Clone, Copy, Debug, RustcDecodable, RustcEncodable)] pub struct MethodCallee<'tcx> { /// Impl method ID, for inherent methods, or trait method ID, otherwise. diff --git a/src/librustc/ty/relate.rs b/src/librustc/ty/relate.rs index ac434c01c6a..dfa11b9c71a 100644 --- a/src/librustc/ty/relate.rs +++ b/src/librustc/ty/relate.rs @@ -124,14 +124,8 @@ fn relate_item_substs<'a, 'gcx, 'tcx, R>(relation: &mut R, a_subst, b_subst); - let variances; - let opt_variances = if relation.tcx().variance_computed.get() { - variances = relation.tcx().variances_of(item_def_id); - Some(&*variances) - } else { - None - }; - relate_substs(relation, opt_variances, a_subst, b_subst) + let opt_variances = relation.tcx().variances_of(item_def_id); + relate_substs(relation, Some(&opt_variances), a_subst, b_subst) } pub fn relate_substs<'a, 'gcx, 'tcx, R>(relation: &mut R, diff --git a/src/librustc_data_structures/transitive_relation.rs b/src/librustc_data_structures/transitive_relation.rs index 0d166cc0b9e..46463944043 100644 --- a/src/librustc_data_structures/transitive_relation.rs +++ b/src/librustc_data_structures/transitive_relation.rs @@ -134,6 +134,20 @@ pub fn contains(&self, a: &T, b: &T) -> bool { } } + /// Returns a vector of all things less than `a`. + /// + /// Really this probably ought to be `impl Iterator`, but + /// I'm too lazy to make that work, and -- given the caching + /// strategy -- it'd be a touch tricky anyhow. + pub fn less_than(&self, a: &T) -> Vec<&T> { + match self.index(a) { + Some(a) => self.with_closure(|closure| { + closure.iter(a.0).map(|i| &self.elements[i]).collect() + }), + None => vec![], + } + } + /// Picks what I am referring to as the "postdominating" /// upper-bound for `a` and `b`. This is usually the least upper /// bound, but in cases where there is no single least upper diff --git a/src/librustc_typeck/lib.rs b/src/librustc_typeck/lib.rs index 94b4bfade94..efb7cacc582 100644 --- a/src/librustc_typeck/lib.rs +++ b/src/librustc_typeck/lib.rs @@ -293,6 +293,7 @@ pub fn provide(providers: &mut Providers) { collect::provide(providers); coherence::provide(providers); check::provide(providers); + variance::provide(providers); } pub fn check_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) @@ -307,9 +308,6 @@ pub fn check_crate<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) })?; - time(time_passes, "variance inference", || - variance::infer_variance(tcx)); - tcx.sess.track_errors(|| { time(time_passes, "impl wf inference", || impl_wf_check::impl_wf_check(tcx)); diff --git a/src/librustc_typeck/variance/README.md b/src/librustc_typeck/variance/README.md index ac785e4058b..9ec20c1a45c 100644 --- a/src/librustc_typeck/variance/README.md +++ b/src/librustc_typeck/variance/README.md @@ -97,51 +97,29 @@ types involved before considering variance. #### Dependency graph management -Because variance works in two phases, if we are not careful, we wind -up with a muddled mess of a dep-graph. Basically, when gathering up -the constraints, things are fairly well-structured, but then we do a -fixed-point iteration and write the results back where they -belong. You can't give this fixed-point iteration a single task -because it reads from (and writes to) the variance of all types in the -crate. In principle, we *could* switch the "current task" in a very -fine-grained way while propagating constraints in the fixed-point -iteration and everything would be automatically tracked, but that -would add some overhead and isn't really necessary anyway. - -Instead what we do is to add edges into the dependency graph as we -construct the constraint set: so, if computing the constraints for -node `X` requires loading the inference variables from node `Y`, then -we can add an edge `Y -> X`, since the variance we ultimately infer -for `Y` will affect the variance we ultimately infer for `X`. - -At this point, we've basically mirrored the inference graph in the -dependency graph. This means we can just completely ignore the -fixed-point iteration, since it is just shuffling values along this -graph. In other words, if we added the fine-grained switching of tasks -I described earlier, all it would show is that we repeatedly read the -values described by the constraints, but those edges were already -added when building the constraints in the first place. - -Here is how this is implemented (at least as of the time of this -writing). The associated `DepNode` for the variance map is (at least -presently) `Signature(DefId)`. This means that, in `constraints.rs`, -when we visit an item to load up its constraints, we set -`Signature(DefId)` as the current task (the "memoization" pattern -described in the `dep-graph` README). Then whenever we find an -embedded type or trait, we add a synthetic read of `Signature(DefId)`, -which covers the variances we will compute for all of its -parameters. This read is synthetic (i.e., we call -`variance_map.read()`) because, in fact, the final variance is not yet -computed -- the read *will* occur (repeatedly) during the fixed-point -iteration phase. - -In fact, we don't really *need* this synthetic read. That's because we -do wind up looking up the `TypeScheme` or `TraitDef` for all -references types/traits, and those reads add an edge from -`Signature(DefId)` (that is, they share the same dep node as -variance). However, I've kept the synthetic reads in place anyway, -just for future-proofing (in case we change the dep-nodes in the -future), and because it makes the intention a bit clearer I think. +Because variance is a whole-crate inference, its dependency graph +can become quite muddled if we are not careful. To resolve this, we refactor +into two queries: + +- `crate_variances` computes the variance for all items in the current crate. +- `item_variances` accesses the variance for an individual reading; it + works by requesting `crate_variances` and extracting the relevant data. + +If you limit yourself to reading `item_variances`, your code will only +depend then on the inference inferred for that particular item. + +Eventually, the goal is to rely on the red-green dependency management +algorithm. At the moment, however, we rely instead on a hack, where +`item_variances` ignores the dependencies of accessing +`crate_variances` and instead computes the *correct* dependencies +itself. To this end, when we build up the constraints in the system, +we also built up a transitive `dependencies` relation as part of the +crate map. A `(X, Y)` pair is added to the map each time we have a +constraint that the variance of some inferred for the item `X` depends +on the variance of some element of `Y`. This is to some extent a +mirroring of the inference graph in the dependency graph. This means +we can just completely ignore the fixed-point iteration, since it is +just shuffling values along this graph. ### Addendum: Variance on traits diff --git a/src/librustc_typeck/variance/constraints.rs b/src/librustc_typeck/variance/constraints.rs index a617551eeb1..e986a381cd9 100644 --- a/src/librustc_typeck/variance/constraints.rs +++ b/src/librustc_typeck/variance/constraints.rs @@ -15,6 +15,7 @@ use hir::def_id::DefId; use middle::resolve_lifetime as rl; +use rustc::dep_graph::{AssertDepGraphSafe, DepNode}; use rustc::ty::subst::Substs; use rustc::ty::{self, Ty, TyCtxt}; use rustc::hir::map as hir_map; @@ -22,12 +23,12 @@ use rustc::hir; use rustc::hir::itemlikevisit::ItemLikeVisitor; +use rustc_data_structures::transitive_relation::TransitiveRelation; + use super::terms::*; use super::terms::VarianceTerm::*; use super::xform::*; -use dep_graph::DepNode::ItemSignature as VarianceDepNode; - pub struct ConstraintContext<'a, 'tcx: 'a> { pub terms_cx: TermsContext<'a, 'tcx>, @@ -38,6 +39,11 @@ pub struct ConstraintContext<'a, 'tcx: 'a> { bivariant: VarianceTermPtr<'a>, pub constraints: Vec>, + + /// This relation tracks the dependencies between the variance of + /// various items. In particular, if `a < b`, then the variance of + /// `a` depends on the sources of `b`. + pub dependencies: TransitiveRelation, } /// Declares that the variable `decl_id` appears in a location with @@ -57,7 +63,6 @@ pub struct Constraint<'a> { /// /// then while we are visiting `Bar`, the `CurrentItem` would have /// the def-id and generics of `Foo`. -#[allow(dead_code)] // TODO -- `def_id` field not used yet pub struct CurrentItem<'a> { def_id: DefId, generics: &'a ty::Generics, @@ -77,10 +82,10 @@ pub fn add_constraints_from_crate<'a, 'tcx>(terms_cx: TermsContext<'a, 'tcx>) invariant: invariant, bivariant: bivariant, constraints: Vec::new(), + dependencies: TransitiveRelation::new(), }; - // See README.md for a discussion on dep-graph management. - tcx.visit_all_item_likes_in_krate(VarianceDepNode, &mut constraint_cx); + tcx.hir.krate().visit_all_item_likes(&mut constraint_cx); constraint_cx } @@ -90,13 +95,64 @@ fn visit_item(&mut self, item: &hir::Item) { let tcx = self.terms_cx.tcx; let def_id = tcx.hir.local_def_id(item.id); + // Encapsulate constructing the constraints into a task we can + // reference later. This can go away once the red-green + // algorithm is in place. + // + // See README.md for a detailed discussion + // on dep-graph management. + match item.node { + hir::ItemEnum(..) | + hir::ItemStruct(..) | + hir::ItemUnion(..) => { + tcx.dep_graph.with_task(DepNode::ItemVarianceConstraints(def_id), + AssertDepGraphSafe(self), + def_id, + visit_item_task); + } + _ => { + // Nothing to do here, skip the task. + } + } + + fn visit_item_task<'a, 'tcx>(ccx: AssertDepGraphSafe<&mut ConstraintContext<'a, 'tcx>>, + def_id: DefId) + { + ccx.0.build_constraints_for_item(def_id); + } + } + + 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)); match item.node { hir::ItemEnum(..) | hir::ItemStruct(..) | hir::ItemUnion(..) => { - let generics = tcx.generics_of(did); + let generics = tcx.generics_of(def_id); let current_item = &CurrentItem { def_id, generics }; // Not entirely obvious: constraints on structs/enums do not @@ -105,24 +161,14 @@ fn visit_item(&mut self, item: &hir::Item) { // // self.add_constraints_from_generics(generics); - for field in tcx.adt_def(did).all_fields() { + for field in tcx.adt_def(def_id).all_fields() { self.add_constraints_from_ty(current_item, - tcx.item_type(field.did), + tcx.type_of(field.did), self.covariant); } } - hir::ItemTrait(..) => { - let generics = tcx.generics_of(did); - let current_item = &CurrentItem { def_id, generics }; - let trait_ref = ty::TraitRef { - def_id: def_id, - substs: Substs::identity_for_item(tcx, def_id) - }; - self.add_constraints_from_trait_ref(current_item, - trait_ref, - self.invariant); - } + hir::ItemTrait(..) | hir::ItemExternCrate(_) | hir::ItemUse(..) | hir::ItemStatic(..) | @@ -133,38 +179,25 @@ fn visit_item(&mut self, item: &hir::Item) { hir::ItemGlobalAsm(..) | hir::ItemTy(..) | hir::ItemImpl(..) | - hir::ItemDefaultImpl(..) => {} + hir::ItemDefaultImpl(..) => { + span_bug!(item.span, "`build_constraints_for_item` invoked for non-type-def"); + } } } - 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 + /// 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 inferred_index(&self, param_id: ast::NodeId) -> InferredIndex { - match self.terms_cx.inferred_map.get(¶m_id) { - Some(&index) => index, - None => { - bug!("no inferred index entry for {}", - self.tcx().hir.node_to_string(param_id)); - } - } + 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 { @@ -245,8 +278,27 @@ fn declared_variance(&self, // Parameter on an item defined within current crate: // variance not yet inferred, so return a symbolic // variance. - let InferredIndex(index) = self.inferred_index(param_node_id); - self.terms_cx.inferred_infos[index].term + 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 + } } else { // Parameter on an item defined within another crate: // variance already inferred, just look it up. @@ -305,11 +357,6 @@ fn add_constraints_from_trait_ref(&mut self, let trait_generics = self.tcx().generics_of(trait_ref.def_id); - // This edge is actually implied by the call to - // `trait_def`, but I'm trying to be future-proof. See - // README.md for a discussion on dep-graph management. - self.tcx().dep_graph.read(VarianceDepNode(trait_ref.def_id)); - self.add_constraints_from_substs(current, trait_ref.def_id, &trait_generics.types, @@ -362,12 +409,7 @@ fn add_constraints_from_ty(&mut self, } ty::TyAdt(def, substs) => { - let adt_generics = self.tcx().generics_of(def.did); - - // This edge is actually implied by the call to - // `trait_def`, but I'm trying to be future-proof. See - // README.md for a discussion on dep-graph management. - self.tcx().dep_graph.read(VarianceDepNode(def.did)); + let adt_generics = self.read_generics(current, def.did); self.add_constraints_from_substs(current, def.did, @@ -381,11 +423,6 @@ fn add_constraints_from_ty(&mut self, let trait_ref = &data.trait_ref; let trait_generics = self.tcx().generics_of(trait_ref.def_id); - // This edge is actually implied by the call to - // `trait_def`, but I'm trying to be future-proof. See - // README.md for a discussion on dep-graph management. - self.tcx().dep_graph.read(VarianceDepNode(trait_ref.def_id)); - self.add_constraints_from_substs(current, trait_ref.def_id, &trait_generics.types, @@ -505,7 +542,7 @@ fn add_constraints_from_region(&mut self, 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.inferred_index(node_id); + let &index = self.opt_inferred_index(node_id).unwrap(); self.add_constraint(index, variance); } } diff --git a/src/librustc_typeck/variance/mod.rs b/src/librustc_typeck/variance/mod.rs index cd0ab1cbb95..99e23589dd7 100644 --- a/src/librustc_typeck/variance/mod.rs +++ b/src/librustc_typeck/variance/mod.rs @@ -12,7 +12,12 @@ //! parameters. See README.md for details. use arena; -use rustc::ty::TyCtxt; +use rustc::dep_graph::DepNode; +use rustc::hir; +use rustc::hir::def_id::{CrateNum, DefId, LOCAL_CRATE}; +use rustc::ty::{self, CrateVariancesMap, TyCtxt}; +use rustc::ty::maps::Providers; +use std::rc::Rc; /// Defines the `TermsContext` basically houses an arena where we can /// allocate terms. @@ -27,10 +32,60 @@ /// Code for transforming variances. mod xform; -pub fn infer_variance<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>) { +pub fn provide(providers: &mut Providers) { + *providers = Providers { + variances_of, + crate_variances, + ..*providers + }; +} + +fn crate_variances<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, crate_num: CrateNum) + -> Rc { + assert_eq!(crate_num, LOCAL_CRATE); let mut arena = arena::TypedArena::new(); let terms_cx = terms::determine_parameters_to_be_inferred(tcx, &mut arena); let constraints_cx = constraints::add_constraints_from_crate(terms_cx); - solve::solve_constraints(constraints_cx); - tcx.variance_computed.set(true); + Rc::new(solve::solve_constraints(constraints_cx)) +} + +fn variances_of<'a, 'tcx>(tcx: TyCtxt<'a, 'tcx, 'tcx>, item_def_id: DefId) + -> Rc> { + 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()]) + } + + hir::ItemEnum(..) | + hir::ItemStruct(..) | + hir::ItemUnion(..) => { + // 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)); + tcx.dep_graph.read(DepNode::ItemVarianceConstraints(item_def_id)); + for &dep_def_id in crate_map.dependencies.less_than(&item_def_id) { + if dep_def_id.is_local() { + tcx.dep_graph.read(DepNode::ItemVarianceConstraints(dep_def_id)); + } else { + tcx.dep_graph.read(DepNode::ItemVariances(dep_def_id)); + } + } + + crate_map.variances.get(&item_def_id) + .unwrap_or(&crate_map.empty_variance) + .clone() + } + + _ => { + // Variance not relevant. + span_bug!(item.span, "asked to compute variance for wrong kind of item") + } + } } diff --git a/src/librustc_typeck/variance/solve.rs b/src/librustc_typeck/variance/solve.rs index 27116cbbb7a..5ba5005ccc2 100644 --- a/src/librustc_typeck/variance/solve.rs +++ b/src/librustc_typeck/variance/solve.rs @@ -15,7 +15,9 @@ //! optimal solution to the constraints. The final variance for each //! inferred is then written into the `variance_map` in the tcx. +use rustc::hir::def_id::DefId; use rustc::ty; +use rustc_data_structures::fx::FxHashMap; use std::rc::Rc; use super::constraints::*; @@ -31,8 +33,8 @@ struct SolveContext<'a, 'tcx: 'a> { solutions: Vec, } -pub fn solve_constraints(constraints_cx: ConstraintContext) { - let ConstraintContext { terms_cx, constraints, .. } = constraints_cx; +pub fn solve_constraints(constraints_cx: ConstraintContext) -> ty::CrateVariancesMap { + let ConstraintContext { terms_cx, dependencies, constraints, .. } = constraints_cx; let solutions = terms_cx.inferred_infos .iter() @@ -45,7 +47,10 @@ pub fn solve_constraints(constraints_cx: ConstraintContext) { solutions: solutions, }; solutions_cx.solve(); - solutions_cx.write(); + let variances = solutions_cx.create_map(); + let empty_variance = Rc::new(Vec::new()); + + ty::CrateVariancesMap { dependencies, variances, empty_variance } } impl<'a, 'tcx> SolveContext<'a, 'tcx> { @@ -83,7 +88,7 @@ fn solve(&mut self) { } } - fn write(&self) { + fn create_map(&self) -> FxHashMap>> { // 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 @@ -95,11 +100,7 @@ fn write(&self) { let tcx = self.terms_cx.tcx; - // Ignore the writes here because the relevant edges were - // already accounted for in `constraints.rs`. See the section - // on dependency graph management in README.md for more - // information. - let _ignore = tcx.dep_graph.in_ignore(); + let mut map = FxHashMap(); let solutions = &self.solutions; let inferred_infos = &self.terms_cx.inferred_infos; @@ -137,9 +138,10 @@ fn write(&self) { item_variances); } - tcx.maps.variances_of.borrow_mut() - .insert(item_def_id, Rc::new(item_variances)); + map.insert(item_def_id, Rc::new(item_variances)); } + + map } 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 61ff154e458..3f4b15e35a4 100644 --- a/src/librustc_typeck/variance/terms.rs +++ b/src/librustc_typeck/variance/terms.rs @@ -139,7 +139,6 @@ fn lang_items(tcx: TyCtxt) -> Vec<(ast::NodeId, Vec)> { impl<'a, 'tcx> TermsContext<'a, 'tcx> { fn add_inferreds_for_item(&mut self, item_id: ast::NodeId, - has_self: bool, generics: &hir::Generics) { //! Add "inferreds" for the generic parameters declared on this //! item. This has a lot of annoying parameters because we are @@ -149,38 +148,17 @@ fn add_inferreds_for_item(&mut self, //! // NB: In the code below for writing the results back into the - // tcx, we rely on the fact that all inferreds for a particular - // item are assigned continuous indices. + // `CrateVariancesMap`, we rely on the fact that all inferreds + // for a particular item are assigned continuous indices. - let inferreds_on_entry = self.num_inferred(); - - if has_self { - self.add_inferred(item_id, 0, item_id); - } - - for (i, p) in generics.lifetimes.iter().enumerate() { + for (p, i) in generics.lifetimes.iter().zip(0..) { let id = p.lifetime.id; - let i = has_self as usize + i; self.add_inferred(item_id, i, id); } - for (i, p) in generics.ty_params.iter().enumerate() { - let i = has_self as usize + generics.lifetimes.len() + i; + for (p, i) in generics.ty_params.iter().zip(generics.lifetimes.len()..) { self.add_inferred(item_id, i, p.id); } - - // If this item has no type or lifetime parameters, - // then there are no variances to infer, so just - // insert an empty entry into the variance map. - // Arguably we could just leave the map empty in this - // case but it seems cleaner to be able to distinguish - // "invalid item id" from "item id with no - // parameters". - if self.num_inferred() == inferreds_on_entry { - let item_def_id = self.tcx.hir.local_def_id(item_id); - self.tcx.maps.variances_of.borrow_mut() - .insert(item_def_id, self.empty_variances.clone()); - } } fn add_inferred(&mut self, item_id: ast::NodeId, index: usize, param_id: ast::NodeId) { @@ -232,15 +210,10 @@ fn visit_item(&mut self, item: &hir::Item) { hir::ItemEnum(_, ref generics) | hir::ItemStruct(_, ref generics) | hir::ItemUnion(_, ref generics) => { - self.add_inferreds_for_item(item.id, false, generics); - } - hir::ItemTrait(_, ref generics, ..) => { - // Note: all inputs for traits are ultimately - // constrained to be invariant. See `visit_item` in - // the impl for `ConstraintContext` in `constraints.rs`. - self.add_inferreds_for_item(item.id, true, generics); + self.add_inferreds_for_item(item.id, generics); } + hir::ItemTrait(..) | hir::ItemExternCrate(_) | hir::ItemUse(..) | hir::ItemDefaultImpl(..) | diff --git a/src/test/compile-fail/dep-graph-variance-alias.rs b/src/test/compile-fail/dep-graph-variance-alias.rs new file mode 100644 index 00000000000..9b621a13fc4 --- /dev/null +++ b/src/test/compile-fail/dep-graph-variance-alias.rs @@ -0,0 +1,32 @@ +// Copyright 2016 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 or the MIT license +// , at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +// Test that changing what a `type` points to does not go unnoticed +// by the variance analysis. + +// compile-flags: -Z query-dep-graph + +#![feature(rustc_attrs)] +#![allow(dead_code)] +#![allow(unused_variables)] + +fn main() { } + +struct Foo { + f: T +} + +#[rustc_if_this_changed] +type TypeAlias = Foo; + +#[rustc_then_this_would_need(ItemVariances)] //~ ERROR OK +struct Use { + x: TypeAlias +} -- 2.44.0