projects/linux·blob master · refs

265 lines · 8.5 KiB

1// SPDX-License-Identifier: Apache-2.0 OR MIT
2
3use proc_macro2::{
4 Span,
5 TokenStream, //
6};
7use quote::{
8 format_ident,
9 quote, //
10};
11use syn::{
12 parse::{
13 Parse,
14 ParseStream, //
15 },
16 visit::Visit,
17 visit_mut::VisitMut,
18 Lifetime,
19 Result,
20 Token,
21 Type, //
22};
23
24pub(crate) enum HigherRankedType {
25 Explicit {
26 _for_token: Token![for],
27 _lt_token: Token![<],
28 lifetime: Lifetime,
29 _gt_token: Token![>],
30 ty: Type,
31 },
32 Implicit {
33 ty: Type,
34 },
35}
36
37impl Parse for HigherRankedType {
38 fn parse(input: ParseStream<'_>) -> Result<Self> {
39 if input.peek(Token![for]) {
40 Ok(Self::Explicit {
41 _for_token: input.parse()?,
42 _lt_token: input.parse()?,
43 lifetime: input.parse()?,
44 _gt_token: input.parse()?,
45 ty: input.parse()?,
46 })
47 } else {
48 Ok(Self::Implicit { ty: input.parse()? })
49 }
50 }
51}
52
53trait TypeExt {
54 fn expand_elided_lifetime(&self, explicit_lt: &Lifetime) -> Type;
55 fn replace_lifetime(&self, src: &Lifetime, dst: &Lifetime) -> Type;
56 fn has_lifetime(&self, lt: &Lifetime) -> bool;
57}
58
59impl TypeExt for Type {
60 fn expand_elided_lifetime(&self, explicit_lt: &Lifetime) -> Type {
61 struct ElidedLifetimeExpander<'a>(&'a Lifetime);
62
63 impl VisitMut for ElidedLifetimeExpander<'_> {
64 fn visit_lifetime_mut(&mut self, lifetime: &mut Lifetime) {
65 // Expand explicit `'_`
66 if lifetime.ident == "_" {
67 *lifetime = self.0.clone();
68 }
69 }
70
71 fn visit_type_reference_mut(&mut self, reference: &mut syn::TypeReference) {
72 syn::visit_mut::visit_type_reference_mut(self, reference);
73
74 if reference.lifetime.is_none() {
75 reference.lifetime = Some(self.0.clone());
76 }
77 }
78 }
79
80 let mut ret = self.clone();
81 ElidedLifetimeExpander(explicit_lt).visit_type_mut(&mut ret);
82 ret
83 }
84
85 fn replace_lifetime(&self, src: &Lifetime, dst: &Lifetime) -> Type {
86 struct LifetimeReplacer<'a>(&'a Lifetime, &'a Lifetime);
87
88 impl VisitMut for LifetimeReplacer<'_> {
89 fn visit_lifetime_mut(&mut self, lifetime: &mut Lifetime) {
90 if lifetime.ident == self.0.ident {
91 *lifetime = self.1.clone();
92 }
93 }
94 }
95
96 let mut ret = self.clone();
97 LifetimeReplacer(src, dst).visit_type_mut(&mut ret);
98 ret
99 }
100
101 fn has_lifetime(&self, lt: &Lifetime) -> bool {
102 struct HasLifetime<'a>(&'a Lifetime, bool);
103
104 impl Visit<'_> for HasLifetime<'_> {
105 fn visit_lifetime(&mut self, lifetime: &Lifetime) {
106 if lifetime.ident == self.0.ident {
107 self.1 = true;
108 }
109 }
110
111 // Macro invocations are opaque; conservatively assume they may
112 // reference the lifetime.
113 fn visit_macro(&mut self, _: &syn::Macro) {
114 self.1 = true;
115 }
116 }
117
118 let mut visitor = HasLifetime(lt, false);
119 visitor.visit_type(self);
120 visitor.1
121 }
122}
123
124struct Prover<'a>(&'a Lifetime, Vec<&'a Type>);
125
126impl<'a> Prover<'a> {
127 /// Prove that `ty` is covariant over `'lt`.
128 ///
129 /// This also needs to prove that it'll be wellformed for any instance of `'lt`.
130 /// It can be assumed that `ty` will be wellformed if `'lt` is substituted to `'static`.
131 fn prove(&mut self, ty: &'a Type) {
132 match ty {
133 Type::Paren(ty) => self.prove(&ty.elem),
134 Type::Group(ty) => self.prove(&ty.elem),
135
136 // No lifetime involved
137 Type::Never(_) => {}
138
139 // `[T; N]` and `[T]` is covariant over `T`.
140 Type::Array(ty) => self.prove(&ty.elem),
141 Type::Slice(ty) => self.prove(&ty.elem),
142
143 Type::Tuple(ty) => {
144 for elem in &ty.elems {
145 self.prove(elem);
146 }
147 }
148
149 // `*const T` is covariant over `T`
150 Type::Ptr(ty) if ty.const_token.is_some() => self.prove(&ty.elem),
151
152 // `&T` is covariant over `T` and lifetime.
153 //
154 // Note that if we encounter `&'other_lt T`, then we still need to make sure the type
155 // is wellformed if `T` involves `&'lt`, so we defer to the compiler.
156 //
157 // This is to block cases like `CovariantForLt!(for<'a> &'static &'a u32)`, as the
158 // presence of the type implies `'a: 'static` but this is unsound.
159 Type::Reference(ty)
160 if ty.mutability.is_none() && ty.lifetime.as_ref() == Some(self.0) =>
161 {
162 self.prove(&ty.elem)
163 }
164
165 // `&[mut] T` is covariant over lifetime.
166 // In case we have `&[mut] NoLifetime`, we don't need to do additional checks.
167 Type::Reference(ty) if !ty.elem.has_lifetime(self.0) => (),
168
169 // No mention of lifetime at all, no need to perform compiler check.
170 ty if !ty.has_lifetime(self.0) => (),
171
172 // Otherwise, we need to emit checks so that compiler can determine if the types are
173 // actually covariant.
174 ty => self.1.push(ty),
175 }
176 }
177}
178
179/// Shared implementation for both `ForLt!` and `CovariantForLt!`.
180///
181/// Both macros run the prover and emit `ProveWf` structs to check well-formedness for all lifetime
182/// instances (workaround for <https://github.com/rust-lang/rust/issues/152489>). `CovariantForLt!`
183/// additionally emits covariance proof functions and sets `N = 1`.
184fn for_lt_inner(input: HigherRankedType, prove_covariance: bool) -> TokenStream {
185 let (ty, lifetime) = match input {
186 HigherRankedType::Explicit { lifetime, ty, .. } => (ty, lifetime),
187 HigherRankedType::Implicit { ty } => {
188 // If there's no explicit `for<'a>` binder, inject a synthetic `'__elided` lifetime
189 // and expand elided sites.
190 let lifetime = Lifetime {
191 apostrophe: Span::mixed_site(),
192 ident: format_ident!("__elided", span = Span::mixed_site()),
193 };
194 (ty.expand_elided_lifetime(&lifetime), lifetime)
195 }
196 };
197
198 let mut prover = Prover(&lifetime, Vec::new());
199 prover.prove(&ty);
200
201 let mut proof = Vec::new();
202
203 // Emit proofs for every type that requires additional compiler help in proving covariance.
204 for (idx, required_proof) in prover.1.into_iter().enumerate() {
205 // Insert a proof that the type is well-formed.
206 //
207 // This is intended to workaround a Rust compiler soundness bug related to HRTB.
208 // https://github.com/rust-lang/rust/issues/152489
209 //
210 // This needs to be a struct instead of fn to avoid the implied WF bounds.
211 let wf_proof_name = format_ident!("ProveWf{idx}");
212 proof.push(quote!(
213 struct #wf_proof_name<#lifetime>(
214 ::core::marker::PhantomData<&#lifetime ()>, #required_proof
215 );
216 ));
217
218 // Insert a proof that the type is covariant.
219 if prove_covariance {
220 let cov_proof_name = format_ident!("prove_covariant_{idx}");
221 proof.push(quote!(
222 fn #cov_proof_name<'__short, '__long: '__short>(
223 long: #wf_proof_name<'__long>
224 ) -> #wf_proof_name<'__short> {
225 long
226 }
227 ));
228 }
229 }
230
231 // Make sure that the type is wellformed when substituting lifetime with `'static`.
232 //
233 // Currently the Rust compiler doesn't check this, see the above `ProveWf` documentation.
234 //
235 // We prefer to use this way of proving WF-ness as it can work when generics are involved.
236 let ty_static = ty.replace_lifetime(
237 &lifetime,
238 &Lifetime {
239 apostrophe: Span::mixed_site(),
240 ident: format_ident!("static"),
241 },
242 );
243
244 let n: usize = prove_covariance.into();
245
246 quote!(
247 ::kernel::types::for_lt::UnsafeForLtImpl::<
248 dyn for<#lifetime> ::kernel::types::for_lt::WithLt<#lifetime, Of = #ty>,
249 #ty_static,
250 {
251 #(#proof)*
252
253 #n
254 }
255 >
256 )
257}
258
259pub(crate) fn for_lt(input: HigherRankedType) -> TokenStream {
260 for_lt_inner(input, false)
261}
262
263pub(crate) fn covariant_for_lt(input: HigherRankedType) -> TokenStream {
264 for_lt_inner(input, true)
265}