(52 lines)

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

   1 # Implementation details
   2 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:
   3 ```lua
   4 local metamethods = {
   5     __index = function(self, key)
   6         local cls = getmetatable(self)
   7         local values = cls.__instances[cls.__hash(self)][self]
   8         if cls.__indices[key] then
   9             return values[cls.__indices[key]]
  10         elseif type(key) == 'number' and 1 <= key and key <= #values - #cls.__fields then
  11             return values[key - #cls.__fields]
  12         else
  13             return cls[key]
  14         end
  15     end,
  16     ...also: __len, __pairs, __ipairs, __tostring, from_table, is_instance...
  17 }
  18 function immutable(fields, class_fields)
  19     local cls = {}
  20     for k,v in pairs(metamethods) do cls[k] = v end
  21     cls.__super = metamethods
  22     for k,v in pairs(class_fields) do cls[k] = v end
  23     cls.__fields, cls.__indices = fields, {}
  24     for i,f in ipairs(fields) do cls.__indices[f] = i end
  25     cls.__instances = setmetatable({}, {__mode='v', __index=function(self, key)
  26         local bucket = setmetatable({}, {__mode='k'})
  27         self[key] = bucket
  28         return bucket
  29     end})
  30     cls.__buckets = setmetatable({}, {__mode='k'})
  31     return setmetatable(cls, {
  32         __call=function(cls, ...)
  33             local hash = calculate_hash(...)
  34             local bucket = cls.__instances[hash]
  35             for userdata, data in pairs(bucket) do
  36                 local match = true
  37                 for i=1,select('#',...) do
  38                     if data[i] ~= select(i, ...) then
  39                         match = false
  40                         break
  41                     end
  42                 end
  43                 if match then return userdata end
  44             end
  45             local userdata = setmetatable(new_userdata(hash), cls)
  46             cls.__buckets[userdata] = bucket
  47             bucket[userdata] = {...}
  48             return userdata
  49         end
  50     })
  51 end
  52 ```