Module-rooted hugrs and node pointers

[aborgna-q]

This proposal tries to simplify the split between how we use runtime hugrs internally here and in tket2 vs how they are serialized, bundled as packages, and emitted by guppy. See #1554.

TLDR: Splitting the hugr root from the portgraph hierarchy root would make the code more straightforward.

The state of things

We seem to be moving towards only supporting module-rooted hugrs;

• Packages only support module-rooted hugrs. The rust implementation does some juggling when loading arbitrary hugrs to wrap them as appropriate.
• hugr-model is designed with this in mind. With the current impl, non-module hugrs will need to be wrapped in a module before being serialized.
• Guppy compiles to packages containing modules with pointers to the entrypoint functions.

This however clashes with how we use hugr internally,

• The builder interfaces both in hugr-py and hugr-rs can define hugrs with any kind of root.
• The unit tests heavily depend on this; we define all kind of small hugrs to try all codepaths.
• We can access sub-regions and parts of the hugr using the HugrView interface, which can have arbitrary root types.
• SimpleRewrites define their replacement using hugrs. Storing a module there would just make things more confusing.

We don't want the serialization format and the in-memory one to diverge semantically, so if we can only store module-rooted graphs then the runtime values should follow suit.

Module-hugrs + region pointers?

If we go with restricting the hugrs to always contain a module at the top, then we should adapt the rest of the code to work with that.

• For builders we either remove the non-module constructors owned variants or make them automatically insert a module first. The first option would affect many unit tests.
• In tket2 programs/circuits, we already store a pointer to a node in the Hugr that contains the entrypoint. As long as every tool produces module-rooted hugrs things should work alright.
• The case of replacements is trickier; we need an owned hugr structure that contains the thing being inserted.
  This could be a module-hugr plus a pointer to a node, but we then have to decide what happens with extraneous nodes and edges. It could be a way to—say— replace some nodes with a call to a newly defined function in the module, but that may be outside the scope SimpleReplace.

All in all, I think this could work for our usecases. It also has good implications in terms of runtime...

Module-hugrs structs + region pointers?

Lets say we split the root field in the hugr definition,

pub struct Hugr {
	...
	/// A node containing the hugr definition.
	/// 
	/// External nodes that are not descendants of this may be
	/// returned by some operations.
	///
	/// Use `Hugr::module_root` to get a handle of the module definition
	/// containing all nodes in the graph.
    root: Node,
	/// The single root node in the portgraph hierarchy. (old `root`)
    portgraph_root: portgraph::NodeIndex,
}

With this, we can still define e.g. "Dfg-hugr"s as ones where the root points to a DFG, independently of what the portgraph root is.

This is similar to DescendantView, except that:

• It owns the underlaying graph, rather than a read-only reference to it.
• The extra nodes are still there, HugrView::node_count, nodes, linked_ports, etc. all take into account the external nodes and edges.
• The structure is HugrMut, it can be mutated.

The current HugrView definition requires all nodes to be descendants of the root, so DescendantView has to check whether a node is in the hierarchy tree on each operation.

The DescendantView filtering is implemented at the portgraph level with a NodeFiltered graph adapter which computes the nodes that should be included on-the-fly by traversing the hierarchy and storing them in a HashMap for caching. This hashmap gets thrown away on any hugr mutation introduces contention between concurrent accesses.

The restriction of not containing out-of-tree nodes in a HugrView is due to keeping reachability from the root to all nodes. Splitting the portgraph root from the view root means we can relax that restriction.
Doing away with the node filtering should have a big impact on performance.

Implementation guide

🦀 rust:

• hugr-rs::Hugr: Split the portgraph_root from the hugr's root node pointer as described above.
• hugr-rs::HugrView: No code changes required, but relax the constraint of only including descendant nodes from the root. The hierarchical root can be accessed via View::base_hugr
• hugr-rs::HugrMut: Mostly unchanged.
  insert_hugr needs to be redefined. Most current uses should call insert_from_view instead (maybe with an owned variant?).
• SimpleReplacement: The replacement is still restricted to dfg-hugrs (or function defs). Possibly we should add the restriction that the root is a direct definition in the module, and no other definitions are present.
• Graph adapters:
  • DescendantsGraph could be removed entirely, and replaced with the more flexible &Hugr (or even mutable refs).
  • SiblingGraph was there to provide more performant filtered views when children were not required. We may be able to remove it too.
• Builders: Auto-wrap builders in a module when using e.g. a DfgBuilder. Should not require other changes.
• Validation: Use the module root to validate instead of root.
• Rendering: Highlight the root node in some way.
• Packages: At most one hugr may have a non-module root.
  - Loading packages would be simplified too, we could drop the patchy conversion between hugrs and module-rooted packages we do currently.

🐍 python:

• Hugr: Add a module_root parameter
  • insert_hugr will require some update to only insert the descendants nodes.
• Builders: Auto-wrap builders in a module when using a DfgBase builder.
• Rendering: Highlight the root node in some way.
• Packages:
  • At most one hugr in the package may have a non-module root.
  • Hugrs themselves could implement NodePointer. That would either need inheritance, or redefining NodePointer as a protocol.

📜 hugr-model:

• Always serialize the full module-rooted graph, and add a node-pointer to the entrypoint.

Alternatives

We could still allow non-module hugrs in the in-memory representation.
Serialization roundtrips would need some metadata to know when to wrap/unwrap the non-module nodes (and some way to encode the root node id in a serialization-stable way).

We could define some extra layer on top of a hugr to accomodate the "hugr+pointer" structures curretly required by tket2, guppy, and packages. This would be similar to what's proposed here, but would add yet another different structure that's almost but not quite a Hugr, so it would complicate the API without much benefit.

[ss2165]

Alternative (?)

Resurrect the idea of Hugr being parametrised by root types. Either reuse OpTag for this or set up a dedicated Root enum. Then

type Module = Hugr<RootModule>;
type Dfg = Hugr<RootDfg>;

etc.

Conversion to/from model is only implemented on Hugr<RootModule>. All other Hugr<Root> have to have From/Into Hugr<RootModule> implemented for conventional encoding/decoding. This may use dedicated metadata keys for the kind of "pointing" you talk about above.

This convention would need to be re-encoded in the python, but i don't think that's too bad because the actual number of roots is constrained nicely.

I'm not sure whether this actually meets your requirements so let me know.

[acl-cqc]

I am not sure I really follow what the portgraph change does - is the portgraph-root an ancestor of the hugr/dfg-root, or what? Can you give examples of how allowing the two roots to be different address which use cases?

[aborgna-q]

Yes, we are just relaxing the requirement that portgraph root is the hugr root to portgraph root is an ancestor of the hugr root. So the hugr points to subtree of the full hierarchy.

This is similar to adding an "entrypoint" attribute to the hugr, e.g. for guppy compilation artifacts.
But the main benefit of the solution described above is that the hugr-view interface things remains mostly unchanged.
hugr.root works in the same way as always, but now hugr.neighbours(node) may return things that are not descendants of that root. Internally, the portgraph graph contains our hugr and may also define other functions or constants used within.

[acl-cqc]

Ok, so the Hugr now contains things that are not descendants of the hugr.root().

In which case the hugr.root really isn't the root - it's just a labelled entrypoint? When you say,

The current HugrView definition requires all nodes to be descendants of the root, so DescendantView has to check whether a node is in the hierarchy tree on each operation.

"the root" is what you now call the "portgraph root", and "a node is in the hierarchy tree" if it's descended from the portgraph root?

In which case, the "portgraph root" is the thing we currently call root. What you are wanting to do is to add a new field, which I might call entrypoint: Node. Can't we do that just with a new structure that stores a Hugr(/View/reference/etc. - maybe #1636 becomes relevant), that maybe Deref/Asrefs to the Hugr(View), and that has a new accessor for the entrypoint?

[acl-cqc]

So without arguing about the portgraph change - I think the uses we have for non-module-rooted Hugrs ATM are good and it would be nice to continue supporting them.

I am less clear why packages and hugr-model need the Hugr to be Module-rooted. Bearing in mind all declarations (FuncDecl, FuncDefn, etc., perhaps OpDecl in future) are scoped, they could go anywhere, even inside another root. So the fact that guppy happens to produce a Module is happenstance. Is it not possible to extend hugr-model to support non-Module-root? And then if OpDecl happens (extensions are declared inside Hugrs rather than outside) then that resolves the package problem too.

A lot of "if"s there. But in the meantime, Seyon's suggestion of parametrization by root type seems good, would that fix things for now??

[aborgna-q]

After some irl discussion, I think we can split the "module-root only" part out of this RFC.

For things like manually built hugrs, it makes sense not to add an implicit module on top that is shown on the renders.
The benefits listed above don't really require the portgraph root to be anything in particular, and my usecase for tket2 doesn't care either (module-roots is just a specific case), at least once #1613 is implemented and we don't need to convert things to packages anymore.