Created
January 29, 2015 09:17
-
-
Save wingo/d1800650a72e1062c3ee to your computer and use it in GitHub Desktop.
luajit randomness not repeatable
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/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(...) |
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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
example output: