Struct PersistentHugr

pub struct PersistentHugr { /* private fields */ }

A HUGR-like object that tracks its mutation history.

When mutations are applied to a PersistentHugr, the object is mutated as expected but all references to previous versions of the object remain valid. Furthermore, older versions of the data can be recovered by traversing the object’s history with Self::as_state_space.

Multiple references to various versions of a Hugr can be maintained in parallel by extracting them from a shared CommitStateSpace.

Supported access and mutation

PersistentHugr implements crate::HugrView, so that it can used as a drop-in substitute for a Hugr wherever read-only access is required. It does not implement HugrMut, however. Mutations must be performed by applying patches (see PatchVerification and Patch). Currently, only SimpleReplacement patches are supported. You can use Self::add_replacement to add a patch to self, or use the aforementioned patch traits.

Patches, commits and history

A PersistentHugr is composed of a unique base HUGR, along with a set of mutations applied to it. All mutations are stored in the form of commits that store the patches applied on top of a base HUGR. You may think of it as a “queue” of patches: whenever the patch of a commit is “applied”, it is in reality just added to the queue. In practice, the total order of the queue is irrelevant, as patches only depend on a subset of the previously applied patches. This creates a partial order on the commits: a directed acyclic graph that we call the “commit history”. A commit history is in effect a subgraph of a commit state space, with the additional invariant that all commits within the history are compatible.

Supported graph types

Currently, only patches that apply to subgraphs within dataflow regions are supported.

Implementations

impl PersistentHugr

pub fn with_base(hugr: Hugr) -> Self

Create a PersistentHugr with hugr as its base HUGR.

All replacements added in the future will apply on top of hugr.

pub fn from_commit(commit: Commit) -> Self

Create a PersistentHugr from a single commit and its ancestors.

pub fn try_new( commits: impl IntoIterator<Item = Commit>, ) -> Result<Self, InvalidCommit>

Create a PersistentHugr from a list of commits.

Self will correspond to the HUGR obtained by applying the patches of the given commits and of all their ancestors.

If the state space of the commits would include two commits which are incompatible, or if the commits do not share a common base HUGR, then an error is returned.

pub fn add_replacement( &mut self, replacement: PersistentReplacement, ) -> CommitId

Add a replacement to self.

The effect of this is equivalent to applying replacement to the equivalent HUGR, i.e. self.to_hugr().apply(replacement) is equivalent to self.add_replacement(replacement).to_hugr().

This will panic if the replacement is invalid. Use PersistentHugr::try_add_replacement instead for more graceful error handling.

pub fn try_add_replacement( &mut self, replacement: PersistentReplacement, ) -> Result<CommitId, InvalidCommit>

Add a replacement to self, with error handling.

All parent commits must already be in self.

Return the ID of) the commit if it was added successfully. This may return the following errors:

• a InvalidCommit::IncompatibleHistory error if the replacement is incompatible with another commit already in self, or
• a InvalidCommit::UnknownParent error if one of the commits that replacement applies on top of is not contained in self.

pub fn try_add_commit( &mut self, commit: Commit, ) -> Result<CommitId, InvalidCommit>

Add a commit to self and all its ancestors.

The commit and all its ancestors must be compatible with all existing commits in self. If this is not satisfied, an InvalidCommit::IncompatibleHistory error is returned. In this case, as many compatible commits as possible are added to self.

pub fn to_hugr(&self) -> Hugr

Convert this PersistentHugr to a materialized Hugr by applying all commits in self.

This operation may be expensive and should be avoided in performance-critical paths. For read-only views into the data, rely instead on the crate::HugrView implementation when possible.

pub fn apply_all(&self) -> (Hugr, HashMap<PatchNode, Node>)

Apply all commits in self to the base HUGR.

Also returns a map from the nodes of the base HUGR to the nodes of the materialized HUGR.

pub fn as_state_space(&self) -> &CommitStateSpace

Get a reference to the underlying state space of self.

pub fn into_state_space(self) -> CommitStateSpace

Convert self into its underlying CommitStateSpace.

pub fn contains(&self, commit: &Commit) -> bool

Check if commit is in the PersistentHugr.

pub fn contains_id(&self, commit_id: CommitId) -> bool

Check if commit_id is in the PersistentHugr.

pub fn base(&self) -> CommitId

Get the base commit ID.

pub fn base_hugr(&self) -> &Hugr

Get the base Hugr.

pub fn base_commit(&self) -> &Commit

Get the base commit.

pub fn get_commit(&self, commit_id: CommitId) -> &Commit

Get the commit with ID commit_id.

pub fn inserted_nodes( &self, commit_id: CommitId, ) -> impl Iterator<Item = PatchNode> + '_

Get an iterator over all nodes inserted by commit_id.

All nodes will be PatchNodes with commit ID commit_id.

pub fn all_commit_ids(&self) -> impl Iterator<Item = CommitId> + Clone + '_

Get an iterator over all commit IDs in the persistent HUGR.

pub fn invalidation_set( &self, commit_id: CommitId, ) -> impl Iterator<Item = Node> + '_

Get the set of nodes of commit_id that are invalidated by the patches in the children commits of commit_id.

The invalidation set must include all nodes that are deleted by the children commits (as returned by Self::deleted_nodes), but may also include further nodes to enforce stricter exclusivity constraints between patches.

pub fn deleted_nodes( &self, commit_id: CommitId, ) -> impl Iterator<Item = Node> + '_

Get the set of nodes of commit_id that are deleted by applying the children commits of commit_id.

This is a subset of Self::invalidation_set. Whilst the latter is used to establish exclusivity constraints between patches, this method is used when we are computing the set of nodes currently present in self.

pub fn contains_node(&self, PatchNode: PatchNode) -> bool

Check if a patch node is in the PersistentHugr, that is, it belongs to a commit in the state space and is not deleted by any child commit.

Trait Implementations

impl Clone for PersistentHugr

fn clone(&self) -> PersistentHugr

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for PersistentHugr

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl HugrInternals for PersistentHugr

type RegionPortgraph<'p> = MultiPortGraph where Self: 'p

The portgraph graph structure returned by HugrInternals::region_portgraph.

type Node = PatchNode

The type of nodes in the Hugr.

type RegionPortgraphNodes = HashMap<PatchNode, Node>

A mapping between HUGR nodes and portgraph nodes in the graph returned by HugrInternals::region_portgraph.

fn region_portgraph( &self, parent: Self::Node, ) -> (FlatRegion<'_, Self::RegionPortgraph<'_>>, Self::RegionPortgraphNodes)

Returns a flat portgraph view of a region in the HUGR, and a mapping between HUGR nodes and portgraph nodes in the graph.

fn node_metadata_map(&self, node: Self::Node) -> &NodeMetadataMap

Returns a metadata entry associated with a node.

impl HugrView for PersistentHugr

fn entrypoint(&self) -> Self::Node

The distinguished node from where operations are applied, commonly defining a region of interest.

fn module_root(&self) -> Self::Node

A pointer to the module region defined at the root of the HUGR.

fn contains_node(&self, node: Self::Node) -> bool

Returns true if the node exists in the HUGR.

fn get_parent(&self, node: Self::Node) -> Option<Self::Node>

Returns the parent of a node.

fn get_optype(&self, node: Self::Node) -> &OpType

Returns the operation type of a node.

fn num_nodes(&self) -> usize

Returns the number of nodes in the HUGR.

fn num_edges(&self) -> usize

Returns the number of edges in the HUGR.

fn num_ports(&self, node: Self::Node, dir: Direction) -> usize

Number of ports in node for a given direction.

fn nodes(&self) -> impl Iterator<Item = Self::Node> + Clone

Iterates over the all the nodes in the HUGR.

fn node_ports( &self, node: Self::Node, dir: Direction, ) -> impl Iterator<Item = Port> + Clone

Iterator over ports of node in a given direction.

fn all_node_ports(&self, node: Self::Node) -> impl Iterator<Item = Port> + Clone

Iterator over both the input and output ports of node.

fn linked_ports( &self, node: Self::Node, port: impl Into<Port>, ) -> impl Iterator<Item = (Self::Node, Port)> + Clone

Iterator over the nodes and ports connected to a port.

fn node_connections( &self, node: Self::Node, other: Self::Node, ) -> impl Iterator<Item = [Port; 2]> + Clone

Iterator the links between two nodes.

fn children( &self, node: Self::Node, ) -> impl DoubleEndedIterator<Item = Self::Node> + Clone

Returns an iterator over the direct children of node.

fn descendants( &self, node: Self::Node, ) -> impl Iterator<Item = Self::Node> + Clone

Returns an iterator over all the descendants of a node, including the node itself.

fn neighbours( &self, node: Self::Node, dir: Direction, ) -> impl Iterator<Item = Self::Node> + Clone

Iterates over neighbour nodes in the given direction. May contain duplicates if the graph has multiple links between nodes.

fn all_neighbours( &self, node: Self::Node, ) -> impl Iterator<Item = Self::Node> + Clone

Iterates over the input and output neighbours of the node in sequence.

fn mermaid_string(&self) -> String

Return the mermaid representation of the underlying hierarchical graph.

fn mermaid_string_with_config(&self, config: RenderConfig<Self::Node>) -> String

Return the mermaid representation of the underlying hierarchical graph.

fn dot_string(&self) -> String

where Self: Sized,

Return the graphviz representation of the underlying graph and hierarchy side by side.

fn extensions(&self) -> &ExtensionRegistry

Returns the set of extensions used by the HUGR.

fn extract_hugr( &self, parent: Self::Node, ) -> (Hugr, impl ExtractionResult<Self::Node> + 'static)

Extracts a HUGR containing the parent node and all its descendants.

fn entrypoint_optype(&self) -> &OpType

Returns the operation type of the entrypoint node.

fn entrypoint_tag(&self) -> OpTag

An operation tag that is guaranteed to represent the HugrView::entrypoint node operation.

fn with_entrypoint(&self, entrypoint: Self::Node) -> Rerooted<&Self>

where Self: Sized,

Returns a non-mutable view of the HUGR with a different entrypoint.

fn get_metadata( &self, node: Self::Node, key: impl AsRef<str>, ) -> Option<&NodeMetadata>

Returns the metadata associated with a node.

fn num_inputs(&self, node: Self::Node) -> usize

Number of inputs to a node. Shorthand for num_ports(node, Direction::Incoming).

fn num_outputs(&self, node: Self::Node) -> usize

Number of outputs from a node. Shorthand for num_ports(node, Direction::Outgoing).

fn node_outputs( &self, node: Self::Node, ) -> impl Iterator<Item = OutgoingPort> + Clone

Iterator over output ports of node. Like node_ports(node, Direction::Outgoing) but preserves knowledge that the ports are OutgoingPorts.

fn node_inputs( &self, node: Self::Node, ) -> impl Iterator<Item = IncomingPort> + Clone

Iterator over inputs ports of node. Like node_ports(node, Direction::Incoming) but preserves knowledge that the ports are IncomingPorts.

fn all_linked_ports( &self, node: Self::Node, dir: Direction, ) -> Either<impl Iterator<Item = (Self::Node, OutgoingPort)>, impl Iterator<Item = (Self::Node, IncomingPort)>>

Iterator over all the nodes and ports connected to a node in a given direction.

fn all_linked_outputs( &self, node: Self::Node, ) -> impl Iterator<Item = (Self::Node, OutgoingPort)>

Iterator over all the nodes and ports connected to a node’s inputs.

fn all_linked_inputs( &self, node: Self::Node, ) -> impl Iterator<Item = (Self::Node, IncomingPort)>

Iterator over all the nodes and ports connected to a node’s outputs.

fn single_linked_port( &self, node: Self::Node, port: impl Into<Port>, ) -> Option<(Self::Node, Port)>

If there is exactly one port connected to this port, return it and its node.

fn single_linked_output( &self, node: Self::Node, port: impl Into<IncomingPort>, ) -> Option<(Self::Node, OutgoingPort)>

If there is exactly one OutgoingPort connected to this IncomingPort, return it and its node.

fn single_linked_input( &self, node: Self::Node, port: impl Into<OutgoingPort>, ) -> Option<(Self::Node, IncomingPort)>

If there is exactly one IncomingPort connected to this OutgoingPort, return it and its node.

fn linked_outputs( &self, node: Self::Node, port: impl Into<IncomingPort>, ) -> impl Iterator<Item = (Self::Node, OutgoingPort)>

Iterator over the nodes and output ports connected to a given input port. Like linked_ports but preserves knowledge that the linked ports are OutgoingPorts.

fn linked_inputs( &self, node: Self::Node, port: impl Into<OutgoingPort>, ) -> impl Iterator<Item = (Self::Node, IncomingPort)>

Iterator over the nodes and input ports connected to a given output port Like linked_ports but preserves knowledge that the linked ports are IncomingPorts.

fn is_linked(&self, node: Self::Node, port: impl Into<Port>) -> bool

Returns whether a port is connected.

fn entry_descendants(&self) -> impl Iterator<Item = Self::Node> + Clone

Returns an iterator over all the descendants of the hugr entrypoint, including the node itself.

fn first_child(&self, node: Self::Node) -> Option<Self::Node>

Returns the first child of the specified node (if it is a parent). Useful because x.children().next() leaves x borrowed.

fn input_neighbours( &self, node: Self::Node, ) -> impl Iterator<Item = Self::Node> + Clone

Iterates over the input neighbours of the node. Shorthand for neighbours(node, Direction::Incoming).

fn output_neighbours( &self, node: Self::Node, ) -> impl Iterator<Item = Self::Node> + Clone

Iterates over the output neighbours of the node. Shorthand for neighbours(node, Direction::Outgoing).

fn get_io(&self, node: Self::Node) -> Option<[Self::Node; 2]>

Get the input and output child nodes of a dataflow parent. If the node isn’t a dataflow parent, then return None

fn inner_function_type(&self) -> Option<Cow<'_, Signature>>

Returns the function type defined by this dataflow HUGR.

fn poly_func_type(&self) -> Option<PolyFuncType>

Returns the function type defined by this HUGR, i.e. Some iff the root is a FuncDecl or FuncDefn.

fn as_petgraph(&self) -> PetgraphWrapper<'_, Self>

where Self: Sized,

Return a wrapper over the view that can be used in petgraph algorithms.

fn static_source(&self, node: Self::Node) -> Option<Self::Node>

If a node has a static input, return the source node.

fn static_targets( &self, node: Self::Node, ) -> Option<impl Iterator<Item = (Self::Node, IncomingPort)>>

If a node has a static output, return the targets.

fn signature(&self, node: Self::Node) -> Option<Cow<'_, Signature>>

Get the “signature” (incoming and outgoing types) of a node, non-Value kind ports will be missing.

fn value_types( &self, node: Self::Node, dir: Direction, ) -> impl Iterator<Item = (Port, Type)>

Iterator over all outgoing ports that have Value type, along with corresponding types.

fn in_value_types( &self, node: Self::Node, ) -> impl Iterator<Item = (IncomingPort, Type)>

Iterator over all incoming ports that have Value type, along with corresponding types.

fn out_value_types( &self, node: Self::Node, ) -> impl Iterator<Item = (OutgoingPort, Type)>

Iterator over all outgoing ports that have Value type, along with corresponding types.

fn validate(&self) -> Result<(), ValidationError<Self::Node>>

where Self: Sized,

Check the validity of the underlying HUGR.

impl IntoIterator for PersistentHugr

type Item = Commit

The type of the elements being iterated over.

type IntoIter = IntoIter<Commit>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl Patch<PersistentHugr> for PersistentReplacement

const UNCHANGED_ON_FAILURE: bool = true

If true, Patch::apply’s of this rewrite guarantee that they do not mutate the Hugr when they return an Err. If false, there is no guarantee; the Hugr should be assumed invalid when Err is returned.

type Outcome = ()

The type returned on successful application of the rewrite.

fn apply(self, h: &mut PersistentHugr) -> Result<Self::Outcome, Self::Error>

Mutate the specified Hugr, or fail with an error.