Source Browser ?

1if not modules then modules = { } end modules ['node-MET'] = {
2    version   = 1.001,
3    comment   = "companion to node-ini.mkiv",
4    author    = "Hans Hagen, PRAGMA-ADE, Hasselt NL",
5    copyright = "PRAGMA ADE / ConTeXt Development Team",
6    license   = "see context related readme files"
7}
8
9-- This is an experimental module. Don't use nuts for generic code, at least not till
10-- the regular code is proven stable. No support otherwise.
11
12-- luatex: todo: copylist should return h, t
13-- todo: see if using insertbefore and insertafter makes sense here
14
15-- This file is a side effect of the \LUATEX\ speed optimization project of Luigi
16-- Scarso and me. As \CONTEXT\ spends over half its time in \LUA, we though that
17-- using \LUAJIT\ could improve performance. We've published some of our experiences
18-- elsewhere, but to summarize: \LUAJITTEX\ benefits a lot from the faster virtual
19-- machine, but when jit is turned of we loose some again. We experimented with
20-- ffi (without messing up the \CONTEXT\ code too much) but there we also lost more
21-- than we gained (mostly due to lack of compatible userdata support: it's all or
22-- nothing). This made us decide to look into the \LUA||\TEX\ interfacing and by
23-- profiling and careful looking at the (of course then still beta source code) we
24-- could come up with some improvements. The first showed up in 0.75 and we've more
25-- on the agenda for 0.80. Although some interfaces could be sped up significantly
26-- in practice we're only talking of 5||10\% on a \CONTEXT\ run and maybe more when
27-- complex and extensive node list manipulations happens (we're talking of hundreds
28-- of millions cross boundary calls then for documents of hundreds pages). One of the
29-- changes in the \CONTEXT\ code base is that we went from indexed access to nodes to
30-- function calls (in principle faster weren't it that the accessors need to do more
31-- checking which makes them slower) and from there to optimizing these calls as well
32-- as providing fast variants for well defined situations. At first optimizations were
33-- put in a separate \type {node.fast} table although some improvements could be
34-- ported to the main node functions. Because we got the feeling that more gain was
35-- possible (especially when using more complex fonts and \MKIV\ functionality) we
36-- eventually abandoned this approach and dropped the \type {fast} table in favour of
37-- another hack. In the process we had done lots of profiling and testing so we knew
38-- where time was wasted,
39--
40-- As lots of testing and experimenting was part of this project, I could not have
41-- done without stacks of new \CD s and \DVD s. This time Porcupine Tree, No-Man
42-- and Archive were came to rescue.
43--
44-- It all started with testing performance of:
45--
46-- node.getfield = metatable.__index
47-- node.setfield = metatable.__newindex
48
49local type, select = type, select
50local setmetatableindex = table.setmetatableindex
51
52-- First we get the metatable of a node:
53
54local metatable = nil
55
56do
57    local glyph = node.new("glyph",0)
58    metatable = getmetatable(glyph)
59    node.free(glyph)
60end
61
62-- statistics.tracefunction(node,       "node",       "getfield","setfield")
63-- statistics.tracefunction(node.direct,"node.direct","getfield","setfield")
64
65-- We start with some helpers and provide all relevant basic functions in the
66-- node namespace as well.
67
68nodes                    = nodes or { }
69local nodes              = nodes
70
71local nodecodes          = nodes.nodecodes
72
73nodes.copy               = node.copy
74nodes.copylist           = node.copylist
75nodes.copy_node          = node.copy
76nodes.currentattributes  = node.currentattributes
77nodes.remove             = node.remove
78nodes.fields             = node.fields
79nodes.flush              = node.flushnode
80nodes.flushlist          = node.flushlist
81nodes.flushnode          = node.flushnode
82nodes.getattribute       = node.getattribute
83nodes.hasattribute       = node.hasattribute
84nodes.hasfield           = node.hasfield
85nodes.insertafter        = node.insertafter
86nodes.insertbefore       = node.insertbefore
87-----.appendafter        = node.appendafter
88-----.prependbefore      = node.prependbefore
89nodes.isnode             = node.isnode
90nodes.isdirect           = node.isdirect
91nodes.isnut              = node.isdirect
92nodes.new                = node.new
93nodes.setattribute       = node.setattribute
94nodes.tail               = node.tail
95nodes.tostring           = node.tostring or tostring
96nodes.traverse           = node.traverse
97nodes.traverseid         = node.traverseid
98nodes.unsetattribute     = node.unsetattribute
99nodes.write              = node.write
100nodes.usedlist           = node.usedlist
101
102nodes.getpropertiestable = node.get_properties_table
103nodes.getproperty        = node.getproperty
104nodes.setproperty        = node.setproperty
105
106-----.show               = node.show
107nodes.serialized         = node.serialized
108
109-- nodes.usedlist
110-- nodes.inuse
111-- nodes.instock
112-- nodes.type
113-- nodes.types
114-- nodes.subtypes
115-- nodes.values
116-- nodes.id
117
118-- nodes.tonode = function(n) return n end
119-- nodes.tonut  = function(n) return n end
120
121-- These are never used in \CONTEXT, only as a gimmick in node operators
122-- so we keep them around.
123--
124-- Fot now I keep them in \LMTX\ but they will go away!
125
126local n_getfield = node.getfield
127local n_getattr  = node.getattribute
128
129local n_setfield = node.setfield
130local n_setattr  = n_setfield
131
132nodes.getfield = n_getfield
133nodes.setfield = n_setfield
134nodes.getattr  = n_getattr
135nodes.setattr  = n_setattr
136nodes.takeattr = nodes.unsetattribute

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

141nodes.getid      = n_getid
142nodes.getsubtype = n_getsubtype
143
144local function n_getchar(n)   return n_getfield(n,"char")    end
145local function n_setchar(n,c) return n_setfield(n,"char",c)  end
146local function n_getfont(n)   return n_getfield(n,"font")    end
147local function n_setfont(n,f) return n_setfield(n,"font",f)  end
148
149nodes.getchar = n_getchar
150nodes.setchar = n_setchar
151nodes.getfont = n_getfont
152nodes.setfont = n_setfont
153
154local function n_getlist  (n)   return n_getfield(n,"list")     end
155local function n_setlist  (n,l) return n_setfield(n,"list",l)   end
156local function n_getleader(n)   return n_getfield(n,"leader")   end
157local function n_setleader(n,l) return n_setfield(n,"leader",l) end
158
159nodes.getlist   = n_getlist
160nodes.setlist   = n_setlist
161nodes.getleader = n_getleader
162nodes.setleader = n_setleader
163
164local function n_getnext(n)       return n_getfield(n,"next")    end
165local function n_setnext(n,nn)    return n_setfield(n,"next",nn) end
166local function n_getprev(n)       return n_getfield(n,"prev")    end
167local function n_setprev(n,pp)    return n_setfield(n,"prev",pp) end
168local function n_getboth(n)       return n_getfield(n,"prev"),    n_getfield(n,"next")    end
169local function n_setboth(n,pp,nn) return n_setfield(n,"prev",pp), n_setfield(n,"next",nn) end
170
171nodes.getnext = n_getnext
172nodes.setnext = n_setnext
173nodes.getprev = n_getprev
174nodes.setprev = n_setprev
175nodes.getboth = n_getboth
176nodes.setboth = n_setboth
177
178local function n_setlink(...)
179    -- not that fast but not used often anyway
180    local h = nil
181    for i=1,select("#",...) do
182        local n = select(i,...)
183        if not n then
184            -- go on
185        elseif h then
186            n_setfield(h,"next",n)
187            n_setfield(n,"prev",h)
188        else
189            h = n
190        end
191    end
192    return h
193end
194
195nodes.setlink = n_setlink
196
197nodes.getbox  = node.getbox or tex.getbox
198nodes.setbox  = node.setbox or tex.setbox
199
200local n_flushnode     = nodes.flushnode
201local n_copy_node     = nodes.copy
202local n_copy_list     = nodes.copylist
203local n_find_tail     = nodes.tail
204local n_insertafter   = nodes.insertafter
205local n_insertbefore  = nodes.insertbefore
206local n_slide         = nodes.slide
207
208local n_remove_node   = node.remove -- not yet nodes.remove
209
210local function remove(head,current,free_too)
211    local t = current
212    head, current = n_remove_node(head,current)
213    if not t then
214        -- forget about it
215    elseif free_too then
216        n_flushnode(t)
217        t = nil
218    else
219        n_setboth(t)
220    end
221    return head, current, t
222end
223
224nodes.remove = remove
225
226function nodes.delete(head,current)
227    return remove(head,current,true)
228end
229
230-- local h, c = nodes.replace(head,current,new)
231-- local c = nodes.replace(false,current,new)
232-- local c = nodes.replace(current,new)
233--
234-- todo: check for new.next and find tail
235
236function nodes.replace(head,current,new) -- no head returned if false
237    if not new then
238        head, current, new = false, head, current
239--         current, new = head, current
240    end
241    local prev = n_getprev(current)
242    local next = n_getnext(current)
243    if next then
244        n_setlink(new,next)
245    end
246    if prev then
247        n_setlink(prev,new)
248    end
249    if head then
250        if head == current then
251            head = new
252        end
253        n_flushnode(current)
254        return head, new
255    else
256        n_flushnode(current)
257        return new
258    end
259end
260
261-- nodes.countall : see node-nut.lua
262
263function nodes.append(head,current,...)
264    for i=1,select("#",...) do
265        head, current = n_insertafter(head,current,(select(i,...)))
266    end
267    return head, current
268end
269
270function nodes.prepend(head,current,...)
271    for i=1,select("#",...) do
272        head, current = n_insertbefore(head,current,(select(i,...)))
273    end
274    return head, current
275end
276
277function nodes.linked(...)
278    local head, last
279    for i=1,select("#",...) do
280        local next = select(i,...)
281        if next then
282            if head then
283                n_setlink(last,next)
284            else
285                head = next
286            end
287            last = n_find_tail(next) -- we could skip the last one
288        end
289    end
290    return head
291end
292
293function nodes.concat(list) -- consider tail instead of slide
294    local head, tail
295    for i=1,#list do
296        local li = list[i]
297        if li then
298            if head then
299                n_setlink(tail,li)
300            else
301                head = li
302            end
303            tail = n_slide(li)
304        end
305    end
306    return head, tail
307end
308
309-- Here starts an experiment with metatables. Of course this only works with nodes
310-- wrapped in userdata with a metatable.
311--
312-- Nodes are kind of special in the sense that you need to keep an eye on creation
313-- and destruction. This is quite natural if you consider that changing the content
314-- of a node would also change any copy (or alias). As there are too many pitfalls
315-- we don't have this kind of support built in \LUATEX, which means that macro
316-- packages are free to provide their own. One can even use local variants.
317--
318-- n1 .. n2 : append nodes, no copies
319-- n1 * 5   : append 4 copies of nodes
320-- 5 + n1   : strip first 5 nodes
321-- n1 - 5   : strip last 5 nodes
322-- n1 + n2  : inject n2 after first of n1
323-- n1 - n2  : inject n2 before last of n1
324-- n1^2     : two copies of nodes (keep orginal)
325-- - n1     : reverse nodes
326-- n1/f     : apply function to nodes
327
328-- local s = nodes.typesetters.tonodes
329--
330-- local function w(lst)
331--     context.dontleavehmode()
332--     context(lst)
333--     context.par()
334-- end
335--
336-- local n1 = s("a")
337-- local n2 = s("b")
338-- local n3 = s("c")
339-- local n4 = s("d")
340-- local n5 = s("e")
341-- local n6 = s("f")
342-- local n7 = s("g")
343--
344-- local n0 = n1 .. (n2 * 10).. n3 .. (5 * n4) .. n5 .. ( 5 * n6 ) .. n7 / function(n) n.char = string.byte("!") return n end
345--
346-- w(#n0)
347--
348-- w(n0)
349--
350-- local n1 = s("a") * 10
351-- local n2 = s("b") * 10
352--
353-- local n0 = ((5 + n1) .. (n2 - 5) )
354-- local n0 = - n0
355--
356-- local n0 = nil .. n0^3 .. nil
357--
358-- w(n0)
359--
360-- w ( s("a") + s("b") ) w ( s("a") + 4*s("b") ) w ( 4*s("a") + s("b") ) w ( 4*s("a") + 4*s("b") )
361-- w ( s("a") - s("b") ) w ( s("a") - 4*s("b") ) w ( 4*s("a") - s("b") ) w ( 4*s("a") - 4*s("b") )
362
363local n_remove_node = nodes.remove
364
365metatable.__concat = function(n1,n2) -- todo: accept nut on one end
366    if not n1 then
367        return n2
368    elseif not n2 then
369        return n1
370    elseif n1 == n2 then
371        -- or abort
372        return n2 -- or n2 * 2
373    else
374        local tail = n_find_tail(n1)
375        n_setlink(tail,n2)
376        return n1
377    end
378end
379
380metatable.__mul = function(n,multiplier)
381    if type(multiplier) ~= "number" then
382        n, multiplier = multiplier, n
383    end
384    if multiplier <= 1 then
385        return n
386    elseif n_getnext(n) then
387        local head
388        for i=2,multiplier do
389            local h = n_copy_list(n)
390            if head then
391                local t = n_find_tail(h)
392                n_setlink(t,head)
393            end
394            head = h
395        end
396        local t = n_find_tail(n)
397        n_setlink(t,head)
398    else
399        local head
400        for i=2,multiplier do
401            local c = n_copy_node(n)
402            if head then
403                n_setlink(c,head)
404            end
405            head = c
406        end
407        n_setlink(n,head)
408    end
409    return n
end
411
412metatable.__sub = function(first,second)
413    if type(second) == "number" then
414        local tail = n_find_tail(first)
415        for i=1,second do
416            local prev = n_getprev(tail)
417            n_flushnode(tail) -- can become flushlist/flushnode
418            if prev then
419                tail = prev
420            else
421                return nil
422            end
423        end
424        if tail then
425            n_setnext(tail)
426            return first
427        else
428            return nil
429        end
430    else
431       -- aaaaa - bbb => aaaabbba
432        local firsttail = n_find_tail(first)
433        local prev = n_getprev(firsttail)
434        if prev then
435            local secondtail = n_find_tail(second)
436            n_setlink(secondtail,firsttail)
437            n_setlink(prev,second)
438            return first
439        else
440            local secondtail = n_find_tail(second)
441            n_setlink(secondtail,first)
442            return second
443        end
444    end
445end
446
447metatable.__add = function(first,second)
448    if type(first) == "number" then
449        local head = second
450        for i=1,first do
451            local second = n_getnext(head)
452            n_flushnode(head) -- can become flushlist/flushnode
453            if second then
454                head = second
455            else
456                return nil
457            end
458        end
459        if head then
460            n_setprev(head)
461            return head
462        else
463            return nil
464        end
465    else
466       -- aaaaa + bbb => abbbaaaa
467        local next = n_getnext(first)
468        if next then
469            local secondtail = n_find_tail(second)
470            n_setlink(first,second)
471            n_setlink(secondtail,next)
472        else
473            n_setlink(first,second)
474        end
475        return first
476    end
477end
478
479metatable.__len = function(current)
480    local length = 0
481    while current do
482        current = n_getnext(current)
483        length = length + 1
484    end
485    return length
486end
487
488metatable.__div = function(list,action)
489    return action(list) or list -- always a value
490end
491
492metatable.__pow = function(n,multiplier)
493    local tail = n
494    local head = nil
495    if n_getnext(n) then
496        if multiplier == 1 then
497            head = n_copy_list(n)
498        else
499            for i=1,multiplier do
500                local h = n_copy_list(n)
501                if head then
502                    local t = n_find_tail(h)
503                    n_setlink(t,head)
504                end
505                head = h
506            end
507        end
508    else
509        if multiplier == 1 then
510            head = n_copy_node(n)
511        else
512            for i=2,multiplier do
513                local c = n_copy_node(n)
514                if head then
515                    n_setlink(head,c)
516                end
517                head = c
518            end
519        end
520    end
521    -- todo: tracing
522    return head
523end
524
525metatable.__unm = function(head)
526    local last = head
527    local first = head
528    local current = n_getnext(head)
529    while current do
530        local next = n_getnext(current)
531        n_setlink(current,first)
532        first = current
533        current = next
534    end
535    n_setprev(first)
536    n_setnext(last)
537    return first
538end
539