xtype (halted)

A non-primitive type can inherit from other types, building a stack of types. This stack defines the order in which the types are evaluated, from the terminal type to the least specific inherited types.

=== Multifunction

A multifunction is a function that can have multiple definitions, each associated to a specific signature. When called, it resolves the call by selecting a matching definition from the call signature.



==== Metaprogramming

We can use Lua as its own metaprogramming language: we can generate Lua code from Lua.

A multifunction can have generators that are called when no definitions could be found, allowing to generate definitions for specific call signatures on-the-fly.

== API

  mf(5,5)
  errcheck("unresolved call signature", mf)
  errcheck("unresolved call signature", mf, 5)
  errcheck("unresolved call signature", mf, 5, 5, 5)
  errcheck("unresolved call signature", mf, 5, "5")
  mf:define(nil, "number", "number")
  errcheck("unresolved call signature", mf, 5, 5)
  -- test ambiguity
  local A = xtype.create("A")
  local B = xtype.create("B")
  local C = xtype.create("C", A, B)
  mf:define(function() end, A, B)
  mf:define(function() end, B, A)
  errcheck("ambiguous call signature", mf.resolve, mf, C, C)
end

  local node = self.hsign
  for _, t in ipairs(sign) do node = node[t] end
  return node[1]
end
multifunction.hashSign = mf_hash_sign

-- Find candidate.
-- return candidate or nothing if none found
--- candidate: {.sign, .dist, .def}
---- sign: call signature
---- dist: distance from call signature
---- def: candidate definition
local function mf_find_candidate(self, sign)
  -- find candidates
  local candidates = {}
  for hash, def in pairs(self.definitions) do
    if #sign == #def.sign then -- same number of parameters
      local dist = sign_dist(sign, def.sign)
      if dist then table.insert(candidates, {sign = sign, def = def, dist = dist}) end
    end
  end
  -- sort candidates
  table.sort(candidates, function(a, b) return a.dist < b.dist end)
  -- check for ambiguity
  if candidates[1] and candidates[2] and candidates[1].dist == candidates[2].dist then
    -- generate ambiguity error
    local candidate_signs = {}
    for _, candidate in ipairs(candidates) do
      if candidate.dist ~= candidates[1].dist then break end
      table.insert(candidate_signs, "\t"..format_sign(candidate.def.sign))
    end
    error("ambiguous call signature "..format_sign(sign).."\ncandidates:\n"..table.concat(candidate_signs, "\n"))
  end
  return candidates[1]
end

local function mf_resolve_sign(self, sign)
  local hash = mf_hash_sign(self, sign)
  local candidate = self.candidates[hash]
  if not candidate then
    candidate = mf_find_candidate(self, sign)
    if not candidate then -- re-try
      -- call generators
      for generator in pairs(self.generators) do generator(self, table_unpack(sign)) end
      candidate = mf_find_candidate(self, sign)
    end
    self.candidates[hash] = candidate
  end
  return candidate and candidate.def.f
end

-- Unoptimized multifunction call.
local function mf_call(self, ...)
  local sign = table_pack(...)
  for i=1, sign.n do sign[i] = xtype_get(sign[i]) end
  local f = mf_resolve_sign(self, sign)
  if not f then error("unresolved call signature "..format_sign(sign)) end
  return f(...)
end

local mfcalls = {}
-- Generate optimized multifunction call.
-- n: maximum number of parameters
local function gen_opt_mfcall(n)
  -- cache check
  local mfcall = mfcalls[n]
  if mfcall then return mfcall end
  -- generate code
  local main = [=[
local select = select
local xtype_get, mf_call = ...
return function(self, ...)
  -- optimized path
  local n = select("#", ...)
  local hash
  --
  $hash_code
  --
  local candidate = self.candidates[hash]
  if candidate then return candidate.def.f(...) end

  -- fallback to unoptimized path
  return mf_call(self, ...)
end
  ]=]
  -- generate table/vararg-less hashing for each arguments count
  local hcode = "if n == 0 then hash = self.hsign[1]\n"
  for i=1,n do
    hcode = hcode.."elseif n == "..i.." then\n"
    hcode = hcode.."local "..xtype.tpllist("a$", 1, i, ", ").." = ...\n"
    hcode = hcode.."hash = self.hsign"..xtype.tpllist("[xtype_get(a$)]", 1, i, "").."[1]\n"
  end
  hcode = hcode.."end\n"

    end
    -- definition
    local def = self.definitions[hash]
    if def then def.f = f -- update definition
    else -- new definition
      def = {f = f, sign = sign}
      self.definitions[hash] = def
      -- update candidates (better or equivalent match)
      for chash, candidate in pairs(self.candidates) do
        local dist = sign_dist(candidate.sign, sign)
        if dist then
          if dist < candidate.dist then -- update if better candidate
            candidate.def, candidate.dist = def, dist
          elseif dist == candidate.dist then -- remove candidate on ambiguity
            self.candidates[chash] = nil
          end
        end
      end
    end
  else -- undefine
    local def = self.definitions[hash]
    if def then
      self.definitions[hash] = nil
      -- remove candidates (removed definition)
      for chash, candidate in pairs(self.candidates) do
        if candidate.def == def then self.candidates[chash] = nil end
      end
    end
  end
end

-- Get the resolved function for a specific signature.
-- ...: call signature, list of types

    __index = multifunction,
    __call = default_call
  }
  return setmetatable({
    hsign = new_hsign(),
    definitions = {}, -- map of sign hash => {.f, .sign}
    generators = {}, -- set of generator functions
    candidates = {}, -- cached candidates, map of call sign hash => {.sign, .dist, .def}
    max_calln = 0, -- maximum call parameters
    call = default_call
  }, multifunction_mt)
end

-- Code generation tools.