Static-analyzed accumulating type lists

language design
1

Hi folks, this may seem like kind of a big, odd and specific topic, but it goes much deeper into the compiler than I first thought so I think the internals forum is still the better place, but be free to correct me :>

This year, I've tried to wrap my head around how some could make a zero-cost but really low-level framework for modelling UI. The goal here was to be modular and give the feeling of writing component functions similar to React etc. but actually having code generated that resembles low level structs with setters that call other effects etc.
This means I want to write smth like let count = signal(0); but letting the compiler know that this widget is exactly (i32,) big and that the value can be stored in that thing on the stack, so no hidden allocations.

After many experiments, I've found a "solution" which uses name shadowing of a &mut tuple, which uses the type inference to resolve that tuple. An example of how this looks can be found here.
A problem with that approach is that it's pretty fragile, I have to shadow the store on every statement that needs it and can't use a decl macro because of hygiene. Proc macros are slow, and when I would want to pass the store to another function instead of just storing something, the macro wouldn't cover it. Also, this whole construct breaks at the point where I use another function instead of closures, as I can't just specify store: Store<_> as an argument, but need to name it, which makes the whole type inference thing impossible.

So, after this wall of text, sorry for that, why what do I want/need?
The thing that made me create this topic was that even in this narrow use-case of a library, I already had found use twice, one time for storing values, and one time for creating a chain of callbacks on compile time. So I wonder if there are more use-cases out there. If so, I would like to ask if we could get language support for those compile-time self-modifying/accumulating types? Or maybe I am overseeing another way of doing something like that which doesn't break on the first normal function declaration?

Also sorry for not proposing something directly after such a long post, but I feel like I don't know enough of the internals of the compiler to propose anything good enough for rust.

Thanks a lot and have a great day!

2

Sounds like variadic generics could help

1 Like
3

Well, it may help with the unsafe pointer magic to break down tuples, so that I can just write let (val, ...store) = store; but that would be it. It's nothing that I've not already solved and has the same problems as my current approach. E.g. for functions, the inference still won't work.

4

This blog post I feel covers the stable compatible technique very well:

along with everything else they wrote about frunk.

Given that store is moved by each operation that adds to the store, that prevents accidental usage of a stale store, at least. If you want to hide the store some, you could sugar it with something like

open!(Composition, || {
    let stateful!(counter) = new!(Signal, 0);
    let stateful!(chain, incr) = new!(ReactionChain);

    react!(chain, || {
        let val = counter.update(|x| x + 1);
        println!("counter is now {val}");
    });
    chain.close();

    assert_eq!(counter.get(), 0);
    incr();
    assert_eq!(counter.get(), 1);
    incr();
    assert_eq!(counter.get(), 2);
});

The trick is that mixed-site macro_rules! hygiene allows you to define and use more macros, as those are item names; e.g.

macro_rules! _define_open_helpers {([$_:tt] $store:ident) => {
    macro_rules! stateful {($_($pat:tt)*) => {
        $crate::…::WithStore {
            store: $store,
            value: ($_($pat)*),
        }
    }}
    macro_rules! new {($T:ty $_(, $_($args:tt)*)?) => {
        <$T as $crate::…::Build>::on(
            $store,
            ($_($_($args)*)?),
        )
    }}
}}
macro_rules! open! {($T:ty, || $b:block) => {
    <$T as $crate::…::Open>::open(|state| {
        $crate::_define_open_helpers!([$] state);
        let result = $b;
        state.close();
        result
    })
}}
macro_rules! react {($reactor:ident, $action:expr) => {
    let $reactor = <_ as $crate::…::React>::react(
        $reactor,
        $action,
    );
}}

The trickiest part is devising a way to give inner macro definitions repetitions. At some point it'll be easily accessible with $$; until then we'll need to use an extra step of indirection by using a $ token via a macro binding, conventionally $_:ident. I'm sure with a little TLC you could smooth the macro experience a bit further as well.

This is where argument impl Trait is useful. Define functions that take e.g. impl State instead of a concrete type, and provide something like open! for the reified state parameter to get back into sugar mode in an existing state instead of opening a new one.

Unfortunately it's not possible to generally define a function which accepts e.g. impl State + Get<T>, as the frunk technique requires inferring I in Get<T, I>, where I is a type level index selecting what position in the HList the T is. You probably could be able to find a solution via sculpting in the caller[1] to take State![$($T),*], with the function morally accepting an HList with a known prefix, but the type and macro trickery to prove that out escapes me at the moment.

This high level design pattern is generally called a type-safe builder pattern, where some kind of builder proxy provides fn(self) -> SelfButDifferent methods. HList accumulation is a niche instance of the pattern — generally builders have a finite set of automata states, and/or dynamically collect some state — but it's a proper implementation of the pattern.

  1. Using frunk method names, very roughly, open!(T, f) would become T::open(|state| { let (need, rest) = state.sculpt(); f(need + rest) }). ↩︎

1 Like
5

Wow, thanks a lot for all those resources!

I gave myself another try at an trait-based approach, and I think it works now :smiley:

Another thing I somehow completely forgot to share here was the downpassing of such accumulating types.
Imagine this:

a
  calls b
    calls c
      adds reaction to chain
    calls d
      adds reaction to chain

Now I have to explicitly specify the whole input and output path of the reactionchain for a, b, c and d. It may be at least partially resolvable with writing impl Chain instead of the whole type each time as this is possible now, but I now still have to specify a value in the output tuple for each input, which then also gets messy and is an easy place for ordering mistakes. I just now wonder if out parameters for functions could serve here as the name-shadowing equivalent of &mut...