Type gymnastics of heterogeneously-typed lists

[Evian-Zhang]

I'm designing a pass system inspired by frunk.

This is a little introduction of the Selector in frunk

Roughly speaking, frunk uses a Selector to simulate specialization in a very graceful way:

pub struct HCons<H, T> {
    pub head: H,
    pub tail: T,
}
pub trait Selector<S, I> {
    fn get(&self) -> &S;
    fn get_mut(&mut self) -> &mut S;
}
impl<T, Tail> Selector<T, Here> for HCons<T, Tail> {
    fn get(&self) -> &T {
        &self.head
    }
    fn get_mut(&mut self) -> &mut T {
        &mut self.head
    }
}

impl<Head, Tail, FromTail, TailIndex> Selector<FromTail, There<TailIndex>> for HCons<Head, Tail>
where
    Tail: Selector<FromTail, TailIndex>,
{
    fn get(&self) -> &FromTail {
        self.tail.get()
    }
    fn get_mut(&mut self) -> &mut FromTail {
        self.tail.get_mut()
    }
}

With the introduction of the second generic parameter, Rust compiler could infer type with some kind of specialization. Now we can use this like:

let h = hlist![1i32, 2u32, "hello", true, 42f32];

// Often, type inference can figure out the type you want.
// You can help guide type inference when necessary by
// using type annotations.
let b: &bool = h.get();
if !b { panic!("no way!") };

// If space is tight, you can also use turbofish syntax.
// The Index is still left to type inference by using `_`.
match *h.get::<u32, _>() {
    2 => { }
    _ => panic!("it can't be!!"),
}

I design a pass trait as

trait Pass {
    fn do_a<I>(pass_chain: &mut PC, ...)
    where
        PC: Selector<Self, I>;
    fn do_b<I>(pass_chain: &mut PC, ...)
    where
        PC: Selector<Self, I>;
    // ...
}

Where a pass chain would be something like a hlist containing different passes.

In the impl of each do_a, do_b, I want each pass can pass the execution towards other funcs in the same pass, or pass to next pass, or pass to the initial pass to redo the whole thing, which means I want each pass to have abilities to invoke do_a, do_b of current pass, next pass, and initial pass of the pass chain.

As a result, I modify the Selector trait like this:

pub trait Selector<S, I> {
    type Next;

    fn get_current(&self) -> &S;
    fn get_current_mut(&mut self) -> &mut S;

    fn get_next(&self) -> &Self::Next;
    fn get_next_mut(&mut self) -> &mut Self::Next;
}

impl<T, Tail> Selector<T, Here> for (T, Tail) {
    type Next = Tail;

    fn get_current(&self) -> &T {
        let (head, _) = self;
        head
    }

    fn get_current_mut(&mut self) -> &mut T {
        let (head, _) = self;
        head
    }

    fn get_next(&self) -> &Tail {
        let (_, next) = self;
        next
    }

    fn get_next_mut(&mut self) -> &mut Tail {
        let (_, next) = self;
        next
    }
}

impl<Head, Tail, FromTail, TailIndex> Selector<FromTail, There<TailIndex>> for (Head, Tail)
where
    Tail: Selector<FromTail, TailIndex>,
{
    type Next = Tail::Next;

    fn get_current(&self) -> &FromTail {
        let (_, tail) = self;
        tail.get_current()
    }

    fn get_current_mut(&mut self) -> &mut FromTail {
        let (_, tail) = self;
        tail.get_current_mut()
    }

    fn get_next(&self) -> &Tail::Next {
        let (_, tail) = self;
        tail.get_next()
    }

    fn get_next_mut(&mut self) -> &mut Tail::Next {
        let (_, tail) = self;
        tail.get_next_mut()
    }
}

However, I could not find out how to write a generic bound for the Next element and PC, so that I could write codes like

impl Pass for PassA {
    fn do_a<I>(pass_chain: &mut PC, ...)
    where
        PC: Selector<Self, I>
    {
         PC::Next::do_a(pass_chain, ...); // Let next passes do other things
         PC::do_a(pass_chain, ...); // Redo the whole thing from the beginning of the chain
    }
}

This problem has made me struggled for about two weeks. Any advice will be appreciated!