+++ /dev/null
---------------------------------------------------------------------------------
--- Metalua
--- Summary: Table-to-source serializer
---------------------------------------------------------------------------------
---
--- Copyright (c) 2008-2009, Fabien Fleutot <metalua@gmail.com>.
---
--- This software is released under the MIT Licence, see licence.txt
--- for details.
---
---------------------------------------------------------------------------------
---
--- Serialize an object into a source code string. This string, when passed as
--- an argument to loadstring()(), returns an object structurally identical
--- to the original one.
---
--- The following are supported:
---
--- * strings, numbers, booleans, nil
---
--- * functions without upvalues
---
--- * tables thereof. There is no restriction on keys; recursive and shared
--- sub-tables are handled correctly.
---
--- Caveat: metatables and environments aren't saved; this might or might not
--- be what you want.
---------------------------------------------------------------------------------
-
-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 = { }
-
- -- Generate fresh indexes to store new sub-tables:
- local function gensym()
- gensym_max = gensym_max + 1 ; return gensym_max
- end
-
- -----------------------------------------------------------------------------
- -- `nest_points' are places where a (recursive) 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' contains 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)' creates a nest point in parent table `p'. It
- -- also marks `p' 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
-
- -----------------------------------------------------------------------------
- -- 1st pass, list the tables and functions which appear more than once in `x'
- -----------------------------------------------------------------------------
- local function mark_multiple_occurences (x)
- if no_identity [type(x)] then return end
- if seen_once [x] then seen_once [x], multiple [x] = nil, true
- elseif multiple [x] then -- pass
- else seen_once [x] = true end
-
- if type (x) == 'table' then
- nested [x] = true
- for k, v in pairs (x) do
- 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
- end
-
- 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
-
- -----------------------------------------------------------------------------
- -- 2nd pass, dump the object; subparts occuring multiple times are dumped
- -- in local variables, which can then be referenced multiple times;
- -- care is taken to dump local vars in an order which repect dependencies.
- -----------------------------------------------------------------------------
- function dump_val(x)
- local t = type(x)
- if x==nil then return 'nil'
- elseif t=="number" then return tostring(x)
- elseif t=="string" then return string.format("%q", x)
- elseif t=="boolean" then return x and "true" or "false"
- elseif t=="function" then
- return string.format ("loadstring(%q,'@serialized')", string.dump (x))
- elseif t=="table" then
-
- local acc = { }
- local idx_dumped = { }
- local np = nest_points [x]
- for i, v in ipairs(x) do
- 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 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,", ").." }"
- else
- error ("Can't serialize data of type "..t)
- end
- end
-
- -- Patch the recursive table entries:
- 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_or_ref_val (x)
- dump_nest_patches()
-
- if next (localdefs) then
- -- Dump local vars containing shared or recursive parts,
- -- then the main table using them.
- return "local _={ }\n" ..
- table.concat (localdefs, "\n") ..
- "\nreturn " .. toplevel
- else
- -- No shared part, straightforward dump:
- return "return " .. toplevel
- end
-end