From 002bc0ea14658e9bf790edfaeffaf24b6150cb10 Mon Sep 17 00:00:00 2001 From: unknown Date: Tue, 23 Dec 2008 13:28:57 +0100 Subject: [PATCH] serialize now handles arbitrary recursions --- src/lib/serialize.lua | 115 +++++++++++++++++++++++++++++++----------- 1 file changed, 86 insertions(+), 29 deletions(-) diff --git a/src/lib/serialize.lua b/src/lib/serialize.lua index 5052918..6929e8b 100644 --- a/src/lib/serialize.lua +++ b/src/lib/serialize.lua @@ -8,19 +8,51 @@ -- Caveat: metatables and environments aren't saved. -------------------------------------------------------------------------------- -local no_identity = { number=1, boolean=1, string=1, nil=1 } +local no_identity = { number=1, boolean=1, string=1, ['nil']=1 } function serialize (x) - + local gensym_max = 0 -- index of the gensym() symbol generator local seen_once = { } -- element->true set of elements seen exactly once in the table local multiple = { } -- element->varname set of elements seen more than once local nested = { } -- transient, set of elements currently being traversed - + local nest_points = { } + local nest_patches = { } + local function gensym() gensym_max = gensym_max + 1 ; return gensym_max end - + + ----------------------------------------------------------------------------- + -- nest_points are places where a table appears within itself, directly or not. + -- for instance, all of these chunks create nest points in table x: + -- "x = { }; x[x] = 1", "x = { }; x[1] = x", "x = { }; x[1] = { y = { x } }". + -- To handle those, two tables are created by mark_nest_point: + -- * nest_points [parent] associates all keys and values in table parent which + -- create a nest_point with boolean `true' + -- * nest_patches contain a list of { parent, key, value } tuples creating + -- a nest point. They're all dumped after all the other table operations + -- have been performed. + -- + -- mark_nest_point (p, k, v) fills tables nest_points and nest_patches with + -- informations required to remember that key/value (k,v) create a nest point + -- in table parent. It also marks `parent' as occuring multiple times, since + -- several references to it will be required in order to patch the nest + -- points. + ----------------------------------------------------------------------------- + local function mark_nest_point (parent, k, v) + local nk, nv = nested[k], nested[v] + assert (not nk or seen_once[k] or multiple[k]) + assert (not nv or seen_once[v] or multiple[v]) + local mode = (nk and nv and "kv") or (nk and "k") or ("v") + local parent_np = nest_points [parent] + local pair = { k, v } + if not parent_np then parent_np = { }; nest_points [parent] = parent_np end + parent_np [k], parent_np [v] = nk, nv + table.insert (nest_patches, { parent, k, v }) + seen_once [parent], multiple [parent] = nil, true + end + ----------------------------------------------------------------------------- -- First pass, list the tables and functions which appear more than once in x ----------------------------------------------------------------------------- @@ -33,10 +65,10 @@ function serialize (x) if type (x) == 'table' then nested [x] = true for k, v in pairs (x) do - if nested [k] or nexted [v] - then error "Can't serialize recursive tables yet" end - mark_multiple_occurences (k) - mark_multiple_occurences (v) + if nested[k] or nested[v] then mark_nest_point (x, k, v) else + mark_multiple_occurences (k) + mark_multiple_occurences (v) + end end nested [x] = nil end @@ -45,12 +77,33 @@ function serialize (x) local dumped = { } -- multiply occuring values already dumped in localdefs local localdefs = { } -- already dumped local definitions as source code lines + + -- mutually recursive functions: + local dump_val, dump_or_ref_val + + -------------------------------------------------------------------- + -- if x occurs multiple times, dump the local var rather than the + -- value. If it's the first time it's dumped, also dump the content + -- in localdefs. + -------------------------------------------------------------------- + function dump_or_ref_val (x) + if nested[x] then return 'false' end -- placeholder for recursive reference + if not multiple[x] then return dump_val (x) end + local var = dumped [x] + if var then return "_[" .. var .. "]" end -- already referenced + local val = dump_val(x) -- first occurence, create and register reference + var = gensym() + table.insert(localdefs, "_["..var.."]="..val) + dumped [x] = var + return "_[" .. var .. "]" + end + ----------------------------------------------------------------------------- -- Second pass, dump the object; subparts occuring multiple times are dumped -- in local variables which can be referenced multiple times; -- care is taken to dump locla vars in asensible order. ----------------------------------------------------------------------------- - local function dump_val(x) + function dump_val(x) local t = type(x) if x==nil then return 'nil' elseif t=="number" then return tostring(x) @@ -59,31 +112,23 @@ function serialize (x) elseif t=="function" then return string.format ("loadstring(%q,'@serialized')", string.dump (x)) elseif t=="table" then - local acc = { } - -------------------------------------------------------------------- - -- if x occurs multiple times, dump the local var rather than the - -- value. If it's the first time it's dumped, also dump the content - -- in localdefs. - -------------------------------------------------------------------- - local function check_multiple (x) - if not multiple[x] then return dump_val (x) end - local var = dumped [x] - if var then return "_[" .. var .. "]" end - local val = dump_val(x) - var = gensym() - table.insert(localdefs, "_["..var.."]="..val) - dumped [x] = var - return "_[" .. var .. "]" - end + local acc = { } local idx_dumped = { } + local np = nest_points [x] for i, v in ipairs(x) do - table.insert (acc, check_multiple(v)) + if np and np[v] then + table.insert (acc, 'false') -- placeholder + else + table.insert (acc, dump_or_ref_val(v)) + end idx_dumped[i] = true end for k, v in pairs(x) do - if not idx_dumped[k] then - table.insert (acc, "[" .. check_multiple(k) .. "] = " .. check_multiple(v)) + if np and (np[k] or np[v]) then + --check_multiple(k); check_multiple(v) -- force dumps in localdefs + elseif not idx_dumped[k] then + table.insert (acc, "[" .. dump_or_ref_val(k) .. "] = " .. dump_or_ref_val(v)) end end return "{ "..table.concat(acc,", ").." }" @@ -92,8 +137,20 @@ function serialize (x) end end + local function dump_nest_patches() + for _, entry in ipairs(nest_patches) do + local p, k, v = unpack (entry) + assert (multiple[p]) + local set = dump_or_ref_val (p) .. "[" .. dump_or_ref_val (k) .. "] = " .. + dump_or_ref_val (v) .. " -- rec " + table.insert (localdefs, set) + end + end + mark_multiple_occurences (x) - local toplevel = dump_val (x) + local toplevel = dump_or_ref_val (x) + dump_nest_patches() + if next (localdefs) then return "local _={ }\n" .. table.concat (localdefs, "\n") .. -- 2.44.0