1pub 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
40pub trait HugrView: HugrInternals {
43 #[inline]
45 fn root(&self) -> Self::Node {
46 self.root_node()
47 }
48
49 #[inline]
51 fn root_type(&self) -> &OpType {
52 let node_type = self.get_optype(self.root());
53 node_type
56 }
57
58 fn contains_node(&self, node: Self::Node) -> bool;
60
61 #[inline]
63 fn valid_node(&self, node: Self::Node) -> bool {
64 self.contains_node(node)
65 }
66
67 #[inline]
71 fn valid_non_root(&self, node: Self::Node) -> bool {
72 self.root() != node && self.valid_node(node)
73 }
74
75 #[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 #[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 #[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 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 fn node_count(&self) -> usize;
118
119 fn edge_count(&self) -> usize;
121
122 fn nodes(&self) -> impl Iterator<Item = Self::Node> + Clone;
124
125 fn node_ports(&self, node: Self::Node, dir: Direction) -> impl Iterator<Item = Port> + Clone;
127
128 #[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 #[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 fn all_node_ports(&self, node: Self::Node) -> impl Iterator<Item = Port> + Clone;
148
149 fn linked_ports(
151 &self,
152 node: Self::Node,
153 port: impl Into<Port>,
154 ) -> impl Iterator<Item = (Self::Node, Port)> + Clone;
155
156 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 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 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 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 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 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 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 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 fn node_connections(
254 &self,
255 node: Self::Node,
256 other: Self::Node,
257 ) -> impl Iterator<Item = [Port; 2]> + Clone;
258
259 fn is_linked(&self, node: Self::Node, port: impl Into<Port>) -> bool {
261 self.linked_ports(node, port).next().is_some()
262 }
263
264 fn num_ports(&self, node: Self::Node, dir: Direction) -> usize;
266
267 #[inline]
270 fn num_inputs(&self, node: Self::Node) -> usize {
271 self.num_ports(node, Direction::Incoming)
272 }
273
274 #[inline]
277 fn num_outputs(&self, node: Self::Node) -> usize {
278 self.num_ports(node, Direction::Outgoing)
279 }
280
281 fn children(&self, node: Self::Node) -> impl DoubleEndedIterator<Item = Self::Node> + Clone;
283
284 fn first_child(&self, node: Self::Node) -> Option<Self::Node> {
287 self.children(node).next()
288 }
289
290 fn neighbours(
293 &self,
294 node: Self::Node,
295 dir: Direction,
296 ) -> impl Iterator<Item = Self::Node> + Clone;
297
298 #[inline]
301 fn input_neighbours(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> + Clone {
302 self.neighbours(node, Direction::Incoming)
303 }
304
305 #[inline]
308 fn output_neighbours(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> + Clone {
309 self.neighbours(node, Direction::Outgoing)
310 }
311
312 fn all_neighbours(&self, node: Self::Node) -> impl Iterator<Item = Self::Node> + Clone;
314
315 #[inline]
318 fn get_io(&self, node: Self::Node) -> Option<[Self::Node; 2]> {
319 let op = self.get_optype(node);
320 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 fn inner_function_type(&self) -> Option<Cow<'_, Signature>> {
338 self.root_type().inner_function_type()
339 }
340
341 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 #[inline]
353 fn as_petgraph(&self) -> PetgraphWrapper<'_, Self>
354 where
355 Self: Sized,
356 {
357 PetgraphWrapper { hugr: self }
358 }
359
360 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 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 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 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 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 fn signature(&self, node: Self::Node) -> Option<Cow<'_, Signature>> {
430 self.get_optype(node).dataflow_signature()
431 }
432
433 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 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 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 fn extensions(&self) -> &ExtensionRegistry {
459 &self.base_hugr().extensions
460 }
461
462 fn validate(&self) -> Result<(), ValidationError> {
469 self.base_hugr().validate()
470 }
471
472 fn validate_no_extensions(&self) -> Result<(), ValidationError> {
478 self.base_hugr().validate_no_extensions()
479 }
480}
481
482pub trait RootTagged: HugrView {
484 type RootHandle: NodeHandle;
489}
490
491pub trait HierarchyView<'a>: RootTagged + Sized {
493 fn try_new(
498 hugr: &'a impl HugrView<Node = Self::Node>,
499 root: Self::Node,
500 ) -> Result<Self, HugrError>;
501}
502
503pub trait ExtractHugr: HugrView + Sized {
506 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
542impl 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
642pub trait PortIterator<P>: Iterator<Item = (Node, P)>
644where
645 P: Into<Port> + Copy,
646 Self: Sized,
647{
648 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 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}