2016-01-12 16:26:00

1 files changed, 685 insertions, 0 deletions

diff --git a/tex/context/base/mkiv/node-met.lua b/tex/context/base/mkiv/node-met.lua
new file mode 100644
index 000000000..5c6e18bd3
--- /dev/null
+++ b/tex/context/base/mkiv/node-met.lua
@@ -0,0 +1,685 @@
+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.
+
+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
+
+----- gonuts               = type(node.direct) == "table"
+-----.gonuts               = gonuts
+
+local nodecodes            = nodes.nodecodes
+local hlist_code           = nodecodes.hlist
+local vlist_code           = nodecodes.vlist
+
+nodes.tostring             = node.tostring or tostring
+nodes.copy                 = node.copy
+nodes.copy_list            = node.copy_list
+nodes.delete               = node.delete
+nodes.dimensions           = node.dimensions
+nodes.end_of_math          = node.end_of_math
+nodes.flush_list           = node.flush_list
+nodes.flush_node           = node.flush_node
+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.slide                = node.slide
+nodes.vpack                = node.vpack
+nodes.fields               = node.fields
+nodes.is_node              = node.is_node
+
+nodes.first_glyph          = node.first_glyph
+nodes.has_glyph            = node.has_glyph or node.first_glyph
+
+nodes.current_attr         = node.current_attr
+nodes.do_ligature_n        = node.do_ligature_n
+nodes.has_field            = node.has_field
+nodes.last_node            = node.last_node
+nodes.usedlist             = node.usedlist
+nodes.protrusion_skippable = node.protrusion_skippable
+nodes.write                = node.write
+
+nodes.has_attribute        = node.has_attribute
+nodes.set_attribute        = node.set_attribute
+nodes.unset_attribute      = node.unset_attribute
+
+nodes.protect_glyphs       = node.protect_glyphs
+nodes.protect_glyph        = node.protect_glyph
+nodes.unprotect_glyphs     = node.unprotect_glyphs
+nodes.kerning              = node.kerning
+nodes.ligaturing           = node.ligaturing
+nodes.mlist_to_hlist       = node.mlist_to_hlist
+
+nodes.effective_glue       = node.effective_glue
+
+-- if not gonuts or not node.getfield then
+--     node.getfield = metatable.__index
+--     node.setfield = metatable.__newindex
+-- end
+
+nodes.tonode = function(n) return n end
+nodes.tonut  = function(n) return n end
+
+local getfield          = node.getfield
+local setfield          = node.setfield
+
+local getattr           = node.get_attribute or node.has_attribute or getfield
+local setattr           = setfield
+
+local getnext           = node.getnext    or function(n) return getfield(n,"next")    end
+local getprev           = node.getprev    or function(n) return getfield(n,"prev")    end
+local getid             = node.getid      or function(n) return getfield(n,"id")      end
+local getchar           = node.getchar    or function(n) return getfield(n,"char")    end
+local getfont           = node.getfont    or function(n) return getfield(n,"font")    end
+local getsubtype        = node.getsubtype or function(n) return getfield(n,"subtype") end
+local getlist           = node.getlist    or function(n) return getfield(n,"list")    end
+local getleader         = node.getleader  or function(n) return getfield(n,"leader")  end
+
+nodes.getfield          = getfield
+nodes.getattr           = getattr
+
+nodes.setfield          = setfield
+nodes.setattr           = setattr
+
+nodes.getnext           = getnext
+nodes.getprev           = getprev
+nodes.getid             = getid
+nodes.getchar           = getchar
+nodes.getfont           = getfont
+nodes.getsubtype        = getsubtype
+nodes.getlist           = getlist
+nodes.getleader         = getleader
+
+nodes.getbox            = node.getbox  or tex.getbox
+nodes.setbox            = node.setbox  or tex.setbox
+nodes.getskip           = node.getskip or tex.get
+
+local n_new_node        = nodes.new
+local n_free_node       = nodes.free
+local n_setfield        = nodes.setfield
+local n_getfield        = nodes.getfield
+local n_getnext         = nodes.getnext
+local n_getprev         = nodes.getprev
+local n_getid           = nodes.getid
+local n_getlist         = nodes.getlist
+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_free_node(t)
+        t = nil
+    else
+        n_setfield(t,"next",nil)
+        n_setfield(t,"prev",nil)
+    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_setfield(new,"next",next)
+        n_setfield(next,"prev",new)
+    end
+    if prev then
+        n_setfield(new,"prev",prev)
+        n_setfield(prev,"next",new)
+    end
+    if head then
+        if head == current then
+            head = new
+        end
+        n_free_node(current)
+        return head, new
+    else
+        n_free_node(current)
+        return new
+    end
+end
+
+local function count(stack,flat)
+    local n = 0
+    while stack do
+        local id = n_getid(stack)
+        if not flat and id == hlist_code or id == vlist_code then
+            local list = n_getlist(stack)
+            if list then
+                n = n + 1 + count(list) -- self counts too
+            else
+                n = n + 1
+            end
+        else
+            n = n + 1
+        end
+        stack = n_getnext(stack)
+    end
+    return n
+end
+
+nodes.count = count
+
+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_setfield(last,"next",next)
+                n_setfield(next,"prev",last)
+            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_setfield(tail,"next",li)
+                n_setfield(li,"prev",tail)
+            else
+                head = li
+            end
+            tail = n_slide(li)
+        end
+    end
+    return head, tail
+end
+
+--[[
+<p>At some point we ran into a problem that the glue specification
+of the zeropoint dimension was overwritten when adapting a glue spec
+node. This is a side effect of glue specs being shared. After a
+couple of hours tracing and debugging Taco and I came to the
+conclusion that it made no sense to complicate the spec allocator
+and settled on a writable flag. This all is a side effect of the
+fact that some glues use reserved memory slots (with the zeropoint
+glue being a noticeable one). So, next we wrap this into a function
+and hide it for the user. And yes, LuaTeX now gives a warning as
+well.</p>
+]]--
+
+-- writable will go away
+
+function nodes.writable_spec(n) -- not pool
+    local spec = n_getfield(n,"spec")
+    if not spec then
+        spec = n_copy_node(glue_spec)
+        n_setfield(n,"spec",spec)
+    elseif not n_getfield(spec,"writable") then
+        spec = n_copy_node(spec)
+        n_setfield(n,"spec",spec)
+    end
+    return spec
+end
+
+function nodes.copy_spec(old,free) -- also frees
+    if not old then
+        return n_new_node("glue_spec")
+    else
+        local new = n_copy_node(old)
+        if free and old.writable then
+            free_node(old)
+        end
+        return new
+    end
+end
+
+function nodes.free_spec(old)
+    if not old then
+        -- skip
+    elseif old.writable then
+        free_node(old)
+    else
+        -- skip
+    end
+end
+
+-- if gonuts then
+
+function nodes.reference(n)
+    return n and tonut(n) or "<none>"
+end
+
+-- else
+--
+--     local left, space = lpeg.P("<"), lpeg.P(" ")
+--
+--     local reference = left * (1-left)^0 * left * space^0 * lpeg.C((1-space)^0)
+--
+--     function nodes.reference(n)
+--         return n and lpegmatch(reference,tostring(n)) or "<none>"
+--     end
+--
+-- 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_setfield(tail,"next",n2)
+        n_setfield(n2,"prev",tail)
+        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_setfield(t,"next",head)
+                n_setfield(head,"prev",t)
+            end
+            head = h
+        end
+        local t = n_find_tail(n)
+        n_setfield(t,"next",head)
+        n_setfield(head,"prev",t)
+    else
+        local head
+        for i=2,multiplier do
+            local c = n_copy_node(n)
+            if head then
+                n_setfield(c,"next",head)
+                n_setfield(head,"prev",c)
+            end
+            head = c
+        end
+        n_setfield(n,"next",head)
+        n_setfield(head,"prev",n)
+    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_getfield(tail,"prev")
+            n_free_node(tail) -- can become flushlist/flushnode
+            if prev then
+                tail = prev
+            else
+                return nil
+            end
+        end
+        if tail then
+            n_setfield(tail,"next",nil)
+            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_setfield(secondtail,"next",firsttail)
+            n_setfield(firsttail,"prev",ltail)
+            n_setfield(prev,"next",second)
+            n_setfield(second,"prev",prev)
+            return first
+        else
+            local secondtail = n_find_tail(second)
+            n_setfield(secondtail,"next",first)
+            n_setfield(first,"prev",ltail)
+            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_free_node(head) -- can become flushlist/flushnode
+            if second then
+                head = second
+            else
+                return nil
+            end
+        end
+        if head then
+            n_setfield(head,"prev",nil)
+            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_setfield(first,"next",second)
+            n_setfield(second,"prev",first)
+            n_setfield(secondtail,"next",next)
+            n_setfield(next,"prev",secondtail)
+        else
+            n_setfield(first,"next",second)
+            n_setfield(second,"prev",first)
+        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 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_setfield(t,"next",head)
+                    n_setfield(head,"prev",t)
+                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_setfield(head,"next",c)
+                    n_setfield(c,"prev",head)
+                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_setfield(first,"prev",current)
+        n_setfield(current,"next",first)
+        first = current
+        current = next
+    end
+    n_setfield(first,"prev",nil)
+    n_setfield(last,"next",nil)
+    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.gluespec,
+    nodecodes.action,
+}
+
+table.setmetatableindex(keys,function(t,k)
+    local v = 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)
+
+table.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)