1extern crate proc_macro;
2
3use proc_macro::TokenStream;
4use proc_macro2::{Spacing, TokenStream as TokenStream2, TokenTree};
5use proc_macro_error::{abort_if_dirty, emit_error, proc_macro_error, set_dummy};
6use syn::parse::{Parse, ParseStream};
7use syn::{braced, Expr, Ident, Path, Token};
8use template_quote::{quote, ToTokens};
9
10#[derive(Clone)]
16enum NodeSpec {
17 Named(Ident),
18 NamedExpr(Ident, Expr),
19 Anon(Expr),
20}
21
22#[derive(Clone)]
24enum EdgeSpec {
25 Named(Ident),
26 NamedExpr(Ident, Expr),
27 Anon(Expr),
28 Empty,
29}
30
31struct EdgeDecl {
33 src: NodeSpec,
34 edge: EdgeSpec,
35 dst: NodeSpec,
36}
37
38struct DoubleDash;
39struct RightArrow;
40struct LeftArrow;
41
42struct GraphInput {
44 crate_path: Path,
45 initial: Option<Expr>,
46 decls: Vec<EdgeDecl>,
47}
48
49impl Parse for NodeSpec {
54 fn parse(input: ParseStream) -> syn::Result<Self> {
55 if input.peek(syn::token::Brace) {
56 let content;
57 braced!(content in input);
58 let expr: Expr = content.parse()?;
59 Ok(NodeSpec::Anon(expr))
60 } else {
61 let ident: Ident = input.parse()?;
62 if input.peek(syn::token::Brace) {
63 let content;
64 braced!(content in input);
65 let expr: Expr = content.parse()?;
66 Ok(NodeSpec::NamedExpr(ident, expr))
67 } else {
68 Ok(NodeSpec::Named(ident))
69 }
70 }
71 }
72}
73
74impl Parse for EdgeSpec {
75 fn parse(input: ParseStream) -> syn::Result<Self> {
76 if input.peek(Token![-]) && input.peek2(Token![-]) {
78 return Ok(EdgeSpec::Empty);
79 }
80 if input.peek(syn::token::Brace) {
81 let content;
82 braced!(content in input);
83 let expr: Expr = content.parse()?;
84 Ok(EdgeSpec::Anon(expr))
85 } else {
86 let ident: Ident = input.parse()?;
87 if input.peek(syn::token::Brace) {
88 let content;
89 braced!(content in input);
90 let expr: Expr = content.parse()?;
91 Ok(EdgeSpec::NamedExpr(ident, expr))
92 } else {
93 Ok(EdgeSpec::Named(ident))
94 }
95 }
96 }
97}
98
99impl Parse for DoubleDash {
100 fn parse(input: ParseStream) -> syn::Result<Self> {
101 let minus = input.parse::<TokenTree>()?;
103 if !matches!(minus, TokenTree::Punct(p) if p.as_char() == '-' && p.spacing() == Spacing::Joint)
104 {
105 return Err(syn::Error::new(
106 input.span(),
107 "expected `-` with joint spacing",
108 ));
109 }
110 input.parse::<Token![-]>()?;
111 Ok(Self)
112 }
113}
114
115impl Parse for RightArrow {
116 fn parse(input: ParseStream) -> syn::Result<Self> {
117 input.parse::<DoubleDash>()?;
118 input.parse::<Token![>]>()?;
119 Ok(Self)
120 }
121}
122
123impl Parse for LeftArrow {
124 fn parse(input: ParseStream) -> syn::Result<Self> {
125 input.parse::<Token![<]>()?;
126 input.parse::<DoubleDash>()?;
127 Ok(Self)
128 }
129}
130
131fn is_arrow_only(input: ParseStream) -> bool {
132 let fork = input.fork();
133 let first = fork.parse::<TokenTree>();
134 let second = fork.parse::<TokenTree>();
135 let third = fork.parse::<TokenTree>();
136 if let (Ok(TokenTree::Punct(a)), Ok(TokenTree::Punct(b)), Ok(TokenTree::Punct(c))) =
137 (first, second, third)
138 {
139 if a.as_char() == '-'
140 && b.as_char() == '-'
141 && c.as_char() == '>'
142 && a.spacing() == Spacing::Joint
143 && b.spacing() == Spacing::Joint
144 {
145 return true;
146 }
147 }
148 false
149}
150
151fn parse_arrow_only(input: ParseStream) -> syn::Result<bool> {
152 if is_arrow_only(input) {
153 let _: TokenTree = input.parse()?;
154 let _: TokenTree = input.parse()?;
155 let _: TokenTree = input.parse()?;
156 return Ok(true);
157 }
158 Ok(false)
159}
160
161fn parse_forward_segment(input: ParseStream, src: NodeSpec) -> syn::Result<(EdgeDecl, NodeSpec)> {
162 if parse_arrow_only(input)? {
163 let dst: NodeSpec = input.parse()?;
164 let decl = EdgeDecl {
165 src,
166 edge: EdgeSpec::Empty,
167 dst: dst.clone(),
168 };
169 return Ok((decl, dst));
170 }
171
172 let _: DoubleDash = input.parse()?;
173 if is_arrow_only(input) {
174 return Err(syn::Error::new(
175 input.span(),
176 "empty forward edge must use `-->` (not `-- -->`)",
177 ));
178 }
179 let edge: EdgeSpec = input.parse()?;
180 let _: RightArrow = input.parse()?;
181 let dst: NodeSpec = input.parse()?;
182 let decl = EdgeDecl {
183 src,
184 edge,
185 dst: dst.clone(),
186 };
187 Ok((decl, dst))
188}
189
190fn parse_reverse_segment(input: ParseStream, left: NodeSpec) -> syn::Result<(EdgeDecl, NodeSpec)> {
191 let _: LeftArrow = input.parse()?;
192
193 if !input.peek(syn::token::Brace) && !input.peek(Ident) && !input.peek(Token![-]) {
195 return Err(syn::Error::new(input.span(), "expected node after `<--`"));
196 }
197
198 if input.peek(syn::token::Brace) || input.peek(Ident) {
200 let fork = input.fork();
201 let maybe_spec = fork.parse::<EdgeSpec>();
202 if let Ok(spec) = maybe_spec {
203 if !matches!(spec, EdgeSpec::Empty) && fork.parse::<DoubleDash>().is_ok() {
204 let edge: EdgeSpec = input.parse()?;
206 let _: DoubleDash = input.parse()?;
207 let right: NodeSpec = input.parse()?;
208 let decl = EdgeDecl {
209 src: right.clone(),
210 edge,
211 dst: left,
212 };
213 return Ok((decl, right));
214 }
215 }
216
217 let right: NodeSpec = input.parse()?;
219 let decl = EdgeDecl {
220 src: right.clone(),
221 edge: EdgeSpec::Empty,
222 dst: left,
223 };
224 return Ok((decl, right));
225 }
226
227 let _: DoubleDash = input.parse()?;
229 Err(syn::Error::new(
230 input.span(),
231 "empty reverse edge must use `<--` (not `<-- --`)",
232 ))
233}
234
235impl Parse for GraphInput {
236 fn parse(input: ParseStream) -> syn::Result<Self> {
237 let crate_path: Path = input.parse()?;
238 input.parse::<Token![,]>()?;
239
240 let initial = if input.peek2(Token![=>]) || {
242 let fork = input.fork();
244 fork.parse::<Expr>().is_ok() && fork.peek(Token![=>])
245 } {
246 let expr: Expr = input.parse()?;
247 input.parse::<Token![=>]>()?;
248 Some(expr)
249 } else {
250 None
251 };
252
253 let mut decls = Vec::new();
254 while !input.is_empty() {
255 let mut cur: NodeSpec = input.parse()?;
256 while !input.is_empty() && !input.peek(Token![,]) {
257 if input.peek(Token![<]) {
258 let (decl, next) = parse_reverse_segment(input, cur)?;
259 decls.push(decl);
260 cur = next;
261 } else {
262 let (decl, next) = parse_forward_segment(input, cur)?;
263 decls.push(decl);
264 cur = next;
265 }
266 }
267 if input.peek(Token![,]) {
268 input.parse::<Token![,]>()?;
269 }
270 }
271
272 Ok(GraphInput {
273 crate_path,
274 initial,
275 decls,
276 })
277 }
278}
279
280fn gen_node_insert(
287 spec: &NodeSpec,
288 crate_path: &Path,
289 graph_access: &TokenStream2,
290 counter: &mut usize,
291) -> (TokenStream2, bool) {
292 match spec {
293 NodeSpec::Named(ident) => {
294 let expr_ident = ident.clone();
295 (
296 quote! {
297 let #expr_ident = unsafe {
298 #crate_path::graph::capability::InsertNode::insert_node_unchecked(
299 #graph_access, #expr_ident
300 ).unwrap()
301 };
302 },
303 true,
304 )
305 }
306 NodeSpec::NamedExpr(ident, expr) => {
307 let binding_ident = ident.clone();
308 (
309 quote! {
310 let #binding_ident = unsafe {
311 #crate_path::graph::capability::InsertNode::insert_node_unchecked(
312 #graph_access, #expr
313 ).unwrap()
314 };
315 },
316 true,
317 )
318 }
319 NodeSpec::Anon(expr) => {
320 let tmp = syn::Ident::new(
321 &format!("__node_{}", counter),
322 proc_macro2::Span::call_site(),
323 );
324 *counter += 1;
325 (
326 quote! {
327 let #tmp = unsafe {
328 #crate_path::graph::capability::InsertNode::insert_node_unchecked(
329 #graph_access, #expr
330 ).unwrap()
331 };
332 },
333 false,
334 )
335 }
336 }
337}
338
339#[proc_macro]
340#[proc_macro_error]
341pub fn graph(input: TokenStream) -> TokenStream {
342 let input = syn::parse_macro_input!(input as GraphInput);
343 let crate_path = &input.crate_path;
344 let has_initial = input.initial.is_some();
345 let graph_access = if has_initial {
346 quote! { &mut *__graph }
347 } else {
348 quote! { &mut __graph }
349 };
350
351 let node_payload_sig = |spec: &NodeSpec| -> Option<String> {
352 match spec {
353 NodeSpec::Named(id) => Some(format!("named:{}", id)),
354 NodeSpec::NamedExpr(_, expr) => Some(format!("expr:{}", expr.to_token_stream())),
355 NodeSpec::Anon(_) => None,
356 }
357 };
358 let edge_payload_sig = |spec: &EdgeSpec| -> String {
359 match spec {
360 EdgeSpec::Named(id) => format!("named:{}", id),
361 EdgeSpec::NamedExpr(_, expr) => format!("expr:{}", expr.to_token_stream()),
362 EdgeSpec::Anon(expr) => format!("anon:{}", expr.to_token_stream()),
363 EdgeSpec::Empty => "empty".to_string(),
364 }
365 };
366
367 let mut named_let_keys = Vec::<String>::new();
370 let mut named_lets = Vec::<TokenStream2>::new();
371 for decl in &input.decls {
372 for spec in [&decl.src, &decl.dst] {
373 match spec {
374 NodeSpec::Named(ident) => {
375 let key = ident.to_string();
376 if !named_let_keys.contains(&key) {
377 let id = ident.clone();
378 named_lets.push(quote! { let #id = #id; });
379 named_let_keys.push(key);
380 }
381 }
382 NodeSpec::NamedExpr(_, _) | NodeSpec::Anon(_) => {}
383 }
384 }
385 }
386
387 let mut named_edge_let_keys = Vec::<String>::new();
389 let mut named_edge_lets = Vec::<TokenStream2>::new();
390 for decl in &input.decls {
391 match &decl.edge {
392 EdgeSpec::Named(ident) => {
393 let key = ident.to_string();
394 if !named_edge_let_keys.contains(&key) {
395 let id = ident.clone();
396 named_edge_lets.push(quote! { let #id = #id; });
397 named_edge_let_keys.push(key);
398 }
399 }
400 EdgeSpec::NamedExpr(_, _) | EdgeSpec::Anon(_) | EdgeSpec::Empty => {}
401 }
402 }
403
404 let mut node_stmts = Vec::<TokenStream2>::new();
406 let mut decl_endpoint_vars = Vec::<(syn::Ident, syn::Ident)>::new();
407 let mut named_node_defined = std::collections::HashMap::<String, String>::new();
408 let mut named_node_span = std::collections::HashMap::<String, proc_macro2::Span>::new();
409 let mut node_counter: usize = 0;
410
411 let mut ensure_node = |spec: &NodeSpec| -> syn::Ident {
412 match spec {
413 NodeSpec::Named(ident) | NodeSpec::NamedExpr(ident, _) => {
414 let key = ident.to_string();
415 let sig = node_payload_sig(spec).unwrap();
416 if let Some(prev) = named_node_defined.get(&key) {
417 if prev != &sig {
418 let first_span = named_node_span[&key];
419 emit_error!(
420 ident.span(),
421 "node `{}` has conflicting definitions",
422 key;
423 help = first_span => "first definition for node `{}` is here", key
424 );
425 }
426 ident.clone()
427 } else {
428 let (stmt, _) =
429 gen_node_insert(spec, crate_path, &graph_access, &mut node_counter);
430 node_stmts.push(stmt);
431 named_node_defined.insert(key.clone(), sig);
432 named_node_span.insert(key, ident.span());
433 ident.clone()
434 }
435 }
436 NodeSpec::Anon(_) => {
437 let tmp = syn::Ident::new(
438 &format!("__node_{}", node_counter),
439 proc_macro2::Span::call_site(),
440 );
441 let (stmt, _) = gen_node_insert(spec, crate_path, &graph_access, &mut node_counter);
442 node_stmts.push(stmt);
443 tmp
444 }
445 }
446 };
447
448 for decl in &input.decls {
449 let src_var = ensure_node(&decl.src);
450 let dst_var = ensure_node(&decl.dst);
451 decl_endpoint_vars.push((src_var, dst_var));
452 }
453
454 let mut edge_stmts = Vec::<TokenStream2>::new();
456 let mut any_named_node = false;
457 let mut any_named_edge = false;
458 let mut named_node_span: Option<proc_macro2::Span> = None;
459 let mut named_edge_span: Option<proc_macro2::Span> = None;
460 let mut edge_counter: usize = 0;
461 let mut named_edge_defined =
462 std::collections::HashMap::<String, (String, proc_macro2::Span)>::new();
463
464 for (decl_ix, decl) in input.decls.iter().enumerate() {
465 let (src_var, dst_var) = &decl_endpoint_vars[decl_ix];
466
467 if matches!(&decl.src, NodeSpec::Named(_) | NodeSpec::NamedExpr(_, _))
469 || matches!(&decl.dst, NodeSpec::Named(_) | NodeSpec::NamedExpr(_, _))
470 {
471 any_named_node = true;
472 if named_node_span.is_none() {
473 named_node_span = match (&decl.src, &decl.dst) {
474 (NodeSpec::Named(id), _) => Some(id.span()),
475 (_, NodeSpec::Named(id)) => Some(id.span()),
476 (NodeSpec::NamedExpr(id, _), _) => Some(id.span()),
477 (_, NodeSpec::NamedExpr(id, _)) => Some(id.span()),
478 _ => None,
479 };
480 }
481 }
482
483 match &decl.edge {
484 EdgeSpec::Named(ident) => {
485 any_named_edge = true;
486 if named_edge_span.is_none() {
487 named_edge_span = Some(ident.span());
488 }
489 let sig = format!("{}|{}|{}", src_var, edge_payload_sig(&decl.edge), dst_var);
490 let key = ident.to_string();
491 if let Some((prev_sig, first_span)) = named_edge_defined.get(&key) {
492 if prev_sig != &sig {
493 emit_error!(
494 ident.span(),
495 "edge `{}` is used for different edges",
496 key;
497 help = *first_span => "first definition for edge `{}` is here", key
498 );
499 }
500 continue;
501 }
502 named_edge_defined.insert(key, (sig, ident.span()));
503 let id = ident.clone();
504 edge_stmts.push(quote! {
505 let #id = unsafe {
506 #crate_path::graph::capability::InsertEdge::insert_edge_unchecked(
507 #graph_access, #id, __directed_endpoints(::core::clone::Clone::clone(&#src_var), ::core::clone::Clone::clone(&#dst_var))
508 ).unwrap()
509 };
510 });
511 }
512 EdgeSpec::NamedExpr(ident, expr) => {
513 any_named_edge = true;
514 if named_edge_span.is_none() {
515 named_edge_span = Some(ident.span());
516 }
517 let sig = format!("{}|{}|{}", src_var, edge_payload_sig(&decl.edge), dst_var);
518 let key = ident.to_string();
519 if let Some((prev_sig, first_span)) = named_edge_defined.get(&key) {
520 if prev_sig != &sig {
521 emit_error!(
522 ident.span(),
523 "edge `{}` is used for different edges",
524 key;
525 help = *first_span => "first definition for edge `{}` is here", key
526 );
527 }
528 continue;
529 }
530 named_edge_defined.insert(key, (sig, ident.span()));
531 let id = ident.clone();
532 edge_stmts.push(quote! {
533 let #id = unsafe {
534 #crate_path::graph::capability::InsertEdge::insert_edge_unchecked(
535 #graph_access, #expr, __directed_endpoints(::core::clone::Clone::clone(&#src_var), ::core::clone::Clone::clone(&#dst_var))
536 ).unwrap()
537 };
538 });
539 }
540 EdgeSpec::Anon(expr) => {
541 let tmp = syn::Ident::new(
542 &format!("__edge_{}", edge_counter),
543 proc_macro2::Span::call_site(),
544 );
545 edge_counter += 1;
546 edge_stmts.push(quote! {
547 let #tmp = unsafe {
548 #crate_path::graph::capability::InsertEdge::insert_edge_unchecked(
549 #graph_access, #expr, __directed_endpoints(::core::clone::Clone::clone(&#src_var), ::core::clone::Clone::clone(&#dst_var))
550 ).unwrap()
551 };
552 });
553 }
554 EdgeSpec::Empty => {
555 let tmp = syn::Ident::new(
556 &format!("__edge_{}", edge_counter),
557 proc_macro2::Span::call_site(),
558 );
559 edge_counter += 1;
560 edge_stmts.push(quote! {
561 let #tmp = unsafe {
562 #crate_path::graph::capability::InsertEdge::insert_edge_unchecked(
563 #graph_access, Default::default(), __directed_endpoints(::core::clone::Clone::clone(&#src_var), ::core::clone::Clone::clone(&#dst_var))
564 ).unwrap()
565 };
566 });
567 }
568 }
569 }
570
571 let assert_node_ident = syn::Ident::new(
572 "__assert_stable_node",
573 named_node_span.unwrap_or(proc_macro2::Span::call_site()),
574 );
575 let assert_edge_ident = syn::Ident::new(
576 "__assert_stable_edge",
577 named_edge_span.unwrap_or(proc_macro2::Span::call_site()),
578 );
579
580 let output = if let Some(init_expr) = &input.initial {
581 quote! {
586 #(#named_lets)*
587 #(#named_edge_lets)*
588 fn __directed_endpoints<E: #crate_path::graph::edge::Endpoints>(
589 source: E::NodeIx,
590 target: E::NodeIx,
591 ) -> E {
592 E::try_from_sources_targets(core::iter::once(source), core::iter::once(target))
593 .expect("failed to construct endpoints from source/target")
594 }
595 let mut __graph = #init_expr;
596 #(#node_stmts)*
597 #(#edge_stmts)*
598 #(if any_named_node) {
599 fn #assert_node_ident<G: #crate_path::graph::capability::StableNode>(_: &G) {}
600 #assert_node_ident(&*__graph);
601 }
602 #(if any_named_edge) {
603 fn #assert_edge_ident<G: #crate_path::graph::capability::StableEdge>(_: &G) {}
604 #assert_edge_ident(&*__graph);
605 }
606 }
607 } else {
608 quote! {
610 {
611 #(#named_lets)*
612 #(#named_edge_lets)*
613 fn __directed_endpoints<E: #crate_path::graph::edge::Endpoints>(
614 source: E::NodeIx,
615 target: E::NodeIx,
616 ) -> E {
617 E::try_from_sources_targets(core::iter::once(source), core::iter::once(target))
618 .expect("failed to construct endpoints from source/target")
619 }
620 let mut __graph = Default::default();
621 #(#node_stmts)*
622 #(#edge_stmts)*
623 __graph
624 }
625 }
626 };
627
628 set_dummy(output.clone());
630
631 abort_if_dirty();
632
633 output.into()
634}