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 outside the root.
61        self.validate_subtree(self.hugr.entrypoint(), &[])?;
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        //
604        // Root nodes are ignored, as they cannot have connected edges.
605        if node != self.hugr.entrypoint() {
606            for dir in Direction::BOTH {
607                for port in self.hugr.node_ports(node, dir) {
608                    self.validate_port(node, port, op_type, var_decls)?;
609                }
610            }
611        }
612
613        // For FuncDefn's, only the type variables declared by the FuncDefn can be referred to by nodes
614        // inside the function. (The same would be true for FuncDecl's, but they have no child nodes.)
615        let var_decls = if let OpType::FuncDefn(fd) = op_type {
616            fd.signature().params()
617        } else {
618            var_decls
619        };
620
621        for child in self.hugr.children(node) {
622            self.validate_subtree(child, var_decls)?;
623        }
624
625        Ok(())
626    }
627}
628
629/// Errors that can occur while validating a Hugr.
630#[derive(Debug, Clone, PartialEq, Error)]
631#[allow(missing_docs)]
632#[non_exhaustive]
633pub enum ValidationError<N: HugrNode> {
634    /// The root node of the Hugr is not a root in the hierarchy.
635    #[error("The root node of the Hugr ({node}) is not a root in the hierarchy.")]
636    RootNotRoot { node: N },
637    /// The node ports do not match the operation signature.
638    #[error(
639        "{node} has an invalid number of ports. The operation {optype} cannot have {actual} {dir:?} ports. Expected {expected}."
640    )]
641    WrongNumberOfPorts {
642        node: N,
643        optype: Box<OpType>,
644        actual: usize,
645        expected: usize,
646        dir: Direction,
647    },
648    /// A dataflow port is not connected.
649    #[error("{node} has an unconnected port {port} of type {port_kind}.")]
650    UnconnectedPort {
651        node: N,
652        port: Port,
653        port_kind: Box<EdgeKind>,
654    },
655    /// A linear port is connected to more than one thing.
656    #[error("{node} has a port {port} of type {port_kind} with more than one connection.")]
657    TooManyConnections {
658        node: N,
659        port: Port,
660        port_kind: Box<EdgeKind>,
661    },
662    /// Connected ports have different types, or non-unifiable types.
663    #[error(
664        "Connected ports {from_port} in {from} and {to_port} in {to} have incompatible kinds. Cannot connect {from_kind} to {to_kind}."
665    )]
666    IncompatiblePorts {
667        from: N,
668        from_port: Port,
669        from_kind: Box<EdgeKind>,
670        to: N,
671        to_port: Port,
672        to_kind: Box<EdgeKind>,
673    },
674    /// The non-root node has no parent.
675    #[error("{node} has no parent.")]
676    NoParent { node: N },
677    /// The parent node is not compatible with the child node.
678    #[error("The operation {parent_optype} cannot contain a {child_optype} as a child. Allowed children: {}. In {child} with parent {parent}.", allowed_children.description())]
679    InvalidParentOp {
680        child: N,
681        child_optype: Box<OpType>,
682        parent: N,
683        parent_optype: Box<OpType>,
684        allowed_children: OpTag,
685    },
686    /// Invalid first/second child.
687    #[error(
688        "A {optype} operation cannot be the {position} child of a {parent_optype}. Expected {expected}. In parent {parent}"
689    )]
690    InvalidInitialChild {
691        parent: N,
692        parent_optype: Box<OpType>,
693        optype: Box<OpType>,
694        expected: OpTag,
695        position: &'static str,
696    },
697    /// The children list has invalid elements.
698    #[error(
699        "An operation {parent_optype} contains invalid children: {source}. In parent {parent}, child {child}",
700        child=source.child(),
701    )]
702    InvalidChildren {
703        parent: N,
704        parent_optype: Box<OpType>,
705        source: ChildrenValidationError<N>,
706    },
707    /// Multiple, incompatible, nodes with [Visibility::Public] use the same `func_name`
708    /// in a [Module](super::Module). (Multiple [`FuncDecl`](crate::ops::FuncDecl)s with
709    /// the same signature are allowed)
710    #[error("FuncDefn/Decl {} is exported under same name {link_name} as earlier node {}", children[0], children[1])]
711    DuplicateExport {
712        /// The `func_name` of a public `FuncDecl` or `FuncDefn`
713        link_name: String,
714        /// Two nodes using that name
715        children: [N; 2],
716    },
717    /// The children graph has invalid edges.
718    #[error(
719        "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:?}",
720        from=source.edge().source,
721        from_port=source.edge().source_port,
722        to=source.edge().target,
723        to_port=source.edge().target_port,
724    )]
725    InvalidEdges {
726        parent: N,
727        parent_optype: Box<OpType>,
728        source: EdgeValidationError<N>,
729    },
730    /// The node operation is not a container, but has children.
731    #[error("{node} with optype {optype} is not a container, but has children.")]
732    NonContainerWithChildren { node: N, optype: Box<OpType> },
733    /// The node must have children, but has none.
734    #[error("{node} with optype {optype} must have children, but has none.")]
735    ContainerWithoutChildren { node: N, optype: Box<OpType> },
736    /// The children of a node do not form a DAG.
737    #[error(
738        "The children of an operation {optype} must form a DAG. Loops are not allowed. In {node}."
739    )]
740    NotADag { node: N, optype: Box<OpType> },
741    /// There are invalid inter-graph edges.
742    #[error(transparent)]
743    InterGraphEdgeError(#[from] InterGraphEdgeError<N>),
744    /// A node claims to still be awaiting extension inference. Perhaps it is not acted upon by inference.
745    #[error(
746        "{node} needs a concrete ExtensionSet - inference will provide this for Case/CFG/Conditional/DataflowBlock/DFG/TailLoop only"
747    )]
748    ExtensionsNotInferred { node: N },
749    /// Error in a node signature
750    #[error("Error in signature of operation {op} at {node}: {cause}")]
751    SignatureError {
752        node: N,
753        op: OpName,
754        #[source]
755        cause: SignatureError,
756    },
757    /// Error in a [`ExtensionOp`] serialized as an [Opaque].
758    ///
759    /// [ExtensionOp]: crate::ops::ExtensionOp
760    /// [Opaque]: crate::ops::OpaqueOp
761    #[error(transparent)]
762    OpaqueOpError(#[from] OpaqueOpError<N>),
763    /// A [Const] contained a [Value] of unexpected [Type].
764    ///
765    /// [Const]: crate::ops::Const
766    /// [Value]: crate::ops::Value
767    /// [Type]: crate::types::Type
768    #[error(transparent)]
769    ConstTypeError(#[from] ConstTypeError),
770    /// The HUGR entrypoint must be a region container.
771    #[error("The HUGR entrypoint ({node}) must be a region container, but '{}' does not accept children.", optype.name())]
772    EntrypointNotContainer { node: N, optype: Box<OpType> },
773}
774
775/// Errors related to the inter-graph edge validations.
776#[derive(Debug, Clone, PartialEq, Error)]
777#[allow(missing_docs)]
778#[non_exhaustive]
779pub enum InterGraphEdgeError<N: HugrNode> {
780    /// Inter-Graph edges can only carry copyable data.
781    #[error(
782        "Inter-graph edges can only carry copyable data. In an inter-graph edge from {from} ({from_offset}) to {to} ({to_offset}) with type {ty}."
783    )]
784    NonCopyableData {
785        from: N,
786        from_offset: Port,
787        to: N,
788        to_offset: Port,
789        ty: Box<EdgeKind>,
790    },
791    /// The grandparent of a dominator inter-graph edge must be a CFG container.
792    #[error(
793        "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})."
794    )]
795    NonCFGAncestor {
796        from: N,
797        from_offset: Port,
798        to: N,
799        to_offset: Port,
800        ancestor_parent_op: Box<OpType>,
801    },
802    /// The sibling ancestors of the external inter-graph edge endpoints must be have an order edge between them.
803    #[error(
804        "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})."
805    )]
806    MissingOrderEdge {
807        from: N,
808        from_offset: Port,
809        to: N,
810        to_offset: Port,
811        to_ancestor: N,
812    },
813    /// The ancestors of an inter-graph edge are not related.
814    #[error(
815        "The ancestors of an inter-graph edge are not related. In an inter-graph edge from {from} ({from_offset}) to {to} ({to_offset})."
816    )]
817    NoRelation {
818        from: N,
819        from_offset: Port,
820        to: N,
821        to_offset: Port,
822    },
823    /// The basic block containing the source node does not dominate the basic block containing the target node.
824    #[error(
825        " 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})."
826    )]
827    NonDominatedAncestor {
828        from: N,
829        from_offset: Port,
830        to: N,
831        to_offset: Port,
832        from_parent: N,
833        ancestor: N,
834    },
835}
836
837#[cfg(test)]
838pub(crate) mod test;
hugr_core/hugr/validate.rs

hugr_core/hugr/
validate.rs
