Reversing an HList: Infinite recursion

I've been trying to wrap my head around frunk, and tried to write something that can reverse the order of an HList. The code below is the closest I've gotten; if you comment out all of the fn call(...) declarations, it can produce a type that is properly reversed. Unfortunately, adding the method definition sends the type checker into an infinite recursion loop.

Something in this code is causing the type checker to attempt verification of ever-larger compound types, but calling the function should never need an intermediate type larger than the input:

  • How can this code be fixed?
  • What's the best way to go about debugging similar issues when they arise?

Edit: Thinking that the problem might be related to the variance change by having the call method, I tried forcing it to be invariant by adding this to the trait:

    const PHANTOM: PhantomData<(*mut Args, *mut Self::Out)>;

It had no effect: the code still compiles without the call methods and fails to compile with them

/Edit


#![recursion_limit = "8"]

#[derive(Debug)]
struct HNil;

#[derive(Debug)]
struct HCons<H, T>(H, T);

trait Call<Args> {
    type Out;
    fn call(args: Args) -> Self::Out;
}

struct Reverse;

impl<L> Call<(L,)> for Reverse
where
    Reverse: Call<(L, HNil)>,
{
    type Out = <Reverse as Call<(L, HNil)>>::Out;
    fn call((list,): (L,)) -> Self::Out {
        Reverse::call((list, HNil))
    }
}

impl<H, T, Result> Call<(HCons<H, T>, Result)> for Reverse
where
    Reverse: Call<(T, HCons<H, Result>)>,
{
    type Out = <Reverse as Call<(T, HCons<H, Result>)>>::Out;
    fn call((HCons(h, t), res): (HCons<H, T>, Result)) -> Self::Out {
        Reverse::call((t, HCons(h, res)))
    }
}

impl<Result> Call<(HNil, Result)> for Reverse {
    type Out = Result;
    fn call((HNil, result): (HNil, Result)) -> Self::Out {
        result
    }
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error[E0275]: overflow evaluating the requirement `Reverse: Call<(HCons<_, _>, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HNil>>>>>>>)>`
  --> src/lib.rs:22:9
   |
22 |         Reverse::call((list, HNil))
   |         ^^^^^^^^^^^^^
   |
   = help: consider adding a `#![recursion_limit="16"]` attribute to your crate (`playground`)
   = note: required because of the requirements on the impl of `Call<(HCons<_, HCons<_, _>>, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HNil>>>>>>)>` for `Reverse`
   = note: required because of the requirements on the impl of `Call<(HCons<_, HCons<_, HCons<_, _>>>, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HNil>>>>>)>` for `Reverse`
   = note: required because of the requirements on the impl of `Call<(HCons<_, HCons<_, HCons<_, HCons<_, _>>>>, HCons<_, HCons<_, HCons<_, HCons<_, HNil>>>>)>` for `Reverse`
   = note: required because of the requirements on the impl of `Call<(HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, _>>>>>, HCons<_, HCons<_, HCons<_, HNil>>>)>` for `Reverse`
   = note: required because of the requirements on the impl of `Call<(HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, _>>>>>>, HCons<_, HCons<_, HNil>>)>` for `Reverse`
   = note: required because of the requirements on the impl of `Call<(HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, _>>>>>>>, HCons<_, HNil>)>` for `Reverse`
   = note: required because of the requirements on the impl of `Call<(HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, _>>>>>>>>, HNil)>` for `Reverse`
   = note: required because of the requirements on the impl of `Call<(HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, HCons<_, _>>>>>>>>,)>` for `Reverse`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0275`.
error: could not compile `playground`.

To learn more, run the command again with --verbose.

I managed to get this working by using fully-qualified calls everywhere, so the problem seems to come from the compiler trying to verify there's only one inference result. It seems like it could have gotten that from the trait definition and the method argument list, but I guess not; maybe chalk will improve this.

(Playground)

#![recursion_limit = "8"]

#[derive(Debug)]
struct HNil;

#[derive(Debug)]
struct HCons<H, T>(H, T);

trait Call<Args> {
    type Out;
    fn call(args: Args) -> Self::Out;
}

struct Reverse;

impl<L> Call<(L,)> for Reverse
where
    Reverse: Call<(L, HNil)>,
{
    type Out = <Reverse as Call<(L, HNil)>>::Out;
    fn call((list,): (L,)) -> Self::Out {
        <Reverse as Call<(L, HNil)>>::call((list, HNil))
    }
}

impl<H, T, Result> Call<(HCons<H, T>, Result)> for Reverse
where
    Reverse: Call<(T, HCons<H, Result>)>,
{
    type Out = <Reverse as Call<(T, HCons<H, Result>)>>::Out;
    fn call((HCons(h, t), res): (HCons<H, T>, Result)) -> Self::Out {
        <Reverse as Call<(T, HCons<H, Result>)>>::call((t, HCons(h, res)))
    }
}

impl<Result> Call<(HNil, Result)> for Reverse {
    type Out = Result;
    fn call((HNil, result): (HNil, Result)) -> Self::Out {
        result
    }
}

fn main() {
    #[derive(Debug)]
    struct Hello;
    println!(
        "{:?}",
        <Reverse as Call<(HCons<&'static str, HCons<Hello, HNil>>,)>>::call((HCons(
            "World!",
            HCons(Hello, HNil)
        ),))
    )
}
1 Like