hugr_core/hugr/patch.rs
1//! Rewrite operations on the HUGR - replacement, outlining, etc.
2
3pub mod consts;
4pub mod inline_call;
5pub mod inline_dfg;
6pub mod insert_cut;
7pub mod insert_identity;
8pub mod outline_cfg;
9pub mod peel_loop;
10mod port_types;
11pub mod replace;
12pub mod simple_replace;
13
14use crate::HugrView;
15use crate::core::HugrNode;
16use crate::hugr::views::NodesIter;
17use itertools::Itertools;
18pub use port_types::{BoundaryPort, HostPort, ReplacementPort};
19pub use simple_replace::{SimpleReplacement, SimpleReplacementError};
20
21use super::HugrMut;
22use super::views::ExtractionResult;
23
24/// Verify that a patch application would succeed.
25// TODO: This trait should be parametrised on `H: NodesIter` to match the
26// generality of [`Patch`], see https://github.com/CQCL/hugr/issues/2546.
27pub trait PatchVerification {
28 /// The type of Error with which this Rewrite may fail
29 type Error: std::error::Error;
30
31 /// The node type of the `HugrView` that this patch applies to.
32 type Node: HugrNode;
33
34 /// Checks whether the rewrite would succeed on the specified Hugr.
35 /// If this call succeeds, [`Patch::apply`] should also succeed on the same
36 /// `h` If this calls fails, [`Patch::apply`] would fail with the same
37 /// error.
38 fn verify(&self, h: &impl HugrView<Node = Self::Node>) -> Result<(), Self::Error>;
39
40 /// The nodes invalidated by the rewrite. Deprecated: implement
41 /// [Self::invalidated_nodes] instead. The default returns the empty
42 /// iterator; this should be fine as there are no external calls.
43 #[deprecated(note = "Use/implement invalidated_nodes instead")]
44 fn invalidation_set(&self) -> impl Iterator<Item = Self::Node> {
45 std::iter::empty()
46 }
47
48 /// Returns the nodes removed or altered by the rewrite. Modifying any of these
49 /// nodes will invalidate the rewrite.
50 ///
51 /// Two `impl Rewrite`s can be composed if their `invalidated_nodes` are
52 /// disjoint.
53 fn invalidated_nodes(
54 &self,
55 h: &impl HugrView<Node = Self::Node>,
56 ) -> impl Iterator<Item = Self::Node> {
57 let _ = h;
58 #[expect(deprecated)]
59 self.invalidation_set()
60 }
61}
62
63/// A patch that can be applied to a mutable Hugr of type `H`.
64///
65/// ### When to use
66///
67/// Use this trait whenever possible in bounds for the most generality. Note
68/// that this will require specifying which type `H` the patch applies to.
69///
70/// ### When to implement
71///
72/// For patches that work on any `H: HugrMut`, prefer implementing
73/// [`PatchHugrMut`] instead. This will automatically implement this trait.
74pub trait Patch<H: NodesIter>: PatchVerification<Node = H::Node> {
75 /// The type returned on successful application of the rewrite.
76 type Outcome;
77
78 /// If `true`, [`Patch::apply`]'s of this rewrite guarantee that they do not
79 /// mutate the Hugr when they return an Err. If `false`, there is no
80 /// guarantee; the Hugr should be assumed invalid when Err is returned.
81 const UNCHANGED_ON_FAILURE: bool;
82
83 /// Mutate the specified Hugr, or fail with an error.
84 ///
85 /// Returns [`Self::Outcome`] if successful. If
86 /// [`Patch::UNCHANGED_ON_FAILURE`] is true, then `h` must be unchanged if Err
87 /// is returned. See also [`PatchVerification::verify`]
88 ///
89 /// # Panics
90 ///
91 /// May panic if-and-only-if `h` would have failed
92 /// [`Hugr::validate`][crate::Hugr::validate]; that is, implementations may
93 /// begin with `assert!(h.validate())`, with `debug_assert!(h.validate())`
94 /// being preferred.
95 fn apply(self, h: &mut H) -> Result<Self::Outcome, Self::Error>;
96}
97
98/// A patch that can be applied to any [`HugrMut`].
99///
100/// This trait is a generalisation of [`Patch`] in that it guarantees that
101/// the patch can be applied to any type implementing [`HugrMut`].
102///
103/// ### When to use
104///
105/// Prefer using the more general [`Patch`] trait in bounds where the
106/// type `H` is known. Resort to this trait if patches must be applicable to
107/// any [`HugrMut`] instance.
108///
109/// ### When to implement
110///
111/// Always implement this trait when possible, to define how a patch is applied
112/// to any type implementing [`HugrMut`]. A blanket implementation ensures that
113/// any type implementing this trait also implements [`Patch`].
114pub trait PatchHugrMut: PatchVerification {
115 /// The type returned on successful application of the rewrite.
116 type Outcome;
117
118 /// If `true`, [self.apply]'s of this rewrite guarantee that they do not
119 /// mutate the Hugr when they return an Err. If `false`, there is no
120 /// guarantee; the Hugr should be assumed invalid when Err is returned.
121 const UNCHANGED_ON_FAILURE: bool;
122
123 /// Mutate the specified Hugr, or fail with an error.
124 ///
125 /// Returns [`Self::Outcome`] if successful. If [`self.unchanged_on_failure`]
126 /// is true, then `h` must be unchanged if Err is returned. See also
127 /// [self.verify]
128 ///
129 /// # Panics
130 ///
131 /// May panic if-and-only-if `h` would have failed
132 /// [`Hugr::validate`][crate::Hugr::validate]; that is, implementations may
133 /// begin with `assert!(h.validate())`, with `debug_assert!(h.validate())`
134 /// being preferred.
135 fn apply_hugr_mut(
136 self,
137 h: &mut impl HugrMut<Node = Self::Node>,
138 ) -> Result<Self::Outcome, Self::Error>;
139}
140
141impl<R: PatchHugrMut, H: HugrMut<Node = R::Node>> Patch<H> for R {
142 type Outcome = R::Outcome;
143 const UNCHANGED_ON_FAILURE: bool = R::UNCHANGED_ON_FAILURE;
144
145 fn apply(self, h: &mut H) -> Result<Self::Outcome, Self::Error> {
146 self.apply_hugr_mut(h)
147 }
148}
149
150/// Wraps any rewrite into a transaction (i.e. that has no effect upon failure)
151pub struct Transactional<R> {
152 underlying: R,
153}
154
155impl<R: PatchVerification> PatchVerification for Transactional<R> {
156 type Error = R::Error;
157 type Node = R::Node;
158
159 fn verify(&self, h: &impl HugrView<Node = Self::Node>) -> Result<(), Self::Error> {
160 self.underlying.verify(h)
161 }
162
163 #[inline]
164 fn invalidated_nodes(
165 &self,
166 h: &impl HugrView<Node = Self::Node>,
167 ) -> impl Iterator<Item = Self::Node> {
168 self.underlying.invalidated_nodes(h)
169 }
170}
171
172// Note we might like to constrain R to Rewrite<unchanged_on_failure=false> but
173// this is not yet supported, https://github.com/rust-lang/rust/issues/92827
174impl<R: PatchHugrMut> PatchHugrMut for Transactional<R> {
175 type Outcome = R::Outcome;
176 const UNCHANGED_ON_FAILURE: bool = true;
177
178 fn apply_hugr_mut(
179 self,
180 h: &mut impl HugrMut<Node = Self::Node>,
181 ) -> Result<Self::Outcome, Self::Error> {
182 if R::UNCHANGED_ON_FAILURE {
183 return self.underlying.apply_hugr_mut(h);
184 }
185 // Backup the whole Hugr.
186 // Temporarily move the entrypoint so every node gets copied.
187 //
188 // TODO: This requires a full graph copy on each application.
189 // Ideally we'd be able to just restore modified nodes, perhaps using a `HugrMut` wrapper
190 // that keeps track of them.
191 let (backup, backup_map) = h.extract_hugr(h.module_root());
192 let backup_root = backup_map.extracted_node(h.module_root());
193 let backup_entrypoint = backup_map.extracted_node(h.entrypoint());
194
195 let r = self.underlying.apply_hugr_mut(h);
196 if r.is_err() {
197 // Restore the backup.
198 let h_root = h.module_root();
199 for f in h.children(h_root).collect_vec() {
200 h.remove_subtree(f);
201 }
202 let insert_map = h.insert_hugr(h_root, backup).node_map;
203 let inserted_root = insert_map[&backup_root];
204 let inserted_entrypoint = insert_map[&backup_entrypoint];
205 h.remove_node(h_root);
206 h.set_module_root(inserted_root);
207 h.set_entrypoint(inserted_entrypoint);
208 }
209 r
210 }
211}