]>
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 | ) { | |
142 | let _: Option<()> = | |
143 | self.find_map_relevant_impl(trait_def_id, self_ty, treat_projections, |did| { | |
144 | f(did); | |
145 | None | |
146 | }); | |
147 | } | |
148 | ||
149 | /// `trait_def_id` MUST BE the `DefId` of a trait. | |
5099ac24 FG |
150 | pub fn non_blanket_impls_for_ty( |
151 | self, | |
353b0b11 | 152 | trait_def_id: DefId, |
5099ac24 FG |
153 | self_ty: Ty<'tcx>, |
154 | ) -> impl Iterator<Item = DefId> + 'tcx { | |
353b0b11 FG |
155 | let impls = self.trait_impls_of(trait_def_id); |
156 | if let Some(simp) = fast_reject::simplify_type(self, self_ty, TreatParams::AsCandidateKey) { | |
5099ac24 FG |
157 | if let Some(impls) = impls.non_blanket_impls.get(&simp) { |
158 | return impls.iter().copied(); | |
159 | } | |
160 | } | |
161 | ||
162 | [].iter().copied() | |
163 | } | |
164 | ||
29967ef6 XL |
165 | /// Applies function to every impl that could possibly match the self type `self_ty` and returns |
166 | /// the first non-none value. | |
353b0b11 FG |
167 | /// |
168 | /// `trait_def_id` MUST BE the `DefId` of a trait. | |
169 | pub fn find_map_relevant_impl<T>( | |
29967ef6 | 170 | self, |
353b0b11 | 171 | trait_def_id: DefId, |
29967ef6 | 172 | self_ty: Ty<'tcx>, |
353b0b11 FG |
173 | treat_projections: TreatProjections, |
174 | mut f: impl FnMut(DefId) -> Option<T>, | |
29967ef6 | 175 | ) -> Option<T> { |
a2a8927a XL |
176 | // FIXME: This depends on the set of all impls for the trait. That is |
177 | // unfortunate wrt. incremental compilation. | |
178 | // | |
179 | // If we want to be faster, we could have separate queries for | |
180 | // blanket and non-blanket impls, and compare them separately. | |
353b0b11 | 181 | let impls = self.trait_impls_of(trait_def_id); |
041b39d2 XL |
182 | |
183 | for &impl_def_id in impls.blanket_impls.iter() { | |
29967ef6 XL |
184 | if let result @ Some(_) = f(impl_def_id) { |
185 | return result; | |
186 | } | |
041b39d2 XL |
187 | } |
188 | ||
353b0b11 FG |
189 | // Note that we're using `TreatParams::ForLookup` to query `non_blanket_impls` while using |
190 | // `TreatParams::AsCandidateKey` while actually adding them. | |
191 | let treat_params = match treat_projections { | |
192 | TreatProjections::NextSolverLookup => TreatParams::NextSolverLookup, | |
193 | TreatProjections::ForLookup => TreatParams::ForLookup, | |
194 | }; | |
a2a8927a XL |
195 | // This way, when searching for some impl for `T: Trait`, we do not look at any impls |
196 | // whose outer level is not a parameter or projection. Especially for things like | |
197 | // `T: Clone` this is incredibly useful as we would otherwise look at all the impls | |
198 | // of `Clone` for `Option<T>`, `Vec<T>`, `ConcreteType` and so on. | |
353b0b11 | 199 | if let Some(simp) = fast_reject::simplify_type(self, self_ty, treat_params) { |
041b39d2 XL |
200 | if let Some(impls) = impls.non_blanket_impls.get(&simp) { |
201 | for &impl_def_id in impls { | |
29967ef6 XL |
202 | if let result @ Some(_) = f(impl_def_id) { |
203 | return result; | |
204 | } | |
041b39d2 XL |
205 | } |
206 | } | |
207 | } else { | |
0bf4aa26 | 208 | for &impl_def_id in impls.non_blanket_impls.values().flatten() { |
29967ef6 XL |
209 | if let result @ Some(_) = f(impl_def_id) { |
210 | return result; | |
211 | } | |
041b39d2 | 212 | } |
9cc50fc6 | 213 | } |
29967ef6 XL |
214 | |
215 | None | |
9cc50fc6 | 216 | } |
0bf4aa26 | 217 | |
353b0b11 FG |
218 | /// Returns an iterator containing all impls for `trait_def_id`. |
219 | /// | |
220 | /// `trait_def_id` MUST BE the `DefId` of a trait. | |
221 | pub fn all_impls(self, trait_def_id: DefId) -> impl Iterator<Item = DefId> + 'tcx { | |
222 | let TraitImpls { blanket_impls, non_blanket_impls } = self.trait_impls_of(trait_def_id); | |
0bf4aa26 | 223 | |
5099ac24 | 224 | blanket_impls.iter().chain(non_blanket_impls.iter().flat_map(|(_, v)| v)).cloned() |
0bf4aa26 | 225 | } |
9cc50fc6 SL |
226 | } |
227 | ||
487cf647 | 228 | /// Query provider for `trait_impls_of`. |
f9f354fc | 229 | pub(super) fn trait_impls_of_provider(tcx: TyCtxt<'_>, trait_id: DefId) -> TraitImpls { |
b7449926 | 230 | let mut impls = TraitImpls::default(); |
7cac9316 | 231 | |
3dfed10e XL |
232 | // Traits defined in the current crate can't have impls in upstream |
233 | // crates, so we don't bother querying the cstore. | |
234 | if !trait_id.is_local() { | |
136023e0 | 235 | for &cnum in tcx.crates(()).iter() { |
3dfed10e XL |
236 | for &(impl_def_id, simplified_self_ty) in |
237 | tcx.implementations_of_trait((cnum, trait_id)).iter() | |
238 | { | |
239 | if let Some(simplified_self_ty) = simplified_self_ty { | |
240 | impls | |
241 | .non_blanket_impls | |
242 | .entry(simplified_self_ty) | |
243 | .or_default() | |
244 | .push(impl_def_id); | |
245 | } else { | |
246 | impls.blanket_impls.push(impl_def_id); | |
b7449926 XL |
247 | } |
248 | } | |
7cac9316 | 249 | } |
3dfed10e XL |
250 | } |
251 | ||
6a06907d XL |
252 | for &impl_def_id in tcx.hir().trait_impls(trait_id) { |
253 | let impl_def_id = impl_def_id.to_def_id(); | |
3dfed10e | 254 | |
9ffffee4 | 255 | let impl_self_ty = tcx.type_of(impl_def_id).subst_identity(); |
3dfed10e XL |
256 | if impl_self_ty.references_error() { |
257 | continue; | |
258 | } | |
7cac9316 | 259 | |
a2a8927a | 260 | if let Some(simplified_self_ty) = |
353b0b11 | 261 | fast_reject::simplify_type(tcx, impl_self_ty, TreatParams::AsCandidateKey) |
a2a8927a | 262 | { |
3dfed10e XL |
263 | impls.non_blanket_impls.entry(simplified_self_ty).or_default().push(impl_def_id); |
264 | } else { | |
265 | impls.blanket_impls.push(impl_def_id); | |
7cac9316 XL |
266 | } |
267 | } | |
268 | ||
f9f354fc | 269 | impls |
9cc50fc6 | 270 | } |
5e7ed085 | 271 | |
487cf647 | 272 | /// Query provider for `incoherent_impls`. |
5e7ed085 FG |
273 | pub(super) fn incoherent_impls_provider(tcx: TyCtxt<'_>, simp: SimplifiedType) -> &[DefId] { |
274 | let mut impls = Vec::new(); | |
275 | ||
276 | for cnum in iter::once(LOCAL_CRATE).chain(tcx.crates(()).iter().copied()) { | |
277 | for &impl_def_id in tcx.crate_incoherent_impls((cnum, simp)) { | |
278 | impls.push(impl_def_id) | |
279 | } | |
280 | } | |
281 | ||
282 | debug!(?impls); | |
283 | ||
284 | tcx.arena.alloc_slice(&impls) | |
285 | } |