Technical Note 8

A fast multiple-inheritance tag method implementation in Lua

Abstract

The Problem

The Solution

The non-caching implementation is rather simple. It uses a _parents = {} member in a table to create an inheritance chain.

-- ********************************************************
-- index tag method AdvProtoIndex(t,f)
--
-- This is a 'simple' version of the multiple inheritance
-- tag method. It does not cache and thus it is quite slow.
-- However, if you think something strange is happening, you
-- can fall back to this version and see if the strangeness
-- goes away.

function AdvProtoIndex (t,f)
  
  if f == '_parents' then -- to avoid loop
    if (OldIndex) then
	    return OldIndex(t,f)
	else
		return nil;
	end
  end

  local p = t["_parents"];

  if (type(p) == 'table') then
     local cur_index = 1; -- start at 1
	 local cur_data;

	 repeat
	   cur_data = p[cur_index];
	   if (type(cur_data) == 'table') then
	       local result = cur_data[f];
	       if (result ~= nil) then
		       return result;        -- we found a match
		   end
	   else
	       if (OldIndex) then
		      return OldIndex(t,f);
		   else
		      return nil;
		   end
	   end
	   cur_index = cur_index + 1; -- do next parent
	 until (cur_data == nil);

	 return nil; -- we didn't find a match
  else 
     return nil;
  end
end

a_base = {
  a_number = 1
}

b_base = {
  b_number = 2
}

ab_class = {
  _parents = { a_base, b_base }
}

print(ab_class.a_number); -- yields "1"
print(ab_class.b_number); -- yields "2"

A performance optimized implementation is provided which functions the mostly same but is drastically faster.

----------------------------------------------------------
-- AdvProtoIndexWithCache
--
-- This inheritance tag method handles multiple inheritance via a
-- "_parent = {}" table. It caches information in the top-level table
-- to make lookups fast.
--
-- Example:
--
-- This tag method is applied to all tables, so all you have to do to
-- get a magic inheritance table is to do this:
--
-- BaseObj1 = { a_value = "a" }
-- BaseObj2 = { b_value = "b" }
-- MyClass  = { _parents = { BaseObj2, BaseObj1 } }
-- MyInstance = { _parents = { MyClass }
--

function setupMultipleInheritenceForTag(a_tag) 
    -- I like to setup my tag methods within a function because
    -- then stuff like these private declarations can be
    -- referenced with upvalues and disappear. :)

    local NIL_OBJECT = { magic_nil_object = 1}
    local SLOT_REF_TAG = newtag()
    local OldIndex = gettagmethod(tag({}),"index")
    local debug_mode = nil

    AdvProtoIndexWithCache = function (t,f, instance, depth)
      if (f == '_parents') or (f == '_slotcache') then -- to avoid loop
	if (%OldIndex) then
		return %OldIndex(t,f)
	    else
		return nil;
	    end
      end


      if instance == nil then
	-- we are the instance!
	instance = t 
      end
      if depth == nil then
	depth = 0
      end

      -- get out the parent table
      local p = rawgettable(t,"_parents")

      local cache = rawgettable(instance,"_slotcache");
      if cache then
	 local item = rawgettable(cache,f)
	 if item then
	   if item == %NIL_OBJECT then
	     return nil
	   elseif tag(item) == %SLOT_REF_TAG then
	     return item.obj[f]
	   else
	     return item
	   end
	 end
      else
	 -- if we are the instance AND we had a _parents
	 -- slot, then create the slot cache!

	 if (instance == t) and (p) then
	   cache = {}
	   rawsettable(t,"_slotcache",cache); -- make the slot cache!
	 end
      end

      if (type(p) == 'table') then
	 local cur_index = 1; -- start at 1
	     local cur_data;


	     repeat
	       cur_data = p[cur_index];

	       if (%debug_mode) then
		 print("---------", cur_index, depth)
	       end
	       if (type(cur_data) == 'table') then
		   if (%debug_mode) then
		     printTables(cur_data)
		   end

		 -- local result = cur_data[f];
		   local result = rawgettable(cur_data,f);

		   if (%debug_mode and (result ~= nil)) then
		     print("value: ", result)
		   end

		   -- if we found the slot in us, then we need
		   -- to do the caching, because after we return
		   -- it's not possible to make a SLOT_REF
		   if ((result ~= nil) and (cache)) then
                     rawsettable(instance,f,result);
		   end

		   if (result == nil) then
		     result = AdvProtoIndexWithCache(cur_data,f,instance, depth + 1)
		   end

		   if (result ~= nil) then
		     if (%debug_mode and (result ~= nil)) then
		       print("value: ", result) 
		     end

		     return result;        -- we found a match
		   end
	       else
		   local result 

		   if (%OldIndex) then
		     result = %OldIndex(t,f);
		   else
		     result = nil;
		   end

			   if cache then
			     if (type(result) == "function") then
			       rawsettable(cache,f,result);
			     elseif result == nil then 
			       rawsettable(cache,f,%NIL_OBJECT)
			     else
			       local slot_ref = { obj = cur_data }
			       settag(slot_ref,%SLOT_REF_TAG);
			       rawsettable(cache,f,slot_ref);
			     end
			   end
			   return result;        -- we found a match


	       end
	       cur_index = cur_index + 1; -- do next parent
	     until (cur_data == nil);

	     if cache then
	       rawsettable(cache,f,%NIL_OBJECT)
	     end

	     return nil; -- we didn't find a match
      else 
	 return nil;
      end
    end


    settagmethod(a_tag,"index",AdvProtoIndexWithCache);  -- Lua 3.1 method
end

Explanation

In the cache, functions are pointed to directly, and other items are pointed to using something called a "SLOT_REF". A SLOT_REF is a special kind of table which is a cache by reference instead of by value. It contains a reference to the table and index of the original value so that if the original data value changes, this SLOT_REF will correctly point to the new data-value. This is not done for methods, because it was decided that performance of method lookups is more important than retaining the ability to change methods in base-classes.

Another implementation of this machinery could be even faster by doing away with SLOT_REF, and instead using some method to invalidate slotcaches (such as maintaining a reverse-slotcache dependency list). Whenever a base-class method or function was changed, the reverse dependency chain's slotcaches would be invalidated. This would probably result in only moderate extra data-keeping if the "_slotcache" were changed to occur at the "class" level of the object instead of the "instance" level as it does now.

Weaknesses

It's important to recognize that because the caching version stores information directly in a single flattened table, changes to the base class methods may be ignored if they are already in the cached table. In practice, changing methods of a base class is an infrequent operation. When using this machinery, one should avoid this practice entirely.

Because Lua (IMO mistakenly) overrides nil as meaning both false and an empty data element, there is no way to override an inherited object member with the nil value. This is because setting self.a = nil will result in the removal of the "a" member, thus causing the missing-index tag method to fire, which consults the _parents or _slotcache tables to find an inherited element "a". I've not yet found a workaround for this problem.

Conclusion

The full code for the solution, including some helpful utility functions, is provided here.

References