xtype (halted)

.Incentives:
Automation:: Prevent writing redundant type checking code.
Interoperability:: Having a general low-level type system library can ease the interactions of third-party code.
Metaprogramming / Genericity:: Exploit the dynamic nature of Lua to generate definitions on-the-fly.

See link:src[].

== Concepts

=== Type

A **xtype**'s type is either primitive or non-primitive.

A primitive type is a string. It can be any Lua types from `type()` or additional types like `xtype` or `multifunction`.

A non-primitive type is a table defining the type. It contains the `xtype_name`, `xtype_stack` and `xtype_set` fields and should identify as a `xtype`.

==== Value

Any Lua value has a type; we will call this the terminal type of the value as opposed to inherited types. If the metatable of a `table` or `userdata` value has a `xtype` field, then the type is the value of that field. If the value is a `cdata`, its type is defined by `xtype.ctype()`. Otherwise, the type is the Lua type returned by `type()`.

==== Inheritance

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.

WARNING: Ambiguities are ignored.

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

=== xtype

[source, lua]
----
-- Create a type.
--
-- The created type is a table with 3 fields: xtype_name, xtype_stack and xtype_set.
-- The table can be modified as long as the xtype fields are left untouched.
-- A default metatable is set; it can be replaced at the condition that the
-- type would still be recognized as a "xtype".
--
-- name: human-readable string (doesn't have to be unique)
-- ...: base types, be specific in descending order
-- return created type
xtype.create(name, ...)

-- Get/bind a type to a ctype (LuaJIT FFI).
--
-- This can't be changed afterwards.
-- The same type can be bound to different ctypes; it can be useful when
-- different ctype qualifiers should match the same type.
--
-- ctype: cdata ctype object
-- t: (optional) type
-- return bound type
xtype.ctype(ctype, t)

-- Get terminal type of a value.
xtype.get(v)

-- Check if a value is of type t.
xtype.is(v, t)

-- Check if a type is of type ot.
xtype.of(t, ot)

-- Create a multifunction.
xtype.multifunction()

-- Global multifunctions namespace for binary operators.
-- For interoperability between third-party types.
-- map of Lua binary op name => multifunction
-- (add, sub, mul, div, mod, pow, concat, eq, lt, le)
xtype.op

-- Code generation tools.

-- Generate "a1, a2, a3, a4..." list string.
-- tpl: string where "$" will be replaced by the index
-- i: start index
-- j: end index
-- separator: (optional) default: ", "
xtype.tpllist(tpl, i, j, separator)

-- Template substitution.
-- tpl: string with $... parameters
-- args: map of param => value
-- return processed template
xtype.tplsub(tpl, args)
----

=== Multifunction

[source, lua]
----
-- Define a multifunction signature.
-- f: definition function; nil to undefine
-- ...: signature, list of types
multifunction:define(f, ...)

-- Add a generator function.
--
-- All generators are called when no matching definition has been found to
-- eventually define new signatures.
--
-- f(multifunction, ...): called to generate new definitions
--- ...: call signature, list of types
multifunction:addGenerator(f)

-- Get the resolved function for a specific signature.
-- ...: call signature, list of types
-- return function or nil without a matching definition
multifunction:resolve(...)

-- Call the multifunction.
multifunction(...)
multifunction:call(...)
----

-- Benchmark multifunction call.
package.path = "src/?.lua;"..package.path
local xtype = require("xtype")

local n = ...
n = tonumber(n) or 1e6

local add = xtype.multifunction()
add:define(function(a,b) return a+b end, "number", "number")

local a = 0
for i=1,n do
  a = add(a, 1)
end
assert(a == n)

-- Benchmark type checking.
package.path = "src/?.lua;"..package.path
local xtype = require("xtype")

local n = ...
n = tonumber(n) or 1e7

local T = xtype.create("T")
local t = setmetatable({}, {xtype = T})

for i=1,n do
  a = xtype.is(T, "xtype") and xtype.is(t, T) and xtype.is(i, "number")
end
assert(a)

-- Test FFI cdata support.
package.path = "src/?.lua;"..package.path
local ffi = require("ffi")
local xtype = require("xtype")

ffi.cdef("typedef struct{double x, y;} vec2_t;")
local vec2 = xtype.create("vec2")
local vec2_t = ffi.typeof("vec2_t")
-- type behavior
setmetatable(vec2, {
  xtype = "xtype",
  __call = function(_, ...) return vec2_t(...) end
})
-- instance behavior
ffi.metatype(vec2_t, {
  __unm = function(v) return vec2(-v.x, -v.y) end,
  __add = xtype.op.add,
  __sub = xtype.op.sub,
  __mul = xtype.op.mul,
  __div = xtype.op.div,
  __eq = xtype.op.eq
})
xtype.op.add:define(function(a, b) return vec2(a.x+b.x, a.y+b.y) end, vec2, vec2)
xtype.op.mul:define(function(v, n) return vec2(v.x*n, v.y*n) end, vec2, "number")
xtype.op.mul:define(function(n, v) return vec2(v.x*n, v.y*n) end, "number", vec2)
xtype.op.div:define(function(a, b) return vec2(a.x/b.x, a.y/b.y) end, vec2, vec2)
xtype.op.div:define(function(v, n) return vec2(v.x/n, v.y/n) end, vec2, "number")
xtype.op.eq:define(function(a, b) return a.x == b.x and a.y == b.y end, vec2, vec2)
-- bind
xtype.ctype(vec2_t, vec2)

assert(vec2(1,1) == vec2(1,1))
assert(vec2(1,1)*2 == 2*vec2(1,1))
assert(vec2(1,1)+vec2(1,1) == vec2(4,4)/2)

local a = ffi.new("vec2_t[1]", {{2,2}})
local r = a[0]
local p = a+0
xtype.ctype(ffi.typeof(r), vec2)
xtype.ctype(ffi.typeof(p), vec2)
assert(r == p)
assert(r == vec2(2,2))
assert(r/p == vec2(1,1))

-- Test errors.
package.path = "src/?.lua;"..package.path
local xtype = require("xtype")

-- Expect an error.
local function check(f)
  local ok, err = pcall(f)
  assert(not ok)
  print("[checked]", err)
end

check(function() xtype.create() end)
check(function() xtype.create(5) end)

local mf = xtype.multifunction()
check(function() mf:define(function() end, nil) end)
check(function() mf:define(function() end, 1) end)
check(function() mf:define(nil, "number", nil, "number") end)
mf:define(function() end, "number", "number")
check(function() mf() end)
check(function() mf(5) end)
check(function() mf(5, 5, 5) end)
check(function() mf(5, "5") end)
mf:define(nil, "number", "number")
check(function() mf(5, 5) end)

-- Test multifunction.
package.path = "src/?.lua;"..package.path
local xtype = require("xtype")

do -- Basic test.
  local op_add = xtype.multifunction()
  local op_mul = xtype.multifunction()
  local op_eq = xtype.multifunction()

  local function build_type(t)
    local ins_mt = {
      xtype = t,
      __add = op_add,
      __mul = op_mul,
      __eq = op_eq
    }
    local type_mt = {
      xtype = "xtype",
      __call = function(t, v)
        return setmetatable({v = v}, ins_mt)
      end
    }
    return setmetatable(t, type_mt)
  end

  local Fruits = build_type(xtype.create("Fruits"))
  local Apples = build_type(xtype.create("Apples", Fruits))
  local Oranges = build_type(xtype.create("Oranges", Fruits))

  op_add:define(function(a, b) return Apples(a.v+b.v) end, Apples, Apples)
  op_add:define(function(a, b) return Oranges(a.v+b.v) end, Oranges, Oranges)
  op_add:define(function(a, b) return Fruits(a.v+b.v) end, Fruits, Fruits)
  op_mul:define(function(a, f) return Apples(a.v*f) end, Apples, "number")
  op_mul:define(function(a, f) return Oranges(a.v*f) end, Oranges, "number")
  op_mul:define(function(a, f) return Fruits(a.v*f) end, Fruits, "number")
  op_eq:define(function(a, b) return a.v == b.v end, Apples, Apples)
  op_eq:define(function(a, b) return a.v == b.v end, Oranges, Oranges)
  op_eq:define(function(a, b)
    return xtype.get(a) == xtype.get(b) and a.v == b.v
  end, Fruits, Fruits)

  local apples = Apples(5)
  local oranges = Oranges(5)
  assert(apples+apples == Apples(10))
  assert(not (apples+oranges == Apples(10)))
  assert(apples+oranges == Fruits(10))
  assert(oranges+apples == Fruits(10))
  assert(apples*3 == Apples(15))
end

do -- Test resolution order.
  local animal = xtype.create("animal")
  local dog = xtype.create("dog", animal)
  local cat = xtype.create("cat", animal)
  local chimera = xtype.create("chimera", cat, dog)

  local what = xtype.multifunction()
  what:define(function() return "animal" end, animal)
  what:define(function() return "cat" end, cat)
  what:define(function() return "dog" end, dog)
  what:define(function() return "chimera" end, chimera)
  local a = setmetatable({}, {xtype = chimera})
  assert(what(a) == "chimera")
  what:define(nil, chimera)
  assert(what(a) == "cat")
  what:define(nil, cat)
  assert(what(a) == "dog")
  what:define(nil, dog)
  assert(what(a) == "animal")
end

do -- Test generator.
  local unpack = table.unpack or unpack
  local count = xtype.multifunction()
  count:addGenerator(function(self, ...)
    local sign = {...}
    self:define(function() return #sign end, unpack(sign))
  end)
  assert(count() == 0)
  assert(count(1, 2, 3) == 3)
  assert(count("a", "b", "c") == 3)
  assert(count(nil, nil, nil) == 3)
  assert(count(1, nil, "c") == 3)
end

-- Test type creation and inheritance.
package.path = "src/?.lua;"..package.path
local xtype = require("xtype")

local being = xtype.create("being")
local animal = xtype.create("animal", being)
local mammal = xtype.create("mammal", animal)
local carnivorous = xtype.create("carnivorous")
local omnivorous = xtype.create("omnivorous")
local hominidae = xtype.create("hominidae", mammal, omnivorous)
local canidae = xtype.create("canidae", mammal, carnivorous)
local human = xtype.create("human", hominidae)
local dog = xtype.create("dog", canidae)
local chimera = xtype.create("chimera", human, dog)

local Nina = setmetatable({}, {xtype = human})
local Alexander = setmetatable({}, {xtype = dog})
local Chimera = setmetatable({}, {xtype = chimera})

assert(xtype.get(0) == "number")
assert(xtype.is(0, "number"))
assert(not xtype.is(0, "string"))
assert(xtype.get(being) == "xtype")
assert(xtype.of(being, being))

assert(xtype.of(animal, being))
assert(xtype.of(mammal, being))
assert(xtype.of(mammal, animal))
assert(xtype.of(canidae, mammal))
assert(xtype.of(canidae, being))
assert(xtype.of(canidae, carnivorous))
assert(xtype.of(dog, canidae))
assert(xtype.of(human, hominidae))
assert(not xtype.of(human, dog))

assert(xtype.is(Nina, human))
assert(xtype.is(Alexander, dog))
assert(xtype.is(Chimera, human))
assert(xtype.is(Chimera, dog))

-- https://github.com/ImagicTheCat/lua-xtype
-- MIT license (see LICENSE or src/xtype.lua)
--[[
MIT License

Copyright (c) 2021 ImagicTheCat

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all
copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
SOFTWARE.
]]

local ffi
do
  local ok; ok, ffi = pcall(require, "ffi")
  ffi = ok and ffi or nil
end
local loadstring = loadstring or load
local table_unpack = table.unpack or unpack
local type, select = type, select
local table_pack = table.pack or function(...)
  local t = {...}
  t.n = select("#", ...)
  return t
end

-- xtype

local xtype = {}

local function xtype_tostring(t)
  local mt = getmetatable(t)
  mt.__tostring = nil
  local str = string.gsub(tostring(t), "table:", "xtype<"..t.xtype_name..">:", 1)
  mt.__tostring = xtype_tostring
  return str
end

local type_mt = {
  xtype = "xtype",
  __tostring = xtype_tostring
}

-- Create a type.
--
-- The created type is a table with 3 fields: xtype_name, xtype_stack and xtype_set.
-- The table can be modified as long as the xtype fields are left untouched.
-- A default metatable is set; it can be replaced at the condition that the
-- type would still be recognized as a "xtype".
--
-- name: human-readable string (doesn't have to be unique)
-- ...: base types, be specific in descending order
-- return created type
function xtype.create(name, ...)
  if type(name) ~= "string" then error("invalid name") end
  -- check base types
  local bases = table_pack(...)
  for i=1, bases.n do
    local base = bases[i]
    if not (type(base) == "string" or (type(base) == "table" and base.xtype_name)) then
      error("invalid base type #"..i)
    end
  end
  -- create
  local t = setmetatable({
    xtype_name = name,
    xtype_stack = {},
    xtype_set = {}
  }, type_mt)
  -- append self
  table.insert(t.xtype_stack, t)
  t.xtype_set[t] = true
  -- Inherits from base types (some kind of cascade breadth first search).
  -- Each base type is evaluated left to right, with one type inheritance per step.
  local step = 1
  local browsing = true
  while browsing do
    browsing = false
    for _, base in ipairs(bases) do
      if type(base) == "string" then -- primitive type
        if step == 1 then
          browsing = true
          if not t.xtype_set[base] then
            t.xtype_set[base] = true
            table.insert(t.xtype_stack, base)
          end
        end
      else -- non-primitive type
        local st = base.xtype_stack[step]
        if st then
          browsing = true
          if not t.xtype_set[st] then
            t.xtype_set[st] = true
            table.insert(t.xtype_stack, st)
          end
        end
      end
    end
    step = step+1
  end
  return t
end

local ctype_types = {} -- map of ctype id => type

-- Get/bind a type to a ctype (LuaJIT FFI).
--
-- This can't be changed afterwards.
-- The same type can be bound to different ctypes; it can be useful when
-- different ctype qualifiers should match the same type.
--
-- ctype: cdata ctype object
-- t: (optional) type
-- return bound type
function xtype.ctype(ctype, t)
  local id = tonumber(ctype)
  if t and not ctype_types[id] then ctype_types[id] = t end
  return ctype_types[id]
end

-- Get terminal type of a value.
local function xtype_get(v)
  local v_type = type(v)
  if v_type == "table" or v_type == "userdata" then
    local mt = getmetatable(v)
    return mt and mt.xtype or v_type
  elseif v_type == "cdata" then
    return ctype_types[tonumber(ffi.typeof(v))] or v_type
  else return v_type end
end
xtype.get = xtype_get

-- Check if a value is of type t.
function xtype.is(v, t)
  local vt = xtype_get(v)
  if type(vt) == "table" then return vt.xtype_set[t] ~= nil
  else return vt == t end
end

-- Check if a type is of type ot.
function xtype.of(t, ot)
  if type(t) == "table" then return t.xtype_set[ot] ~= nil
  else return t == ot end
end

-- Multifunction.

local function multifunction_tostring(t)
  local mt = getmetatable(t)
  mt.__tostring = nil
  local str = string.gsub(tostring(t), "table:", "multifunction:", 1)
  mt.__tostring = multifunction_tostring
  return str
end

local multifunction = {}

-- Create hash sign tree.
local function new_hsign()
  local count = 0
  local hasher_mt
  hasher_mt = {
    __index = function(t, k)
      count = count+1
      local st = setmetatable({count}, hasher_mt)
      t[k] = st
      return st
    end
  }
  local root = setmetatable({count}, hasher_mt)
  return root
end

-- Hash function signature.
-- sign: signature, list of types
-- return number
local function mf_hash_sign(self, sign)
  local node = self.hsign
  for _, t in ipairs(sign) do node = node[t] end
  return node[1]
end

-- Check and return signature.
local function check_sign(...)
  local sign = table_pack(...)
  for i=1, sign.n do
    local t = sign[i]
    if type(t) ~= "table" and type(t) ~= "string" then
      error("invalid signature type #"..i)
    end
  end
  return sign
end

-- return formatted signature string
local function format_sign(sign)
  local names = {}
  for _, t in ipairs(sign) do
    table.insert(names, type(t) == "string" and t or t.xtype_name)
  end
  return "("..table.concat(names, ", ")..")"
end

-- Stack distance to another type from a terminal type.
-- return distance or nil if not of type ot
local function type_dist(t, ot)
  if type(t) == "string" then return t == ot and 0 or nil end
  for i, st in ipairs(t.xtype_stack) do
    if st == ot then return i-1 end
  end
end

-- Distance to another signature from a call signature.
-- return distance or nil if not generalizable to osign
local function sign_dist(sign, osign)
  local dist = 0
  for i=1, #sign do
    local tdist = type_dist(sign[i], osign[i])
    if not tdist then return end
    dist = dist+tdist
  end
  return dist
end

-- Find candidate.
-- return candidate or nil if none found
--- candidate: {def, dist}
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, {def, dist}) end
    end
  end
  -- sort candidates
  table.sort(candidates, function(a, b) return a[2] < b[2] end)
  -- NOTE: check for ambiguity ?
  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[1].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 mutifunction 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[1].f(...) end

  -- fallback to unoptimized path
  return mf_call(self, ...)
end
  ]=]
  -- generate vararg/table-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"
  local code = xtype.tplsub(main, {hash_code = hcode})
  -- compile
  mfcall = loadstring(code, "xtype multifunction call("..n..")")(xtype_get, mf_call)
  -- cache
  mfcalls[n] = mfcall
  return mfcall
end

-- Define a multifunction signature.
-- f: definition function; nil to undefine
-- ...: signature, list of types
function multifunction:define(f, ...)
  local sign = check_sign(...)
  local hash = mf_hash_sign(self, sign)
  if f then -- define
    -- increase call parameters, re-compile call function
    if sign.n > self.max_calln then
      self.max_calln = sign.n
      local fcall = gen_opt_mfcall(self.max_calln)
      local mt = getmetatable(self)
      self.call = fcall
      mt.__call = fcall
    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 match)
      for _, candidate in pairs(self.candidates) do
        local dist = sign_dist(candidate[1].sign, sign)
        if dist and dist < candidate[2] then -- update if better candidate
          candidate[1], candidate[2] = def, dist
        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[1] == def then self.candidates[chash] = nil end
      end
    end
  end
end

-- Get the resolved function for a specific signature.
-- ...: call signature, list of types
-- return function or nil without a matching definition
function multifunction:resolve(...)
  local sign = check_sign(...)
  return mf_resolve_sign(self, sign)
end

-- Add a generator function.
--
-- All generators are called when no matching definition has been found to
-- eventually define new signatures.
--
-- f(multifunction, ...): called to generate new definitions
--- ...: call signature, list of types
function multifunction:addGenerator(f)
  self.generators[f] = true
end

-- Create a multifunction.
function xtype.multifunction()
  -- The metatable is per multifunction to independently update the call
  -- function.
  local default_call = gen_opt_mfcall(0)
  local multifunction_mt = {
    xtype = "multifunction",
    __tostring = multifunction_tostring,
    __index = multifunction,
    __call = default_call
  }

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

-- Code generation tools.

-- Generate "a1, a2, a3, a4..." list string.
-- tpl: string where "$" will be replaced by the index
-- i: start index
-- j: end index
-- separator: (optional) default: ", "
function xtype.tpllist(tpl, i, j, separator)
  local list = {}
  for k=i,j do table.insert(list, (string.gsub(tpl, "%$", k))) end
  return table.concat(list, separator or ", ")
end

-- Template substitution.
-- tpl: string with $... parameters
-- args: map of param => value
-- return processed template
function xtype.tplsub(tpl, args)
  return string.gsub(tpl, "%$([%w_]+)", args)
end

-- Global multifunctions namespace for binary operators.
-- For interoperability between third-party types.
-- map of Lua binary op name => multifunction
-- (add, sub, mul, div, mod, pow, concat, eq, lt, le)
xtype.op = {
  add = xtype.multifunction(),
  sub = xtype.multifunction(),
  mul = xtype.multifunction(),
  div = xtype.multifunction(),
  mod = xtype.multifunction(),
  pow = xtype.multifunction(),
  concat = xtype.multifunction(),
  eq = xtype.multifunction(),
  lt = xtype.multifunction(),
  le = xtype.multifunction()
}

return xtype