crystal
crystal copied to clipboard
crystal-lang
Hoist complex element expressions outside container literals
Fixes #7340. A "complex expression" is anything that isn't a Nop, NilLiteral, BoolLiteral, NumberLiteral, CharLiteral, StringLiteral, SymbolLiteral, Var, InstanceVar, or ClassVar. (This same criterion is used by the normalizer to determine whether the LHS of a compound assignment needs to be hoisted into a temporary variable.) As the examples below show, those complex expressions cannot appear inside the expanded typeof expressions.
The following:
class Array(T)
def self.unsafe_build(capacity); new; end
def to_unsafe; self; end
def []=(index, value); end
end
[[[nil]]]
produces with AFTER=1 crystal build --prelude=empty:
After
__temp_1 = (
__temp_4 = (
__temp_7 = ::Array(typeof(nil)).unsafe_build(1)
__temp_8 = __temp_7.to_unsafe
__temp_8[0] = nil
__temp_7
)
__temp_5 = ::Array(typeof(__temp_4)).unsafe_build(1)
__temp_6 = __temp_5.to_unsafe
__temp_6[0] = __temp_4
__temp_5
)
__temp_2 = ::Array(typeof(__temp_1)).unsafe_build(1)
__temp_3 = __temp_2.to_unsafe
__temp_3[0] = __temp_1
__temp_2
The following:
class Hash(K, V)
def []=(index, value); end
end
{ { {'a' => 'b'} => 'c'} => {'d' => {'e' => 'f'} } }
produces:
Before
__temp_1 = ::Hash(typeof(begin
__temp_2 = ::Hash(typeof(begin
__temp_3 = ::Hash(typeof('a'), typeof('b')).new
__temp_3['a'] = 'b'
__temp_3
end), typeof('c')).new
__temp_2[begin
__temp_4 = ::Hash(typeof('a'), typeof('b')).new
__temp_4['a'] = 'b'
__temp_4
] = 'c'
__temp_2
end, typeof(begin
__temp_5 = ::Hash(typeof('d'), typeof(begin
__temp_6 = ::Hash(typeof('e'), typeof('f')).new
__temp_6['e'] = 'f'
__temp_6
end)).new
__temp_5['d'] = begin
__temp_7 = ::Hash(typeof('e'), typeof('f')).new
__temp_7['e'] = 'f'
__temp_7
end
__temp_5
end)).new
__temp_1[begin
__temp_8 = ::Hash(typeof(begin
__temp_9 = ::Hash(typeof('a'), typeof('b')).new
__temp_9['a'] = 'b'
__temp_9
end), typeof('c')).new
__temp_8[begin
__temp_10 = ::Hash(typeof('a'), typeof('b')).new
__temp_10['a'] = 'b'
__temp_10
end] = 'c'
__temp_8
end] = begin
__temp_11 = ::Hash(typeof('d'), typeof(begin
__temp_12 = ::Hash(typeof('e'), typeof('f')).new
__temp_12['e'] = 'f'
__temp_12
end)).new
__temp_11['d'] = begin
__temp_13 = ::Hash(typeof('e'), typeof('f')).new
__temp_13['e'] = 'f'
__temp_13
end
__temp_11
end
__temp_1
After
__temp_1 = (
__temp_4 = (
__temp_6 = ::Hash(typeof('a'), typeof('b')).new
__temp_6['a'] = 'b'
__temp_6
)
__temp_5 = ::Hash(typeof(__temp_4), typeof('c')).new
__temp_5[__temp_4] = 'c'
__temp_5
)
__temp_2 = (
__temp_7 = (
__temp_9 = ::Hash(typeof('e'), typeof('f')).new
__temp_9['e'] = 'f'
__temp_9
)
__temp_8 = ::Hash(typeof('d'), typeof(__temp_7)).new
__temp_8['d'] = __temp_7
__temp_8
)
__temp_3 = ::Hash(typeof(__temp_1), typeof(__temp_2)).new
__temp_3[__temp_1] = __temp_2
__temp_3
Is this a relevant question for code using the Type{} shortcut (ie Set{1, 2, Deque{1,2}}) as well?
(I sincerely hope no-one writes code like that particular example)
Array-like and hash-like literals are also covered. Before:
__temp_1 = Set(T)(typeof(1, 2, begin
__temp_2 = Deque(T)(typeof(1, 2)).new
__temp_2 << 1
__temp_2 << 2
__temp_2
end)).new
__temp_1 << 1
__temp_1 << 2
__temp_1 << (
__temp_3 = Deque(T)(typeof(1, 2)).new
__temp_3 << 1
__temp_3 << 2
__temp_3
)
__temp_1
After:
__temp_1 = (
__temp_3 = Deque(T)(typeof(1, 2)).new
__temp_3 << 1
__temp_3 << 2
__temp_3
)
__temp_2 = Set(T)(typeof(1, 2, __temp_1)).new
__temp_2 << 1
__temp_2 << 2
__temp_2 << __temp_1
__temp_2
A more realistic example, this nested container in the standard library specs:
https://github.com/crystal-lang/crystal/blob/5de237e052004bca0e5a43e903139558f5368a2a/spec/std/crypto/subtle_spec.cr#L6-L11
Before
__temp_1 = ::Array(typeof(begin
__temp_3 = ::Hash(typeof("a", "b", "result"), typeof(Slice.new(1, 17), Slice.new(1, 17), true)).new
__temp_3["a"] = Slice.new(1, 17)
__temp_3["b"] = Slice.new(1, 17)
__temp_3["result"] = true
__temp_3
end, begin
__temp_6 = ::Hash(typeof("a", "b", "result"), typeof(Slice.new(1, 18), Slice.new(1, 17), false)).new
__temp_6["a"] = Slice.new(1, 18)
__temp_6["b"] = Slice.new(1, 17)
__temp_6["result"] = false
__temp_6
end, begin
__temp_7 = ::Hash(typeof("a", "b", "result"), typeof(Slice.new(1, 17), Slice.new(2) do |i|
17 + i
end, false)).new
__temp_7["a"] = Slice.new(1, 17)
__temp_7["b"] = Slice.new(2) do |i|
17 + i
end
__temp_7["result"] = false
__temp_7
end, begin
__temp_10 = ::Hash(typeof("a", "b", "result"), typeof(Slice.new(2) do |i|
17 + i
end, Slice.new(1, 17), false)).new
__temp_10["a"] = Slice.new(2) do |i|
17 + i
end
__temp_10["b"] = Slice.new(1, 17)
__temp_10["result"] = false
__temp_10
end)).unsafe_build(4)
__temp_2 = __temp_1.to_unsafe
__temp_2[0] = begin
__temp_13 = ::Hash(typeof("a", "b", "result"), typeof(Slice.new(1, 17), Slice.new(1, 17), true)).new
__temp_13["a"] = Slice.new(1, 17)
__temp_13["b"] = Slice.new(1, 17)
__temp_13["result"] = true
__temp_13
end
__temp_2[1] = begin
__temp_14 = ::Hash(typeof("a", "b", "result"), typeof(Slice.new(1, 18), Slice.new(1, 17), false)).new
__temp_14["a"] = Slice.new(1, 18)
__temp_14["b"] = Slice.new(1, 17)
__temp_14["result"] = false
__temp_14
end
__temp_2[2] = begin
__temp_15 = ::Hash(typeof("a", "b", "result"), typeof(Slice.new(1, 17), Slice.new(2) do |i|
17 + i
end, false)).new
__temp_15["a"] = Slice.new(1, 17)
__temp_15["b"] = Slice.new(2) do |i|
17 + i
end
__temp_15["result"] = false
__temp_15
end
__temp_2[3] = begin
__temp_18 = ::Hash(typeof("a", "b", "result"), typeof(Slice.new(2) do |i|
17 + i
end, Slice.new(1, 17), false)).new
__temp_18["a"] = Slice.new(2) do |i|
17 + i
end
__temp_18["b"] = Slice.new(1, 17)
__temp_18["result"] = false
__temp_18
end
__temp_1
After
__temp_1 = (
__temp_7 = Slice.new(1, 17)
__temp_8 = Slice.new(1, 17)
__temp_9 = ::Hash(typeof("a", "b", "result"), typeof(__temp_7, __temp_8, true)).new
__temp_9["a"] = __temp_7
__temp_9["b"] = __temp_8
__temp_9["result"] = true
__temp_9
)
__temp_2 = (
__temp_12 = Slice.new(1, 18)
__temp_13 = Slice.new(1, 17)
__temp_14 = ::Hash(typeof("a", "b", "result"), typeof(__temp_12, __temp_13, false)).new
__temp_14["a"] = __temp_12
__temp_14["b"] = __temp_13
__temp_14["result"] = false
__temp_14
)
__temp_3 = (
__temp_15 = Slice.new(1, 17)
__temp_16 = Slice.new(2) do |i|
17 + i
end
__temp_17 = ::Hash(typeof("a", "b", "result"), typeof(__temp_15, __temp_16, false)).new
__temp_17["a"] = __temp_15
__temp_17["b"] = __temp_16
__temp_17["result"] = false
__temp_17
)
__temp_4 = (
__temp_19 = Slice.new(2) do |i|
17 + i
end
__temp_20 = Slice.new(1, 17)
__temp_21 = ::Hash(typeof("a", "b", "result"), typeof(__temp_19, __temp_20, false)).new
__temp_21["a"] = __temp_19
__temp_21["b"] = __temp_20
__temp_21["result"] = false
__temp_21
)
__temp_5 = ::Array(typeof(__temp_1, __temp_2, __temp_3, __temp_4)).unsafe_build(4)
__temp_6 = __temp_5.to_unsafe
__temp_6[0] = __temp_1
__temp_6[1] = __temp_2
__temp_6[2] = __temp_3
__temp_6[3] = __temp_4
__temp_5
I sincerely hope no-one writes code like that particular example
No matter what language feature we are talking about, in my experience hoping that someone won't do this or that is always in vain 😄
This is really cool!
One optimization I always wanted to do, but didn't think it's worth it (but it probably is!) is trying to not use typeof when we know the type of all elements. For example, if we have [1, 2] we can just do Array(Int32). Same if we have [1, nil], we can do Array(Int32 | Nil). And even in something like [[1,2]], we can do Array(Array(Int32)) and avoid using typeof.
But that can come as a follow-up PR.
Some expansions are actually longer when they don't involve typeof expressions, i.e. when the container literals use of and the container-like literals don't use uninstantiated generics. Take this example from the parser specs:
[(ArrayLiteral.new([(ArrayLiteral.new([1.int32] of ASTNode)).splat] of ASTNode)).splat, (ArrayLiteral.new([2.int32] of ASTNode)).splat] of ASTNode
Before:
__temp_1 = ::Array(ASTNode).unsafe_build(2)
__temp_2 = __temp_1.to_unsafe
__temp_2[0] = (ArrayLiteral.new(begin
__temp_3 = ::Array(ASTNode).unsafe_build(1)
__temp_4 = __temp_3.to_unsafe
__temp_4[0] = (ArrayLiteral.new(begin
__temp_5 = ::Array(ASTNode).unsafe_build(1)
__temp_6 = __temp_5.to_unsafe
__temp_6[0] = 1.int32
__temp_5
end)).splat
__temp_3
end)).splat
__temp_2[1] = (ArrayLiteral.new(begin
__temp_8 = ::Array(ASTNode).unsafe_build(1)
__temp_9 = __temp_8.to_unsafe
__temp_9[0] = 2.int32
__temp_8
end)).splat
__temp_1
After:
__temp_1 = (ArrayLiteral.new(begin
__temp_5 = (ArrayLiteral.new(begin
__temp_8 = 1.int32
__temp_9 = ::Array(ASTNode).unsafe_build(1)
__temp_10 = __temp_9.to_unsafe
__temp_10[0] = __temp_8
__temp_9
end)).splat
__temp_6 = ::Array(ASTNode).unsafe_build(1)
__temp_7 = __temp_6.to_unsafe
__temp_7[0] = __temp_5
__temp_6
end)).splat
__temp_2 = (ArrayLiteral.new(begin
__temp_12 = 2.int32
__temp_13 = ::Array(ASTNode).unsafe_build(1)
__temp_14 = __temp_13.to_unsafe
__temp_14[0] = __temp_12
__temp_13
end)).splat
__temp_3 = ::Array(ASTNode).unsafe_build(2)
__temp_4 = __temp_3.to_unsafe
__temp_4[0] = __temp_1
__temp_4[1] = __temp_2
__temp_3
One can spot that after this PR the 3 calls to #int32 and the 2 calls to #splat are hoisted, which are where the extra temporary variables come from. However I still think we should do this and not selectively apply the optimization to the other kinds of container literals, because this ensures a consistent execution order across all those containers.