Crate hugr_persistent 

Persistent data structure for HUGR mutations.

This crate provides a persistent data structure [PersistentHugr] that implements HugrView. A persistent data structure:

• is cheap to clone,
• shares as much of the underlying data with other versions of the data structure as possible, even as it gets mutated (unlike, say the Rust Cow type),
• in our case, multiple versions of the same data structure can even be merged together (with a notion of “compatibility” between versions).

Persistent data structures are sometimes called immutable data structures, as mutations can always be implemented as cheap clone + cheap mutation. Mutations to the data are stored persistently as a set of [Commit]s 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.

Multiple [PersistentHugr] may use commits from a common [CommitStateSpace]: [PersistentHugr]s derived from mutations of previous [PersistentHugr]s will always share a common state space. A [Walker] can be used on a state space to explore all possible [PersistentHugr]s that can be created from commits in the space.

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 contains a a subset of the commits of a [CommitStateSpace], with the guarantee that they are all 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 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 all [PersistentHugr] and [CommitStateSpace] that refer to it are dropped.
• [PersistentHugr] A data structure that implements HugrView and can be used as a drop-in replacement for a 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] A registry of all commits within the [PersistentHugr]s of the state space. 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.

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