Programming in Lua : 12.1.2

This first edition was written for Lua 5.0. While still largely relevant for later versions, there are some differences.
The fourth edition targets Lua 5.3 and is available at Amazon and other bookstores.
By buying the book, you also help to support the Lua project.

Programming in Lua

Part II. Tables and Objects Chapter 12. Data Files and Persistence

12.1.2 – Saving Tables with Cycles

To handle tables with generic topology (i.e., with cycles and shared sub-tables) we need a different approach. Constructors cannot represent such tables, so we will not use them. To represent cycles we need names, so our next function will get as arguments the value to be saved plus its name. Moreover, we must keep track of the names of the tables already saved, to reuse them when we detect a cycle. We will use an extra table for this tracking. This table will have tables as indices and their names as the associated values.

We will keep the restriction that the tables we want to save have only strings or numbers as keys. The following function serializes these basic types, returning the result:

    function basicSerialize (o)
      if type(o) == "number" then
        return tostring(o)
      else   -- assume it is a string
        return string.format("%q", o)
      end
    end

The next function does the hard work. The saved parameter is the table that keeps track of tables already saved:

    function save (name, value, saved)
      saved = saved or {}       -- initial value
      io.write(name, " = ")
      if type(value) == "number" or type(value) == "string" then
        io.write(basicSerialize(value), "\n")
      elseif type(value) == "table" then
        if saved[value] then    -- value already saved?
          io.write(saved[value], "\n")  -- use its previous name
        else
          saved[value] = name   -- save name for next time
          io.write("{}\n")     -- create a new table
          for k,v in pairs(value) do      -- save its fields
            local fieldname = string.format("%s[%s]", name,
                                            basicSerialize(k))
            save(fieldname, v, saved)
          end
        end
      else
        error("cannot save a " .. type(value))
      end
    end

As an example, if we build a table like

    a = {x=1, y=2; {3,4,5}}
    a[2] = a    -- cycle
    a.z = a[1]  -- shared sub-table

then the call save('a', a) will save it as follows:

    a = {}
    a[1] = {}
    a[1][1] = 3
    a[1][2] = 4
    a[1][3] = 5
    
    a[2] = a
    a["y"] = 2
    a["x"] = 1
    a["z"] = a[1]

(The actual order of these assignments may vary, as it depends on a table traversal. Nevertheless, the algorithm ensures that any previous node needed in a new definition is already defined.)

If we want to save several values with shared parts, we can make the calls to save using the same saved table. For instance, if we create the following two tables,

    a = {{"one", "two"}, 3}
    b = {k = a[1]}

and save them as follows,

    save('a', a)
    save('b', b)

the result will not have common parts:

    a = {}
    a[1] = {}
    a[1][1] = "one"
    a[1][2] = "two"
    a[2] = 3
    b = {}
    b["k"] = {}
    b["k"][1] = "one"
    b["k"][2] = "two"

However, if we use the same saved table for each call to save,

    local t = {}
    save('a', a, t)
    save('b', b, t)

then the result will share common parts:

    a = {}
    a[1] = {}
    a[1][1] = "one"
    a[1][2] = "two"
    a[2] = 3
    b = {}
    b["k"] = a[1]

As is usual in Lua, there are several other alternatives. Among them, we can save a value without giving it a global name (instead, the chunk builds a local value and returns it); we can handle functions (by building a table that associates each function to its name) etc. Lua gives you the power; you build the mechanisms.