Fix NEWTABLE instruction allocating incorrect array size

[Shiranuit]

What does this PR do ?

The NEWTABLE instruction had an issue where it was allocating the wrong amount of size for the array and nodes. The issue was parser was encoding array length and hash length using a floating point byte and the NEWTABLE instruction only reading the value as a byte without decoding it.

This caused some unexpected behaviour in some cases like the one bellow where Lua is stuck in the for loop because of next not behaving correctly.

local val = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,[24]={}}
for k, v in pairs(val) do
    print(k) -- This prints all the values from 1 to 18 then it loop indefinitely on the 24th element inside the nodes part
end

What happens is

• There are 18 values in the array and 1 node
• The parser encodes the 18 into 17 using the floating point byte notation
• Then the NEWTABLE instruction reads it a 17 instead of decoding it as 18
• Which causes the allocation to be one slot smaller than it should be
• Then follow a SETLIST instruction that presizes the array to 18 normally nothing would happens here because 18 would be equal to the length of the array that would have been 18 and so no resize would happen, but since only 17 slots have been allocated, the presize is going to allocate the next power of 2 from 18 which is 32.
• The array has now a size of 32 but only contains 18 elements which means that there are 14 elements that are nil after the 18th. normally this is impossible since no value can be nil in the array part of a table except when the table is static in the code, but even in this case there is no nil value that can be put after the last non nil element, but because of this allocating error the table contract is not respected.
• This caused rawget to return nil when asking for the 24th element because (1 <= 24 <= 32) so it searches directly in the array part
• This also caused the next to return the wrong value
  • next(24) calls findIndex(24)
  • findIndex early exit if the index is (1 <= index <= array.length) and returns index (24)
  • next(24) then doesn't find a value not nil in the array part with the given index (24)
  • Then continues searching in the nodes part
  • Find the key 24 and returns (key, value) -> (24, \<value>)
  • since the returned key is also 24 and the 24th value is still nil in the array this creates an endless loop

[SquidDev]

Oh wow, this is an amazing PR. Thank you so much investigating, fixing, and then writing things up!

One thing which concerns here is that the table having the wrong size shouldn't cause the subsequent SETLIST instruction to fail. I think we should probably also change presize to use the underlying resize function (which is what PUC Lua does). I think this patch looks reasonable:

--- a/src/main/java/org/squiddev/cobalt/LuaTable.java
+++ b/src/main/java/org/squiddev/cobalt/LuaTable.java
@@ -186,7 +186,7 @@ public final class LuaTable extends LuaValue {
         */
        public void presize(int nArray) {
                if (nArray > array.length) {
-                       array = setArrayVector(array, 1 << log2(nArray), false, weakValues);
+                       resize(getHashLength(), 1 << log2(nArray), false);
                }
        }

[Shiranuit]

@SquidDev

One thing which concerns here is that the table having the wrong size shouldn't cause the subsequent SETLIST instruction to fail. I think we should probably also change presize to use the underlying resize function (which is what PUC Lua does). I think this patch looks reasonable:

--- a/src/main/java/org/squiddev/cobalt/LuaTable.java
+++ b/src/main/java/org/squiddev/cobalt/LuaTable.java
@@ -186,7 +186,7 @@ public final class LuaTable extends LuaValue {
         */
        public void presize(int nArray) {
                if (nArray > array.length) {
-                       array = setArrayVector(array, 1 << log2(nArray), false, weakValues);
+                       resize(getHashLength(), 1 << log2(nArray), false);
                }
        }

Yes, I agree it would be better to use resize instead of presize, it will lead to much less errors with the allocations.

Unfortunately in the case described earlier it wouldn't have made a difference, since SETLIST did not fail but assumed that it had to realloc the array since the size given by NEWTABLE was smaller than the size SETLIST obtained, which had the effect to override the size that the parser wanted to allocate specifically for the array because the array is static (until an insertion/deletion occurs).

[SquidDev]

Sorry, by fail I meant "produce a malformed table", not error or anything!

I think we should probably apply both patches, as both NEWLIST and presize are broken in different ways :D.