在游戏中replay是个必不可少的功能，无论是玩家的需求还是对开发和调试的帮助。但是lua的官方实现并不能很好地支持replay的实现。

replay的关键在于所有行为都是确定且可重现的。对于随机函数math.random很简单，lua提供了设置随机种子的函数math.randomseed，相同的随机种子总是产生相同的随机序列，我们只需要保证replay使用了相同的随机种子即可。

但是lua还有一个随机行为，考虑以下代码 

1
2
3
4
5
6
7
 
local t = {
    a = 0, b = 1, c = 2, d = 3, e = 4,
    f = 5, g = 6, h = 7, i = 8, j = 9,
}
for k, v in pairs(t) do
    print(k, v)
end

你会发现每次的输出都是不一样的。lua遍历表的次序取决于key的hash值，而lua的很多数据类型的hash都是随机的，这包括了string、table、userdata等。而且它并不取决于math.randomseed指定的随机种子，所以不能很简单地解决它。

重写pairs函数？

既然pair有随机性，那么我们来写一个没有随机性pairs吧。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
local function sortpairs(t)
    local sort = {}
    for k, v in pairs(t) do
        sort[#sort+1] = {k, v}
    end
    table.sort(sort, function (a, b)
        return a[1] < b[1]
    end)
    local n = 1
    return function()
        local v = sort[n]
        if not v then
            return
        end
        n = n + 1
        return v[1], v[2]
    end
end
local t = {
    a = 0, b = 1, c = 2, d = 3, e = 4,
    f = 5, g = 6, h = 7, i = 8, j = 9,
}
for k, v in sortpairs(t) do
    print(k, v)
end

这是一个根据key排序次序遍历的pairs，但是这个pairs也有几个问题

  • 需要遍历两次表加上一次排序，效率低。

  • 现在的输出是a、b、c、d…，但我更希望是看起来是随机的次序，这样行为看起来会和原版的pairs更像。这就需要在排序比较函数里加上一个hash函数。然而由于lua无法高效地访问字符串，所以如果hash函数不用c实现的话，效率低得可怕。 

    1
    2
    3
    		 
    table.sort(sort, function (a, b)
        return hash(a[1]) < hash(b[1])
    end)

  • hash函数需要保证没有冲突。由于第一次遍历是随机的，所以两个hash值相同的项遍历的次序也是随机的。

  • userdata、table等数据类型的支持。

    • 重写lua的hash函数

    其实lua的table在插入时，就做了类似我们上面sortpairs所做的事情，对key取hash然后排序插入表，pairs所做的就是按次序遍历了一遍排序的结果。只是lua的这个hash函数带有随机性，所以才让pairs带有随机性。lua的hash函数在ltable.c中 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    		 
    static Node *mainposition (const Table *t, const TValue *key) {
      switch (ttype(key)) {
        case LUA_TNUMINT:
          return hashint(t, ivalue(key));
        case LUA_TNUMFLT:
          return hashmod(t, l_hashfloat(fltvalue(key)));
        case LUA_TSHRSTR:
          return hashstr(t, tsvalue(key));
        case LUA_TLNGSTR:
          return hashpow2(t, luaS_hashlongstr(tsvalue(key)));
        case LUA_TBOOLEAN:
          return hashboolean(t, bvalue(key));
        case LUA_TLIGHTUSERDATA:
          return hashpointer(t, pvalue(key));
        case LUA_TLCF:
          return hashpointer(t, fvalue(key));
        default:
          lua_assert(!ttisdeadkey(key));
          return hashpointer(t, gcvalue(key));
      }
    }

    这里面有随机性的是LUA_TSHRSTR、LUA_TLNGSTR、LUA_TLIGHTUSERDATA、LUA_TLCF和default。

    遍历string key

    先说字符串，字符串在计算hash时引入了一个随机种子，这个随机种子和math.randomseed不一样，在lstate.c里的lua_newstate初始化。 

    1
    2
    3
    4
    5
    6
    7
    8
    		 
    LUA_API lua_State *lua_newstate (lua_Alloc f, void *ud) {
      int i;
      lua_State *L;
    ...
      g->mainthread = L;
      g->seed = makeseed(L);
      g->gcrunning = 0;  /* no GC while building state */
    ...
    		 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    		 
    static unsigned int makeseed (lua_State *L) {
      char buff[4 * sizeof(size_t)];
      unsigned int h = luai_makeseed();
      int p = 0;
      addbuff(buff, p, L);  /* heap variable */
      addbuff(buff, p, &h);  /* local variable */
      addbuff(buff, p, luaO_nilobject);  /* global variable */
      addbuff(buff, p, &lua_newstate);  /* public function */
      lua_assert(p == sizeof(buff));
      return luaS_hash(buff, p, h);
    }

    为了保证这个随机种子的随机性，lua引入了多种随机变量来保证随机性。所以最好的办法就是重写makeseed，或者把随机种子从lua_newstate的参数传入。因为lua_newstate只需要在lua_State初始化时调用一次，所以随机种子从lua_newstate的参数传入是个不错的方案。

    这样我们就可以通过传入的随机种子来改变pairs遍历字符串key时的次序了。

    遍历userdata key

    hash的关键在于相同的值，总是能得到相同的结果。由于lua不知道userdat的d具体含义，无法和string那样根据值来计算hash。不过值得庆幸的是lua里同一个userdata只有一个副本，所以我们只需要在userdata初始化时给它一个全局唯一的ID，就可以作为它的hash值了。

    首先要修改userdata的数据结构，加一个hash值，这个在lobject.h中 

    1
    2
    3
    4
    5
    		 
    /*
    ** Common Header for all collectable objects (in macro form, to be
    ** included in other objects)
    */
    #define CommonHeader	GCObject *next; lu_byte tt; lu_byte marked

    然后在初始化时，给一个全局唯一的ID。 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    		 
    GCObject *luaC_newobj (lua_State *L, int tt, size_t sz) {
      global_State *g = G(L);
      GCObject *o = cast(GCObject *, luaM_newobject(L, novariant(tt), sz));
      o->marked = luaC_white(g);
      o->tt = tt;
      o->next = g->allgc;
      g->allgc = o;
      return o;
    }