Crystal: Compile-time stack overflow on module-abstracted instance var with generic struct impl and decorator for it

[ony]

Failing code suitable to be run in crystal eval:

abstract class AnySack(T)
  include Iterable(T)
end

class Sack(T) < AnySack(T)
  def initialize(@values : Iterable(T)); end
  def each; @values.each; end
end

class MapSack(T, U) < AnySack(T)  # <-- removing superclass fixes
  def initialize(@source : AnySack(U), &@block : U -> T); end
  def each; @source.each.map &@block end
end

s = Sack.new({1, 2})
s.each.to_a  # [1, 2] : Array(Int32)
MapSack(Bool, Int32).new(s) { |x| true }.each.to_a  # works fine
MapSack(Int32, Int32).new(s) { |x| 1 }.each.to_a  # Stack overflow (e.g., infinite or very deep recursion)

Note that it work when #each returns Iterator(Bool) but not when it returns same type @source.each returns.

So I expect that issue is caused by the fact that we implement #each from abstract class and use it inside of implementation. And looks like compiler do some extra checks.

Tested on:

Crystal 0.27.0 [c9d1eef8f] (2018-11-01)

LLVM: 4.0.0
Default target: x86_64-unknown-linux-gnu

[asterite]

I'm still not sure why it happens, but for this code:

class MapSack(T)
  include Iterable(T)

  def initialize(@source : Iterable(T))
  end

  def each
    @source.each.map { |x| x }
  end
end

s = {'a'}
MapSack.new(s).each

Iterator::Map(Indexable::ItemIterator(Tuple(Int32)))

showing generic instantiations by the compiler I see:

Indexable::ItemIterator(Tuple(Char), Char)
Iterator::Map(Indexable::ItemIterator(Tuple(Char), Char), Char, Char)
Iterator::Map(Iterator::Map(Indexable::ItemIterator(Tuple(Char), Char), Char, Char), Char, Char)
Iterator::Map(Iterator::Map(Iterator::Map(Indexable::ItemIterator(Tuple(Char), Char), Char, Char), Char, Char), Char, Char)
Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Indexable::ItemIterator(Tuple(Char), Char), Char, Char), Char, Char), Char, Char), Char, Char)
Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Indexable::ItemIterator(Tuple(Char), Char), Char, Char), Char, Char), Char, Char), Char, Char), Char, Char)
Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Indexable::ItemIterator(Tuple(Char), Char), Char, Char), Char, Char), Char, Char), Char, Char), Char, Char), Char, Char)
Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Indexable::ItemIterator(Tuple(Char), Char), Char, Char), Char, Char), Char, Char), Char, Char), Char, Char), Char, Char), Char, Char)
# and so on...

I think it happens because you have an Iterable that has an Iterable as an instance variable and then the type generation explodes somehow.

My advice: don't use Iterable (or Iterator, possibly any generic module) as an instance variable.

This will never be fixed, at most you will get a compile-time error (well, I think right now you get an error). This is because there are no real virtual types in the compiler, all possible instantiations are known and analyzed by the compiler and these kind of recursions can happen.

[ony]

I think it happens because you have an Iterable that has an Iterable as an instance variable and then the type generation explodes somehow.

My advice: don't use Iterable (or Iterator, possibly any generic module) as an instance variable.

@asterite, I'm not sure I understand you. Are you saying that I should avoid using Iterable and/or Iterator and create own implementations? Or you are saying that modules cannot be used as type restrictions for instance variable?

Note that even if I replace Iterable(T) with AnySack(T) it still have same issue.

This will never be fixed, at most you will get a compile-time error (well, I think right now you get an error). This is because there are no real virtual types in the compiler, all possible instantiations are known and analyzed by the compiler and these kind of recursions can happen.

That sounds scary. Sorry. I'm not good at Crystal yet to understand virtual types.

Could it be that culprit is:

# iterator.cr
  def map(&func : T -> U) forall U
    Map(typeof(self), T, U).new(self, func)
  end

  private struct Map(I, T, U)
    include Iterator(U)
    include IteratorWrapper

    def initialize(@iterator : I, @func : T -> U)
    end

    def next
      value = wrapped_next
      @func.call(value)
    end
  end

As you can see instead of abstracting underlying iterator behind Iterator(T) we actually kinda preserve its type and get those Iterator::Map(Iterator::Map(....)) stuff.

I suspect that is caused by the fact that we want to use struct and benefit from in-lining them in memory instead of having references. With that code we trigger path that generates infinite number of types. Without doing any induction reasoning instead of generating all the code paths it will be a popular issue, I guess.

An isolated example that trigger this issue:

module Generator(T)
  abstract def generate : T

  def map(&func : T -> U) : Generator(U) forall U
    Map(typeof(self), T, U).new(self, func)
  end

  def self.of(x : T) : Generator(T); Const.new(x) end

  private struct Const(T)
    include Generator(T)

    def initialize(@x : T); end
    def generate; @x end
  end

  private struct Map(G, T, U)
    include Generator(U)

    def initialize(@base : G, @func : T -> U); end
    def generate; @func.call(@base.generate) end
  end
end

class Trigger(T)
  def initialize(@base : Generator(T)); end
  def boom!; @base.map { |x| x } end
end

Trigger.new(Generator.of(42)).boom!

But I don't understand why next code doesn't trigger it:

def trigger(base : Generator(T)) : Generator(T) forall T
  base.map { |x| x }
end

trigger(Generator.of(42)).generate

Why method definition doesn't generate this? Why only if we store as instance variable?

[ony]

But I don't understand why next code doesn't trigger it:

def trigger(base : Generator(T)) : Generator(T) forall T
  base.map { |x| x }
end

trigger(Generator.of(42)).generate

Why method definition doesn't generate this? Why only if we store as instance variable?

I think I got it. I guess reason is behind the fact that #trigger gets implicit specialized implementations that handle any argument restricted to Generator(T). Thus it triggers only for used arguments.
Why class is different? I.e. it is not a struct and we can have implicit children of the class that handle specific instances:

abstract class Trigger(T)
  abstract def boom! : Generator(T)

  def self.make(base : Generator(T))
    Specialized(typeof(base), T).new(base)
  end

  private class Specialized(G, T) < Trigger(T)
    def initialize(@base : G); end  
    def boom!; @base.map { |x| x } end
  end
end

Trigger.make(Generator.of(42)).boom!.generate

Or maybe somehow box it:

abstract class Boxed(T)
  abstract def unbox : T

  def self.box(unboxed : U) : Boxed(T) forall U
    Specialized(typeof(unboxed), T).new(unboxed)
  end

  class Specialized(U, T) < Boxed(T)
    def initialize(@unboxed : U); end
    def unbox; @unboxed; end
  end
end

class Trigger(T)
  def initialize(base : Generator(T))
    @base = Boxed(Generator(T)).box(base)
  end
  def boom!; @base.unbox.map { |x| x } end
end

Trigger.new(Generator.of(42)).boom!.generate

[ony]

Even smaller isolated example:

module Nat
  def succ : Nat; Succ(typeof(self)).new end
  struct Succ(T); include Nat end
end

class Trigger
  def initialize(@nat : Nat); end
  def boom!; @nat.succ; end
end

z = Nat::Succ(Int32).new
z
z.succ
Trigger.new(z).boom!

[vlazar]

When I run original code there is no stack overflow. I see this error:

$ crystal test.cr
Showing last frame. Use --error-trace for full trace.

In /usr/local/Cellar/crystal/0.31.1/src/iterator.cr:693:5

 693 | Map(typeof(self), T, U).new(self, func)
       ^
Error: generic type too nested: Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Iterator::Map(Indexable::ItemIterator(Array(Int32), Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32), Int32, Int32)

Crystal 0.31.1 on MacOS

$ crystal --version
Crystal 0.31.1 (2019-10-02)

LLVM: 8.0.1
Default target: x86_64-apple-macosx

[asterite]

Thank you for finding out it doesn't segfault anymore!

However, the issue is not so much a segfault or a compile error, but rather having the code work in some way.