hugr_core/builder/
dataflow.rs

1//! Builders for dataflow regions.
2
3use itertools::Itertools;
4
5use super::build_traits::{HugrBuilder, SubContainer};
6use super::handle::BuildHandle;
7use super::{BuildError, Container, Dataflow, DfgID, FuncID};
8
9use std::marker::PhantomData;
10
11use crate::hugr::internal::HugrMutInternals;
12use crate::hugr::{HugrView, ValidationError};
13use crate::ops::handle::NodeHandle;
14use crate::ops::{self, DFG, FuncDefn, NamedOp, OpParent, OpType};
15use crate::types::{PolyFuncType, Signature, Type};
16use crate::{Direction, Hugr, IncomingPort, Node, OutgoingPort, Visibility, Wire, hugr::HugrMut};
17
18/// Builder for a [`ops::DFG`] node.
19///
20/// See the [crate-level documentation](https://docs.rs/hugr/latest/hugr/#example)
21/// for an example of using [`DFGBuilder`] to construct a boolean circuit or the
22/// [extension module documentation](crate::extension) for an example of using the builder
23/// with a quantum extension.
24#[derive(Debug, Clone, PartialEq)]
25pub struct DFGBuilder<T> {
26    pub(crate) base: T,
27    pub(crate) dfg_node: Node,
28    pub(crate) num_in_wires: usize,
29    pub(crate) num_out_wires: usize,
30}
31
32/// Error returned by [`DFGBuilder::add_input`] and [`DFGBuilder::add_output`].
33#[derive(Debug, Clone, PartialEq, derive_more::Display, derive_more::Error)]
34#[non_exhaustive]
35pub enum DFGAddPortError {
36    /// The parent optype is not a [`FuncDefn`], [`DFG`], or dataflow block so we cannot update its signature.
37    #[display("Adding port to an optype {op} is not supported.")]
38    ParentOpNotSupported {
39        /// The name of the unsupported operation.
40        op: String,
41    },
42}
43
44impl<T: AsMut<Hugr> + AsRef<Hugr>> DFGBuilder<T> {
45    /// Returns a new `DFGBuilder` with the given base and parent node.
46    ///
47    /// Sets up the input and output nodes of the region. If `parent` already has
48    /// input and output nodes, use [`DFGBuilder::create`] instead.
49    pub fn create_with_io(
50        mut base: T,
51        parent: Node,
52        signature: Signature,
53    ) -> Result<Self, BuildError> {
54        debug_assert_eq!(base.as_ref().children(parent).count(), 0);
55
56        let num_in_wires = signature.input_count();
57        let num_out_wires = signature.output_count();
58        let input = ops::Input {
59            types: signature.input().clone(),
60        };
61        let output = ops::Output {
62            types: signature.output().clone(),
63        };
64        base.as_mut().add_node_with_parent(parent, input);
65        base.as_mut().add_node_with_parent(parent, output);
66
67        Ok(Self {
68            base,
69            dfg_node: parent,
70            num_in_wires,
71            num_out_wires,
72        })
73    }
74
75    /// Returns a new `DFGBuilder` with the given base and parent node.
76    ///
77    /// The parent node may be any `DataflowParent` node.
78    ///
79    /// If `parent` doesn't have input and output nodes, use
80    /// [`DFGBuilder::create_with_io`] instead.
81    pub fn create(base: T, parent: Node) -> Result<Self, BuildError> {
82        let sig = base
83            .as_ref()
84            .get_optype(parent)
85            .inner_function_type()
86            .expect("DFG parent must have an inner function signature.");
87        let num_in_wires = sig.input_count();
88        let num_out_wires = sig.output_count();
89
90        Ok(Self {
91            base,
92            dfg_node: parent,
93            num_in_wires,
94            num_out_wires,
95        })
96    }
97
98    /// Add a new input to the dataflow being constructed.
99    ///
100    /// Updates the parent's optype to include the new input type.
101    ///
102    /// # Returns
103    ///
104    /// - The new wire from the input node.
105    ///
106    /// # Errors
107    ///
108    /// - [`DFGAddPortError::ParentOpNotSupported`] if the container optype is not a [`FuncDefn`], [`DFG`], or dataflow block so we cannot add an input.
109    ///   In this case, the Hugr will not be updated.
110    pub fn add_input(&mut self, input_type: Type) -> Result<Wire, DFGAddPortError> {
111        let [inp_node, _] = self.io();
112
113        // Update the parent's root type
114        if !self.update_parent_signature(|mut s| {
115            s.input.to_mut().push(input_type.clone());
116            s
117        }) {
118            return Err(DFGAddPortError::ParentOpNotSupported {
119                op: self
120                    .hugr()
121                    .get_optype(self.container_node())
122                    .name()
123                    .to_string(),
124            });
125        }
126
127        // Update the inner input node
128        let OpType::Input(inp) = self.hugr_mut().optype_mut(inp_node) else {
129            panic!("Input node {inp_node} is not an Input");
130        };
131        inp.types.to_mut().push(input_type);
132
133        let mut new_port = self.hugr_mut().add_ports(inp_node, Direction::Outgoing, 1);
134        let new_port = new_port.next().unwrap();
135
136        // The last port in an input/output node is an order edge port, so we must shift any connections to it.
137        let new_value_port: OutgoingPort = (new_port - 1).into();
138        let new_order_port: OutgoingPort = new_port.into();
139        let order_edge_targets = self
140            .hugr()
141            .linked_inputs(inp_node, new_value_port)
142            .collect_vec();
143        self.hugr_mut().disconnect(inp_node, new_value_port);
144        for (tgt_node, tgt_port) in order_edge_targets {
145            self.hugr_mut()
146                .connect(inp_node, new_order_port, tgt_node, tgt_port);
147        }
148
149        // Update the builder metadata
150        self.num_in_wires += 1;
151
152        Ok(self.input_wires().next_back().unwrap())
153    }
154
155    /// Add a new output to the function being constructed.
156    ///
157    /// Updates the parent's optype to include the new input type, if possible.
158    /// If the container optype is not a [`FuncDefn`], [`DFG`], or dataflow
159    /// block, the optype will not be updated.
160    ///
161    /// # Errors
162    ///
163    /// - [`DFGAddPortError::ParentOpNotSupported`] if the container optype is not a [`FuncDefn`], [`DFG`], or dataflow block so we cannot add an input.
164    ///   In this case, the Hugr will not be updated.
165    pub fn add_output(&mut self, output_type: Type) -> Result<(), DFGAddPortError> {
166        let [_, out_node] = self.io();
167
168        // Update the parent's root type
169        if !self.update_parent_signature(|mut s| {
170            s.output.to_mut().push(output_type.clone());
171            s
172        }) {
173            return Err(DFGAddPortError::ParentOpNotSupported {
174                op: self
175                    .hugr()
176                    .get_optype(self.container_node())
177                    .name()
178                    .to_string(),
179            });
180        }
181
182        // Update the inner input node
183        let OpType::Output(out) = self.hugr_mut().optype_mut(out_node) else {
184            panic!("Output node {out_node} is not an Output");
185        };
186        out.types.to_mut().push(output_type);
187
188        let mut new_port = self.hugr_mut().add_ports(out_node, Direction::Incoming, 1);
189        let new_port = new_port.next().unwrap();
190
191        // The last port in an input/output node is an order edge port, so we must shift any connections to it.
192        let new_value_port: IncomingPort = (new_port - 1).into();
193        let new_order_port: IncomingPort = new_port.into();
194        let order_edge_sources = self
195            .hugr()
196            .linked_outputs(out_node, new_value_port)
197            .collect_vec();
198        self.hugr_mut().disconnect(out_node, new_value_port);
199        for (src_node, src_port) in order_edge_sources {
200            self.hugr_mut()
201                .connect(src_node, src_port, out_node, new_order_port);
202        }
203
204        // Update the builder metadata
205        self.num_out_wires += 1;
206
207        Ok(())
208    }
209
210    /// Update the container's parent signature, if it is a function definition, DFG region, or dataflow block.
211    ///
212    /// Internal function used in [`add_input`] and [`add_output`].
213    ///
214    /// Does not update the input and output nodes.
215    ///
216    /// # Returns
217    ///
218    /// - `true` if the parent signature was updated.
219    /// - `false` if the parent optype is not a [`FuncDefn`], [`DFG`], or dataflow block so we cannot update the signature.
220    fn update_parent_signature(&mut self, f: impl FnOnce(Signature) -> Signature) -> bool {
221        let parent = self.container_node();
222
223        match self.hugr_mut().optype_mut(parent) {
224            ops::OpType::FuncDefn(fd) => {
225                let mut sig = std::mem::take(fd.signature_mut());
226                let body = std::mem::take(sig.body_mut());
227                *sig.body_mut() = f(body);
228                *fd.signature_mut() = sig;
229            }
230            ops::OpType::DFG(dfg) => {
231                let sig = std::mem::take(&mut dfg.signature);
232                dfg.signature = f(sig);
233            }
234            ops::OpType::DataflowBlock(dfb) => {
235                let inp = std::mem::take(&mut dfb.inputs);
236                let other_outputs = std::mem::take(&mut dfb.other_outputs);
237                let sig = f(Signature::new(inp, other_outputs));
238                dfb.inputs = sig.input;
239                dfb.other_outputs = sig.output;
240            }
241            _ => return false,
242        }
243        true
244    }
245}
246
247impl DFGBuilder<Hugr> {
248    /// Begin building a new DFG-rooted HUGR given its inputs, outputs,
249    /// and extension delta.
250    ///
251    /// # Errors
252    ///
253    /// Error in adding DFG child nodes.
254    pub fn new(signature: Signature) -> Result<DFGBuilder<Hugr>, BuildError> {
255        let dfg_op: DFG = ops::DFG {
256            signature: signature.clone(),
257        };
258        let base = Hugr::new_with_entrypoint(dfg_op).expect("DFG entrypoint should be valid");
259        let root = base.entrypoint();
260        DFGBuilder::create_with_io(base, root, signature)
261    }
262}
263
264impl HugrBuilder for DFGBuilder<Hugr> {
265    fn finish_hugr(self) -> Result<Hugr, ValidationError<Node>> {
266        self.base.validate()?;
267        Ok(self.base)
268    }
269}
270
271impl<T: AsMut<Hugr> + AsRef<Hugr>> Container for DFGBuilder<T> {
272    #[inline]
273    fn container_node(&self) -> Node {
274        self.dfg_node
275    }
276
277    #[inline]
278    fn hugr_mut(&mut self) -> &mut Hugr {
279        self.base.as_mut()
280    }
281
282    #[inline]
283    fn hugr(&self) -> &Hugr {
284        self.base.as_ref()
285    }
286}
287
288impl<T: AsMut<Hugr> + AsRef<Hugr>> SubContainer for DFGBuilder<T> {
289    type ContainerHandle = BuildHandle<DfgID>;
290    #[inline]
291    fn finish_sub_container(self) -> Result<Self::ContainerHandle, BuildError> {
292        Ok((self.dfg_node, self.num_out_wires).into())
293    }
294}
295
296impl<T: AsMut<Hugr> + AsRef<Hugr>> Dataflow for DFGBuilder<T> {
297    #[inline]
298    fn num_inputs(&self) -> usize {
299        self.num_in_wires
300    }
301}
302
303/// Wrapper around [`DFGBuilder`] used to build other dataflow regions.
304// Stores option of DFGBuilder so it can be taken out without moving.
305#[derive(Debug, Clone, PartialEq)]
306pub struct DFGWrapper<B, T>(DFGBuilder<B>, PhantomData<T>);
307
308impl<B, T: NodeHandle> DFGWrapper<B, T> {
309    /// Wrap a [`DFGBuilder`] into a [`DFGWrapper`], with the given handle type.
310    ///
311    /// The caller must ensure that the DFGBuilder's parent node has the correct
312    /// handle type given by `T::TAG`.
313    pub fn from_dfg_builder(db: DFGBuilder<B>) -> Self {
314        Self(db, PhantomData)
315    }
316
317    /// Unwrap the [`DFGWrapper`] into a [`DFGBuilder`].
318    pub fn into_dfg_builder(self) -> DFGBuilder<B> {
319        self.0
320    }
321}
322
323impl<B: AsMut<Hugr> + AsRef<Hugr>, T> DFGWrapper<B, T> {
324    /// Add a new input to the dataflow being constructed.
325    ///
326    /// Updates the parent's optype to include the new input type, if possible.
327    /// If the container optype is not a [`FuncDefn`] or a [`DFG`], the optype
328    /// will not be updated.
329    ///
330    /// # Returns
331    ///
332    /// - The new wire from the input node.
333    ///
334    /// # Errors
335    ///
336    /// - [`DFGAddPortError::ParentOpNotSupported`] if the container optype is
337    ///   not a [`FuncDefn`], [`DFG`], or dataflow block so we cannot add an
338    ///   input. In this case, the Hugr will not be updated.
339    pub fn add_input(&mut self, input_type: Type) -> Result<Wire, DFGAddPortError> {
340        self.0.add_input(input_type)
341    }
342
343    /// Add a new output to the dataflow being constructed.
344    ///
345    /// Updates the parent's optype to include the new output type, if possible.
346    /// If the container optype is not a [`FuncDefn`] or a [`DFG`], the optype
347    /// will not be updated.
348    ///
349    /// # Errors
350    ///
351    /// - [`DFGAddPortError::ParentOpNotSupported`] if the container optype is
352    ///   not a [`FuncDefn`], [`DFG`], or dataflow block so we cannot add an
353    ///   input. In this case, the Hugr will not be updated.
354    pub fn add_output(&mut self, output_type: Type) -> Result<(), DFGAddPortError> {
355        self.0.add_output(output_type)
356    }
357}
358
359/// Builder for a [`ops::FuncDefn`] node
360pub type FunctionBuilder<B> = DFGWrapper<B, BuildHandle<FuncID<true>>>;
361
362impl FunctionBuilder<Hugr> {
363    /// Initialize a builder for a [`FuncDefn`]-rooted HUGR; the function will
364    /// be private. (See also [Self::new_vis].)
365    ///
366    /// # Errors
367    ///
368    /// Error in adding DFG child nodes.
369    pub fn new(
370        name: impl Into<String>,
371        signature: impl Into<PolyFuncType>,
372    ) -> Result<Self, BuildError> {
373        Self::new_with_op(FuncDefn::new(name, signature))
374    }
375
376    /// Initialize a builder for a FuncDefn-rooted HUGR, with the specified
377    /// [Visibility].
378    ///
379    /// # Errors
380    ///
381    /// Error in adding DFG child nodes.
382    pub fn new_vis(
383        name: impl Into<String>,
384        signature: impl Into<PolyFuncType>,
385        visibility: Visibility,
386    ) -> Result<Self, BuildError> {
387        Self::new_with_op(FuncDefn::new_vis(name, signature, visibility))
388    }
389
390    fn new_with_op(op: FuncDefn) -> Result<Self, BuildError> {
391        let body = op.signature().body().clone();
392
393        let base = Hugr::new_with_entrypoint(op).expect("FuncDefn entrypoint should be valid");
394        let root = base.entrypoint();
395
396        let db = DFGBuilder::create_with_io(base, root, body)?;
397        Ok(Self::from_dfg_builder(db))
398    }
399}
400
401impl<B: AsMut<Hugr> + AsRef<Hugr>> FunctionBuilder<B> {
402    /// Initialize a new function definition on the root module of an existing HUGR.
403    ///
404    /// The HUGR's entrypoint will **not** be modified.
405    ///
406    /// # Errors
407    ///
408    /// Error in adding DFG child nodes.
409    pub fn with_hugr(
410        mut hugr: B,
411        name: impl Into<String>,
412        signature: impl Into<PolyFuncType>,
413    ) -> Result<Self, BuildError> {
414        let signature: PolyFuncType = signature.into();
415        let body = signature.body().clone();
416        let op = ops::FuncDefn::new(name, signature);
417
418        let module = hugr.as_ref().module_root();
419        let func = hugr.as_mut().add_node_with_parent(module, op);
420
421        let db = DFGBuilder::create_with_io(hugr, func, body)?;
422        Ok(Self::from_dfg_builder(db))
423    }
424}
425
426impl<B: AsMut<Hugr> + AsRef<Hugr>, T> Container for DFGWrapper<B, T> {
427    #[inline]
428    fn container_node(&self) -> Node {
429        self.0.container_node()
430    }
431
432    #[inline]
433    fn hugr_mut(&mut self) -> &mut Hugr {
434        self.0.hugr_mut()
435    }
436
437    #[inline]
438    fn hugr(&self) -> &Hugr {
439        self.0.hugr()
440    }
441}
442
443impl<B: AsMut<Hugr> + AsRef<Hugr>, T> Dataflow for DFGWrapper<B, T> {
444    #[inline]
445    fn num_inputs(&self) -> usize {
446        self.0.num_inputs()
447    }
448}
449
450impl<B: AsMut<Hugr> + AsRef<Hugr>, T: From<BuildHandle<DfgID>>> SubContainer for DFGWrapper<B, T> {
451    type ContainerHandle = T;
452
453    #[inline]
454    fn finish_sub_container(self) -> Result<Self::ContainerHandle, BuildError> {
455        self.0.finish_sub_container().map(Into::into)
456    }
457}
458
459impl<T> HugrBuilder for DFGWrapper<Hugr, T> {
460    fn finish_hugr(self) -> Result<Hugr, ValidationError<Node>> {
461        self.0.finish_hugr()
462    }
463}
464
465#[cfg(test)]
466pub(crate) mod test {
467    use cool_asserts::assert_matches;
468    use rstest::rstest;
469    use std::collections::HashMap;
470
471    use crate::builder::build_traits::DataflowHugr;
472    use crate::builder::test::dfg_calling_defn_decl;
473    use crate::builder::{
474        BuilderWiringError, CFGBuilder, DataflowSubContainer, ModuleBuilder, TailLoopBuilder,
475        endo_sig, inout_sig,
476    };
477    use crate::extension::SignatureError;
478    use crate::extension::prelude::{Noop, bool_t, qb_t, usize_t};
479    use crate::hugr::linking::{NameLinkingPolicy, NodeLinkingDirective, OnMultiDefn};
480    use crate::hugr::validate::InterGraphEdgeError;
481    use crate::metadata::Metadata;
482    use crate::ops::{FuncDecl, FuncDefn, OpParent, OpTag, OpTrait, Value, handle::NodeHandle};
483    use crate::std_extensions::logic::test::and_op;
484    use crate::types::type_param::TypeParam;
485    use crate::types::{EdgeKind, FuncValueType, RowVariable, Signature, Type, TypeBound, TypeRV};
486    use crate::utils::test_quantum_extension::h_gate;
487    use crate::{Wire, builder::test::n_identity, type_row};
488
489    use super::super::test::simple_dfg_hugr;
490    use super::*;
491    #[test]
492    fn nested_identity() -> Result<(), BuildError> {
493        let build_result = {
494            let mut outer_builder = DFGBuilder::new(endo_sig(vec![usize_t(), qb_t()]))?;
495
496            let [int, qb] = outer_builder.input_wires_arr();
497
498            let q_out = outer_builder.add_dataflow_op(h_gate(), vec![qb])?;
499
500            let inner_builder = outer_builder.dfg_builder_endo([(usize_t(), int)])?;
501            let inner_id = n_identity(inner_builder)?;
502
503            outer_builder.finish_hugr_with_outputs(inner_id.outputs().chain(q_out.outputs()))
504        };
505
506        assert_eq!(build_result.err(), None);
507
508        Ok(())
509    }
510
511    // Scaffolding for copy insertion tests
512    fn copy_scaffold<F>(f: F, msg: &'static str) -> Result<(), BuildError>
513    where
514        F: FnOnce(&mut DFGBuilder<Hugr>) -> Result<(), BuildError>,
515    {
516        let build_result = {
517            let mut builder = DFGBuilder::new(inout_sig([bool_t()], vec![bool_t(); 2]))?;
518
519            f(&mut builder)?;
520
521            builder.finish_hugr()
522        };
523        assert_matches!(build_result, Ok(_), "Failed on example: {}", msg);
524
525        Ok(())
526    }
527    #[test]
528    fn copy_insertion() -> Result<(), BuildError> {
529        copy_scaffold(
530            |f_build| {
531                let [b1] = f_build.input_wires_arr();
532                f_build.set_outputs([b1, b1])
533            },
534            "Copy input and output",
535        )?;
536
537        copy_scaffold(
538            |f_build| {
539                let [b1] = f_build.input_wires_arr();
540                let xor = f_build.add_dataflow_op(and_op(), [b1, b1])?;
541                f_build.set_outputs([xor.out_wire(0), b1])
542            },
543            "Copy input and use with binary function",
544        )?;
545
546        copy_scaffold(
547            |f_build| {
548                let [b1] = f_build.input_wires_arr();
549                let xor1 = f_build.add_dataflow_op(and_op(), [b1, b1])?;
550                let xor2 = f_build.add_dataflow_op(and_op(), [b1, xor1.out_wire(0)])?;
551                f_build.set_outputs([xor2.out_wire(0), b1])
552            },
553            "Copy multiple times",
554        )?;
555
556        Ok(())
557    }
558
559    #[test]
560    fn copy_insertion_qubit() {
561        let builder = || {
562            let mut module_builder = ModuleBuilder::new();
563
564            let f_build = module_builder
565                .define_function("main", Signature::new(vec![qb_t()], vec![qb_t(), qb_t()]))?;
566
567            let [q1] = f_build.input_wires_arr();
568            f_build.finish_with_outputs([q1, q1])?;
569
570            Ok(module_builder.finish_hugr()?)
571        };
572
573        assert_matches!(
574            builder(),
575            Err(BuildError::OutputWiring {
576                error: BuilderWiringError::NoCopyLinear { typ, .. },
577                ..
578            })
579            if *typ == qb_t()
580        );
581    }
582
583    #[test]
584    fn simple_inter_graph_edge() {
585        let builder = || -> Result<Hugr, BuildError> {
586            let mut f_build =
587                FunctionBuilder::new("main", Signature::new(vec![bool_t()], vec![bool_t()]))?;
588
589            let [i1] = f_build.input_wires_arr();
590            let noop = f_build.add_dataflow_op(Noop(bool_t()), [i1])?;
591            let i1 = noop.out_wire(0);
592
593            let mut nested =
594                f_build.dfg_builder(Signature::new(type_row![], vec![bool_t()]), [])?;
595
596            let id = nested.add_dataflow_op(Noop(bool_t()), [i1])?;
597
598            let nested = nested.finish_with_outputs([id.out_wire(0)])?;
599
600            f_build.finish_hugr_with_outputs([nested.out_wire(0)])
601        };
602
603        assert_matches!(builder(), Ok(_));
604    }
605
606    #[rstest]
607    #[case::function(|sig| FunctionBuilder::new("main", sig).unwrap().into_dfg_builder())]
608    #[case::dfg(|sig| DFGBuilder::new(sig).unwrap())]
609    #[case::df_block(|sig: Signature| {
610        let outs = sig.output.clone();
611        let mut h = CFGBuilder::new(sig).unwrap();
612        let entry_node = h.entry_builder([], outs).unwrap().finish_sub_container().unwrap().node();
613        let hugr = std::mem::take(h.hugr_mut());
614        DFGBuilder::create(hugr, entry_node).unwrap()
615    })]
616    fn add_inputs_outputs(#[case] builder: impl FnOnce(Signature) -> DFGBuilder<Hugr>) {
617        let builder = || -> Result<(Hugr, Node, Signature), BuildError> {
618            let mut dfg = builder(Signature::new(vec![bool_t()], vec![bool_t()]));
619            let dfg_node = dfg.container_node();
620
621            // Initial inner signature, before any inputs or outputs are added
622            let initial_sig = dfg
623                .hugr()
624                .get_optype(dfg_node)
625                .inner_function_type()
626                .unwrap()
627                .into_owned();
628
629            let [i0] = dfg.input_wires_arr();
630            let noop0 = dfg.add_dataflow_op(Noop(bool_t()), [i0])?;
631
632            // Some some order edges
633            dfg.set_order(&dfg.io()[0], &noop0.node());
634            dfg.set_order(&noop0.node(), &dfg.io()[1]);
635
636            // Add a new input and output, and connect them with a noop in between
637            dfg.add_output(qb_t()).unwrap();
638            let i1 = dfg.add_input(qb_t()).unwrap();
639            let noop1 = dfg.add_dataflow_op(Noop(qb_t()), [i1])?;
640
641            // Do not validate the final hugr, as it may have disconnected inputs.
642            dfg.set_outputs([noop0.out_wire(0), noop1.out_wire(0)])?;
643            let hugr = std::mem::take(dfg.hugr_mut());
644            Ok((hugr, dfg_node, initial_sig))
645        };
646
647        let (hugr, dfg_node, initial_sig) = builder().unwrap_or_else(|e| panic!("{e}"));
648
649        let container_sig = hugr.get_optype(dfg_node).inner_function_type().unwrap();
650        let mut expected_sig = initial_sig;
651        expected_sig.input.to_mut().push(qb_t());
652        expected_sig.output.to_mut().push(qb_t());
653        assert_eq!(
654            container_sig.io(),
655            (&expected_sig.input, &expected_sig.output),
656            "Got signature: {container_sig}, expected: {expected_sig}",
657        );
658    }
659
660    #[rstest]
661    #[case::tail_loop(|sig: Signature| TailLoopBuilder::new(sig.input, vec![], sig.output).unwrap().into_dfg_builder())]
662    fn add_inputs_outputs_unsupported(#[case] builder: impl FnOnce(Signature) -> DFGBuilder<Hugr>) {
663        let mut dfg = builder(Signature::new(vec![bool_t()], vec![bool_t()]));
664
665        // Add a new input and output, and connect them with a noop in between
666        assert!(dfg.add_output(qb_t()).is_err());
667        assert!(dfg.add_input(qb_t()).is_err());
668    }
669
670    #[test]
671    fn error_on_linear_inter_graph_edge() -> Result<(), BuildError> {
672        let mut f_build = FunctionBuilder::new("main", Signature::new(vec![qb_t()], vec![qb_t()]))?;
673
674        let [i1] = f_build.input_wires_arr();
675        let noop = f_build.add_dataflow_op(Noop(qb_t()), [i1])?;
676        let i1 = noop.out_wire(0);
677
678        let mut nested = f_build.dfg_builder(Signature::new(type_row![], vec![qb_t()]), [])?;
679
680        let id_res = nested.add_dataflow_op(Noop(qb_t()), [i1]);
681
682        // The error would anyway be caught in validation when we finish the Hugr,
683        // but the builder catches it earlier
684        assert_matches!(
685            id_res.map(|bh| bh.handle().node()), // Transform into something that impl's Debug
686            Err(BuildError::OperationWiring {
687                error: BuilderWiringError::NonCopyableIntergraph { .. },
688                ..
689            })
690        );
691
692        Ok(())
693    }
694
695    #[rstest]
696    fn dfg_hugr(simple_dfg_hugr: Hugr) {
697        assert_eq!(simple_dfg_hugr.num_nodes(), 7);
698        assert_eq!(simple_dfg_hugr.entry_descendants().count(), 3);
699        assert_matches!(simple_dfg_hugr.entrypoint_optype().tag(), OpTag::Dfg);
700    }
701
702    #[test]
703    fn add_hugr() -> Result<(), BuildError> {
704        struct XIntMetadata;
705        impl Metadata for XIntMetadata {
706            type Type<'hugr> = u32;
707            const KEY: &'static str = "x";
708        }
709
710        struct XStringMetadata;
711        impl Metadata for XStringMetadata {
712            type Type<'hugr> = &'hugr str;
713            const KEY: &'static str = "x";
714        }
715
716        // Create a simple DFG
717        let mut dfg_builder = DFGBuilder::new(Signature::new_endo([bool_t()]))?;
718        let [i1] = dfg_builder.input_wires_arr();
719        dfg_builder.set_metadata::<XIntMetadata>(42);
720        let dfg_hugr = dfg_builder.finish_hugr_with_outputs([i1])?;
721
722        // Create a module, and insert the DFG into it
723        let mut module_builder = ModuleBuilder::new();
724
725        let (dfg_node, f_node) = {
726            let mut f_build =
727                module_builder.define_function("main", Signature::new_endo([bool_t()]))?;
728
729            let [i1] = f_build.input_wires_arr();
730            let dfg = f_build.add_hugr_with_wires(dfg_hugr, [i1])?;
731            let f = f_build.finish_with_outputs([dfg.out_wire(0)])?;
732            module_builder.set_child_metadata::<XStringMetadata>(f.node(), "hi");
733            (dfg.node(), f.node())
734        };
735
736        let hugr = module_builder.finish_hugr()?;
737        assert_eq!(hugr.entry_descendants().count(), 7);
738
739        assert_eq!(hugr.get_metadata::<XIntMetadata>(hugr.entrypoint()), None);
740        assert_eq!(hugr.get_metadata::<XIntMetadata>(dfg_node), Some(42));
741        assert_eq!(hugr.get_metadata::<XStringMetadata>(f_node), Some("hi"));
742
743        Ok(())
744    }
745
746    #[rstest]
747    fn add_link_hugr_by_node(
748        #[values(false, true)] replace: bool,
749        #[values(true, false)] view: bool,
750    ) {
751        let mut fb = FunctionBuilder::new("main", Signature::new_endo([bool_t()])).unwrap();
752        let my_decl = fb
753            .module_root_builder()
754            .declare("func1", Signature::new_endo([bool_t()]).into())
755            .unwrap();
756        let (insert, ins_defn, ins_decl) = dfg_calling_defn_decl();
757        let ins_defn_name = insert
758            .get_optype(ins_defn.node())
759            .as_func_defn()
760            .unwrap()
761            .func_name()
762            .clone();
763        let ins_decl_name = insert
764            .get_optype(ins_decl.node())
765            .as_func_decl()
766            .unwrap()
767            .func_name()
768            .clone();
769        let decl_mode = if replace {
770            NodeLinkingDirective::UseExisting(my_decl.node())
771        } else {
772            NodeLinkingDirective::add()
773        };
774        let link_spec = HashMap::from([
775            (ins_defn.node(), NodeLinkingDirective::add()),
776            (ins_decl.node(), decl_mode),
777        ]);
778        let inserted = if view {
779            fb.add_link_view_by_node_with_wires(&insert, [], link_spec)
780                .unwrap()
781        } else {
782            fb.add_link_hugr_by_node_with_wires(insert, [], link_spec)
783                .unwrap()
784        };
785        let h = fb.finish_hugr_with_outputs(inserted.outputs()).unwrap();
786        let defn_names = h
787            .nodes()
788            .filter_map(|n| h.get_optype(n).as_func_defn().map(FuncDefn::func_name))
789            .collect_vec();
790        assert_eq!(defn_names, [&"main".to_string(), &ins_defn_name]);
791        let decl_names = h
792            .nodes()
793            .filter_map(|n| h.get_optype(n).as_func_decl().map(FuncDecl::func_name))
794            .cloned()
795            .collect_vec();
796        let mut expected_decl_names = vec!["func1".to_string()];
797        if !replace {
798            expected_decl_names.push(ins_decl_name)
799        }
800        assert_eq!(decl_names, expected_decl_names);
801    }
802
803    #[test]
804    fn add_link_hugr() {
805        let to_insert = {
806            let mut dfb = DFGBuilder::new(endo_sig(vec![usize_t(); 2])).unwrap();
807            let mut mb = dfb.module_root_builder();
808            let fb = mb
809                .define_function_vis("foo", endo_sig([usize_t()]), Visibility::Public)
810                .unwrap();
811            let ins = fb.input_wires();
812            let func = fb.finish_with_outputs(ins).unwrap();
813            let [in1, in2] = dfb.input_wires_arr();
814            let [out1] = dfb.call(func.handle(), &[], [in1]).unwrap().outputs_arr();
815            let [out2] = dfb.call(func.handle(), &[], [in2]).unwrap().outputs_arr();
816            dfb.finish_hugr_with_outputs([out1, out2]).unwrap()
817        };
818        let mut dfb = DFGBuilder::new(inout_sig([usize_t()], vec![usize_t(); 2])).unwrap();
819        let [in1] = dfb.input_wires_arr();
820        let pol = NameLinkingPolicy::default().on_multiple_defn(OnMultiDefn::UseTarget);
821        let [out1, out2] = dfb
822            .add_link_view_with_wires(&to_insert, &pol, [in1, in1])
823            .unwrap()
824            .outputs_arr();
825        assert!({
826            let h = dfb.hugr();
827            h.children(h.module_root())
828                .skip(1)
829                .exactly_one()
830                .is_ok_and(|n| h.static_targets(n).unwrap().count() == 2)
831        });
832        let [out3, out4] = dfb
833            .add_link_hugr_with_wires(to_insert, &pol, [out1, out2])
834            .unwrap()
835            .outputs_arr();
836        let h = dfb.finish_hugr_with_outputs([out3, out4]).unwrap();
837        assert!(
838            h.children(h.module_root())
839                .skip(1)
840                .exactly_one()
841                .is_ok_and(|n| h.static_targets(n).unwrap().count() == 4)
842        );
843    }
844
845    #[test]
846    fn barrier_node() -> Result<(), BuildError> {
847        let mut parent = DFGBuilder::new(endo_sig([bool_t()]))?;
848
849        let [w] = parent.input_wires_arr();
850
851        let mut dfg_b = parent.dfg_builder(endo_sig([bool_t()]), [w])?;
852        let [w] = dfg_b.input_wires_arr();
853
854        let barr0 = dfg_b.add_barrier([w])?;
855        let [w] = barr0.outputs_arr();
856
857        let barr1 = dfg_b.add_barrier([w])?;
858        let [w] = barr1.outputs_arr();
859
860        let dfg = dfg_b.finish_with_outputs([w])?;
861        let [w] = dfg.outputs_arr();
862
863        let mut dfg2_b = parent.dfg_builder(endo_sig(vec![bool_t(), bool_t()]), [w, w])?;
864        let [w1, w2] = dfg2_b.input_wires_arr();
865        let barr2 = dfg2_b.add_barrier([w1, w2])?;
866        let wires: Vec<Wire> = barr2.outputs().collect();
867
868        let dfg2 = dfg2_b.finish_with_outputs(wires)?;
869        let [w, _] = dfg2.outputs_arr();
870        parent.finish_hugr_with_outputs([w])?;
871
872        Ok(())
873    }
874
875    #[test]
876    fn non_cfg_ancestor() -> Result<(), BuildError> {
877        let unit_sig = Signature::new_endo([Type::UNIT]);
878        let mut b = DFGBuilder::new(unit_sig.clone())?;
879        let b_child = b.dfg_builder(unit_sig.clone(), b.input_wires())?;
880        let [b_child_in_wire] = b_child.input_wires_arr();
881        b_child.finish_with_outputs([b_child_in_wire])?;
882        let b_child_2 = b.dfg_builder(Signature::new([], [Type::UNIT]), [])?;
883
884        // DFG block has edge coming a sibling block, which is only valid for
885        // CFGs
886        let b_child_2_handle = b_child_2.finish_with_outputs([b_child_in_wire])?;
887
888        let res = b.finish_hugr_with_outputs([b_child_2_handle.out_wire(0)]);
889
890        assert_matches!(
891            res,
892            Err(BuildError::InvalidHUGR(
893                ValidationError::InterGraphEdgeError(InterGraphEdgeError::NonCFGAncestor { .. })
894            ))
895        );
896        Ok(())
897    }
898
899    #[test]
900    fn no_relation_edge() -> Result<(), BuildError> {
901        let unit_sig = Signature::new(type_row![Type::UNIT], type_row![Type::UNIT]);
902        let mut b = DFGBuilder::new(unit_sig.clone())?;
903        let mut b_child = b.dfg_builder(unit_sig.clone(), [b.input().out_wire(0)])?;
904        let b_child_child = b_child.dfg_builder(unit_sig.clone(), [b_child.input().out_wire(0)])?;
905        let b_child_child_in_wire = b_child_child.input().out_wire(0);
906
907        b_child_child.finish_with_outputs([])?;
908        b_child.finish_with_outputs([])?;
909
910        let mut b_child_2 = b.dfg_builder(unit_sig.clone(), [])?;
911        let b_child_2_child =
912            b_child_2.dfg_builder(unit_sig.clone(), [b_child_2.input().out_wire(0)])?;
913
914        let res = b_child_2_child.finish_with_outputs([b_child_child_in_wire]);
915
916        assert_matches!(
917            res.map(|h| h.handle().node()), // map to something that implements Debug
918            Err(BuildError::OutputWiring {
919                error: BuilderWiringError::NoRelationIntergraph { .. },
920                ..
921            })
922        );
923        Ok(())
924    }
925
926    #[test]
927    fn no_outer_row_variables() -> Result<(), BuildError> {
928        let e = crate::hugr::validate::test::extension_with_eval_parallel();
929        let tv = TypeRV::new_row_var_use(0, TypeBound::Copyable);
930        // Can *declare* a function that takes a function-value of unknown #args
931        FunctionBuilder::new(
932            "bad_eval",
933            PolyFuncType::new(
934                [TypeParam::new_list_type(TypeBound::Copyable)],
935                Signature::new(
936                    [Type::new_function(FuncValueType::new(
937                        [usize_t()],
938                        [tv.clone()],
939                    ))],
940                    [],
941                ),
942            ),
943        )?;
944
945        // But cannot eval it...
946        let ev = e.instantiate_extension_op(
947            "eval",
948            [vec![usize_t().into()].into(), vec![tv.into()].into()],
949        );
950        assert_eq!(
951            ev,
952            Err(SignatureError::RowVarWhereTypeExpected {
953                var: RowVariable(0, TypeBound::Copyable)
954            })
955        );
956        Ok(())
957    }
958
959    #[test]
960    fn order_edges() {
961        let (mut hugr, load_constant, call) = {
962            let mut builder = ModuleBuilder::new();
963            let func = builder
964                .declare("func", Signature::new_endo([bool_t()]).into())
965                .unwrap();
966            let (load_constant, call) = {
967                let mut builder = builder
968                    .define_function("main", Signature::new(Type::EMPTY_TYPEROW, [bool_t()]))
969                    .unwrap();
970                let load_constant = builder.add_load_value(Value::true_val());
971                let [r] = builder
972                    .call(&func, &[], [load_constant])
973                    .unwrap()
974                    .outputs_arr();
975                builder.finish_with_outputs([r]).unwrap();
976                (load_constant.node(), r.node())
977            };
978            (builder.finish_hugr().unwrap(), load_constant, call)
979        };
980
981        let lc_optype = hugr.get_optype(load_constant);
982        let call_optype = hugr.get_optype(call);
983        assert_eq!(EdgeKind::StateOrder, lc_optype.other_input().unwrap());
984        assert_eq!(EdgeKind::StateOrder, lc_optype.other_output().unwrap());
985        assert_eq!(EdgeKind::StateOrder, call_optype.other_input().unwrap());
986        assert_eq!(EdgeKind::StateOrder, call_optype.other_output().unwrap());
987
988        hugr.connect(
989            load_constant,
990            lc_optype.other_output_port().unwrap(),
991            call,
992            call_optype.other_input_port().unwrap(),
993        );
994
995        hugr.validate().unwrap();
996    }
997}
hugr_core/builder/dataflow.rs

hugr_core/builder/
dataflow.rs
