Re: Proposal: Constant Tables (i.e. composed keys)
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: Proposal: Constant Tables (i.e. composed keys)
- From: Dirk Laurie <dpl@...>
- Date: 2011年8月14日 00:50:55 +0200
On Sat, Aug 13, 2011 at 06:56:48PM +0200, Lars Doelle wrote:
> No, Dirk, please reread my original post. It is all about tables and
> hashing. The problem is rather to use a composed key. How would
> you do that in LUA? This is what i talk about, and the concept of
> tables is clear lacking here, if you like it or not.
>
OK, just to show I'm not a troll, here is my attempt at implementing
such a feature.
~~~~ file immutable.lua
local ctab = {} -- table of constant tables
local function ctab_eq(t,s)
for k,v in pairs(t) do if s[k]~=v then return false end end
for k,v in pairs(s) do if t[k]~=v then return false end end
return true
end
local function ctab_put(hashkey,proxy)
-- called only when it is known that proxy is not in ctab
-- keeps a table of arrays that have the same hashkey
local found = ctab[hashkey]
if not found then ctab[hashkey]={proxy} return end
found[#found+1] = proxy
ctab[hashkey] = found
end
local function ctab_get(hashkey,rawtable)
local found = ctab[h]
if not found then return nil end
for _,p in ipairs(found) do
if ctab_eq(p,rawtable) then return p end end
end
local function is_mutable(t)
-- returns nil if t is not a table, false if t is immutable
if type(t)=='table' then
return getmetatable(t)==nil or getmetatable(t).__eq~=ctab_eq end
end
local function hash(t) -- details unimportant here
-- this particular function goes via an intermediate string
local h = 0
if type(t)~='table' then t=tostring(t) end
if type(t)=='string' then --
for n=1,#t do h=bit32.bxor(h,bit32.lshift(t:byte(n,n),5*((n-1)%7)))
end
return h
end
for k,v in pairs(t) do -- keys ignored for the purpose of hashing
if is_mutable(v) then
error('attempt to create constant table with mutable fields',3)
else v=tostring(v)
end
h = bit32.bxor(h,hash(v))
end
return h
end
local function immutable(t)
if not is_mutable(t) then return t end
local h = hash(t)
local known = ctab_get(h,t)
if known then return known end
-- see PiL §13.4
local proxy = {}
local mt = {
__index = t,
__eq = ctab_eq,
__pairs = function() return pairs(t) end,
__ipairs = function() return ipairs(t) end,
__newindex = function()
error("attempt to update a read-only table",2)
end
}
setmetatable(proxy,mt)
ctab_put(h,proxy)
return proxy
end
return immutable
~~~~
Use like this:
imm = require "immutable"
s = imm {n=3,1,2,3}
t = {1,2,3,4,n=4}
t[#t] = nil; t.n = t.n -1
print ( s == t ) --> false
print ( s == imm(t) ) --> true
Math = imm(math)
print (Math.pi) --> 3.1415926535898
Math.pi = 22/7 --> gives an error
Warning: The safe thing is to make immutable tables only from table
constants. If you have another reference to the table you are
making immutable, that reference is not also immutable.
math.pi = 22/7
print (Math.pi) --> 3.1428571428571
Dirk