Module persistent

Persistent data structure for HUGR mutations.

This module provides a persistent data structure PersistentHugr that implements crate::HugrView; mutations to the data are stored persistently as a set of Commits along with the dependencies between the commits.

As a result of persistency, the entire mutation history of a HUGR can be traversed and references to previous versions of the data remain valid even as the HUGR graph is “mutated” by applying patches: the patches are in effect added to the history as new commits.

The data structure underlying PersistentHugr, which stores the history of all commits, is CommitStateSpace. Multiple PersistentHugr can be stored within a single CommitStateSpace, which allows for the efficient exploration of the space of all possible graph rewrites.

Overlapping commits

In general, CommitStateSpace may contain overlapping commits. Such mutations are mutually exclusive as they modify the same nodes. It is therefore not possible to apply all commits in a CommitStateSpace simultaneously. A PersistentHugr on the other hand always corresponds to a subgraph of a CommitStateSpace that is guaranteed to contain only non-overlapping, compatible commits. By applying all commits in a PersistentHugr, we can materialize a Hugr. Traversing the materialized HUGR is equivalent to using the crate::HugrView implementation of the corresponding PersistentHugr.

Summary of data types

• Commit A modification to a Hugr (currently a SimpleReplacement) that forms the atomic unit of change for a PersistentHugr (like a commit in git). This is a reference-counted value that is cheap to clone and will be freed when the last reference is dropped.
• PersistentHugr A data structure that implements crate::HugrView and can be used as a drop-in replacement for a crate::Hugr for read-only access and mutations through the PatchVerification and Patch traits. Mutations are stored as a history of commits. Unlike CommitStateSpace, it maintains the invariant that all contained commits are compatible with eachother.
• CommitStateSpace Stores commits, recording the dependencies between them. Includes the base HUGR and any number of possibly incompatible (overlapping) commits. Unlike a PersistentHugr, a state space can contain mutually exclusive commits.

Usage

A PersistentHugr can be created from a base HUGR using PersistentHugr::with_base. Replacements can then be applied to it using PersistentHugr::add_replacement. Alternatively, if you already have a populated state space, use PersistentHugr::try_new to create a new HUGR with those commits.

Add a sequence of commits to a state space by merging a PersistentHugr into it using CommitStateSpace::extend or directly using CommitStateSpace::try_add_commit.

To obtain a PersistentHugr from your state space, use CommitStateSpace::try_extract_hugr. A PersistentHugr can always be materialized into a Hugr type using PersistentHugr::to_hugr.

Re-exports

pub use walker::PinnedWire;

pub use walker::Walker;

Modules

walker

Incremental traversal and construction of PersistentHugrs from CommitStateSpaces.

Structs

Commit

A patch that can be applied to a PersistentHugr or a CommitStateSpace as an atomic commit.

CommitStateSpace

A set of commits with directed (acyclic) dependencies between them.

PatchNode

A HUGR node within a commit of the commit state space

PersistentHugr

A HUGR-like object that tracks its mutation history.

PointerEqResolver

A resolver that considers two nodes equivalent if they are the same pointer.

Enums

InvalidCommit

An error that occurs when trying to add a commit to a commit state space.

Type Aliases

CommitId

A copyable handle to a Commit vertex within a CommitStateSpace

PersistentReplacement

A replacement operation that can be applied to a PersistentHugr.