A read only struct value type for Lua

struct.lua

--[[
An immutable structure-like value type for Lua.

 Sean Heber ([email protected])
 BSD License
 July, 2017
 Written on an iPad using Codea (https://codea.io)

I’m pretty new to Lua, but I kept running into situations where I wanted to use a complex value type
such as a Point as a key in a table. Unfortunately since each table instance is unique, using a table
as a key in another table does not do what I wanted. For example:

local key1 = {x=1, y=2}
local key2 = {x=1, y=2}
uniqueThings = {}
uniqueThings[key1] = 10
uniqueThings[key2] = 42

The uniqueThings table ends up with two entries even though, at first glance, it might seem like it
should just have one - after all, key1 and key2 are seemingly the same value! 

But of course Lua doesn’t work this way...

In a (perhaps misguided) attempt to make it work this way in Lua, I’ve created an implementation of
a "new" type called "struct". The basic idea is that whenever you create a new instance of a struct,
that instance is made unique and only a single instance of the data is stored and referenced. This
means that from Lua’s point of view, you are just referencing the same single instance over and
over. This allows us to safely use struct instances as keys in other Lua tables.

The struct instances themselves are made "immutable" as best as I could figure out how - otherwise
this would all break down very badly. The unique instances are also stored weakly so they don’t
use up all of your RAM.

Each struct type that you create must have a hash() and eq() function defined for it.

The eq(self, other) function must return true when all properties of self and other are the same.

The hash(self) function must return a number which is suitable as a hash for the given structure.
It is important that eq() and hash() both use the same properties when computing their results!

Optionally an init() function can be defined which is called when a new instance of your struct is
created. Once the init() function has finished, you should not be able to mutate the properties of
your struct’s instances.

If you give the struct() function a list of parameter names that will define the struct, then you
get init(), hash(), eq(), and a mutate() functions generated automatically. Of course you may be able
to get better performance by implementing your own versions which know more about your use-cases,
but the defaults should be good enough to get started.


Examples:

-- create a new "type" named Point with properties named "x" and "y"!
Point = struct{"x", "y"}

local p1 = Point(1, 2)
assert(p1.x == 1)   -- true!
assert(p1.y == 2)   -- true!
p1.x = 42    -- error!

local p2 = Point(1, 2)
assert(p1 == p2)   -- true!

-- use the auto-genertated mutate() function to create a new copy with some changes!
local p3 = p2:mutate{x=100}
assert(p3.x == 100)   -- true!
assert(p3.y == 2)   -- true!

local p4 = Point()
assert(p4.x == nil)   -- true!
assert(p4.y == nil)   -- true!


-- define a structure with default values!
Size = struct({"width", "height"}, 1, 7)
local s1 = Size()
assert(s1.width == 1)   -- true!
assert(s1.height == 7)   -- true!


-- make a totally custom structure with your own init(), eq(), hash() functions!
Custom = struct()

function Custom:init(v)
    self.value = v
end

function Custom:hash()
    return v
end

function Custom:eq(other)
    return other.v == self.v
end


-- use a hybrid approach!
Hybrid = struct{"field1", "field2"}
function Hybrid:hash()
    return self.field1 * self.field2
end

  ]]


local storage = {}

local function readonly(T, self)
    assert(false, "struct is readonly")
end

local function missingHash(T, self)
    assert(false, "struct is missing function: hash")
end

local function missingEq(T, self, other)
    assert(false, "struct is missing function: eq")
end

local function missingMutate(T, self, changes)
    assert(false, "struct is missing function: mutate")
end

-- borrowed from http://wowwiki.wikia.com/wiki/StringHash
local function stringHash(str)
    local len = string.len(str)
    local counter = 1
    for i = 1, len, 3 do 
        counter = math.fmod(counter*8161, 4294967279) +  -- 2^32 - 17: Prime!
  	     (string.byte(str,i)*16776193) +
  	     ((string.byte(str,i+1) or (len-i+256))*8372226) +
  	     ((string.byte(str,i+2) or (len-i+256))*3932164)
    end
    return math.fmod(counter, 4294967291) -- 2^32 - 5: Prime (and different from the prime in the loop)
end

local function initializeValue(T, ...)
    local value = {}
    
    if T.init then
        T.init(value, ...)
    end
    
    local hash = T.hash(value)

    if not storage[T] then
        storage[T] = {}
    end

    local bucket = storage[T][hash]
    local instance = nil
    
    -- if needed, create a new bucket to weakly store the unique instances of this value type
    if not bucket then
        bucket = setmetatable({}, {__mode = "v"})
        storage[T][hash] = bucket
    else
        for _,obj in pairs(bucket) do
            if T.eq(value, obj) then
                instance = obj
                break
            end
        end
    end
    
    if not instance then
        instance = setmetatable({}, {
            __newindex = readonly,
            __len = function()
                return #value
            end,
            __index = function(self, key)
                return value[key] or T[key]
            end,
            __tostring = T.__tostring,
        })
        
        table.insert(bucket, instance)
    end
    
    return instance
end

function struct(properties, ...)
    local T = {init = nil, hash = missingHash, eq = missingEq, mutate = missingMutate}
    local defaults = {...}
    
    if properties and #properties > 0 then
        T.init = function(self, ...)
            local args = {...}
            assert(#args <= #properties, "too many arguments")
            
            for i,prop in ipairs(properties) do
                self[prop] = args[i] or defaults[i]
            end
        end
        
        T.eq = function(self, other)
            for _,prop in pairs(properties) do
                if self[prop] ~= other[prop] then
                    return false
                end
            end
            return true
        end
        
        T.hash = function(self)
            local propertyValues = {}
            
            for i,prop in ipairs(properties) do
                table.insert(propertyValues, i, tostring(self[prop]))
            end
            
            return stringHash(table.concat(propertyValues))
        end
        
        T.__tostring = function(self)
            local parts = {}
            for i,prop in ipairs(properties) do
                table.insert(parts, prop .. "=" .. tostring(self[prop]))
            end
            return "{" .. table.concat(parts, ", ") .. "}"
        end
        
        T.mutate = function(self, changes)
            local values = {}
            for i,prop in ipairs(properties) do
                table.insert(values, i, changes[prop] or self[prop])
            end
            return initializeValue(T, unpack(values))
        end
    end
    
    return setmetatable(T, {
        __call = initializeValue,
    })
end

-- debug
function structInstances()
    local data = {}
   
    for _,typeBuckets in pairs(storage) do
        for _,bucket in pairs(typeBuckets) do
            for _, value in pairs(bucket) do
                table.insert(data, value)
            end
        end
    end
    
    return data
end