lua 序列化（serialization） - 哆啦比猫的技术瞎扯 - Arch Linux · ドラえもん · 实时绘制
lua 序列化（serialization）
序
学习就是自己发明轮子的过程。lua 里序列化的库有很多（这里有一堆），要用的话可以直接选一个，但是一个成熟的库学习起来会有一定难度，所以干脆自己设计实现一个。
考虑比较常用的数据类型，以及实现的难度，决定实现以下类型的序列化：nil，number，string，boolean，table（with cycles 带环）。（带环的表其实挺常见的，像各种树结构，一般每个节点都要保存孩子和父亲）。
带环表的序列化思路
带环表的序列化其实是受 blender 启发的。在 blender 文件里，指针是直接当地址保存的，而每个数据结构的地址也都保存，这样就可以知到指针指向哪个数据了。在载入文件时指针会被重新指向正确的位置。
而在 lua 中，tostring 一个 table 可以得到类似于“table: 0xd2a550” 的字符串，后面那个“0xd2a550”就是这个表在内存中的地址。这样就可以效仿 blender 保存指针的方法了。
原子数据（atom）
不展开处理的数据称之为“原子数据”，之前提到的5种数据都可以作为原子数据。表，按照前面的思路，只保存地址，因此不会展开处理，故也可作为原子数据。当然，表也可以作为复合数据（compound），最终也肯定要以复合数据来处理。
原子数据序列化后为“类型+参数”的形式，不过 boolean 是例外，如：
- nil -> "nil"
- 13 -> "number13" （13 为数字内容）
- "13" -> "string2 13" （2 为字符串长度）
- {} -> "table0xd2a550" （0xd2a550 为表的地址）
- true -> "true"
- false -> "false"
正式点描述就是：
- nil -> "nil"
- number -> ("number%d"):format(number)
- string -> ("string%d %s"):format(string:len(), string)
- boolean -> tostring(boolean)
- table -> ("table%s"):format(tostring(table):match("0x%x+"))
复合数据（compound）
指的就是表啦，前面说过，表可以作为原子数据（只保存地址），也可作为复合数据（展开处理，即保存表里面的每一个键值对）。
作为复合数据的表 序列化后分为 头部 和 键值对组 两部分。头部为 ("%d %s\s"):format(count(table), tostring(table):match("0x%x+"))，其中的 count(table) 计算表中键值对个数，\s 表示任意空白符（包括空格、tab、换行，下同），如 "1 0xd2a550\n" 表示有一个键值对的表，表的地址为 0xd2a550；键值对组就是简单的 按原子数据序列化的键+"\s"+按原子数据序列化的值+"\s" 的重复。如：
1 0xd2a550 string1 a number1 string1 b true
最后的换行很重要（当然，换成空格或者 tab 也是可以的，只要是 “\s” 就行）
表的序列化
讲了那么多，表的序列化方法已经很清晰了：把表当作复合数据序列化，序列化过程中如果在键或者值中发现了表的话，做个标记，待所有键值对都当作原子数据序列化完之后，再把它当作复合数据序列化。重复着个过程就可以完成表的序列化。
完整的序列化
那么，不是表的数据要怎么序列化呢？所以，为了统一处理，不管数据是什么类型，直接丢到一个新的表里，再把这个新的表序列化。这样序列化的结果就一定会有一个只含一个数据的表，而且一定是出现在最前面。
完整的例子
例1
将 “hello, world!” 序列化将得到：
1 0x13deb50 number1 string13 hello, world!
例2
这样子创建表：
local a = {}
local b = {}
a.sub = b
b.parent = a
a.data = 10e30
b.next = "yes? no!"
local c = { childs = {a, b}, bool=false }
a.pa = c
b.pa = c
将表 c 序列化将得到：
1 0x13e3260 number1 table0x13ddb00 2 0x13ddb00 string4 bool false string6 childs table0x13ddbb0 2 0x13ddbb0 number1 table0x13e2c30 number2 table0x13e1930 3 0x13e2c30 string4 data number1e+31 string3 sub table0x13e1930 string2 pa table0x13ddb00 3 0x13e1930 string6 parent table0x13e2c30 string4 next string9 yes? no! string2 pa table0x13ddb00
序列化的实现
local atom = function(val)
local t = type(val)
if t == 'nil' then return t
elseif t == 'number' then return t..val
elseif t == 'string' then return ("%s%d %s"):format(t, val:len(), val)
elseif t == 'boolean' then return tostring(val)
elseif t == 'table' then return t .. tostring(val):match("0x%x+")
else error(("cannot atomify %s: %s"):format(t, tostring(val))) end
end
local count = function(tbl)
local n = 0
for _ in pairs(tbl) do n = n + 1 end
return n
end
stringify = function(ds)
local linear = {} -- 序列化后的线性数据
local pack = { ds } -- 说好的先打包
local todo = { [ pack ] = true } -- 将要序列化的表
local done = {} -- 已序列化的表，防止其被再次处理
while true do
local t = next(todo)
if t == nil then return table.concat(linear, "\n") .. "\n" end
todo[t] = nil
-- 序列化头部
local n = count(t)
local addr = tostring(t):match("0x%x+")
local c = { ("%d %s"):format(n, addr) }
done[t] = true
-- 序列化键值对组
for k,v in pairs(t) do
c[#c+1] = ("%s\t\t%s"):format(atom(k), atom(v))
if type(k) == 'table' and not done[k] then todo[k] = true end
if type(v) == 'table' and not done[v] then todo[v] = true end
end
linear[#linear+1] = table.concat(c, "\n") .. "\n"
end
end
解析（parse）
光序列化是不够的，序列化之后还要能还原成原来的数据。具体做法就是，按照复合数据解析每一个表，在解析键值对过程中，如果发现了作为原子数据的表，那就先键一个表，把地址保存在这个表中。
所有表就解析出来后，再对表的引用进行修正。
解析的实现
local atom = function(s, pos)
local t
t, pos = s:match("(%a+)()", pos)
if t == 'nil' then return nil, pos
elseif t == 'number' then
t, pos = s:match("(.-%s)()", pos)
return tonumber(t), pos
elseif t == 'string' then
t, pos = s:match("(.-%s)()", pos)
return s:sub(pos, pos+t-1), pos+t
elseif t == 'true' then return true, pos
elseif t == 'false' then return false, pos
elseif t == 'table' then
t, pos = s:match("(0x%x+)()", pos)
return { ref=t }, pos
else error(("cannot atomify: %s"):format(s:sub(pos))) end
end
local parsetable = function(s, pos)
local n, addr
n, addr, pos = s:match("(%d+) (0x%x+)()", pos)
if not n then return end
local t = {}
for i=1,n do
local k,v
k, pos = atom(s, pos)
v, pos = atom(s, pos)
t[k] = v
end
return addr, t, pos
end
S.parse = function(s)
local linear = {}
local pack
-- 先载入所有的表
local addr, t, pos
while true do
addr, t, pos = parsetable(s, pos)
if not addr then break end
linear[addr] = t
if not pack then pack = t end -- 第一个表是打包时创建的
end
-- 再修复引用
for _,t in pairs(linear) do
for k,v in pairs(t) do
if type(v) == 'table' then
v = linear[v.ref]
end
if type(k) == 'table' then
t[k] = nil
k = linear[k.ref]
end
t[k] = v
end
end
return pack[1] -- 既然打了包，自然得解开它
end
完整的实现
local S = {}
do
local atom = function(val)
local t = type(val)
if t == 'nil' then return t
elseif t == 'number' then return t..val
elseif t == 'string' then return ("%s%d %s"):format(t, val:len(), val)
elseif t == 'boolean' then return tostring(val)
elseif t == 'table' then return t .. tostring(val):match("0x%x+")
else error(("cannot atomify %s: %s"):format(t, tostring(val))) end
end
local count = function(tbl)
local n = 0
for _ in pairs(tbl) do n = n + 1 end
return n
end
S.stringify = function(ds)
local linear = {}
local pack = { ds }
local todo = { [ pack ] = true }
local done = {}
while true do
local t = next(todo)
if t == nil then return table.concat(linear, "\n") .. "\n" end
todo[t] = nil
local n = count(t)
local addr = tostring(t):match("0x%x+")
local c = { ("%d %s"):format(n, addr) }
done[t] = true
for k,v in pairs(t) do
c[#c+1] = ("%s\t\t%s"):format(atom(k), atom(v))
if type(k) == 'table' and not done[k] then todo[k] = true end
if type(v) == 'table' and not done[v] then todo[v] = true end
end
linear[#linear+1] = table.concat(c, "\n") .. "\n"
end
end
end
do
local atom = function(s, pos)
local t
t, pos = s:match("(%a+)()", pos)
if t == 'nil' then return nil, pos
elseif t == 'number' then
t, pos = s:match("(.-%s)()", pos)
return tonumber(t), pos
elseif t == 'string' then
t, pos = s:match("(.-%s)()", pos)
return s:sub(pos, pos+t-1), pos+t
elseif t == 'true' then return true, pos
elseif t == 'false' then return false, pos
elseif t == 'table' then
t, pos = s:match("(0x%x+)()", pos)
return { ref=t }, pos
else error(("cannot atomify: %s"):format(s:sub(pos))) end
end
local parsetable = function(s, pos)
local n, addr
n, addr, pos = s:match("(%d+) (0x%x+)()", pos)
if not n then return end
local t = {}
for i=1,n do
local k,v
k, pos = atom(s, pos)
v, pos = atom(s, pos)
t[k] = v
end
return addr, t, pos
end
S.parse = function(s)
local linear = {}
local pack
-- load all tables in
local addr, t, pos
while true do
addr, t, pos = parsetable(s, pos)
if not addr then break end
linear[addr] = t
if not pack then pack = t end
end
-- fix table refs
for _,t in pairs(linear) do
for k,v in pairs(t) do
if type(v) == 'table' then
v = linear[v.ref]
end
if type(k) == 'table' then
t[k] = nil
k = linear[k.ref]
end
t[k] = v
end
end
return pack[1]
end
end
return S
使用：
local S = require 'serializer'
local a = {}
local b = {}
a.sub = b
b.parent = a
a.data = 10e30
b.next = "yes? no!"
local c = { childs = {a, b}, bool=false }
a.pa = c
b.pa = c
local str = S.stringify(c)
print(str)
print(S.stringify(S.parse(str)))
print(S.stringify("hello, world!"))
输出：
1 0x1ba3310 number1 table0x1b9dbc0 2 0x1b9dbc0 string6 childs table0x1b9dc70 string4 bool false 2 0x1b9dc70 number1 table0x1ba2c30 number2 table0x1ba1930 3 0x1ba2c30 string2 pa table0x1b9dbc0 string3 sub table0x1ba1930 string4 data number1e+31 3 0x1ba1930 string2 pa table0x1b9dbc0 string4 next string9 yes? no! string6 parent table0x1ba2c30 1 0x1b9cb70 number1 table0x1b9cd80 2 0x1b9cd80 string6 childs table0x1ba4c70 string4 bool false 2 0x1ba4c70 number1 table0x1ba4ea0 number2 table0x1ba5130 3 0x1ba4ea0 string2 pa table0x1b9cd80 string3 sub table0x1ba5130 string4 data number1e+31 3 0x1ba5130 string2 pa table0x1b9cd80 string4 next string9 yes? no! string6 parent table0x1ba4ea0 1 0x1b9d6a0 number1 string13 hello, world!
凡未特殊声明（转载/翻译），所有文章均为原创。
by Giumo Xavier Clanjor (哆啦比猫/兰威举), 2010-2019.
本作品采用知识共享署名·非商业性使用·相同方式共享 3.0 中国大陆许可协议进行许可。
文中凡未特殊声明且未声明为引用的代码均以 MIT 协议授权。
blog comments powered by Disqus