dfir_lang/graph/meta_graph.rs
1#![warn(missing_docs)]
2
3extern crate proc_macro;
4
5use std::collections::{BTreeMap, BTreeSet};
6use std::fmt::Debug;
7use std::iter::FusedIterator;
8
9use itertools::Itertools;
10use proc_macro2::{Ident, Literal, Span, TokenStream, TokenTree};
11use quote::{ToTokens, format_ident, quote, quote_spanned};
12use serde::{Deserialize, Serialize};
13use slotmap::{Key, SecondaryMap, SlotMap, SparseSecondaryMap};
14use syn::spanned::Spanned;
15
16use super::graph_write::{Dot, GraphWrite, Mermaid};
17use super::ops::snapshot_keyed::SNAPSHOT_KEYED;
18use super::ops::snapshot_prefix::SNAPSHOT_PREFIX;
19use super::ops::{
20 DelayType, FloType, OPERATORS, OperatorWriteOutput, WriteContextArgs, find_op_op_constraints,
21 null_write_iterator_fn,
22};
23use super::{
24 CONTEXT, Color, DiMulGraph, GRAPH, GraphEdgeId, GraphLoopId, GraphNode, GraphNodeId,
25 GraphSubgraphId, HANDOFF_NODE_STR, HandoffKind, MODULE_BOUNDARY_NODE_STR, OperatorInstance,
26 PortIndexValue, SINGLETON_SLOT_NODE_STR, Varname, change_spans, get_operator_generics,
27};
28use crate::diagnostic::{Diagnostic, Diagnostics, Level};
29use crate::pretty_span::{PrettyRowCol, PrettySpan};
30use crate::process_singletons;
31
32/// The shape of the persistent state backing a retaining windowing (`FloType::WindowingRetain`)
33/// loop-entry handoff. Such state is declared outside the tick closure, persists across ticks,
34/// and is never consumed by the loop (which reads clones out of it each time it fires).
35#[derive(Copy, Clone, Debug, PartialEq, Eq)]
36enum RetainKind {
37 /// `snapshot()`: a single last-write-wins `Option<T>` cell; each new item replaces the
38 /// previous one.
39 Cell,
40 /// `snapshot_keyed()`: a per-key `FxHashMap<K, V>` fed by `(K, Option<V>)` updates; `Some(v)`
41 /// upserts, `None` removes.
42 Keyed,
43 /// `snapshot_prefix()`: an append-only `Vec<T>` of every item received so far, in arrival
44 /// order.
45 Prefix,
46}
47
48/// A resolved handoff reference: the target node ID plus mutability and access group info.
49#[derive(Clone, Debug, Serialize, Deserialize)]
50pub struct ResolvedHandoffRef {
51 /// The resolved target node ID (`None` if unresolved/error).
52 pub node_id: Option<GraphNodeId>,
53 /// Whether this is a mutable reference (`#mut var`).
54 pub is_mut: bool,
55 /// Optional access group for ordering (`#{N} var`).
56 pub access_group: Option<u32>,
57}
58
59/// An abstract "meta graph" representation of a DFIR graph.
60///
61/// Can be with or without subgraph partitioning, stratification, and handoff insertion. This is
62/// the meta graph used for generating Rust source code in macros from DFIR sytnax.
63///
64/// This struct has a lot of methods for manipulating the graph, vaguely grouped together in
65/// separate `impl` blocks. You might notice a few particularly specific arbitray-seeming methods
66/// in here--those are just what was needed for the compilation algorithms. If you need another
67/// method then add it.
68#[derive(Default, Debug, Serialize, Deserialize)]
69pub struct DfirGraph {
70 /// Each node type (operator or handoff).
71 nodes: SlotMap<GraphNodeId, GraphNode>,
72
73 /// Instance data corresponding to each operator node.
74 /// This field will be empty after deserialization.
75 #[serde(skip)]
76 operator_instances: SecondaryMap<GraphNodeId, OperatorInstance>,
77 /// Debugging/tracing tag for each operator node.
78 operator_tag: SecondaryMap<GraphNodeId, String>,
79 /// Graph data structure (two-way adjacency list).
80 graph: DiMulGraph<GraphNodeId, GraphEdgeId>,
81 /// Input and output port for each edge.
82 ports: SecondaryMap<GraphEdgeId, (PortIndexValue, PortIndexValue)>,
83
84 /// Which loop a node belongs to (or none for top-level).
85 node_loops: SecondaryMap<GraphNodeId, GraphLoopId>,
86 /// Which nodes belong to each loop.
87 loop_nodes: SlotMap<GraphLoopId, Vec<GraphNodeId>>,
88 /// For the loop, what is its parent (`None` for top-level).
89 loop_parent: SparseSecondaryMap<GraphLoopId, GraphLoopId>,
90 /// What loops are at the root.
91 root_loops: Vec<GraphLoopId>,
92 /// For the loop, what are its child loops.
93 loop_children: SecondaryMap<GraphLoopId, Vec<GraphLoopId>>,
94
95 /// Which subgraph each node belongs to.
96 node_subgraph: SecondaryMap<GraphNodeId, GraphSubgraphId>,
97
98 /// Which nodes belong to each subgraph.
99 subgraph_nodes: SlotMap<GraphSubgraphId, Vec<GraphNodeId>>,
100 /// Subgraph IDs in topological sort order (set during partitioning).
101 subgraph_toposort: Vec<GraphSubgraphId>,
102
103 /// Resolved handoff varnames references, per node.
104 node_handoff_references: SparseSecondaryMap<GraphNodeId, Vec<ResolvedHandoffRef>>,
105 /// What variable name each graph node belongs to (if any). For debugging (graph writing) purposes only.
106 node_varnames: SparseSecondaryMap<GraphNodeId, Varname>,
107
108 /// Delay type for handoff nodes that represent tick-boundary back-edges.
109 /// Set by `order_subgraphs` for `defer_tick` / `defer_tick_lazy`, either on handoff nodes
110 /// it injects or on existing handoff nodes that it marks as tick-boundary back-edges.
111 handoff_delay_type: SparseSecondaryMap<GraphNodeId, DelayType>,
112}
113
114/// Basic methods.
115impl DfirGraph {
116 /// Create a new empty graph.
117 pub fn new() -> Self {
118 Default::default()
119 }
120}
121
122/// Node methods.
123impl DfirGraph {
124 /// Get a node with its operator instance (if applicable).
125 pub fn node(&self, node_id: GraphNodeId) -> &GraphNode {
126 self.nodes.get(node_id).expect("Node not found.")
127 }
128
129 /// Get the `OperatorInstance` for a given node. Node must be an operator and have an
130 /// `OperatorInstance` present, otherwise will return `None`.
131 ///
132 /// Note that no operator instances will be persent after deserialization.
133 pub fn node_op_inst(&self, node_id: GraphNodeId) -> Option<&OperatorInstance> {
134 self.operator_instances.get(node_id)
135 }
136
137 /// Get the debug variable name attached to a graph node.
138 pub fn node_varname(&self, node_id: GraphNodeId) -> Option<&Varname> {
139 self.node_varnames.get(node_id)
140 }
141
142 /// Get subgraph for node.
143 pub fn node_subgraph(&self, node_id: GraphNodeId) -> Option<GraphSubgraphId> {
144 self.node_subgraph.get(node_id).copied()
145 }
146
147 /// Degree into a node, i.e. the number of predecessors.
148 pub fn node_degree_in(&self, node_id: GraphNodeId) -> usize {
149 self.graph.degree_in(node_id)
150 }
151
152 /// Degree out of a node, i.e. the number of successors.
153 pub fn node_degree_out(&self, node_id: GraphNodeId) -> usize {
154 self.graph.degree_out(node_id)
155 }
156
157 /// Successors, iterator of `(GraphEdgeId, GraphNodeId)` of outgoing edges.
158 pub fn node_successors(
159 &self,
160 src: GraphNodeId,
161 ) -> impl '_
162 + DoubleEndedIterator<Item = (GraphEdgeId, GraphNodeId)>
163 + ExactSizeIterator
164 + FusedIterator
165 + Clone
166 + Debug {
167 self.graph.successors(src)
168 }
169
170 /// Predecessors, iterator of `(GraphEdgeId, GraphNodeId)` of incoming edges.
171 pub fn node_predecessors(
172 &self,
173 dst: GraphNodeId,
174 ) -> impl '_
175 + DoubleEndedIterator<Item = (GraphEdgeId, GraphNodeId)>
176 + ExactSizeIterator
177 + FusedIterator
178 + Clone
179 + Debug {
180 self.graph.predecessors(dst)
181 }
182
183 /// Successor edges, iterator of `GraphEdgeId` of outgoing edges.
184 pub fn node_successor_edges(
185 &self,
186 src: GraphNodeId,
187 ) -> impl '_
188 + DoubleEndedIterator<Item = GraphEdgeId>
189 + ExactSizeIterator
190 + FusedIterator
191 + Clone
192 + Debug {
193 self.graph.successor_edges(src)
194 }
195
196 /// Predecessor edges, iterator of `GraphEdgeId` of incoming edges.
197 pub fn node_predecessor_edges(
198 &self,
199 dst: GraphNodeId,
200 ) -> impl '_
201 + DoubleEndedIterator<Item = GraphEdgeId>
202 + ExactSizeIterator
203 + FusedIterator
204 + Clone
205 + Debug {
206 self.graph.predecessor_edges(dst)
207 }
208
209 /// Successor nodes, iterator of `GraphNodeId`.
210 pub fn node_successor_nodes(
211 &self,
212 src: GraphNodeId,
213 ) -> impl '_
214 + DoubleEndedIterator<Item = GraphNodeId>
215 + ExactSizeIterator
216 + FusedIterator
217 + Clone
218 + Debug {
219 self.graph.successor_vertices(src)
220 }
221
222 /// Predecessor nodes, iterator of `GraphNodeId`.
223 pub fn node_predecessor_nodes(
224 &self,
225 dst: GraphNodeId,
226 ) -> impl '_
227 + DoubleEndedIterator<Item = GraphNodeId>
228 + ExactSizeIterator
229 + FusedIterator
230 + Clone
231 + Debug {
232 self.graph.predecessor_vertices(dst)
233 }
234
235 /// Iterator of node IDs `GraphNodeId`.
236 pub fn node_ids(&self) -> slotmap::basic::Keys<'_, GraphNodeId, GraphNode> {
237 self.nodes.keys()
238 }
239
240 /// Iterator over `(GraphNodeId, &Node)` pairs.
241 pub fn nodes(&self) -> slotmap::basic::Iter<'_, GraphNodeId, GraphNode> {
242 self.nodes.iter()
243 }
244
245 /// Insert a node, assigning the given varname.
246 pub fn insert_node(
247 &mut self,
248 node: GraphNode,
249 varname_opt: Option<Ident>,
250 loop_opt: Option<GraphLoopId>,
251 ) -> GraphNodeId {
252 let node_id = self.nodes.insert(node);
253 if let Some(varname) = varname_opt {
254 self.node_varnames.insert(node_id, Varname(varname));
255 }
256 if let Some(loop_id) = loop_opt {
257 self.node_loops.insert(node_id, loop_id);
258 self.loop_nodes[loop_id].push(node_id);
259 }
260 node_id
261 }
262
263 /// Insert an operator instance for the given node. Panics if already set.
264 pub fn insert_node_op_inst(&mut self, node_id: GraphNodeId, op_inst: OperatorInstance) {
265 assert!(matches!(
266 self.nodes.get(node_id),
267 Some(GraphNode::Operator(_))
268 ));
269 let old_inst = self.operator_instances.insert(node_id, op_inst);
270 assert!(old_inst.is_none());
271 }
272
273 /// Assign all operator instances if not set. Write diagnostic messages/errors into `diagnostics`.
274 pub fn insert_node_op_insts_all(&mut self, diagnostics: &mut Diagnostics) {
275 // Handle all nodes in two phases, since the helper methods take total ownership of `&self`.
276 // Possible to do in one phase, but would require accessing fields directly for partial mutable ownership.
277
278 // Collect operator instances, then assign.
279 let mut op_insts = Vec::new();
280 // Collect nodes that should be lowered to handoffs (the `handoff()`/`singleton()` pseudo-operators).
281 let mut handoff_nodes: Vec<(GraphNodeId, HandoffKind, Span)> = Vec::new();
282
283 for (node_id, node) in self.nodes() {
284 let GraphNode::Operator(operator) = node else {
285 continue;
286 };
287 if self.node_op_inst(node_id).is_some() {
288 continue;
289 };
290
291 // Recognize `handoff()`/`singleton()` pseudo-operators and lower to GraphNode::Handoff.
292 let handoff_kind = match &*operator.name_string() {
293 "handoff" => Some(HandoffKind::Vec),
294 "singleton" => Some(HandoffKind::Singleton),
295 "optional" => Some(HandoffKind::Optional),
296 _ => None,
297 };
298 if let Some(kind) = handoff_kind {
299 if !operator.args.is_empty() {
300 diagnostics.push(Diagnostic::spanned(
301 operator.path.span(),
302 Level::Error,
303 format!("`{}` takes no arguments.", operator.name_string()),
304 ));
305 }
306 if operator.type_arguments().is_some() {
307 diagnostics.push(Diagnostic::spanned(
308 operator.path.span(),
309 Level::Error,
310 format!("`{}` takes no generic arguments.", operator.name_string()),
311 ));
312 }
313 handoff_nodes.push((node_id, kind, operator.path.span()));
314 continue;
315 }
316
317 // Op constraints.
318 let Some(op_constraints) = find_op_op_constraints(operator) else {
319 diagnostics.push(Diagnostic::spanned(
320 operator.path.span(),
321 Level::Error,
322 format!("Unknown operator `{}`", operator.name_string()),
323 ));
324 continue;
325 };
326
327 // Input and output ports.
328 let (input_ports, output_ports) = {
329 let mut input_edges: Vec<(&PortIndexValue, GraphNodeId)> = self
330 .node_predecessors(node_id)
331 .map(|(edge_id, pred_id)| (self.edge_ports(edge_id).1, pred_id))
332 .collect();
333 // Ensure sorted by port index.
334 input_edges.sort();
335 let input_ports: Vec<PortIndexValue> = input_edges
336 .into_iter()
337 .map(|(port, _pred)| port)
338 .cloned()
339 .collect();
340
341 // Collect output arguments (successors).
342 let mut output_edges: Vec<(&PortIndexValue, GraphNodeId)> = self
343 .node_successors(node_id)
344 .map(|(edge_id, succ)| (self.edge_ports(edge_id).0, succ))
345 .collect();
346 // Ensure sorted by port index.
347 output_edges.sort();
348 let output_ports: Vec<PortIndexValue> = output_edges
349 .into_iter()
350 .map(|(port, _succ)| port)
351 .cloned()
352 .collect();
353
354 (input_ports, output_ports)
355 };
356
357 // Generic arguments.
358 let generics = get_operator_generics(diagnostics, operator);
359 // Generic argument errors.
360 {
361 // Span of `generic_args` (if it exists), otherwise span of the operator name.
362 let generics_span = generics
363 .generic_args
364 .as_ref()
365 .map(Spanned::span)
366 .unwrap_or_else(|| operator.path.span());
367
368 if !op_constraints
369 .persistence_args
370 .contains(&generics.persistence_args.len())
371 {
372 diagnostics.push(Diagnostic::spanned(
373 generics.persistence_args_span().unwrap_or(generics_span),
374 Level::Error,
375 format!(
376 "`{}` should have {} persistence lifetime arguments, actually has {}.",
377 op_constraints.name,
378 op_constraints.persistence_args.human_string(),
379 generics.persistence_args.len()
380 ),
381 ));
382 }
383 if !op_constraints.type_args.contains(&generics.type_args.len()) {
384 diagnostics.push(Diagnostic::spanned(
385 generics.type_args_span().unwrap_or(generics_span),
386 Level::Error,
387 format!(
388 "`{}` should have {} generic type arguments, actually has {}.",
389 op_constraints.name,
390 op_constraints.type_args.human_string(),
391 generics.type_args.len()
392 ),
393 ));
394 }
395 }
396
397 op_insts.push((
398 node_id,
399 OperatorInstance {
400 op_constraints,
401 input_ports,
402 output_ports,
403 singletons_referenced: operator.singletons_referenced.clone(),
404 generics,
405 arguments_pre: operator.args.clone(),
406 arguments_raw: operator.args_raw.clone(),
407 },
408 ));
409 }
410
411 for (node_id, op_inst) in op_insts {
412 self.insert_node_op_inst(node_id, op_inst);
413 }
414
415 // Replace pseudo-operator nodes with GraphNode::Handoff.
416 for (node_id, kind, span) in handoff_nodes {
417 self.nodes[node_id] = GraphNode::Handoff {
418 kind,
419 src_span: span,
420 dst_span: span,
421 };
422 }
423 }
424
425 /// Inserts a node between two existing nodes connected by the given `edge_id`.
426 ///
427 /// `edge`: (src, dst, `dst_idx`)
428 ///
429 /// Before: A (src) ------------> B (dst)
430 /// After: A (src) -> X (new) -> B (dst)
431 ///
432 /// Returns the ID of X & ID of edge OUT of X.
433 ///
434 /// Note that both the edges will be new and `edge_id` will be removed. Both new edges will
435 /// get the edge type of the original edge.
436 pub fn insert_intermediate_node(
437 &mut self,
438 edge_id: GraphEdgeId,
439 new_node: GraphNode,
440 ) -> (GraphNodeId, GraphEdgeId) {
441 let span = Some(new_node.span());
442
443 // Make corresponding operator instance (if `node` is an operator).
444 let op_inst_opt = 'oc: {
445 let GraphNode::Operator(operator) = &new_node else {
446 break 'oc None;
447 };
448 let Some(op_constraints) = find_op_op_constraints(operator) else {
449 break 'oc None;
450 };
451 let (input_port, output_port) = self.ports.get(edge_id).cloned().unwrap();
452
453 let mut dummy_diagnostics = Diagnostics::new();
454 let generics = get_operator_generics(&mut dummy_diagnostics, operator);
455 assert!(dummy_diagnostics.is_empty());
456
457 Some(OperatorInstance {
458 op_constraints,
459 input_ports: vec![input_port],
460 output_ports: vec![output_port],
461 singletons_referenced: operator.singletons_referenced.clone(),
462 generics,
463 arguments_pre: operator.args.clone(),
464 arguments_raw: operator.args_raw.clone(),
465 })
466 };
467
468 // Insert new `node`.
469 let node_id = self.nodes.insert(new_node);
470 // Insert corresponding `OperatorInstance` if applicable.
471 if let Some(op_inst) = op_inst_opt {
472 self.operator_instances.insert(node_id, op_inst);
473 }
474 // Update edges to insert node within `edge_id`.
475 let (e0, e1) = self
476 .graph
477 .insert_intermediate_vertex(node_id, edge_id)
478 .unwrap();
479
480 // Update corresponding ports.
481 let (src_idx, dst_idx) = self.ports.remove(edge_id).unwrap();
482 self.ports
483 .insert(e0, (src_idx, PortIndexValue::Elided(span)));
484 self.ports
485 .insert(e1, (PortIndexValue::Elided(span), dst_idx));
486
487 (node_id, e1)
488 }
489
490 /// Remove the node `node_id` but preserves and connects the single predecessor and single successor.
491 /// Panics if the node does not have exactly one predecessor and one successor, or is not in the graph.
492 pub fn remove_intermediate_node(&mut self, node_id: GraphNodeId) {
493 assert_eq!(
494 1,
495 self.node_degree_in(node_id),
496 "Removed intermediate node must have one predecessor"
497 );
498 assert_eq!(
499 1,
500 self.node_degree_out(node_id),
501 "Removed intermediate node must have one successor"
502 );
503 assert!(
504 self.node_subgraph.is_empty() && self.subgraph_nodes.is_empty(),
505 "Should not remove intermediate node after subgraph partitioning"
506 );
507
508 assert!(self.nodes.remove(node_id).is_some());
509 let (new_edge_id, (pred_edge_id, succ_edge_id)) =
510 self.graph.remove_intermediate_vertex(node_id).unwrap();
511 self.operator_instances.remove(node_id);
512 self.node_varnames.remove(node_id);
513
514 let (src_port, _) = self.ports.remove(pred_edge_id).unwrap();
515 let (_, dst_port) = self.ports.remove(succ_edge_id).unwrap();
516 self.ports.insert(new_edge_id, (src_port, dst_port));
517 }
518
519 /// Helper method: determine the "color" (pull vs push) of a node based on its in and out degree,
520 /// excluding reference edges. If linear (1 in, 1 out), color is `None`, indicating it can be
521 /// either push or pull.
522 ///
523 /// Note that this does NOT consider `DelayType` barriers (which generally implies `Pull`).
524 pub(crate) fn node_color(&self, node_id: GraphNodeId) -> Option<Color> {
525 if matches!(self.node(node_id), GraphNode::Handoff { .. }) {
526 return Some(Color::Hoff);
527 }
528
529 // TODO(shadaj): this is a horrible hack
530 if let GraphNode::Operator(op) = self.node(node_id)
531 && (op.name_string() == "resolve_futures_blocking"
532 || op.name_string() == "resolve_futures_blocking_ordered")
533 {
534 return Some(Color::Push);
535 }
536
537 // In-degree, excluding ref-edges.
538 let inn_degree = self.node_predecessor_nodes(node_id).len();
539 // Out-degree excluding ref-edges.
540 let out_degree = self.node_successor_nodes(node_id).len();
541
542 match (inn_degree, out_degree) {
543 (0, 0) => None, // Generally should not happen, "Degenerate subgraph detected".
544 (0, 1) => Some(Color::Pull),
545 (1, 0) => Some(Color::Push),
546 (1, 1) => None, // Linear, can be either push or pull.
547 (_many, 0 | 1) => Some(Color::Pull),
548 (0 | 1, _many) => Some(Color::Push),
549 (_many, _to_many) => Some(Color::Comp),
550 }
551 }
552
553 /// Set the operator tag (for debugging/tracing).
554 pub fn set_operator_tag(&mut self, node_id: GraphNodeId, tag: String) {
555 self.operator_tag.insert(node_id, tag);
556 }
557}
558
559/// Handoff references.
560impl DfirGraph {
561 /// Set the handoff references for the `node_id` operator. Each reference corresponds to the
562 /// same index in the [`crate::parse::Operator::singletons_referenced`] vec.
563 pub fn set_node_handoff_references(
564 &mut self,
565 node_id: GraphNodeId,
566 singletons_referenced: Vec<ResolvedHandoffRef>,
567 ) -> Option<Vec<ResolvedHandoffRef>> {
568 self.node_handoff_references
569 .insert(node_id, singletons_referenced)
570 }
571
572 /// Gets the handoff references for a node. Returns an empty slice for non-operators and
573 /// operators that do not reference handoffs.
574 pub fn node_handoff_references(&self, node_id: GraphNodeId) -> &[ResolvedHandoffRef] {
575 self.node_handoff_references
576 .get(node_id)
577 .map(std::ops::Deref::deref)
578 .unwrap_or_default()
579 }
580
581 /// Collect all refs, grouped by the handoff they're pointing at, then by the access group idx `Option<u32>`.
582 pub fn node_handoff_reference_groups(&self) -> NodeHandoffReferenceGroups<'_> {
583 let mut handoff_references = NodeHandoffReferenceGroups::new();
584 for node_id in self.node_ids() {
585 if let GraphNode::Operator(operator) = self.node(node_id) {
586 let resolved = self.node_handoff_references(node_id);
587 for (resolved_ref, ref_token) in
588 resolved.iter().zip(operator.singletons_referenced.iter())
589 {
590 if let Some(target_nid) = resolved_ref.node_id {
591 handoff_references
592 .entry(target_nid)
593 .or_default()
594 .entry(resolved_ref.access_group)
595 .or_default()
596 .push((node_id, resolved_ref, ref_token.span()));
597 }
598 }
599 }
600 }
601 handoff_references
602 }
603}
604
605/// Per-node handoff references, in turn grouped by access group.
606/// Map: `handoff_node_id` -> `access_group` -> (source `GraphNodeId`, `ResolvedHandoffRef`, `#ref` span)
607pub type NodeHandoffReferenceGroups<'a> =
608 BTreeMap<GraphNodeId, BTreeMap<Option<u32>, Vec<(GraphNodeId, &'a ResolvedHandoffRef, Span)>>>;
609
610/// Module methods.
611impl DfirGraph {
612 /// When modules are imported into a flat graph, they come with an input and output `ModuleBoundary` node.
613 /// The partitioner doesn't understand these nodes and will panic if it encounters them.
614 /// `merge_modules` removes them from the graph, stitching the input and output sides of the `ModuleBoundary`s based on their ports.
615 /// For example:
616 ///
617 /// ```text
618 /// source_iter([]) -> [myport]ModuleBoundary(input)[my_port] -> map(|x| x) -> ModuleBoundary(output) -> null();
619 /// ```
620 ///
621 /// In the above example, the `[myport]` port will be used to connect the `source_iter` with the `map` that is inside of the module.
622 /// The output module boundary has elided ports, this is also used to match up the input/output across the module boundary.
623 pub fn merge_modules(&mut self) -> Result<(), Diagnostic> {
624 let mod_bound_nodes = self
625 .nodes()
626 .filter(|(_nid, node)| matches!(node, GraphNode::ModuleBoundary { .. }))
627 .map(|(nid, _node)| nid)
628 .collect::<Vec<_>>();
629
630 for mod_bound_node in mod_bound_nodes {
631 self.remove_module_boundary(mod_bound_node)?;
632 }
633
634 Ok(())
635 }
636
637 /// see `merge_modules`
638 /// This function removes a singular module boundary from the graph and performs the necessary stitching to fix the graph afterward.
639 /// `merge_modules` calls this function for each module boundary in the graph.
640 fn remove_module_boundary(&mut self, mod_bound_node: GraphNodeId) -> Result<(), Diagnostic> {
641 assert!(
642 self.node_subgraph.is_empty() && self.subgraph_nodes.is_empty(),
643 "Should not remove intermediate node after subgraph partitioning"
644 );
645
646 let mut mod_pred_ports = BTreeMap::new();
647 let mut mod_succ_ports = BTreeMap::new();
648
649 for mod_out_edge in self.node_predecessor_edges(mod_bound_node) {
650 let (pred_port, succ_port) = self.edge_ports(mod_out_edge);
651 mod_pred_ports.insert(succ_port.clone(), (mod_out_edge, pred_port.clone()));
652 }
653
654 for mod_inn_edge in self.node_successor_edges(mod_bound_node) {
655 let (pred_port, succ_port) = self.edge_ports(mod_inn_edge);
656 mod_succ_ports.insert(pred_port.clone(), (mod_inn_edge, succ_port.clone()));
657 }
658
659 if mod_pred_ports.keys().collect::<BTreeSet<_>>()
660 != mod_succ_ports.keys().collect::<BTreeSet<_>>()
661 {
662 // get module boundary node
663 let GraphNode::ModuleBoundary { input, import_expr } = self.node(mod_bound_node) else {
664 panic!();
665 };
666
667 if *input {
668 return Err(Diagnostic {
669 span: *import_expr,
670 level: Level::Error,
671 message: format!(
672 "The ports into the module did not match. input: {:?}, expected: {:?}",
673 mod_pred_ports.keys().map(|x| x.to_string()).join(", "),
674 mod_succ_ports.keys().map(|x| x.to_string()).join(", ")
675 ),
676 });
677 }
678 return Err(Diagnostic {
679 span: *import_expr,
680 level: Level::Error,
681 message: format!(
682 "The ports out of the module did not match. output: {:?}, expected: {:?}",
683 mod_succ_ports.keys().map(|x| x.to_string()).join(", "),
684 mod_pred_ports.keys().map(|x| x.to_string()).join(", "),
685 ),
686 });
687 }
688
689 for (port, (pred_edge, pred_port)) in mod_pred_ports {
690 let (succ_edge, succ_port) = mod_succ_ports.remove(&port).unwrap();
691
692 let (src, _) = self.edge(pred_edge);
693 let (_, dst) = self.edge(succ_edge);
694 self.remove_edge(pred_edge);
695 self.remove_edge(succ_edge);
696
697 let new_edge_id = self.graph.insert_edge(src, dst);
698 self.ports.insert(new_edge_id, (pred_port, succ_port));
699 }
700
701 self.graph.remove_vertex(mod_bound_node);
702 self.nodes.remove(mod_bound_node);
703
704 Ok(())
705 }
706}
707
708/// Edge methods.
709impl DfirGraph {
710 /// Get the `src` and `dst` for an edge: `(src GraphNodeId, dst GraphNodeId)`.
711 pub fn edge(&self, edge_id: GraphEdgeId) -> (GraphNodeId, GraphNodeId) {
712 let (src, dst) = self.graph.edge(edge_id).expect("Edge not found.");
713 (src, dst)
714 }
715
716 /// Get the source and destination ports for an edge: `(src &PortIndexValue, dst &PortIndexValue)`.
717 pub fn edge_ports(&self, edge_id: GraphEdgeId) -> (&PortIndexValue, &PortIndexValue) {
718 let (src_port, dst_port) = self.ports.get(edge_id).expect("Edge not found.");
719 (src_port, dst_port)
720 }
721
722 /// Iterator of all edge IDs `GraphEdgeId`.
723 pub fn edge_ids(&self) -> slotmap::basic::Keys<'_, GraphEdgeId, (GraphNodeId, GraphNodeId)> {
724 self.graph.edge_ids()
725 }
726
727 /// Iterator over all edges: `(GraphEdgeId, (src GraphNodeId, dst GraphNodeId))`.
728 pub fn edges(
729 &self,
730 ) -> impl '_
731 + ExactSizeIterator<Item = (GraphEdgeId, (GraphNodeId, GraphNodeId))>
732 + FusedIterator
733 + Clone
734 + Debug {
735 self.graph.edges()
736 }
737
738 /// Insert an edge between nodes thru the given ports.
739 pub fn insert_edge(
740 &mut self,
741 src: GraphNodeId,
742 src_port: PortIndexValue,
743 dst: GraphNodeId,
744 dst_port: PortIndexValue,
745 ) -> GraphEdgeId {
746 let edge_id = self.graph.insert_edge(src, dst);
747 self.ports.insert(edge_id, (src_port, dst_port));
748 edge_id
749 }
750
751 /// Removes an edge and its corresponding ports and edge type info.
752 pub fn remove_edge(&mut self, edge: GraphEdgeId) {
753 let (_src, _dst) = self.graph.remove_edge(edge).unwrap();
754 let (_src_port, _dst_port) = self.ports.remove(edge).unwrap();
755 }
756}
757
758/// Subgraph methods.
759impl DfirGraph {
760 /// Nodes belonging to the given subgraph.
761 pub fn subgraph(&self, subgraph_id: GraphSubgraphId) -> &Vec<GraphNodeId> {
762 self.subgraph_nodes
763 .get(subgraph_id)
764 .expect("Subgraph not found.")
765 }
766
767 /// Iterator over all subgraph IDs.
768 pub fn subgraph_ids(&self) -> slotmap::basic::Keys<'_, GraphSubgraphId, Vec<GraphNodeId>> {
769 self.subgraph_nodes.keys()
770 }
771
772 /// Subgraph IDs in topological sort order.
773 pub fn subgraph_toposort(&self) -> &[GraphSubgraphId] {
774 &self.subgraph_toposort
775 }
776
777 /// Set the topological sort order for subgraphs.
778 pub fn set_subgraph_toposort(&mut self, order: Vec<GraphSubgraphId>) {
779 self.subgraph_toposort = order;
780 }
781
782 /// Iterator over all subgraphs, ID and members: `(GraphSubgraphId, Vec<GraphNodeId>)`.
783 pub fn subgraphs(&self) -> slotmap::basic::Iter<'_, GraphSubgraphId, Vec<GraphNodeId>> {
784 self.subgraph_nodes.iter()
785 }
786
787 /// Create a subgraph consisting of `node_ids`. Returns an error if any of the nodes are already in a subgraph.
788 pub fn insert_subgraph(
789 &mut self,
790 node_ids: Vec<GraphNodeId>,
791 ) -> Result<GraphSubgraphId, (GraphNodeId, GraphSubgraphId)> {
792 // Check none are already in subgraphs
793 for &node_id in node_ids.iter() {
794 if let Some(&old_sg_id) = self.node_subgraph.get(node_id) {
795 return Err((node_id, old_sg_id));
796 }
797 }
798 let subgraph_id = self.subgraph_nodes.insert_with_key(|sg_id| {
799 for &node_id in node_ids.iter() {
800 self.node_subgraph.insert(node_id, sg_id);
801 }
802 node_ids
803 });
804
805 Ok(subgraph_id)
806 }
807
808 /// Removes a node from its subgraph. Returns true if the node was in a subgraph.
809 pub fn remove_from_subgraph(&mut self, node_id: GraphNodeId) -> bool {
810 if let Some(old_sg_id) = self.node_subgraph.remove(node_id) {
811 self.subgraph_nodes[old_sg_id].retain(|&other_node_id| other_node_id != node_id);
812 true
813 } else {
814 false
815 }
816 }
817
818 /// Gets the delay type for a handoff node, if set.
819 pub fn handoff_delay_type(&self, node_id: GraphNodeId) -> Option<DelayType> {
820 self.handoff_delay_type.get(node_id).copied()
821 }
822
823 /// Sets the delay type for a handoff node.
824 pub fn set_handoff_delay_type(&mut self, node_id: GraphNodeId, delay_type: DelayType) {
825 self.handoff_delay_type.insert(node_id, delay_type);
826 }
827
828 /// Helper: finds the first index in `subgraph_nodes` where it transitions from pull to push.
829 fn find_pull_to_push_idx(&self, subgraph_nodes: &[GraphNodeId]) -> usize {
830 subgraph_nodes
831 .iter()
832 .position(|&node_id| {
833 self.node_color(node_id)
834 .is_some_and(|color| Color::Pull != color)
835 })
836 .unwrap_or(subgraph_nodes.len())
837 }
838}
839
840/// Display/output methods.
841impl DfirGraph {
842 /// Helper to generate a deterministic `Ident` for the given node.
843 fn node_as_ident(&self, node_id: GraphNodeId, is_pred: bool) -> Ident {
844 let name = match &self.nodes[node_id] {
845 GraphNode::Operator(_) => format!("op_{:?}", node_id.data()),
846 GraphNode::Handoff {
847 kind: HandoffKind::Vec,
848 ..
849 } => format!(
850 "hoff_{:?}_{}",
851 node_id.data(),
852 if is_pred { "recv" } else { "send" }
853 ),
854 GraphNode::Handoff {
855 kind: HandoffKind::Singleton | HandoffKind::Optional,
856 ..
857 } => format!(
858 "singleton_{:?}_{}",
859 node_id.data(),
860 if is_pred { "recv" } else { "send" }
861 ),
862 GraphNode::ModuleBoundary { .. } => panic!(),
863 };
864 let span = match (is_pred, &self.nodes[node_id]) {
865 (_, GraphNode::Operator(operator)) => operator.span(),
866 (true, &GraphNode::Handoff { src_span, .. }) => src_span,
867 (false, &GraphNode::Handoff { dst_span, .. }) => dst_span,
868 (_, GraphNode::ModuleBoundary { .. }) => panic!(),
869 };
870 Ident::new(&name, span)
871 }
872
873 /// Helper to generate the main buffer `Ident` for a handoff node.
874 fn hoff_buf_ident(&self, hoff_id: GraphNodeId, span: Span) -> Ident {
875 Ident::new(&format!("hoff_{:?}_buf", hoff_id.data()), span)
876 }
877
878 /// Helper to generate the back (double-buffer) `Ident` for a handoff node.
879 fn hoff_back_ident(&self, hoff_id: GraphNodeId, span: Span) -> Ident {
880 Ident::new(&format!("hoff_{:?}_back", hoff_id.data()), span)
881 }
882
883 /// Resolve the handoff references via [`Self::node_handoff_references`] for the given `node_id`.
884 /// Returns token streams for each reference:
885 /// - For `HandoffKind::Singleton`: `buf.as_ref().unwrap()` (shared, `&T`) or
886 /// `buf.as_mut().unwrap()` (mutable, `&mut T`)
887 /// - For `HandoffKind::Optional`: `&buf` (shared, `&Option<T>`) or
888 /// `&mut buf` (mutable, `&mut Option<T>`)
889 /// - For `HandoffKind::Vec`: `&buf` (shared, `&Vec<T>`) or
890 /// `&mut buf` (mutable, `&mut Vec<T>`)
891 fn helper_resolve_singletons(&self, node_id: GraphNodeId, span: Span) -> Vec<TokenStream> {
892 self.node_handoff_references(node_id)
893 .iter()
894 .map(|resolved_ref| {
895 // TODO(mingwei): this `expect` should be caught in error checking
896 let ref_node_id = resolved_ref
897 .node_id
898 .expect("Expected singleton to be resolved but was not, this is a bug.");
899 let is_mut = resolved_ref.is_mut;
900 match self.node(ref_node_id) {
901 GraphNode::Handoff {
902 kind: HandoffKind::Singleton,
903 ..
904 } => {
905 let buf_ident = self.hoff_buf_ident(ref_node_id, span);
906 if is_mut {
907 quote_spanned! {span=> #buf_ident.as_mut().unwrap() }
908 } else {
909 quote_spanned! {span=> #buf_ident.as_ref().unwrap() }
910 }
911 }
912 GraphNode::Handoff {
913 kind: HandoffKind::Optional | HandoffKind::Vec,
914 ..
915 } => {
916 let buf_ident = self.hoff_buf_ident(ref_node_id, span);
917 if is_mut {
918 quote_spanned! {span=> &mut #buf_ident }
919 } else {
920 quote_spanned! {span=> &#buf_ident }
921 }
922 }
923 _ => {
924 unreachable!("Only handoff nodes should be reachable as handoff references")
925 }
926 }
927 })
928 .collect::<Vec<_>>()
929 }
930
931 /// Returns each subgraph's receive and send handoffs.
932 /// `Map<GraphSubgraphId, (recv handoffs, send handoffs)>`
933 fn helper_collect_subgraph_handoffs(
934 &self,
935 ) -> SecondaryMap<GraphSubgraphId, (Vec<GraphNodeId>, Vec<GraphNodeId>)> {
936 // Get data on handoff src and dst subgraphs.
937 let mut subgraph_handoffs: SecondaryMap<
938 GraphSubgraphId,
939 (Vec<GraphNodeId>, Vec<GraphNodeId>),
940 > = self
941 .subgraph_nodes
942 .keys()
943 .map(|k| (k, Default::default()))
944 .collect();
945
946 // For each handoff/singleton node, add it to the `send`/`recv` lists for the corresponding subgraphs.
947 for (hoff_id, hoff) in self.nodes() {
948 if !matches!(hoff, GraphNode::Handoff { .. }) {
949 continue;
950 }
951 // Receivers from the handoff. (Should really only be one).
952 for (_edge, succ_id) in self.node_successors(hoff_id) {
953 let succ_sg = self
954 .node_subgraph(succ_id)
955 .expect("bug: successor not in subgraph, may be a doubled/adjacent handoff");
956 subgraph_handoffs[succ_sg].0.push(hoff_id);
957 }
958 // Senders into the handoff. (Should really only be one).
959 for (_edge, pred_id) in self.node_predecessors(hoff_id) {
960 let pred_sg = self
961 .node_subgraph(pred_id)
962 .expect("bug: predecessor not in subgraph, may be a doubled/adjacent handoff");
963 subgraph_handoffs[pred_sg].1.push(hoff_id);
964 }
965 }
966
967 subgraph_handoffs
968 }
969
970 /// Compute the output handoffs exiting each loop (sender inside, receiver outside).
971 /// Returns a map from loop ID to the list of handoff node IDs that exit that loop.
972 fn helper_loop_output_handoffs(&self) -> SecondaryMap<GraphLoopId, Vec<GraphNodeId>> {
973 let mut loop_hoffs_out = SecondaryMap::<GraphLoopId, Vec<GraphNodeId>>::new();
974
975 for (hoff_id, hoff) in self.nodes() {
976 if !matches!(hoff, GraphNode::Handoff { .. }) {
977 continue;
978 }
979
980 let loop_pred = self
981 .node_predecessors(hoff_id)
982 .next()
983 .and_then(|(_, pred)| self.node_loop(pred));
984 let loop_succ = self
985 .node_successors(hoff_id)
986 .next()
987 .and_then(|(_, succ)| self.node_loop(succ));
988
989 if let Some(loop_pred) = loop_pred
990 && loop_succ == self.loop_parent(loop_pred)
991 {
992 // Pred is inside a child loop, succ is in the parent/outer.
993 loop_hoffs_out
994 .entry(loop_pred)
995 .expect("loop removed")
996 .or_default()
997 .push(hoff_id);
998 }
999 }
1000
1001 loop_hoffs_out
1002 }
1003
1004 /// Returns true if `node_loop` is `loop_id` or a (transitive) child of `loop_id`.
1005 fn is_inside_loop(&self, node_loop: Option<GraphLoopId>, loop_id: GraphLoopId) -> bool {
1006 let mut current = node_loop;
1007 while let Some(l) = current {
1008 if l == loop_id {
1009 return true;
1010 }
1011 current = self.loop_parent(l);
1012 }
1013 false
1014 }
1015
1016 /// Emit a loop gate: wraps `child_body` in the appropriate control structure
1017 /// and appends the result + swap code to `output`.
1018 ///
1019 /// - **Root-level loops** (no parent) are fused with the tick: they emit an `if`
1020 /// so the body runs at most once per tick when their entry condition is met.
1021 /// - **Nested loops** (have a parent loop) emit a `while` so they can iterate
1022 /// until fixpoint (driven by `defer_tick` back-edges).
1023 /// - If there are no gate checks, the body is emitted unconditionally.
1024 fn emit_loop_gate(
1025 &self,
1026 loop_id: GraphLoopId,
1027 child_body: TokenStream,
1028 loop_input_handoffs: &SecondaryMap<GraphLoopId, Vec<GraphNodeId>>,
1029 back_edge_hoffs_and_lazyness: &SparseSecondaryMap<GraphNodeId, bool>,
1030 loop_swap_code: &std::collections::HashMap<GraphLoopId, Vec<TokenStream>>,
1031 output: &mut TokenStream,
1032 ) {
1033 // Get swap code for this loop's defer_tick handoffs.
1034 let swap_code = loop_swap_code
1035 .get(&loop_id)
1036 .map(|v| v.as_slice())
1037 .unwrap_or(&[]);
1038
1039 // Root-level loops are fused with the tick: emit `if` instead of `while`.
1040 let is_root_loop = self.loop_parent(loop_id).is_none();
1041
1042 // Build the gate condition from entry handoffs (excluding lazy windowing operators).
1043 let entry_handoffs = loop_input_handoffs.get(loop_id).expect("loop missing");
1044 let mut gate_checks: Vec<TokenStream> = entry_handoffs
1045 .iter()
1046 .filter(|&&hoff_id| {
1047 // Check if the successor (windowing operator) is lazy or retaining.
1048 // If so, exclude from the gate — it doesn't trigger the loop.
1049 let is_lazy = self
1050 .node_successors(hoff_id)
1051 .next()
1052 .and_then(|(_, succ)| self.node_op_inst(succ))
1053 .is_some_and(|op_inst| {
1054 matches!(
1055 op_inst.op_constraints.flo_type,
1056 Some(FloType::WindowingLazy | FloType::WindowingRetain)
1057 )
1058 });
1059 !is_lazy
1060 })
1061 .map(|&hoff_id| {
1062 let span = self.node(hoff_id).span();
1063 let buf_ident = self.hoff_buf_ident(hoff_id, span);
1064 if back_edge_hoffs_and_lazyness.contains_key(hoff_id) {
1065 let back_ident = self.hoff_back_ident(hoff_id, span);
1066 quote_spanned! {span=> !#back_ident.is_empty() }
1067 } else {
1068 quote_spanned! {span=> !#buf_ident.is_empty() }
1069 }
1070 })
1071 .collect();
1072
1073 // Non-lazy defer_tick back-buffers also contribute to the gate (nested loops only).
1074 if !is_root_loop {
1075 for (hoff_id, hoff) in self.nodes() {
1076 if !matches!(hoff, GraphNode::Handoff { .. }) {
1077 continue;
1078 }
1079 let Some(delay_type) = self.handoff_delay_type(hoff_id) else {
1080 continue;
1081 };
1082 if delay_type != DelayType::Loop {
1083 continue;
1084 }
1085 // Check this handoff belongs to loop_id.
1086 let hoff_loop = self
1087 .node_successors(hoff_id)
1088 .next()
1089 .and_then(|(_, succ)| self.node_subgraph(succ))
1090 .and_then(|sg| self.subgraph_loop(sg));
1091 if hoff_loop != Some(loop_id) {
1092 continue;
1093 }
1094 let span = self.node(hoff_id).span();
1095 let back_ident = self.hoff_back_ident(hoff_id, span);
1096 gate_checks.push(quote_spanned! {span=> !#back_ident.is_empty() });
1097 }
1098 }
1099
1100 // For root-level loops: non-lazy defer_tick back-buffers also contribute to the gate.
1101 // This ensures the loop fires on the next tick when data was deferred via defer_tick.
1102 if is_root_loop {
1103 for (hoff_id, hoff) in self.nodes() {
1104 if !matches!(hoff, GraphNode::Handoff { .. }) {
1105 continue;
1106 }
1107 let Some(delay_type) = self.handoff_delay_type(hoff_id) else {
1108 continue;
1109 };
1110 if delay_type != DelayType::Tick {
1111 continue;
1112 }
1113 // Check this handoff's consumer is inside this root-level loop.
1114 let hoff_loop = self
1115 .node_successors(hoff_id)
1116 .next()
1117 .and_then(|(_, succ)| self.node_subgraph(succ))
1118 .and_then(|sg| self.subgraph_loop(sg));
1119 if hoff_loop != Some(loop_id) {
1120 continue;
1121 }
1122 let span = self.node(hoff_id).span();
1123 let back_ident = self.hoff_back_ident(hoff_id, span);
1124 gate_checks.push(quote_spanned! {span=> !#back_ident.is_empty() });
1125 }
1126 }
1127
1128 // An eager windowing operator (`batch_eager()`) forces the loop to fire unconditionally,
1129 // even when its windowed input is empty. It is only valid at the entry of a root-level
1130 // loop (disallowed in nested loops during validation, since forcing a nested loop to
1131 // always fire would prevent its fixpoint iteration from terminating).
1132 let has_eager = entry_handoffs.iter().any(|&hoff_id| {
1133 self.node_successors(hoff_id)
1134 .next()
1135 .and_then(|(_, succ)| self.node_op_inst(succ))
1136 .is_some_and(|op_inst| {
1137 op_inst.op_constraints.flo_type == Some(FloType::WindowingEager)
1138 })
1139 });
1140
1141 if has_eager && is_root_loop {
1142 // Eager entry: always run the loop body (gate forced true).
1143 output.extend(child_body);
1144 output.extend(quote! { #( #swap_code )* });
1145 } else if gate_checks.is_empty() {
1146 // No entry handoffs — always run.
1147 output.extend(child_body);
1148 output.extend(quote! { #( #swap_code )* });
1149 } else if is_root_loop {
1150 // Root-level loop: fused with tick, fire at most once.
1151 output.extend(quote! {
1152 #[allow(clippy::nonminimal_bool, reason = "codegen")]
1153 if false #( || #gate_checks )* {
1154 #child_body
1155 #( #swap_code )*
1156 }
1157 });
1158 } else {
1159 // Nested loop: iterate until fixpoint.
1160 output.extend(quote! {
1161 #[allow(clippy::nonminimal_bool, reason = "codegen")]
1162 while false #( || #gate_checks )* {
1163 #child_body
1164 #( #swap_code )*
1165 }
1166 });
1167 }
1168 }
1169
1170 /// Compute the input handoffs into each loop (predecessor outside, successor inside).
1171 fn helper_loop_input_handoffs(&self) -> SecondaryMap<GraphLoopId, Vec<GraphNodeId>> {
1172 let mut loop_hoffs_inn = SecondaryMap::<GraphLoopId, Vec<GraphNodeId>>::new();
1173
1174 // Check each handoff node.
1175 for (hoff_id, hoff) in self.nodes() {
1176 if !matches!(hoff, GraphNode::Handoff { .. }) {
1177 continue;
1178 }
1179
1180 // Get the loop context of the predecessor and successor.
1181 let loop_pred = self
1182 .node_predecessors(hoff_id)
1183 .next()
1184 .and_then(|(_, pred)| self.node_loop(pred));
1185 let loop_succ = self
1186 .node_successors(hoff_id)
1187 .next()
1188 .and_then(|(_, succ)| self.node_loop(succ));
1189
1190 if let Some(loop_succ) = loop_succ
1191 && loop_pred == self.loop_parent(loop_succ)
1192 {
1193 // Pred is parent/outer loop of succ.
1194 loop_hoffs_inn
1195 .entry(loop_succ)
1196 .expect("loop removed")
1197 .or_default()
1198 .push(hoff_id);
1199 }
1200 }
1201
1202 loop_hoffs_inn
1203 }
1204
1205 /// Emit this graph as runnable Rust source code tokens that execute inline.
1206 /// Generates a flat `async move |df: &mut Context|` closure where subgraph
1207 /// blocks are inlined in topological order, using local `Vec<T>` buffers
1208 /// instead of runtime handoffs. Each call to the closure runs one tick.
1209 ///
1210 /// The generated code block evaluates to a `Dfir` instance wrapping the
1211 /// closure. Operator prologues run at construction time on the `Context`
1212 /// before it is moved into `Dfir::new`. `Dfir` provides the `Context`
1213 /// to the closure on each tick run.
1214 ///
1215 /// Uses the default [`AsCodeOptions`] (aside from `include_type_guards`), so runtime metrics
1216 /// tracking is *not* included; use [`Self::as_code_with_options`] to opt in via
1217 /// [`AsCodeOptions::include_metrics_tracking`].
1218 ///
1219 /// # Errors
1220 ///
1221 /// Returns all diagnostics as `Err(diagnostics)` if any are errors
1222 /// (leaving `&mut diagnostics` empty).
1223 pub fn as_code(
1224 &self,
1225 root: &TokenStream,
1226 include_type_guards: bool,
1227 prefix: TokenStream,
1228 diagnostics: &mut Diagnostics,
1229 ) -> Result<TokenStream, Diagnostics> {
1230 self.as_code_with_options(
1231 root,
1232 &AsCodeOptions {
1233 exclude_type_guards: !include_type_guards,
1234 ..Default::default()
1235 },
1236 prefix,
1237 diagnostics,
1238 )
1239 }
1240
1241 /// Like [`Self::as_code`] but with the full set of [`AsCodeOptions`].
1242 ///
1243 /// The simulator calls `Dfir::new()` on each iteration, and as a part of that
1244 /// it does parsing of the metagraph and diagnostics blob. One of them causes spans to get allocated,
1245 /// each time a span is allocated, some threadlocal u32 is being incremented, and, on a long simulator run,
1246 /// the u32 overflows and panics.
1247 pub fn as_code_with_options(
1248 &self,
1249 root: &TokenStream,
1250 options: &AsCodeOptions,
1251 prefix: TokenStream,
1252 diagnostics: &mut Diagnostics,
1253 ) -> Result<TokenStream, Diagnostics> {
1254 let df = Ident::new(GRAPH, Span::call_site());
1255 let context = Ident::new(CONTEXT, Span::call_site());
1256 // Tick-local bump-allocated Vec handoff declarations (inside the tick closure).
1257 let bump_ident = Ident::new("__dfir_bump", Span::call_site());
1258
1259 // 1. Collect all handoff nodes.
1260 let handoff_nodes = self
1261 .nodes
1262 .iter()
1263 .filter_map(|(node_id, node)| match node {
1264 &GraphNode::Handoff {
1265 kind,
1266 src_span,
1267 dst_span,
1268 } => Some((node_id, kind, (src_span, dst_span))),
1269 GraphNode::Operator(_) => None,
1270 GraphNode::ModuleBoundary { .. } => panic!(),
1271 })
1272 .collect::<Vec<_>>();
1273
1274 // Determine which handoff nodes are tick-boundary (defer_tick) back-edges.
1275 // These must remain as captured Vec<T> since they persist across ticks.
1276 // All other Vec handoffs will be bump-allocated (tick-local).
1277 let back_edge_hoffs_and_lazyness = handoff_nodes
1278 .iter()
1279 .map(|&(node_id, _, _)| node_id)
1280 .filter_map(|node_id| {
1281 let delay_type = self.handoff_delay_type(node_id)?;
1282 Some((
1283 node_id,
1284 matches!(delay_type, DelayType::TickLazy | DelayType::LoopLazy),
1285 ))
1286 })
1287 .collect::<SparseSecondaryMap<_, _>>();
1288
1289 // Determine which handoff nodes feed a retaining windowing operator
1290 // (`FloType::WindowingRetain`: `snapshot()`, `snapshot_keyed()`, `snapshot_prefix()`).
1291 // Like defer_tick back-edges, these buffers are declared outside the tick closure so that
1292 // retained state persists across ticks. Unlike other handoffs they are never cleared or
1293 // consumed: the loop reads clones out of them each time it fires. The shape of the
1294 // retained state depends on the operator — see `RetainKind`.
1295 let retain_hoffs = handoff_nodes
1296 .iter()
1297 .map(|&(node_id, _, _)| node_id)
1298 .filter_map(|node_id| {
1299 let op_inst = self
1300 .node_successors(node_id)
1301 .next()
1302 .and_then(|(_, succ)| self.node_op_inst(succ))?;
1303 if op_inst.op_constraints.flo_type != Some(FloType::WindowingRetain) {
1304 return None;
1305 }
1306 let retain_kind = if op_inst.op_constraints.name == SNAPSHOT_KEYED.name {
1307 RetainKind::Keyed
1308 } else if op_inst.op_constraints.name == SNAPSHOT_PREFIX.name {
1309 RetainKind::Prefix
1310 } else {
1311 RetainKind::Cell
1312 };
1313 Some((node_id, retain_kind))
1314 })
1315 .collect::<BTreeMap<_, _>>();
1316
1317 // Declarations for retaining windowing handoff state, emitted outside the tick closure.
1318 let retain_buf_decls = handoff_nodes
1319 .iter()
1320 .filter_map(|&(hoff_id, kind, (src_span, dst_span))| {
1321 let retain_kind = *retain_hoffs.get(&hoff_id)?;
1322 // The graph-level kind is `Vec` (like all loop-entry handoffs), but codegen
1323 // special-cases retain handoffs with the storage below.
1324 assert_eq!(
1325 HandoffKind::Vec,
1326 kind,
1327 "retaining windowing (`snapshot*()`) handoffs must be `Vec`-kind"
1328 );
1329 let span = src_span.join(dst_span).unwrap_or(src_span);
1330 let buf_ident = self.hoff_buf_ident(hoff_id, span);
1331 Some(match retain_kind {
1332 RetainKind::Cell => quote! {
1333 let mut #buf_ident = ::std::option::Option::None;
1334 },
1335 RetainKind::Keyed => quote! {
1336 let mut #buf_ident = #root::rustc_hash::FxHashMap::default();
1337 },
1338 RetainKind::Prefix => quote! {
1339 let mut #buf_ident = ::std::vec::Vec::new();
1340 },
1341 })
1342 })
1343 .collect::<Vec<_>>();
1344
1345 // Back buffer idents, buf idents, and if they are lazy.
1346 let back_buffer_idents_laziness = handoff_nodes
1347 .iter()
1348 .filter_map(|&(hoff_id, _kind, (src_span, dst_span))| {
1349 back_edge_hoffs_and_lazyness.get(hoff_id).map(|&is_lazy| {
1350 let span = src_span.join(dst_span).unwrap_or(src_span);
1351 let back_ident = self.hoff_back_ident(hoff_id, span);
1352 let buf_ident = self.hoff_buf_ident(hoff_id, span);
1353 (back_ident, buf_ident, is_lazy)
1354 })
1355 })
1356 .collect::<Vec<_>>();
1357
1358 // Generate swap code for tick-boundary (defer_tick / defer_tick_lazy) handoffs.
1359 // At the end of each tick, swap the regular buffer and back buffer so the
1360 // consumer reads last tick's data from the back buffer.
1361 // Only tick-level swaps go here; loop-level swaps are emitted inside the loop gate.
1362 // IMPORTANT: For defer_tick handoffs whose consumer is inside a root-level loop,
1363 // the swap is emitted inside the `if` gate (via loop_swap_code), not at tick level.
1364 let back_edge_swap_code = handoff_nodes
1365 .iter()
1366 .filter(|&&(node_id, _kind, _)| {
1367 self.handoff_delay_type(node_id)
1368 .is_some_and(|dt| matches!(dt, DelayType::Tick | DelayType::TickLazy))
1369 })
1370 .filter(|&&(hoff_id, _kind, _)| {
1371 // Exclude handoffs whose consumer is inside a root-level loop.
1372 // Those get their swap emitted inside the loop gate.
1373 let consumer_loop = self
1374 .node_successors(hoff_id)
1375 .next()
1376 .and_then(|(_, succ)| self.node_subgraph(succ))
1377 .and_then(|sg| self.subgraph_loop(sg));
1378 if let Some(loop_id) = consumer_loop {
1379 // If it's a root-level loop, don't include in tick-level swap.
1380 self.loop_parent(loop_id).is_some()
1381 } else {
1382 // No loop context: emit at tick level (original behavior).
1383 true
1384 }
1385 })
1386 .map(|&(hoff_id, _kind, _)| {
1387 let span = self.nodes[hoff_id].span();
1388 let buf_ident = self.hoff_buf_ident(hoff_id, span);
1389 let back_ident = self.hoff_back_ident(hoff_id, span);
1390 quote_spanned! {span=>
1391 ::std::mem::swap(&mut #buf_ident, &mut #back_ident);
1392 }
1393 })
1394 .collect::<Vec<_>>();
1395
1396 // Collect per-loop swap code for defer_tick / defer_tick_lazy handoffs.
1397 // AND defer_tick / defer_tick_lazy handoffs inside root-level loops.
1398 // Keyed by the loop ID of the consumer (successor) of the handoff.
1399 let mut loop_swap_code: std::collections::HashMap<GraphLoopId, Vec<TokenStream>> =
1400 std::collections::HashMap::new();
1401 for &(hoff_id, _kind, _) in handoff_nodes.iter() {
1402 let Some(delay_type) = self.handoff_delay_type(hoff_id) else {
1403 continue;
1404 };
1405 // Find the loop this handoff belongs to (from its consumer's loop context).
1406 let loop_id = self
1407 .node_successors(hoff_id)
1408 .next()
1409 .and_then(|(_, succ)| self.node_subgraph(succ))
1410 .and_then(|sg| self.subgraph_loop(sg));
1411 let Some(loop_id) = loop_id else {
1412 continue;
1413 };
1414 let include = match delay_type {
1415 DelayType::Loop | DelayType::LoopLazy => true,
1416 DelayType::Tick | DelayType::TickLazy => {
1417 // Only include in loop swap if this is a root-level loop.
1418 self.loop_parent(loop_id).is_none()
1419 }
1420 };
1421 if !include {
1422 continue;
1423 }
1424 let span = self.nodes[hoff_id].span();
1425 let buf_ident = self.hoff_buf_ident(hoff_id, span);
1426 let back_ident = self.hoff_back_ident(hoff_id, span);
1427 loop_swap_code
1428 .entry(loop_id)
1429 .or_default()
1430 .push(quote_spanned! {span=>
1431 ::std::mem::swap(&mut #buf_ident, &mut #back_ident);
1432 });
1433 }
1434
1435 // 2. Collect per-subgraph recv & send handoffs.
1436 let subgraph_handoffs = self.helper_collect_subgraph_handoffs();
1437
1438 // 3. Use pre-computed subgraph topological order.
1439 let all_subgraphs: Vec<_> = self
1440 .subgraph_toposort()
1441 .iter()
1442 .map(|&sg_id| (sg_id, self.subgraph(sg_id)))
1443 .collect();
1444
1445 // TODO(mingwei): If a handoff has no pipe consumers we should drop it as soon as possible, after all reference
1446 // consumers. Right now we just let these handoffs die at the end of the tick.
1447
1448 let mut op_prologue_code = Vec::new();
1449 let mut op_tick_end_code = Vec::new();
1450
1451 // Stack-based hierarchical code generation.
1452 // Each entry is (loop_id, body_tokens) for an open loop context.
1453 // The "current output" is always the innermost open context (or root).
1454 let mut loop_stack: Vec<(GraphLoopId, TokenStream)> = Vec::new();
1455 let mut current_output = TokenStream::new();
1456
1457 // Pre-compute loop gate data.
1458 let loop_input_handoffs = self.helper_loop_input_handoffs();
1459 let loop_output_handoffs = self.helper_loop_output_handoffs();
1460
1461 {
1462 for &(subgraph_id, subgraph_nodes) in all_subgraphs.iter() {
1463 let sg_loop = self.subgraph_loop(subgraph_id);
1464
1465 // Transition loop contexts: close loops we've exited, open loops we've entered.
1466 // Close loops until we're at the right level.
1467 while let Some(&(top_loop, _)) = loop_stack.last() {
1468 if sg_loop == Some(top_loop) || self.is_inside_loop(sg_loop, top_loop) {
1469 break;
1470 }
1471 // Pop: wrap the body in a loop gate and append to parent.
1472 let (closed_loop, child_body) = loop_stack.pop().unwrap();
1473 let target = if let Some((_, parent_body)) = loop_stack.last_mut() {
1474 parent_body
1475 } else {
1476 &mut current_output
1477 };
1478 self.emit_loop_gate(
1479 closed_loop,
1480 child_body,
1481 &loop_input_handoffs,
1482 &back_edge_hoffs_and_lazyness,
1483 &loop_swap_code,
1484 target,
1485 );
1486 }
1487
1488 // Open new loops if we've descended.
1489 if let Some(target_loop) = sg_loop
1490 && loop_stack.last().map(|&(l, _)| l) != Some(target_loop)
1491 {
1492 // Find the path of loops to open (from outermost to target).
1493 let mut path = Vec::new();
1494 let mut cur = Some(target_loop);
1495 while let Some(l) = cur {
1496 if loop_stack.last().map(|&(top, _)| top) == Some(l) {
1497 break;
1498 }
1499 path.push(l);
1500 cur = self.loop_parent(l);
1501 }
1502 // Push in outermost-first order, emitting exit-handoff declarations
1503 // to the parent level before the while loop.
1504 for &loop_id in path.iter().rev() {
1505 // Declare exit-handoff buffers at the current (parent) level.
1506 if let Some(exit_hoffs) = loop_output_handoffs.get(loop_id) {
1507 let exit_hoff_decls = exit_hoffs.iter().map(|&hoff_id| {
1508 let span = self.nodes[hoff_id].span();
1509 let buf_ident = self.hoff_buf_ident(hoff_id, span);
1510 let GraphNode::Handoff { kind, .. } = self.node(hoff_id) else {
1511 panic!()
1512 };
1513 match kind {
1514 HandoffKind::Vec => quote_spanned! {span=>
1515 let mut #buf_ident = #root::bumpalo::collections::Vec::new_in(&#bump_ident);
1516 },
1517 HandoffKind::Singleton | HandoffKind::Optional => quote_spanned! {span=>
1518 let mut #buf_ident = ::std::option::Option::None;
1519 },
1520 }
1521 });
1522 let target = if let Some((_, body)) = loop_stack.last_mut() {
1523 body
1524 } else {
1525 &mut current_output
1526 };
1527 target.extend(quote! { #( #exit_hoff_decls )* });
1528 }
1529 loop_stack.push((loop_id, TokenStream::new()));
1530 }
1531 }
1532 let sg_metrics_ffi = subgraph_id.data().as_ffi();
1533 let (recv_hoffs, send_hoffs) = &subgraph_handoffs[subgraph_id];
1534
1535 // Generate buffer ident helpers for this subgraph's handoffs.
1536 let recv_port_idents: Vec<Ident> = recv_hoffs
1537 .iter()
1538 .map(|&hoff_id| self.node_as_ident(hoff_id, true))
1539 .collect();
1540 let send_port_idents: Vec<Ident> = send_hoffs
1541 .iter()
1542 .map(|&hoff_id| self.node_as_ident(hoff_id, false))
1543 .collect();
1544
1545 // Map handoff node IDs to buffer idents.
1546 let recv_buf_idents: Vec<Ident> = recv_hoffs
1547 .iter()
1548 .map(|&hoff_id| self.hoff_buf_ident(hoff_id, self.nodes[hoff_id].span()))
1549 .collect();
1550 let send_buf_idents: Vec<Ident> = send_hoffs
1551 .iter()
1552 .map(|&hoff_id| self.hoff_buf_ident(hoff_id, self.nodes[hoff_id].span()))
1553 .collect();
1554
1555 // Handoff kinds
1556 let recv_kinds = recv_hoffs
1557 .iter()
1558 .map(|&hoff_id| {
1559 let GraphNode::Handoff { kind, .. } = self.node(hoff_id) else {
1560 panic!()
1561 };
1562 *kind
1563 })
1564 .collect::<Vec<_>>();
1565 let send_kinds = send_hoffs
1566 .iter()
1567 .map(|&hoff_id| {
1568 let GraphNode::Handoff { kind, .. } = self.node(hoff_id) else {
1569 panic!()
1570 };
1571 *kind
1572 })
1573 .collect::<Vec<_>>();
1574
1575 // Recv port code: drain from buffer into iterator, tracking if non-empty.
1576 // For back-edge (defer_tick) handoffs, drain from the back buffer instead.
1577 // Also update handoff metrics (measured at recv, not send — see graph.rs).
1578 let recv_port_code: Vec<TokenStream> = recv_port_idents
1579 .iter()
1580 .zip(recv_buf_idents.iter())
1581 .zip(recv_kinds.iter())
1582 .zip(recv_hoffs.iter())
1583 .map(|(((port_ident, buf_ident), &kind), &hoff_id)| {
1584 let hoff_ffi = hoff_id.data().as_ffi();
1585 // Use call_site span for internal identifiers to avoid
1586 // hygiene issues when invoked through declarative macros
1587 // (e.g. dfir_expect_warnings!). TODO(#2781): define these once.
1588 let work_done = Ident::new("__dfir_work_done", Span::call_site());
1589 let metrics = Ident::new("__dfir_metrics", Span::call_site());
1590
1591 // Compute len and drain expressions based on handoff kind.
1592 let (len_expr, drain_expr) = match retain_hoffs.get(&hoff_id) {
1593 Some(RetainKind::Keyed) => {
1594 // Retaining keyed windowing (`snapshot_keyed()`) handoffs are a
1595 // persistent keyed map, declared outside the tick closure. Like
1596 // `snapshot()`, it is NOT consumed when the loop fires: every firing
1597 // observes a clone of every current entry. Requires `K: Clone, V: Clone`.
1598 (
1599 quote! { #buf_ident.len() },
1600 quote! {
1601 {
1602 #[allow(clippy::disallowed_methods, reason = "FxHasher is deterministic")]
1603 let __snapshot_keyed_entries = #buf_ident.iter();
1604 #root::dfir_pipes::pull::iter(
1605 __snapshot_keyed_entries.map(
1606 #[allow(suspicious_double_ref_op, clippy::clone_on_copy)]
1607 |(k, v)| (::std::clone::Clone::clone(k), ::std::clone::Clone::clone(v))
1608 )
1609 )
1610 }
1611 },
1612 )
1613 }
1614 Some(RetainKind::Prefix) => {
1615 // Retaining prefix windowing (`snapshot_prefix()`) handoffs are a
1616 // persistent `Vec<T>` of every element received so far, declared
1617 // outside the tick closure. NOT consumed when the loop fires: every
1618 // firing replays a clone of the whole prefix, in arrival order.
1619 // Requires `T: Clone`.
1620 (
1621 quote! { #buf_ident.len() },
1622 quote! { #root::dfir_pipes::pull::iter(#buf_ident.iter().cloned()) },
1623 )
1624 }
1625 Some(RetainKind::Cell) => {
1626 // Retaining windowing (`snapshot()`) handoffs are a single
1627 // last-write-wins `Option<T>` cell, declared outside the tick closure.
1628 // The cell is NOT consumed when the loop fires: it is a persistent
1629 // view of the latest value, so the loop observes it again on every
1630 // firing until a newer value replaces it. Requires `T: Clone`.
1631 (
1632 quote! { if #buf_ident.is_some() { 1usize } else { 0usize } },
1633 quote! { #root::dfir_pipes::pull::iter(::std::clone::Clone::clone(&#buf_ident).into_iter()) },
1634 )
1635 }
1636 None => match kind {
1637 HandoffKind::Singleton | HandoffKind::Optional => (
1638 quote! { if #buf_ident.is_some() { 1usize } else { 0usize } },
1639 quote! { #root::dfir_pipes::pull::iter(#buf_ident.take().into_iter()) },
1640 ),
1641 HandoffKind::Vec => {
1642 // Special asymmetric handling for defer tick handoffs, which are double-buffered.
1643 // The producer writes to the regular buffer; at end-of-tick the buffers are swapped,
1644 // so the consumer drains from the back buffer (here).
1645 let drain_ident = if back_edge_hoffs_and_lazyness.contains_key(hoff_id) {
1646 &self.hoff_back_ident(hoff_id, buf_ident.span())
1647 } else {
1648 buf_ident
1649 };
1650 (
1651 quote! { #drain_ident.len() },
1652 quote! { #root::dfir_pipes::pull::iter(#drain_ident.drain(..)) },
1653 )
1654 }
1655 },
1656 };
1657
1658 let track_hoff_metrics = options.include_metrics_tracking.then(|| {
1659 quote_spanned! {port_ident.span()=>
1660 let hoff_metrics = &#metrics.handoffs[
1661 #root::slotmap::KeyData::from_ffi(#hoff_ffi).into()
1662 ];
1663 #root::scheduled::metrics::MetricCell::add(&hoff_metrics.total_items_count, hoff_len);
1664 #root::scheduled::metrics::MetricCell::set(&hoff_metrics.curr_items_count, hoff_len);
1665 }
1666 });
1667
1668 quote_spanned! {port_ident.span()=>
1669 {
1670 let hoff_len = #len_expr;
1671 if hoff_len > 0 {
1672 #work_done = true;
1673 }
1674 #track_hoff_metrics
1675 }
1676 let #port_ident = #drain_expr;
1677 }
1678 })
1679 .collect();
1680
1681 // Send port code: push into buffer.
1682 let send_port_code: Vec<TokenStream> = send_port_idents
1683 .iter()
1684 .zip(send_buf_idents.iter())
1685 .zip(send_kinds.iter())
1686 .zip(send_hoffs.iter())
1687 .map(|(((port_ident, buf_ident), &kind), &hoff_id)| {
1688 match retain_hoffs.get(&hoff_id) {
1689 Some(RetainKind::Keyed) => {
1690 // Retaining keyed windowing (`snapshot_keyed()`) map: apply each
1691 // `(K, Option<V>)` update — `Some(v)` replaces the key's value (latest
1692 // write wins per key), `None` removes the key.
1693 return quote_spanned! {port_ident.span()=>
1694 let #port_ident = #root::dfir_pipes::push::for_each(|(__key, __update)| {
1695 match __update {
1696 ::std::option::Option::Some(__value) => {
1697 #buf_ident.insert(__key, __value);
1698 }
1699 ::std::option::Option::None => {
1700 #buf_ident.remove(&__key);
1701 }
1702 }
1703 });
1704 };
1705 }
1706 Some(RetainKind::Prefix) => {
1707 // Retaining prefix windowing (`snapshot_prefix()`) buffer: append
1708 // every item. Nothing is ever dropped or replaced.
1709 return quote_spanned! {port_ident.span()=>
1710 let #port_ident = #root::dfir_pipes::push::for_each(|__item| {
1711 #buf_ident.push(__item);
1712 });
1713 };
1714 }
1715 Some(RetainKind::Cell) => {
1716 // Retaining windowing (`snapshot()`) cell: last-write-wins. Each new
1717 // item replaces (and drops) any previously pending item, so at most
1718 // one value is retained no matter how many ticks pass before the
1719 // consuming loop fires.
1720 return quote_spanned! {port_ident.span()=>
1721 let #port_ident = #root::dfir_pipes::push::for_each(|__item| {
1722 #buf_ident = ::std::option::Option::Some(__item);
1723 });
1724 };
1725 }
1726 None => {}
1727 }
1728 match kind {
1729 HandoffKind::Singleton => {
1730 // Singleton slot: store exactly one item, panic on duplicate.
1731 quote_spanned! {port_ident.span()=>
1732 let #port_ident = #root::dfir_pipes::push::for_each(|__item| {
1733 if #buf_ident.replace(__item).is_some() {
1734 panic!("singleton() received more than one item");
1735 }
1736 });
1737 }
1738 }
1739 HandoffKind::Optional => {
1740 // Optional slot: store at most one item, panic on duplicate.
1741 quote_spanned! {port_ident.span()=>
1742 let #port_ident = #root::dfir_pipes::push::for_each(|__item| {
1743 if #buf_ident.replace(__item).is_some() {
1744 panic!("optional() received more than one item");
1745 }
1746 });
1747 }
1748 }
1749 HandoffKind::Vec => {
1750 quote_spanned! {port_ident.span()=>
1751 // TODO(mingwei): use `#root::dfir_pipes::push::vec_push`?
1752 let #port_ident = #root::dfir_pipes::push::for_each(|item| { #buf_ident.push(item); });
1753 }
1754 }
1755 }
1756 })
1757 .collect();
1758
1759 // All nodes in a subgraph should be in the same loop.
1760 let loop_id = self.node_loop(subgraph_nodes[0]);
1761
1762 let mut subgraph_op_iter_code = Vec::new();
1763 let mut subgraph_op_iter_after_code = Vec::new();
1764 {
1765 let pull_to_push_idx = self.find_pull_to_push_idx(subgraph_nodes);
1766
1767 let (pull_half, push_half) = subgraph_nodes.split_at(pull_to_push_idx);
1768 let nodes_iter = pull_half.iter().chain(push_half.iter().rev());
1769
1770 for (idx, &node_id) in nodes_iter.enumerate() {
1771 let node = &self.nodes[node_id];
1772 assert!(
1773 matches!(node, GraphNode::Operator(_)),
1774 "Handoffs are not part of subgraphs."
1775 );
1776 let op_inst = &self.operator_instances[node_id];
1777
1778 let op_span = node.span();
1779 let op_name = op_inst.op_constraints.name;
1780 // Use op's span for root. #root is expected to be correct, any errors should span back to the op gen.
1781 let root = change_spans(root.clone(), op_span);
1782 let op_constraints = OPERATORS
1783 .iter()
1784 .find(|op| op_name == op.name)
1785 .unwrap_or_else(|| panic!("Failed to find op: {}", op_name));
1786
1787 let ident = self.node_as_ident(node_id, false);
1788
1789 {
1790 // TODO clean this up.
1791 // Collect input arguments (predecessors).
1792 let mut input_edges = self
1793 .graph
1794 .predecessor_edges(node_id)
1795 .map(|edge_id| (self.edge_ports(edge_id).1, edge_id))
1796 .collect::<Vec<_>>();
1797 // Ensure sorted by port index.
1798 input_edges.sort();
1799
1800 let inputs = input_edges
1801 .iter()
1802 .map(|&(_port, edge_id)| {
1803 let (pred, _) = self.edge(edge_id);
1804 self.node_as_ident(pred, true)
1805 })
1806 .collect::<Vec<_>>();
1807
1808 // Collect output arguments (successors).
1809 let mut output_edges = self
1810 .graph
1811 .successor_edges(node_id)
1812 .map(|edge_id| (&self.ports[edge_id].0, edge_id))
1813 .collect::<Vec<_>>();
1814 // Ensure sorted by port index.
1815 output_edges.sort();
1816
1817 let outputs = output_edges
1818 .iter()
1819 .map(|&(_port, edge_id)| {
1820 let (_, succ) = self.edge(edge_id);
1821 self.node_as_ident(succ, false)
1822 })
1823 .collect::<Vec<_>>();
1824
1825 let is_pull = idx < pull_to_push_idx;
1826
1827 // There's a bit of dark magic hidden in `Span`s... you'd think it's just a `file:line:column`,
1828 // but it has one extra bit of info for _name resolution_, used for `Ident`s. `Span::call_site()`
1829 // has the (unhygienic) resolution we want, an ident is just solely determined by its string name,
1830 // which is what you'd expect out of unhygienic proc macros like this. Meanwhile, declarative macros
1831 // use `Span::mixed_site()` which is weird and I don't understand it. It turns out that if you call
1832 // the dfir syntax proc macro from _within_ a declarative macro then `op_span` will have the
1833 // bad `Span::mixed_site()` name resolution and cause "Cannot find value `df/context`" errors. So
1834 // we call `.resolved_at()` to fix resolution back to `Span::call_site()`. -Mingwei
1835 let df_local = &Ident::new(GRAPH, op_span.resolved_at(df.span()));
1836 let context = &Ident::new(CONTEXT, op_span.resolved_at(context.span()));
1837
1838 let singletons_resolved =
1839 self.helper_resolve_singletons(node_id, op_span);
1840
1841 let arguments = &process_singletons::postprocess_singletons(
1842 op_inst.arguments_raw.clone(),
1843 singletons_resolved,
1844 );
1845
1846 let source_tag = 'a: {
1847 if let Some(tag) = self.operator_tag.get(node_id).cloned() {
1848 break 'a tag;
1849 }
1850
1851 if proc_macro::is_available() {
1852 let op_span = op_span.unwrap();
1853 break 'a format!(
1854 "loc_{}_{}_{}_{}_{}",
1855 crate::pretty_span::make_source_path_relative(
1856 &op_span.file()
1857 )
1858 .display()
1859 .to_string()
1860 .replace(|x: char| !x.is_ascii_alphanumeric(), "_"),
1861 op_span.start().line(),
1862 op_span.start().column(),
1863 op_span.end().line(),
1864 op_span.end().column(),
1865 );
1866 }
1867
1868 format!(
1869 "loc_nopath_{}_{}_{}_{}",
1870 op_span.start().line,
1871 op_span.start().column,
1872 op_span.end().line,
1873 op_span.end().column
1874 )
1875 };
1876
1877 let work_fn = format_ident!(
1878 "{}__{}__{}",
1879 ident,
1880 op_name,
1881 source_tag,
1882 span = op_span
1883 );
1884 let work_fn_async = format_ident!("{}__async", work_fn, span = op_span);
1885
1886 let context_args = WriteContextArgs {
1887 root: &root,
1888 df_ident: df_local,
1889 context,
1890 subgraph_id,
1891 node_id,
1892 loop_id,
1893 op_span,
1894 op_tag: self.operator_tag.get(node_id).cloned(),
1895 work_fn: &work_fn,
1896 work_fn_async: &work_fn_async,
1897 ident: &ident,
1898 is_pull,
1899 inputs: &inputs,
1900 outputs: &outputs,
1901 op_name,
1902 op_inst,
1903 arguments,
1904 options,
1905 };
1906
1907 let write_result =
1908 (op_constraints.write_fn)(&context_args, diagnostics);
1909 let OperatorWriteOutput {
1910 write_prologue,
1911 write_iterator,
1912 write_iterator_after,
1913 write_tick_end,
1914 } = write_result.unwrap_or_else(|()| {
1915 assert!(
1916 diagnostics.has_error(),
1917 "Operator `{}` returned `Err` but emitted no diagnostics, this is a bug.",
1918 op_name,
1919 );
1920 OperatorWriteOutput {
1921 write_prologue: Default::default(),
1922 write_iterator: null_write_iterator_fn(&context_args),
1923 write_iterator_after: Default::default(),
1924 write_tick_end: Default::default(),
1925 }
1926 });
1927
1928 // The `work_fn` / `work_fn_async` thunks exist purely so that work done
1929 // by an operator outside of the pull/push pipeline (e.g. `fold`
1930 // accumulation) is attributed to a named frame in flamegraphs. Only emit
1931 // them if the operator's codegen actually references them, otherwise they
1932 // are dead code which just clutters the output.
1933 let op_outputs = [
1934 &write_prologue,
1935 &write_iterator,
1936 &write_iterator_after,
1937 &write_tick_end,
1938 ];
1939 let uses_ident = |ident: &Ident| {
1940 op_outputs
1941 .iter()
1942 .any(|tokens| tokens_contain_ident((*tokens).clone(), ident))
1943 };
1944
1945 if uses_ident(&work_fn) {
1946 op_prologue_code.push(syn::parse_quote! {
1947 #[allow(dead_code, non_snake_case, reason = "codegen")]
1948 #[inline(always)]
1949 fn #work_fn<T>(thunk: impl ::std::ops::FnOnce() -> T) -> T {
1950 thunk()
1951 }
1952 });
1953 }
1954 if uses_ident(&work_fn_async) {
1955 op_prologue_code.push(syn::parse_quote! {
1956 #[allow(dead_code, non_snake_case, reason = "codegen")]
1957 #[inline(always)]
1958 async fn #work_fn_async<T>(
1959 thunk: impl ::std::future::Future<Output = T>,
1960 ) -> T {
1961 thunk.await
1962 }
1963 });
1964 }
1965 op_prologue_code.push(write_prologue);
1966 op_tick_end_code.push(write_tick_end);
1967 subgraph_op_iter_code.push(write_iterator);
1968
1969 // The per-operator wrapper serves a dual purpose: it is the type guard,
1970 // and (since the wrapper's `pull`/`push` impls live inside a fn named
1971 // after the operator) it is also what gives streaming operators a named
1972 // frame in flamegraphs.
1973 if !options.exclude_type_guards || options.require_flame_attribution {
1974 let type_guard = if is_pull {
1975 quote_spanned! {op_span=>
1976 let #ident = {
1977 #[allow(non_snake_case)]
1978 #[inline(always)]
1979 pub fn #work_fn<Item, Input>(input: Input)
1980 -> impl #root::dfir_pipes::pull::Pull<Item = Item, Meta = (), CanPend = Input::CanPend, CanEnd = Input::CanEnd>
1981 where
1982 Input: #root::dfir_pipes::pull::Pull<Item = Item, Meta = ()>,
1983 {
1984 #root::pin_project_lite::pin_project! {
1985 #[repr(transparent)]
1986 struct Pull<Item, Input: #root::dfir_pipes::pull::Pull<Item = Item>> {
1987 #[pin]
1988 inner: Input
1989 }
1990 }
1991
1992 impl<Item, Input> #root::dfir_pipes::pull::Pull for Pull<Item, Input>
1993 where
1994 Input: #root::dfir_pipes::pull::Pull<Item = Item>,
1995 {
1996 type Ctx<'ctx> = Input::Ctx<'ctx>;
1997
1998 type Item = Item;
1999 type Meta = Input::Meta;
2000 type CanPend = Input::CanPend;
2001 type CanEnd = Input::CanEnd;
2002
2003 #[inline(always)]
2004 fn pull(
2005 self: ::std::pin::Pin<&mut Self>,
2006 ctx: &mut Self::Ctx<'_>,
2007 ) -> #root::dfir_pipes::pull::PullStep<Self::Item, Self::Meta, Self::CanPend, Self::CanEnd> {
2008 #root::dfir_pipes::pull::Pull::pull(self.project().inner, ctx)
2009 }
2010
2011 #[inline(always)]
2012 fn size_hint(&self) -> (usize, Option<usize>) {
2013 #root::dfir_pipes::pull::Pull::size_hint(&self.inner)
2014 }
2015 }
2016
2017 Pull {
2018 inner: input
2019 }
2020 }
2021 #work_fn::<_, _>( #ident )
2022 };
2023 }
2024 } else {
2025 quote_spanned! {op_span=>
2026 let #ident = {
2027 #[allow(non_snake_case)]
2028 #[inline(always)]
2029 pub fn #work_fn<Item, Psh>(psh: Psh) -> impl #root::dfir_pipes::push::Push<Item, (), CanPend = Psh::CanPend>
2030 where
2031 Psh: #root::dfir_pipes::push::Push<Item, ()>
2032 {
2033 #root::pin_project_lite::pin_project! {
2034 #[repr(transparent)]
2035 struct PushGuard<Psh> {
2036 #[pin]
2037 inner: Psh,
2038 }
2039 }
2040
2041 impl<Item, Psh> #root::dfir_pipes::push::Push<Item, ()> for PushGuard<Psh>
2042 where
2043 Psh: #root::dfir_pipes::push::Push<Item, ()>,
2044 {
2045 type Ctx<'ctx> = Psh::Ctx<'ctx>;
2046
2047 type CanPend = Psh::CanPend;
2048
2049 #[inline(always)]
2050 fn poll_ready(
2051 self: ::std::pin::Pin<&mut Self>,
2052 ctx: &mut Self::Ctx<'_>,
2053 ) -> #root::dfir_pipes::push::PushStep<Self::CanPend> {
2054 #root::dfir_pipes::push::Push::poll_ready(self.project().inner, ctx)
2055 }
2056
2057 #[inline(always)]
2058 fn start_send(
2059 self: ::std::pin::Pin<&mut Self>,
2060 item: Item,
2061 meta: (),
2062 ) {
2063 #root::dfir_pipes::push::Push::start_send(self.project().inner, item, meta)
2064 }
2065
2066 #[inline(always)]
2067 fn poll_finalize(
2068 self: ::std::pin::Pin<&mut Self>,
2069 ctx: &mut Self::Ctx<'_>,
2070 ) -> #root::dfir_pipes::push::PushStep<Self::CanPend> {
2071 #root::dfir_pipes::push::Push::poll_finalize(self.project().inner, ctx)
2072 }
2073
2074 #[inline(always)]
2075 fn size_hint(
2076 self: ::std::pin::Pin<&mut Self>,
2077 hint: (usize, Option<usize>),
2078 ) {
2079 #root::dfir_pipes::push::Push::size_hint(self.project().inner, hint)
2080 }
2081 }
2082
2083 PushGuard {
2084 inner: psh
2085 }
2086 }
2087 #work_fn( #ident )
2088 };
2089 }
2090 };
2091 subgraph_op_iter_code.push(type_guard);
2092 }
2093 subgraph_op_iter_after_code.push(write_iterator_after);
2094 }
2095 }
2096
2097 {
2098 // Determine pull and push halves of the `Pivot`.
2099 let pull_ident = if 0 < pull_to_push_idx {
2100 self.node_as_ident(subgraph_nodes[pull_to_push_idx - 1], false)
2101 } else {
2102 // Entire subgraph is push (with a single recv/pull handoff input).
2103 recv_port_idents[0].clone()
2104 };
2105
2106 #[rustfmt::skip]
2107 let push_ident = if let Some(&node_id) =
2108 subgraph_nodes.get(pull_to_push_idx)
2109 {
2110 self.node_as_ident(node_id, false)
2111 } else if 1 == send_port_idents.len() {
2112 // Entire subgraph is pull (with a single send/push handoff output).
2113 send_port_idents[0].clone()
2114 } else {
2115 diagnostics.push(Diagnostic::spanned(
2116 pull_ident.span(),
2117 Level::Error,
2118 "Degenerate subgraph detected, is there a disconnected `null()` or other degenerate pipeline somewhere?",
2119 ));
2120 continue;
2121 };
2122
2123 // Pivot span is combination of pull and push spans (or if not possible, just take the push).
2124 let pivot_span = pull_ident
2125 .span()
2126 .join(push_ident.span())
2127 .unwrap_or_else(|| push_ident.span());
2128 let root = change_spans(root.clone(), pivot_span);
2129 if options.exclude_type_guards {
2130 // `send_push` already carries the same `Item`/`Meta` bounds as the
2131 // guard function below, so call it directly.
2132 subgraph_op_iter_code.push(quote_spanned! {pivot_span=>
2133 #root::dfir_pipes::pull::Pull::send_push(#pull_ident, #push_ident).await;
2134 });
2135 } else {
2136 let pivot_fn_ident = Ident::new(
2137 &format!("pivot_run_sg_{:?}", subgraph_id.data()),
2138 pivot_span,
2139 );
2140 subgraph_op_iter_code.push(quote_spanned! {pivot_span=>
2141 #[inline(always)]
2142 fn #pivot_fn_ident<Pul, Psh, Item>(pull: Pul, push: Psh)
2143 -> impl ::std::future::Future<Output = ()>
2144 where
2145 Pul: #root::dfir_pipes::pull::Pull<Item = Item>,
2146 Psh: #root::dfir_pipes::push::Push<Item, Pul::Meta>,
2147 {
2148 #root::dfir_pipes::pull::Pull::send_push(pull, push)
2149 }
2150 (#pivot_fn_ident)(#pull_ident, #push_ident).await;
2151 });
2152 }
2153 }
2154 };
2155
2156 // Generate send-side curr_items_count updates (after subgraph runs).
2157 let send_metrics_code = if options.include_metrics_tracking {
2158 send_hoffs
2159 .iter()
2160 .zip(send_buf_idents.iter())
2161 .zip(send_kinds.iter())
2162 .map(|((&hoff_id, buf_ident), &kind)| {
2163 let hoff_ffi = hoff_id.data().as_ffi();
2164 let len_expr = match retain_hoffs.get(&hoff_id) {
2165 Some(RetainKind::Keyed | RetainKind::Prefix) => {
2166 // Retaining keyed map (`snapshot_keyed()`) or prefix buffer
2167 // (`snapshot_prefix()`).
2168 quote! { #buf_ident.len() }
2169 }
2170 Some(RetainKind::Cell) => {
2171 // Retaining windowing (`snapshot()`) single `Option<T>` cell.
2172 quote! { if #buf_ident.is_some() { 1 } else { 0 } }
2173 }
2174 None => match kind {
2175 HandoffKind::Singleton | HandoffKind::Optional => {
2176 quote! { if #buf_ident.is_some() { 1 } else { 0 } }
2177 }
2178 HandoffKind::Vec => {
2179 quote! { #buf_ident.len() }
2180 }
2181 },
2182 };
2183 quote! {
2184 #root::scheduled::metrics::MetricCell::set(
2185 &__dfir_metrics.handoffs[
2186 #root::slotmap::KeyData::from_ffi(#hoff_ffi).into()
2187 ].curr_items_count,
2188 #len_expr,
2189 );
2190 }
2191 })
2192 .collect::<Vec<_>>()
2193 } else {
2194 Vec::new()
2195 };
2196
2197 // Create the handoffs we are about to push to (send).
2198 // Exit handoffs (sender inside a loop, receiver in parent) are already declared
2199 // before the while loop, so skip them here.
2200 let send_hoff_make_code = send_buf_idents.iter()
2201 .zip(send_kinds.iter())
2202 .zip(send_hoffs.iter())
2203 .filter_map(|((buf_ident, &kind), &hoff_id)| {
2204 let span = buf_ident.span();
2205 if retain_hoffs.contains_key(&hoff_id) {
2206 // Retaining windowing (`snapshot*()`) state is declared outside the
2207 // tick closure and must NOT be re-declared or cleared: it persists
2208 // across ticks (and across loop firings).
2209 None
2210 } else if back_edge_hoffs_and_lazyness.contains_key(hoff_id) {
2211 // Defer_tick send buffers are declared outside the tick closure
2212 // as std::vec::Vec for O(1) swap. Just clear here.
2213 Some(quote_spanned! {span=>
2214 #buf_ident.clear();
2215 })
2216 } else {
2217 // Check if this is a loop-exit handoff: sender is in a loop,
2218 // receiver is in the parent (already declared outside the while loop).
2219 let receiver_loop = self
2220 .node_successors(hoff_id)
2221 .next()
2222 .and_then(|(_, succ)| self.node_loop(succ));
2223 let is_exit = if let Some(sender_loop) = sg_loop {
2224 receiver_loop == self.loop_parent(sender_loop)
2225 } else {
2226 false
2227 };
2228 if is_exit {
2229 // Exit handoff: buffer already declared at parent level.
2230 None
2231 } else {
2232 Some(match kind {
2233 HandoffKind::Vec => quote_spanned! {span=>
2234 let mut #buf_ident = #root::bumpalo::collections::Vec::new_in(&#bump_ident);
2235 },
2236 HandoffKind::Singleton | HandoffKind::Optional => quote_spanned! {span=>
2237 let mut #buf_ident = ::std::option::Option::None;
2238 },
2239 })
2240 }
2241 }
2242 })
2243 .collect::<Vec<_>>();
2244 // Drop the handoffs we just drained (recv).
2245 // TODO(mingwei): we could use `.into_iter()` instead of `.drain(..)` to consume the handoffs directly.
2246 // This only works for handoffs within the tick, though, not `defer_tick` handoffs.
2247 let recv_hoff_drop_code = recv_buf_idents
2248 .iter()
2249 .zip(recv_hoffs.iter())
2250 .filter(|&(_, &hoff_id)| {
2251 !back_edge_hoffs_and_lazyness.contains_key(hoff_id)
2252 && !retain_hoffs.contains_key(&hoff_id)
2253 })
2254 .map(|(buf_ident, _)| {
2255 let span = buf_ident.span();
2256 quote_spanned! {span=>
2257 let _ = #buf_ident;
2258 }
2259 });
2260
2261 // The subgraph body: set up ports, run the operators' pull/push pipeline.
2262 let sg_body = quote! {
2263 let #context = &#df;
2264 #( #recv_port_code )*
2265 #( #send_port_code )*
2266 #( #subgraph_op_iter_code )*
2267 #( #subgraph_op_iter_after_code )*
2268 };
2269
2270 let run_sg = if options.include_metrics_tracking {
2271 // When metrics are tracked, the subgraph body must be wrapped in an `async`
2272 // block so it can be individually instrumented (poll/idle durations).
2273 quote! {
2274 // Instrument w/ the subgraph metrics.
2275 let sg_metrics = &__dfir_metrics.subgraphs[
2276 #root::slotmap::KeyData::from_ffi(#sg_metrics_ffi).into()
2277 ];
2278 #root::scheduled::metrics::InstrumentSubgraph::new(
2279 async { #sg_body },
2280 sg_metrics,
2281 ).await;
2282 #root::scheduled::metrics::MetricCell::add(&sg_metrics.total_run_count, 1);
2283
2284 // Update send (output) handoff metrics.
2285 #( #send_metrics_code )*
2286 }
2287 } else {
2288 // Otherwise, run the subgraph body inline. We are already in an `async`
2289 // context (the tick closure), so there is no need for an intermediate
2290 // `async` block which is immediately `.await`ed.
2291 sg_body
2292 };
2293
2294 // Emit subgraph block to the current loop level (top of stack or root).
2295 let sg_block = quote! {
2296 // Create the handoffs we are about to push to (send).
2297 #( #send_hoff_make_code )*
2298
2299 {
2300 #run_sg
2301 }
2302
2303 // Drop the handoffs we just drained (recv).
2304 #( #recv_hoff_drop_code )*
2305 };
2306 if let Some((_, body)) = loop_stack.last_mut() {
2307 body.extend(sg_block);
2308 } else {
2309 current_output.extend(sg_block);
2310 }
2311 }
2312 }
2313
2314 // Close any remaining open loops.
2315 let gated_subgraph_code = {
2316 while let Some((closed_loop, child_body)) = loop_stack.pop() {
2317 let target = if let Some((_, parent_body)) = loop_stack.last_mut() {
2318 parent_body
2319 } else {
2320 &mut current_output
2321 };
2322 self.emit_loop_gate(
2323 closed_loop,
2324 child_body,
2325 &loop_input_handoffs,
2326 &back_edge_hoffs_and_lazyness,
2327 &loop_swap_code,
2328 target,
2329 );
2330 }
2331 current_output
2332 };
2333
2334 if diagnostics.has_error() {
2335 return Err(std::mem::take(diagnostics));
2336 }
2337 let _ = diagnostics; // Ensure no more diagnostics may be added after checking for errors.
2338
2339 let (meta_graph_arg, diagnostics_arg) = if !options.exclude_meta {
2340 let meta_graph_json = serde_json::to_string(&self).unwrap();
2341 let meta_graph_json = Literal::string(&meta_graph_json);
2342
2343 let serde_diagnostics: Vec<_> = diagnostics.iter().map(Diagnostic::to_serde).collect();
2344 let diagnostics_json = serde_json::to_string(&*serde_diagnostics).unwrap();
2345 let diagnostics_json = Literal::string(&diagnostics_json);
2346
2347 (
2348 quote! { Some(#meta_graph_json) },
2349 quote! { Some(#diagnostics_json) },
2350 )
2351 } else {
2352 (quote! { None }, quote! { None })
2353 };
2354
2355 // Generate the `Context` constructor, the `Context<M>` metrics typestate used in the tick
2356 // closure's signature, and, if metrics tracking is enabled, the metrics initialization
2357 // (one entry per handoff and per subgraph) plus the per-tick `__dfir_metrics` binding used
2358 // by the tracking code.
2359 //
2360 // When metrics tracking is disabled, `Context<()>` is used, which statically guarantees that
2361 // no metrics state exists at runtime (see `dfir_rs::scheduled::metrics::MetricsState`).
2362 let (context_new_code, context_metrics_ty, tick_metrics_code) = if options
2363 .include_metrics_tracking
2364 {
2365 let handoff_inits = handoff_nodes.iter().map(|&(node_id, _, _)| {
2366 let ffi = node_id.data().as_ffi();
2367 quote! {
2368 dfir_metrics.handoffs.insert(
2369 #root::slotmap::KeyData::from_ffi(#ffi).into(),
2370 ::std::default::Default::default(),
2371 );
2372 }
2373 });
2374 let subgraph_inits = all_subgraphs.iter().map(|&(sg_id, _)| {
2375 let ffi = sg_id.data().as_ffi();
2376 quote! {
2377 dfir_metrics.subgraphs.insert(
2378 #root::slotmap::KeyData::from_ffi(#ffi).into(),
2379 ::std::default::Default::default(),
2380 );
2381 }
2382 });
2383 let init_code = handoff_inits.chain(subgraph_inits).collect::<Vec<_>>();
2384 (
2385 quote! {
2386 #root::scheduled::context::Context::new_with_metrics({
2387 let mut dfir_metrics = #root::scheduled::metrics::DfirMetrics::default();
2388 #( #init_code )*
2389 dfir_metrics
2390 })
2391 },
2392 quote! {
2393 #root::scheduled::metrics::DfirMetrics
2394 },
2395 quote! {
2396 let __dfir_metrics = #df.metrics();
2397 },
2398 )
2399 } else {
2400 (
2401 quote! {
2402 #root::scheduled::context::Context::new()
2403 },
2404 quote! { () },
2405 quote! {},
2406 )
2407 };
2408
2409 // For creating back-buffer handoff vecs.
2410 let back_buffer_idents = back_buffer_idents_laziness
2411 .iter()
2412 .map(|(back_ident, _, _)| back_ident);
2413 // For creating the send-side buffer for defer_tick handoffs (also outside the closure).
2414 let defer_tick_buf_idents = back_buffer_idents_laziness
2415 .iter()
2416 .map(|(_, buf_ident, _)| buf_ident);
2417 // For checking if we should start the next tick (`schedule_subgraph`):
2418 // Collect the ident to check for each non-lazy back-edge handoff.
2419 // - For defer_tick handoffs in a root-level loop: check `back` (swap happened inside `if`)
2420 // - For all others: check `buf` (original behavior; tick-level swap hasn't happened yet)
2421 let non_lazy_schedule_idents: Vec<&Ident> = handoff_nodes
2422 .iter()
2423 .filter_map(|&(hoff_id, _, _)| {
2424 let delay_type = self.handoff_delay_type(hoff_id)?;
2425 // Only non-lazy.
2426 if matches!(delay_type, DelayType::TickLazy | DelayType::LoopLazy) {
2427 return None;
2428 }
2429 let span = self.nodes[hoff_id].span();
2430 let expected_back_ident = self.hoff_back_ident(hoff_id, span);
2431 let entry = back_buffer_idents_laziness
2432 .iter()
2433 .find(|(back_ident, _, _)| *back_ident == expected_back_ident)?;
2434
2435 // For defer_tick inside a root-level loop, check `back`.
2436 if delay_type == DelayType::Tick {
2437 let consumer_loop = self
2438 .node_successors(hoff_id)
2439 .next()
2440 .and_then(|(_, succ)| self.node_subgraph(succ))
2441 .and_then(|sg| self.subgraph_loop(sg));
2442 if consumer_loop.is_some_and(|lid| self.loop_parent(lid).is_none()) {
2443 return Some(&entry.0); // back ident
2444 }
2445 }
2446 Some(&entry.1) // buf ident
2447 })
2448 .collect();
2449
2450 // Prologues and buffer declarations persist across ticks (outside the closure).
2451 // Subgraph blocks run each tick (inside the closure).
2452 Ok(quote! {
2453 {
2454 #prefix
2455
2456 use #root::{var_expr, var_args};
2457
2458 #[allow(unused_mut)]
2459 let mut #df = #context_new_code;
2460
2461 #( #op_prologue_code )*
2462
2463 // For tick-boundary handoffs (`defer_tick` / `defer_tick_lazy`), declare both the
2464 // send buffer and the "back" buffer as std::vec::Vec outside the tick closure.
2465 // This enables O(1) mem::swap at end of tick for double-buffering.
2466 #( let mut #back_buffer_idents = ::std::vec::Vec::new(); )*
2467 #( let mut #defer_tick_buf_idents = ::std::vec::Vec::new(); )*
2468
2469 // Retaining windowing (`snapshot*()`) handoff state: declared outside the tick
2470 // closure so it persists across ticks, and never consumed by the loop (which reads
2471 // clones each time it fires). `snapshot()` is a single last-write-wins `Option<T>`,
2472 // `snapshot_keyed()` a per-key `FxHashMap<K, V>`, `snapshot_prefix()` an
2473 // append-only `Vec<T>`. See `RetainKind`.
2474 #( #retain_buf_decls )*
2475
2476 // Bump allocator for handoffs (except for back-edge handoffs, above).
2477 let mut #bump_ident = #root::bumpalo::Bump::new();
2478
2479 // Pre-set to true so the first tick always returns true
2480 // (matching Dfir pre-scheduling behavior). Subsequent ticks
2481 // start false (from take()) and are set true by recv port code
2482 // if any handoff buffer has data.
2483 let mut __dfir_work_done = true;
2484 #[allow(unused_qualifications, unused_mut, unused_variables, clippy::await_holding_refcell_ref, clippy::deref_addrof)]
2485 let __dfir_inline_tick = async move |#df: &mut #root::scheduled::context::Context<#context_metrics_ty>| {
2486 // Reset arena between ticks (start-of-tick)
2487 #bump_ident.reset();
2488
2489 {
2490 #tick_metrics_code
2491
2492 #gated_subgraph_code
2493
2494 // For non-lazy defer_tick: if any deferred buffer has data,
2495 // signal that another tick should run.
2496 #[allow(clippy::nonminimal_bool, reason = "codegen")]
2497 if false #( || !#non_lazy_schedule_idents.is_empty() )* {
2498 #df.schedule_subgraph(true);
2499 }
2500
2501 // Double-buffer swap for defer_tick handoffs: move last tick's producer output (regular buffer)
2502 // into the back buffer for the consumer to drain.
2503 #( #back_edge_swap_code )*
2504 }
2505
2506 // End-of-tick per-operator state handling (i.e. 'tick persistence).
2507 #( #op_tick_end_code )*
2508
2509 #df.__end_tick();
2510
2511 ::std::mem::take(&mut __dfir_work_done)
2512 };
2513 #root::scheduled::context::Dfir::new(
2514 #root::scheduled::context::TickClosureFn::new(__dfir_inline_tick),
2515 #df,
2516 #meta_graph_arg,
2517 #diagnostics_arg,
2518 )
2519 }
2520 })
2521 }
2522
2523 /// Color mode (pull vs. push, handoff vs. comp) for nodes. Some nodes can be push *OR* pull;
2524 /// those nodes will not be set in the returned map.
2525 pub fn node_color_map(&self) -> SparseSecondaryMap<GraphNodeId, Color> {
2526 let mut node_color_map: SparseSecondaryMap<GraphNodeId, Color> = self
2527 .node_ids()
2528 .filter_map(|node_id| {
2529 let op_color = self.node_color(node_id)?;
2530 Some((node_id, op_color))
2531 })
2532 .collect();
2533
2534 // Fill in rest via subgraphs.
2535 for sg_nodes in self.subgraph_nodes.values() {
2536 let pull_to_push_idx = self.find_pull_to_push_idx(sg_nodes);
2537
2538 for (idx, node_id) in sg_nodes.iter().copied().enumerate() {
2539 let is_pull = idx < pull_to_push_idx;
2540 node_color_map.insert(node_id, if is_pull { Color::Pull } else { Color::Push });
2541 }
2542 }
2543
2544 node_color_map
2545 }
2546
2547 /// Writes this graph as mermaid into a string.
2548 pub fn to_mermaid(&self, write_config: &WriteConfig) -> String {
2549 let mut output = String::new();
2550 self.write_mermaid(&mut output, write_config).unwrap();
2551 output
2552 }
2553
2554 /// Writes this graph as mermaid into the given `Write`.
2555 pub fn write_mermaid(
2556 &self,
2557 output: impl std::fmt::Write,
2558 write_config: &WriteConfig,
2559 ) -> std::fmt::Result {
2560 let mut graph_write = Mermaid::new(output);
2561 self.write_graph(&mut graph_write, write_config)
2562 }
2563
2564 /// Writes this graph as DOT (graphviz) into a string.
2565 pub fn to_dot(&self, write_config: &WriteConfig) -> String {
2566 let mut output = String::new();
2567 let mut graph_write = Dot::new(&mut output);
2568 self.write_graph(&mut graph_write, write_config).unwrap();
2569 output
2570 }
2571
2572 /// Writes this graph as DOT (graphviz) into the given `Write`.
2573 pub fn write_dot(
2574 &self,
2575 output: impl std::fmt::Write,
2576 write_config: &WriteConfig,
2577 ) -> std::fmt::Result {
2578 let mut graph_write = Dot::new(output);
2579 self.write_graph(&mut graph_write, write_config)
2580 }
2581
2582 /// Write out this graph using the given `GraphWrite`. E.g. `Mermaid` or `Dot`.
2583 pub(crate) fn write_graph<W>(
2584 &self,
2585 mut graph_write: W,
2586 write_config: &WriteConfig,
2587 ) -> Result<(), W::Err>
2588 where
2589 W: GraphWrite,
2590 {
2591 fn helper_edge_label(
2592 src_port: &PortIndexValue,
2593 dst_port: &PortIndexValue,
2594 ) -> Option<String> {
2595 let src_label = match src_port {
2596 PortIndexValue::Path(path) => Some(path.to_token_stream().to_string()),
2597 PortIndexValue::Int(index) => Some(index.value.to_string()),
2598 _ => None,
2599 };
2600 let dst_label = match dst_port {
2601 PortIndexValue::Path(path) => Some(path.to_token_stream().to_string()),
2602 PortIndexValue::Int(index) => Some(index.value.to_string()),
2603 _ => None,
2604 };
2605 let label = match (src_label, dst_label) {
2606 (Some(l1), Some(l2)) => Some(format!("{}\n{}", l1, l2)),
2607 (Some(l1), None) => Some(l1),
2608 (None, Some(l2)) => Some(l2),
2609 (None, None) => None,
2610 };
2611 label
2612 }
2613
2614 // Make node color map one time.
2615 let node_color_map = self.node_color_map();
2616
2617 // Write prologue.
2618 graph_write.write_prologue()?;
2619
2620 // Define nodes.
2621 let mut skipped_handoffs = BTreeSet::new();
2622 for (node_id, node) in self.nodes() {
2623 if matches!(node, GraphNode::Handoff { .. }) && write_config.no_handoffs {
2624 skipped_handoffs.insert(node_id);
2625 continue;
2626 }
2627 graph_write.write_node_definition(
2628 node_id,
2629 &if write_config.op_short_text {
2630 node.to_name_string()
2631 } else if write_config.op_text_no_imports {
2632 // Remove any lines that start with "use" (imports)
2633 let full_text = node.to_pretty_string();
2634 let mut output = String::new();
2635 for sentence in full_text.split('\n') {
2636 if sentence.trim().starts_with("use") {
2637 continue;
2638 }
2639 output.push('\n');
2640 output.push_str(sentence);
2641 }
2642 output.into()
2643 } else {
2644 node.to_pretty_string()
2645 },
2646 if write_config.no_pull_push {
2647 None
2648 } else {
2649 node_color_map.get(node_id).copied()
2650 },
2651 )?;
2652 }
2653
2654 // Write edges.
2655 for (edge_id, (src_id, mut dst_id)) in self.edges() {
2656 // Handling for if `write_config.no_handoffs` true.
2657 if skipped_handoffs.contains(&src_id) {
2658 continue;
2659 }
2660
2661 let (src_port, mut dst_port) = self.edge_ports(edge_id);
2662 if skipped_handoffs.contains(&dst_id) {
2663 // The destination is a hidden handoff. If it has a successor, skip through.
2664 // If it has 0 successors (ref-only singleton), drop this edge entirely —
2665 // the data dependency is captured via the reference edge instead.
2666 let mut handoff_succs = self.node_successors(dst_id);
2667 if handoff_succs.len() == 0 {
2668 continue;
2669 }
2670 let (succ_edge, succ_node) = handoff_succs.next().unwrap();
2671 dst_id = succ_node;
2672 dst_port = self.edge_ports(succ_edge).1;
2673 }
2674
2675 let label = helper_edge_label(src_port, dst_port);
2676 let delay_type = self
2677 .node_op_inst(dst_id)
2678 .and_then(|op_inst| (op_inst.op_constraints.input_delaytype_fn)(dst_port));
2679 graph_write.write_edge(src_id, dst_id, delay_type, label.as_deref(), false)?;
2680 }
2681
2682 // Write reference edges.
2683 if !write_config.no_references {
2684 for dst_id in self.node_ids() {
2685 for src_ref_id in self
2686 .node_handoff_references(dst_id)
2687 .iter()
2688 .filter_map(|r| r.node_id)
2689 {
2690 // When handoffs are hidden, resolve through to the predecessor of
2691 // the singleton handoff so the edge points from the actual writer.
2692 let resolved_src = if skipped_handoffs.contains(&src_ref_id) {
2693 self.node_predecessor_nodes(src_ref_id).next()
2694 } else {
2695 Some(src_ref_id)
2696 };
2697 let Some(resolved_src) = resolved_src else {
2698 continue;
2699 };
2700 let label = None;
2701 graph_write.write_edge(resolved_src, dst_id, None, label, true)?;
2702 }
2703 }
2704 }
2705
2706 // The following code is a little bit tricky. Generally, the graph has the hierarchy:
2707 // `loop -> subgraph -> varname -> node`. However, each of these can be disabled via the `write_config`. To
2708 // handle both the enabled and disabled case, this code is structured as a series of nested loops. If the layer
2709 // is disabled, then the HashMap<Option<KEY>, Vec<VALUE>> will only have a single key (`None`) with a
2710 // corresponding `Vec` value containing everything. This way no special handling is needed for the next layer.
2711
2712 // Loop -> Subgraphs
2713 let loop_subgraphs = self.subgraph_ids().map(|sg_id| {
2714 let loop_id = if write_config.no_loops {
2715 None
2716 } else {
2717 self.subgraph_loop(sg_id)
2718 };
2719 (loop_id, sg_id)
2720 });
2721 let loop_subgraphs = into_group_map(loop_subgraphs);
2722 for (loop_id, subgraph_ids) in loop_subgraphs {
2723 if let Some(loop_id) = loop_id {
2724 graph_write.write_loop_start(loop_id)?;
2725 }
2726
2727 // Subgraph -> Varnames.
2728 let subgraph_varnames_nodes = subgraph_ids.into_iter().flat_map(|sg_id| {
2729 self.subgraph(sg_id).iter().copied().map(move |node_id| {
2730 let opt_sg_id = if write_config.no_subgraphs {
2731 None
2732 } else {
2733 Some(sg_id)
2734 };
2735 (opt_sg_id, (self.node_varname(node_id), node_id))
2736 })
2737 });
2738 let subgraph_varnames_nodes = into_group_map(subgraph_varnames_nodes);
2739 for (sg_id, varnames) in subgraph_varnames_nodes {
2740 if let Some(sg_id) = sg_id {
2741 graph_write.write_subgraph_start(sg_id)?;
2742 }
2743
2744 // Varnames -> Nodes.
2745 let varname_nodes = varnames.into_iter().map(|(varname, node)| {
2746 let varname = if write_config.no_varnames {
2747 None
2748 } else {
2749 varname
2750 };
2751 (varname, node)
2752 });
2753 let varname_nodes = into_group_map(varname_nodes);
2754 for (varname, node_ids) in varname_nodes {
2755 if let Some(varname) = varname {
2756 graph_write.write_varname_start(&varname.0.to_string(), sg_id)?;
2757 }
2758
2759 // Write all nodes.
2760 for node_id in node_ids {
2761 graph_write.write_node(node_id)?;
2762 }
2763
2764 if varname.is_some() {
2765 graph_write.write_varname_end()?;
2766 }
2767 }
2768
2769 if sg_id.is_some() {
2770 graph_write.write_subgraph_end()?;
2771 }
2772 }
2773
2774 if loop_id.is_some() {
2775 graph_write.write_loop_end()?;
2776 }
2777 }
2778
2779 // Write epilogue.
2780 graph_write.write_epilogue()?;
2781
2782 Ok(())
2783 }
2784
2785 /// Convert back into surface syntax.
2786 pub fn surface_syntax_string(&self) -> String {
2787 let mut string = String::new();
2788 self.write_surface_syntax(&mut string).unwrap();
2789 string
2790 }
2791
2792 /// Convert back into surface syntax.
2793 pub fn write_surface_syntax(&self, write: &mut impl std::fmt::Write) -> std::fmt::Result {
2794 for (key, node) in self.nodes.iter() {
2795 match node {
2796 GraphNode::Operator(op) => {
2797 writeln!(write, "_{:?} = {};", key.data(), op.to_token_stream())?;
2798 }
2799 GraphNode::Handoff {
2800 kind: HandoffKind::Vec,
2801 ..
2802 } => {
2803 writeln!(write, "_{:?} = handoff();", key.data())?;
2804 }
2805 GraphNode::Handoff {
2806 kind: HandoffKind::Singleton,
2807 ..
2808 } => {
2809 writeln!(write, "_{:?} = singleton();", key.data())?;
2810 }
2811 GraphNode::Handoff {
2812 kind: HandoffKind::Optional,
2813 ..
2814 } => {
2815 writeln!(write, "_{:?} = optional();", key.data())?;
2816 }
2817 GraphNode::ModuleBoundary { .. } => panic!(),
2818 }
2819 }
2820 writeln!(write)?;
2821 for (e, (src_key, dst_key)) in self.graph.edges() {
2822 let (src_port, dst_port) = self.edge_ports(e);
2823 let src_port_str = if src_port.is_specified() {
2824 format!("[{}]", src_port)
2825 } else {
2826 String::new()
2827 };
2828 let dst_port_str = if dst_port.is_specified() {
2829 format!("[{}]", dst_port)
2830 } else {
2831 String::new()
2832 };
2833 writeln!(
2834 write,
2835 "_{:?}{} -> {}_{:?};",
2836 src_key.data(),
2837 src_port_str,
2838 dst_port_str,
2839 dst_key.data()
2840 )?;
2841 }
2842 Ok(())
2843 }
2844
2845 /// Convert into a [mermaid](https://mermaid-js.github.io/) graph. Ignores subgraphs.
2846 pub fn mermaid_string_flat(&self) -> String {
2847 let mut string = String::new();
2848 self.write_mermaid_flat(&mut string).unwrap();
2849 string
2850 }
2851
2852 /// Convert into a [mermaid](https://mermaid-js.github.io/) graph. Ignores subgraphs.
2853 pub fn write_mermaid_flat(&self, write: &mut impl std::fmt::Write) -> std::fmt::Result {
2854 writeln!(write, "flowchart TB")?;
2855 for (key, node) in self.nodes.iter() {
2856 match node {
2857 GraphNode::Operator(operator) => writeln!(
2858 write,
2859 " %% {span}\n {id:?}[\"{row_col} <tt>{code}</tt>\"]",
2860 span = PrettySpan(node.span()),
2861 id = key.data(),
2862 row_col = PrettyRowCol(node.span()),
2863 code = operator
2864 .to_token_stream()
2865 .to_string()
2866 .replace('&', "&")
2867 .replace('<', "<")
2868 .replace('>', ">")
2869 .replace('"', """)
2870 .replace('\n', "<br>"),
2871 ),
2872 GraphNode::Handoff {
2873 kind: HandoffKind::Vec,
2874 ..
2875 } => {
2876 writeln!(write, r#" {:?}{{"{}"}}"#, key.data(), HANDOFF_NODE_STR)
2877 }
2878 GraphNode::Handoff {
2879 kind: HandoffKind::Singleton | HandoffKind::Optional,
2880 ..
2881 } => {
2882 writeln!(
2883 write,
2884 r#" {:?}{{"{}"}}"#,
2885 key.data(),
2886 SINGLETON_SLOT_NODE_STR
2887 )
2888 }
2889 GraphNode::ModuleBoundary { .. } => {
2890 writeln!(
2891 write,
2892 r#" {:?}{{"{}"}}"#,
2893 key.data(),
2894 MODULE_BOUNDARY_NODE_STR
2895 )
2896 }
2897 }?;
2898 }
2899 writeln!(write)?;
2900 for (_e, (src_key, dst_key)) in self.graph.edges() {
2901 writeln!(write, " {:?}-->{:?}", src_key.data(), dst_key.data())?;
2902 }
2903 Ok(())
2904 }
2905}
2906
2907/// Loops
2908impl DfirGraph {
2909 /// Iterator over all loop IDs.
2910 pub fn loop_ids(&self) -> slotmap::basic::Keys<'_, GraphLoopId, Vec<GraphNodeId>> {
2911 self.loop_nodes.keys()
2912 }
2913
2914 /// Iterator over all loops, ID and members: `(GraphLoopId, Vec<GraphNodeId>)`.
2915 pub fn loops(&self) -> slotmap::basic::Iter<'_, GraphLoopId, Vec<GraphNodeId>> {
2916 self.loop_nodes.iter()
2917 }
2918
2919 /// Get a loop's member nodes.
2920 pub fn loop_nodes(&self, loop_id: GraphLoopId) -> &[GraphNodeId] {
2921 self.loop_nodes.get(loop_id).unwrap()
2922 }
2923
2924 /// Create a new loop context, with the given parent loop (or `None`).
2925 pub fn insert_loop(&mut self, parent_loop: Option<GraphLoopId>) -> GraphLoopId {
2926 let loop_id = self.loop_nodes.insert(Vec::new());
2927 self.loop_children.insert(loop_id, Vec::new());
2928 if let Some(parent_loop) = parent_loop {
2929 self.loop_parent.insert(loop_id, parent_loop);
2930 self.loop_children
2931 .get_mut(parent_loop)
2932 .unwrap()
2933 .push(loop_id);
2934 } else {
2935 self.root_loops.push(loop_id);
2936 }
2937 loop_id
2938 }
2939
2940 /// Get a node's loop context (or `None` for root).
2941 pub fn node_loop(&self, node_id: GraphNodeId) -> Option<GraphLoopId> {
2942 self.node_loops.get(node_id).copied()
2943 }
2944
2945 /// Get a subgraph's loop context (or `None` for root).
2946 pub fn subgraph_loop(&self, subgraph_id: GraphSubgraphId) -> Option<GraphLoopId> {
2947 let &node_id = self.subgraph(subgraph_id).first().unwrap();
2948 let out = self.node_loop(node_id);
2949 debug_assert!(
2950 self.subgraph(subgraph_id)
2951 .iter()
2952 .all(|&node_id| self.node_loop(node_id) == out),
2953 "Subgraph nodes should all have the same loop context."
2954 );
2955 out
2956 }
2957
2958 /// Get a loop context's parent loop context (or `None` for root).
2959 pub fn loop_parent(&self, loop_id: GraphLoopId) -> Option<GraphLoopId> {
2960 self.loop_parent.get(loop_id).copied()
2961 }
2962
2963 /// Get a loop context's child loops.
2964 pub fn loop_children(&self, loop_id: GraphLoopId) -> &Vec<GraphLoopId> {
2965 self.loop_children.get(loop_id).unwrap()
2966 }
2967
2968 /// Get root-level loops (those with no parent loop).
2969 pub fn root_loops(&self) -> &[GraphLoopId] {
2970 &self.root_loops
2971 }
2972}
2973
2974/// Options for [`DfirGraph::as_code_with_options`].
2975#[derive(Clone, Debug, Default)]
2976#[non_exhaustive]
2977pub struct AsCodeOptions {
2978 /// Controls whether type guards are emitted in codegen.
2979 ///
2980 /// Type guards are identity wrapper functions emitted around each operator (and in some
2981 /// operators' own codegen, e.g. `check_stream` in `source_stream`, or the `pivot_run_sg_*`
2982 /// function joining the pull and push halves of a subgraph), which pin down the `Item`/`Meta`
2983 /// types flowing between operators so that type errors in user code are reported at the
2984 /// offending operator rather than somewhere downstream. They have no runtime effect, but they
2985 /// make the generated code significantly more verbose.
2986 ///
2987 /// Excluding type guards may result in worse error messages for hand-written DFIR. However,
2988 /// front-ends which already type-check the dataflow themselves (e.g. Hydro) and inject their
2989 /// own type hints can safely exclude them to produce much more compact generated code.
2990 ///
2991 /// Note that the per-operator type guard wrapper is also what gives streaming operators (e.g.
2992 /// `map`, `filter`) a named stack frame in profiles/flamegraphs, since the wrapper struct's
2993 /// `pull`/`push` impls live inside a function named after the operator. Set
2994 /// [`Self::require_flame_attribution`] to keep those wrappers even when type guards are
2995 /// excluded.
2996 pub exclude_type_guards: bool,
2997 /// Requires that every operator gets a named stack frame for profiler/flamegraph attribution,
2998 /// even when [`Self::exclude_type_guards`] is set.
2999 ///
3000 /// Operators which do work outside the pull/push pipeline (e.g. `fold`, `join`) always get
3001 /// attribution via their `work_fn` thunks. Streaming operators (e.g. `map`, `filter`) only get
3002 /// attribution via the per-operator type guard wrapper, so this option forces that wrapper to
3003 /// be emitted when type guards are otherwise excluded. Has no effect when type guards are
3004 /// included (the default).
3005 pub require_flame_attribution: bool,
3006 /// Controls whether the runtime meta graph + diagnostics JSON blobs are baked into the generated
3007 /// `Dfir::new(...)` call.
3008 pub exclude_meta: bool,
3009 /// Controls whether metrics are tracked. Metrics tracking is opt-in: no tracking code is
3010 /// generated unless this is set.
3011 ///
3012 /// This selects the `MetricsState` typestate of the generated `Dfir`'s `Context`: when set,
3013 /// `Context<DfirMetrics>` is used and `Dfir::metrics()` is available; when unset,
3014 /// `Context<()>` is used, which statically guarantees that there is no metrics state (and no
3015 /// `Dfir::metrics()` accessor) at runtime.
3016 pub include_metrics_tracking: bool,
3017}
3018
3019/// Configuration for writing graphs.
3020#[derive(Clone, Debug, Default)]
3021#[cfg_attr(feature = "clap-derive", derive(clap::Args))]
3022pub struct WriteConfig {
3023 /// Subgraphs will not be rendered if set.
3024 #[cfg_attr(feature = "clap-derive", arg(long))]
3025 pub no_subgraphs: bool,
3026 /// Variable names will not be rendered if set.
3027 #[cfg_attr(feature = "clap-derive", arg(long))]
3028 pub no_varnames: bool,
3029 /// Will not render pull/push shapes if set.
3030 #[cfg_attr(feature = "clap-derive", arg(long))]
3031 pub no_pull_push: bool,
3032 /// Will not render handoffs if set.
3033 #[cfg_attr(feature = "clap-derive", arg(long))]
3034 pub no_handoffs: bool,
3035 /// Will not render singleton references if set.
3036 #[cfg_attr(feature = "clap-derive", arg(long))]
3037 pub no_references: bool,
3038 /// Will not render loops if set.
3039 #[cfg_attr(feature = "clap-derive", arg(long))]
3040 pub no_loops: bool,
3041
3042 /// Op text will only be their name instead of the whole source.
3043 #[cfg_attr(feature = "clap-derive", arg(long))]
3044 pub op_short_text: bool,
3045 /// Op text will exclude any line that starts with "use".
3046 #[cfg_attr(feature = "clap-derive", arg(long))]
3047 pub op_text_no_imports: bool,
3048}
3049
3050/// Enum for choosing between mermaid and dot graph writing.
3051#[derive(Copy, Clone, Debug)]
3052#[cfg_attr(feature = "clap-derive", derive(clap::Parser, clap::ValueEnum))]
3053pub enum WriteGraphType {
3054 /// Mermaid graphs.
3055 Mermaid,
3056 /// Dot (Graphviz) graphs.
3057 Dot,
3058}
3059
3060/// Returns `true` if `ident` appears anywhere (at any nesting depth) in `tokens`.
3061fn tokens_contain_ident(tokens: TokenStream, ident: &Ident) -> bool {
3062 tokens.into_iter().any(|tt| match tt {
3063 TokenTree::Ident(i) => i == *ident,
3064 TokenTree::Group(group) => tokens_contain_ident(group.stream(), ident),
3065 TokenTree::Punct(_) | TokenTree::Literal(_) => false,
3066 })
3067}
3068
3069/// [`itertools::Itertools::into_group_map`], but for `BTreeMap`.
3070fn into_group_map<K, V>(iter: impl IntoIterator<Item = (K, V)>) -> BTreeMap<K, Vec<V>>
3071where
3072 K: Ord,
3073{
3074 let mut out: BTreeMap<_, Vec<_>> = BTreeMap::new();
3075 for (k, v) in iter {
3076 out.entry(k).or_default().push(v);
3077 }
3078 out
3079}