typo-duc.lmt /size: 38 Kb    last modification: 2023-12-21 09:44
1if not modules then modules = { } end modules ['typo-duc'] = {
2    version   = 1.001,
3    comment   = "companion to typo-dir.mkiv",
4    author    = "Hans Hagen, PRAGMA-ADE, Hasselt NL",
5    copyright = "PRAGMA ADE / ConTeXt Development Team",
6    license   = "see context related readme files",
7    comment   = "Unicode bidi (sort of) variant c",
8}
9
10-- This is a follow up on typo-uda which itself is a follow up on t-bidi by Khaled Hosny which
11-- in turn is based on minibidi.c from Arabeyes. This is a further optimizations, as well as
12-- an update on some recent unicode bidi developments. There is (and will) also be more control
13-- added. As a consequence this module is somewhat slower than its precursor which itself is
14-- slower than the one-pass bidi handler. This is also a playground and I might add some plugin
15-- support. However, in the meantime performance got a bit better and this third variant is again
16-- some 10% faster than the second variant.
17
18-- todo (cf html):
19--
20-- normal            The element does not offer a additional level of embedding with respect to the bidirectional algorithm. For inline elements implicit reordering works across element boundaries.
21-- embed             If the element is inline, this value opens an additional level of embedding with respect to the bidirectional algorithm. The direction of this embedding level is given by the direction property.
22-- bidi-override     For inline elements this creates an override. For block container elements this creates an override for inline-level descendants not within another block container element. This means that inside the element, reordering is strictly in sequence according to the direction property; the implicit part of the bidirectional algorithm is ignored.
23-- isolate           This keyword indicates that the element's container directionality should be calculated without considering the content of this element. The element is therefore isolated from its siblings. When applying its bidirectional-resolution algorithm, its container element treats it as one or several U+FFFC Object Replacement Character, i.e. like an image.
24-- isolate-override  This keyword applies the isolation behavior of the isolate keyword to the surrounding content and the override behavior o f the bidi-override keyword to the inner content.
25-- plaintext         This keyword makes the elements directionality calculated without considering its parent bidirectional state or the value of the direction property. The directionality is calculated using the P2 and P3 rules of the Unicode Bidirectional Algorithm.
26--                   This value allows to display data which has already formatted using a tool following the Unicode Bidirectional Algorithm.
27--
28-- todo: check for introduced errors
29-- todo: reuse list, we have size, so we can just change values (and auto allocate when not there)
30-- todo: reuse the stack
31-- todo: no need for a max check
32-- todo: collapse bound similar ranges (not ok yet)
33-- todo: combine some sweeps
34-- todo: removing is not needed when we inject at the same spot (only change the dir property)
35-- todo: isolated runs (isolating runs are similar to bidi=local in the basic analyzer)
36
37-- todo: check unicode addenda (from the draft):
38--
39-- Added support for canonical equivalents in BD16.
40-- Changed logic in N0 to not check forwards for context in the case of enclosed text opposite the embedding direction.
41-- Major extension of the algorithm to allow for the implementation of directional isolates and the introduction of new isolate-related values to the Bidi_Class property.
42-- Adds BD8, BD9, BD10, BD11, BD12, BD13, BD14, BD15, and BD16, Sections 2.4 and 2.5, and Rules X5a, X5b, X5c and X6a.
43-- Extensively revises Section 3.3.2, Explicit Levels and Directions and its existing X rules to formalize the algorithm for matching a PDF with the embedding or override initiator whose scope it terminates.
44-- Moves Rules X9 and X10 into a separate new Section 3.3.3, Preparations for Implicit Processing.
45-- Modifies Rule X10 to make the isolating run sequence the unit to which subsequent rules are applied.
46-- Modifies Rule W1 to change an NSM preceded by an isolate initiator or PDI into ON.
47-- Adds Rule N0 and makes other changes to Section 3.3.5, Resolving Neutral and Isolate Formatting Types to resolve bracket pairs to the same level.
48
49local insert, remove, unpack, concat = table.insert, table.remove, table.unpack, table.concat
50local utfchar = utf.char
51local setmetatable = setmetatable
52local formatters = string.formatters
53
54local directiondata        = characters.directions
55local mirrordata           = characters.mirrors
56local textclassdata        = characters.textclasses
57
58local nuts                 = nodes.nuts
59
60local getnext              = nuts.getnext
61local getprev              = nuts.getprev
62local getid                = nuts.getid
63local getsubtype           = nuts.getsubtype
64local getlist              = nuts.getlist
65----- getchar              = nuts.getchar
66local getattr              = nuts.getattr
67local getprop              = nuts.getprop
68local getdirection         = nuts.getdirection
69local isnextchar           = nuts.isnextchar     -- we do this before the font handler
70
71local setprop              = nuts.setprop
72local setchar              = nuts.setchar
73local setdirection         = nuts.setdirection
74local setattrlist          = nuts.setattrlist
75
76local properties           = nodes.properties.data
77
78local remove_node          = nuts.remove
79local insertnodeafter      = nuts.insertafter
80local insertnodebefore     = nuts.insertbefore
81
82local startofpar           = nuts.startofpar
83
84local nodepool             = nuts.pool
85local new_direction        = nodepool.direction
86
87local nodecodes            = nodes.nodecodes
88local gluecodes            = nodes.gluecodes
89
90local glyph_code           = nodecodes.glyph
91local glue_code            = nodecodes.glue
92local hlist_code           = nodecodes.hlist
93local vlist_code           = nodecodes.vlist
94local math_code            = nodecodes.math
95local dir_code             = nodecodes.dir
96local par_code             = nodecodes.par
97local penalty_code         = nodecodes.penalty
98
99local parfillskip_code     = gluecodes.parfillskip
100local parfillleftskip_code = gluecodes.parfillleftskip
101
102local directioncodes       = tex.directioncodes
103local lefttoright_code     = directioncodes.lefttoright
104local righttoleft_code     = directioncodes.righttoleft
105
106local maximum_stack        = 0xFF
107
108local a_directions         = attributes.private('directions')
109
110local directions           = typesetters.directions
111local setcolor             = directions.setcolor
112local getfences            = directions.getfences
113
114local remove_controls      = true  directives.register("typesetters.directions.removecontrols",function(v) remove_controls  = v end)
115----- analyze_fences       = true  directives.register("typesetters.directions.analyzefences", function(v) analyze_fences   = v end)
116
117local report_directions    = logs.reporter("typesetting","directions three")
118
119local trace_directions     = false trackers.register("typesetters.directions",         function(v) trace_directions = v end)
120local trace_details        = false trackers.register("typesetters.directions.details", function(v) trace_details    = v end)
121local trace_list           = false trackers.register("typesetters.directions.list",    function(v) trace_list       = v end)
122
123-- strong (old):
124--
125-- l   : left to right
126-- r   : right to left
127-- lro : left to right override
128-- rlo : left to left override
129-- lre : left to right embedding
130-- rle : left to left embedding
131-- al  : right to legt arabic (esp punctuation issues)
132--
133-- weak:
134--
135-- en  : english number
136-- es  : english number separator
137-- et  : english number terminator
138-- an  : arabic number
139-- cs  : common number separator
140-- nsm : nonspacing mark
141-- bn  : boundary neutral
142--
143-- neutral:
144--
145-- b  : paragraph separator
146-- s  : segment separator
147-- ws : whitespace
148-- on : other neutrals
149--
150-- interesting: this is indeed better (and more what we expect i.e. we already use this split
151-- in the old original (also these isolates)
152--
153-- strong (new):
154--
155-- l   : left to right
156-- r   : right to left
157-- al  : right to left arabic (esp punctuation issues)
158--
159-- explicit: (new)
160--
161-- lro : left to right override
162-- rlo : left to left override
163-- lre : left to right embedding
164-- rle : left to left embedding
165-- pdf : pop dir format
166-- lri : left to right isolate
167-- rli : left to left isolate
168-- fsi : first string isolate
169-- pdi : pop directional isolate
170
171local whitespace = {
172    lre = true,
173    rle = true,
174    lro = true,
175    rlo = true,
176    pdf = true,
177    bn  = true,
178    ws  = true,
179}
180
181local b_s_ws_on = {
182    b   = true,
183    s   = true,
184    ws  = true,
185    on  = true
186}
187
188-- tracing
189
190local function show_list(list,size,what)
191    local what   = what or "direction"
192    local joiner = utfchar(0x200C)
193    local result = { }
194    for i=1,size do
195        local entry     = list[i]
196        local character = entry.char
197        local direction = entry[what]
198        if character == 0xFFFC then
199            local first = entry.id
200            local last  = entry.last
201            local skip  = entry.skip
202            if last then
203                result[i] = formatters["%-3s:%s %s..%s (%i)"](direction,joiner,nodecodes[first],nodecodes[last],skip or 0)
204            else
205                result[i] = formatters["%-3s:%s %s (%i)"](direction,joiner,nodecodes[first],skip or 0)
206            end
207        elseif character >= 0x202A and character <= 0x202C then
208            result[i] = formatters["%-3s:%s %U"](direction,joiner,character)
209        else
210            result[i] = formatters["%-3s:%s %c %U"](direction,joiner,character,character)
211        end
212    end
213    return concat(result,joiner .. " | " .. joiner)
214end
215
216-- preparation
217
218local function show_done(list,size)
219    local joiner = utfchar(0x200C)
220    local result = { }
221    local format = formatters["<%s>"]
222    for i=1,size do
223        local entry     = list[i]
224        local character = entry.char
225        local begindir  = entry.begindir
226        local enddir    = entry.enddir
227        if begindir then
228            result[#result+1] = format(begindir)
229        end
230        if entry.remove then
231            -- continue
232        elseif character == 0xFFFC then
233            result[#result+1] = format("?")
234        elseif character == 0x0020 then
235            result[#result+1] = format(" ")
236        elseif character >= 0x202A and character <= 0x202C then
237            result[#result+1] = format(entry.original)
238        else
239            result[#result+1] = utfchar(character)
240        end
241        if enddir then
242            result[#result+1] = format(enddir)
243        end
244    end
245    return concat(result,joiner)
246end
247
248-- keeping the list and overwriting doesn't save much runtime, only a few percent
249-- char is only used for mirror, so in fact we can as well only store it for
250-- glyphs only
251--
252-- tracking what direction is used and skipping tests is not faster (extra kind of
253-- compensates gain)
254
255local mt_space  = { __index = { char = 0x0020, direction = "ws",  original = "ws",  level = 0, skip = 0 } }
256local mt_lre    = { __index = { char = 0x202A, direction = "lre", original = "lre", level = 0, skip = 0 } }
257local mt_rle    = { __index = { char = 0x202B, direction = "rle", original = "rle", level = 0, skip = 0 } }
258local mt_pdf    = { __index = { char = 0x202C, direction = "pdf", original = "pdf", level = 0, skip = 0 } }
259local mt_object = { __index = { char = 0xFFFC, direction = "on",  original = "on",  level = 0, skip = 0 } }
260
261local stack = table.setmetatableindex("table") -- shared
262local list  = { }                              -- shared
263
264-- instead of skip we can just have slots filled with 'skip'
265
266local function build_list(head,where)
267    -- P1
268    local current = head
269    local size    = 0
270    while current do
271        size = size + 1
272     -- local id = getid(current)
273        local nxt, chr, id = isnextchar(current)
274        local p  = properties[current]
275        if p and p.directions then
276            -- tricky as dirs can be injected in between
277            local skip = 0
278            local last = id
279         -- current    = getnext(current)
280            current    = nxt
281            while current do
282                local id = getid(current)
283                local p  = properties[current]
284                if p and p.directions then
285                    skip    = skip + 1
286                    last    = id
287                    current = getnext(current)
288                else
289                    break
290                end
291            end
292            if id == last then -- the start id
293                list[size] = setmetatable({ skip = skip, id = id },mt_object)
294            else
295                list[size] = setmetatable({ skip = skip, id = id, last = last },mt_object)
296            end
297     -- elseif id == glyph_code then
298        elseif chr then
299         -- local chr  = getchar(current)
300            local dir  = directiondata[chr]
301            -- could also be a metatable
302            list[size] = { char = chr, direction = dir, original = dir, level = 0 }
303         -- current    = getnext(current)
304            current    = nxt
305         -- if not list[dir] then list[dir] = true end -- not faster when we check for usage
306        elseif id == glue_code then -- and how about kern
307            list[size] = setmetatable({ },mt_space)
308         -- current    = getnext(current)
309            current    = nxt
310        elseif id == dir_code then
311            local dir, pop = getdirection(current)
312            if dir == lefttoright_code then
313                list[size] = setmetatable({ },pop and mt_pdf or mt_lre)
314            elseif dir == righttoleft_code then
315                list[size] = setmetatable({ },pop and mt_pdf or mt_rle)
316            else
317                list[size] = setmetatable({ id = id },mt_object)
318            end
319         -- current    = getnext(current)
320            current    = nxt
321        elseif id == math_code then
322            local skip = 0
323         -- current    = getnext(current)
324            current    = nxt
325            while getid(current) ~= math_code do
326                skip    = skip + 1
327                current = getnext(current)
328            end
329            skip       = skip + 1
330            current    = getnext(current)
331            list[size] = setmetatable({ id = id, skip = skip },mt_object)
332        else -- disc_code: we assume that these are the same as the surrounding
333            local skip = 0
334            local last = id
335         -- current    = getnext(current)
336            current    = nxt
337            while n do
338                local id = getid(current)
339                if id ~= glyph_code and id ~= glue_code and id ~= dir_code then
340                    skip    = skip + 1
341                    last    = id
342                    current = getnext(current)
343                else
344                    break
345                end
346            end
347            if id == last then -- the start id
348                list[size] = setmetatable({ id = id, skip = skip },mt_object)
349            else
350                list[size] = setmetatable({ id = id, skip = skip, last = last },mt_object)
351            end
352        end
353    end
354    return list, size
355end
356
357-- new
358
359-- we could support ( ] and [ ) and such ...
360
361-- ש ) ל ( א       0-0
362-- ש ( ל ] א       0-0
363-- ש ( ל ) א       2-4
364-- ש ( ל [ א ) כ ] 2-6
365-- ש ( ל ] א ) כ   2-6
366-- ש ( ל ) א ) כ   2-4
367-- ש ( ל ( א ) כ   4-6
368-- ש ( ל ( א ) כ ) 2-8,4-6
369-- ש ( ל [ א ] כ ) 2-8,4-6
370
371local fencestack = table.setmetatableindex("table")
372
373local function resolve_fences(list,size,start,limit)
374    -- N0: funny effects, not always better, so it's an option
375    local nofstack = 0
376    for i=start,limit do
377        local entry = list[i]
378        if entry.direction == "on" then
379            local char   = entry.char
380            local mirror = mirrordata[char]
381            if mirror then
382                local class = textclassdata[char]
383                entry.mirror = mirror
384                entry.class  = class
385                if class == "open" then
386                    nofstack       = nofstack + 1
387                    local stacktop = fencestack[nofstack]
388                    stacktop[1]    = mirror
389                    stacktop[2]    = i
390                elseif nofstack == 0 then
391                    -- skip
392                elseif class == "close" then
393                    while nofstack > 0 do
394                        local stacktop = fencestack[nofstack]
395                        if stacktop[1] == char then
396                            local open  = stacktop[2]
397                            local close = i
398                            list[open ].paired = close
399                            list[close].paired = open
400                            break
401                        else
402                            -- do we mirror or not
403                        end
404                        nofstack = nofstack - 1
405                    end
406                end
407            end
408        end
409    end
410end
411
412-- local function test_fences(str)
413--     local list  = { }
414--     for s in string.gmatch(str,".") do
415--         local b = utf.byte(s)
416--         list[#list+1] = { c = s, char = b, direction = directiondata[b] }
417--     end
418--     resolve_fences(list,#list,1,#size)
419--     inspect(list)
420-- end
421--
422-- test_fences("a(b)c(d)e(f(g)h)i")
423-- test_fences("a(b[c)d]")
424
425-- the action
426
427local function get_baselevel(head,list,size,direction)
428    if direction == lefttoright_code or direction == righttoleft_code then
429        return direction, true
430    elseif getid(head) == par_code and startofpar(head) then
431        direction = getdirection(head)
432        if direction == lefttoright_code or direction == righttoleft_code then
433            return direction, true
434        end
435    end
436    -- P2, P3
437    for i=1,size do
438        local entry     = list[i]
439        local direction = entry.direction
440        if direction == "r" or direction == "al" then -- and an ?
441            return righttoleft_code, true
442        elseif direction == "l" then
443            return lefttoright_code, true
444        end
445    end
446    return lefttoright_code, false
447end
448
449local function resolve_explicit(list,size,baselevel)
450-- if list.rle or list.lre or list.rlo or list.lro then
451    -- X1
452    local level    = baselevel
453    local override = "on"
454    local nofstack = 0
455    for i=1,size do
456        local entry     = list[i]
457        local direction = entry.direction
458        -- X2
459        if direction == "rle" then
460            if nofstack < maximum_stack then
461                nofstack        = nofstack + 1
462                local stacktop  = stack[nofstack]
463                stacktop[1]     = level
464                stacktop[2]     = override
465                level           = level + (level % 2 == 1 and 2 or 1) -- least_greater_odd(level)
466                override        = "on"
467                entry.level     = level
468                entry.direction = "bn"
469                entry.remove    = true
470            elseif trace_directions then
471                report_directions("stack overflow at position %a with direction %a",i,direction)
472            end
473        -- X3
474        elseif direction == "lre" then
475            if nofstack < maximum_stack then
476                nofstack        = nofstack + 1
477                local stacktop  = stack[nofstack]
478                stacktop[1]     = level
479                stacktop[2]     = override
480                level           = level + (level % 2 == 1 and 1 or 2) -- least_greater_even(level)
481                override        = "on"
482                entry.level     = level
483                entry.direction = "bn"
484                entry.remove    = true
485            elseif trace_directions then
486                report_directions("stack overflow at position %a with direction %a",i,direction)
487            end
488        -- X4
489        elseif direction == "rlo" then
490            if nofstack < maximum_stack then
491                nofstack        = nofstack + 1
492                local stacktop  = stack[nofstack]
493                stacktop[1]     = level
494                stacktop[2]     = override
495                level           = level + (level % 2 == 1 and 2 or 1) -- least_greater_odd(level)
496                override        = "r"
497                entry.level     = level
498                entry.direction = "bn"
499                entry.remove    = true
500            elseif trace_directions then
501                report_directions("stack overflow at position %a with direction %a",i,direction)
502            end
503        -- X5
504        elseif direction == "lro" then
505            if nofstack < maximum_stack then
506                nofstack        = nofstack + 1
507                local stacktop  = stack[nofstack]
508                stacktop[1]     = level
509                stacktop[2]     = override
510                level           = level + (level % 2 == 1 and 1 or 2) -- least_greater_even(level)
511                override        = "l"
512                entry.level     = level
513                entry.direction = "bn"
514                entry.remove    = true
515            elseif trace_directions then
516                report_directions("stack overflow at position %a with direction %a",i,direction)
517            end
518        -- X7
519        elseif direction == "pdf" then
520            if nofstack > 0 then
521                local stacktop  = stack[nofstack]
522                level           = stacktop[1]
523                override        = stacktop[2]
524                nofstack        = nofstack - 1
525                entry.level     = level
526                entry.direction = "bn"
527                entry.remove    = true
528            elseif trace_directions then
529                report_directions("stack underflow at position %a with direction %a",
530                    i, direction)
531            else
532                report_directions("stack underflow at position %a with direction %a: %s",
533                    i, direction, show_list(list,size))
534            end
535        -- X6
536        else
537            entry.level = level
538            if override ~= "on" then
539                entry.direction = override
540            end
541        end
542    end
543    -- X8 (reset states and overrides after paragraph)
544end
545
546local function resolve_weak(list,size,start,limit,orderbefore,orderafter)
547    -- W1: non spacing marks get the direction of the previous character
548-- if list.nsm then
549    for i=start,limit do
550        local entry = list[i]
551        if entry.direction == "nsm" then
552            if i == start then
553                entry.direction = orderbefore
554            else
555                entry.direction = list[i-1].direction
556            end
557        end
558    end
559-- end
560    -- W2: mess with numbers and arabic
561-- if list.en then
562    for i=start,limit do
563        local entry = list[i]
564        if entry.direction == "en" then
565            for j=i-1,start,-1 do
566                local prev = list[j]
567                local direction = prev.direction
568                if direction == "al" then
569                    entry.direction = "an"
570                    break
571                elseif direction == "r" or direction == "l" then
572                    break
573                end
574            end
575        end
576    end
577-- end
578    -- W3
579-- if list.al then
580    for i=start,limit do
581        local entry = list[i]
582        if entry.direction == "al" then
583            entry.direction = "r"
584        end
585    end
586-- end
587    -- W4: make separators number
588-- if list.es or list.cs then
589        -- skip
590    if false then
591        for i=start+1,limit-1 do
592            local entry     = list[i]
593            local direction = entry.direction
594            if direction == "es" then
595                if list[i-1].direction == "en" and list[i+1].direction == "en" then
596                    entry.direction = "en"
597                end
598            elseif direction == "cs" then
599                local prevdirection = list[i-1].direction
600                if prevdirection == "en" then
601                    if list[i+1].direction == "en" then
602                        entry.direction = "en"
603                    end
604                elseif prevdirection == "an" and list[i+1].direction == "an" then
605                    entry.direction = "an"
606                end
607            end
608        end
609    else -- only more efficient when we have es/cs
610        local runner = start + 2
611        if runner <= limit then
612            local before  = list[start]
613            local current = list[start + 1]
614            local after   = list[runner]
615            while after do
616                local direction = current.direction
617                if direction == "es" then
618                    if before.direction == "en" and after.direction == "en" then
619                        current.direction = "en"
620                    end
621                elseif direction == "cs" then
622                    local prevdirection = before.direction
623                    if prevdirection == "en" then
624                        if after.direction == "en" then
625                            current.direction = "en"
626                        end
627                    elseif prevdirection == "an" and after.direction == "an" then
628                        current.direction = "an"
629                    end
630                end
631                before  = current
632                current = after
633                after   = list[runner]
634                runner  = runner + 1
635            end
636        end
637    end
638-- end
639    -- W5
640-- if list.et then
641    local i = start
642    while i <= limit do
643        if list[i].direction == "et" then
644            local runstart = i
645            local runlimit = runstart
646            for i=runstart,limit do
647                if list[i].direction == "et" then
648                    runlimit = i
649                else
650                    break
651                end
652            end
653            local rundirection = runstart == start and sor or list[runstart-1].direction
654            if rundirection ~= "en" then
655                rundirection = runlimit == limit and orderafter or list[runlimit+1].direction
656            end
657            if rundirection == "en" then
658                for j=runstart,runlimit do
659                    list[j].direction = "en"
660                end
661            end
662            i = runlimit
663        end
664        i = i + 1
665    end
666-- end
667    -- W6
668-- if list.es or list.cs or list.et then
669    for i=start,limit do
670        local entry     = list[i]
671        local direction = entry.direction
672        if direction == "es" or direction == "et" or direction == "cs" then
673            entry.direction = "on"
674        end
675    end
676-- end
677    -- W7
678    for i=start,limit do
679        local entry = list[i]
680        if entry.direction == "en" then
681            local prev_strong = orderbefore
682            for j=i-1,start,-1 do
683                local direction = list[j].direction
684                if direction == "l" or direction == "r" then
685                    prev_strong = direction
686                    break
687                end
688            end
689            if prev_strong == "l" then
690                entry.direction = "l"
691            end
692        end
693    end
694end
695
696local function resolve_neutral(list,size,start,limit,orderbefore,orderafter)
697    -- N1, N2
698    for i=start,limit do
699        local entry = list[i]
700        if b_s_ws_on[entry.direction] then
701            -- this needs checking
702            local leading_direction, trailing_direction, resolved_direction
703            local runstart = i
704            local runlimit = runstart
705--             for j=runstart,limit do
706            for j=runstart+1,limit do
707                if b_s_ws_on[list[j].direction] then
708--                     runstart = j
709                    runlimit = j
710                else
711                    break
712                end
713            end
714            if runstart == start then
715                leading_direction = orderbefore
716            else
717                leading_direction = list[runstart-1].direction
718                if leading_direction == "en" or leading_direction == "an" then
719                    leading_direction = "r"
720                end
721            end
722            if runlimit == limit then
723                trailing_direction = orderafter
724            else
725                trailing_direction = list[runlimit+1].direction
726                if trailing_direction == "en" or trailing_direction == "an" then
727                    trailing_direction = "r"
728                end
729            end
730            if leading_direction == trailing_direction then
731                -- N1
732                resolved_direction = leading_direction
733            else
734                -- N2 / does the weird period
735                resolved_direction = entry.level % 2 == 1 and "r" or "l"
736            end
737            for j=runstart,runlimit do
738                list[j].direction = resolved_direction
739            end
740            i = runlimit
741        end
742        i = i + 1
743    end
744end
745
746local function resolve_implicit(list,size,start,limit,orderbefore,orderafter,baselevel)
747    for i=start,limit do
748        local entry     = list[i]
749        local level     = entry.level
750        local direction = entry.direction
751        if level % 2 ~= 1 then -- even
752            -- I1
753            if direction == "r" then
754                entry.level = level + 1
755            elseif direction == "an" or direction == "en" then
756                entry.level = level + 2
757            end
758        else
759            -- I2
760            if direction == "l" or direction == "en" or direction == "an" then
761                entry.level = level + 1
762            end
763        end
764    end
765end
766
767local function resolve_levels(list,size,baselevel,analyze_fences)
768    -- X10
769    local start = 1
770    while start < size do
771        local level = list[start].level
772        local limit = start + 1
773        while limit < size and list[limit].level == level do
774            limit = limit + 1
775        end
776        local prev_level  = start == 1    and baselevel or list[start-1].level
777        local next_level  = limit == size and baselevel or list[limit+1].level
778        local orderbefore = (level > prev_level and level or prev_level) % 2 == 1 and "r" or "l"
779        local orderafter  = (level > next_level and level or next_level) % 2 == 1 and "r" or "l"
780        -- W1 .. W7
781        resolve_weak(list,size,start,limit,orderbefore,orderafter)
782        -- N0
783        if analyze_fences then
784            resolve_fences(list,size,start,limit)
785        end
786        -- N1 .. N2
787        resolve_neutral(list,size,start,limit,orderbefore,orderafter)
788        -- I1 .. I2
789        resolve_implicit(list,size,start,limit,orderbefore,orderafter,baselevel)
790        start = limit
791    end
792    -- L1
793    for i=1,size do
794        local entry     = list[i]
795        local direction = entry.original
796        -- (1)
797        if direction == "s" or direction == "b" then
798            entry.level = baselevel
799            -- (2)
800            for j=i-1,1,-1 do
801                local entry = list[j]
802                if whitespace[entry.original] then
803                    entry.level = baselevel
804                else
805                    break
806                end
807            end
808        end
809    end
810    -- (3)
811    for i=size,1,-1 do
812        local entry = list[i]
813        if whitespace[entry.original] then
814            entry.level = baselevel
815        else
816            break
817        end
818    end
819    -- L4
820    if analyze_fences then
821        for i=1,size do
822            local entry = list[i]
823            if entry.level % 2 == 1 then -- odd(entry.level)
824                if entry.mirror and not entry.paired then
825                    entry.mirror = false
826                end
827                -- okay
828            elseif entry.mirror then
829                entry.mirror = false
830            end
831        end
832    else
833        for i=1,size do
834            local entry = list[i]
835            if entry.level % 2 == 1 then -- odd(entry.level)
836                local mirror = mirrordata[entry.char]
837                if mirror then
838                    entry.mirror = mirror
839                end
840            end
841        end
842    end
843end
844
845local stack = { }
846
847local function insert_dir_points(list,size)
848    -- L2, but no actual reversion is done, we simply annotate where
849    -- begindir/endddir node will be inserted.
850    local maxlevel = 0
851    local toggle   = true
852    for i=1,size do
853        local level = list[i].level
854        if level > maxlevel then
855            maxlevel = level
856        end
857    end
858    for level=0,maxlevel do
859        local started  -- = false
860        local begindir -- = nil
861        local enddir   -- = nil
862        local prev     -- = nil
863        if toggle then
864            begindir = lefttoright_code
865            enddir   = lefttoright_code
866            toggle   = false
867        else
868            begindir = righttoleft_code
869            enddir   = righttoleft_code
870            toggle   = true
871        end
872        for i=1,size do
873            local entry = list[i]
874            if entry.level >= level then
875                if not started then
876                    entry.begindir = begindir
877                    started        = true
878                end
879            else
880                if started then
881                    prev.enddir = enddir
882                    started     = false
883                end
884            end
885            prev = entry
886        end
887    end
888    -- make sure to close the run at end of line
889    local last = list[size]
890    if not last.enddir then
891        local n = 0
892        for i=1,size do
893            local entry = list[i]
894            local e = entry.enddir
895            local b = entry.begindir
896            if e then
897                n = n - 1
898            end
899            if b then
900                n = n + 1
901                stack[n] = b
902            end
903        end
904        if n > 0 then
905            if trace_list and n > 1 then
906                report_directions("unbalanced list")
907            end
908            last.enddir = stack[n]
909        end
910    end
911end
912
913-- We flag nodes that can be skipped when we see them again but because whatever
914-- mechanism can inject dir nodes that then are not flagged, we don't flag dir
915-- nodes that we inject here.
916
917local function apply_to_list(list,size,head,pardir)
918    local index   = 1
919    local current = head
920    if trace_list then
921        report_directions("start run")
922    end
923    while current do
924        if index > size then
925            report_directions("fatal error, size mismatch")
926            break
927        end
928        local id       = getid(current) -- we can better store the id in list[index]
929        local entry    = list[index]
930        local begindir = entry.begindir
931        local enddir   = entry.enddir
932        local p = properties[current]
933        if p then
934            p.directions = true
935        else
936            properties[current] = { directions = true }
937        end
938        if id == glyph_code then
939            local mirror = entry.mirror
940            if mirror then
941                setchar(current,mirror)
942            end
943            if trace_directions then
944                local direction = entry.direction
945                if trace_list then
946                    local original = entry.original
947                    local char     = entry.char
948                    local level    = entry.level
949                    if direction == original then
950                        report_directions("%2i : %C : %s",level,char,direction)
951                    else
952                        report_directions("%2i : %C : %s -> %s",level,char,original,direction)
953                    end
954                end
955                setcolor(current,direction,false,mirror)
956            end
957        elseif id == hlist_code or id == vlist_code then
958            setdirection(current,pardir) -- is this really needed?
959        elseif id == glue_code then
960            -- Maybe I should also fix dua and dub but on the other hand ... why?
961--             if enddir and getsubtype(current) == parfillskip_code then
962--                 -- insert the last enddir before \parfillskip glue
963--                 local c = current
964--                 local p = getprev(c)
965--                 if p and getid(p) == glue_code and getsubtype(p) == parfillleftskip_code then
966--                     c = p
967--                     p = getprev(c)
968--                 end
969--                 while p and getid(p) == glue_code do
970--                     c = p
971--                     p = getprev(c)
972--                 end
973--                 if p and getid(p) == penalty_code then -- linepenalty
974--                     c = p
975--                 end
976--                 -- there is always a par nodes so head will stay
977--                 local d = new_direction(enddir,true)
978--                 setattrlist(d,current)
979--                 head = insertnodebefore(head,c,d)
980--                 enddir = false
981--             end
982            if enddir then
983                local d = new_direction(enddir,true)
984                setattrlist(d,current)
985                head = insertnodebefore(head,current,d)
986                enddir = false
987            end
988        elseif begindir then
989            if id == par_code and startofpar(current) then
990                -- par should always be the 1st node
991                local d = new_direction(begindir)
992                setattrlist(d,current)
993                head, current = insertnodeafter(head,current,d)
994                begindir = nil
995            end
996        end
997        if begindir then
998            local d = new_direction(begindir)
999            setattrlist(d,current)
1000            head = insertnodebefore(head,current,d)
1001        end
1002        local skip = entry.skip
1003        if skip and skip > 0 then
1004            for i=1,skip do
1005                current = getnext(current)
1006                local p = properties[current]
1007                if p then
1008                    p.directions = true
1009                else
1010                    properties[current] = { directions = true }
1011                end
1012            end
1013        end
1014        if enddir then
1015            local d = new_direction(enddir,true)
1016            setattrlist(d,current)
1017            head, current = insertnodeafter(head,current,d)
1018        end
1019        if not entry.remove then
1020            current = getnext(current)
1021        elseif remove_controls then
1022            -- X9
1023            head, current = remove_node(head,current,true)
1024        else
1025            current = getnext(current)
1026        end
1027        index = index + 1
1028    end
1029    if trace_list then
1030        report_directions("stop run")
1031    end
1032    return head
1033end
1034
1035-- If needed we can optimize for only_one. There is no need to do anything
1036-- when it's not a glyph. Otherwise we only need to check mirror and apply
1037-- directions when it's different from the surrounding. Paragraphs always
1038-- have more than one node. Actually, we only enter this function when we
1039-- do have a glyph!
1040
1041local function process(head,direction,only_one,where)
1042    -- for the moment a whole paragraph property
1043    local attr = getattr(head,a_directions)
1044    local analyze_fences = getfences(attr)
1045    --
1046    local list, size = build_list(head,where)
1047    local baselevel, dirfound = get_baselevel(head,list,size,direction)
1048    if trace_details then
1049        report_directions("analyze: baselevel %a",baselevel == righttoleft_code and "r2l" or "l2r")
1050        report_directions("before : %s",show_list(list,size,"original"))
1051    end
1052    resolve_explicit(list,size,baselevel)
1053    resolve_levels(list,size,baselevel,analyze_fences)
1054    insert_dir_points(list,size)
1055    if trace_details then
1056        report_directions("after  : %s",show_list(list,size,"direction"))
1057        report_directions("result : %s",show_done(list,size))
1058    end
1059    return apply_to_list(list,size,head,baselevel)
1060end
1061
1062local variables = interfaces.variables
1063
1064directions.installhandler(variables.one,    process) -- for old times sake
1065directions.installhandler(variables.two,    process) -- for old times sake
1066directions.installhandler(variables.three,  process) -- for old times sake
1067directions.installhandler(variables.unicode,process)
1068