--[[

Copyright (c) 2014 Robin Wellner

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated 
documentation files (the "Software"), to deal in the Software without restriction, including without limitation 
the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and 
to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED 
TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 
THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF 
CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 
DEALINGS IN THE SOFTWARE.

]]

local M = {}
local expect_object, dump_object
local error, tostring, pairs, type, floor, huge, concat = error, tostring, pairs, type, math.floor, math.huge, table.concat

local dump_type = {}

function dump_type:string(nmemo, memo, acc)
	local nacc = #acc
	acc[nacc + 1] = '"'
	acc[nacc + 2] = self:gsub('"', '""')
	acc[nacc + 3] = '"'
	return nmemo
end

function dump_type:number(nmemo, memo, acc)
	acc[#acc + 1] = ("%.17g"):format(self)
	return nmemo
end

function dump_type:table(nmemo, memo, acc)
	if memo[self] then
		acc[#acc + 1] = '@'
		acc[#acc + 1] = tostring(memo[self])
		return nmemo
	end
	nmemo = nmemo + 1
	memo[self] = nmemo
	acc[#acc + 1] = '{'
	local nself = #self
	for i = 1, nself do -- don't use ipairs here, we need the gaps
		nmemo = dump_object(self[i], nmemo, memo, acc)
		acc[#acc + 1] = ','
	end
	for k, v in pairs(self) do
		if type(k) ~= 'number' or floor(k) ~= k or k < 1 or k > nself then
			nmemo = dump_object(k, nmemo, memo, acc)
			acc[#acc + 1] = ':'
			nmemo = dump_object(v, nmemo, memo, acc)
			acc[#acc + 1] = ','
		end
	end
	acc[#acc] = acc[#acc] == '{' and '{}' or '}'
	return nmemo
end

function dump_object(object, nmemo, memo, acc)
	if object == true then
		acc[#acc + 1] = 't'
	elseif object == false then
		acc[#acc + 1] = 'f'
	elseif object == nil then
		acc[#acc + 1] = 'n'
	elseif object ~= object then
		if (''..object):sub(1,1) == '-' then
			acc[#acc + 1] = 'N'
		else
			acc[#acc + 1] = 'Q'
		end
	elseif object == huge then
		acc[#acc + 1] = 'I'
	elseif object == -huge then
		acc[#acc + 1] = 'i'
	else
		local t = type(object)
		if not dump_type[t] then
			error('cannot dump type ' .. t)
		end
		return dump_type[t](object, nmemo, memo, acc)
	end
	return nmemo
end

function M.dumps(object)
	local nmemo = 0
	local memo = {}
	local acc = {}
	dump_object(object, nmemo, memo, acc)
	return concat(acc)
end

local function invalid(i)
	error('invalid input at position ' .. i)
end

local nonzero_digit = {['1'] = true, ['2'] = true, ['3'] = true, ['4'] = true, ['5'] = true, ['6'] = true, ['7'] = true, ['8'] = true, ['9'] = true}
local is_digit = {['0'] = true, ['1'] = true, ['2'] = true, ['3'] = true, ['4'] = true, ['5'] = true, ['6'] = true, ['7'] = true, ['8'] = true, ['9'] = true}
local function expect_number(string, start)
	local i = start
	local head = string:sub(i, i)
	if head == '-' then
		i = i + 1
		head = string:sub(i, i)
	end
	if nonzero_digit[head] then
		repeat
			i = i + 1
			head = string:sub(i, i)
		until not is_digit[head]
	elseif head == '0' then
		i = i + 1
		head = string:sub(i, i)
	else
		invalid(i)
	end
	if head == '.' then
		local oldi = i
		repeat
			i = i + 1
			head = string:sub(i, i)
		until not is_digit[head]
		if i == oldi + 1 then
			invalid(i)
		end
	end
	if head == 'e' or head == 'E' then
		i = i + 1
		head = string:sub(i, i)
		if head == '+' or head == '-' then
			i = i + 1
			head = string:sub(i, i)
		end
		if not is_digit[head] then
			invalid(i)
		end
		repeat
			i = i + 1
			head = string:sub(i, i)
		until not is_digit[head]
	end
	return tonumber(string:sub(start, i - 1)), i
end

local expect_object_head = {
	t = function(string, i) return true, i end,
	f = function(string, i) return false, i end,
	n = function(string, i) return nil, i end,
	Q = function(string, i) return -(0/0), i end,
	N = function(string, i) return 0/0, i end,
	I = function(string, i) return 1/0, i end,
	i = function(string, i) return -1/0, i end,
	['"'] = function(string, i)
		local nexti = i - 1
		repeat
			nexti = string:find('"', nexti + 1, true) + 1
		until string:sub(nexti, nexti) ~= '"'
		return string:sub(i, nexti - 2):gsub('""', '"'), nexti
	end,
	['0'] = function(string, i)
		return expect_number(string, i - 1)
	end,
	['{'] = function(string, i, tables)
		local nt, k, v = {}
		local j = 1
		tables[#tables + 1] = nt
		if string:sub(i, i) == '}' then
			return nt, i + 1
		end
		while true do
			k, i = expect_object(string, i, tables)
			if string:sub(i, i) == ':' then
				v, i = expect_object(string, i + 1, tables)
				nt[k] = v
			else
				nt[j] = k
				j = j + 1
			end
			local head = string:sub(i, i)
			if head == ',' then
				i = i + 1
			elseif head == '}' then
				return nt, i + 1
			else
				invalid(i)
			end
		end
	end,
	['@'] = function(string, i, tables)
		local match = string:match('^%d+', i)
		local ref = tonumber(match)
		if tables[ref] then
			return tables[ref], i + #match
		end
		invalid(i)
	end,
}
expect_object_head['1'] = expect_object_head['0']
expect_object_head['2'] = expect_object_head['0']
expect_object_head['3'] = expect_object_head['0']
expect_object_head['4'] = expect_object_head['0']
expect_object_head['5'] = expect_object_head['0']
expect_object_head['6'] = expect_object_head['0']
expect_object_head['7'] = expect_object_head['0']
expect_object_head['8'] = expect_object_head['0']
expect_object_head['9'] = expect_object_head['0']
expect_object_head['-'] = expect_object_head['0']
expect_object_head['.'] = expect_object_head['0']

expect_object = function(string, i, tables)
	local head = string:sub(i, i)
	if expect_object_head[head] then
		return expect_object_head[head](string, i + 1, tables)
	end
	invalid(i)
end

function M.loads(string, maxsize)
	return (expect_object(string, 1, {}))
end

return M