Bug in b88: Stack Overflow when changing a Supplier to a lambda using LazySeq

[Samir Talwar]

The attachments were stripped, so here they are inline. (Thanks to
Brian for pointing that out.)

Crashing with a stack overflow:

// START

import com.blogspot.nurkiewicz.lazyseq.LazySeq;

class MergeSortCrashing {
    public static <T extends Comparable<T>> LazySeq<T>
mergeSorted(LazySeq<T> a, LazySeq<T> b) {
        if (a.isEmpty()) {
            return b;
        }

        if (b.isEmpty()) {
            return a;
        }

        if (a.head().compareTo(b.head()) <= 0) {
            return LazySeq.cons(a.head(), () -> mergeSorted(a.tail(), b));
        } else {
            return LazySeq.cons(b.head(), () -> mergeSorted(a, b.tail()));
        }
    }
}

// END

Compiles fine without lambdas:

// START

import java.util.function.Supplier;
import com.blogspot.nurkiewicz.lazyseq.LazySeq;

class MergeSortWithoutLambdas {
    public static <T extends Comparable<T>> LazySeq<T>
mergeSorted(LazySeq<T> a, LazySeq<T> b) {
        if (a.isEmpty()) {
            return b;
        }

        if (b.isEmpty()) {
            return a;
        }

        if (a.head().compareTo(b.head()) <= 0) {
            return LazySeq.cons(a.head(), new Supplier<LazySeq<T>>() {
                @Override public LazySeq<T> get() {
                    return mergeSorted(a.tail(), b);
                }
            });
        } else {
            return LazySeq.cons(a.head(), new Supplier<LazySeq<T>>() {
                @Override public LazySeq<T> get() {
                    return mergeSorted(a, b.tail());
                }
            });
        }
    }
}

// END

Compiles fine with an explicit comparator instead and the <T extends
Comparable<T>> business changed to <T>:

(If you change the type parameter back to <T extends Comparable<T>>,
it crashes, even with this version.)

// START

import java.util.Comparator;
import com.blogspot.nurkiewicz.lazyseq.LazySeq;

class MergeSortSafe {
    public static <T> LazySeq<T> mergeSorted(LazySeq<T> a, LazySeq<T>
b, Comparator<T> comparator) {
        if (a.isEmpty()) {
            return b;
        }

        if (b.isEmpty()) {
            return a;
        }

        if (comparator.compare(a.head(), b.head()) <= 0) {
            return LazySeq.cons(a.head(), () -> mergeSorted(a.tail(),
b, comparator));
        } else {
            return LazySeq.cons(b.head(), () -> mergeSorted(a,
b.tail(), comparator));
        }
    }
}

// END

— Samir.

On Sun, May 26, 2013 at 6:29 PM, Samir Talwar <samir at noodlesandwich.com> wrote:
> I wrote some code using the LazySeq library (
> https://github.com/nurkiewicz/LazySeq ) which implements merge sort
> given two already-sorted lists. It crashes with a stack overflow.
>
> That works well. If I try and use lambdas, javac crashes with a stack overflow.
>
> Lambdas code (MergeSortCrashing.java):
>
>     public static <T extends Comparable<T>> LazySeq<T>
> mergeSorted(LazySeq<T> a, LazySeq<T> b) {
>         if (a.isEmpty()) {
>             return b;
>         }
>
>         if (b.isEmpty()) {
>             return a;
>         }
>
>         if (a.head().compareTo(b.head()) <= 0) {
>             return LazySeq.cons(a.head(), () -> mergeSorted(a.tail(), b));
>         } else {
>             return LazySeq.cons(b.head(), () -> mergeSorted(a, b.tail()));
>         }
>     }
>
> This is attempting to build against b88. Crashes in both IntelliJ and Maven.
>
> Two things: if an explicit comparator is passed in rather than having
> T be Comparable, it works. (See attachment: MergeSortSafe.java). It
> also works if I replace the lambdas with explicit instantiations of
> Supplier<LazySeq<T>> (see MergeSortWithoutLambdas.java).
>
> I'm pretty sure this is a bug. I hope this is the right place to
> report it. Cheers for all your hard work, guys. I hope this one gets
> fixed soon.
>
> — Samir.