1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
//! The recursive shape-matching kernel: match_ty compares a shape template
//! (syn::Type) against a leaf type position-by-position, binding differing
//! idents as slots and resolving variadic segments. Split out of shape.rs
//! to keep every source file under the 350-line cap.
use crate::codegen::shape::{Mapping, ShapeError, VarSeg};
use crate::preprocess::varseg::{is_varseg_type, varseg_prefix};
use quote::ToTokens;
/// A bare single-segment path with no generic args (`T` / `Vec`).
fn is_bare_ident(tp: &syn::TypePath) -> bool {
tp.qself.is_none()
&& tp.path.segments.len() == 1
&& matches!(tp.path.segments[0].arguments, syn::PathArguments::None)
}
/// The ident of a variadic-segment placeholder type (defensive: the caller
/// has already checked `is_varseg_type`; `None` keeps the no-panic promise
/// on any internal drift).
fn varseg_ident(tp: &syn::Type) -> Option<&syn::Ident> {
let syn::Type::Path(p) = tp else { return None };
(p.path.segments.len() == 1).then(|| &p.path.segments[0].ident)
}
/// The ident of a bare single-segment path expression (`N` in `[T; N]`);
/// `None` for any other expression (literals, arithmetic, `N + 1`, ...).
fn bare_path_ident(expr: &syn::Expr) -> Option<String> {
let syn::Expr::Path(ep) = expr else { return None };
if ep.qself.is_some()
|| ep.path.segments.len() != 1
|| !matches!(ep.path.segments[0].arguments, syn::PathArguments::None)
{
return None;
}
Some(ep.path.segments[0].ident.to_string())
}
/// Recursive position-by-position match (see module docs for the rules).
pub(crate) fn match_ty(
template: &syn::Type, leaf: &syn::Type, map: &mut Mapping, segs: &mut Vec<VarSeg>,
) -> Result<(), ShapeError> {
match template {
// Bare ident: `_` is a wildcard (matches any type, never binds a
// slot); an equal leaf ident → literal; anything else → slot bound
// to the whole leaf subtree (the "0-arity → T := leaf" rule).
// A variadic-segment placeholder is legal only as a tuple element —
// reaching the bare-ident arm means it sits elsewhere (rejected).
syn::Type::Path(tp) if is_bare_ident(tp) => {
let name = &tp.path.segments[0].ident;
if is_varseg_type(template) {
return Err(ShapeError::ShapeMismatch(
"a variadic segment (`ident@..`) is only supported as a tuple element \
inside an `impl{...}` template"
.into(),
));
}
if name == "_" {
return Ok(());
}
if let syn::Type::Path(lp) = leaf
&& is_bare_ident(lp)
&& lp.path.segments[0].ident == *name
{
return Ok(());
}
map.bind(&name.to_string(), leaf.to_token_stream())
}
// Composite path: structural compare + recurse into segments/args.
syn::Type::Path(tp) => {
let syn::Type::Path(lp) = leaf else {
return Err(ShapeError::ShapeMismatch(
"the template is a path but the target is not".into(),
));
};
if tp.qself.is_some() || lp.qself.is_some() {
return Err(ShapeError::ShapeMismatch(
"qualified paths (`<T as Trait>::...`) are not supported in templates".into(),
));
}
if tp.path.segments.len() != lp.path.segments.len() {
return Err(ShapeError::ShapeMismatch(format!(
"path segment count differs (template `{}` has {}, target has {})",
template.to_token_stream(),
tp.path.segments.len(),
lp.path.segments.len(),
)));
}
for (tseg, lseg) in tp.path.segments.iter().zip(lp.path.segments.iter()) {
// Segment ident: equal → literal; different → slot bound to
// the target segment's base ident.
if tseg.ident != lseg.ident {
map.bind(&tseg.ident.to_string(), lseg.ident.to_token_stream())?;
}
match (&tseg.arguments, &lseg.arguments) {
(syn::PathArguments::None, syn::PathArguments::None) => {}
(
syn::PathArguments::AngleBracketed(t),
syn::PathArguments::AngleBracketed(l),
) => {
if t.args.len() != l.args.len() {
return Err(ShapeError::ShapeMismatch(format!(
"generic arity differs (template `{}` has {} args, target has {})",
template.to_token_stream(),
t.args.len(),
l.args.len(),
)));
}
for (ta, la) in t.args.iter().zip(l.args.iter()) {
match (ta, la) {
(
syn::GenericArgument::Type(tt),
syn::GenericArgument::Type(lt),
) => match_ty(tt, lt, map, segs)?,
// Lifetime args: `'_` (anonymous) is a
// wildcard matching any lifetime (skip);
// named lifetimes compare verbatim (`'a` vs
// `'b` mismatches — cross-lifetime binding is
// out of scope).
(
syn::GenericArgument::Lifetime(tl),
syn::GenericArgument::Lifetime(ll),
) => {
if tl.ident != "_" && tl.ident != ll.ident {
return Err(ShapeError::ShapeMismatch(format!(
"generic argument differs (template `{}` vs target `{}`)",
ta.to_token_stream(),
la.to_token_stream(),
)));
}
}
_ => {
// Binding names, const args, lifetime-vs-
// type: verbatim compare (no slots
// inside; cross-class binding is out of
// scope).
if ta.to_token_stream().to_string()
!= la.to_token_stream().to_string()
{
return Err(ShapeError::ShapeMismatch(format!(
"generic argument differs (template `{}` vs target `{}`)",
ta.to_token_stream(),
la.to_token_stream(),
)));
}
}
}
}
}
(
syn::PathArguments::Parenthesized(t),
syn::PathArguments::Parenthesized(l),
) => {
// Fn-trait sugar (`Fn(A) -> B`): verbatim compare
// (syn 3 models the inputs as named args; slots
// inside fn-trait sugar are out of scope).
if t.to_token_stream().to_string() != l.to_token_stream().to_string() {
return Err(ShapeError::ShapeMismatch(
"parenthesized generic arguments differ".into(),
));
}
}
_ => {
return Err(ShapeError::ShapeMismatch(format!(
"generic argument shape differs at segment `{}`",
tseg.ident,
)));
}
}
}
Ok(())
}
// Structural containers: recurse into the element(s).
syn::Type::Reference(t) => {
let syn::Type::Reference(l) = leaf else {
return Err(ShapeError::ShapeMismatch(
"the template is a reference but the target is not".into(),
));
};
if t.mutability.is_some() != l.mutability.is_some() {
return Err(ShapeError::ShapeMismatch("reference mutability differs".into()));
}
match_ty(&t.elem, &l.elem, map, segs)
}
syn::Type::Tuple(t) => {
let syn::Type::Tuple(l) = leaf else {
return Err(ShapeError::ShapeMismatch(
"the template is a tuple but the target is not".into(),
));
};
// Variadic segments (`ident@..` placeholders): the remaining
// leaf positions (after the fixed template elements) split
// evenly across the segments. Each segment binds its name
// sequence (`prefix` + leaf start index..) to the corresponding
// leaf elements — name numbering aligns with the leaf position
// (user-confirmed: `(A, B@..)` → `B1, B2, ...`).
let seg_count = t.elems.iter().filter(|e| is_varseg_type(e)).count();
if seg_count > 0 {
let fixed = t.elems.len() - seg_count;
if l.elems.len() < fixed {
return Err(ShapeError::ShapeMismatch(format!(
"tuple arity differs (template has {} fixed elements, target has {})",
fixed,
l.elems.len(),
)));
}
let remaining = l.elems.len() - fixed;
if remaining % seg_count != 0 {
return Err(ShapeError::ShapeMismatch(format!(
"variadic segments cannot be split evenly: target tuple has {} \
elements after {} fixed, split across {} segments",
remaining, fixed, seg_count,
)));
}
let seg_len = remaining / seg_count;
let mut leaf_idx = 0;
for te in &t.elems {
if is_varseg_type(te) {
let Some(ident) = varseg_ident(te) else {
return Err(ShapeError::ShapeMismatch(
"malformed variadic segment placeholder".into(),
));
};
let Some(prefix) = varseg_prefix(ident) else {
return Err(ShapeError::ShapeMismatch(
"malformed variadic segment placeholder".into(),
));
};
if segs.iter().any(|s| s.prefix == prefix) {
return Err(ShapeError::ShapeMismatch(format!(
"duplicate variadic segment prefix `{}` (each \
`ident@..` in one template must be unique)",
prefix,
)));
}
segs.push(VarSeg { prefix: prefix.clone(), start: leaf_idx, len: seg_len });
for k in 0..seg_len {
let name = format!("{}{}", prefix, leaf_idx + k);
map.bind(&name, l.elems[leaf_idx + k].to_token_stream())?;
}
leaf_idx += seg_len;
} else {
match_ty(te, &l.elems[leaf_idx], map, segs)?;
leaf_idx += 1;
}
}
return Ok(());
}
if t.elems.len() != l.elems.len() {
return Err(ShapeError::ShapeMismatch(format!(
"tuple arity differs (template has {}, target has {})",
t.elems.len(),
l.elems.len(),
)));
}
for (te, le) in t.elems.iter().zip(l.elems.iter()) {
match_ty(te, le, map, segs)?;
}
Ok(())
}
syn::Type::Array(t) => {
let syn::Type::Array(l) = leaf else {
return Err(ShapeError::ShapeMismatch(
"the template is an array but the target is not".into(),
));
};
// Length: `_` is a wildcard (matches any length, never binds);
// a bare const-param name in the template (`[A; N]`) is a slot
// bound to the leaf's length expression (any literal / const
// generic); anything else compares verbatim (`[A; 3]` ↔
// `[u8; 3]`).
if matches!(t.len, syn::Expr::Infer(_)) {
// `_` wildcard
} else if let Some(name) = bare_path_ident(&t.len) {
if name != "_" {
map.bind(&name, l.len.to_token_stream())?;
}
} else if t.len.to_token_stream().to_string() != l.len.to_token_stream().to_string() {
return Err(ShapeError::ShapeMismatch("array length differs".into()));
}
match_ty(&t.elem, &l.elem, map, segs)
}
syn::Type::Slice(t) => {
let syn::Type::Slice(l) = leaf else {
return Err(ShapeError::ShapeMismatch(
"the template is a slice but the target is not".into(),
));
};
match_ty(&t.elem, &l.elem, map, segs)
}
syn::Type::Ptr(t) => {
let syn::Type::Ptr(l) = leaf else {
return Err(ShapeError::ShapeMismatch(
"the template is a pointer but the target is not".into(),
));
};
// syn 3 `PointerMutability` has no `PartialEq` — compare by arm.
let mut_eq = matches!(
(&t.mutability, &l.mutability),
(syn::PointerMutability::Const(_), syn::PointerMutability::Const(_))
| (syn::PointerMutability::Mut(_), syn::PointerMutability::Mut(_))
);
if !mut_eq {
return Err(ShapeError::ShapeMismatch("pointer mutability differs".into()));
}
match_ty(&t.elem, &l.elem, map, segs)
}
syn::Type::Paren(t) => {
let syn::Type::Paren(l) = leaf else {
return Err(ShapeError::ShapeMismatch(
"the template is a parenthesized type but the target is not".into(),
));
};
match_ty(&t.elem, &l.elem, map, segs)
}
syn::Type::Group(t) => {
let syn::Type::Group(l) = leaf else {
return Err(ShapeError::ShapeMismatch(
"the template is a grouped type but the target is not".into(),
));
};
match_ty(&t.elem, &l.elem, map, segs)
}
// `_` infer wildcard: matches ANY type, never binds a slot
syn::Type::Infer(_) => Ok(()),
// Everything else (fn pointers, trait objects, infer, macros...):
// verbatim compare — templates only bind idents in path/container
// positions; anything else must be written out exactly.
other => {
if other.to_token_stream().to_string() != leaf.to_token_stream().to_string() {
return Err(ShapeError::ShapeMismatch(format!(
"template `{}` does not match target `{}`",
other.to_token_stream(),
leaf.to_token_stream(),
)));
}
Ok(())
}
}
}