]>
Commit | Line | Data |
---|---|---|
9fa01778 | 1 | use crate::traits::specialization_graph; |
353b0b11 | 2 | use crate::ty::fast_reject::{self, SimplifiedType, TreatParams, TreatProjections}; |
9ffffee4 | 3 | use crate::ty::visit::TypeVisitableExt; |
5099ac24 | 4 | use crate::ty::{Ident, Ty, TyCtxt}; |
5e7ed085 | 5 | use hir::def_id::LOCAL_CRATE; |
dfeec247 | 6 | use rustc_hir as hir; |
17df50a5 | 7 | use rustc_hir::def_id::DefId; |
5e7ed085 | 8 | use std::iter; |
041b39d2 | 9 | |
c295e0f8 | 10 | use rustc_data_structures::fx::FxIndexMap; |
5e7ed085 | 11 | use rustc_errors::ErrorGuaranteed; |
532ac7d7 | 12 | use rustc_macros::HashStable; |
8bb4bdeb | 13 | |
476ff2be | 14 | /// A trait's definition with type information. |
5e7ed085 | 15 | #[derive(HashStable, Encodable, Decodable)] |
476ff2be SL |
16 | pub struct TraitDef { |
17 | pub def_id: DefId, | |
9cc50fc6 | 18 | |
9cc50fc6 SL |
19 | pub unsafety: hir::Unsafety, |
20 | ||
21 | /// If `true`, then this trait had the `#[rustc_paren_sugar]` | |
22 | /// attribute, indicating that it should be used with `Foo()` | |
32a655c1 | 23 | /// sugar. This is a temporary thing -- eventually any trait will |
9cc50fc6 SL |
24 | /// be usable with the sugar (or without it). |
25 | pub paren_sugar: bool, | |
26 | ||
abe05a73 | 27 | pub has_auto_impl: bool, |
8bb4bdeb | 28 | |
0bf4aa26 XL |
29 | /// If `true`, then this trait has the `#[marker]` attribute, indicating |
30 | /// that all its associated items have defaults that cannot be overridden, | |
31 | /// and thus `impl`s of it are allowed to overlap. | |
32 | pub is_marker: bool, | |
33 | ||
9ffffee4 FG |
34 | /// If `true`, then this trait has to `#[rustc_coinductive]` attribute or |
35 | /// is an auto trait. This indicates that trait solver cycles involving an | |
36 | /// `X: ThisTrait` goal are accepted. | |
37 | /// | |
38 | /// In the future all traits should be coinductive, but we need a better | |
39 | /// formal understanding of what exactly that means and should probably | |
40 | /// also have already switched to the new trait solver. | |
41 | pub is_coinductive: bool, | |
42 | ||
cdc7bbd5 XL |
43 | /// If `true`, then this trait has the `#[rustc_skip_array_during_method_dispatch]` |
44 | /// attribute, indicating that editions before 2021 should not consider this trait | |
45 | /// during method dispatch if the receiver is an array. | |
46 | pub skip_array_during_method_dispatch: bool, | |
47 | ||
ba9703b0 XL |
48 | /// Used to determine whether the standard library is allowed to specialize |
49 | /// on this trait. | |
50 | pub specialization_kind: TraitSpecializationKind, | |
51 | ||
5099ac24 FG |
52 | /// List of functions from `#[rustc_must_implement_one_of]` attribute one of which |
53 | /// must be implemented. | |
54 | pub must_implement_one_of: Option<Box<[Ident]>>, | |
9cc50fc6 SL |
55 | } |
56 | ||
ba9703b0 XL |
57 | /// Whether this trait is treated specially by the standard library |
58 | /// specialization lint. | |
5e7ed085 | 59 | #[derive(HashStable, PartialEq, Clone, Copy, Encodable, Decodable)] |
ba9703b0 XL |
60 | pub enum TraitSpecializationKind { |
61 | /// The default. Specializing on this trait is not allowed. | |
62 | None, | |
63 | /// Specializing on this trait is allowed because it doesn't have any | |
64 | /// methods. For example `Sized` or `FusedIterator`. | |
65 | /// Applies to traits with the `rustc_unsafe_specialization_marker` | |
66 | /// attribute. | |
67 | Marker, | |
68 | /// Specializing on this trait is allowed because all of the impls of this | |
69 | /// trait are "always applicable". Always applicable means that if | |
70 | /// `X<'x>: T<'y>` for any lifetimes, then `for<'a, 'b> X<'a>: T<'b>`. | |
71 | /// Applies to traits with the `rustc_specialization_trait` attribute. | |
72 | AlwaysApplicable, | |
73 | } | |
74 | ||
c295e0f8 | 75 | #[derive(Default, Debug, HashStable)] |
7cac9316 | 76 | pub struct TraitImpls { |
041b39d2 | 77 | blanket_impls: Vec<DefId>, |
9fa01778 | 78 | /// Impls indexed by their simplified self type, for fast lookup. |
a2a8927a | 79 | non_blanket_impls: FxIndexMap<SimplifiedType, Vec<DefId>>, |
7cac9316 | 80 | } |
9cc50fc6 | 81 | |
cdc7bbd5 XL |
82 | impl TraitImpls { |
83 | pub fn blanket_impls(&self) -> &[DefId] { | |
84 | self.blanket_impls.as_slice() | |
85 | } | |
064997fb FG |
86 | |
87 | pub fn non_blanket_impls(&self) -> &FxIndexMap<SimplifiedType, Vec<DefId>> { | |
88 | &self.non_blanket_impls | |
89 | } | |
cdc7bbd5 XL |
90 | } |
91 | ||
dc9dc135 | 92 | impl<'tcx> TraitDef { |
dc9dc135 XL |
93 | pub fn ancestors( |
94 | &self, | |
95 | tcx: TyCtxt<'tcx>, | |
96 | of_impl: DefId, | |
5e7ed085 | 97 | ) -> Result<specialization_graph::Ancestors<'tcx>, ErrorGuaranteed> { |
7cac9316 | 98 | specialization_graph::ancestors(tcx, self.def_id, of_impl) |
8bb4bdeb | 99 | } |
041b39d2 | 100 | } |
8bb4bdeb | 101 | |
dc9dc135 | 102 | impl<'tcx> TyCtxt<'tcx> { |
353b0b11 FG |
103 | /// `trait_def_id` MUST BE the `DefId` of a trait. |
104 | pub fn for_each_impl<F: FnMut(DefId)>(self, trait_def_id: DefId, mut f: F) { | |
105 | let impls = self.trait_impls_of(trait_def_id); | |
041b39d2 XL |
106 | |
107 | for &impl_def_id in impls.blanket_impls.iter() { | |
9cc50fc6 SL |
108 | f(impl_def_id); |
109 | } | |
041b39d2 XL |
110 | |
111 | for v in impls.non_blanket_impls.values() { | |
112 | for &impl_def_id in v { | |
113 | f(impl_def_id); | |
114 | } | |
115 | } | |
9cc50fc6 SL |
116 | } |
117 | ||
353b0b11 FG |
118 | /// Iterate over every impl that could possibly match the self type `self_ty`. |
119 | /// | |
120 | /// `trait_def_id` MUST BE the `DefId` of a trait. | |
121 | pub fn for_each_relevant_impl( | |
dfeec247 | 122 | self, |
353b0b11 | 123 | trait_def_id: DefId, |
dfeec247 | 124 | self_ty: Ty<'tcx>, |
353b0b11 | 125 | f: impl FnMut(DefId), |
dfeec247 | 126 | ) { |
353b0b11 FG |
127 | self.for_each_relevant_impl_treating_projections( |
128 | trait_def_id, | |
129 | self_ty, | |
130 | TreatProjections::ForLookup, | |
131 | f, | |
132 | ) | |
29967ef6 XL |
133 | } |
134 | ||
353b0b11 FG |
135 | pub fn for_each_relevant_impl_treating_projections( |
136 | self, | |
137 | trait_def_id: DefId, | |
138 | self_ty: Ty<'tcx>, | |
139 | treat_projections: TreatProjections, | |
140 | mut f: impl FnMut(DefId), | |
141 | ) { | |
a2a8927a XL |
142 | // FIXME: This depends on the set of all impls for the trait. That is |
143 | // unfortunate wrt. incremental compilation. | |
144 | // | |
145 | // If we want to be faster, we could have separate queries for | |
146 | // blanket and non-blanket impls, and compare them separately. | |
353b0b11 | 147 | let impls = self.trait_impls_of(trait_def_id); |
041b39d2 XL |
148 | |
149 | for &impl_def_id in impls.blanket_impls.iter() { | |
49aad941 | 150 | f(impl_def_id); |
041b39d2 XL |
151 | } |
152 | ||
353b0b11 FG |
153 | // Note that we're using `TreatParams::ForLookup` to query `non_blanket_impls` while using |
154 | // `TreatParams::AsCandidateKey` while actually adding them. | |
155 | let treat_params = match treat_projections { | |
156 | TreatProjections::NextSolverLookup => TreatParams::NextSolverLookup, | |
157 | TreatProjections::ForLookup => TreatParams::ForLookup, | |
158 | }; | |
a2a8927a XL |
159 | // This way, when searching for some impl for `T: Trait`, we do not look at any impls |
160 | // whose outer level is not a parameter or projection. Especially for things like | |
161 | // `T: Clone` this is incredibly useful as we would otherwise look at all the impls | |
162 | // of `Clone` for `Option<T>`, `Vec<T>`, `ConcreteType` and so on. | |
353b0b11 | 163 | if let Some(simp) = fast_reject::simplify_type(self, self_ty, treat_params) { |
041b39d2 XL |
164 | if let Some(impls) = impls.non_blanket_impls.get(&simp) { |
165 | for &impl_def_id in impls { | |
49aad941 | 166 | f(impl_def_id); |
041b39d2 XL |
167 | } |
168 | } | |
169 | } else { | |
0bf4aa26 | 170 | for &impl_def_id in impls.non_blanket_impls.values().flatten() { |
49aad941 | 171 | f(impl_def_id); |
041b39d2 | 172 | } |
9cc50fc6 | 173 | } |
49aad941 | 174 | } |
29967ef6 | 175 | |
49aad941 FG |
176 | /// `trait_def_id` MUST BE the `DefId` of a trait. |
177 | pub fn non_blanket_impls_for_ty( | |
178 | self, | |
179 | trait_def_id: DefId, | |
180 | self_ty: Ty<'tcx>, | |
181 | ) -> impl Iterator<Item = DefId> + 'tcx { | |
182 | let impls = self.trait_impls_of(trait_def_id); | |
183 | if let Some(simp) = fast_reject::simplify_type(self, self_ty, TreatParams::AsCandidateKey) { | |
184 | if let Some(impls) = impls.non_blanket_impls.get(&simp) { | |
185 | return impls.iter().copied(); | |
186 | } | |
187 | } | |
188 | ||
189 | [].iter().copied() | |
9cc50fc6 | 190 | } |
0bf4aa26 | 191 | |
353b0b11 FG |
192 | /// Returns an iterator containing all impls for `trait_def_id`. |
193 | /// | |
194 | /// `trait_def_id` MUST BE the `DefId` of a trait. | |
195 | pub fn all_impls(self, trait_def_id: DefId) -> impl Iterator<Item = DefId> + 'tcx { | |
196 | let TraitImpls { blanket_impls, non_blanket_impls } = self.trait_impls_of(trait_def_id); | |
0bf4aa26 | 197 | |
5099ac24 | 198 | blanket_impls.iter().chain(non_blanket_impls.iter().flat_map(|(_, v)| v)).cloned() |
0bf4aa26 | 199 | } |
9cc50fc6 SL |
200 | } |
201 | ||
487cf647 | 202 | /// Query provider for `trait_impls_of`. |
f9f354fc | 203 | pub(super) fn trait_impls_of_provider(tcx: TyCtxt<'_>, trait_id: DefId) -> TraitImpls { |
b7449926 | 204 | let mut impls = TraitImpls::default(); |
7cac9316 | 205 | |
3dfed10e XL |
206 | // Traits defined in the current crate can't have impls in upstream |
207 | // crates, so we don't bother querying the cstore. | |
208 | if !trait_id.is_local() { | |
136023e0 | 209 | for &cnum in tcx.crates(()).iter() { |
3dfed10e XL |
210 | for &(impl_def_id, simplified_self_ty) in |
211 | tcx.implementations_of_trait((cnum, trait_id)).iter() | |
212 | { | |
213 | if let Some(simplified_self_ty) = simplified_self_ty { | |
214 | impls | |
215 | .non_blanket_impls | |
216 | .entry(simplified_self_ty) | |
217 | .or_default() | |
218 | .push(impl_def_id); | |
219 | } else { | |
220 | impls.blanket_impls.push(impl_def_id); | |
b7449926 XL |
221 | } |
222 | } | |
7cac9316 | 223 | } |
3dfed10e XL |
224 | } |
225 | ||
6a06907d XL |
226 | for &impl_def_id in tcx.hir().trait_impls(trait_id) { |
227 | let impl_def_id = impl_def_id.to_def_id(); | |
3dfed10e | 228 | |
9ffffee4 | 229 | let impl_self_ty = tcx.type_of(impl_def_id).subst_identity(); |
3dfed10e XL |
230 | if impl_self_ty.references_error() { |
231 | continue; | |
232 | } | |
7cac9316 | 233 | |
a2a8927a | 234 | if let Some(simplified_self_ty) = |
353b0b11 | 235 | fast_reject::simplify_type(tcx, impl_self_ty, TreatParams::AsCandidateKey) |
a2a8927a | 236 | { |
3dfed10e XL |
237 | impls.non_blanket_impls.entry(simplified_self_ty).or_default().push(impl_def_id); |
238 | } else { | |
239 | impls.blanket_impls.push(impl_def_id); | |
7cac9316 XL |
240 | } |
241 | } | |
242 | ||
f9f354fc | 243 | impls |
9cc50fc6 | 244 | } |
5e7ed085 | 245 | |
487cf647 | 246 | /// Query provider for `incoherent_impls`. |
5e7ed085 FG |
247 | pub(super) fn incoherent_impls_provider(tcx: TyCtxt<'_>, simp: SimplifiedType) -> &[DefId] { |
248 | let mut impls = Vec::new(); | |
249 | ||
250 | for cnum in iter::once(LOCAL_CRATE).chain(tcx.crates(()).iter().copied()) { | |
251 | for &impl_def_id in tcx.crate_incoherent_impls((cnum, simp)) { | |
252 | impls.push(impl_def_id) | |
253 | } | |
254 | } | |
255 | ||
256 | debug!(?impls); | |
257 | ||
258 | tcx.arena.alloc_slice(&impls) | |
259 | } |