src/lib/serialize.lua

   1 --------------------------------------------------------------------------------
   2 -- Metalua
   3 -- Summary: Table-to-source serializer
   4 --------------------------------------------------------------------------------
   5 --
   6 -- Copyright (c) 2008-2009, Fabien Fleutot <metalua@gmail.com>.
   7 --
   8 -- This software is released under the MIT Licence, see licence.txt
   9 -- for details.
  10 --
  11 --------------------------------------------------------------------------------
  12 --
  13 -- Serialize an object into a source code string. This string, when passed as
  14 -- an argument to loadstring()(), returns an object structurally identical
  15 -- to the original one.
  16 --
  17 -- The following are supported:
  18 --
  19 -- * strings, numbers, booleans, nil
  20 --
  21 -- * functions without upvalues
  22 --
  23 -- * tables thereof. There is no restriction on keys; recursive and shared
  24 --   sub-tables are handled correctly.
  25 --
  26 -- Caveat: metatables and environments aren't saved; this might or might not
  27 --         be what you want.
  28 --------------------------------------------------------------------------------
  29
  30 local no_identity = { number=1, boolean=1, string=1, ['nil']=1 }
  31
  32 function serialize (x)
  33
  34    local gensym_max =  0  -- index of the gensym() symbol generator
  35    local seen_once  = { } -- element->true set of elements seen exactly once in the table
  36    local multiple   = { } -- element->varname set of elements seen more than once
  37    local nested     = { } -- transient, set of elements currently being traversed
  38    local nest_points  = { }
  39    local nest_patches = { }
  40
  41    -- Generate fresh indexes to store new sub-tables:
  42    local function gensym()
  43       gensym_max = gensym_max + 1 ;  return gensym_max
  44    end
  45
  46    -----------------------------------------------------------------------------
  47    -- `nest_points' are places where a (recursive) table appears within
  48    -- itself, directly or not.  for instance, all of these chunks
  49    -- create nest points in table `x':
  50    --
  51    -- "x = { }; x[x] = 1"
  52    -- "x = { }; x[1] = x"
  53    -- "x = { }; x[1] = { y = { x } }".
  54    --
  55    -- To handle those, two tables are created by `mark_nest_point()':
  56    --
  57    -- * `nest_points [parent]' associates all keys and values in table
  58    --   parent which create a nest_point with boolean `true'
  59    --
  60    -- * `nest_patches' contains a list of `{ parent, key, value }'
  61    --   tuples creating a nest point. They're all dumped after all the
  62    --   other table operations have been performed.
  63    --
  64    -- `mark_nest_point (p, k, v)' fills tables `nest_points' and
  65    -- `nest_patches' with informations required to remember that
  66    -- key/value `(k,v)' creates a nest point in parent table `p'. It
  67    -- also marks `p' as occuring multiple times, since several
  68    -- references to it will be required in order to patch the nest
  69    -- points.
  70    -----------------------------------------------------------------------------
  71    local function mark_nest_point (parent, k, v)
  72       local nk, nv = nested[k], nested[v]
  73       assert (not nk or seen_once[k] or multiple[k])
  74       assert (not nv or seen_once[v] or multiple[v])
  75       local mode = (nk and nv and "kv") or (nk and "k") or ("v")
  76       local parent_np = nest_points [parent]
  77       local pair = { k, v }
  78       if not parent_np then parent_np = { }; nest_points [parent] = parent_np end
  79       parent_np [k], parent_np [v] = nk, nv
  80       table.insert (nest_patches, { parent, k, v })
  81       seen_once [parent], multiple [parent]  = nil, true
  82    end
  83
  84    -----------------------------------------------------------------------------
  85    -- 1st pass, list the tables and functions which appear more than once in `x'
  86    -----------------------------------------------------------------------------
  87    local function mark_multiple_occurences (x)
  88       if no_identity [type(x)] then return end
  89       if     seen_once [x]     then seen_once [x], multiple [x] = nil, true
  90       elseif multiple  [x]     then -- pass
  91       else   seen_once [x] = true end
  92
  93       if type (x) == 'table' then
  94          nested [x] = true
  95          for k, v in pairs (x) do
  96             if nested[k] or nested[v] then mark_nest_point (x, k, v) else
  97                mark_multiple_occurences (k)
  98                mark_multiple_occurences (v)
  99             end
 100          end
 101          nested [x] = nil
 102       end
 103    end
 104
 105    local dumped    = { } -- multiply occuring values already dumped in localdefs
 106    local localdefs = { } -- already dumped local definitions as source code lines
 107
 108
 109    -- mutually recursive functions:
 110    local dump_val, dump_or_ref_val
 111
 112    ------------------------------------------------------------------------------
 113    -- if `x' occurs multiple times, dump the local var rather than the
 114    -- value. If it's the first time it's dumped, also dump the content
 115    -- in localdefs.
 116    ------------------------------------------------------------------------------
 117    function dump_or_ref_val (x)
 118       if nested[x] then return 'false' end -- placeholder for recursive reference
 119       if not multiple[x] then return dump_val (x) end
 120       local var = dumped [x]
 121       if var then return "_[" .. var .. "]" end -- already referenced
 122       local val = dump_val(x) -- first occurence, create and register reference
 123       var = gensym()
 124       table.insert(localdefs, "_["..var.."]="..val)
 125       dumped [x] = var
 126       return "_[" .. var .. "]"
 127    end
 128
 129    -----------------------------------------------------------------------------
 130    -- 2nd pass, dump the object; subparts occuring multiple times are dumped
 131    -- in local variables, which can then be referenced multiple times;
 132    -- care is taken to dump local vars in an order which repect dependencies.
 133    -----------------------------------------------------------------------------
 134    function dump_val(x)
 135       local  t = type(x)
 136       if     x==nil        then return 'nil'
 137       elseif t=="number"   then return tostring(x)
 138       elseif t=="string"   then return string.format("%q", x)
 139       elseif t=="boolean"  then return x and "true" or "false"
 140       elseif t=="function" then
 141          return string.format ("loadstring(%q,'@serialized')", string.dump (x))
 142       elseif t=="table" then
 143
 144          local acc        = { }
 145          local idx_dumped = { }
 146          local np         = nest_points [x]
 147          for i, v in ipairs(x) do
 148             if np and np[v] then
 149                table.insert (acc, 'false') -- placeholder
 150             else
 151                table.insert (acc, dump_or_ref_val(v))
 152             end
 153             idx_dumped[i] = true
 154          end
 155          for k, v in pairs(x) do
 156             if np and (np[k] or np[v]) then
 157                --check_multiple(k); check_multiple(v) -- force dumps in localdefs
 158             elseif not idx_dumped[k] then
 159                table.insert (acc, "[" .. dump_or_ref_val(k) .. "] = " .. dump_or_ref_val(v))
 160             end
 161          end
 162          return "{ "..table.concat(acc,", ").." }"
 163       else
 164          error ("Can't serialize data of type "..t)
 165       end
 166    end
 167
 168    -- Patch the recursive table entries:
 169    local function dump_nest_patches()
 170       for _, entry in ipairs(nest_patches) do
 171          local p, k, v = unpack (entry)
 172          assert (multiple[p])
 173          local set = dump_or_ref_val (p) .. "[" .. dump_or_ref_val (k) .. "] = " ..
 174             dump_or_ref_val (v) .. " -- rec "
 175          table.insert (localdefs, set)
 176       end
 177    end
 178
 179    mark_multiple_occurences (x)
 180    local toplevel = dump_or_ref_val (x)
 181    dump_nest_patches()
 182
 183    if next (localdefs) then
 184       -- Dump local vars containing shared or recursive parts,
 185       -- then the main table using them.
 186       return "local _={ }\n" ..
 187          table.concat (localdefs, "\n") ..
 188          "\nreturn " .. toplevel
 189    else
 190       -- No shared part, straightforward dump:
 191       return "return " .. toplevel
 192    end
 193 end