Crate hugr_persistent

Source
Expand description

Persistent data structure for HUGR mutations.

This crate provides a persistent data structure [PersistentHugr] that implements HugrView; 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.

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 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 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] 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].