luajit randomness not repeatable

gistfile1.lua

#!/usr/bin/env luajit
-- -*- lua -*-

function equals(expected, actual)
   if type(expected) ~= type(actual) then return false end
   if type(expected) == 'table' then
      for k, v in pairs(expected) do
         if not equals(v, actual[k]) then return false end
      end
      for k, _ in pairs(actual) do
         if expected[k] == nil then return false end
      end
      return true
   else
      return expected == actual
   end
end

function is_array(x)
   if type(x) ~= 'table' then return false end
   if #x == 0 then return false end
   for k,v in pairs(x) do
      if type(k) ~= 'number' then return false end
      -- Restrict to unsigned 32-bit integer keys.
      if k < 0 or k >= 2^32 then return false end
      -- Array indices are integers.
      if k - math.floor(k) ~= 0 then return false end
      -- Negative zero is not a valid array index.
      if 1 / k < 0 then return false end
   end
   return true
end

function choose(choices)
   local idx = math.random(#choices)
   return choices[idx]
end

function pp(expr, indent, suffix)
   indent = indent or ''
   suffix = suffix or ''
   if type(expr) == 'number' then
      print(indent..expr..suffix)
   elseif type(expr) == 'string' then
      print(indent..'"'..expr..'"'..suffix)
   elseif type(expr) == 'boolean' then
      print(indent..(expr and 'true' or 'false')..suffix)
   elseif is_array(expr) then
      assert(#expr > 0)
      if #expr == 1 then
         if type(expr[1]) == 'table' then
            print(indent..'{')
            pp(expr[1], indent..'  ', ' }'..suffix)
         else
            print(indent..'{ "'..expr[1]..'" }'..suffix)
         end
      else
         if type(expr[1]) == 'table' then
            print(indent..'{')
            pp(expr[1], indent..'  ', ',')
         else
            print(indent..'{ "'..expr[1]..'",')
         end
         indent = indent..'  '
         for i=2,#expr-1 do pp(expr[i], indent, ',') end
         pp(expr[#expr], indent, ' }'..suffix)
      end
   elseif type(expr) == 'table' then
      error('unimplemented')
   else
      error("unsupported type "..type(expr))
   end
   return expr
end

local True, False, Fail, ComparisonOp, BinaryOp, UnaryOp, Number, Len
local Unary, Binary, Arithmetic, Comparison, Conditional
-- Logical intentionally is not local; it is used elsewhere

function True() return { 'true' } end
function False() return { 'false' } end
function Fail() return { 'fail' } end
function ComparisonOp() return choose({ '<', '>' }) end
function BinaryOp() return choose({ '+', '-', '/' }) end
function UnaryOp()
   return choose({ 'uint32', 'int32', 'ntohs', 'ntohl' })
end
-- Boundary numbers are often particularly interesting; test them often
function Number()
   if math.random() < 0.2
      then return math.random(-2^31, 2^32 - 1)
   else
      return choose({ 0, 1, -2^31, 2^32-1, 2^31-1 })
   end
end
function Len() return 'len' end
function Unary(db) return { UnaryOp(), Arithmetic(db) } end
function Binary(db)
   local op, lhs, rhs = BinaryOp(), Arithmetic(db), Arithmetic(db)
   if op == '/' then table.insert(db, { '!=', rhs, 0 }) end
   return { op, lhs, rhs }
end
function PacketAccess(db)
   local pkt_access_size = choose({1, 2, 4})
   local position = {'uint32', Arithmetic(db) }
   table.insert(db, {'>=', 'len', {'+', position, pkt_access_size}})
   return { '[]', position, pkt_access_size }
end
function Arithmetic(db)
   return choose({ Unary, Binary, Number, Len, PacketAccess })(db)
end
function Comparison()
   local asserts = {}
   local expr = { ComparisonOp(), Arithmetic(asserts), Arithmetic(asserts) }
   for i=#asserts,1,-1 do
      expr = { 'if', asserts[i], expr, { 'fail' } }
   end
   return expr
end
function Conditional() return { 'if', Logical(), Logical(), Logical() } end
function Logical()
   return choose({ Conditional, Comparison, True, False, Fail })()
end

local function generate(seed)
   math.randomseed(seed)
   return { Logical(), Logical(), Logical() }
end

function assert_equals(expected, actual)
   if not equals(expected, actual) then
      pp(expected)
      pp(actual)
      error('not equal')
   end
end

function main(...)
   local seed = ...
   seed = assert(tonumber(seed), 'usage: test.lua SEED')
   for i=1,10000 do
      assert_equals(generate(seed), generate(seed))
   end
end
main(...)

run as test.lua 693763393

example output:

wingo@rusty:~/src/pflua/tests$ PATH=../deps/luajit/usr/local/bin:$PATH ../test.lua 693763393
{
  { "if",
    { "if",
      { "if",
        { ">=",
          "len",
          { "+",
            { "uint32",
              "len" },
            4 } },
        { "<",
          { "-",
            { "-",
              { "int32",
                "len" },
              "len" },
            { "+",
              "len",
              { "int32",
                -2147483648 } } },
          { "[]",
            { "uint32",
              "len" },
            4 } },
        { "fail" } },
      { "true" },
      { "if",
        { ">=",
          "len",
          { "+",
            { "uint32",
              { "+",
                "len",
                221528420 } },
            1 } },
        { "<",
          { "ntohs",
            { "ntohl",
              { "[]",
                { "uint32",
                  { "+",
                    "len",
                    221528420 } },
                1 } } },
          { "-",
            "len",
            "len" } },
        { "fail" } } },
    { ">",
      { "-",
        { "-",
          "len",
          "len" },
        { "-",
          "len",
          0 } },
      { "ntohs",
        3239707403 } },
    { "fail" } },
  { "fail" },
  { "false" } }
{
  { "if",
    { "if",
      { "if",
        { ">=",
          "len",
          { "+",
            { "uint32",
              "len" },
            4 } },
        { "<",
          { "-",
            { "-",
              { "int32",
                "len" },
              "len" },
            { "+",
              "len",
              { "int32",
                -2147483648 } } },
          { "[]",
            { "uint32",
              "len" },
            4 } },
        { "fail" } },
      { "true" },
      { "if",
        { ">=",
          "len",
          { "+",
            { "uint32",
              { "+",
                "len",
                221528420 } },
            1 } },
        { "<",
          { "ntohs",
            { "ntohl",
              { "[]",
                { "uint32",
                  { "+",
                    "len",
                    221528420 } },
                1 } } },
          { "-",
            "len",
            "len" } },
        { "fail" } } },
    { ">",
      { "-",
        { "-",
          "len",
          "len" },
        { "-",
          "len",
          0 } },
      { "ntohs",
        3328978173 } },
    { "fail" } },
  { "false" },
  { "fail" } }
luajit: ../test.lua:134: not equal
stack traceback:
    [C]: in function 'error'
    ../test.lua:134: in function 'assert_equals'
    ../test.lua:143: in function 'main'
    ../test.lua:146: in main chunk
    [C]: at 0x00404340

shorter program:

#!/usr/bin/env luajit
-- -*- lua -*-

function equals(expected, actual)
   if type(expected) ~= type(actual) then return false end
   if type(expected) == 'table' then
      for k, v in pairs(expected) do
         if not equals(v, actual[k]) then return false end
      end
      for k, _ in pairs(actual) do
         if expected[k] == nil then return false end
      end
      return true
   else
      return expected == actual
   end
end

function pp(expr, indent, suffix)
   indent = indent or ''
   suffix = suffix or ''
   if type(expr) == 'number' then
      print(indent..expr..suffix)
   elseif type(expr) == 'table' then
      print(indent..'{ "'..expr[1]..'",')
      indent = indent..'  '
      for i=2,#expr-1 do pp(expr[i], indent, ',') end
      pp(expr[#expr], indent, ' }'..suffix)
   else
      error("unsupported type "..type(expr))
   end
   return expr
end

function assert_equals(expected, actual)
   if not equals(expected, actual) then
      pp(expected)
      pp(actual)
      error('not equal')
   end
end

function choose(choices)
   local idx = math.random(#choices)
   return choices[idx]
end

function Number()
   if math.random() < 0.2
      then return math.random(-2^31, 2^32 - 1)
   else
      return choose({ 0, 1, -2^31, 2^32-1, 2^31-1 })
   end
end
function Binary()
   return { '+', Arithmetic(), Arithmetic() }
end
function Arithmetic()
   return choose({ Binary, Number })()
end
function Comparison()
   return { '<', Arithmetic(), Arithmetic() }
end

function generate(seed)
   math.randomseed(seed)
   return Comparison()
end

function main(...)
   local seed = ...
   seed = assert(tonumber(seed), 'usage: test.lua SEED')
   for i=1,10000 do
      assert_equals(generate(seed), generate(seed))
   end
end
main(...)

FML it was fixed somewhere between 66515a054c0826cee4f0abc5e532f35b421e9c81 and 7f013005f61b82300d4ec591fd4cec59a74d62ff.

of luajit