hugr_core/hugr/
views.rs

1//! Read-only access into HUGR graphs and subgraphs.
2
3pub mod descendants;
4mod impls;
5pub mod petgraph;
6pub mod render;
7mod root_checked;
8pub mod sibling;
9pub mod sibling_subgraph;
10
11#[cfg(test)]
12mod tests;
13
14use std::borrow::Cow;
15
16pub use self::petgraph::PetgraphWrapper;
17use self::render::RenderConfig;
18pub use descendants::DescendantsGraph;
19pub use root_checked::RootChecked;
20pub use sibling::SiblingGraph;
21pub use sibling_subgraph::SiblingSubgraph;
22
23use itertools::Itertools;
24use portgraph::render::{DotFormat, MermaidFormat};
25use portgraph::{LinkView, PortView};
26
27use super::internal::HugrInternals;
28use super::{
29    Hugr, HugrError, HugrMut, Node, NodeMetadata, NodeMetadataMap, ValidationError, DEFAULT_OPTYPE,
30};
31use crate::extension::ExtensionRegistry;
32use crate::ops::handle::NodeHandle;
33use crate::ops::{OpParent, OpTag, OpTrait, OpType};
34
35use crate::types::{EdgeKind, PolyFuncType, Signature, Type};
36use crate::{Direction, IncomingPort, OutgoingPort, Port};
37
38use itertools::Either;
39
40/// A trait for inspecting HUGRs.
41/// For end users we intend this to be superseded by region-specific APIs.
42pub trait HugrView: HugrInternals {
43    /// Return the root node of this view.
44    #[inline]
45    fn root(&self) -> Self::Node {
46        self.root_node()
47    }
48
49    /// Return the type of the HUGR root node.
50    #[inline]
51    fn root_type(&self) -> &OpType {
52        let node_type = self.get_optype(self.root());
53        // Sadly no way to do this at present
54        // debug_assert!(Self::RootHandle::can_hold(node_type.tag()));
55        node_type
56    }
57
58    /// Returns whether the node exists.
59    fn contains_node(&self, node: Self::Node) -> bool;
60
61    /// Validates that a node is valid in the graph.
62    #[inline]
63    fn valid_node(&self, node: Self::Node) -> bool {
64        self.contains_node(node)
65    }
66
67    /// Validates that a node is a valid root descendant in the graph.
68    ///
69    /// To include the root node use [`HugrView::valid_node`] instead.
70    #[inline]
71    fn valid_non_root(&self, node: Self::Node) -> bool {
72        self.root() != node && self.valid_node(node)
73    }
74
75    /// Returns the parent of a node.
76    #[inline]
77    fn get_parent(&self, node: Self::Node) -> Option<Self::Node> {
78        if !self.valid_non_root(node) {
79            return None;
80        };
81        self.base_hugr()
82            .hierarchy
83            .parent(self.get_pg_index(node))
84            .map(|index| self.get_node(index))
85    }
86
87    /// Returns the operation type of a node.
88    #[inline]
89    fn get_optype(&self, node: Self::Node) -> &OpType {
90        match self.contains_node(node) {
91            true => self.base_hugr().op_types.get(self.get_pg_index(node)),
92            false => &DEFAULT_OPTYPE,
93        }
94    }
95
96    /// Returns the metadata associated with a node.
97    #[inline]
98    fn get_metadata(&self, node: Self::Node, key: impl AsRef<str>) -> Option<&NodeMetadata> {
99        match self.contains_node(node) {
100            true => self.get_node_metadata(node)?.get(key.as_ref()),
101            false => None,
102        }
103    }
104
105    /// Retrieve the complete metadata map for a node.
106    fn get_node_metadata(&self, node: Self::Node) -> Option<&NodeMetadataMap> {
107        if !self.valid_node(node) {
108            return None;
109        }
110        self.base_hugr()
111            .metadata
112            .get(self.get_pg_index(node))
113            .as_ref()
114    }
115
116    /// Returns the number of nodes in the hugr.
117    fn node_count(&self) -> usize;
118
119    /// Returns the number of edges in the hugr.
120    fn edge_count(&self) -> usize;
121
122    /// Iterates over the nodes in the port graph.
123    fn nodes(&self) -> impl Iterator<Item = Self::Node> + Clone;
124
125    /// Iterator over ports of node in a given direction.
126    fn node_ports(&self, node: Self::Node, dir: Direction) -> impl Iterator<Item = Port> + Clone;
127
128    /// Iterator over output ports of node.
129    /// Like [`node_ports`][HugrView::node_ports]`(node, Direction::Outgoing)`
130    /// but preserves knowledge that the ports are [OutgoingPort]s.
131    #[inline]
132    fn node_outputs(&self, node: Self::Node) -> impl Iterator<Item = OutgoingPort> + Clone {
133        self.node_ports(node, Direction::Outgoing)
134            .map(|p| p.as_outgoing().unwrap())
135    }
136
137    /// Iterator over inputs ports of node.
138    /// Like [`node_ports`][HugrView::node_ports]`(node, Direction::Incoming)`
139    /// but preserves knowledge that the ports are [IncomingPort]s.
140    #[inline]
141    fn node_inputs(&self, node: Self::Node) -> impl Iterator<Item = IncomingPort> + Clone {
142        self.node_ports(node, Direction::Incoming)
143            .map(|p| p.as_incoming().unwrap())
144    }
145
146    /// Iterator over both the input and output ports of node.
147    fn all_node_ports(&self, node: Self::Node) -> impl Iterator<Item = Port> + Clone;
148
149    /// Iterator over the nodes and ports connected to a port.
150    fn linked_ports(
151        &self,
152        node: Self::Node,
153        port: impl Into<Port>,
154    ) -> impl Iterator<Item = (Self::Node, Port)> + Clone;
155
156    /// Iterator over all the nodes and ports connected to a node in a given direction.
157    fn all_linked_ports(
158        &self,
159        node: Self::Node,
160        dir: Direction,
161    ) -> Either<
162        impl Iterator<Item = (Self::Node, OutgoingPort)>,
163        impl Iterator<Item = (Self::Node, IncomingPort)>,
164    > {
165        match dir {
166            Direction::Incoming => Either::Left(
167                self.node_inputs(node)
168                    .flat_map(move |port| self.linked_outputs(node, port)),
169            ),
170            Direction::Outgoing => Either::Right(
171                self.node_outputs(node)
172                    .flat_map(move |port| self.linked_inputs(node, port)),
173            ),
174        }
175    }
176
177    /// Iterator over all the nodes and ports connected to a node's inputs.
178    fn all_linked_outputs(
179        &self,
180        node: Self::Node,
181    ) -> impl Iterator<Item = (Self::Node, OutgoingPort)> {
182        self.all_linked_ports(node, Direction::Incoming)
183            .left()
184            .unwrap()
185    }
186
187    /// Iterator over all the nodes and ports connected to a node's outputs.
188    fn all_linked_inputs(
189        &self,
190        node: Self::Node,
191    ) -> impl Iterator<Item = (Self::Node, IncomingPort)> {
192        self.all_linked_ports(node, Direction::Outgoing)
193            .right()
194            .unwrap()
195    }
196
197    /// If there is exactly one port connected to this port, return
198    /// it and its node.
199    fn single_linked_port(
200        &self,
201        node: Self::Node,
202        port: impl Into<Port>,
203    ) -> Option<(Self::Node, Port)> {
204        self.linked_ports(node, port).exactly_one().ok()
205    }
206
207    /// If there is exactly one OutgoingPort connected to this IncomingPort, return
208    /// it and its node.
209    fn single_linked_output(
210        &self,
211        node: Self::Node,
212        port: impl Into<IncomingPort>,
213    ) -> Option<(Self::Node, OutgoingPort)> {
214        self.single_linked_port(node, port.into())
215            .map(|(n, p)| (n, p.as_outgoing().unwrap()))
216    }
217
218    /// If there is exactly one IncomingPort connected to this OutgoingPort, return
219    /// it and its node.
220    fn single_linked_input(
221        &self,
222        node: Self::Node,
223        port: impl Into<OutgoingPort>,
224    ) -> Option<(Self::Node, IncomingPort)> {
225        self.single_linked_port(node, port.into())
226            .map(|(n, p)| (n, p.as_incoming().unwrap()))
227    }
228    /// Iterator over the nodes and output ports connected to a given *input* port.
229    /// Like [`linked_ports`][HugrView::linked_ports] but preserves knowledge
230    /// that the linked ports are [OutgoingPort]s.
231    fn linked_outputs(
232        &self,
233        node: Self::Node,
234        port: impl Into<IncomingPort>,
235    ) -> impl Iterator<Item = (Self::Node, OutgoingPort)> {
236        self.linked_ports(node, port.into())
237            .map(|(n, p)| (n, p.as_outgoing().unwrap()))
238    }
239
240    /// Iterator over the nodes and input ports connected to a given *output* port
241    /// Like [`linked_ports`][HugrView::linked_ports] but preserves knowledge
242    /// that the linked ports are [IncomingPort]s.
243    fn linked_inputs(
244        &self,
245        node: Self::Node,
246        port: impl Into<OutgoingPort>,
247    ) -> impl Iterator<Item = (Self::Node, IncomingPort)> {
248        self.linked_ports(node, port.into())
249            .map(|(n, p)| (n, p.as_incoming().unwrap()))
250    }
251
252    /// Iterator the links between two nodes.
253    fn node_connections(
254        &self,
255        node: Self::Node,
256        other: Self::Node,
257    ) -> impl Iterator<Item = [Port; 2]> + Clone;
258
259    /// Returns whether a port is connected.
260    fn is_linked(&self, node: Self::Node, port: impl Into<Port>) -> bool {
261        self.linked_ports(node, port).next().is_some()
262    }
263
264    /// Number of ports in node for a given direction.
265    fn num_ports(&self, node: Self::Node, dir: Direction) -> usize;
266
267    /// Number of inputs to a node.
268    /// Shorthand for [`num_ports`][HugrView::num_ports]`(node, Direction::Incoming)`.
269    #[inline]
270    fn num_inputs(&self, node: Self::Node) -> usize {
271        self.num_ports(node, Direction::Incoming)
272    }
273
274    /// Number of outputs from a node.
275    /// Shorthand for [`num_ports`][HugrView::num_ports]`(node, Direction::Outgoing)`.
276    #[inline]
277    fn num_outputs(&self, node: Self::Node) -> usize {
278        self.num_ports(node, Direction::Outgoing)
279    }
280
281    /// Return iterator over the direct children of node.
282    fn children(&self, node: Self::Node) -> impl DoubleEndedIterator<Item = Self::Node> + Clone;
283
284    /// Returns the first child of the specified node (if it is a parent).
285    /// Useful because `x.children().next()` leaves x borrowed.
286    fn first_child(&self, node: Self::Node) -> Option<Self::Node> {
287        self.children(node).next()
288    }
289
290    /// Iterates over neighbour nodes in the given direction.
291    /// May contain duplicates if the graph has multiple links between nodes.
292    fn neighbours(
293        &self,
294        node: Self::Node,
295        dir: Direction,
296    ) -> impl Iterator<Item = Self::Node> + Clone;
297
298    /// Iterates over the input neighbours of the `node`.
299    /// Shorthand for [`neighbours`][HugrView::neighbours]`(node, Direction::Incoming)`.
300    #[inline]
301    fn input_neighbours(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> + Clone {
302        self.neighbours(node, Direction::Incoming)
303    }
304
305    /// Iterates over the output neighbours of the `node`.
306    /// Shorthand for [`neighbours`][HugrView::neighbours]`(node, Direction::Outgoing)`.
307    #[inline]
308    fn output_neighbours(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> + Clone {
309        self.neighbours(node, Direction::Outgoing)
310    }
311
312    /// Iterates over the input and output neighbours of the `node` in sequence.
313    fn all_neighbours(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> + Clone;
314
315    /// Get the input and output child nodes of a dataflow parent.
316    /// If the node isn't a dataflow parent, then return None
317    #[inline]
318    fn get_io(&self, node: Self::Node) -> Option<[Self::Node; 2]> {
319        let op = self.get_optype(node);
320        // Nodes outside the view have no children (and a non-DataflowParent OpType::default())
321        if OpTag::DataflowParent.is_superset(op.tag()) {
322            self.children(node).take(2).collect_vec().try_into().ok()
323        } else {
324            None
325        }
326    }
327
328    /// Returns the function type defined by this dataflow HUGR.
329    ///
330    /// If the root of the Hugr is a
331    /// [`DataflowParent`][crate::ops::DataflowParent] operation, report the
332    /// signature corresponding to the input and output node of its sibling
333    /// graph. Otherwise, returns `None`.
334    ///
335    /// In contrast to [`poly_func_type`][HugrView::poly_func_type], this
336    /// method always return a concrete [`Signature`].
337    fn inner_function_type(&self) -> Option<Cow<'_, Signature>> {
338        self.root_type().inner_function_type()
339    }
340
341    /// Returns the function type defined by this HUGR, i.e. `Some` iff the root is
342    /// a [`FuncDecl`][crate::ops::FuncDecl] or [`FuncDefn`][crate::ops::FuncDefn].
343    fn poly_func_type(&self) -> Option<PolyFuncType> {
344        match self.root_type() {
345            OpType::FuncDecl(decl) => Some(decl.signature.clone()),
346            OpType::FuncDefn(defn) => Some(defn.signature.clone()),
347            _ => None,
348        }
349    }
350
351    /// Return a wrapper over the view that can be used in petgraph algorithms.
352    #[inline]
353    fn as_petgraph(&self) -> PetgraphWrapper<'_, Self>
354    where
355        Self: Sized,
356    {
357        PetgraphWrapper { hugr: self }
358    }
359
360    /// Return the mermaid representation of the underlying hierarchical graph.
361    ///
362    /// The hierarchy is represented using subgraphs. Edges are labelled with
363    /// their source and target ports.
364    ///
365    /// For a more detailed representation, use the [`HugrView::dot_string`]
366    /// format instead.
367    fn mermaid_string(&self) -> String {
368        self.mermaid_string_with_config(RenderConfig {
369            node_indices: true,
370            port_offsets_in_edges: true,
371            type_labels_in_edges: true,
372        })
373    }
374
375    /// Return the mermaid representation of the underlying hierarchical graph.
376    ///
377    /// The hierarchy is represented using subgraphs. Edges are labelled with
378    /// their source and target ports.
379    ///
380    /// For a more detailed representation, use the [`HugrView::dot_string`]
381    /// format instead.
382    fn mermaid_string_with_config(&self, config: RenderConfig) -> String {
383        let hugr = self.base_hugr();
384        let graph = self.portgraph();
385        graph
386            .mermaid_format()
387            .with_hierarchy(&hugr.hierarchy)
388            .with_node_style(render::node_style(self, config))
389            .with_edge_style(render::edge_style(self, config))
390            .finish()
391    }
392
393    /// Return the graphviz representation of the underlying graph and hierarchy side by side.
394    ///
395    /// For a simpler representation, use the [`HugrView::mermaid_string`] format instead.
396    fn dot_string(&self) -> String
397    where
398        Self: Sized,
399    {
400        let hugr = self.base_hugr();
401        let graph = self.portgraph();
402        let config = RenderConfig::default();
403        graph
404            .dot_format()
405            .with_hierarchy(&hugr.hierarchy)
406            .with_node_style(render::node_style(self, config))
407            .with_port_style(render::port_style(self, config))
408            .with_edge_style(render::edge_style(self, config))
409            .finish()
410    }
411
412    /// If a node has a static input, return the source node.
413    fn static_source(&self, node: Self::Node) -> Option<Self::Node> {
414        self.linked_outputs(node, self.get_optype(node).static_input_port()?)
415            .next()
416            .map(|(n, _)| n)
417    }
418
419    /// If a node has a static output, return the targets.
420    fn static_targets(
421        &self,
422        node: Self::Node,
423    ) -> Option<impl Iterator<Item = (Self::Node, IncomingPort)>> {
424        Some(self.linked_inputs(node, self.get_optype(node).static_output_port()?))
425    }
426
427    /// Get the "signature" (incoming and outgoing types) of a node, non-Value
428    /// kind ports will be missing.
429    fn signature(&self, node: Self::Node) -> Option<Cow<'_, Signature>> {
430        self.get_optype(node).dataflow_signature()
431    }
432
433    /// Iterator over all outgoing ports that have Value type, along
434    /// with corresponding types.
435    fn value_types(&self, node: Self::Node, dir: Direction) -> impl Iterator<Item = (Port, Type)> {
436        let sig = self.signature(node).unwrap_or_default();
437        self.node_ports(node, dir)
438            .flat_map(move |port| sig.port_type(port).map(|typ| (port, typ.clone())))
439    }
440
441    /// Iterator over all incoming ports that have Value type, along
442    /// with corresponding types.
443    fn in_value_types(&self, node: Self::Node) -> impl Iterator<Item = (IncomingPort, Type)> {
444        self.value_types(node, Direction::Incoming)
445            .map(|(p, t)| (p.as_incoming().unwrap(), t))
446    }
447
448    /// Iterator over all incoming ports that have Value type, along
449    /// with corresponding types.
450    fn out_value_types(&self, node: Self::Node) -> impl Iterator<Item = (OutgoingPort, Type)> {
451        self.value_types(node, Direction::Outgoing)
452            .map(|(p, t)| (p.as_outgoing().unwrap(), t))
453    }
454
455    /// Returns the set of extensions used by the HUGR.
456    ///
457    /// This set may contain extensions that are no longer required by the HUGR.
458    fn extensions(&self) -> &ExtensionRegistry {
459        &self.base_hugr().extensions
460    }
461
462    /// Check the validity of the underlying HUGR.
463    ///
464    /// This includes checking consistency of extension requirements between
465    /// connected nodes and between parents and children.
466    /// See [`HugrView::validate_no_extensions`] for a version that doesn't check
467    /// extension requirements.
468    fn validate(&self) -> Result<(), ValidationError> {
469        self.base_hugr().validate()
470    }
471
472    /// Check the validity of the underlying HUGR, but don't check consistency
473    /// of extension requirements between connected nodes or between parents and
474    /// children.
475    ///
476    /// For a more thorough check, use [`HugrView::validate`].
477    fn validate_no_extensions(&self) -> Result<(), ValidationError> {
478        self.base_hugr().validate_no_extensions()
479    }
480}
481
482/// Trait for views that provides a guaranteed bound on the type of the root node.
483pub trait RootTagged: HugrView {
484    /// The kind of handle that can be used to refer to the root node.
485    ///
486    /// The handle is guaranteed to be able to contain the operation returned by
487    /// [`HugrView::root_type`].
488    type RootHandle: NodeHandle;
489}
490
491/// A common trait for views of a HUGR hierarchical subgraph.
492pub trait HierarchyView<'a>: RootTagged + Sized {
493    /// Create a hierarchical view of a HUGR given a root node.
494    ///
495    /// # Errors
496    /// Returns [`HugrError::InvalidTag`] if the root isn't a node of the required [OpTag]
497    fn try_new(
498        hugr: &'a impl HugrView<Node = Self::Node>,
499        root: Self::Node,
500    ) -> Result<Self, HugrError>;
501}
502
503/// A trait for [`HugrView`]s that can be extracted into a valid HUGR containing
504/// only the nodes and edges of the view.
505pub trait ExtractHugr: HugrView + Sized {
506    /// Extracts the view into an owned HUGR, rooted at the view's root node
507    /// and containing only the nodes and edges of the view.
508    fn extract_hugr(self) -> Hugr {
509        let mut hugr = Hugr::default();
510        let old_root = hugr.root();
511        let new_root = hugr.insert_from_view(old_root, &self).new_root;
512        hugr.set_root(new_root);
513        hugr.remove_node(old_root);
514        hugr
515    }
516}
517
518fn check_tag<Required: NodeHandle, N>(
519    hugr: &impl HugrView<Node = N>,
520    node: N,
521) -> Result<(), HugrError> {
522    let actual = hugr.get_optype(node).tag();
523    let required = Required::TAG;
524    if !required.is_superset(actual) {
525        return Err(HugrError::InvalidTag { required, actual });
526    }
527    Ok(())
528}
529
530impl RootTagged for Hugr {
531    type RootHandle = Node;
532}
533
534impl RootTagged for &Hugr {
535    type RootHandle = Node;
536}
537
538impl RootTagged for &mut Hugr {
539    type RootHandle = Node;
540}
541
542// Explicit implementation to avoid cloning the Hugr.
543impl ExtractHugr for Hugr {
544    fn extract_hugr(self) -> Hugr {
545        self
546    }
547}
548
549impl ExtractHugr for &Hugr {
550    fn extract_hugr(self) -> Hugr {
551        self.clone()
552    }
553}
554
555impl ExtractHugr for &mut Hugr {
556    fn extract_hugr(self) -> Hugr {
557        self.clone()
558    }
559}
560
561impl HugrView for Hugr {
562    #[inline]
563    fn contains_node(&self, node: Node) -> bool {
564        self.graph.contains_node(node.pg_index())
565    }
566
567    #[inline]
568    fn node_count(&self) -> usize {
569        self.graph.node_count()
570    }
571
572    #[inline]
573    fn edge_count(&self) -> usize {
574        self.graph.link_count()
575    }
576
577    #[inline]
578    fn nodes(&self) -> impl Iterator<Item = Node> + Clone {
579        self.graph.nodes_iter().map_into()
580    }
581
582    #[inline]
583    fn node_ports(&self, node: Node, dir: Direction) -> impl Iterator<Item = Port> + Clone {
584        self.graph.port_offsets(node.pg_index(), dir).map_into()
585    }
586
587    #[inline]
588    fn all_node_ports(&self, node: Node) -> impl Iterator<Item = Port> + Clone {
589        self.graph.all_port_offsets(node.pg_index()).map_into()
590    }
591
592    #[inline]
593    fn linked_ports(
594        &self,
595        node: Node,
596        port: impl Into<Port>,
597    ) -> impl Iterator<Item = (Node, Port)> + Clone {
598        let port = port.into();
599
600        let port = self
601            .graph
602            .port_index(node.pg_index(), port.pg_offset())
603            .unwrap();
604        self.graph.port_links(port).map(|(_, link)| {
605            let port = link.port();
606            let node = self.graph.port_node(port).unwrap();
607            let offset = self.graph.port_offset(port).unwrap();
608            (node.into(), offset.into())
609        })
610    }
611
612    #[inline]
613    fn node_connections(&self, node: Node, other: Node) -> impl Iterator<Item = [Port; 2]> + Clone {
614        self.graph
615            .get_connections(node.pg_index(), other.pg_index())
616            .map(|(p1, p2)| {
617                [p1, p2].map(|link| self.graph.port_offset(link.port()).unwrap().into())
618            })
619    }
620
621    #[inline]
622    fn num_ports(&self, node: Node, dir: Direction) -> usize {
623        self.graph.num_ports(node.pg_index(), dir)
624    }
625
626    #[inline]
627    fn children(&self, node: Node) -> impl DoubleEndedIterator<Item = Node> + Clone {
628        self.hierarchy.children(node.pg_index()).map_into()
629    }
630
631    #[inline]
632    fn neighbours(&self, node: Node, dir: Direction) -> impl Iterator<Item = Node> + Clone {
633        self.graph.neighbours(node.pg_index(), dir).map_into()
634    }
635
636    #[inline]
637    fn all_neighbours(&self, node: Node) -> impl Iterator<Item = Node> + Clone {
638        self.graph.all_neighbours(node.pg_index()).map_into()
639    }
640}
641
642/// Trait implementing methods on port iterators.
643pub trait PortIterator<P>: Iterator<Item = (Node, P)>
644where
645    P: Into<Port> + Copy,
646    Self: Sized,
647{
648    /// Filter an iterator of node-ports to only dataflow dependency specifying
649    /// ports (Value and StateOrder)
650    fn dataflow_ports_only(
651        self,
652        hugr: &impl HugrView<Node = Node>,
653    ) -> impl Iterator<Item = (Node, P)> {
654        self.filter_edge_kind(
655            |kind| matches!(kind, Some(EdgeKind::Value(..) | EdgeKind::StateOrder)),
656            hugr,
657        )
658    }
659
660    /// Filter an iterator of node-ports based on the port kind.
661    fn filter_edge_kind(
662        self,
663        predicate: impl Fn(Option<EdgeKind>) -> bool,
664        hugr: &impl HugrView<Node = Node>,
665    ) -> impl Iterator<Item = (Node, P)> {
666        self.filter(move |(n, p)| {
667            let kind = hugr.get_optype(*n).port_kind(*p);
668            predicate(kind)
669        })
670    }
671}
672
673impl<I, P> PortIterator<P> for I
674where
675    I: Iterator<Item = (Node, P)>,
676    P: Into<Port> + Copy,
677{
678}