mk-nodes.tex /size: 17 Kb    last modification: 2023-12-21 09:43
1% language=us
2
3\startcomponent mk-nodes
4
5\environment mk-environment
6
7\chapter {Nodes and attributes}
8
9\subject{introduction}
10
11Here we will tell a bit about the development of node access in \LUATEX. We
12will also introduce attributes, a feature closely related to nodes. We assume
13that you are somewhat familiar with \TEX's nodes: glyphs, kerns, glue, penalties,
14whatsits and friends.
15
16\subject{tables}
17
18Access to node lists has been implemented rather early in the development because
19we needed it to fulfil the objectives of the Oriental \TEX\ project.  The first
20implementation used nested tables, indexed by number. In that approach, the first
21entry in each node indicated the type in string format. At that time a horizontal
22list looked as follows:
23
24\starttyping
25list = {
26    [1] = "hlist",
27    [2] = 0,
28    ...
29    [8] = {
30        [1] = {
31            [1] = "glyph",
32            ...
33        },
34        [2] = {
35            ...
36        }
37}
38\stoptyping
39
40Processing such lists is rather convenient since we can use the normal table
41iterators. Because in practice only a few entries of a node are accessed, working
42with numbers is no real problem: in slot~1 we have the type, en in the
43case of a horizontal or vertical list, we know that slot~8 is either empty or
44a table. Looping over the list is done with:
45
46\starttyping
47for i, node in ipairs(list) do
48    if node[1] == "glyph" then
49        list[i][5] = string.byte(string.upper(string.char(node[5])))
50    end
51end
52\stoptyping
53
54Node processing code hooks into the box packagers and paragraph builder and
55a few more places. This means that when using the table approach a lot of
56callbacks take place where \TEX\ has to convert to and from \LUA. Apart from
57processing time, we also have to deal with garbage collection then and on an older
58machine with insufficient memory interesting bottlenecks show up. Therefore some
59following optimizations were implemented at the \TEX\ end of the game.
60
61Side note concerning speed: when memory of processing speed is low, runtime can
62increase five to tenfold compared to \PDFTEX\ when one does intensive node
63manipulations. This is due to garbage collection at the \LUA\ end and memory
64(de)allocation at the \TEX\ end. There is not much we can do about that. Interfacing
65has a price and hardware is more powerful than when \TEX\ was written. Processing
66the \TEX\ book using no callbacks is not that much slower than using a traditional
67\TEX\ engine. However, nowadays fonts are more extensive, demands for special
68features more pressing and that comes at a price.
69
70When the list is not changed, the callback function can return the value \type
71{true}. This signals \TEX\ that it can keep the original list. When the list is
72empty, the callback function can return the value \type {false}. This signals
73\TEX\ that the list can be discarded.
74
75In order to minimize conversions and redundant processing, nested lists were
76not passed as table but as a reference. One could expand such a list when
77needed. For instance, when one hooks the same function in the \type
78{hpack_filter} and \type {pre_linebreak_filter} callbacks, this way one can be
79pretty sure that each node is only processed once. Boxed material that is part
80of the paragraph stream first enters the box packers and then already is
81processed before it enters the paragraph callback. Of course one can decide the
82expand the referred sublist and process it again. Keep in mind that we're still
83talking of a table approach, but we're slowly moving away from big conversions.
84
85In principle one can insert and delete nodes in such a list but given that
86the average length of a list representing a page is around 4000, you can
87imagine that moving around a large amount of data is not that efficient. In order
88to cope with this, we experimented a lot and came to solutions which will be
89discussed later on.
90
91At the \LUA\ end some tricks were used to avoid the mentioned insertion and
92deletion penalty. When a node was deleted, we simply set its value to \type
93{false}. Deleting all glyphs then became:
94
95\starttyping
96for i, node in ipairs(list) do
97    if node[1] == "glyph" then
98        list[i] = false
99    end
100end
101\stoptyping
102
103When \TEX\ converted a \LUA\ table back into its internal representation, it
104ignored such false nodes.
105
106For insertion a dummy node was introduced at the \LUA\ end. The next code
107duplicates the glyphs.
108
109\starttyping
110for i, node in ipairs(list) do
111    if node[1] == "glyph" then
112        list[i] = { 'inline', 0, nil, { node, node } }
113    end
114end
115\stoptyping
116
117Just before we passed the resulting list back to \TEX\ we collapsed these
118inline pseudo nodes. This was a rather fast operation.
119
120So far so good. But then we introduced attributes and keeping track of them
121as well as processing them takes quite some processing power. Nodes with
122attributes then looked like:
123
124\starttyping
125someglyph = {
126    [1] = "glyph",               -- type
127    [2] = 0,                     -- subtype
128    [3] = { [1] = 5, [4] = 10 }, -- attributes
129    [4] = 88,                    -- slot
130    [5] = 32                     -- font
131}
132\stoptyping
133
134Constructing attribute tables for each node is costly in terms of memory usage
135and processing time and we found out that the garbage collector was becoming
136a bottleneck, especially when resources are thin. We will go into more detail
137about attributes elsewhere.
138
139\subject{lists}
140
141At the same time that we discussed these issues, new Dutch word lists (adapted
142spelling) were published and we started wondering if we could use such lists
143directly for hyphenation purposes instead of relying on traditional patterns. Here
144the first observation was that handling these really huge lists is no problem at
145all. Okay, it costs some memory but we only need to load one of maybe a few of
146these lists. Hyphenating a paragraph using tables with hyphenated words and
147processing the paragraph related node list is not only fast, it also gives us the
148opportunity to cross font boundaries. Of course there are kerns and ligatures to
149deal with but this is no big deal. At least it can be an alternative or addendum
150to the current hyphenator. Some languages have very small pattern files or a very
151systematic approach to hyphenation so there is no reason to abandon the traditional
152ways in all cases. Take your choice.
153
154When experimenting with the new implementation we tested the performance by letting
155\LUA\ take care of hyphenation, spell checking (marking words) and adding
156inter||character kerns. When playing with big lists of words we found out that the
157caching mechanism could not be used due to some limitations in the \LUA\ byte code
158interpreter, so eventually we ended up with a dedicated loader.
159
160However, again we ran into performance problems when lists became more complex. And so,
161instead of converting \TEX\ datastructures into \LUA\ tables userdata types came into
162view. Taco already had reimplemented the node memory management, so a logical next step
163was to reimplement the callbacks and box related code to deal with nodes as linked lists.
164Since this is now the fashion in \LUATEX, you may forget the previous examples, although
165it is not that hard to introduce table representations again once we need them.
166
167Of course this resulted in an adaption to the regular \TEX\ code but a nice side effect
168was that we could now use fields instead of indexes into the node data structure. There
169is a small price to pay in terms of performance, but this can be compensated by clever
170programming.
171
172\starttyping
173someglyph = {
174    type = 41,
175    subtype = 0,
176    attributes = <attributes>,
177    char = 88,
178    font = 32
179}
180\stoptyping
181
182Attributes themselves are userdata. The same is true for components that are present
183when we're for instance dealing with ligatures.
184
185As you can see, in the field variant, a type is a number. In practice, because \LUA\
186hashes strings, working with strings is as fast when comparing, but since we now have
187the more abstract type indicator, we stick with the numbers, which saves a few conversions.
188When dealing with tables we get code like:
189
190\starttyping
191function loop_over_nodes(list)
192    for i, n in ipairs(list)
193        local kind = n[1]
194        if kind == "hlist" or kind == "vlist" then
195            ...
196        end
197    end
198end
199\stoptyping
200
201But now that we have linked lists, we get the following. Node related methods
202are available in the \type {node} namespace.
203
204\starttyping
205function loop_over_nodes(head)
206    local hlist, vlist = node.id('hlist'), node.id('vlist')
207    while head do
208        local kind = head.type
209        if kind == hlist or kind == vlist then
210            ...
211        end
212        head = head.next
213    end
214end
215\stoptyping
216
217Using an abstraction (i.e.\ a constant representing \type {hlist} looks
218nice here, which is why numbers instead of strings are used. The indexed
219variant is still supported and there we have strings.
220
221Going from a node list (head node) to a table is not that complex. Sometimes
222this can be handy because manipulating tables is more convenient that messing
223around with userdata when it comes down to debugging or tracing.
224
225\starttyping
226function nodes.totable(n)
227    function totable(n)
228        local f, tt = node.fields(n.id,n.subtype), { }
229        for _,v in ipairs(f) do
230            local nv = n[v]
231            if nv then
232                local tnv = type(nv)
233                if tnv == "string" or tnv == "number" then
234                    tt[v] = nv
235                else -- userdata
236                    tt[v] = nodes.totable(nv)
237                end
238            end
239        end
240        return tt
241    end
242    local t = { }
243    while n do
244        t[#t+1] = totable(n)
245        n = n.next
246    end
247    return t
248end
249\stoptyping
250
251It will be clear that here we collect data in \LUA\ while treating nodes
252as userdata keeps most of it at the \TEX\ side and this is where the gain in
253speed comes from.
254
255\subject{side effects}
256
257While experimenting with node lists Taco and I ran into a peculiar side effect.
258One of the tests involved adding kerns between glyphs (inter character spacing
259as sometimes uses in titles in a large print). When applied to a whole document
260we noticed that at some places (words) the added kerning was gone. We used
261the subtype zero kern (which is most efficient) and in the process of hyphenating
262\TEX\ removes these kerns and inserts them later (but then based on the
263information stored in the font.
264
265The reason why \TEX\ removes the font related kerns, is the following. Consider
266the code:
267
268\starttyping
269\setbox0=\hbox{some text} the text \unhcopy0 has width \the\wd0
270\stoptyping
271
272While constructing the \type {\hbox}, \TEX\ will apply kerning as dictated
273by the font. Otherwise the width of the box would not be correct. This means
274that the node list entering the linebreak machinery contains such kerns.
275Because hyphenating works on words \TEX\ will remove these kerns in the
276process of identifying the words. It creates a string, removes the original
277sequence of nodes, determines hyphenation points, and add the result to
278the node list.  For efficiency reasons \TEX\ will only look at places
279where hyphenation makes  sense.
280
281Now, imagine that we add those kerns in the callback. This time, all characters
282are surrounded by kerns (which we gave subtype zero). When \TEX\ is determining
283feasable breakpoints (hyphenation), it will remove those kerns, but only at
284certain places. Because our kerns are way larger than the normal interglyph
285kerns, we suddenly end up with an intercharacter spaced paragraph that has
286some words without such spacing but the font dictated kerns.
287
288\blank
289m o s t\quad w o r d s\quad a r e\quad s p a c e d\quad b u t\quad
290some words\quad a r e\quad n o t
291\blank
292
293Of course a solution is to use a different kern, but at least this shows that
294the moment of processing nodes as well as the kind of manipulations need
295to be chosen with care.
296
297Kerning is a nasty business anyway. Imagine the following word:
298
299\starttyping
300effe
301\stoptyping
302
303When typeset this turns into three characters, one of them being a ligature.
304
305\starttyping
306[char e] [liga ff (components f f)] [char e]
307\stoptyping
308
309However, in Dutch, such a word hyphenates as:
310
311\starttyping
312ef-fe
313\stoptyping
314
315This means that in the node list we eventually find something:
316
317\starttyping
318[char e] [disc (f-) (f) (skip 1)] [liga ff (components f f)] [char e]
319\stoptyping
320
321So, eventually we need to kern between the character sequences [e,f-],
322[e,ff], [ff,e] and [f,e].
323
324\subject {attributes}
325
326We now arrive at attributes, a new property of nodes. Before we explain a
327bit more what can be done with them, we show how to define a new attribute
328and toggle it. In the following example the \type {\visualizenextnodes} macro
329is part of \CONTEXT\ \MKIV.
330
331\startbuffer
332\newattribute\aa
333\newattribute\ab
334\visualizenextnodes \hbox {\aa1 T{\ab3\aa2 E}X}
335\stopbuffer
336
337\typebuffer
338
339\placefigure
340  [page]
341  []
342  {\type{\hbox {\aa1 T{\ab3\aa2 E}X \ab 4}}}
343  {\switchtobodyfont[7pt]%
344   \scale[width=.9\textwidth]{\framed
345     [offset=2ex,foregroundcolor=red]
346     {\startsimplecolumns[n=2]
347        \resetglobalattributes
348        \resetlocalattributes
349        \getbuffer
350      \stopsimplecolumns}}}
351
352For the sake of this example, we start the allocation at 2000 because we don't
353want to interfere with attributes already defined in \CONTEXT. The node list
354resulting from the box is shown at the next page. As you can see here, internally
355attributes become a linked list assigned to the \type {attr} field. This means
356that one has to do some work in order to inspect attributes.
357
358\starttyping
359function has_attribute(n,a)
360    if n and n.attr then
361        n = n.attr.next
362        while n do
363            if n.number == a then
364                return n.value
365            end
366            n = n.next
367        end
368    else
369        return false
370    end
371end
372\stoptyping
373
374The previous function can be used in tests like:
375
376\starttyping
377local total = 0
378while n do
379    if has_attribute(n,2000) then
380        total = total + 1
381    end
382    n = n.next
383end
384texio.write_nl(string.format(
385    "attribute 2000 has been seen % times", total
386))
387\stoptyping
388
389When implementing nodes and attributes we did rather extensive tests and
390one of the test documents implemented some preliminary color mechanism
391based on attributes. When handling the colors the previous function was
392called some 300.000 times and the total node processing time (which also
393involved font handling) was some 2.9 seconds. Implementing this function
394as a helper brought down node processing time to 2.4 seconds. Of course
395the gain depends on the complexity of the list (nesting) and the number
396of attributes that are set (upto 5 per node in this test). A few more helper
397functions are available, some are for convenience, some gain us some speed.
398
399The nice thing about attributes is that they obey grouping. This means that
400in the following sequence:
401
402\starttyping
403x {\aa1 x \ab2 x} x
404\stoptyping
405
406the attributes are assigned like:
407
408\starttyping
409x x(201=1) x(201=1,202=2) x
410\stoptyping
411
412Internally \LUATEX\ does some optimizations with respect to assigning
413a sequence of similar attributes, but you should keep in mind that in practice
414the memory usage will be larger when using many attributes.
415
416We played with color and other properties, hyphenation based on word lists
417(and tracking languages with attributes) and or special algorithms (url
418hyphenation), spell checking (marking words as being spelled wrongly), and
419a few more things. This involved handling attributes in several callbacks
420resulting in the insertion or deletion of nodes.
421
422When using attributes for color support, we have to insert \type {pdfliteral} whatsit
423nodes at some point depending on the current color. This also means that the
424time spent with color support at the \TEX\ end will be compensated by
425time spent at the \LUA\ side. It also means that because housekeeping to do
426with colors spanning pages and columns is gone because from now on color
427information travels with the nodes. This saves quite some ugly code.
428
429Because most of the things that we want to do with attributes (and we have
430quite an agenda) are already nicely isolated in \CONTEXT, attributes will
431find their way rather soon in \CONTEXT\ \MKIV.
432
433Let's end with an observation. Attributes themselves are not something
434revolutionary. However, if you had to deal with them in \TEX, i.e.\
435associate them with for instance actions in during shipout, quite some
436time would have been spent on getting things right. Even worse: it would
437have lead to never ending discussions in the \TEX\ community and as
438such it's no surprise that something like this never showed up. The fact that
439we can use \LUA\ and manipulate node lists in many ways frees us from
440much discussion.
441
442We are even considering in future versions of \LUATEX\ to turn font, language
443and direction related information into attributes (in some private range) so this
444story is far from finished. As a teaser, consider the following line of thinking.
445
446Currently when a character enters the machinery, it becomes a glyph node. Among
447other characteristics, this node contains information about the font and the
448slot in that font which is used to represent that character. In a similar fashion,
449a space becomes glue with a measure probably related to the current font.
450
451However, with access to nodes and attributes, you can imagine the following
452scenario. Instead of a font (internally represented by a font id), you use an
453attribute referring to a font. At that time, the font field us just pointing to
454\TEX's null font. In a pass over the node list, you resolve the character and their
455attributes to a fonts and (maybe) other characters. Spacing can be postponed as well
456and instead of real glue values we can use multipliers and again attributes point
457the way to resolve them.
458
459Of course the question is if this is worth the trouble. After all typesetting is
460about fonts and there is no real reason not to give them a special place.
461
462\stopcomponent
463