lua-immutable/implementation.md

Implementation details

Under the hood, immutable tables are implemented in C as a userdata (that stores a hash value and length) with a metatable. That metatable has a weak-keyed mapping from hash -> userdata -> associated data. Immutable tables are garbage collected, so if you no longer have any references to the userdata, the userdata will get garbage collected, which will result in the entry being removed from the metatable's mapping. When new instances are created, a hash value is computed, and all the data in the associated hash bucket is scanned to look for duplicates. If a match is found, the existing instance is returned, otherwise a new one is created and added to the hash bucket. The following lua pseudocode approximates the C implementation's behavior:

local metamethods = {
    __index = function(self, key)
        local cls = getmetatable(self)
        local values = cls.__instances[cls.__hash(self)][self]
        if cls.__indices[key] then
            return values[cls.__indices[key]]
        elseif type(key) == 'number' and 1 <= key and key <= #values - #cls.__fields then
            return values[key - #cls.__fields]
        else
            return cls[key]
        end
    end,
    ...also: __len, __pairs, __ipairs, __tostring, from_table, is_instance...
}
function immutable(fields, class_fields)
    local cls = {}
    for k,v in pairs(metamethods) do cls[k] = v end
    cls.__super = metamethods
    for k,v in pairs(class_fields) do cls[k] = v end
    cls.__fields, cls.__indices = fields, {}
    for i,f in ipairs(fields) do cls.__indices[f] = i end
    cls.__instances = setmetatable({}, {__mode='v', __index=function(self, key)
        local bucket = setmetatable({}, {__mode='k'})
        self[key] = bucket
        return bucket
    end})
    cls.__buckets = setmetatable({}, {__mode='k'})
    return setmetatable(cls, {
        __call=function(cls, ...)
            local hash = calculate_hash(...)
            local bucket = cls.__instances[hash]
            for userdata, data in pairs(bucket) do
                local match = true
                for i=1,select('#',...) do
                    if data[i] ~= select(i, ...) then
                        match = false
                        break
                    end
                end
                if match then return userdata end
            end
            local userdata = setmetatable(new_userdata(hash), cls)
            cls.__buckets[userdata] = bucket
            bucket[userdata] = {...}
            return userdata
        end
    })
end