Miscompile on Object that produces an Iterator

[z64]

Take the following program:

require "crinja"

struct StructWithIterator
  include Crinja::Object

  # removing this `include` fixes
  include ::Iterable(Crinja::Value)

  @iter : -> ::Iterator(Crinja::Value)

  def initialize
    @iter = "invalid code to show it isn't being instanced directly?"
  end

  def each : ::Iterator(Crinja::Value)
    # replacing the below line fixes:
    # Array(Crinja::Value).new.each
    @iter.call
  end

  # to satisfy Value#raw_each
  def each(& : Crinja::Value ->)
    yield Crinja.value(1)
  end

  # to satisfy Value#first
  def first
    1
  end
end

template = Crinja::Template.new(<<-JINJA)
{% for k, v in table %}
{% endfor %}
JINJA

table = {0 => 0} # must be a hash?
template.render({table: table})

Take note that StructWithIter is NOT used directly within any of this code.

If you compile this program once, and run it multiple times, it will have one of two outputs:

Exception 1

``` Unhandled exception: Missing value for unpack template: :1:1 .. 2:13 1 | {% for k, v in table %} X | ^ 2 | {% endfor %} (Crinja::RuntimeError) from lib/crinja/src/runtime/context.cr:133:25 in 'unpack' from lib/crinja/src/lib/tag/for.cr:83:13 in 'run_loop' from lib/crinja/src/lib/tag/for.cr:35:5 in 'interpret_output' from lib/crinja/src/runtime/renderer.cr:90:5 in 'render' from lib/crinja/src/runtime/renderer.cr:70:19 in 'render' from lib/crinja/src/runtime/renderer.cr:64:5 in 'render' from lib/crinja/src/runtime/renderer.cr:50:14 in 'render' from lib/crinja/src/template.cr:69:5 in 'render' from lib/crinja/src/template.cr:61:7 in 'render' from lib/crinja/src/template.cr:54:7 in 'render' from _example.cr:38:1 in '__crystal_main' from /usr/lib/crystal/crystal/main.cr:129:5 in 'main_user_code' from /usr/lib/crystal/crystal/main.cr:115:7 in 'main' from /usr/lib/crystal/crystal/main.cr:141:3 in 'main' from /usr/lib/libc.so.6 in '??' from /usr/lib/libc.so.6 in '__libc_start_main' from /home/lune/.cache/crystal/crystal-run-_example.tmp in '_start' from ??? ```

Exception 2

``` Unhandled exception: Index out of bounds (IndexError) from /usr/lib/crystal/indexable.cr:89:20 in '[]' from /usr/lib/crystal/indexable.cr:1324:17 in 'next' from lib/crinja/src/runtime/value.cr:274:15 in 'next' from lib/crinja/src/runtime/value.cr:302:15 in 'next' from lib/crinja/src/runtime/context.cr:131:19 in 'unpack' from lib/crinja/src/lib/tag/for.cr:83:13 in 'run_loop' from lib/crinja/src/lib/tag/for.cr:35:5 in 'interpret_output' from lib/crinja/src/runtime/renderer.cr:90:5 in 'render' from lib/crinja/src/runtime/renderer.cr:70:19 in 'render' from lib/crinja/src/runtime/renderer.cr:64:5 in 'render' from lib/crinja/src/runtime/renderer.cr:50:14 in 'render' from lib/crinja/src/template.cr:69:5 in 'render' from lib/crinja/src/template.cr:61:7 in 'render' from lib/crinja/src/template.cr:54:7 in 'render' from _example.cr:38:1 in '__crystal_main' from /usr/lib/crystal/crystal/main.cr:129:5 in 'main_user_code' from /usr/lib/crystal/crystal/main.cr:115:7 in 'main' from /usr/lib/crystal/crystal/main.cr:141:3 in 'main' from /usr/lib/libc.so.6 in '??' from /usr/lib/libc.so.6 in '__libc_start_main' from /home/lune/.cache/crystal/crystal-run-_example.tmp in '_start' from ??? ```

If you compile it in release mode, it segfaults due to some kind of stack corruption:

Segfault example

``` Invalid memory access (signal 11) at address 0xa [0x557acb3d6d29] ?? +93985884171561 in /home/lune/.cache/crystal/crystal-run-_example.tmp [0x557acb3d6cf8] ?? +93985884171512 in /home/lune/.cache/crystal/crystal-run-_example.tmp [0x7f5dee740710] ?? +140041409267472 in /usr/lib/libc.so.6 [0x557acb3f9b3c] ?? +93985884314428 in /home/lune/.cache/crystal/crystal-run-_example.tmp [0x557acb3f9925] ?? +93985884313893 in /home/lune/.cache/crystal/crystal-run-_example.tmp [0x557acb3f9c55] ?? +93985884314709 in /home/lune/.cache/crystal/crystal-run-_example.tmp [0x557acb40e062] ?? +93985884397666 in /home/lune/.cache/crystal/crystal-run-_example.tmp [0x557acb40a50c] ?? +93985884382476 in /home/lune/.cache/crystal/crystal-run-_example.tmp [0x557acb440040] ?? +93985884602432 in /home/lune/.cache/crystal/crystal-run-_example.tmp [0x557acb37eeb8] __crystal_main +34424 in /home/lune/.cache/crystal/crystal-run-_example.tmp [0x557acb3840f0] main +64 in /home/lune/.cache/crystal/crystal-run-_example.tmp [0x7f5dee729cd0] ?? +140041409174736 in /usr/lib/libc.so.6 [0x7f5dee729d8a] __libc_start_main +138 in /usr/lib/libc.so.6 [0x557acb376765] _start +37 in /home/lune/.cache/crystal/crystal-run-_example.tmp [0x0] ??? ```

---

I think this is clearly some kind of upstream compiler issue, but I'm opening here first to see if we can't workshop a more minimal repro that doesn't depend on Crinja, or maybe you can identify an existing upstream issue. If you would prefer me to open on the main Crystal repo, I can move it there.

The behavior is also slightly different if you pass table = [1, 2, 3] for example; it will 50/50 between outputting nothing and index OOB, where a hash will throw 100% of the time (with 2 different errors).

[straight-shoota]

Crinja does some unique things that seem to poke the compiler in ways that nobody has done before. I used to discover a couple of such bugs while building it.

I agree this is pretty likely a compiler bug The code looks fine and should be expected to work. I don't recall any specific upstream issue, but I think there have been a couple in the past that might be similar. Maybe @hertzdevil has some idea?

[HertzDevil]

First reduction:

iter = Crinja.value({1}).each
iter.class # => Crinja::Value::Iterator(
           #      Crinja::Value::HashTupleIterator |
           #      Crinja::Value::RawIterator |
           #      Indexable::ItemIterator(Array(Nil), Nil) |
           #      Iterator(Crinja::Value) |
           #      Iterator::MapIterator(String::CharIterator, Char, String))
iter.next  # => #<Iterator::Stop:0x7fef158d1fe0>

The expected output is:

iter.class # => Crinja::Value::Iterator(
           #      Crinja::Function::Cycler |
           #      Crinja::Value::HashTupleIterator |
           #      Crinja::Value::RawIterator |
           #      Indexable::ItemIterator(Array(Crinja::Value), Crinja::Value) |
           #      Indexable::ItemIterator(Array(Nil), Nil) |
           #      Indexable::ItemIterator(Crinja::Tuple, Crinja::Value) |
           #      Iterator::MapIterator(String::CharIterator, Char, String))
iter.next  # => Crinja::Value<1>

This might be related to crystal-lang/crystal#7044 or crystal-lang/crystal#10967. You might be better off turning ::Iterator(Crinja::Value) into a generic parameter:

struct StructWithIterator(T)
  include Crinja::Object

  include ::Iterable(Crinja::Value)

  @iter : -> T

  def initialize(@iter : -> T)
    {% raise "..." unless T <= ::Iterator(::Crinja::Value) %}
  end
end

StructWithIterator.new(-> { Array(Crinja::Value).new.each })
Crinja.value({1}).each.next # => Crinja::Value<1>

---

Second reduction:

class Crinja
  module Object
  end

  alias Raw = Int32 | Crinja::Object | Array(Value)

  struct Value
    getter raw : Raw

    def initialize(@raw : Raw)
    end

    def raw_each
      case object = @raw
      when Iterable(Value)
        RawIterator.new(object.each)
      else
        raise RuntimeError.new("#{object.class} is not iterable")
      end
    end

    class RawIterator
      include Iterator(Raw)

      def initialize(@iterator : Iterator(Value))
      end

      def next
        case value = @iterator.next
        when Value
          value.raw
        else
          stop
        end
      end
    end
  end

  class Tuple
    include Indexable(Value)
    include Object

    def unsafe_fetch(index : Int)
      Crinja::Value.new(1)
    end

    def size
      1
    end
  end
end

struct StructWithIterator
  include Crinja::Object

  {% unless flag?(:good1) %}
    include ::Iterable(Crinja::Value)
  {% end %}

  @iter = uninitialized -> Iterator(Crinja::Value)

  def each
    {% if flag?(:good2) %}
      Array(Crinja::Value).new.each
    {% else %}
      @iter.call
    {% end %}
  end
end

values = Crinja::Value.new(Crinja::Tuple.new)
iter = values.raw_each
iter      # => #<Crinja::Value::RawIterator:0x7f2dba3e4e60 @iterator= ...>
iter.next # => Invalid memory access (signal 11) at address 0x0

Expected result: (run with -Dgood1 or -Dgood2)

iter      # => #<Crinja::Value::RawIterator:0x7fc3d3247e60 @iterator=#<Indexable::ItemIterator(Crinja::Tuple, Crinja::Value):0x7fc3d3247e80 @array=#<Crinja::Tuple:0x7fc3d3248e70>, @index=0>>
iter.next # => 1

[HertzDevil]

Alternatively, it seems this could also be fixed on Crinja's end by:

diff --git a/src/runtime/value.cr b/src/runtime/value.cr
index 27902d9a..6f9c63aa 100644
--- a/src/runtime/value.cr
+++ b/src/runtime/value.cr
@@ -260,11 +260,11 @@ struct Crinja::Value
   end

   # :nodoc:
-  class RawIterator
+  class RawIterator(T)
     include ::Iterator(Raw)
     include IteratorWrapper

-    def initialize(@iterator : ::Iterator(Value))
+    def initialize(@iterator : T)
     end

     def next

Then Crinja.value({1}).each.class becomes:

Crinja::Value::Iterator(
  Crinja::Value::HashTupleIterator |
  Crinja::Value::RawIterator(
    Crinja::Function::Cycler |
    Iterator(Crinja::Value)
  ) |
  Crinja::Value::RawIterator(
    Indexable::ItemIterator(Crinja::Tuple, Crinja::Value) |
    Iterator(Crinja::Value)
  ) |
  Indexable::ItemIterator(Array(Nil), Nil) |
  Iterator(Crinja::Value) |
  Iterator::MapIterator(String::CharIterator, Char, String)
)

[straight-shoota]

I suppose making RawIterator generic might be benefitial any way as it trims down the number of types to the one that is actually used, simplifing method dispatch.