src/lib/serialize.lua

   1 --------------------------------------------------------------------------------
   2 -- Serialize an object into a source code string. This string, when passed as
   3 -- an argument to loadstring()(), returns an object structurally identical
   4 -- to the original one. The following are currently supported:
   5 -- * strings, numbers, booleans, nil
   6 -- * functions without upvalues
   7 -- * tables thereof. Tables can have shared part, but can't be recursive yet.
   8 -- Caveat: metatables and environments aren't saved.
   9 --------------------------------------------------------------------------------
  10
  11 local no_identity = { number=1, boolean=1, string=1, ['nil']=1 }
  12
  13 function serialize (x)
  14
  15    local gensym_max =  0  -- index of the gensym() symbol generator
  16    local seen_once  = { } -- element->true set of elements seen exactly once in the table
  17    local multiple   = { } -- element->varname set of elements seen more than once
  18    local nested     = { } -- transient, set of elements currently being traversed
  19    local nest_points = { }
  20    local nest_patches = { }
  21
  22    local function gensym()
  23       gensym_max = gensym_max + 1 ;  return gensym_max
  24    end
  25
  26    -----------------------------------------------------------------------------
  27    -- nest_points are places where a table appears within itself, directly or not.
  28    -- for instance, all of these chunks create nest points in table x:
  29    -- "x = { }; x[x] = 1", "x = { }; x[1] = x", "x = { }; x[1] = { y = { x } }".
  30    -- To handle those, two tables are created by mark_nest_point:
  31    -- * nest_points [parent] associates all keys and values in table parent which
  32    --   create a nest_point with boolean `true'
  33    -- * nest_patches contain a list of { parent, key, value } tuples creating
  34    --   a nest point. They're all dumped after all the other table operations
  35    --   have been performed.
  36    --
  37    -- mark_nest_point (p, k, v) fills tables nest_points and nest_patches with
  38    -- informations required to remember that key/value (k,v) create a nest point
  39    -- in table parent. It also marks `parent' as occuring multiple times, since
  40    -- several references to it will be required in order to patch the nest
  41    -- points.
  42    -----------------------------------------------------------------------------
  43    local function mark_nest_point (parent, k, v)
  44       local nk, nv = nested[k], nested[v]
  45       assert (not nk or seen_once[k] or multiple[k])
  46       assert (not nv or seen_once[v] or multiple[v])
  47       local mode = (nk and nv and "kv") or (nk and "k") or ("v")
  48       local parent_np = nest_points [parent]
  49       local pair = { k, v }
  50       if not parent_np then parent_np = { }; nest_points [parent] = parent_np end
  51       parent_np [k], parent_np [v] = nk, nv
  52       table.insert (nest_patches, { parent, k, v })
  53       seen_once [parent], multiple [parent]  = nil, true
  54    end
  55
  56    -----------------------------------------------------------------------------
  57    -- First pass, list the tables and functions which appear more than once in x
  58    -----------------------------------------------------------------------------
  59    local function mark_multiple_occurences (x)
  60       if no_identity [type(x)] then return end
  61       if     seen_once [x]     then seen_once [x], multiple [x] = nil, true
  62       elseif multiple  [x]     then -- pass
  63       else   seen_once [x] = true end
  64
  65       if type (x) == 'table' then
  66          nested [x] = true
  67          for k, v in pairs (x) do
  68             if nested[k] or nested[v] then mark_nest_point (x, k, v) else
  69                mark_multiple_occurences (k)
  70                mark_multiple_occurences (v)
  71             end
  72          end
  73          nested [x] = nil
  74       end
  75    end
  76
  77    local dumped    = { } -- multiply occuring values already dumped in localdefs
  78    local localdefs = { } -- already dumped local definitions as source code lines
  79
  80
  81    -- mutually recursive functions:
  82    local dump_val, dump_or_ref_val
  83
  84    --------------------------------------------------------------------
  85    -- if x occurs multiple times, dump the local var rather than the
  86    -- value. If it's the first time it's dumped, also dump the content
  87    -- in localdefs.
  88    --------------------------------------------------------------------
  89    function dump_or_ref_val (x)
  90       if nested[x] then return 'false' end -- placeholder for recursive reference
  91       if not multiple[x] then return dump_val (x) end
  92       local var = dumped [x]
  93       if var then return "_[" .. var .. "]" end -- already referenced
  94       local val = dump_val(x) -- first occurence, create and register reference
  95       var = gensym()
  96       table.insert(localdefs, "_["..var.."]="..val)
  97       dumped [x] = var
  98       return "_[" .. var .. "]"
  99    end
 100
 101    -----------------------------------------------------------------------------
 102    -- Second pass, dump the object; subparts occuring multiple times are dumped
 103    -- in local variables which can be referenced multiple times;
 104    -- care is taken to dump locla vars in asensible order.
 105    -----------------------------------------------------------------------------
 106    function dump_val(x)
 107       local  t = type(x)
 108       if     x==nil        then return 'nil'
 109       elseif t=="number"   then return tostring(x)
 110       elseif t=="string"   then return string.format("%q", x)
 111       elseif t=="boolean"  then return x and "true" or "false"
 112       elseif t=="function" then
 113          return string.format ("loadstring(%q,'@serialized')", string.dump (x))
 114       elseif t=="table" then
 115
 116          local acc        = { }
 117          local idx_dumped = { }
 118          local np         = nest_points [x]
 119          for i, v in ipairs(x) do
 120             if np and np[v] then
 121                table.insert (acc, 'false') -- placeholder
 122             else
 123                table.insert (acc, dump_or_ref_val(v))
 124             end
 125             idx_dumped[i] = true
 126          end
 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))
 132             end
 133          end
 134          return "{ "..table.concat(acc,", ").." }"
 135       else
 136          error ("Can't serialize data of type "..t)
 137       end
 138    end
 139
 140    local function dump_nest_patches()
 141       for _, entry in ipairs(nest_patches) do
 142          local p, k, v = unpack (entry)
 143          assert (multiple[p])
 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)
 147       end
 148    end
 149
 150    mark_multiple_occurences (x)
 151    local toplevel = dump_or_ref_val (x)
 152    dump_nest_patches()
 153
 154    if next (localdefs) then
 155       return "local _={ }\n" ..
 156          table.concat (localdefs, "\n") ..
 157          "\nreturn " .. toplevel
 158    else
 159       return "return " .. toplevel
 160    end
 161 end