#### Howdy, Stranger!

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

# Struct

Posts: 35

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: https://gist.github.com/BigZaphod/0a3a95807f653b64f6eacbc1ae740ca6 And to make things easy here, I’ve pasted it below:

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

Sean Heber (sean@fifthace.com)
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

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
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 = {}

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({}, {
__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

``````