hugr icon indicating copy to clipboard operation
hugr copied to clipboard

Confluently persistent Hugr data structure

Open lmondada opened this issue 8 months ago • 1 comments

Create a PersistentHugr struct that allows for non-destructive modifications of Hugrs. In other words https://github.com/CQCL/tket2/pull/773 should be moved/generalised to Hugr.

This is blocked by

  • Agree on hugr mutation naming scheme (https://github.com/CQCL/hugr/issues/588)
  • Generic rewrite over subject type (https://github.com/CQCL/hugr/issues/2052)
  • HugrInternals cannot expose the Hugr, or else HugrView must be implementable without HugrInternals (https://github.com/CQCL/hugr/issues/1926)

lmondada avatar Apr 02 '25 10:04 lmondada

Suggested naming scheme (pending #588)

  • PatchGraph: a whole bunch of Patches that are the result of applying rewrites, possibly conflicting. It's main purpose is to keep Rcs to the Patches that we are interested in during optimisation.
  • PatchHistory: a subgraph of PatchGraph that only contains non-conflicting rewrites that can be applied to obtain a Hugr.
  • PersistentHugr: the main object users will actually interact with. Implements HugrView, but is immutable and fully persistent. Is in fact a wrapper around PatchHistory.
  • Patch: a mostly module-internal struct that are the nodes of the PatchGraph and PatchHistory. It stores the location of an edit within its parent Patches, along with the new subgraph that replaces them. In the first version, the Patch will be a SimpleReplacement.

lmondada avatar Apr 02 '25 11:04 lmondada