Crystal: Invalid memory access when accessing Hash containing cyclical structure

[bjeanes]

(at least, I think that's what's happening)

• Code: https://play.crystal-lang.org/#/r/10t8 (playground also exhibiting the exception)
• Version: 0.17.4 (2016-05-26)

As soon as the Hash is used to get or set a key, the bad memory access occurs. If the foos collection is an Array it's fine. If the Hash value type is Set, the issue also occurs.

I'm not sure if the behaviour occurs if I were using structs or classes instead of tuples, because I was getting SIGILL with structs earlier in the day, which I couldn't reduce to a small example.

[asterite]

Ah, yes, I imagined it had to do with recursive structs.

Note that there's no compiler bug here, it's just a stack overflow at runtime. You can tell this because if you do crystal build foo.cr it works, but then you do ./foo and get the error.

I'll copy the code:

alias A = NamedTuple(bs: Array(B))
alias B = NamedTuple(a: A)

a = {bs: [] of B}
b = {a: a}

foos = {} of B => Array(B)

# Comment out either of these lines to avoid invalid memory access
a[:bs] << b
foos[b]?

So, to compute foos[b]? we need to compute the hash of b. To compute the hash of b we need to compute the hash of a. To compute the hash of a we need to compute the hash of [] of B, which now has b, so we need to compute the hash of b, and so on... There's no way to correctly implement this because b is a struct so it's passed by value, there's no way to remember that we already visited b because there's no object_id for structs.

Next question is: why do you need something like this?

[bjeanes]

it's just a stack overflow at runtime.

Ah, of course.... that makes total sense. Is there any way for this to announce itself as a stack overflow instead of invalid memory access? I had sort of assumed a stack overflow here due to the huge stack trace generated, but still...

FWIW, I think Ruby wouldn't have a probable with this kind of recursive hashing setup:

irb(main):001:0> x = {}
=> {}
irb(main):002:0> y = {x: x}
=> {:x=>{}}
irb(main):003:0> x[:y] = y
=> {:x=>{:y=>{...}}}
irb(main):004:0> z = {}
=> {}
irb(main):005:0> z[x] = true
=> true
irb(main):006:0> z
=> {{:y=>{:x=>{...}}}=>true}

I'm not sure what Ruby is doing differently with Hash#hash calculation, though.

Next question is: why do you need something like this?

I don't. In fact, putting something whose hash changes as a key in a Hash is an awful idea. I just opened the issue since I ran into it and it wasn't immediately obvious why. Your explanation totally clarifies it though.

I thought I could get away with it because structs are immutable, but I have a mutable value in one of its fields so I'm going to run into other surprising situations like this.

Nonetheless, the "why" is because I was somewhat creating a graph to model dependency relationships between database columns. I'll find another way though :)

[asterite]

I think in Ruby hash is probably computed with a recursion check. It can be done in Crystal for reference types, but for value types like a struct it's impossible. So Ruby will never haver this problem, but it's something that I don't know if it can be solved in Crystal.

[asterite]

A stack overflow will eventually be reported as such, see #271