hugr_core/hugr/
validate.rs

1//! HUGR invariant checks.
2
3use std::collections::HashMap;
4use std::collections::hash_map::Entry;
5use std::iter;
6
7use itertools::Itertools;
8use petgraph::algo::dominators::{self, Dominators};
9use petgraph::visit::{Topo, Walker};
10use thiserror::Error;
11
12use crate::core::HugrNode;
13use crate::extension::SignatureError;
14
15use crate::ops::constant::ConstTypeError;
16use crate::ops::custom::{ExtensionOp, OpaqueOpError};
17use crate::ops::validate::{
18    ChildrenEdgeData, ChildrenValidationError, EdgeValidationError, OpValidityFlags,
19};
20use crate::ops::{NamedOp, OpName, OpTag, OpTrait, OpType, ValidateOp};
21use crate::types::EdgeKind;
22use crate::types::type_param::TypeParam;
23use crate::{Direction, Port, Visibility};
24
25use super::internal::PortgraphNodeMap;
26use super::views::HugrView;
27
28/// Structure keeping track of pre-computed information used in the validation
29/// process.
30///
31/// TODO: Consider implementing updatable dominator trees and storing it in the
32/// Hugr to avoid recomputing it every time.
33pub(super) struct ValidationContext<'a, H: HugrView> {
34    hugr: &'a H,
35    /// Dominator tree for each CFG region, using the container node as index.
36    dominators: HashMap<H::Node, (Dominators<portgraph::NodeIndex>, H::RegionPortgraphNodes)>,
37}
38
39impl<'a, H: HugrView> ValidationContext<'a, H> {
40    /// Create a new validation context.
41    pub fn new(hugr: &'a H) -> Self {
42        let dominators = HashMap::new();
43        Self { hugr, dominators }
44    }
45
46    /// Check the validity of the HUGR.
47    pub fn validate(&mut self) -> Result<(), ValidationError<H::Node>> {
48        // Root node must be a root in the hierarchy.
49        if self.hugr.get_parent(self.hugr.module_root()).is_some() {
50            return Err(ValidationError::RootNotRoot {
51                node: self.hugr.module_root(),
52            });
53        }
54
55        // Node-specific checks
56        for node in self.hugr.nodes().map_into() {
57            self.validate_node(node)?;
58        }
59
60        // Hierarchy and children. No type variables declared by the module root.
61        self.validate_subtree(self.hugr.module_root(), &[])?;
62
63        self.validate_linkage()?;
64        // In tests we take the opportunity to verify that the hugr
65        // serialization round-trips. We verify the schema of the serialization
66        // format only when an environment variable is set. This allows
67        // a developer to modify the definition of serialized types locally
68        // without having to change the schema.
69        #[cfg(all(test, not(miri)))]
70        {
71            use crate::envelope::EnvelopeConfig;
72            use crate::hugr::hugrmut::HugrMut;
73            use crate::hugr::views::ExtractionResult;
74
75            let (mut hugr, node_map) = self.hugr.extract_hugr(self.hugr.module_root());
76            hugr.set_entrypoint(node_map.extracted_node(self.hugr.entrypoint()));
77            // TODO: Currently fails when using `hugr-model`
78            //crate::envelope::test::check_hugr_roundtrip(&hugr, EnvelopeConfig::binary());
79            crate::envelope::test::check_hugr_roundtrip(&hugr, EnvelopeConfig::text());
80        }
81
82        Ok(())
83    }
84
85    fn validate_linkage(&self) -> Result<(), ValidationError<H::Node>> {
86        // Map from func_name, for visible funcs only, to *tuple of*
87        //    Node with that func_name,
88        //    Signature,
89        //    bool - true for FuncDefn
90        let mut node_sig_defn = HashMap::new();
91
92        for c in self.hugr.children(self.hugr.module_root()) {
93            let (func_name, sig, is_defn) = match self.hugr.get_optype(c) {
94                OpType::FuncDecl(fd) if fd.visibility() == &Visibility::Public => {
95                    (fd.func_name(), fd.signature(), false)
96                }
97                OpType::FuncDefn(fd) if fd.visibility() == &Visibility::Public => {
98                    (fd.func_name(), fd.signature(), true)
99                }
100                _ => continue,
101            };
102            match node_sig_defn.entry(func_name) {
103                Entry::Vacant(ve) => {
104                    ve.insert((c, sig, is_defn));
105                }
106                Entry::Occupied(oe) => {
107                    // Allow two decls of the same sig (aliasing - we are allowing some laziness here).
108                    // Reject if at least one Defn - either two conflicting impls,
109                    //                               or Decl+Defn which should have been linked
110                    let (prev_c, prev_sig, prev_defn) = oe.get();
111                    if prev_sig != &sig || is_defn || *prev_defn {
112                        return Err(ValidationError::DuplicateExport {
113                            link_name: func_name.clone(),
114                            children: [*prev_c, c],
115                        });
116                    };
117                }
118            }
119        }
120        Ok(())
121    }
122
123    /// Compute the dominator tree for a CFG region, identified by its container
124    /// node.
125    ///
126    /// The results of this computation should be cached in `self.dominators`.
127    /// We don't do it here to avoid mutable borrows.
128    fn compute_dominator(
129        &self,
130        parent: H::Node,
131    ) -> (Dominators<portgraph::NodeIndex>, H::RegionPortgraphNodes) {
132        let (region, node_map) = self.hugr.region_portgraph(parent);
133        let entry_node = self.hugr.children(parent).next().unwrap();
134        let doms = dominators::simple_fast(&region, node_map.to_portgraph(entry_node));
135        (doms, node_map)
136    }
137
138    /// Check the constraints on a single node.
139    ///
140    /// This includes:
141    /// - Matching the number of ports with the signature
142    /// - Dataflow ports are correct. See `validate_df_port`
143    fn validate_node(&self, node: H::Node) -> Result<(), ValidationError<H::Node>> {
144        let op_type = self.hugr.get_optype(node);
145
146        if let OpType::OpaqueOp(opaque) = op_type {
147            Err(OpaqueOpError::UnresolvedOp(
148                node,
149                opaque.unqualified_id().clone(),
150                opaque.extension().clone(),
151            ))?;
152        }
153        // The Hugr can have only one root node.
154
155        for dir in Direction::BOTH {
156            // Check that we have the correct amount of ports and edges.
157            let num_ports = self.hugr.num_ports(node, dir);
158            if num_ports != op_type.port_count(dir) {
159                return Err(ValidationError::WrongNumberOfPorts {
160                    node,
161                    optype: Box::new(op_type.clone()),
162                    actual: num_ports,
163                    expected: op_type.port_count(dir),
164                    dir,
165                });
166            }
167        }
168
169        if node != self.hugr.module_root() {
170            let Some(parent) = self.hugr.get_parent(node) else {
171                return Err(ValidationError::NoParent { node });
172            };
173
174            let parent_optype = self.hugr.get_optype(parent);
175            let allowed_children = parent_optype.validity_flags::<H::Node>().allowed_children;
176            if !allowed_children.is_superset(op_type.tag()) {
177                return Err(ValidationError::InvalidParentOp {
178                    child: node,
179                    child_optype: Box::new(op_type.clone()),
180                    parent,
181                    parent_optype: Box::new(parent_optype.clone()),
182                    allowed_children,
183                });
184            }
185        }
186
187        // Entrypoints must be region containers.
188        if node == self.hugr.entrypoint() {
189            let validity_flags: OpValidityFlags = op_type.validity_flags();
190            if validity_flags.allowed_children == OpTag::None {
191                return Err(ValidationError::EntrypointNotContainer {
192                    node,
193                    optype: Box::new(op_type.clone()),
194                });
195            }
196        }
197
198        // Thirdly that the node has correct children
199        self.validate_children(node, op_type)?;
200
201        // OpType-specific checks.
202        // TODO Maybe we should delegate these checks to the OpTypes themselves.
203        if let OpType::Const(c) = op_type {
204            c.validate()?;
205        }
206
207        Ok(())
208    }
209
210    /// Check whether a port is valid.
211    /// - Input ports and output linear ports must be connected
212    /// - The linked port must have a compatible type.
213    fn validate_port(
214        &mut self,
215        node: H::Node,
216        port: Port,
217        op_type: &OpType,
218        var_decls: &[TypeParam],
219    ) -> Result<(), ValidationError<H::Node>> {
220        let port_kind = op_type.port_kind(port).unwrap();
221        let dir = port.direction();
222
223        let mut links = self.hugr.linked_ports(node, port).peekable();
224        // Linear dataflow values must be used, and control must have somewhere to flow.
225        let outgoing_is_unique = port_kind.is_linear() || port_kind == EdgeKind::ControlFlow;
226        // All dataflow wires must have a unique source.
227        let incoming_is_unique = port_kind.is_value() || port_kind.is_const();
228        let must_be_connected = match dir {
229            // Incoming ports must be connected, except for state order ports, branch case nodes,
230            // and CFG nodes.
231            Direction::Incoming => {
232                port_kind != EdgeKind::StateOrder
233                    && port_kind != EdgeKind::ControlFlow
234                    && op_type.tag() != OpTag::Case
235            }
236            Direction::Outgoing => outgoing_is_unique,
237        };
238        if must_be_connected && links.peek().is_none() {
239            return Err(ValidationError::UnconnectedPort {
240                node,
241                port,
242                port_kind: Box::new(port_kind),
243            });
244        }
245
246        // Avoid double checking connected port types.
247        if dir == Direction::Incoming {
248            if incoming_is_unique && links.nth(1).is_some() {
249                return Err(ValidationError::TooManyConnections {
250                    node,
251                    port,
252                    port_kind: Box::new(port_kind),
253                });
254            }
255            return Ok(());
256        }
257
258        self.validate_port_kind(&port_kind, var_decls)
259            .map_err(|cause| ValidationError::SignatureError {
260                node,
261                op: op_type.name(),
262                cause,
263            })?;
264
265        let mut link_cnt = 0;
266        for (other_node, other_offset) in links {
267            link_cnt += 1;
268            if outgoing_is_unique && link_cnt > 1 {
269                return Err(ValidationError::TooManyConnections {
270                    node,
271                    port,
272                    port_kind: Box::new(port_kind),
273                });
274            }
275
276            let other_op = self.hugr.get_optype(other_node);
277            let Some(other_kind) = other_op.port_kind(other_offset) else {
278                panic!(
279                    "The number of ports in {other_node} does not match the operation definition. This should have been caught by `validate_node`."
280                );
281            };
282            if other_kind != port_kind {
283                return Err(ValidationError::IncompatiblePorts {
284                    from: node,
285                    from_port: port,
286                    from_kind: Box::new(port_kind),
287                    to: other_node,
288                    to_port: other_offset,
289                    to_kind: Box::new(other_kind),
290                });
291            }
292
293            self.validate_edge(node, port, op_type, other_node, other_offset)?;
294        }
295
296        Ok(())
297    }
298
299    fn validate_port_kind(
300        &self,
301        port_kind: &EdgeKind,
302        var_decls: &[TypeParam],
303    ) -> Result<(), SignatureError> {
304        match &port_kind {
305            EdgeKind::Value(ty) => ty.validate(var_decls),
306            // Static edges must *not* refer to type variables declared by enclosing FuncDefns
307            // as these are only types at runtime.
308            EdgeKind::Const(ty) => ty.validate(&[]),
309            EdgeKind::Function(pf) => pf.validate(),
310            _ => Ok(()),
311        }
312    }
313
314    /// Check operation-specific constraints.
315    ///
316    /// These are flags defined for each operation type as an [`OpValidityFlags`] object.
317    fn validate_children(
318        &self,
319        node: H::Node,
320        op_type: &OpType,
321    ) -> Result<(), ValidationError<H::Node>> {
322        let flags = op_type.validity_flags();
323
324        if self.hugr.children(node).count() > 0 {
325            if flags.allowed_children.is_empty() {
326                return Err(ValidationError::NonContainerWithChildren {
327                    node,
328                    optype: Box::new(op_type.clone()),
329                });
330            }
331
332            let all_children = self.hugr.children(node);
333            let mut first_two_children = all_children.clone().take(2);
334            let first_child = self.hugr.get_optype(first_two_children.next().unwrap());
335            if !flags.allowed_first_child.is_superset(first_child.tag()) {
336                return Err(ValidationError::InvalidInitialChild {
337                    parent: node,
338                    parent_optype: Box::new(op_type.clone()),
339                    optype: Box::new(first_child.clone()),
340                    expected: flags.allowed_first_child,
341                    position: "first",
342                });
343            }
344
345            if let Some(second_child) = first_two_children
346                .next()
347                .map(|child| self.hugr.get_optype(child))
348            {
349                if !flags.allowed_second_child.is_superset(second_child.tag()) {
350                    return Err(ValidationError::InvalidInitialChild {
351                        parent: node,
352                        parent_optype: Box::new(op_type.clone()),
353                        optype: Box::new(second_child.clone()),
354                        expected: flags.allowed_second_child,
355                        position: "second",
356                    });
357                }
358            }
359            // Additional validations running over the full list of children optypes
360            let children_optypes = all_children.map(|c| (c, self.hugr.get_optype(c)));
361            if let Err(source) = op_type.validate_op_children(children_optypes) {
362                return Err(ValidationError::InvalidChildren {
363                    parent: node,
364                    parent_optype: Box::new(op_type.clone()),
365                    source,
366                });
367            }
368
369            // Additional validations running over the edges of the contained graph
370            if let Some(edge_check) = flags.edge_check {
371                for source in self.hugr.children(node) {
372                    for target in self.hugr.output_neighbours(source) {
373                        if self.hugr.get_parent(target) != Some(node) {
374                            continue;
375                        }
376                        let source_op = self.hugr.get_optype(source);
377                        let target_op = self.hugr.get_optype(target);
378                        for [source_port, target_port] in self.hugr.node_connections(source, target)
379                        {
380                            let edge_data = ChildrenEdgeData {
381                                source,
382                                target,
383                                source_port,
384                                target_port,
385                                source_op: source_op.clone(),
386                                target_op: target_op.clone(),
387                            };
388                            if let Err(source) = edge_check(edge_data) {
389                                return Err(ValidationError::InvalidEdges {
390                                    parent: node,
391                                    parent_optype: Box::new(op_type.clone()),
392                                    source,
393                                });
394                            }
395                        }
396                    }
397                }
398            }
399
400            if flags.requires_dag {
401                self.validate_children_dag(node, op_type)?;
402            }
403        } else if flags.requires_children {
404            return Err(ValidationError::ContainerWithoutChildren {
405                node,
406                optype: Box::new(op_type.clone()),
407            });
408        }
409
410        Ok(())
411    }
412
413    /// Ensure that the children of a node form a directed acyclic graph.
414    ///
415    /// Inter-graph edges are ignored. Only internal dataflow, constant, or
416    /// state order edges are considered.
417    fn validate_children_dag(
418        &self,
419        parent: H::Node,
420        op_type: &OpType,
421    ) -> Result<(), ValidationError<H::Node>> {
422        if self.hugr.children(parent).next().is_none() {
423            // No children, nothing to do
424            return Ok(());
425        }
426
427        let (region, node_map) = self.hugr.region_portgraph(parent);
428        let postorder = Topo::new(&region);
429        let nodes_visited = postorder
430            .iter(&region)
431            .filter(|n| *n != node_map.to_portgraph(parent))
432            .count();
433        let node_count = self.hugr.children(parent).count();
434        if nodes_visited != node_count {
435            return Err(ValidationError::NotADag {
436                node: parent,
437                optype: Box::new(op_type.clone()),
438            });
439        }
440
441        Ok(())
442    }
443
444    /// Check the edge is valid, i.e. the source/target nodes are at appropriate
445    /// positions in the hierarchy for some locality:
446    /// - Local edges, of any kind;
447    /// - External edges, for static and value edges only: from a node to a sibling's descendant.
448    ///   For Value edges, there must also be an order edge between the copy and the sibling.
449    /// - Dominator edges, for value edges only: from a node in a `BasicBlock` node to
450    ///   a descendant of a post-dominating sibling of the `BasicBlock`.
451    fn validate_edge(
452        &mut self,
453        from: H::Node,
454        from_offset: Port,
455        from_optype: &OpType,
456        to: H::Node,
457        to_offset: Port,
458    ) -> Result<(), InterGraphEdgeError<H::Node>> {
459        let from_parent = self
460            .hugr
461            .get_parent(from)
462            .expect("Root nodes cannot have ports");
463        let to_parent = self.hugr.get_parent(to);
464        let edge_kind = from_optype.port_kind(from_offset).unwrap();
465        if Some(from_parent) == to_parent {
466            return Ok(()); // Local edge
467        }
468        let is_static = edge_kind.is_static();
469        if !is_static && !matches!(&edge_kind, EdgeKind::Value(t) if t.copyable()) {
470            return Err(InterGraphEdgeError::NonCopyableData {
471                from,
472                from_offset,
473                to,
474                to_offset,
475                ty: Box::new(edge_kind),
476            });
477        }
478
479        // To detect either external or dominator edges, we traverse the ancestors
480        // of the target until we find either `from_parent` (in the external
481        // case), or the parent of `from_parent` (in the dominator case).
482        //
483        // This search could be sped-up with a pre-computed LCA structure, but
484        // for valid Hugrs this search should be very short.
485        let from_parent_parent = self.hugr.get_parent(from_parent);
486        for (ancestor, ancestor_parent) in
487            iter::successors(to_parent, |&p| self.hugr.get_parent(p)).tuple_windows()
488        {
489            if ancestor_parent == from_parent {
490                // External edge.
491                if !is_static {
492                    // Must have an order edge.
493                    self.hugr
494                        .node_connections(from, ancestor)
495                        .find(|&[p, _]| from_optype.port_kind(p) == Some(EdgeKind::StateOrder))
496                        .ok_or(InterGraphEdgeError::MissingOrderEdge {
497                            from,
498                            from_offset,
499                            to,
500                            to_offset,
501                            to_ancestor: ancestor,
502                        })?;
503                }
504                return Ok(());
505            } else if Some(ancestor_parent) == from_parent_parent && !is_static {
506                // Dominator edge
507                let ancestor_parent_op = self.hugr.get_optype(ancestor_parent);
508                if ancestor_parent_op.tag() != OpTag::Cfg {
509                    return Err(InterGraphEdgeError::NonCFGAncestor {
510                        from,
511                        from_offset,
512                        to,
513                        to_offset,
514                        ancestor_parent_op: Box::new(ancestor_parent_op.clone()),
515                    });
516                }
517
518                // Check domination
519                let (dominator_tree, node_map) =
520                    if let Some(tree) = self.dominators.get(&ancestor_parent) {
521                        tree
522                    } else {
523                        let (tree, node_map) = self.compute_dominator(ancestor_parent);
524                        self.dominators.insert(ancestor_parent, (tree, node_map));
525                        self.dominators.get(&ancestor_parent).unwrap()
526                    };
527                if !dominator_tree
528                    .dominators(node_map.to_portgraph(ancestor))
529                    .is_some_and(|mut ds| ds.any(|n| n == node_map.to_portgraph(from_parent)))
530                {
531                    return Err(InterGraphEdgeError::NonDominatedAncestor {
532                        from,
533                        from_offset,
534                        to,
535                        to_offset,
536                        from_parent,
537                        ancestor,
538                    });
539                }
540
541                return Ok(());
542            }
543        }
544
545        Err(InterGraphEdgeError::NoRelation {
546            from,
547            from_offset,
548            to,
549            to_offset,
550        })
551    }
552
553    /// Validates that `TypeArgs` are valid wrt the [`ExtensionRegistry`] and that nodes
554    /// only refer to type variables declared by the closest enclosing `FuncDefn`.
555    fn validate_subtree(
556        &mut self,
557        node: H::Node,
558        var_decls: &[TypeParam],
559    ) -> Result<(), ValidationError<H::Node>> {
560        let op_type = self.hugr.get_optype(node);
561        // The op_type must be defined only in terms of type variables defined outside the node
562
563        let validate_ext = |ext_op: &ExtensionOp| -> Result<(), ValidationError<H::Node>> {
564            // Check TypeArgs are valid, and if we can, fit the declared TypeParams
565            ext_op
566                .def()
567                .validate_args(ext_op.args(), var_decls)
568                .map_err(|cause| ValidationError::SignatureError {
569                    node,
570                    op: op_type.name(),
571                    cause,
572                })
573        };
574        match op_type {
575            OpType::ExtensionOp(ext_op) => validate_ext(ext_op)?,
576            OpType::OpaqueOp(opaque) => {
577                Err(OpaqueOpError::UnresolvedOp(
578                    node,
579                    opaque.qualified_id(),
580                    opaque.extension().clone(),
581                ))?;
582            }
583            OpType::Call(c) => {
584                c.validate()
585                    .map_err(|cause| ValidationError::SignatureError {
586                        node,
587                        op: op_type.name(),
588                        cause,
589                    })?;
590            }
591            OpType::LoadFunction(c) => {
592                c.validate()
593                    .map_err(|cause| ValidationError::SignatureError {
594                        node,
595                        op: op_type.name(),
596                        cause,
597                    })?;
598            }
599            _ => (),
600        }
601
602        // Check port connections.
603        for dir in Direction::BOTH {
604            for port in self.hugr.node_ports(node, dir) {
605                self.validate_port(node, port, op_type, var_decls)?;
606            }
607        }
608
609        // For FuncDefn's, only the type variables declared by the FuncDefn can be referred to by nodes
610        // inside the function. (The same would be true for FuncDecl's, but they have no child nodes.)
611        let var_decls = if let OpType::FuncDefn(fd) = op_type {
612            fd.signature().params()
613        } else {
614            var_decls
615        };
616
617        for child in self.hugr.children(node) {
618            self.validate_subtree(child, var_decls)?;
619        }
620
621        Ok(())
622    }
623}
624
625/// Errors that can occur while validating a Hugr.
626#[derive(Debug, Clone, PartialEq, Error)]
627#[allow(missing_docs)]
628#[non_exhaustive]
629pub enum ValidationError<N: HugrNode> {
630    /// The root node of the Hugr is not a root in the hierarchy.
631    #[error("The root node of the Hugr ({node}) is not a root in the hierarchy.")]
632    RootNotRoot { node: N },
633    /// The node ports do not match the operation signature.
634    #[error(
635        "{node} has an invalid number of ports. The operation {optype} cannot have {actual} {dir:?} ports. Expected {expected}."
636    )]
637    WrongNumberOfPorts {
638        node: N,
639        optype: Box<OpType>,
640        actual: usize,
641        expected: usize,
642        dir: Direction,
643    },
644    /// A dataflow port is not connected.
645    #[error("{node} has an unconnected port {port} of type {port_kind}.")]
646    UnconnectedPort {
647        node: N,
648        port: Port,
649        port_kind: Box<EdgeKind>,
650    },
651    /// A linear port is connected to more than one thing.
652    #[error("{node} has a port {port} of type {port_kind} with more than one connection.")]
653    TooManyConnections {
654        node: N,
655        port: Port,
656        port_kind: Box<EdgeKind>,
657    },
658    /// Connected ports have different types, or non-unifiable types.
659    #[error(
660        "Connected ports {from_port} in {from} and {to_port} in {to} have incompatible kinds. Cannot connect {from_kind} to {to_kind}."
661    )]
662    IncompatiblePorts {
663        from: N,
664        from_port: Port,
665        from_kind: Box<EdgeKind>,
666        to: N,
667        to_port: Port,
668        to_kind: Box<EdgeKind>,
669    },
670    /// The non-root node has no parent.
671    #[error("{node} has no parent.")]
672    NoParent { node: N },
673    /// The parent node is not compatible with the child node.
674    #[error("The operation {parent_optype} cannot contain a {child_optype} as a child. Allowed children: {}. In {child} with parent {parent}.", allowed_children.description())]
675    InvalidParentOp {
676        child: N,
677        child_optype: Box<OpType>,
678        parent: N,
679        parent_optype: Box<OpType>,
680        allowed_children: OpTag,
681    },
682    /// Invalid first/second child.
683    #[error(
684        "A {optype} operation cannot be the {position} child of a {parent_optype}. Expected {expected}. In parent {parent}"
685    )]
686    InvalidInitialChild {
687        parent: N,
688        parent_optype: Box<OpType>,
689        optype: Box<OpType>,
690        expected: OpTag,
691        position: &'static str,
692    },
693    /// The children list has invalid elements.
694    #[error(
695        "An operation {parent_optype} contains invalid children: {source}. In parent {parent}, child {child}",
696        child=source.child(),
697    )]
698    InvalidChildren {
699        parent: N,
700        parent_optype: Box<OpType>,
701        source: ChildrenValidationError<N>,
702    },
703    /// Multiple, incompatible, nodes with [Visibility::Public] use the same `func_name`
704    /// in a [Module](super::Module). (Multiple [`FuncDecl`](crate::ops::FuncDecl)s with
705    /// the same signature are allowed)
706    #[error("FuncDefn/Decl {} is exported under same name {link_name} as earlier node {}", children[0], children[1])]
707    DuplicateExport {
708        /// The `func_name` of a public `FuncDecl` or `FuncDefn`
709        link_name: String,
710        /// Two nodes using that name
711        children: [N; 2],
712    },
713    /// The children graph has invalid edges.
714    #[error(
715        "An operation {parent_optype} contains invalid edges between its children: {source}. In parent {parent}, edge from {from:?} port {from_port:?} to {to:?} port {to_port:?}",
716        from=source.edge().source,
717        from_port=source.edge().source_port,
718        to=source.edge().target,
719        to_port=source.edge().target_port,
720    )]
721    InvalidEdges {
722        parent: N,
723        parent_optype: Box<OpType>,
724        source: EdgeValidationError<N>,
725    },
726    /// The node operation is not a container, but has children.
727    #[error("{node} with optype {optype} is not a container, but has children.")]
728    NonContainerWithChildren { node: N, optype: Box<OpType> },
729    /// The node must have children, but has none.
730    #[error("{node} with optype {optype} must have children, but has none.")]
731    ContainerWithoutChildren { node: N, optype: Box<OpType> },
732    /// The children of a node do not form a DAG.
733    #[error(
734        "The children of an operation {optype} must form a DAG. Loops are not allowed. In {node}."
735    )]
736    NotADag { node: N, optype: Box<OpType> },
737    /// There are invalid inter-graph edges.
738    #[error(transparent)]
739    InterGraphEdgeError(#[from] InterGraphEdgeError<N>),
740    /// A node claims to still be awaiting extension inference. Perhaps it is not acted upon by inference.
741    #[error(
742        "{node} needs a concrete ExtensionSet - inference will provide this for Case/CFG/Conditional/DataflowBlock/DFG/TailLoop only"
743    )]
744    ExtensionsNotInferred { node: N },
745    /// Error in a node signature
746    #[error("Error in signature of operation {op} at {node}: {cause}")]
747    SignatureError {
748        node: N,
749        op: OpName,
750        #[source]
751        cause: SignatureError,
752    },
753    /// Error in a [`ExtensionOp`] serialized as an [Opaque].
754    ///
755    /// [ExtensionOp]: crate::ops::ExtensionOp
756    /// [Opaque]: crate::ops::OpaqueOp
757    #[error(transparent)]
758    OpaqueOpError(#[from] OpaqueOpError<N>),
759    /// A [Const] contained a [Value] of unexpected [Type].
760    ///
761    /// [Const]: crate::ops::Const
762    /// [Value]: crate::ops::Value
763    /// [Type]: crate::types::Type
764    #[error(transparent)]
765    ConstTypeError(#[from] ConstTypeError),
766    /// The HUGR entrypoint must be a region container.
767    #[error("The HUGR entrypoint ({node}) must be a region container, but '{}' does not accept children.", optype.name())]
768    EntrypointNotContainer { node: N, optype: Box<OpType> },
769}
770
771/// Errors related to the inter-graph edge validations.
772#[derive(Debug, Clone, PartialEq, Error)]
773#[allow(missing_docs)]
774#[non_exhaustive]
775pub enum InterGraphEdgeError<N: HugrNode> {
776    /// Inter-Graph edges can only carry copyable data.
777    #[error(
778        "Inter-graph edges can only carry copyable data. In an inter-graph edge from {from} ({from_offset}) to {to} ({to_offset}) with type {ty}."
779    )]
780    NonCopyableData {
781        from: N,
782        from_offset: Port,
783        to: N,
784        to_offset: Port,
785        ty: Box<EdgeKind>,
786    },
787    /// The grandparent of a dominator inter-graph edge must be a CFG container.
788    #[error(
789        "The grandparent of a dominator inter-graph edge must be a CFG container. Found operation {ancestor_parent_op}. In a dominator inter-graph edge from {from} ({from_offset}) to {to} ({to_offset})."
790    )]
791    NonCFGAncestor {
792        from: N,
793        from_offset: Port,
794        to: N,
795        to_offset: Port,
796        ancestor_parent_op: Box<OpType>,
797    },
798    /// The sibling ancestors of the external inter-graph edge endpoints must be have an order edge between them.
799    #[error(
800        "Missing state order between the external inter-graph source {from} and the ancestor of the target {to_ancestor}. In an external inter-graph edge from {from} ({from_offset}) to {to} ({to_offset})."
801    )]
802    MissingOrderEdge {
803        from: N,
804        from_offset: Port,
805        to: N,
806        to_offset: Port,
807        to_ancestor: N,
808    },
809    /// The ancestors of an inter-graph edge are not related.
810    #[error(
811        "The ancestors of an inter-graph edge are not related. In an inter-graph edge from {from} ({from_offset}) to {to} ({to_offset})."
812    )]
813    NoRelation {
814        from: N,
815        from_offset: Port,
816        to: N,
817        to_offset: Port,
818    },
819    /// The basic block containing the source node does not dominate the basic block containing the target node.
820    #[error(
821        " The basic block containing the source node does not dominate the basic block containing the target node in the CFG. Expected {from_parent} to dominate {ancestor}. In a dominator inter-graph edge from {from} ({from_offset}) to {to} ({to_offset})."
822    )]
823    NonDominatedAncestor {
824        from: N,
825        from_offset: Port,
826        to: N,
827        to_offset: Port,
828        from_parent: N,
829        ancestor: N,
830    },
831}
832
833#[cfg(test)]
834pub(crate) mod test;
hugr_core/hugr/validate.rs

hugr_core/hugr/
validate.rs
