1 -- Minetest: builtin/serialize.lua
3 -- https://github.com/fab13n/metalua/blob/no-dll/src/lib/serialize.lua
4 -- Copyright (c) 2006-2997 Fabien Fleutot <metalua@gmail.com>
6 --------------------------------------------------------------------------------
7 -- Serialize an object into a source code string. This string, when passed as
8 -- an argument to deserialize(), returns an object structurally identical
9 -- to the original one. The following are currently supported:
10 -- * strings, numbers, booleans, nil
11 -- * tables thereof. Tables can have shared part, but can't be recursive yet.
12 -- Caveat: metatables and environments aren't saved.
13 --------------------------------------------------------------------------------
15 local no_identity = { number=1, boolean=1, string=1, ['nil']=1 }
17 function minetest.serialize(x)
19 local gensym_max = 0 -- index of the gensym() symbol generator
20 local seen_once = { } -- element->true set of elements seen exactly once in the table
21 local multiple = { } -- element->varname set of elements seen more than once
22 local nested = { } -- transient, set of elements currently being traversed
23 local nest_points = { }
24 local nest_patches = { }
26 local function gensym()
27 gensym_max = gensym_max + 1 ; return gensym_max
30 -----------------------------------------------------------------------------
31 -- nest_points are places where a table appears within itself, directly or not.
32 -- for instance, all of these chunks create nest points in table x:
33 -- "x = { }; x[x] = 1", "x = { }; x[1] = x", "x = { }; x[1] = { y = { x } }".
34 -- To handle those, two tables are created by mark_nest_point:
35 -- * nest_points [parent] associates all keys and values in table parent which
36 -- create a nest_point with boolean `true'
37 -- * nest_patches contain a list of { parent, key, value } tuples creating
38 -- a nest point. They're all dumped after all the other table operations
39 -- have been performed.
41 -- mark_nest_point (p, k, v) fills tables nest_points and nest_patches with
42 -- informations required to remember that key/value (k,v) create a nest point
43 -- in table parent. It also marks `parent' as occuring multiple times, since
44 -- several references to it will be required in order to patch the nest
46 -----------------------------------------------------------------------------
47 local function mark_nest_point (parent, k, v)
48 local nk, nv = nested[k], nested[v]
49 assert (not nk or seen_once[k] or multiple[k])
50 assert (not nv or seen_once[v] or multiple[v])
51 local mode = (nk and nv and "kv") or (nk and "k") or ("v")
52 local parent_np = nest_points [parent]
54 if not parent_np then parent_np = { }; nest_points [parent] = parent_np end
55 parent_np [k], parent_np [v] = nk, nv
56 table.insert (nest_patches, { parent, k, v })
57 seen_once [parent], multiple [parent] = nil, true
60 -----------------------------------------------------------------------------
61 -- First pass, list the tables and functions which appear more than once in x
62 -----------------------------------------------------------------------------
63 local function mark_multiple_occurences (x)
64 if no_identity [type(x)] then return end
65 if seen_once [x] then seen_once [x], multiple [x] = nil, true
66 elseif multiple [x] then -- pass
67 else seen_once [x] = true end
69 if type (x) == 'table' then
71 for k, v in pairs (x) do
72 if nested[k] or nested[v] then mark_nest_point (x, k, v) else
73 mark_multiple_occurences (k)
74 mark_multiple_occurences (v)
81 local dumped = { } -- multiply occuring values already dumped in localdefs
82 local localdefs = { } -- already dumped local definitions as source code lines
84 -- mutually recursive functions:
85 local dump_val, dump_or_ref_val
87 --------------------------------------------------------------------
88 -- if x occurs multiple times, dump the local var rather than the
89 -- value. If it's the first time it's dumped, also dump the content
91 --------------------------------------------------------------------
92 function dump_or_ref_val (x)
93 if nested[x] then return 'false' end -- placeholder for recursive reference
94 if not multiple[x] then return dump_val (x) end
95 local var = dumped [x]
96 if var then return "_[" .. var .. "]" end -- already referenced
97 local val = dump_val(x) -- first occurence, create and register reference
99 table.insert(localdefs, "_["..var.."]="..val)
101 return "_[" .. var .. "]"
104 -----------------------------------------------------------------------------
105 -- Second pass, dump the object; subparts occuring multiple times are dumped
106 -- in local variables which can be referenced multiple times;
107 -- care is taken to dump locla vars in asensible order.
108 -----------------------------------------------------------------------------
111 if x==nil then return 'nil'
112 elseif t=="number" then return tostring(x)
113 elseif t=="string" then return string.format("%q", x)
114 elseif t=="boolean" then return x and "true" or "false"
115 elseif t=="table" then
117 local idx_dumped = { }
118 local np = nest_points [x]
119 for i, v in ipairs(x) do
121 table.insert (acc, 'false') -- placeholder
123 table.insert (acc, dump_or_ref_val(v))
127 for k, v in pairs(x) do
128 if np and (np[k] or np[v]) then
129 --check_multiple(k); check_multiple(v) -- force dumps in localdefs
130 elseif not idx_dumped[k] then
131 table.insert (acc, "[" .. dump_or_ref_val(k) .. "] = " .. dump_or_ref_val(v))
134 return "{ "..table.concat(acc,", ").." }"
136 error ("Can't serialize data of type "..t)
140 local function dump_nest_patches()
141 for _, entry in ipairs(nest_patches) do
142 local p, k, v = unpack (entry)
144 local set = dump_or_ref_val (p) .. "[" .. dump_or_ref_val (k) .. "] = " ..
145 dump_or_ref_val (v) .. " -- rec "
146 table.insert (localdefs, set)
150 mark_multiple_occurences (x)
151 local toplevel = dump_or_ref_val (x)
154 if next (localdefs) then
155 return "local _={ }\n" ..
156 table.concat (localdefs, "\n") ..
157 "\nreturn " .. toplevel
159 return "return " .. toplevel
164 -- http://stackoverflow.com/questions/5958818/loading-serialized-data-into-a-table
167 local function stringtotable(sdata)
168 if sdata:byte(1) == 27 then return nil, "binary bytecode prohibited" end
169 local f, message = assert(loadstring(sdata))
170 if not f then return nil, message end
175 function minetest.deserialize(sdata)
177 local okay,results = pcall(stringtotable, sdata)
181 print('error:'.. results)
185 -- Run some unit tests
186 local function unit_test()
187 function unitTest(name, success)
189 error(name .. ': failed')
193 unittest_input = {cat={sound="nyan", speed=400}, dog={sound="woof"}}
194 unittest_output = minetest.deserialize(minetest.serialize(unittest_input))
196 unitTest("test 1a", unittest_input.cat.sound == unittest_output.cat.sound)
197 unitTest("test 1b", unittest_input.cat.speed == unittest_output.cat.speed)
198 unitTest("test 1c", unittest_input.dog.sound == unittest_output.dog.sound)
200 unittest_input = {escapechars="\n\r\t\v\\\"\'\[\]", noneuropean="θשׁ٩∂"}
201 unittest_output = minetest.deserialize(minetest.serialize(unittest_input))
202 unitTest("test 3a", unittest_input.escapechars == unittest_output.escapechars)
203 unitTest("test 3b", unittest_input.noneuropean == unittest_output.noneuropean)
205 unit_test() -- Run it
206 unit_test = nil -- Hide it