Tracking issue for extension requirement inference

[croyzor]

New plan following Re^n-super-redux proposed by Lukas:

• Ignore input_extensions and (non-hierarchy) edges, validate only that extension deltas on nodes are a subset of their parent - this is feat!: Validate Extensions using hierarchy, ignore input_extensions, RIP inference #1142
• phase 2:
• Cleanup: remove input_extensions and NodeType - this is refactor!: Remove NodeType and input_extensions #1183
• Custom operations implicitly require their extension #388
• Infer extension-requirements for nested DFGs #640 (this becomes even more important than under the input_extensions-based scheme because we don't have the "empty delta so inputs = outputs" escape hatch)
• builder front-end for building DFGs (dfg_builder): in feat: Helper functions for requesting inference, use with builder in tests #1219 (DFGBuilder::new takes a FunctionType so no need to update)
• conditional_builder, (simple_)block_builder / entry_builder - in fix!: Ops require their own extension #1226
• Remaining bits of builder frontend for inference #1318
• phase 3:
• Unclear when/whether we need Infer extension-deltas for FuncDefn's #1237 (before/after removing feature flag - let's see how we do before removing the flag)
• We'll want Polymorphic top-level Hugrs / Substitution across nodes of Hugr #709 at some point
• Update spec
• Remove feature flag

---

Below relates to the "Reredux" where we retain input_extensions but switch to only subset constraints between them (effectively, every edge gains a lift node, with the delta of the lift being inferred) - detailed in https://cqc.atlassian.net/wiki/spaces/~221321769/pages/2803236998/HUGR+Extension+Inference+reredux.

Redux Plan:

• refactor: Validate hugrs before extension inference is run #943 (Preliminary to 713 and 918)
• Handle ExtensionSet type parameters in inference #713
• Validation for graphs with resource variables #457
• (Maybe?) Extension Inference: infer one layer at a time #918
• Update extension inference to use subset constraints #919
• Rewrite extension section of spec to reflect current behaviour #745

At this point, the following issues can be dropped (and Lift nodes removed):

• Add lift nodes after extension requirement inference #423
• refactor: Generalise Lift nodes to ExtensionSets #819

And these should become easy:

• bug: Two call nodes for the same function must have matching resources #695
• Custom operations implicitly require their extension #388

At which point we hopefully should find the system is usable enough to turn inference back on (no more feature gate)

Then we should revisit

• Extension Inference for functions relies on builder #702
• Polymorphic top-level Hugrs / Substitution across nodes of Hugr #709

Finally, we hope this last step is an "optional extra" / improvement, rather than part of the MVP:

• Infer extension-requirements for nested DFGs #640

[acl-cqc]

A few suggestions...[EDIT: all these now redundant following the "Reredux" on confluence and "Redux plan" above]

• Can we make lift nodes, and Plus constraints, take an ExtensionSet rather than a single Extension?
• ....and then, can we make Lift nodes not specify the ExtensionSet, and get inference to figure it out?

Even that might be a lesser step than #423, but I'm wondering how easy that will be

We might want to work on error reporting. Picking out a random (HashSet-iteration-order) location (i.e. (Node,Direction)) for each Meta (in report_mismatch) isn't terribly helpful.

Can we allow a non-mutating infer_and_validate that calls validate_with_extension_closure passing the union of the solution and closure? (These have disjoint keys, right)

• Rename gen_union_constraint to gen_plus_constraint, or rename Constraint::Plus to Constraint::Union