1 use crate::ich
::{self, StableHashingContext}
;
2 use crate::traits
::specialization_graph
;
3 use crate::ty
::fast_reject
;
4 use crate::ty
::fold
::TypeFoldable
;
5 use crate::ty
::{Ty, TyCtxt}
;
7 use rustc_hir
::def_id
::{CrateNum, DefId}
;
8 use rustc_hir
::definitions
::DefPathHash
;
11 use rustc_data_structures
::fx
::FxHashMap
;
12 use rustc_data_structures
::stable_hasher
::{HashStable, StableHasher}
;
13 use rustc_errors
::ErrorReported
;
14 use rustc_macros
::HashStable
;
15 use std
::collections
::BTreeMap
;
17 /// A trait's definition with type information.
20 // We already have the def_path_hash below, no need to hash it twice
21 #[stable_hasher(ignore)]
24 pub unsafety
: hir
::Unsafety
,
26 /// If `true`, then this trait had the `#[rustc_paren_sugar]`
27 /// attribute, indicating that it should be used with `Foo()`
28 /// sugar. This is a temporary thing -- eventually any trait will
29 /// be usable with the sugar (or without it).
30 pub paren_sugar
: bool
,
32 pub has_auto_impl
: bool
,
34 /// If `true`, then this trait has the `#[marker]` attribute, indicating
35 /// that all its associated items have defaults that cannot be overridden,
36 /// and thus `impl`s of it are allowed to overlap.
39 /// Used to determine whether the standard library is allowed to specialize
41 pub specialization_kind
: TraitSpecializationKind
,
43 /// The ICH of this trait's DefPath, cached here so it doesn't have to be
44 /// recomputed all the time.
45 pub def_path_hash
: DefPathHash
,
48 /// Whether this trait is treated specially by the standard library
49 /// specialization lint.
50 #[derive(HashStable, PartialEq, Clone, Copy, RustcEncodable, RustcDecodable)]
51 pub enum TraitSpecializationKind
{
52 /// The default. Specializing on this trait is not allowed.
54 /// Specializing on this trait is allowed because it doesn't have any
55 /// methods. For example `Sized` or `FusedIterator`.
56 /// Applies to traits with the `rustc_unsafe_specialization_marker`
59 /// Specializing on this trait is allowed because all of the impls of this
60 /// trait are "always applicable". Always applicable means that if
61 /// `X<'x>: T<'y>` for any lifetimes, then `for<'a, 'b> X<'a>: T<'b>`.
62 /// Applies to traits with the `rustc_specialization_trait` attribute.
67 pub struct TraitImpls
{
68 blanket_impls
: Vec
<DefId
>,
69 /// Impls indexed by their simplified self type, for fast lookup.
70 non_blanket_impls
: FxHashMap
<fast_reject
::SimplifiedType
, Vec
<DefId
>>,
76 unsafety
: hir
::Unsafety
,
80 specialization_kind
: TraitSpecializationKind
,
81 def_path_hash
: DefPathHash
,
98 ) -> Result
<specialization_graph
::Ancestors
<'tcx
>, ErrorReported
> {
99 specialization_graph
::ancestors(tcx
, self.def_id
, of_impl
)
103 impl<'tcx
> TyCtxt
<'tcx
> {
104 pub fn for_each_impl
<F
: FnMut(DefId
)>(self, def_id
: DefId
, mut f
: F
) {
105 let impls
= self.trait_impls_of(def_id
);
107 for &impl_def_id
in impls
.blanket_impls
.iter() {
111 for v
in impls
.non_blanket_impls
.values() {
112 for &impl_def_id
in v
{
118 /// Iterate over every impl that could possibly match the
119 /// self type `self_ty`.
120 pub fn for_each_relevant_impl
<F
: FnMut(DefId
)>(
126 let impls
= self.trait_impls_of(def_id
);
128 for &impl_def_id
in impls
.blanket_impls
.iter() {
132 // simplify_type(.., false) basically replaces type parameters and
133 // projections with infer-variables. This is, of course, done on
134 // the impl trait-ref when it is instantiated, but not on the
135 // predicate trait-ref which is passed here.
137 // for example, if we match `S: Copy` against an impl like
138 // `impl<T:Copy> Copy for Option<T>`, we replace the type variable
139 // in `Option<T>` with an infer variable, to `Option<_>` (this
140 // doesn't actually change fast_reject output), but we don't
141 // replace `S` with anything - this impl of course can't be
142 // selected, and as there are hundreds of similar impls,
143 // considering them would significantly harm performance.
145 // This depends on the set of all impls for the trait. That is
146 // unfortunate. When we get red-green recompilation, we would like
147 // to have a way of knowing whether the set of relevant impls
148 // changed. The most naive
149 // way would be to compute the Vec of relevant impls and see whether
150 // it differs between compilations. That shouldn't be too slow by
151 // itself - we do quite a bit of work for each relevant impl anyway.
153 // If we want to be faster, we could have separate queries for
154 // blanket and non-blanket impls, and compare them separately.
156 // I think we'll cross that bridge when we get to it.
157 if let Some(simp
) = fast_reject
::simplify_type(self, self_ty
, true) {
158 if let Some(impls
) = impls
.non_blanket_impls
.get(&simp
) {
159 for &impl_def_id
in impls
{
164 for &impl_def_id
in impls
.non_blanket_impls
.values().flatten() {
170 /// Returns a vector containing all impls
171 pub fn all_impls(self, def_id
: DefId
) -> impl Iterator
<Item
= DefId
> + 'tcx
{
172 let TraitImpls { blanket_impls, non_blanket_impls }
= self.trait_impls_of(def_id
);
176 .chain(non_blanket_impls
.into_iter().map(|(_
, v
)| v
).flatten())
181 // Query provider for `all_local_trait_impls`.
182 pub(super) fn all_local_trait_impls
<'tcx
>(
185 ) -> &'tcx BTreeMap
<DefId
, Vec
<HirId
>> {
186 &tcx
.hir_crate(krate
).trait_impls
189 // Query provider for `trait_impls_of`.
190 pub(super) fn trait_impls_of_provider(tcx
: TyCtxt
<'_
>, trait_id
: DefId
) -> &TraitImpls
{
191 let mut impls
= TraitImpls
::default();
194 let mut add_impl
= |impl_def_id
: DefId
| {
195 let impl_self_ty
= tcx
.type_of(impl_def_id
);
196 if impl_def_id
.is_local() && impl_self_ty
.references_error() {
200 if let Some(simplified_self_ty
) = fast_reject
::simplify_type(tcx
, impl_self_ty
, false) {
201 impls
.non_blanket_impls
.entry(simplified_self_ty
).or_default().push(impl_def_id
);
203 impls
.blanket_impls
.push(impl_def_id
);
207 // Traits defined in the current crate can't have impls in upstream
208 // crates, so we don't bother querying the cstore.
209 if !trait_id
.is_local() {
210 for &cnum
in tcx
.crates().iter() {
211 for &def_id
in tcx
.implementations_of_trait((cnum
, trait_id
)).iter() {
217 for &hir_id
in tcx
.hir().trait_impls(trait_id
) {
218 add_impl(tcx
.hir().local_def_id(hir_id
));
222 tcx
.arena
.alloc(impls
)
225 impl<'a
> HashStable
<StableHashingContext
<'a
>> for TraitImpls
{
226 fn hash_stable(&self, hcx
: &mut StableHashingContext
<'a
>, hasher
: &mut StableHasher
) {
227 let TraitImpls { ref blanket_impls, ref non_blanket_impls }
= *self;
229 ich
::hash_stable_trait_impls(hcx
, hasher
, blanket_impls
, non_blanket_impls
);