How to add optional type "tags" for a hierarchy of structs?

help
1

I maintain a crate ( bex ) that works with boolean expressions as graphs.

Conceptually, both the nodes and their associated boolean variables are referenced by simple usize values, but I wrap these in types called NID and VID (for "node ID" and "variable ID") both for clarity and so I can add associated functions to the individual types.

From these two primitives, I build up various graph structures. For example, I often have use
struct VHL { v: VID, hi: NID, lo: NID } when I need a binary-tree-node like structure that branches on input variable v and evaluates to the hi branch whenever v==1, and lo when v==0.

Similarly, there's struct HiLo { hi:NID, lo:NID} if I don't need the variable at the moment, and then higher order structs like VHLBase, VHLParts, HiLoCache, VHLRow, VHLScaffold, etc, that build these things up into complicated graph structures.

Now the problem is that often I want to work with two or more of these graph structures at a time. For example, I have one kind of graph structure called a BDD and another called an ANF, and I might want to convert a set of nodes from one to the other. Or, I might want to experiment with re-ordering the variables to see how the graphs change (because doing this can make them much bigger or smaller).

Because of this, I often find myself dealing with multiple sets of nodes. I found that wrapping the NIDS in simple wrapper types really helps me to keep the code straight in my head. For example, if I'm translating from a source structure to a destination structure, I use a pair of types like this:

struct SrcNid = { n: NID }
struct DstNid = { n: NID }

This is easy, and it makes me very happy that I can use the type markers for free.

But now I want to do the same thing for entire structures, and I might have multiple "tags" that I want to apply to my primitives.

For example, the VHLScaffold type I'm working on has the ability to re-order variables internally while keeping track of the user's original ordering. So when I copy items between two VHLScaffolds, I wind up with a bunch of different functions, and it would be nice to be able to tag the parameters with Src, Dst, In, Ex, or even pairs of these (ExSrc InSrc ExDst, InDst).

The problem is that I want these tags to apply not just to one struct, but to the entire family of structures. When I ask a XNID<ExSrc> for it's associated variable, I want to get back a XVID<ExSrc>, and likewise, I want some kind of XVHLScaffold<T> that acts as if it contains XVHLRow<T> and deals with XVHL<T> and XHilo<T> and so on. (I'm just using the X prefix as a placeholder notation.)

OTOH, most of the time I don't want to use tags.

I know I could just define all my primitives and associated functions with a <T> parameter from the start, and then when I don't need tags, just hide it with something like type NID = XNID<NoTag> or something, but I'd rather not have to litter my code with normally-unused <T> parameters and PhantomData<T> members.

So I guess ideally, I would be able to take an existing type hierarchy and lift it up into a new type hierarchy that used these tags.

Is there any way to get close to this in rust without writing the code by hand, perhaps with procedural derive macros? (And more importantly, do such macros / techniques already exist?)

2

Would default type parameters work for you? i.e. struct NID<T = NoTag> { ... }

1 Like
3

Edit: I put this in the playground and got it working after a few changes; The code below hasn’t been updated; it allows this code:


fn main() {
    let f = |x:&usize| format!("{}", 3* *x);

    println!("{:?}", f.call_tagged(7));
    println!("{:?}", f.call_tagged(Src(7)));
    println!("{:?}", f.call_tagged(Src(Ex(7))));

}

to produce the output:

"21"
Src("21")
Src(Ex("21"))

I haven’t run it through the compiler, but I think you should be able to do something like this:

trait Tagger<Inner> {
    type Out: Borrow<Inner>;
    fn tag(val: Inner)->Self::Out;
}

// Start def_tag!{Src} output
struct Src<T>(T);

impl<T,U> Borrow<T> for Src<U> where U:Borrow<T> { /* ... */ }
impl<New, Old:Tagger<New>> Tagger<New> for Src<Old> {
    type Out = Src< <Old as Tagger<New>>::Out >;
    fn tag(val:New)->Self::Out { Src( Old::tag(val) ) }
}
// End def_tag!{Src}

// Start untagged!(NID)
impl<New> Tagger<New> for NID {
    type Out = New;
    fn tag(val:New)->New { val }
}

You can then write functions that are generic over tagged values, and any sequence of the tagging wrapper structs will be stripped off and re-added at the end:

fn<Nid: Borrow<NID>+Tagger<VID>>
get_vid(nid: &Nid) -> <Nid as Tagger<VID>>::Out {
    let nid: &NID = nid.borrow();
    let result: VID;
    /* ... */
    Nid::tag(result)
}

It’s a bit cumbersome overall, but might be a reasonable basis for a suite of macros.

1 Like
4

Huh! Interesting. I had no idea this was a thing. I don't even see it in the docs. I'll definitely explore this. Thanks!

5

This is fantastic! I'm still wrapping my head around it, but I like the idea of using nested wrapper structs, and the tag/untag combinators. I'm definitely going to study this more. Thanks so much!

1 Like
6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.