]>
Commit | Line | Data |
---|---|---|
9fa01778 | 1 | use crate::traits::specialization_graph; |
5e7ed085 | 2 | use crate::ty::fast_reject::{self, SimplifiedType, TreatParams}; |
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> { |
041b39d2 XL |
103 | pub fn for_each_impl<F: FnMut(DefId)>(self, def_id: DefId, mut f: F) { |
104 | let impls = self.trait_impls_of(def_id); | |
105 | ||
106 | for &impl_def_id in impls.blanket_impls.iter() { | |
9cc50fc6 SL |
107 | f(impl_def_id); |
108 | } | |
041b39d2 XL |
109 | |
110 | for v in impls.non_blanket_impls.values() { | |
111 | for &impl_def_id in v { | |
112 | f(impl_def_id); | |
113 | } | |
114 | } | |
9cc50fc6 SL |
115 | } |
116 | ||
117 | /// Iterate over every impl that could possibly match the | |
9fa01778 | 118 | /// self type `self_ty`. |
dfeec247 XL |
119 | pub fn for_each_relevant_impl<F: FnMut(DefId)>( |
120 | self, | |
121 | def_id: DefId, | |
122 | self_ty: Ty<'tcx>, | |
123 | mut f: F, | |
124 | ) { | |
29967ef6 XL |
125 | let _: Option<()> = self.find_map_relevant_impl(def_id, self_ty, |did| { |
126 | f(did); | |
127 | None | |
128 | }); | |
129 | } | |
130 | ||
5099ac24 FG |
131 | pub fn non_blanket_impls_for_ty( |
132 | self, | |
133 | def_id: DefId, | |
134 | self_ty: Ty<'tcx>, | |
135 | ) -> impl Iterator<Item = DefId> + 'tcx { | |
136 | let impls = self.trait_impls_of(def_id); | |
923072b8 | 137 | if let Some(simp) = fast_reject::simplify_type(self, self_ty, TreatParams::AsInfer) { |
5099ac24 FG |
138 | if let Some(impls) = impls.non_blanket_impls.get(&simp) { |
139 | return impls.iter().copied(); | |
140 | } | |
141 | } | |
142 | ||
143 | [].iter().copied() | |
144 | } | |
145 | ||
29967ef6 XL |
146 | /// Applies function to every impl that could possibly match the self type `self_ty` and returns |
147 | /// the first non-none value. | |
148 | pub fn find_map_relevant_impl<T, F: FnMut(DefId) -> Option<T>>( | |
149 | self, | |
150 | def_id: DefId, | |
151 | self_ty: Ty<'tcx>, | |
152 | mut f: F, | |
153 | ) -> Option<T> { | |
a2a8927a XL |
154 | // FIXME: This depends on the set of all impls for the trait. That is |
155 | // unfortunate wrt. incremental compilation. | |
156 | // | |
157 | // If we want to be faster, we could have separate queries for | |
158 | // blanket and non-blanket impls, and compare them separately. | |
041b39d2 XL |
159 | let impls = self.trait_impls_of(def_id); |
160 | ||
161 | for &impl_def_id in impls.blanket_impls.iter() { | |
29967ef6 XL |
162 | if let result @ Some(_) = f(impl_def_id) { |
163 | return result; | |
164 | } | |
041b39d2 XL |
165 | } |
166 | ||
923072b8 FG |
167 | // Note that we're using `TreatParams::AsPlaceholder` to query `non_blanket_impls` while using |
168 | // `TreatParams::AsInfer` while actually adding them. | |
041b39d2 | 169 | // |
a2a8927a XL |
170 | // This way, when searching for some impl for `T: Trait`, we do not look at any impls |
171 | // whose outer level is not a parameter or projection. Especially for things like | |
172 | // `T: Clone` this is incredibly useful as we would otherwise look at all the impls | |
173 | // of `Clone` for `Option<T>`, `Vec<T>`, `ConcreteType` and so on. | |
923072b8 | 174 | if let Some(simp) = fast_reject::simplify_type(self, self_ty, TreatParams::AsPlaceholder) { |
041b39d2 XL |
175 | if let Some(impls) = impls.non_blanket_impls.get(&simp) { |
176 | for &impl_def_id in impls { | |
29967ef6 XL |
177 | if let result @ Some(_) = f(impl_def_id) { |
178 | return result; | |
179 | } | |
041b39d2 XL |
180 | } |
181 | } | |
182 | } else { | |
0bf4aa26 | 183 | for &impl_def_id in impls.non_blanket_impls.values().flatten() { |
29967ef6 XL |
184 | if let result @ Some(_) = f(impl_def_id) { |
185 | return result; | |
186 | } | |
041b39d2 | 187 | } |
9cc50fc6 | 188 | } |
29967ef6 XL |
189 | |
190 | None | |
9cc50fc6 | 191 | } |
0bf4aa26 | 192 | |
1b1a35ee | 193 | /// Returns an iterator containing all impls |
ba9703b0 XL |
194 | pub fn all_impls(self, def_id: DefId) -> impl Iterator<Item = DefId> + 'tcx { |
195 | let TraitImpls { blanket_impls, non_blanket_impls } = self.trait_impls_of(def_id); | |
0bf4aa26 | 196 | |
5099ac24 | 197 | blanket_impls.iter().chain(non_blanket_impls.iter().flat_map(|(_, v)| v)).cloned() |
0bf4aa26 | 198 | } |
9cc50fc6 SL |
199 | } |
200 | ||
487cf647 | 201 | /// Query provider for `trait_impls_of`. |
f9f354fc | 202 | pub(super) fn trait_impls_of_provider(tcx: TyCtxt<'_>, trait_id: DefId) -> TraitImpls { |
b7449926 | 203 | let mut impls = TraitImpls::default(); |
7cac9316 | 204 | |
3dfed10e XL |
205 | // Traits defined in the current crate can't have impls in upstream |
206 | // crates, so we don't bother querying the cstore. | |
207 | if !trait_id.is_local() { | |
136023e0 | 208 | for &cnum in tcx.crates(()).iter() { |
3dfed10e XL |
209 | for &(impl_def_id, simplified_self_ty) in |
210 | tcx.implementations_of_trait((cnum, trait_id)).iter() | |
211 | { | |
212 | if let Some(simplified_self_ty) = simplified_self_ty { | |
213 | impls | |
214 | .non_blanket_impls | |
215 | .entry(simplified_self_ty) | |
216 | .or_default() | |
217 | .push(impl_def_id); | |
218 | } else { | |
219 | impls.blanket_impls.push(impl_def_id); | |
b7449926 XL |
220 | } |
221 | } | |
7cac9316 | 222 | } |
3dfed10e XL |
223 | } |
224 | ||
6a06907d XL |
225 | for &impl_def_id in tcx.hir().trait_impls(trait_id) { |
226 | let impl_def_id = impl_def_id.to_def_id(); | |
3dfed10e | 227 | |
9ffffee4 | 228 | let impl_self_ty = tcx.type_of(impl_def_id).subst_identity(); |
3dfed10e XL |
229 | if impl_self_ty.references_error() { |
230 | continue; | |
231 | } | |
7cac9316 | 232 | |
a2a8927a | 233 | if let Some(simplified_self_ty) = |
923072b8 | 234 | fast_reject::simplify_type(tcx, impl_self_ty, TreatParams::AsInfer) |
a2a8927a | 235 | { |
3dfed10e XL |
236 | impls.non_blanket_impls.entry(simplified_self_ty).or_default().push(impl_def_id); |
237 | } else { | |
238 | impls.blanket_impls.push(impl_def_id); | |
7cac9316 XL |
239 | } |
240 | } | |
241 | ||
f9f354fc | 242 | impls |
9cc50fc6 | 243 | } |
5e7ed085 | 244 | |
487cf647 | 245 | /// Query provider for `incoherent_impls`. |
5e7ed085 FG |
246 | pub(super) fn incoherent_impls_provider(tcx: TyCtxt<'_>, simp: SimplifiedType) -> &[DefId] { |
247 | let mut impls = Vec::new(); | |
248 | ||
249 | for cnum in iter::once(LOCAL_CRATE).chain(tcx.crates(()).iter().copied()) { | |
250 | for &impl_def_id in tcx.crate_incoherent_impls((cnum, simp)) { | |
251 | impls.push(impl_def_id) | |
252 | } | |
253 | } | |
254 | ||
255 | debug!(?impls); | |
256 | ||
257 | tcx.arena.alloc_slice(&impls) | |
258 | } |