path: root/tex/context/base/mkiv/node-met.lua

if not modules then modules = { } end modules ['node-nut'] = {
    version   = 1.001,
    comment   = "companion to node-ini.mkiv",
    author    = "Hans Hagen, PRAGMA-ADE, Hasselt NL",
    copyright = "PRAGMA ADE / ConTeXt Development Team",
    license   = "see context related readme files"
}

-- This is an experimental module. Don't use nuts for generic code, at least not till
-- the regular code is proven stable. No support otherwise.

-- luatex: todo: copylist should return h, t
-- todo: see if using insert_before and insert_after makes sense here

-- This file is a side effect of the \LUATEX\ speed optimization project of Luigi
-- Scarso and me. As \CONTEXT\ spends over half its time in \LUA, we though that
-- using \LUAJIT\ could improve performance. We've published some of our experiences
-- elsewhere, but to summarize: \LUAJITTEX\ benefits a lot from the faster virtual
-- machine, but when jit is turned of we loose some again. We experimented with
-- ffi (without messing up the \CONTEXT\ code too much) but there we also lost more
-- than we gained (mostly due to lack of compatible userdata support: it's all or
-- nothing). This made us decide to look into the \LUA||\TEX\ interfacing and by
-- profiling and careful looking at the (of course then still beta source code) we
-- could come up with some improvements. The first showed up in 0.75 and we've more
-- on the agenda for 0.80. Although some interfaces could be sped up significantly
-- in practice we're only talking of 5||10\% on a \CONTEXT\ run and maybe more when
-- complex and extensive node list manipulations happens (we're talking of hundreds
-- of millions cross boundary calls then for documents of hundreds pages). One of the
-- changes in the \CONTEXT\ code base is that we went from indexed access to nodes to
-- function calls (in principle faster weren't it that the accessors need to do more
-- checking which makes them slower) and from there to optimizing these calls as well
-- as providing fast variants for well defined situations. At first optimizations were
-- put in a separate \type {node.fast} table although some improvements could be
-- ported to the main node functions. Because we got the feeling that more gain was
-- possible (especially when using more complex fonts and \MKIV\ functionality) we
-- eventually abandoned this approach and dropped the \type {fast} table in favour of
-- another hack. In the process we had done lots of profiling and testing so we knew
-- where time was wasted,
--
-- As lots of testing and experimenting was part of this project, I could not have
-- done without stacks of new \CD s and \DVD s. This time Porcupine Tree, No-Man
-- and Archive were came to rescue.
--
-- It all started with testing performance of:
--
-- node.getfield = metatable.__index
-- node.setfield = metatable.__newindex

local type, select = type, select
local setmetatableindex = table.setmetatableindex

-- First we get the metatable of a node:

local metatable = nil

do
    local glyph = node.new("glyph",0)
    metatable = getmetatable(glyph)
    node.free(glyph)
end

-- statistics.tracefunction(node,       "node",       "getfield","setfield")
-- statistics.tracefunction(node.direct,"node.direct","getfield","setfield")

-- We start with some helpers and provide all relevant basic functions in the
-- node namespace as well.

nodes                       = nodes or { }
local nodes                 = nodes

local nodecodes               = nodes.nodecodes

nodes.tostring                = node.tostring or tostring
nodes.copy                    = node.copy
nodes.copy_node               = node.copy
nodes.copy_list               = node.copy_list
nodes.delete                  = node.delete
nodes.dimensions              = node.dimensions
nodes.rangedimensions         = node.rangedimensions
nodes.end_of_math             = node.end_of_math
nodes.flush                   = node.flush_node
nodes.flush_node              = node.flush_node
nodes.flush_list              = node.flush_list
nodes.free                    = node.free
nodes.insert_after            = node.insert_after
nodes.insert_before           = node.insert_before
nodes.hpack                   = node.hpack
nodes.new                     = node.new
nodes.tail                    = node.tail
nodes.traverse                = node.traverse
nodes.traverse_id             = node.traverse_id
nodes.traverse_char           = node.traverse_char
nodes.traverse_glyph          = node.traverse_glyph
nodes.traverse_list           = node.traverse_list
nodes.slide                   = node.slide
nodes.vpack                   = node.vpack
nodes.fields                  = node.fields
nodes.is_node                 = node.is_node
nodes.setglue                 = node.setglue
nodes.uses_font               = node.uses_font

nodes.first_glyph             = node.first_glyph
nodes.has_glyph               = node.has_glyph or node.first_glyph

nodes.current_attr            = node.current_attr
nodes.has_field               = node.has_field
nodes.last_node               = node.last_node
nodes.usedlist                = node.usedlist
nodes.protrusion_skippable    = node.protrusion_skippable
nodes.check_discretionaries   = node.check_discretionaries
nodes.write                   = node.write
nodes.flatten_discretionaries = node.flatten_discretionaries

nodes.count                   = node.count
nodes.length                  = node.length

nodes.has_attribute           = node.has_attribute
nodes.set_attribute           = node.set_attribute
nodes.find_attribute          = node.find_attribute
nodes.unset_attribute         = node.unset_attribute

nodes.protect_glyph           = node.protect_glyph
nodes.protect_glyphs          = node.protect_glyphs
nodes.unprotect_glyph         = node.unprotect_glyph
nodes.unprotect_glyphs        = node.unprotect_glyphs
nodes.kerning                 = node.kerning
nodes.ligaturing              = node.ligaturing
nodes.hyphenating             = node.hyphenating
nodes.mlist_to_hlist          = node.mlist_to_hlist

nodes.effective_glue          = node.effective_glue
nodes.getglue                 = node.getglue
nodes.setglue                 = node.setglue
nodes.is_zero_glue            = node.is_zero_glue

nodes.tonode = function(n) return n end
nodes.tonut  = function(n) return n end

-- These are never used in \CONTEXT, only as a gimmick in node operators
-- so we keep them around.

local n_getfield = node.getfield
local n_getattr  = node.get_attribute

local n_setfield = node.setfield
local n_setattr  = n_setfield

nodes.getfield = n_getfield
nodes.setfield = n_setfield
nodes.getattr  = n_getattr
nodes.setattr  = n_setattr
nodes.takeattr = nodes.unset_attribute

local function n_getid     (n) return n_getfield(n,"id")      end
local function n_getsubtype(n) return n_getfield(n,"subtype") end

nodes.getid      = n_getid
nodes.getsubtype = n_getsubtype

local function n_getchar(n)   return n_getfield(n,"char")    end
local function n_setchar(n,c) return n_setfield(n,"char",c)  end
local function n_getfont(n)   return n_getfield(n,"font")    end
local function n_setfont(n,f) return n_setfield(n,"font",f)  end

nodes.getchar = n_getchar
nodes.setchar = n_setchar
nodes.getfont = n_getfont
nodes.setfont = n_setfont

local function n_getlist  (n)   return n_getfield(n,"list")     end
local function n_setlist  (n,l) return n_setfield(n,"list",l)   end
local function n_getleader(n)   return n_getfield(n,"leader")   end
local function n_setleader(n,l) return n_setfield(n,"leader",l) end

nodes.getlist   = n_getlist
nodes.setlist   = n_setlist
nodes.getleader = n_getleader
nodes.setleader = n_setleader

local function n_getnext(n)       return n_getfield(n,"next")    end
local function n_setnext(n,nn)    return n_setfield(n,"next",nn) end
local function n_getprev(n)       return n_getfield(n,"prev")    end
local function n_setprev(n,pp)    return n_setfield(n,"prev",pp) end
local function n_getboth(n)       return n_getfield(n,"prev"),    n_getfield(n,"next")    end
local function n_setboth(n,pp,nn) return n_setfield(n,"prev",pp), n_setfield(n,"next",nn) end

nodes.getnext = n_getnext
nodes.setnext = n_setnext
nodes.getprev = n_getprev
nodes.setprev = n_setprev
nodes.getboth = n_getboth
nodes.setboth = n_setboth

local function n_setlink(...)
    -- not that fast but not used often anyway
    local h = nil
    for i=1,select("#",...) do
        local n = select(i,...)
        if not n then
            -- go on
        elseif h then
            n_setfield(h,"next",n)
            n_setfield(n,"prev",h)
        else
            h = n
        end
    end
    return h
end

nodes.setlink = n_setlink

nodes.getbox  = node.getbox or tex.getbox
nodes.setbox  = node.setbox or tex.setbox

local n_flush_node    = nodes.flush
local n_copy_node     = nodes.copy
local n_copy_list     = nodes.copy_list
local n_find_tail     = nodes.tail
local n_insert_after  = nodes.insert_after
local n_insert_before = nodes.insert_before
local n_slide         = nodes.slide

local n_remove_node   = node.remove -- not yet nodes.remove

local function remove(head,current,free_too)
    local t = current
    head, current = n_remove_node(head,current)
    if not t then
        -- forget about it
    elseif free_too then
        n_flush_node(t)
        t = nil
    else
        n_setboth(t)
    end
    return head, current, t
end

nodes.remove = remove

function nodes.delete(head,current)
    return remove(head,current,true)
end

-- local h, c = nodes.replace(head,current,new)
-- local c = nodes.replace(false,current,new)
-- local c = nodes.replace(current,new)
--
-- todo: check for new.next and find tail

function nodes.replace(head,current,new) -- no head returned if false
    if not new then
        head, current, new = false, head, current
--         current, new = head, current
    end
    local prev = n_getprev(current)
    local next = n_getnext(current)
    if next then
        n_setlink(new,next)
    end
    if prev then
        n_setlink(prev,new)
    end
    if head then
        if head == current then
            head = new
        end
        n_flush_node(current)
        return head, new
    else
        n_flush_node(current)
        return new
    end
end

-- nodes.countall : see node-nut.lua

function nodes.append(head,current,...)
    for i=1,select("#",...) do
        head, current = n_insert_after(head,current,(select(i,...)))
    end
    return head, current
end

function nodes.prepend(head,current,...)
    for i=1,select("#",...) do
        head, current = n_insert_before(head,current,(select(i,...)))
    end
    return head, current
end

function nodes.linked(...)
    local head, last
    for i=1,select("#",...) do
        local next = select(i,...)
        if next then
            if head then
                n_setlink(last,next)
            else
                head = next
            end
            last = n_find_tail(next) -- we could skip the last one
        end
    end
    return head
end

function nodes.concat(list) -- consider tail instead of slide
    local head, tail
    for i=1,#list do
        local li = list[i]
        if li then
            if head then
                n_setlink(tail,li)
            else
                head = li
            end
            tail = n_slide(li)
        end
    end
    return head, tail
end

function nodes.reference(n)
    return n and tonut(n) or "<none>"
end

-- Here starts an experiment with metatables. Of course this only works with nodes
-- wrapped in userdata with a metatable.
--
-- Nodes are kind of special in the sense that you need to keep an eye on creation
-- and destruction. This is quite natural if you consider that changing the content
-- of a node would also change any copy (or alias). As there are too many pitfalls
-- we don't have this kind of support built in \LUATEX, which means that macro
-- packages are free to provide their own. One can even use local variants.
--
-- n1 .. n2 : append nodes, no copies
-- n1 * 5   : append 4 copies of nodes
-- 5 + n1   : strip first 5 nodes
-- n1 - 5   : strip last 5 nodes
-- n1 + n2  : inject n2 after first of n1
-- n1 - n2  : inject n2 before last of n1
-- n1^2     : two copies of nodes (keep orginal)
-- - n1     : reverse nodes
-- n1/f     : apply function to nodes

-- local s = nodes.typesetters.tonodes
--
-- local function w(lst)
--     context.dontleavehmode()
--     context(lst)
--     context.par()
-- end
--
-- local n1 = s("a")
-- local n2 = s("b")
-- local n3 = s("c")
-- local n4 = s("d")
-- local n5 = s("e")
-- local n6 = s("f")
-- local n7 = s("g")
--
-- local n0 = n1 .. (n2 * 10).. n3 .. (5 * n4) .. n5 .. ( 5 * n6 ) .. n7 / function(n) n.char = string.byte("!") return n end
--
-- w(#n0)
--
-- w(n0)
--
-- local n1 = s("a") * 10
-- local n2 = s("b") * 10
--
-- local n0 = ((5 + n1) .. (n2 - 5) )
-- local n0 = - n0
--
-- local n0 = nil .. n0^3 .. nil
--
-- w(n0)
--
-- w ( s("a") + s("b") ) w ( s("a") + 4*s("b") ) w ( 4*s("a") + s("b") ) w ( 4*s("a") + 4*s("b") )
-- w ( s("a") - s("b") ) w ( s("a") - 4*s("b") ) w ( 4*s("a") - s("b") ) w ( 4*s("a") - 4*s("b") )

local n_remove_node = nodes.remove

metatable.__concat = function(n1,n2) -- todo: accept nut on one end
    if not n1 then
        return n2
    elseif not n2 then
        return n1
    elseif n1 == n2 then
        -- or abort
        return n2 -- or n2 * 2
    else
        local tail = n_find_tail(n1)
        n_setlink(tail,n2)
        return n1
    end
end

metatable.__mul = function(n,multiplier)
    if type(multiplier) ~= "number" then
        n, multiplier = multiplier, n
    end
    if multiplier <= 1 then
        return n
    elseif n_getnext(n) then
        local head
        for i=2,multiplier do
            local h = n_copy_list(n)
            if head then
                local t = n_find_tail(h)
                n_setlink(t,head)
            end
            head = h
        end
        local t = n_find_tail(n)
        n_setlink(t,head)
    else
        local head
        for i=2,multiplier do
            local c = n_copy_node(n)
            if head then
                n_setlink(c,head)
            end
            head = c
        end
        n_setlink(n,head)
    end
    return n
end

metatable.__sub = function(first,second)
    if type(second) == "number" then
        local tail = n_find_tail(first)
        for i=1,second do
            local prev = n_getprev(tail)
            n_flush_node(tail) -- can become flushlist/flushnode
            if prev then
                tail = prev
            else
                return nil
            end
        end
        if tail then
            n_setnext(tail)
            return first
        else
            return nil
        end
    else
       -- aaaaa - bbb => aaaabbba
        local firsttail = n_find_tail(first)
        local prev = n_getprev(firsttail)
        if prev then
            local secondtail = n_find_tail(second)
            n_setlink(secondtail,firsttail)
            n_setlink(prev,second)
            return first
        else
            local secondtail = n_find_tail(second)
            n_setlink(secondtail,first)
            return second
        end
    end
end

metatable.__add = function(first,second)
    if type(first) == "number" then
        local head = second
        for i=1,first do
            local second = n_getnext(head)
            n_flush_node(head) -- can become flushlist/flushnode
            if second then
                head = second
            else
                return nil
            end
        end
        if head then
            n_setprev(head)
            return head
        else
            return nil
        end
    else
       -- aaaaa + bbb => abbbaaaa
        local next = n_getnext(first)
        if next then
            local secondtail = n_find_tail(second)
            n_setlink(first,second)
            n_setlink(secondtail,next)
        else
            n_setlink(first,second)
        end
        return first
    end
end

metatable.__len = function(current)
    local length = 0
    while current do
        current = n_getnext(current)
        length = length + 1
    end
    return length
end

metatable.__div = function(list,action)
    return action(list) or list -- always a value
end

metatable.__pow = function(n,multiplier)
    local tail = n
    local head = nil
    if n_getnext(n) then
        if multiplier == 1 then
            head = n_copy_list(n)
        else
            for i=1,multiplier do
                local h = n_copy_list(n)
                if head then
                    local t = n_find_tail(h)
                    n_setlink(t,head)
                end
                head = h
            end
        end
    else
        if multiplier == 1 then
            head = n_copy_node(n)
        else
            for i=2,multiplier do
                local c = n_copy_node(n)
                if head then
                    n_setlink(head,c)
                end
                head = c
            end
        end
    end
    -- todo: tracing
    return head
end

metatable.__unm = function(head)
    local last = head
    local first = head
    local current = n_getnext(head)
    while current do
        local next = n_getnext(current)
        n_setlink(current,first)
        first = current
        current = next
    end
    n_setprev(first)
    n_setnext(last)
    return first
end

-- see node-nut.lua for more info on going nuts

-- if not gonuts then
--
--     local nuts = { }
--     nodes.nuts = nuts
--
--     local function dummy(f) return f end
--
--     nodes.vianuts  = dummy
--     nodes.vianodes = dummy
--
--     for k, v in next, nodes do
--         if type(v) == "function" then
--             nuts[k] = v
--         end
--     end
--
-- end

-- also handy

local tonode       = nodes.tonode
local whatsit_code = nodecodes.whatsit
local getfields    = node.fields
local sort         = table.sort
local whatsitkeys  = { }
local keys         = { whatsit = whatsitkeys }
local messyhack    = table.tohash { -- temporary solution
    nodecodes.attributelist,
    nodecodes.attribute,
    nodecodes.action, -- hm
}

setmetatableindex(keys,function(t,k)
    local v = (k == "attributelist" or k == nodecodes.attributelist) and { } or getfields(k)
    if messyhack[k] then
        for i=1,#v do
            if v[i] == "subtype" then
                remove(v,i)
                break
            end
        end
    end
    if v[ 0] then v[#v+1] = "next" v[ 0] = nil end
    if v[-1] then v[#v+1] = "prev" v[-1] = nil end
    sort(v)
    t[k] = v
    return v
end)

setmetatableindex(whatsitkeys,function(t,k)
    local v = getfields(whatsit_code,k)
    if v[ 0] then v[#v+1] = "next" v[ 0] = nil end
    if v[-1] then v[#v+1] = "prev" v[-1] = nil end
    sort(v)
    t[k] = v
    return v
end)

local function nodefields(n)
    n = tonode(n)
    local id = n.id
    if id == whatsit_code then
        return whatsitkeys[n.subtype]
    else
        return keys[id]
    end
end

nodes.keys   = keys       -- [id][subtype]
nodes.fields = nodefields -- (n)

if not nodes.count then

    local type = type

    local direct   = node.direct
    local todirect = direct.tovaliddirect
    local tonode   = direct.tonode

    local count  = direct.count
    local length = direct.length
    local slide  = direct.slide

    function node.count(id,first,last)
        return count(id,first and todirect(first), last and todirect(last) or nil)
    end

    function node.length(first,last)
        return length(first and todirect(first), last and todirect(last) or nil)
    end

    function node.slide(n)
        if n then
            n = slide(todirect(n))
            if n then
                return tonode(n)
            end
        end
        return nil
    end

    local hyphenating = direct.hyphenating
    local ligaturing  = direct.ligaturing
    local kerning     = direct.kerning

    -- kind of inconsistent

    function node.hyphenating(first,last)
        if first then
            local h, t = hyphenating(todirect(first), last and todirect(last) or nil)
            return h and tonode(h) or nil, t and tonode(t) or nil, true
        else
            return nil, false
        end
    end

    function node.ligaturing(first,last)
        if first then
            local h, t = ligaturing(todirect(first), last and todirect(last) or nil)
            return h and tonode(h) or nil, t and tonode(t) or nil, true
        else
            return nil, false
        end
    end

    function node.kerning(first,last)
        if first then
            local h, t = kerning(todirect(first), last and todirect(last) or nil)
            return h and tonode(h) or nil, t and tonode(t) or nil, true
        else
            return nil, false
        end
     end

    local protect_glyph    = direct.protect_glyph
    local unprotect_glyph  = direct.unprotect_glyph
    local protect_glyphs   = direct.protect_glyphs
    local unprotect_glyphs = direct.unprotect_glyphs

    function node.protect_glyphs(first,last)
        protect_glyphs(todirect(first), last and todirect(last) or nil)
    end

    function node.unprotect_glyphs(first,last)
        unprotect_glyphs(todirect(first), last and todirect(last) or nil)
    end

    function node.protect_glyph(first)
        protect_glyph(todirect(first))
    end

    function node.unprotect_glyph(first)
        unprotect_glyph(todirect(first))
    end

    local flatten_discretionaries = direct.flatten_discretionaries
    local check_discretionaries   = direct.check_discretionaries
    local check_discretionary     = direct.check_discretionary

    function node.flatten_discretionaries(first)
        local h, count = flatten_discretionaries(todirect(first))
        return tonode(h), count
    end

    function node.check_discretionaries(n)
        check_discretionaries(todirect(n))
    end

    function node.check_discretionary(n)
        check_discretionary(todirect(n))
    end

    local hpack         = direct.hpack
    local vpack         = direct.vpack
    local list_to_hlist = direct.mlist_to_hlist

    function node.hpack(head,...)
        local h, badness = hpack(head and todirect(head) or nil,...)
        return tonode(h), badness
    end

    function node.vpack(head,...)
        local h, badness = vpack(head and todirect(head) or nil,...)
        return tonode(h), badness
    end

    function node.mlist_to_hlist(head,...)
        return tonode(mlist_to_hlist(head and todirect(head) or nil,...))
    end

    local end_of_math    = direct.end_of_math
    local find_attribute = direct.find_attribute
    local first_glyph    = direct.first_glyph

    function node.end_of_math(n)
        if n then
            n = end_of_math(todirect(n))
            if n then
                return tonode(n)
            end
        end
        return nil
    end

    function node.find_attribute(n,a)
        if n then
            local v, n = find_attribute(todirect(n),a)
            if n then
                return v, tonode(n)
            end
        end
        return nil
    end

    function node.first_glyph(first,last)
        local n = first_glyph(todirect(first), last and todirect(last) or nil)
        return n and tonode(n) or nil
    end

    local dimensions      = direct.dimensions
    local rangedimensions = direct.rangedimensions
    local effective_glue  = direct.effective_glue

    function node.dimensions(a,b,c,d,e)
        if type(a) == "userdata" then
            a = todirect(a)
            if type(b) == "userdata" then
                b = todirect(b)
            end
            return dimensions(a,b)
        else
            d = todirect(d)
            if type(e) == "userdata" then
                e = todirect(e)
            end
            return dimensions(a,b,c,d,e)
        end
        return 0, 0, 0
    end

    function node.rangedimensions(parent,first,last)
        return rangedimenensions(todirect(parent),todirect(first),last and todirect(last))
    end

    function node.effective_glue(list,parent)
        return effective_glue(list and todirect(list) or nil,parent and todirect(parent) or nil)
    end

    local uses_font            = direct.uses_font
    local has_glyph            = direct.has_glyph
    local protrusion_skippable = direct.protrusion_skippable
    local prepend_prevdepth    = direct.prepend_prevdepth
    local make_extensible      = direct.make_extensible

    function node.uses_font(n,f)
        return uses_font(todirect(n),f)
    end

    function node.has_glyph(n)
        return has_glyph(todirect(n))
    end

    function node.protrusion_skippable(n)
        return protrusion_skippable(todirect(n))
    end

    function node.prepend_prevdepth(n)
        local n, d = prepend_prevdepth(todirect(n))
        return tonode(n), d
    end

    function node.make_extensible(...)
        local n = make_extensible(...)
        return n and tonode(n) or nil
    end

    local last_node = direct.last_node

    function node.last_node()
        local n = last_node()
        return n and tonode(n) or nil
    end

    local is_zero_glue = direct.is_zero_glue
    local getglue      = direct.getglue
    local setglue      = direct.setglue

    function node.is_zero_glue(n)
        return is_zero_glue(todirect(n))
    end

    function node.get_glue(n)
        return get_glue(todirect(n))
    end

    function node.set_glue(n)
        return set_glue(todirect(n))
    end

end