lua 序列化(serialization) - 哆啦比猫's Blog - I'm an ArchLinuxer

lua 序列化(serialization)

哆啦比猫 posted @ 2014年3月23日 00:01 in coding with tags Lua serialization cycle , 4509 阅读

学习就是自己发明轮子的过程。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, 2011, 2012, 2013, 2014, 2015-2016 and 2017.
知识共享许可协议本作品采用知识共享署名·非商业性使用·相同方式共享 3.0 中国大陆许可协议进行许可。
文中凡未特殊声明且未声明为引用的代码均以 MIT 协议授权。

blog comments powered by Disqus
© 2010, 2011, 2012, 2013, 2014, 2015-2016 and 2017 Giumo Xavier Clanjor (哆啦比猫/兰威举).
© 2013, 2014, 2015-2016 and 2017 The Dark Colorscheme Designed by Giumo Xavier Clanjor (哆啦比猫/兰威举).
知识共享署名·非商业性使用·相同方式共享 3.0 中国大陆许可协议
| © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee