From ca64b965344a7d4039d3c9745e593aacd5281504 Mon Sep 17 00:00:00 2001 From: Waqas Hussain Date: Sun, 5 May 2013 15:02:33 -0400 Subject: util.json: Optimize long string parsing. --- util/json.lua | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) (limited to 'util') diff --git a/util/json.lua b/util/json.lua index 9c2dd2c6..6251af1a 100644 --- a/util/json.lua +++ b/util/json.lua @@ -258,16 +258,16 @@ function json.decode(json) return val; end local function readstring() - local s = ""; + local s = {}; checkandskip("\""); while ch do while ch and ch ~= "\\" and ch ~= "\"" do - s = s..ch; next(); + t_insert(s, ch); next(); end if ch == "\\" then next(); if unescapes[ch] then - s = s..unescapes[ch]; + t_insert(s, unescapes[ch]); next(); elseif ch == "u" then local seq = ""; @@ -277,13 +277,13 @@ function json.decode(json) if not ch:match("[0-9a-fA-F]") then error("invalid unicode escape sequence in string"); end seq = seq..ch; end - s = s..codepoint_to_utf8(tonumber(seq, 16)); + t_insert(s, codepoint_to_utf8(tonumber(seq, 16))); next(); else error("invalid escape sequence in string"); end end if ch == "\"" then next(); - return s; + return t_concat(s); end end error("eof while reading string"); -- cgit v1.2.3 From 5d0847b19a2e0449cdcf88a726ae0dd98a6676fd Mon Sep 17 00:00:00 2001 From: Waqas Hussain Date: Mon, 6 May 2013 19:42:54 -0400 Subject: util.json: Fix variable name typo which broke util.json when util.array was missing. --- util/json.lua | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'util') diff --git a/util/json.lua b/util/json.lua index 6251af1a..67276765 100644 --- a/util/json.lua +++ b/util/json.lua @@ -17,7 +17,7 @@ local newproxy, getmetatable = newproxy, getmetatable; local print = print; local has_array, array = pcall(require, "util.array"); -local array_mt = hasarray and getmetatable(array()) or {}; +local array_mt = has_array and getmetatable(array()) or {}; --module("json") local json = {}; -- cgit v1.2.3 From 4687bfd21474f94f951e11af67c8610dfd10fb26 Mon Sep 17 00:00:00 2001 From: Waqas Hussain Date: Mon, 6 May 2013 19:43:59 -0400 Subject: util.json: Make setmetatable local. --- util/json.lua | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'util') diff --git a/util/json.lua b/util/json.lua index 67276765..0ce315b2 100644 --- a/util/json.lua +++ b/util/json.lua @@ -13,7 +13,7 @@ local tostring, tonumber = tostring, tonumber; local pairs, ipairs = pairs, ipairs; local next = next; local error = error; -local newproxy, getmetatable = newproxy, getmetatable; +local newproxy, getmetatable, setmetatable = newproxy, getmetatable, setmetatable; local print = print; local has_array, array = pcall(require, "util.array"); -- cgit v1.2.3 From def3fc6cd940d413adc04c080b5aa3b40d0d9626 Mon Sep 17 00:00:00 2001 From: Waqas Hussain Date: Tue, 7 May 2013 10:41:03 -0400 Subject: util.array: Wrap tostring() output in {} (otherwise empty arrays print as ""). --- util/array.lua | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'util') diff --git a/util/array.lua b/util/array.lua index b78fb98f..2d58e7fb 100644 --- a/util/array.lua +++ b/util/array.lua @@ -17,7 +17,7 @@ local tostring = tostring; local array = {}; local array_base = {}; local array_methods = {}; -local array_mt = { __index = array_methods, __tostring = function (array) return array:concat(", "); end }; +local array_mt = { __index = array_methods, __tostring = function (array) return "{"..array:concat(", ").."}"; end }; local function new_array(self, t, _s, _var) if type(t) == "function" then -- Assume iterator -- cgit v1.2.3 From 4d84405868480d4eae26f58afe4f010b661ddc4f Mon Sep 17 00:00:00 2001 From: Waqas Hussain Date: Tue, 7 May 2013 10:42:44 -0400 Subject: util.json: New, faster, stricter, more compliant JSON decoder. Now returns nil,err instead of throwing errors on invalid input. --- util/json.lua | 347 ++++++++++++++++++++++++++-------------------------------- 1 file changed, 155 insertions(+), 192 deletions(-) (limited to 'util') diff --git a/util/json.lua b/util/json.lua index 0ce315b2..82ebcc43 100644 --- a/util/json.lua +++ b/util/json.lua @@ -185,214 +185,177 @@ end ----------------------------------- -function json.decode(json) - json = json.." "; -- appending a space ensures valid json wouldn't touch EOF - local pos = 1; - local current = {}; - local stack = {}; - local ch, peek; - local function next() - ch = json:sub(pos, pos); - if ch == "" then error("Unexpected EOF"); end - pos = pos+1; - peek = json:sub(pos, pos); - return ch; - end - - local function skipwhitespace() - while ch and (ch == "\r" or ch == "\n" or ch == "\t" or ch == " ") do - next(); +local function _skip_whitespace(json, index) + return json:find("[^ \t\r\n]", index) or index; -- no need to check \r\n, we converted those to \t +end +local function _fixobject(obj) + local __array = obj.__array; + if __array then + obj.__array = nil; + for i,v in ipairs(__array) do + t_insert(obj, v); end end - local function skiplinecomment() - repeat next(); until not(ch) or ch == "\r" or ch == "\n"; - skipwhitespace(); - end - local function skipstarcomment() - next(); next(); -- skip '/', '*' - while peek and ch ~= "*" and peek ~= "/" do next(); end - if not peek then error("eof in star comment") end - next(); next(); -- skip '*', '/' - skipwhitespace(); - end - local function skipstuff() - while true do - skipwhitespace(); - if ch == "/" and peek == "*" then - skipstarcomment(); - elseif ch == "/" and peek == "/" then - skiplinecomment(); + local __hash = obj.__hash; + if __hash then + obj.__hash = nil; + local k; + for i,v in ipairs(__hash) do + if k ~= nil then + obj[k] = v; k = nil; else - return; + k = v; end end end - - local readvalue; - local function readarray() - local t = setmetatable({}, array_mt); - next(); -- skip '[' - skipstuff(); - if ch == "]" then next(); return t; end - t_insert(t, readvalue()); - while true do - skipstuff(); - if ch == "]" then next(); return t; end - if not ch then error("eof while reading array"); - elseif ch == "," then next(); - elseif ch then error("unexpected character in array, comma expected"); end - if not ch then error("eof while reading array"); end - t_insert(t, readvalue()); + return obj; +end +local _readvalue, _readstring; +local function _readobject(json, index) + local o = {}; + while true do + local key, val; + index = _skip_whitespace(json, index + 1); + if json:byte(index) ~= 0x22 then -- "\"" + if json:byte(index) == 0x7d then return o, index + 1; end -- "}" + return nil, "key expected"; end + key, index = _readstring(json, index); + if key == nil then return nil, index; end + index = _skip_whitespace(json, index); + if json:byte(index) ~= 0x3a then return nil, "colon expected"; end -- ":" + val, index = _readvalue(json, index + 1); + if val == nil then return nil, index; end + o[key] = val; + index = _skip_whitespace(json, index); + local b = json:byte(index); + if b == 0x7d then return _fixobject(o), index + 1; end -- "}" + if b ~= 0x2c then return nil, "object eof"; end -- "," end - - local function checkandskip(c) - local x = ch or "eof"; - if x ~= c then error("unexpected "..x..", '"..c.."' expected"); end - next(); - end - local function readliteral(lit, val) - for c in lit:gmatch(".") do - checkandskip(c); +end +local function _readarray(json, index) + local a = {}; + local oindex = index; + while true do + local val; + val, index = _readvalue(json, index + 1); + if val == nil then + if json:byte(oindex + 1) == 0x5d then return setmetatable(a, array_mt), oindex + 2; end -- "]" + return val, index; end - return val; + t_insert(a, val); + index = _skip_whitespace(json, index); + local b = json:byte(index); + if b == 0x5d then return setmetatable(a, array_mt), index + 1; end -- "]" + if b ~= 0x2c then return nil, "array eof"; end -- "," end - local function readstring() - local s = {}; - checkandskip("\""); - while ch do - while ch and ch ~= "\\" and ch ~= "\"" do - t_insert(s, ch); next(); - end - if ch == "\\" then - next(); - if unescapes[ch] then - t_insert(s, unescapes[ch]); - next(); - elseif ch == "u" then - local seq = ""; - for i=1,4 do - next(); - if not ch then error("unexpected eof in string"); end - if not ch:match("[0-9a-fA-F]") then error("invalid unicode escape sequence in string"); end - seq = seq..ch; - end - t_insert(s, codepoint_to_utf8(tonumber(seq, 16))); - next(); - else error("invalid escape sequence in string"); end - end - if ch == "\"" then - next(); - return t_concat(s); - end - end - error("eof while reading string"); +end +local _unescape_error; +local function _unescape_surrogate_func(x) + local lead, trail = tonumber(x:sub(3, 6), 16), tonumber(x:sub(9, 12), 16); + local codepoint = lead * 0x400 + trail - 0x35FDC00; + local a = codepoint % 64; + codepoint = (codepoint - a) / 64; + local b = codepoint % 64; + codepoint = (codepoint - b) / 64; + local c = codepoint % 64; + codepoint = (codepoint - c) / 64; + return s_char(0xF0 + codepoint, 0x80 + c, 0x80 + b, 0x80 + a); +end +local function _unescape_func(x) + x = x:match("%x%x%x%x", 3); + if x then + --if x >= 0xD800 and x <= 0xDFFF then _unescape_error = true; end -- bad surrogate pair + return codepoint_to_utf8(tonumber(x, 16)); end - local function readnumber() - local s = ""; - if ch == "-" then - s = s..ch; next(); - if not ch:match("[0-9]") then error("number format error"); end - end - if ch == "0" then - s = s..ch; next(); - if ch:match("[0-9]") then error("number format error"); end - else - while ch and ch:match("[0-9]") do - s = s..ch; next(); - end - end - if ch == "." then - s = s..ch; next(); - if not ch:match("[0-9]") then error("number format error"); end - while ch and ch:match("[0-9]") do - s = s..ch; next(); - end - if ch == "e" or ch == "E" then - s = s..ch; next(); - if ch == "+" or ch == "-" then - s = s..ch; next(); - if not ch:match("[0-9]") then error("number format error"); end - while ch and ch:match("[0-9]") do - s = s..ch; next(); - end - end - end - end - return tonumber(s); + _unescape_error = true; +end +function _readstring(json, index) + index = index + 1; + local endindex = json:find("\"", index, true); + if endindex then + local s = json:sub(index, endindex - 1); + --if s:find("[%z-\31]") then return nil, "control char in string"; end + -- FIXME handle control characters + _unescape_error = nil; + --s = s:gsub("\\u[dD][89abAB]%x%x\\u[dD][cdefCDEF]%x%x", _unescape_surrogate_func); + -- FIXME handle escapes beyond BMP + s = s:gsub("\\u.?.?.?.?", _unescape_func); + if _unescape_error then return nil, "invalid escape"; end + return s, endindex + 1; end - local function readmember(t) - skipstuff(); - local k = readstring(); - skipstuff(); - checkandskip(":"); - t[k] = readvalue(); + return nil, "string eof"; +end +local function _readnumber(json, index) + local m = json:match("[0-9%.%-eE%+]+", index); -- FIXME do strict checking + return tonumber(m), index + #m; +end +local function _readnull(json, index) + local a, b, c = json:byte(index + 1, index + 3); + if a == 0x75 and b == 0x6c and c == 0x6c then + return null, index + 4; end - local function fixobject(obj) - local __array = obj.__array; - if __array then - obj.__array = nil; - for i,v in ipairs(__array) do - t_insert(obj, v); - end - end - local __hash = obj.__hash; - if __hash then - obj.__hash = nil; - local k; - for i,v in ipairs(__hash) do - if k ~= nil then - obj[k] = v; k = nil; - else - k = v; - end - end - end - return obj; + return nil, "null parse failed"; +end +local function _readtrue(json, index) + local a, b, c = json:byte(index + 1, index + 3); + if a == 0x72 and b == 0x75 and c == 0x65 then + return true, index + 4; end - local function readobject() - local t = {}; - next(); -- skip '{' - skipstuff(); - if ch == "}" then next(); return t; end - if not ch then error("eof while reading object"); end - readmember(t); - while true do - skipstuff(); - if ch == "}" then next(); return fixobject(t); end - if not ch then error("eof while reading object"); - elseif ch == "," then next(); - elseif ch then error("unexpected character in object, comma expected"); end - if not ch then error("eof while reading object"); end - readmember(t); - end + return nil, "true parse failed"; +end +local function _readfalse(json, index) + local a, b, c, d = json:byte(index + 1, index + 4); + if a == 0x61 and b == 0x6c and c == 0x73 and d == 0x65 then + return false, index + 5; end - - function readvalue() - skipstuff(); - while ch do - if ch == "{" then - return readobject(); - elseif ch == "[" then - return readarray(); - elseif ch == "\"" then - return readstring(); - elseif ch:match("[%-0-9%.]") then - return readnumber(); - elseif ch == "n" then - return readliteral("null", null); - elseif ch == "t" then - return readliteral("true", true); - elseif ch == "f" then - return readliteral("false", false); - else - error("invalid character at value start: "..ch); - end - end - error("eof while reading value"); + return nil, "false parse failed"; +end +function _readvalue(json, index) + index = _skip_whitespace(json, index); + local b = json:byte(index); + -- TODO try table lookup instead of if-else? + if b == 0x7B then -- "{" + return _readobject(json, index); + elseif b == 0x5B then -- "[" + return _readarray(json, index); + elseif b == 0x22 then -- "\"" + return _readstring(json, index); + elseif b ~= nil and b >= 0x30 and b <= 0x39 or b == 0x2d then -- "0"-"9" or "-" + return _readnumber(json, index); + elseif b == 0x6e then -- "n" + return _readnull(json, index); + elseif b == 0x74 then -- "t" + return _readtrue(json, index); + elseif b == 0x66 then -- "f" + return _readfalse(json, index); + else + return nil, "value expected"; end - next(); - return readvalue(); +end +local first_escape = { + ["\\\""] = "\\u0022"; + ["\\\\"] = "\\u005c"; + ["\\/" ] = "\\u002f"; + ["\\b" ] = "\\u0008"; + ["\\f" ] = "\\u000C"; + ["\\n" ] = "\\u000A"; + ["\\r" ] = "\\u000D"; + ["\\t" ] = "\\u0009"; + ["\\u" ] = "\\u"; +}; + +function json.decode(json) + json = json:gsub("\\.", first_escape) -- get rid of all escapes except \uXXXX, making string parsing much simpler + --:gsub("[\r\n]", "\t"); -- \r\n\t are equivalent, we care about none of them, and none of them can be in strings + + -- TODO do encoding verification + + local val, index = _readvalue(json, 1); + if val == nil then return val, index; end + if json:find("[^ \t\r\n]", index) then return nil, "garbage at eof"; end + + return val; end function json.test(object) -- cgit v1.2.3