Infer extension-requirements for nested DFGs

[acl-cqc]

Nodes such as DFG, CFG, BasicBlock etc. are created wth a FunctionType that specifies a delta:

hugr/src/types/signature.rs

Line 25 in 1a07cd9

pub extension_reqs: ExtensionSet,

This must be specified explicitly at creation time - one cannot say "None" as one can for input_extensions. However it would be nicer if one could, such that the inference algorithm then infers it, which I believe is possible as follows.

(This would require some change to the FunctionType/NodeType/DFG structures to allow specifying an Option, and then mutating it when inference is complete, in discussion below)

During inference, we both 1. constraint the input+output variables to match those at the Input and Output nodes of the DFG:

hugr/src/extension/infer.rs

Lines 283 to 288 in 1a07cd9

	if let Some([input, output]) = hugr.get_io(node) {
	for dir in Direction::BOTH {
	let m_input_node = self.make_or_get_meta(input, dir);
	self.add_constraint(m_input_node, Constraint::Equal(m_input));
	let m_output_node = self.make_or_get_meta(output, dir);
	self.add_constraint(m_output_node, Constraint::Equal(m_output));

and 2. constrain the outputs to be the input plus the specified delta:

hugr/src/extension/infer.rs

Lines 314 to 318 in 1a07cd9

	self.gen_union_constraint(
	m_input,
	m_output,
	node_type.op_signature().extension_reqs,
	);

If we simplify avoid the second constraints in such cases, the constraints with the Input/Output nodes should be sufficient to calculate both. We can then compute the delta as the difference between the two. (If this last seems dubious - indeed the delta could also include any subset of the inputs - then this is no worse than at present, where such a delta specified by the programmer would be accepted by inference and validation. We could instead move to a system where the Input node also has empty input extensions, but that's another issue.)

[acl-cqc]

Thus, two possible solutions:

• Recursively infer delta from the nested subgraph first, use that in the outer graph. This won't handle functions containing recursive calls (you need the delta from the function body to infer around the call node) - user-provided annotations on functions?
• Try to generalize "Plus" constraint to merge two variables. This might magically work or break everything, not sure. Maybe it's no worse than what we have now, but likely impossible to solve such a constraint backwards (as per Inference Redux #780 )

[acl-cqc]

This would require some change to the FunctionType/NodeType/DFG structures to allow specifying an Option, and then mutating it when inference is complete

So it's worth thinking about this because it could be quite disruptive. There are several possible methods, including:

1. Change FunctionType to store an Option<ExtensionSet>. Then validation checks all these (including those nested within port/edge types) are non-None. However it's not clear that None is useful in many places, e.g. outside of a node's signature(). Moreover having to deal with Option rather than ExtensionSet everywhere one has a FunctionType makes this seem like the most disruptive method.
2. Separate Node signature() from FunctionType; the former has an Option, the latter a non-optional ExtensionSet. Given we are working on Separate type of node signature from function value #1094 (e.g. refactor!: Separate Signature from FuncValueType by parametrizing Type(/Row)/etc. #1138) this seems possible but could be very complex.
3. Leave all signatures/FunctionTypes containing an ExtensionSet, but allow inference to mutate it (!). There are are few further variants...
   • Allow any container node's extension_reqs to be mutated. This means that extension-delta-inference will never fail, but seems a bit wild.
   • Allow, say, only container extension_reqs that are currently empty to be inferred.
   • Restrict inference to e.g. only increasing extension_reqs, or only reducing them.
   • As a variant on the latter, suppose some kind of special ExtensionId wildcard/universal-set, which could be seen as meaning either "all possible extensions" or "please infer me". An ExtensionSet containing both the special please-infer and other ExtensionIds coould mean "at least the others, possibly more". We might want to make the default ExtensionSet contain only the wildcard, and (even more likely) make the builder default to using just the wildcard.
4. Remove extension_reqs from FunctionType, so the latter is just inputs/outputs; then a Type(Enum)::Function stores both a FunctionType (in/out) and a non-optional ExtensionSet; whereas a node has a "signature() -> FunctionType" and a separate extension_delta: Option<ExtensionSet> that can be set (from None) by inference. [Yes, this is a different spin on 2., but it might be a good way of decoupling the delta from the FunctionType-does/doesn't-have-rowvariables question.]

[acl-cqc]

Closing after #1195, front-end/builder changes can be separate issue (and #1237 is a separate issue!)