builtin/common/serialize.lua

   1 --- Lua module to serialize values as Lua code.
   2 -- From: https://github.com/fab13n/metalua/blob/no-dll/src/lib/serialize.lua
   3 -- License: MIT
   4 -- @copyright 2006-2997 Fabien Fleutot <metalua@gmail.com>
   5 -- @author Fabien Fleutot <metalua@gmail.com>
   6 -- @author ShadowNinja <shadowninja@minetest.net>
   7 --------------------------------------------------------------------------------
   8
   9 --- Serialize an object into a source code string. This string, when passed as
  10 -- an argument to deserialize(), returns an object structurally identical to
  11 -- the original one.  The following are currently supported:
  12 --   * Booleans, numbers, strings, and nil.
  13 --   * Functions; uses interpreter-dependent (and sometimes platform-dependent) bytecode!
  14 --   * Tables; they can cantain multiple references and can be recursive, but metatables aren't saved.
  15 -- This works in two phases:
  16 --   1. Recursively find and record multiple references and recursion.
  17 --   2. Recursively dump the value into a string.
  18 -- @param x Value to serialize (nil is allowed).
  19 -- @return load()able string containing the value.
  20 function core.serialize(x)
  21         local local_index  = 1  -- Top index of the "_" local table in the dump
  22         -- table->nil/1/2 set of tables seen.
  23         -- nil = not seen, 1 = seen once, 2 = seen multiple times.
  24         local seen = {}
  25
  26         -- nest_points are places where a table appears within itself, directly
  27         -- or not.  For instance, all of these chunks create nest points in
  28         -- table x: "x = {}; x[x] = 1", "x = {}; x[1] = x",
  29         -- "x = {}; x[1] = {y = {x}}".
  30         -- To handle those, two tables are used by mark_nest_point:
  31         -- * nested - Transient set of tables being currently traversed.
  32         --   Used for detecting nested tables.
  33         -- * nest_points - parent->{key=value, ...} table cantaining the nested
  34         --   keys and values in the parent.  They're all dumped after all the
  35         --   other table operations have been performed.
  36         --
  37         -- mark_nest_point(p, k, v) fills nest_points with information required
  38         -- to remember that key/value (k, v) creates a nest point  in table
  39         -- parent. It also marks "parent" and the nested item(s) as occuring
  40         -- multiple times, since several references to it will be required in
  41         -- order to patch the nest points.
  42         local nest_points  = {}
  43         local nested = {}
  44         local function mark_nest_point(parent, k, v)
  45                 local nk, nv = nested[k], nested[v]
  46                 local np = nest_points[parent]
  47                 if not np then
  48                         np = {}
  49                         nest_points[parent] = np
  50                 end
  51                 np[k] = v
  52                 seen[parent] = 2
  53                 if nk then seen[k] = 2 end
  54                 if nv then seen[v] = 2 end
  55         end
  56
  57         -- First phase, list the tables and functions which appear more than
  58         -- once in x.
  59         local function mark_multiple_occurences(x)
  60                 local tp = type(x)
  61                 if tp ~= "table" and tp ~= "function" then
  62                         -- No identity (comparison is done by value, not by instance)
  63                         return
  64                 end
  65                 if seen[x] == 1 then
  66                         seen[x] = 2
  67                 elseif seen[x] ~= 2 then
  68                         seen[x] = 1
  69                 end
  70
  71                 if tp == "table" then
  72                         nested[x] = true
  73                         for k, v in pairs(x) do
  74                                 if nested[k] or nested[v] then
  75                                         mark_nest_point(x, k, v)
  76                                 else
  77                                         mark_multiple_occurences(k)
  78                                         mark_multiple_occurences(v)
  79                                 end
  80                         end
  81                         nested[x] = nil
  82                 end
  83         end
  84
  85         local dumped     = {}  -- object->varname set
  86         local local_defs = {}  -- Dumped local definitions as source code lines
  87
  88         -- Mutually recursive local functions:
  89         local dump_val, dump_or_ref_val
  90
  91         -- If x occurs multiple times, dump the local variable rather than
  92         -- the value. If it's the first time it's dumped, also dump the
  93         -- content in local_defs.
  94         function dump_or_ref_val(x)
  95                 if seen[x] ~= 2 then
  96                         return dump_val(x)
  97                 end
  98                 local var = dumped[x]
  99                 if var then  -- Already referenced
 100                         return var
 101                 end
 102                 -- First occurence, create and register reference
 103                 local val = dump_val(x)
 104                 local i = local_index
 105                 local_index = local_index + 1
 106                 var = "_["..i.."]"
 107                 table.insert(local_defs, var.." = "..val)
 108                 dumped[x] = var
 109                 return var
 110         end
 111
 112         -- Second phase.  Dump the object; subparts occuring multiple times
 113         -- are dumped in local variables which can be referenced multiple
 114         -- times.  Care is taken to dump local vars in a sensible order.
 115         function dump_val(x)
 116                 local  tp = type(x)
 117                 if     x  == nil        then return "nil"
 118                 elseif tp == "number"   then return tostring(x)
 119                 elseif tp == "string"   then return string.format("%q", x)
 120                 elseif tp == "boolean"  then return x and "true" or "false"
 121                 elseif tp == "function" then
 122                         return string.format("loadstring(%q)", string.dump(x))
 123                 elseif tp == "table" then
 124                         local vals = {}
 125                         local idx_dumped = {}
 126                         local np = nest_points[x]
 127                         for i, v in ipairs(x) do
 128                                 if not np or not np[i] then
 129                                         table.insert(vals, dump_or_ref_val(v))
 130                                 end
 131                                 idx_dumped[i] = true
 132                         end
 133                         for k, v in pairs(x) do
 134                                 if (not np or not np[k]) and
 135                                                 not idx_dumped[k] then
 136                                         table.insert(vals,
 137                                                 "["..dump_or_ref_val(k).."] = "
 138                                                 ..dump_or_ref_val(v))
 139                                 end
 140                         end
 141                         return "{"..table.concat(vals, ", ").."}"
 142                 else
 143                         error("Can't serialize data of type "..tp)
 144                 end
 145         end
 146
 147         local function dump_nest_points()
 148                 for parent, vals in pairs(nest_points) do
 149                         for k, v in pairs(vals) do
 150                                 table.insert(local_defs, dump_or_ref_val(parent)
 151                                         .."["..dump_or_ref_val(k).."] = "
 152                                         ..dump_or_ref_val(v))
 153                         end
 154                 end
 155         end
 156
 157         mark_multiple_occurences(x)
 158         local top_level = dump_or_ref_val(x)
 159         dump_nest_points()
 160
 161         if next(local_defs) then
 162                 return "local _ = {}\n"
 163                         ..table.concat(local_defs, "\n")
 164                         .."\nreturn "..top_level
 165         else
 166                 return "return "..top_level
 167         end
 168 end
 169
 170 -- Deserialization
 171
 172 local env = {
 173         loadstring = loadstring,
 174 }
 175
 176 local safe_env = {
 177         loadstring = function() end,
 178 }
 179
 180 function core.deserialize(str, safe)
 181         if str:byte(1) == 0x1B then
 182                 return nil, "Bytecode prohibited"
 183         end
 184         local f, err = loadstring(str)
 185         if not f then return nil, err end
 186         setfenv(f, safe and safe_env or env)
 187
 188         local good, data = pcall(f)
 189         if good then
 190                 return data
 191         else
 192                 return nil, data
 193         end
 194 end
 195
 196
 197 -- Unit tests
 198 local test_in = {cat={sound="nyan", speed=400}, dog={sound="woof"}}
 199 local test_out = core.deserialize(core.serialize(test_in))
 200
 201 assert(test_in.cat.sound == test_out.cat.sound)
 202 assert(test_in.cat.speed == test_out.cat.speed)
 203 assert(test_in.dog.sound == test_out.dog.sound)
 204
 205 test_in = {escape_chars="\n\r\t\v\\\"\'", non_european="θשׁ٩∂"}
 206 test_out = core.deserialize(core.serialize(test_in))
 207 assert(test_in.escape_chars == test_out.escape_chars)
 208 assert(test_in.non_european == test_out.non_european)
 209