Source Browser ?

    if 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.tostring               = node.tostring or tostring
74nodes.copy                   = node.copy
75nodes.copynode               = node.copy
76nodes.copylist               = node.copy_list
77nodes.delete                 = node.delete
78nodes.dimensions             = node.dimensions
79nodes.rangedimensions        = node.rangedimensions
80nodes.endofmath              = node.end_of_math
81nodes.flush                  = node.flush_node
82nodes.flushnode              = node.flush_node
83nodes.flushlist              = node.flush_list
84nodes.free                   = node.free
85nodes.insertafter            = node.insert_after
86nodes.insertbefore           = node.insert_before
87nodes.hpack                  = node.hpack
88nodes.new                    = node.new
89nodes.tail                   = node.tail
90nodes.traverse               = node.traverse
91nodes.traverseid             = node.traverse_id
92nodes.traversechar           = node.traverse_char
93nodes.traverseglyph          = node.traverse_glyph
94nodes.traverselist           = node.traverse_list
95nodes.slide                  = node.slide
96nodes.vpack                  = node.vpack
97nodes.fields                 = node.fields
98nodes.isnode                 = node.is_node
99nodes.isdirect               = node.is_direct
100nodes.isnut                  = node.is_direct
101nodes.setglue                = node.setglue
102nodes.usesfont               = node.uses_font
103
104nodes.firstglyph             = node.first_glyph
105nodes.hasglyph               = node.has_glyph
106
107nodes.currentattributes      = node.current_attributes or node.current_attr
108nodes.hasfield               = node.has_field
109nodes.last_node              = node.last_node
110nodes.usedlist               = node.usedlist
111nodes.protrusionskippable    = node.protrusion_skippable
112nodes.checkdiscretionaries   = node.check_discretionaries
113nodes.write                  = node.write
114nodes.flattendiscretionaries = node.flatten_discretionaries
115
116nodes.count                  = node.count
117nodes.length                 = node.length
118
119nodes.hasattribute           = node.has_attribute
120nodes.setattribute           = node.set_attribute
121nodes.findattribute          = node.find_attribute
122nodes.unsetattribute         = node.unset_attribute
123
124nodes.protectglyph           = node.protect_glyph
125nodes.protectglyphs          = node.protect_glyphs
126nodes.unprotectglyph         = node.unprotect_glyph
127nodes.unprotectglyphs        = node.unprotect_glyphs
128nodes.kerning                = node.kerning
129nodes.ligaturing             = node.ligaturing
130nodes.hyphenating            = node.hyphenating
131nodes.mlisttohlist           = node.mlist_to_hlist
132
133nodes.effectiveglue          = node.effective_glue
134nodes.getglue                = node.getglue
135nodes.setglue                = node.setglue
136nodes.iszeroglue             = node.iszeroglue
137
138nodes.tonode = function(n) return n end
139nodes.tonut  = function(n) return n end
140
141-- These are never used in \CONTEXT, only as a gimmick in node operators
142-- so we keep them around.
143
144local n_getfield = node.getfield
145local n_getattr  = node.get_attribute
146
147local n_setfield = node.setfield
148local n_setattr  = n_setfield
149
150nodes.getfield = n_getfield
151nodes.setfield = n_setfield
152nodes.getattr  = n_getattr
153nodes.setattr  = n_setattr
154nodes.takeattr = nodes.unsetattribute
155
156local function n_getid     (n) return n_getfield(n,"id")      end
157local function n_getsubtype(n) return n_getfield(n,"subtype") end
158
159nodes.getid      = n_getid
160nodes.getsubtype = n_getsubtype
161
162local function n_getchar(n)   return n_getfield(n,"char")    end
163local function n_setchar(n,c) return n_setfield(n,"char",c)  end
164local function n_getfont(n)   return n_getfield(n,"font")    end
165local function n_setfont(n,f) return n_setfield(n,"font",f)  end
166
167nodes.getchar = n_getchar
168nodes.setchar = n_setchar
169nodes.getfont = n_getfont
170nodes.setfont = n_setfont
171
172local function n_getlist  (n)   return n_getfield(n,"list")     end
173local function n_setlist  (n,l) return n_setfield(n,"list",l)   end
174local function n_getleader(n)   return n_getfield(n,"leader")   end
175local function n_setleader(n,l) return n_setfield(n,"leader",l) end
176
177nodes.getlist   = n_getlist
178nodes.setlist   = n_setlist
179nodes.getleader = n_getleader
180nodes.setleader = n_setleader
181
182local function n_getnext(n)       return n_getfield(n,"next")    end
183local function n_setnext(n,nn)    return n_setfield(n,"next",nn) end
184local function n_getprev(n)       return n_getfield(n,"prev")    end
185local function n_setprev(n,pp)    return n_setfield(n,"prev",pp) end
186local function n_getboth(n)       return n_getfield(n,"prev"),    n_getfield(n,"next")    end
187local function n_setboth(n,pp,nn) return n_setfield(n,"prev",pp), n_setfield(n,"next",nn) end
188
189nodes.getnext = n_getnext
190nodes.setnext = n_setnext
191nodes.getprev = n_getprev
192nodes.setprev = n_setprev
193nodes.getboth = n_getboth
194nodes.setboth = n_setboth
195
196local function n_setlink(...)
197    -- not that fast but not used often anyway
198    local h = nil
199    for i=1,select("#",...) do
200        local n = select(i,...)
201        if not n then
202            -- go on
203        elseif h then
204            n_setfield(h,"next",n)
205            n_setfield(n,"prev",h)
206        else
207            h = n
208        end
209    end
210    return h
211end
212
213nodes.setlink = n_setlink
214
215nodes.getbox  = node.getbox or tex.getbox
216nodes.setbox  = node.setbox or tex.setbox
217
218local n_flushnode    = nodes.flush
219local n_copynode     = nodes.copy
220local n_copylist     = nodes.copylist
221local n_findtail     = nodes.tail
222local n_insertafter  = nodes.insertafter
223local n_insertbefore = nodes.insertbefore
224local n_slide        = nodes.slide
225
226local n_remove_node   = node.remove -- not yet nodes.remove
227
228local function remove(head,current,free_too)
229    local t = current
230    head, current = n_remove_node(head,current)
231    if not t then
232        -- forget about it
233    elseif free_too then
234        n_flushnode(t)
235        t = nil
236    else
237        n_setboth(t)
238    end
239    return head, current, t
240end
241
242nodes.remove = remove
243
244function nodes.delete(head,current)
245    return remove(head,current,true)
246end
247
248-- local h, c = nodes.replace(head,current,new)
249-- local c = nodes.replace(false,current,new)
250-- local c = nodes.replace(current,new)
251--
252-- todo: check for new.next and find tail
253
254function nodes.replace(head,current,new) -- no head returned if false
255    if not new then
256        head, current, new = false, head, current
257--         current, new = head, current
258    end
259    local prev = n_getprev(current)
260    local next = n_getnext(current)
261    if next then
262        n_setlink(new,next)
263    end
264    if prev then
265        n_setlink(prev,new)
266    end
267    if head then
268        if head == current then
269            head = new
270        end
271        n_flushnode(current)
272        return head, new
273    else
274        n_flushnode(current)
275        return new
276    end
277end
278
279-- nodes.countall : see node-nut.lua
280
281function nodes.append(head,current,...)
282    for i=1,select("#",...) do
283        head, current = n_insertafter(head,current,(select(i,...)))
284    end
285    return head, current
286end
287
288function nodes.prepend(head,current,...)
289    for i=1,select("#",...) do
290        head, current = n_insertbefore(head,current,(select(i,...)))
291    end
292    return head, current
293end
294
295function nodes.linked(...)
296    local head, last
297    for i=1,select("#",...) do
298        local next = select(i,...)
299        if next then
300            if head then
301                n_setlink(last,next)
302            else
303                head = next
304            end
305            last = n_findtail(next) -- we could skip the last one
306        end
307    end
308    return head
309end
310
311function nodes.concat(list) -- consider tail instead of slide
312    local head, tail
313    for i=1,#list do
314        local li = list[i]
315        if li then
316            if head then
317                n_setlink(tail,li)
318            else
319                head = li
320            end
321            tail = n_slide(li)
322        end
323    end
324    return head, tail
325end
326
327function nodes.reference(n)
328    return n and tonut(n) or "<none>"
329end
330
331-- Here starts an experiment with metatables. Of course this only works with nodes
332-- wrapped in userdata with a metatable.
333--
334-- Nodes are kind of special in the sense that you need to keep an eye on creation
335-- and destruction. This is quite natural if you consider that changing the content
336-- of a node would also change any copy (or alias). As there are too many pitfalls
337-- we don't have this kind of support built in \LUATEX, which means that macro
338-- packages are free to provide their own. One can even use local variants.
339--
340-- n1 .. n2 : append nodes, no copies
341-- n1 * 5   : append 4 copies of nodes
342-- 5 + n1   : strip first 5 nodes
343-- n1 - 5   : strip last 5 nodes
344-- n1 + n2  : inject n2 after first of n1
345-- n1 - n2  : inject n2 before last of n1
346-- n1^2     : two copies of nodes (keep orginal)
347-- - n1     : reverse nodes
348-- n1/f     : apply function to nodes
349
350-- local s = nodes.typesetters.tonodes
351--
352-- local function w(lst)
353--     context.dontleavehmode()
354--     context(lst)
355--     context.par()
356-- end
357--
358-- local n1 = s("a")
359-- local n2 = s("b")
360-- local n3 = s("c")
361-- local n4 = s("d")
362-- local n5 = s("e")
363-- local n6 = s("f")
364-- local n7 = s("g")
365--
366-- local n0 = n1 .. (n2 * 10).. n3 .. (5 * n4) .. n5 .. ( 5 * n6 ) .. n7 / function(n) n.char = string.byte("!") return n end
367--
368-- w(#n0)
369--
370-- w(n0)
371--
372-- local n1 = s("a") * 10
373-- local n2 = s("b") * 10
374--
375-- local n0 = ((5 + n1) .. (n2 - 5) )
376-- local n0 = - n0
377--
378-- local n0 = nil .. n0^3 .. nil
379--
380-- w(n0)
381--
382-- w ( s("a") + s("b") ) w ( s("a") + 4*s("b") ) w ( 4*s("a") + s("b") ) w ( 4*s("a") + 4*s("b") )
383-- w ( s("a") - s("b") ) w ( s("a") - 4*s("b") ) w ( 4*s("a") - s("b") ) w ( 4*s("a") - 4*s("b") )
384
385local n_remove_node = nodes.remove
386
387metatable.__concat = function(n1,n2) -- todo: accept nut on one end
388    if not n1 then
389        return n2
390    elseif not n2 then
391        return n1
392    elseif n1 == n2 then
393        -- or abort
394        return n2 -- or n2 * 2
395    else
396        local tail = n_findtail(n1)
397        n_setlink(tail,n2)
398        return n1
399    end
400end
401
402metatable.__mul = function(n,multiplier)
403    if type(multiplier) ~= "number" then
404        n, multiplier = multiplier, n
405    end
406    if multiplier <= 1 then
407        return n
408    elseif n_getnext(n) then
409        local head
410        for i=2,multiplier do
411            local h = n_copylist(n)
412            if head then
413                local t = n_findtail(h)
414                n_setlink(t,head)
415            end
416            head = h
417        end
418        local t = n_findtail(n)
419        n_setlink(t,head)
420    else
421        local head
422        for i=2,multiplier do
423            local c = n_copynode(n)
424            if head then
425                n_setlink(c,head)
426            end
427            head = c
428        end
429        n_setlink(n,head)
430    end
431    return n
432end
433
434metatable.__sub = function(first,second)
435    if type(second) == "number" then
436        local tail = n_findtail(first)
437        for i=1,second do
438            local prev = n_getprev(tail)
439            n_flushnode(tail) -- can become flushlist/flushnode
440            if prev then
441                tail = prev
442            else
443                return nil
444            end
445        end
446        if tail then
447            n_setnext(tail)
448            return first
449        else
450            return nil
451        end
452    else
453       -- aaaaa - bbb => aaaabbba
454        local firsttail = n_findtail(first)
455        local prev = n_getprev(firsttail)
456        if prev then
457            local secondtail = n_findtail(second)
458            n_setlink(secondtail,firsttail)
459            n_setlink(prev,second)
460            return first
461        else
462            local secondtail = n_findtail(second)
463            n_setlink(secondtail,first)
464            return second
465        end
466    end
467end
468
469metatable.__add = function(first,second)
470    if type(first) == "number" then
471        local head = second
472        for i=1,first do
473            local second = n_getnext(head)
474            n_flushnode(head) -- can become flushlist/flushnode
475            if second then
476                head = second
477            else
478                return nil
479            end
480        end
481        if head then
482            n_setprev(head)
483            return head
484        else
485            return nil
486        end
487    else
488       -- aaaaa + bbb => abbbaaaa
489        local next = n_getnext(first)
490        if next then
491            local secondtail = n_findtail(second)
492            n_setlink(first,second)
493            n_setlink(secondtail,next)
494        else
495            n_setlink(first,second)
496        end
497        return first
498    end
499end
500
501metatable.__len = function(current)
502    local length = 0
503    while current do
504        current = n_getnext(current)
505        length = length + 1
506    end
507    return length
508end
509
510metatable.__div = function(list,action)
511    return action(list) or list -- always a value
512end
513
514metatable.__pow = function(n,multiplier)
515    local tail = n
516    local head = nil
517    if n_getnext(n) then
518        if multiplier == 1 then
519            head = n_copylist(n)
520        else
521            for i=1,multiplier do
522                local h = n_copylist(n)
523                if head then
524                    local t = n_findtail(h)
525                    n_setlink(t,head)
526                end
527                head = h
528            end
529        end
530    else
531        if multiplier == 1 then
532            head = n_copynode(n)
533        else
534            for i=2,multiplier do
535                local c = n_copynode(n)
536                if head then
537                    n_setlink(head,c)
538                end
539                head = c
540            end
541        end
542    end
543    -- todo: tracing
544    return head
545end
546
547metatable.__unm = function(head)
548    local last = head
549    local first = head
550    local current = n_getnext(head)
551    while current do
552        local next = n_getnext(current)
553        n_setlink(current,first)
554        first = current
555        current = next
556    end
557    n_setprev(first)
558    n_setnext(last)
559    return first
560end
561