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

[Maurizio Cimadamore]

Fixed. Thanks for the report.

Maurizio

On 26/05/13 19:58, Samir Talwar wrote:
> 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.