hugr_core/hugr/
validate.rs

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

hugr_core/hugr/
validate.rs
