builtin/common/serialize.lua

   1 -- Minetest: builtin/serialize.lua
   2
   3 -- https://github.com/fab13n/metalua/blob/no-dll/src/lib/serialize.lua
   4 -- Copyright (c) 2006-2997 Fabien Fleutot <metalua@gmail.com>
   5 -- License: MIT
   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 --------------------------------------------------------------------------------
  14
  15 local no_identity = { number=1, boolean=1, string=1, ['nil']=1 }
  16
  17 function core.serialize(x)
  18
  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 = { }
  25
  26         local function gensym()
  27                 gensym_max = gensym_max + 1 ;  return gensym_max
  28         end
  29
  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.
  40         --
  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
  45         -- points.
  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]
  53                 local pair = { k, v }
  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
  58         end
  59
  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
  68
  69                 if type (x) == 'table' then
  70                         nested [x] = true
  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)
  75                                 end
  76                         end
  77                         nested [x] = nil
  78                 end
  79         end
  80
  81         local dumped    = { } -- multiply occuring values already dumped in localdefs
  82         local localdefs = { } -- already dumped local definitions as source code lines
  83
  84         -- mutually recursive functions:
  85         local dump_val, dump_or_ref_val
  86
  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
  90         -- in localdefs.
  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
  98                 var = gensym()
  99                 table.insert(localdefs, "_["..var.."]="..val)
 100                 dumped [x] = var
 101                 return "_[" .. var .. "]"
 102         end
 103
 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         -----------------------------------------------------------------------------
 109         function dump_val(x)
 110                 local  t = type(x)
 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=="function" then
 116                         return "loadstring("..string.format("%q", string.dump(x))..")"
 117                 elseif t=="table" then
 118                         local acc        = { }
 119                         local idx_dumped = { }
 120                         local np         = nest_points [x]
 121                         for i, v in ipairs(x) do
 122                                 if np and np[v] then
 123                                         table.insert (acc, 'false') -- placeholder
 124                                 else
 125                                         table.insert (acc, dump_or_ref_val(v))
 126                                 end
 127                                 idx_dumped[i] = true
 128                         end
 129                         for k, v in pairs(x) do
 130                                 if np and (np[k] or np[v]) then
 131                                         --check_multiple(k); check_multiple(v) -- force dumps in localdefs
 132                                 elseif not idx_dumped[k] then
 133                                         table.insert (acc, "[" .. dump_or_ref_val(k) .. "] = " .. dump_or_ref_val(v))
 134                                 end
 135                         end
 136                         return "{ "..table.concat(acc,", ").." }"
 137                 else
 138                         error ("Can't serialize data of type "..t)
 139                 end
 140         end
 141
 142         local function dump_nest_patches()
 143                 for _, entry in ipairs(nest_patches) do
 144                         local p, k, v = unpack (entry)
 145                         assert (multiple[p])
 146                         local set = dump_or_ref_val (p) .. "[" .. dump_or_ref_val (k) .. "] = " ..
 147                                 dump_or_ref_val (v) .. " -- rec "
 148                         table.insert (localdefs, set)
 149                 end
 150         end
 151
 152         mark_multiple_occurences (x)
 153         local toplevel = dump_or_ref_val (x)
 154         dump_nest_patches()
 155
 156         if next (localdefs) then
 157                 return "local _={ }\n" ..
 158                         table.concat (localdefs, "\n") ..
 159                         "\nreturn " .. toplevel
 160         else
 161                 return "return " .. toplevel
 162         end
 163 end
 164
 165 -- Deserialization.
 166 -- http://stackoverflow.com/questions/5958818/loading-serialized-data-into-a-table
 167 --
 168
 169 local env = {
 170         loadstring = loadstring,
 171 }
 172
 173 local function noop() end
 174
 175 local safe_env = {
 176         loadstring = noop,
 177 }
 178
 179 local function stringtotable(sdata, safe)
 180         if sdata:byte(1) == 27 then return nil, "binary bytecode prohibited" end
 181         local f, message = assert(loadstring(sdata))
 182         if not f then return nil, message end
 183         if safe then
 184                 setfenv(f, safe_env)
 185         else
 186                 setfenv(f, env)
 187         end
 188         return f()
 189 end
 190
 191 function core.deserialize(sdata, safe)
 192         local table = {}
 193         local okay, results = pcall(stringtotable, sdata, safe)
 194         if okay then
 195                 return results
 196         end
 197         core.log('error', 'core.deserialize(): '.. results)
 198         return nil
 199 end
 200
 201 -- Run some unit tests
 202 local function unit_test()
 203         function unitTest(name, success)
 204                 if not success then
 205                         error(name .. ': failed')
 206                 end
 207         end
 208
 209         unittest_input = {cat={sound="nyan", speed=400}, dog={sound="woof"}}
 210         unittest_output = core.deserialize(core.serialize(unittest_input))
 211
 212         unitTest("test 1a", unittest_input.cat.sound == unittest_output.cat.sound)
 213         unitTest("test 1b", unittest_input.cat.speed == unittest_output.cat.speed)
 214         unitTest("test 1c", unittest_input.dog.sound == unittest_output.dog.sound)
 215
 216         unittest_input = {escapechars="\n\r\t\v\\\"\'", noneuropean="θשׁ٩∂"}
 217         unittest_output = core.deserialize(core.serialize(unittest_input))
 218         unitTest("test 3a", unittest_input.escapechars == unittest_output.escapechars)
 219         unitTest("test 3b", unittest_input.noneuropean == unittest_output.noneuropean)
 220 end
 221 unit_test() -- Run it
 222 unit_test = nil -- Hide it
 223