Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!


This might be somewhat crazy, but I wrote a read only value type “struct” implementation in Lua. The idea was that this could allow me to make a Point struct and then use different instances of the same values as keys in a table and have it work the way I expected. I’ve posted the code on Github: And to make things easy here, I’ve pasted it below:

An immutable structure-like value type for Lua.

 Sean Heber (
 BSD License
 July, 2017
 Written on an iPad using Codea (

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.


-- 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

function Custom:hash()
    return v

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

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


local storage = {}

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

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

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

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

-- borrowed from
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)
    return math.fmod(counter, 4294967291) -- 2^32 - 5: Prime (and different from the prime in the loop)

local function initializeValue(T, ...)
    local value = {}

    if T.init then
        T.init(value, ...)

    local hash = T.hash(value)

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

    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
        for _,obj in pairs(bucket) do
            if T.eq(value, obj) then
                instance = obj

    if not instance then
        instance = setmetatable({}, {
            __newindex = readonly,
            __len = function()
                return #value
            __index = function(self, key)
                return value[key] or T[key]
            __tostring = T.__tostring,

        table.insert(bucket, instance)

    return instance

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]

        T.eq = function(self, other)
            for _,prop in pairs(properties) do
                if self[prop] ~= other[prop] then
                    return false
            return true

        T.hash = function(self)
            local propertyValues = {}

            for i,prop in ipairs(properties) do
                table.insert(propertyValues, i, tostring(self[prop]))

            return stringHash(table.concat(propertyValues))

        T.__tostring = function(self)
            local parts = {}
            for i,prop in ipairs(properties) do
                table.insert(parts, prop .. "=" .. tostring(self[prop]))
            return "{" .. table.concat(parts, ", ") .. "}"

        T.mutate = function(self, changes)
            local values = {}
            for i,prop in ipairs(properties) do
                table.insert(values, i, changes[prop] or self[prop])
            return initializeValue(T, unpack(values))

    return setmetatable(T, {
        __call = initializeValue,

-- 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)

    return data

Sign In or Register to comment.