Skip to main content

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('&', "&amp;")
2867                        .replace('<', "&lt;")
2868                        .replace('>', "&gt;")
2869                        .replace('"', "&quot;")
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}