From 8d8d528d2ad52599f11250cfc567fea4f37f2a8b Mon Sep 17 00:00:00 2001 From: Context Git Mirror Bot Date: Tue, 12 Jan 2016 17:15:07 +0100 Subject: 2016-01-12 16:26:00 --- tex/context/base/mkiv/node-met.lua | 685 +++++++++++++++++++++++++++++++++++++ 1 file changed, 685 insertions(+) create mode 100644 tex/context/base/mkiv/node-met.lua (limited to 'tex/context/base/mkiv/node-met.lua') 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 + +--[[ +

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.

+]]-- + +-- 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 "" +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 "" +-- 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) -- cgit v1.2.3