rustc loop forever in case of polymorphic recursion

[NawfelBgh]

Hello,
rustc goes into an infinite loop when compiling this

enum Dequelette<T> {
    Deque1(T),
    Deque2(T, T),
    Deque3(T, T, T),
    Deque4(T, T, T, T)
}

// this is a purely functional deque implemented with a finger tree
// different versions are supposed to share nodes
// that is why i used @
enum Deque<T> {
    Empty,
    Single(T),
    Multi(@Dequelette<T>, @Deque<Dequelette<T>>, @Dequelette<T>)
}

trait IDeque<T> {
    fn enque_right(&self, T) -> @Self;
    fn enque_left (&self, T) -> @Self;
    fn deque_right(&self) -> @Self;
    fn deque_left (&self) -> @Self;
    fn peek_right (&self) -> T;
    fn peek_left  (&self) -> T;
    fn is_empty    (&self) -> bool;
}

impl<T> IDeque<T> for Deque<T> {
    fn is_empty(&self) -> bool {
        match self {
            &Empty => true,
            _ => false
        }
    }

    fn enque_right(&self, e: T) -> @Deque<T> {
        match self {
            &Empty => @Single(e),
            &Single(v) => @Multi(@Deque1(v), @Empty, @Deque1(e)),

            &Multi(left, inner_deque, @Deque1(a))
            => @Multi(left, inner_deque, @Deque2(a, e)),

            &Multi(left, inner_deque, @Deque2(a, b))
            => @Multi(left, inner_deque, @Deque3(a, b, e)),

            &Multi(left, inner_deque, @Deque3(a, b, c))
            => @Multi(left, inner_deque, @Deque4(a, b, c, e)),

            // inner_deque.enque_right(...)  <--- polymorphic recursion
            &Multi(left, inner_deque, @Deque4(a, b, c, d))
            => @Multi(left, inner_deque.enque_right(Deque3(a, b, c)), @Deque2(d, e))
        }
    }

    fn enque_left (&self, e: T) -> @Deque<T> {
        match self {
            &Empty => @Single(e),
            &Single(v) => @Multi(@Deque1(e), @Empty, @Deque1(v)),

            &Multi(@Deque1(a), inner_deque, right)
            => @Multi(@Deque2(e, a), inner_deque, right),

            &Multi(@Deque2(a, b), inner_deque, right)
            => @Multi(@Deque3(e, a, b), inner_deque, right),

            &Multi(@Deque3(a, b, c), inner_deque, right)
            => @Multi(@Deque4(e, a, b, c), inner_deque, right),

            // inner_deque.enque_left(...)  <--- polymorphic recursion
            &Multi(@Deque4(a, b, c, d), inner_deque, right)
            => @Multi(@Deque2(e, a), inner_deque.enque_left(Deque3(b, c, d)), right)
        }
    }
    fn deque_right(&self) -> @Deque<T> {
        match self {
            &Empty => { fail!(~"empty deque") }
            &Single(_) => @Empty,

            &Multi(left, inner_deque, @Deque2(a, _))
            => @Multi(left, inner_deque, @Deque1(a)),

            &Multi(left, inner_deque, @Deque3(a, b, _))
            => { @Multi(left, inner_deque, @Deque2(a, b)) }

            &Multi(left, inner_deque, @Deque4(a, b, c, _))
            => @Multi(left, inner_deque, @Deque3(a, b, c)),

            &Multi(@Deque1(v), @Empty, @Deque1(_))
            => @Single(v),

            &Multi(@Deque2(a, b), @Empty, @Deque1(_))
            => @Multi(@Deque1(a), @Empty, @Deque1(b)),

            &Multi(@Deque3(a, b, c), @Empty, @Deque1(_))
            => { @Multi(@Deque2(a, b), @Empty, @Deque1(c)) },

            &Multi(@Deque4(a, b, c, d), @Empty, @Deque1(_))
            => @Multi(@Deque2(a, b), @Empty, @Deque2(c, d)),

            &Multi(left, inner_deque, @Deque1(_))
            => {
                let dequelette =  inner_deque.peek_right();
                @Multi(left, inner_deque.deque_right(), @dequelette) // <-- polymorphic recursion
            }
        }
    }
    fn deque_left (&self) -> @Deque<T> {
        match self {
            &Empty => fail!(~"empty deque"),
            &Single(_) => @Empty,

            &Multi(@Deque2(_, b), inner_deque, right)
            => @Multi(@Deque1(b), inner_deque, right),

            &Multi(@Deque3(_, b, c), inner_deque, right)
            => @Multi(@Deque2(b, c), inner_deque, right),

            &Multi(@Deque4(_, b, c, d), inner_deque, right)
            => @Multi(@Deque3(b, c, d), inner_deque, right),

            &Multi(@Deque1(_), @Empty, @Deque1(v))
            => @Single(v),

            &Multi(@Deque1(_), @Empty, @Deque2(a, b))
            => @Multi(@Deque1(a), @Empty, @Deque1(b)),

            &Multi(@Deque1(_), @Empty, @Deque3(a, b, c))
            => @Multi(@Deque1(a), @Empty, @Deque2(b, c)),

            &Multi(@Deque1(_), @Empty, @Deque4(a, b, c, d))
            => @Multi(@Deque2(a, b), @Empty, @Deque2(c, d)),

            &Multi(@Deque1(_), inner_deque, right)
            => {
                let dequelette = inner_deque.peek_left();
                @Multi(@dequelette, inner_deque.deque_left(), right) // <-- polymorphic recursion
            }
        }
    }

    fn peek_right (&self) -> T {
        match self {
            &Empty => fail!(~"empty deque"),
            &Single(v) => v,
            &Multi(_, _, right_dequelette) => match (right_dequelette) {
                @Deque1(v) => v,
                @Deque2(_, v) => v,
                @Deque3(_, _, v) => v,
                @Deque4(_, _, _, v) => v
            }
        }
    }

    fn peek_left  (&self) -> T {
        match self {
            &Empty => fail!(~"empty deque"),
            &Single(v) => v,
            &Multi(left_dequelette, _, _) => match (left_dequelette) {
                @Deque1(v) => v,
                @Deque2(v, _) => v,
                @Deque3(v, _, _) => v,
                @Deque4(v, _, _, _) => v
            }
        }
    }
}

fn main() {
    let mut q: @Deque<int> = @Empty;
    q = q.enque_right(0).enque_right(1).enque_right(2).enque_left(3);
    assert!(q.peek_left() == 3);
    q = q.deque_left();
    assert!(q.peek_left() == 0);
    q = q.deque_left();
    assert!(q.peek_left() == 1);
    q = q.deque_left();
    assert!(q.peek_left() == 2);
    q = q.deque_left();
    assert!(q.is_empty());
}

here is what i was doing

1. http://blogs.msdn.com/b/ericlippert/archive/2008/02/12/immutability-in-c-part-eleven-a-working-double-ended-queue.aspx
2. http://www.soi.city.ac.uk/~ross/papers/FingerTree.pdf
3. https://docs.google.com/file/d/0B9nStCiu3GXxdzhsMEgtdE54NW8/edit?usp=sharing

I think that the problem is that Rust does not support polymorphic recursion which is undecidable and requires the use of a semi-algorithm or programmer supplied type annotations according to this http://en.wikipedia.org/wiki/Polymorphic_recursion -> http://dl.acm.org/citation.cfm?doid=169701.169692

i found the info about this polymorphic recursion thing in the link 2 (FingerTree.pdf)

rustc should identify the problem and report an error rather than looping forever

One more question: is it feasible to support this kind of things in Rust ?

Thanks

[huonw]

There are several issues about this (or things similar to this):

• Better error message for polymorphic recursion #4287
• ICE on recursive type #4363
• rustc stack overflow when using polymorphically recursive type #7587

I'm going to close this as a dupe of #7587 specifically.

---

To answer your questions about support in Rust; this comment:

In many ways, Rust is like low-level Haskell. That's why this test doesn't work! Because we are operating at a low level, we don't have uniform representation and implicit boxing and so forth. Therefore, like C++, we monomorphize generic functions---this implies that we would require an infinite set of functions to deal with recursive functions like the one you wrote here (note that other cases of polymorphic recursion work just fine, so long as they don't generate an infinite stream of types). I am going to close this as "not a bug, working as designed".

(There's a variety of other discussion about this on those issues also.)

[NawfelBgh]

thank you huonw for the reply
but there is still the problem of infinite loop
A user friendly compiler should stop at some stage and report an error.

[huonw]

Most definitely; that requirement is covered by the issues that I linked. :) (In fact, #4287 is explicitly about this problem.)

[nikomatsakis]

Possibly a dup of #8613 but I'm not sure. Reopening for now.

[emberian]

@nikomatsakis surely this isn't a dup of itself?

[nikomatsakis]

@cmr indeed. Not sure which issue I was thinking of now :)

[NawfelBgh]

what about generating a (configurable) fixed number of implementations: for Deque<T>, .... Deque<Dequelette<...Dequelette<T>...>>

and failing at runtime if more depth is needed.
That makes sense in this example, since a deck of N elements requires (i guess) <= log4(N) different implementations. (example: log4(100000) = (ln 100000)÷ln4 ~= 9 )

[steveklabnik]

This does in fact seem to be a dup of #4287, at least, that's the only way this is going to be improved. So I'm giving it a close.