Generic Rewrite trait over HugrMut type

[lmondada]

Currently Rewrite bakes in the types that it can apply to as HugrMut. This means we cannot generalise Rewrite to H: HugrView<Node = N> where N $\neq $Node (as introduced by #1932).

It also makes it impossible to implement this trait on any persistent data structure.

Proposal

We add a generic Subject type that specifies on what types the Rewrite can be applied.

pub trait Rewrite<Subject> {
    type Node;
    ...
    fn verify(&self, h: &Self::Subject) -> Result<...>

    fn apply(self. h &mut Self::Subject) -> Result<...>
    
    fn invalidation_set(&self) -> impl Iterator<Item = Self::Node>;
}

All current impls would then look as follows

impl<H: HugrMut> Rewrite<H> for XYZ {
    type Node = H::Node;
    ...
}

Drawbacks

• Trait is more verbose
• My proposal forces verify and apply to act on the same type (whereas the current version of verify accepts any HugrView)

Thoughts?

[lmondada]

Note that trait Rewrite might soon get renamed, see #588

[aborgna-q]

Do you mean this instead for the current rewrites?

impl<H: HugrMut> Rewrite<H> for XYZ {
    ...
}

Note that that doesn't restrict running verify and apply on the same type.

An alternative would be to use associated types,

pub trait Rewrite {
    type Subject: HugrMut;
    ...
    fn verify(&self, h: &Self::Subject) -> Result<...>

    fn apply(self. h &mut Self::Subject) -> Result<...>
    ...
}

but that's probably too restrictive, as some rewrites may work generically.

[lmondada]

Do you mean this instead for the current rewrites? Note that that doesn't restrict running verify and apply on the same type.

Yes, sorry, corrected the type signature. I don't think the associate type approach would work, you definitely want most rewrites to apply to any H: HugrMut.

You are right that you could use what are effectively different impls to run verify and satisfy on different types. This is nevertheless still strictly weaker than the current API, which guarantees that you can call verify on any HugrView.