Come posso confrontare in profondità 2 tabelle Lua, che possono avere o meno tabelle come chiavi?

Question

(pubblicato anche sulla mailing list Lua)

Così ho scritto algoritmi di deep-copy e voglio testarli per vedere se funzionano nel modo in cui li voglio. Mentre ho accesso alla mappa originale-> copia, voglio un algoritmo di confronto approfondito per uso generico che deve essere in grado di confrontare i tasti della tabella (tabelle come chiavi?).

I miei algoritmi di deep-copy sono disponibili qui: https://gist.github.com/SoniEx2/fc5d3614614e4e3fe131 (non è molto organizzato, ma ce ne sono 3, uno usa le chiamate ricorsive, l'altro usa una tabella di todo e l'altro simula uno stack di chiamate (in un modo molto brutto ma compatibile-5,1))

versione ricorsiva:

local function deep(inp,copies) 
    if type(inp) ~= "table" then 
    return inp 
    end 
    local out = {} 
    copies = (type(copies) == "table") and copies or {} 
    copies[inp] = out -- use normal assignment so we use copies' metatable (if any) 
    for key,value in next,inp do -- skip metatables by using next directly 
    -- we want a copy of the key and the value 
    -- if one is not available on the copies table, we have to make one 
    -- we can't do normal assignment here because metatabled copies tables might set metatables 

    -- out[copies[key] or deep(key,copies)]=copies[value] or deep(value,copies) 
    rawset(out,copies[key] or deep(key,copies),copies[value] or deep(value,copies)) 
    end 
    return out 
end 

Edit: ho trovato cose come questa, che in realtà non gestiscono le tabelle come chiavi: http://snippets.luacode.org/snippets/Deep_Comparison_of_Two_Values_3 (copia del frammento qui sotto)

function deepcompare(t1,t2,ignore_mt) 
    local ty1 = type(t1) 
    local ty2 = type(t2) 
    if ty1 ~= ty2 then return false end 
    -- non-table types can be directly compared 
    if ty1 ~= 'table' and ty2 ~= 'table' then return t1 == t2 end 
    -- as well as tables which have the metamethod __eq 
    local mt = getmetatable(t1) 
    if not ignore_mt and mt and mt.__eq then return t1 == t2 end 
    for k1,v1 in pairs(t1) do 
    local v2 = t2[k1] 
    if v2 == nil or not deepcompare(v1,v2) then return false end 
    end 
    for k2,v2 in pairs(t2) do 
    local v1 = t1[k2] 
    if v1 == nil or not deepcompare(v1,v2) then return false end 
    end 
    return true 
end 

Anche la serializzazione non è un'opzione, in quanto l'ordine di serializzazione è "casuale".

Answer 1

Come altri hanno detto, dipende molto dalla definizione di equivalenza. Se si desidera che questo per essere vero:

local t1 = {[{}] = {1}, [{}] = {2}} 
local t2 = {[{}] = {1}, [{}] = {2}} 
assert(table_eq(t1, t2)) 

Se lo fai, allora ogni volta che la chiave nel T1 è una tabella, dovrete verificare l'equivalenza con ogni chiave tavola in T2 e provare uno di loro per uno. Questo è un modo per farlo (materiale apprezzabile lasciato fuori per la leggibilità).

function table_eq(table1, table2) 
    local avoid_loops = {} 
    local function recurse(t1, t2) 
     -- compare value types 
     if type(t1) ~= type(t2) then return false end 
     -- Base case: compare simple values 
     if type(t1) ~= "table" then return t1 == t2 end 
     -- Now, on to tables. 
     -- First, let's avoid looping forever. 
     if avoid_loops[t1] then return avoid_loops[t1] == t2 end 
     avoid_loops[t1] = t2 
     -- Copy keys from t2 
     local t2keys = {} 
     local t2tablekeys = {} 
     for k, _ in pairs(t2) do 
     if type(k) == "table" then table.insert(t2tablekeys, k) end 
     t2keys[k] = true 
     end 
     -- Let's iterate keys from t1 
     for k1, v1 in pairs(t1) do 
     local v2 = t2[k1] 
     if type(k1) == "table" then 
      -- if key is a table, we need to find an equivalent one. 
      local ok = false 
      for i, tk in ipairs(t2tablekeys) do 
       if table_eq(k1, tk) and recurse(v1, t2[tk]) then 
        table.remove(t2tablekeys, i) 
        t2keys[tk] = nil 
        ok = true 
        break 
       end 
      end 
      if not ok then return false end 
     else 
      -- t1 has a key which t2 doesn't have, fail. 
      if v2 == nil then return false end 
      t2keys[k1] = nil 
      if not recurse(v1, v2) then return false end 
     end 
     end 
     -- if t2 has a key which t1 doesn't have, fail. 
     if next(t2keys) then return false end 
     return true 
    end 
    return recurse(table1, table2) 
end 

assert(table_eq({}, {})) 
assert(table_eq({1,2,3}, {1,2,3})) 
assert(table_eq({1,2,3, foo = "fighters"}, {["foo"] = "fighters", 1,2,3})) 
assert(table_eq({{{}}}, {{{}}})) 
assert(table_eq({[{}] = {1}, [{}] = {2}}, {[{}] = {1}, [{}] = {2}})) 
assert(table_eq({a = 1, [{}] = {}}, {[{}] = {}, a = 1})) 
assert(table_eq({a = 1, [{}] = {1}, [{}] = {2}}, {[{}] = {2}, a = 1, [{}] = {1}})) 

assert(not table_eq({1,2,3,4}, {1,2,3})) 
assert(not table_eq({1,2,3, foo = "fighters"}, {["foo"] = "bar", 1,2,3})) 
assert(not table_eq({{{}}}, {{{{}}}})) 
assert(not table_eq({[{}] = {1}, [{}] = {2}}, {[{}] = {1}, [{}] = {2}, [{}] = {3}})) 
assert(not table_eq({[{}] = {1}, [{}] = {2}}, {[{}] = {1}, [{}] = {3}})) 

Answer 2

Invece del confronto diretto, è possibile provare a serializzare ciascuna tabella e confrontare i risultati serializzati. Esistono diversi serializzatori che gestiscono la tabella come chiavi e possono serializzare strutture profonde e ricorsive. Ad esempio, si può provare a Serpent (disponibile come modulo autonomo e anche incluso nel Mobdebug):

local dump = pcall(require, 'serpent') and require('serpent').dump 
    or pcall(require, 'mobdebug') and require('mobdebug').dump 
    or error("can't find serpent or mobdebug") 
local a = dump({a = 1, [{}] = {}}) 
local b = dump({[{}] = {}, a = 1}) 
print(a==b) 

Questo restituisce true per me (sia Lua Lua 5.1 e 5.2). Una delle avvertenze è che il risultato della serializzazione dipende dall'ordine in cui le chiavi sono serializzate. Le tabelle come chiave di default vengono ordinati in base al loro valore tostring, il che significa che l'ordine dipende dalla loro indirizzo di assegnazione e non è difficile trovare un esempio che fallisce sotto Lua 5.2:

local dump = pcall(require, 'serpent') and require('serpent').dump 
    or pcall(require, 'mobdebug') and require('mobdebug').dump 
    or error("can't find serpent or mobdebug") 
local a = dump({a = 1, [{}] = {1}, [{}] = {2}}) 
local b = dump({[{}] = {2}, a = 1, [{}] = {1}}) 
print(a==b) --<-- `false` under Lua 5.2 

Un modo per proteggersi da questo è rappresentare coerentemente le tabelle nel confronto delle chiavi; ad esempio, invece del valore predefinito , potresti voler serializzare le tabelle e i relativi valori e ordinare le chiavi in ​​base a quello (serpent consente un custom handler for sortkeys), che renderebbe l'ordinamento più robusto ei risultati serializzati più stabili.