node-ltp.lua /size: 145 Kb    last modification: 2021-10-28 13:50
1if not modules then modules = { } end modules ['node-par'] = {
2    version   = 1.001,
3    optimize  = true,
4    comment   = "companion to node-par.mkiv",
5    author    = "Hans Hagen",
6    copyright = "ConTeXt Development Team",
7    license   = "see context related readme files",
8    comment   = "a translation of the built in parbuilder, initial convertsin by Taco Hoekwater",
9}
10
11-- todo: remove nest_stack from linebreak.w
12-- todo: permit global steps i.e. using an attribute that sets min/max/step and overloads the font parameters
13-- todo: split the three passes into three functions
14-- todo: see if we can do without delta nodes (needs thinking)
15-- todo: add more mkiv like tracing
16-- todo: add a couple of plugin hooks
17-- todo: fix line numbers (cur_list.pg_field needed)
18-- todo: optimize a bit more (less par.*)
19
20-- issue: ls / rs added when zero content and normalize
21
22--[[
23
24    This code is derived from traditional TeX and has bits of pdfTeX, Aleph (Omega), and of course LuaTeX. So,
25    the basic algorithm for sure is not our work. On the other hand, the directional model in LuaTeX is cleaned
26    up as is other code. And of course there are hooks for callbacks.
27
28    The first version of the code below was a conversion of the C code that in turn was a conversion from the
29    original Pascal code. Around September 2008 we experimented with cq. discussed possible approaches to improved
30    typesetting of Arabic and as our policy is that extensions happen in Lua this means that we need a parbuilder
31    in Lua. Taco's first conversion still looked quite C-ish and in the process of cleaning up we uncovered some odd
32    bits and pieces in the original code as well. I did some first cleanup to get rid of C-artefacts, and Taco and I
33    spent the usual amount of Skyping to sort out problems. At that point we diverted to other LuaTeX issues.
34
35    A while later I decided to pick up this thread and decided to look into better ways to deal with font expansion
36    (aka hz). I got it running using a simpler method. One reason why the built-in mechanims is slow is that there is
37    lots of redudancy in calculations. Expanded widths are recalculated each time and because the hpakc routine does
38    it again that gives some overhead. In the process extra fonts are created with different dimensions so that the
39    backend can deal with it. The alternative method doesn't create fonts but passes an expansion factor to the
40    pdf generator. The small patch needed for the backend code worked more or less okay but was never intergated into
41    LuaTeX due to lack of time.
42
43    This all happened in 2010 while listening to Peter Gabriels "Scratch My Back" and Camels "Rayaz" so it was a
44    rather relaxed job.
45
46    In 2012 I picked up this thread. Because both languages are similar but also quite different it took some time
47    to get compatible output. Because the C code uses macros, careful checking was needed. Of course Lua's table model
48    and local variables brought some work as well. And still the code looks a bit C-ish. We could not divert too much
49    from the original model simply because it's well documented but future versions (or variants) might as well look
50    different.
51
52    Eventually I'll split this code into passes so that we can better see what happens, but first we need to reach
53    a decent level of stability. The current expansion results are not the same as the built-in but that was never
54    the objective. It all has to do with slightly different calculations.
55
56    The original C-code related to protrusion and expansion is not that efficient as many (redundant) function
57    calls take place in the linebreaker and packer. As most work related to fonts is done in the backend, we
58    can simply stick to width calculations here. Also, it is no problem at all that we use floating point
59    calculations (as Lua has only floats). The final result will look ok as the hpack will nicely compensate
60    for rounding errors as it will normally distribute the content well enough. And let's admit: most texies
61    won't see it anyway. As long as we're cross platform compatible it's fine.
62
63    We use the table checked_expansion to keep track of font related parameters (per paragraph). The table is
64    also the signal that we have adjustments > 1. In retrospect one might wonder if adjusting kerns is such a
65    good idea because other spacing is also not treated. If we would stick to the regular hpack routine
66    we do have to follow the same logic, but I decided to use a Lua hpacker so that constraint went away. And
67    anyway, instead of doing a lookup in the kern table (that we don't have in node mode) the set kern value
68    is used. Disabling kern scaling will become an option in Luatex some day. You can blame me for all errors
69    that crept in and I know that there are some.
70
71    To be honest, I slowly start to grasp the magic here as normally I start from scratch when implementing
72    something (as it's the only way I can understand things). This time I had a recently acquired stack of
73    Porcupine Tree disks to get me through, although I must admit that watching their dvd's is more fun
74    than coding.
75
76    Picking up this effort was inspired by discussions between Luigi Scarso and me about efficiency of Lua
77    code and we needed some stress tests to compare regular LuaTeX and LuajitTeX. One of the tests was
78    processing tufte.tex as that one has lots of hyphenations and is a tough one to get right.
79
80    tufte: boxed 1000 times, no flushing in backend:
81
82                           \testfeatureonce{1000}{\setbox0\hbox{\tufte}}
83                           \testfeatureonce{1000}{\setbox0\vbox{\tufte}}
84    \startparbuilder[basic]\testfeatureonce{1000}{\setbox0\vbox{\tufte}}\stopparbuilder
85
86                method     normal   hz      comment
87
88    luatex      tex hbox    9.64     9.64   baseline font feature processing, hyphenation etc: 9.74
89                tex vbox    9.84    10.16   0.20 linebreak / 0.52 with hz -> 0.32 hz overhead (150pct more)
90                lua vbox   17.28    18.43   7.64 linebreak / 8.79 with hz -> 1.33 hz overhead ( 20pct more)
91
92    new laptop | no nuts
93                            3.42            baseline
94                            3.63            0.21 linebreak
95                            7.38            3.96 linebreak
96
97    new laptop | most nuts
98                            2.45            baseline
99                            2.53            0.08 linebreak
100                            6.16            3.71 linebreak
101                 ltp nuts   5.45            3.00 linebreak
102
103    luajittex   tex hbox    6.33     6.33   baseline font feature processing, hyphenation etc: 6.33
104                tex vbox    6.53     6.81   0.20 linebreak / 0.48 with hz -> 0.28 hz overhead (expected 0.32)
105                lua vbox   11.06    11.81   4.53 linebreak / 5.28 with hz -> 0.75 hz overhead
106
107    new laptop | no nuts
108                            2.06            baseline
109                            2.27            0.21 linebreak
110                            3.95            1.89 linebreak
111
112    new laptop | most nuts
113                            1.25            baseline
114                            1.30            0.05 linebreak
115                            3.03            1.78 linebreak
116                 ltp nuts   2.47            1.22 linebreak
117
118    Interesting is that the runtime for the built-in parbuilder indeed increases much when expansion
119    is enabled, but in the Lua variant the extra overhead is way less significant. This means that when we
120    retrofit the same approach into the core, the overhead of expansion can be sort of nilled.
121
122    In 2013 the expansion factor method became also used at the TeX end so then I could complete the code
123    here, and indeed, expansions works quite well now (not compatible of course because we use floats at
124    the Lua end. The Lua base variant is still slower but quite ok, especially if we go nuts.
125
126    A next iteration will provide plug-ins and more control. I will also explore the possibility to avoid
127    the redundant hpack calculations (easier now, although I've only done some quick and dirty experiments.)
128
129    The code has been adapted to the more reasonable and simplified direction model.
130
131    In case I forget when I added the normalization code: it was november 2019 and it took me way more time
132    than usual because I got distracted after discovering Alyona Yarushina on YT (in november 2019) which
133    blew some fuses in the musical aware part of my brain in a similar way as when I discovered Kate Bush,
134    so I had to watch a whole lot of her perfect covers (multiple times and for sure many more times). A
135    new benchmark.
136
137]]--
138
139local unpack = unpack
140
141-- local fonts, nodes, node = fonts, nodes, node -- too many locals
142
143local trace_basic         = false  trackers.register("builders.paragraphs.basic",       function(v) trace_basic       = v end)
144local trace_lastlinefit   = false  trackers.register("builders.paragraphs.lastlinefit", function(v) trace_lastlinefit = v end)
145local trace_adjusting     = false  trackers.register("builders.paragraphs.adjusting",   function(v) trace_adjusting   = v end)
146local trace_protruding    = false  trackers.register("builders.paragraphs.protruding",  function(v) trace_protruding  = v end)
147local trace_expansion     = false  trackers.register("builders.paragraphs.expansion",   function(v) trace_expansion   = v end)
148
149local report_parbuilders  = logs.reporter("nodes","parbuilders")
150----- report_hpackers     = logs.reporter("nodes","hpackers")
151
152local calculate_badness   = tex.badness
153local texlists            = tex.lists
154local texget              = tex.get
155local texset              = tex.set
156local texgetglue          = tex.getglue
157
158-- (t == 0 and 0) or (s <= 0 and 10000) or calculate_badness(t,s)
159
160-- local function calculate_badness(t,s)
161--     if t == 0 then
162--         return 0
163--     elseif s <= 0 then
164--         return 10000 -- infinite_badness
165--     else
166--         local r
167--         if t <= 7230584 then
168--             r = (t * 297) / s
169--         elseif s >= 1663497 then
170--             r = t / (s / 297)
171--         else
172--             r = t
173--         end
174--         if r > 1290 then
175--             return 10000 -- infinite_badness
176--         else
177--             return (r * r * r + 0x20000) / 0x40000
178--         end
179--     end
180-- end
181
182local parbuilders             = builders.paragraphs
183local constructors            = parbuilders.constructors
184
185local setmetatableindex       = table.setmetatableindex
186
187local fonthashes              = fonts.hashes
188local chardata                = fonthashes.characters
189local quaddata                = fonthashes.quads
190local parameters              = fonthashes.parameters
191
192local nuts                    = nodes.nuts
193local tonut                   = nuts.tonut
194
195local getfield                = nuts.getfield
196local getid                   = nuts.getid
197local getsubtype              = nuts.getsubtype
198local getnext                 = nuts.getnext
199local getprev                 = nuts.getprev
200local getboth                 = nuts.getboth
201local getlist                 = nuts.getlist
202local getdisc                 = nuts.getdisc
203local getattr                 = nuts.getattr
204local getdisc                 = nuts.getdisc
205local getglue                 = nuts.getglue
206local getwhd                  = nuts.getwhd
207local getkern                 = nuts.getkern
208local getpenalty              = nuts.getpenalty
209local getdirection            = nuts.getdirection
210local getshift                = nuts.getshift
211local getwidth                = nuts.getwidth
212local getheight               = nuts.getheight
213local getdepth                = nuts.getdepth
214local getdata                 = nuts.getdata
215local getreplace              = nuts.getreplace
216local setreplace              = nuts.setreplace
217local getpost                 = nuts.getpost
218local setpost                 = nuts.setpost
219local getpre                  = nuts.getpre
220local setpre                  = nuts.setpre
221
222local isglyph                 = nuts.isglyph
223local startofpar              = nuts.startofpar
224
225local setfield                = nuts.setfield
226local setlink                 = nuts.setlink
227local setlist                 = nuts.setlist
228local setboth                 = nuts.setboth
229local setnext                 = nuts.setnext
230local setprev                 = nuts.setprev
231local setdisc                 = nuts.setdisc
232local setsubtype              = nuts.setsubtype
233local setglue                 = nuts.setglue
234local setwhd                  = nuts.setwhd
235local setkern                 = nuts.setkern
236local setdirection            = nuts.setdirection
237local setshift                = nuts.setshift
238local setwidth                = nuts.setwidth
239local setexpansion            = nuts.setexpansion
240
241local find_tail               = nuts.tail
242local copy_node               = nuts.copy
243local flushnode               = nuts.flush
244local flushnodelist           = nuts.flushlist
245----- hpack_nodes             = nuts.hpack
246local xpack_nodes             = nuts.hpack
247local replace_node            = nuts.replace
248local remove_node             = nuts.remove
249local insertnodeafter         = nuts.insertafter
250local insertnodebefore        = nuts.insertbefore
251local iszeroglue              = nuts.iszeroglue
252local protrusionskippable     = nuts.protrusionskippable
253local setattributelist        = nuts.setattributelist
254local find_node               = nuts.find_node
255
256local nextnode                = nuts.traversers.node
257local nextglue                = nuts.traversers.glue
258
259local nodepool                = nuts.pool
260
261local nodecodes               = nodes.nodecodes
262local kerncodes               = nodes.kerncodes
263local disccodes               = nodes.disccodes
264local mathcodes               = nodes.mathcodes
265local fillcodes               = nodes.fillcodes
266local gluecodes               = nodes.gluecodes
267
268local temp_code               = nodecodes.temp
269local glyph_code              = nodecodes.glyph
270local insert_code             = nodecodes.insert
271local mark_code               = nodecodes.mark
272local adjust_code             = nodecodes.adjust
273local penalty_code            = nodecodes.penalty
274local disc_code               = nodecodes.disc
275local math_code               = nodecodes.math
276local kern_code               = nodecodes.kern
277local glue_code               = nodecodes.glue
278local hlist_code              = nodecodes.hlist
279local vlist_code              = nodecodes.vlist
280local unset_code              = nodecodes.unset
281local marginkern_code         = nodecodes.marginkern
282local dir_code                = nodecodes.dir
283local boundary_code           = nodecodes.boundary
284local par_code                = nodecodes.par
285
286local protrusionboundary_code = nodes.boundarycodes.protrusion
287local leaders_code            = nodes.gluecodes.leaders
288local indentlist_code         = nodes.listcodes.indent
289local cancel_code             = nodes.dircodes.cancel
290
291local userkern_code           = kerncodes.userkern
292local italickern_code         = kerncodes.italiccorrection
293local fontkern_code           = kerncodes.fontkern
294local accentkern_code         = kerncodes.accentkern
295
296local automaticdisc_code      = disccodes.automatic
297local regulardisc_code        = disccodes.regular
298local firstdisc_code          = disccodes.first
299local seconddisc_code         = disccodes.second
300
301local spaceskip_code          = gluecodes.spaceskip
302local xspaceskip_code         = gluecodes.xspaceskip
303local rightskip_code          = gluecodes.rightskip
304
305local endmath_code            = mathcodes.endmath
306
307local righttoleft_code        = nodes.dirvalues.righttoleft
308
309local nosubtype_code          = 0
310
311local unhyphenated_code       = nodecodes.unhyphenated or 1
312local hyphenated_code         = nodecodes.hyphenated   or 2
313local delta_code              = nodecodes.delta        or 3
314local passive_code            = nodecodes.passive      or 4
315
316local maxdimen                = number.maxdimen
317
318local max_halfword            = 0x7FFFFFFF
319local infinite_penalty        =  10000
320local eject_penalty           = -10000
321local infinite_badness        =  10000
322local awful_badness           = 0x3FFFFFFF
323local ignore_depth            = -65536000
324
325local fit_very_loose_class    = 0  -- fitness for lines stretching more than their stretchability
326local fit_loose_class         = 1  -- fitness for lines stretching 0.5 to 1.0 of their stretchability
327local fit_decent_class        = 2  -- fitness for all other lines
328local fit_tight_class         = 3  -- fitness for lines shrinking 0.5 to 1.0 of their shrinkability
329
330local new_penalty             = nodepool.penalty
331local new_direction           = nodepool.direction
332local new_leftmarginkern      = nodepool.leftmarginkern
333local new_rightmarginkern     = nodepool.rightmarginkern
334local new_leftskip            = nodepool.leftskip
335local new_rightskip           = nodepool.rightskip
336local new_lefthangskip        = nodepool.lefthangskip
337local new_righthangskip       = nodepool.righthangskip
338local new_indentskip          = nodepool.indentskip
339local new_correctionskip      = nodepool.correctionskip
340local new_lineskip            = nodepool.lineskip
341local new_baselineskip        = nodepool.baselineskip
342local new_temp                = nodepool.temp
343local new_rule                = nodepool.rule
344local new_hlist               = nodepool.hlist
345
346local getnormalizeline        = nodes.getnormalizeline
347
348local packing_exactly    = "exactly"
349local packing_additional = "additional"
350local packing_expanded   = CONTEXTLMTXMODE > 0 and "expanded"   or "cal_expand_ratio"
351local packing_substitute = CONTEXTLMTXMODE > 0 and "substiture" or "subst_ex_font"
352
353-- helpers --
354
355-- It makes more sense to move the somewhat messy dir state tracking
356-- out of the main functions. First we create a stack allocator.
357
358-- The next function checks a dir node and returns the new dir state. By
359-- using a static table we are quite efficient. This function is used
360-- in the parbuilder.
361
362local function checked_line_dir(stack,current) -- can be inlined now
363    local direction, pop = getdirection(current)
364    local n = stack.n
365    if not pop then
366        n = n + 1
367        stack.n = n
368        stack[n] = direction
369        return direction
370    elseif n > 0 then
371        n = n - 1
372        stack.n = n
373        return stack[n]
374    else
375        report_parbuilders("warning: missing pop node (%a)",1) -- in line ...
376    end
377end
378
379-- The next function checks dir nodes in a list and injects dir nodes
380-- that are currently needed.
381
382local function inject_dirs_at_begin_of_line(stack,current)
383    local n = stack.n
384    if n > 0 then
385        local h = current
386        for i=1,n do
387            local d = new_direction(stack[i])
388            setattributelist(d,current)
389            h, current = insertnodeafter(h,current,d)
390        end
391        stack.n = 0
392        return h
393    else
394        return current
395    end
396end
397
398local function inject_dirs_at_end_of_line(stack,current,start,stop)
399    local n = stack.n
400    while start and start ~= stop do
401        local id = getid(start)
402        if id == dir_code then
403            local direction, pop = getdirection(start)
404            if not pop then
405                n = n + 1
406                stack[n] = direction
407            elseif n > 0 then
408if direction == stack[n] then
409    -- like in the engine
410                n = n - 1
411end
412            else
413                report_parbuilders("warning: missing pop node (%a)",2) -- in line ...
414            end
415        end
416        start = getnext(start)
417    end
418    if n > 0 then
419        -- from 1,n and before
420        local h = start
421        for i=n,1,-1 do
422            local d = new_direction(stack[i],true)
423            setattributelist(d,start)
424            h, current = insertnodeafter(h,current,d)
425        end
426    end
427    stack.n = n
428    return current
429end
430
431local ignoremathskip = nuts.ignoremathskip or function(current)
432    local mode = texget("mathskipmode")
433    if mode == 6 or mode == 7 then
434        local b = true
435        local n = getsubtype(current) == endmath_code and getnext(current) or getprev(current)
436        if n and getid(n) == glue_code then
437            local s = getsubtype(n)
438            if s == spaceskip_code or s == xspaceskip_code then
439                b = false
440            end
441        end
442        if mode == 7 then
443            b = not b
444        end
445        if b then
446            setglue(current)
447            return true
448        end
449    end
450    return false
451end
452
453-- diagnostics --
454
455local dummy = function() end
456
457local diagnostics = {
458    start          = dummy,
459    stop           = dummy,
460    current_pass   = dummy,
461    break_node     = dummy,
462    feasible_break = dummy,
463}
464
465-- statistics --
466
467local nofpars, noflines, nofprotrudedlines, nofadjustedlines = 0, 0, 0, 0
468
469local function register_statistics(par)
470    local statistics  = par.statistics
471    nofpars           = nofpars           + 1
472    noflines          = noflines          + statistics.noflines
473    nofprotrudedlines = nofprotrudedlines + statistics.nofprotrudedlines
474    nofadjustedlines  = nofadjustedlines  + statistics.nofadjustedlines
475end
476
477-- expansion etc --
478
479local function calculate_fraction(x,n,d,max_answer)
480    local the_answer = x * n/d + 1/2 -- round ?
481    if the_answer > max_answer then
482        return  max_answer
483    elseif the_answer < -max_answer then
484        return -max_answer
485    else
486        return  the_answer
487    end
488end
489
490local function infinite_shrinkage_error(par)
491    if par.no_shrink_error_yet then
492        par.no_shrink_error_yet = false
493        report_parbuilders("infinite glue shrinkage found in a paragraph and removed")
494    end
495end
496
497-- It doesn't really speed up much but the additional memory usage is
498-- rather small so it doesn't hurt too much.
499
500local expansions = { }
501local nothing    = { stretch = 0, shrink = 0 } -- or just true or so
502
503-- setmetatableindex(expansions,function(t,font) -- we can store this in tfmdata if needed
504--     local expansion = parameters[font].expansion -- can be an extra hash
505--     if expansion and expansion.step ~= 0 then
506--         local stretch = expansion.stretch
507--         local shrink  = expansion.shrink
508--         if shrink ~= 0 or stretch ~= 0 then
509--             local factors = { }
510--             local c = chardata[font]
511--             setmetatableindex(factors,function(t,char)
512--                 local fc = c[char]
513--                 local ef = fc.expansion_factor
514--                 if ef and ef > 0 then
515--                     if stretch ~= 0 or shrink ~= 0 then
516--                         -- todo in lmtx: get rid of quad related scaling
517--                         local factor  = ef / 1000
518--                         local ef_quad = factor * quaddata[font] / 1000
519--                         local v = {
520--                             glyphstretch = stretch * ef_quad,
521--                             glyphshrink  = shrink  * ef_quad,
522--                             factor       = factor,  -- do we need these, if not then we
523--                             stretch      = stretch, -- can as well use the chardata table
524--                             shrink       = shrink,  -- to store the two above
525--                         }
526--                         t[char] = v
527--                         return v
528--                     end
529--                 end
530--                 t[char] = nothing
531--                 return nothing
532--             end)
533--             t[font] = factors
534--             return factors
535--         end
536--     end
537--     t[font] = false
538--     return false
539-- end)
540
541-- local function kern_stretch_shrink(p,d)
542--     local left = getprev(p)
543--     if left then
544--         local char, font = isglyph(left)
545--         if char then
546--             local data = expansions[font]
547--             if data then
548--                 data = data[char]
549--                 if data then
550--                     local stretch = data.stretch
551--                     local shrink  = data.shrink
552--                     if stretch ~= 0 then
553--                         stretch = data.factor * d * (stretch - 1)
554--                     end
555--                     if shrink ~= 0 then
556--                         shrink = data.factor  * d * (shrink  - 1)
557--                     end
558--                     return stretch, shrink
559--                 end
560--             end
561--         end
562--     end
563--     return 0, 0
564-- end
565
566setmetatableindex(expansions,function(t,font) -- we can store this in tfmdata if needed
567    local expansion = parameters[font].expansion -- can be an extra hash
568    if expansion and expansion.step ~= 0 then
569        local stretch = expansion.stretch
570        local shrink  = expansion.shrink
571        if shrink ~= 0 or stretch ~= 0 then
572            local factors = {
573                stretch = stretch,
574                shrink  = shrink,
575            }
576            local c = chardata[font]
577            setmetatableindex(factors,function(t,char)
578                local fc = c[char]
579                local ef = fc.expansion_factor
580                if ef and ef > 0 and stretch ~= 0 or shrink ~= 0 then
581                    -- todo in lmtx: get rid of quad related scaling
582                    local factor  = ef / 1000
583                    local ef_quad = factor * quaddata[font] / 1000
584                    local v = {
585                        glyphstretch = stretch * ef_quad,
586                        glyphshrink  = shrink  * ef_quad,
587                        factor       = factor,
588                    }
589                    t[char] = v
590                    return v
591                end
592                t[char] = nothing
593                return nothing
594            end)
595            t[font] = factors
596            return factors
597        end
598    end
599    t[font] = false
600    return false
601end)
602
603local function kern_stretch_shrink(p,d)
604    local left = getprev(p)
605    if left then
606        local char, font = isglyph(left)
607        if char then
608            local fdata = expansions[font]
609            if fdata then
610                local cdata = fdata[char]
611                if cdata then
612                    local stretch = fdata.stretch
613                    local shrink  = fdata.shrink
614                    local factor  = cdata.factor * d
615                    if stretch ~= 0 then
616                        stretch = factor * (stretch - 1)
617                    end
618                    if shrink ~= 0 then
619                        shrink = factor * (shrink  - 1)
620                    end
621                    return stretch, shrink
622                end
623            end
624        end
625    end
626    return 0, 0
627end
628
629local expand_kerns_mode = false
630local expand_kerns      = false
631
632directives.register("builders.paragraphs.adjusting.kerns",function(v)
633    if not v then
634        expand_kerns_mode = false
635    elseif v == "stretch" or v == "shrink" then
636        expand_kerns_mode = v
637    elseif v == "both" then
638        expand_kerns_mode = true
639    else
640        expand_kerns_mode = toboolean(v,true) or false
641    end
642end)
643
644-- state:
645
646-- the step criterium is no longer an issue, we can be way more tolerant in
647-- luatex as we act per glyph
648
649local function check_expand_pars(checked_expansion,f)
650    local expansion = parameters[f].expansion
651    if not expansion then
652        checked_expansion[f] = false
653        return false
654    end
655-- expansion.step = 1
656    local step    = expansion.step    or 0
657    local stretch = expansion.stretch or 0
658    local shrink  = expansion.shrink  or 0
659    if step == 0 or (stretch == 0 and schrink == 0) then
660        checked_expansion[f] = false
661        return false
662    end
663    local par = checked_expansion.par
664    if par.cur_font_step < 0 then
665        par.cur_font_step = step
666    elseif par.cur_font_step ~= step then
667        report_parbuilders("using fonts with different step of expansion in one paragraph is not allowed")
668        checked_expansion[f] = false
669        return false
670    end
671    if stretch == 0 then
672        -- okay
673    elseif par.max_stretch_ratio < 0 then
674        par.max_stretch_ratio = stretch -- expansion_factor
675    elseif par.max_stretch_ratio ~= stretch then
676        report_parbuilders("using fonts with different stretch limit of expansion in one paragraph is not allowed")
677        checked_expansion[f] = false
678        return false
679    end
680    if shrink == 0 then
681        -- okay
682    elseif par.max_shrink_ratio < 0 then
683        par.max_shrink_ratio = shrink -- - expansion_factor
684    elseif par.max_shrink_ratio ~= shrink then
685        report_parbuilders("using fonts with different shrink limit of expansion in one paragraph is not allowed")
686        checked_expansion[f] = false
687        return false
688    end
689    if trace_adjusting then
690        report_parbuilders("expanding font %a using step %a, shrink %a and stretch %a",f,step,stretch,shrink)
691    end
692    local e = expansions[f]
693    checked_expansion[f] = e
694    return e
695end
696
697local function check_expand_lines(checked_expansion,f)
698    local expansion = parameters[f].expansion
699    if not expansion then
700        checked_expansion[f] = false
701        return false
702    end
703-- expansion.step = 1
704    local step    = expansion.step    or 0
705    local stretch = expansion.stretch or 0
706    local shrink  = expansion.shrink  or 0
707    if step == 0 or (stretch == 0 and schrink == 0) then
708        checked_expansion[f] = false
709        return false
710    end
711    if trace_adjusting then
712        report_parbuilders("expanding font %a using step %a, shrink %a and stretch %a",f,step,stretch,shrink)
713    end
714    local e = expansions[f]
715    checked_expansion[f] = e
716    return e
717end
718
719-- protrusion
720
721local function find(head) -- do we really want to recurse into an hlist?
722    while head do
723        local id = getid(head)
724        if id == glyph_code then
725            return head
726        elseif id == hlist_code then
727            local found = find(getlist(head))
728            if found then
729                return found
730            else
731                head = getnext(head)
732            end
733        elseif id == boundary_code then
734            if getsubtype(head) == protrusionboundary_code then
735                local v = getdata(head)
736                if v == 1 or v == 3 then -- brrr
737                    head = getnext(head)
738                    if head then
739                        head = getnext(head)
740                    end
741                else
742                    return head
743                end
744            else
745                return head
746            end
747        elseif protrusionskippable(head) then
748            head = getnext(head)
749        else
750            return head
751        end
752    end
753    return nil
754end
755
756local function find_protchar_left(l) -- weird function
757    local ln = getnext(l)
758    if ln and getid(ln) == hlist_code and not getlist(ln) then
759        local w, h, d = getwhd(ln)
760        if w == 0 and h == 0 and d == 0 then
761            l = getnext(l)
762            return find(l) or l
763        end
764    end -- if d then -- was always true
765    local id = getid(l)
766    while ln and not (id == glyph_code or id < math_code) do -- is there always a glyph?
767        l = ln
768        ln = getnext(l)
769        id = getid(ln)
770    end
771    return find(l) or l
772end
773
774local function find(head,tail)
775    local tail = tail or find_tail(head)
776    while tail do
777        local id = getid(tail)
778        if id == glyph_code then
779            return tail
780        elseif id == hlist_code then
781            local found = find(getlist(tail))
782            if found then
783                return found
784            else
785                tail = getprev(tail)
786            end
787        elseif id == boundary_code then
788            if getsubtype(head) == protrusionboundary_code then
789                local v = getdata(tail)
790                if v == 2 or v == 3 then
791                    tail = getprev(tail)
792                    if tail then
793                        tail = getprev(tail)
794                    end
795                else
796                    return tail
797                end
798            else
799                return tail
800            end
801        elseif protrusionskippable(tail) then
802            tail = getprev(tail)
803        else
804            return tail
805        end
806    end
807    return nil
808end
809
810local function find_protchar_right(l,r)
811    return r and find(l,r) or r
812end
813
814local function left_pw(p)
815    local char, font = isglyph(p)
816    local prot = chardata[font][char].left_protruding
817    if not prot or prot == 0 then
818        return 0
819    end
820    return prot, p
821end
822
823local function right_pw(p)
824    local char, font = isglyph(p)
825    local prot = chardata[font][char].right_protruding
826    if not prot or prot == 0 then
827        return 0
828    end
829    return prot, p
830end
831
832-- par parameters
833
834local function reset_meta(par)
835    local active = {
836        id          = hyphenated_code,
837        line_number = max_halfword,
838    }
839    active.next = par.active -- head of metalist
840    par.active  = active
841    par.passive = nil
842end
843
844local function add_to_width(line_break_dir,checked_expansion,s) -- split into two loops (normal and expansion)
845    local size           = 0
846    local adjust_stretch = 0
847    local adjust_shrink  = 0
848    while s do
849        local char, id = isglyph(s)
850        if char then
851            size = size + getwidth(s)
852            if checked_expansion then
853                local data = checked_expansion[id] -- id == font
854                if data then
855                    data = data[char]
856                    if data then
857                        adjust_stretch = adjust_stretch + data.glyphstretch
858                        adjust_shrink  = adjust_shrink  + data.glyphshrink
859                    end
860                end
861            end
862        elseif id == hlist_code or id == vlist_code then
863            size = size + getwidth(s)
864        elseif id == kern_code then
865            local kern = getkern(s)
866            if kern ~= 0 then
867                if checked_expansion and expand_kerns and getsubtype(s) == fontkern_code then
868                    local stretch, shrink = kern_stretch_shrink(s,kern)
869                    if expand_kerns == "stretch" then
870                        adjust_stretch = adjust_stretch + stretch
871                    elseif expand_kerns == "shrink" then
872                        adjust_shrink  = adjust_shrink  + shrink
873                    else
874                        adjust_stretch = adjust_stretch + stretch
875                        adjust_shrink  = adjust_shrink  + shrink
876                    end
877                end
878                size = size + kern
879            end
880        elseif id == rule_code then
881            size = size + getwidth(s)
882        elseif trace_unsupported then
883            report_parbuilders("unsupported node at location %a",6)
884        end
885        s = getnext(s)
886    end
887    return size, adjust_stretch, adjust_shrink
888end
889
890-- We can actually make par local to this module as we never break inside a break call and that way the
891-- array is reused. At some point the information will be part of the paragraph spec as passed.
892
893local hztolerance = 2500
894local hzwarned    = false
895
896do
897
898    local function compute_break_width(par,break_type,p) -- split in two
899        local break_width = par.break_width
900        if break_type > unhyphenated_code then
901            local disc_width           = par.disc_width
902            local checked_expansion    = par.checked_expansion
903            local line_break_dir       = par.line_break_dir
904            local break_size           = break_width.size           + disc_width.size
905            local break_adjust_stretch = break_width.adjust_stretch + disc_width.adjust_stretch
906            local break_adjust_shrink  = break_width.adjust_shrink  + disc_width.adjust_shrink
907            local pre, post, replace = getdisc(p)
908            if replace then
909                local size, adjust_stretch, adjust_shrink = add_to_width(line_break_dir,checked_expansion,replace)
910                break_size           = break_size           - size
911                break_adjust_stretch = break_adjust_stretch - adjust_stretch
912                break_adjust_shrink  = break_adjust_shrink  - adjust_shrink
913            end
914            if post then
915                local size, adjust_stretch, adjust_shrink = add_to_width(line_break_dir,checked_expansion,post)
916                break_size           = break_size           + size
917                break_adjust_stretch = break_adjust_stretch + adjust_stretch
918                break_adjust_shrink  = break_adjust_shrink  + adjust_shrink
919            end
920            break_width.size           = break_size
921            break_width.adjust_stretch = break_adjust_stretch
922            break_width.adjust_shrink  = break_adjust_shrink
923            if not post then
924                p = getnext(p)
925            else
926                return
927            end
928        end
929        while p do -- skip spacing etc
930            local id = getid(p)
931            if id == glyph_code then
932                return -- happens often
933            elseif id == glue_code then
934                local wd, stretch, shrink, stretch_order = getglue(p)
935                local order = fillcodes[stretch_order]
936                break_width.size   = break_width.size   - wd
937                break_width[order] = break_width[order] - stretch
938                break_width.shrink = break_width.shrink - shrink
939            elseif id == penalty_code then
940                -- do nothing
941            elseif id == kern_code then
942                local s = getsubtype(p)
943                if s == userkern_code or s == italickern_code then
944                    break_width.size = break_width.size - getkern(p)
945                else
946                    return
947                end
948            elseif id == math_code then
949                break_width.size = break_width.size - getkern(p) -- surround
950                -- new in luatex
951                local wd, stretch, shrink, stretch_order = getglue(p)
952                local order = fillcodes[stretch_order]
953                break_width.size   = break_width.size   - wd
954                break_width[order] = break_width[order] - stretch
955                break_width.shrink = break_width.shrink - shrink
956            else
957                return
958            end
959            p = getnext(p)
960        end
961    end
962
963    local function append_to_vlist(par, b)
964        local prev_depth = par.prev_depth
965        local head_field = par.head_field
966        local tail_field = head_field and find_tail(head_field)
967        local is_hlist   = getid(b) == hlist_code
968        if prev_depth > ignore_depth then
969            if is_hlist then
970                -- we can fetch the skips values earlier if needed
971                local width, stretch, shrink, stretch_order, shrink_order = unpack(par.baseline_skip)
972                local delta = width - prev_depth - getheight(b) -- deficiency of space between baselines
973                local skip = nil
974                if delta < par.line_skip_limit then
975                    width, stretch, shrink, stretch_order, shrink_order = unpack(par.lineskip)
976                    skip = new_lineskip(width, stretch, shrink, stretch_order, shrink_order)
977                else
978                    skip = new_baselineskip(delta, stretch, shrink, stretch_order, shrink_order)
979                end
980                setattributelist(skip,par.head)
981                if head_field then
982                    setlink(tail_field,skip)
983                else
984                    par.head_field = skip
985                    head_field = skip
986                end
987                tail_field = skip
988            end
989        end
990        if head_field then
991            setlink(tail_field,b)
992        else
993            par.head_field = b
994        end
995        if is_hlist then
996            local pd = getdepth(b)
997            par.prev_depth = pd
998            texset("prevdepth",pd)
999        end
1000    end
1001
1002    local function append_list(par, b)
1003        local head_field = par.head_field
1004        if head_field then
1005            local n = find_tail(head_field)
1006            setlink(n,b)
1007        else
1008            par.head_field = b
1009        end
1010    end
1011
1012    local function used_skip(s)
1013        return s and not iszeroglue(s) and s
1014    end
1015
1016    local function initialize_line_break(head,display)
1017
1018        local hang_indent    = texget("hangindent")
1019        local hsize          = texget("hsize")
1020        local hang_after     = texget("hangafter")
1021        local par_shape_ptr  = texget("parshape")
1022        local left_skip      = { texgetglue("leftskip") }
1023        local right_skip     = { texgetglue("rightskip") }
1024        local pretolerance   = texget("pretolerance")
1025        local tolerance      = texget("tolerance")
1026        local adjust_spacing = texget("adjustspacing")
1027        local protrude_chars = texget("protrudechars")
1028        local last_line_fit  = texget("lastlinefit")
1029        local par_dir        = texget("pardirection")
1030
1031        local newhead = new_temp()
1032        setnext(newhead,head)
1033
1034        local adjust_spacing_status = adjust_spacing > 1 and -1 or 0
1035
1036        -- metatables
1037
1038        local par = {
1039            head                         = newhead,
1040            head_field                   = nil,
1041            display                      = display,
1042            font_in_short_display        = 0,
1043            no_shrink_error_yet          = true,   -- have we complained about infinite shrinkage?
1044            second_pass                  = false,  -- is this our second attempt to break this paragraph?
1045            final_pass                   = false,  -- is this our final attempt to break this paragraph?
1046            threshold                    = 0,      -- maximum badness on feasible lines
1047
1048            passive                      = nil,    -- most recent node on passive list
1049            printed_node                 = head,   -- most recent node that has been printed
1050            pass_number                  = 0,      -- the number of passive nodes allocated on this pass
1051            auto_breaking                = 0,      -- make auto_breaking accessible out of line_break
1052
1053            active_width                 = { size = 0, normal = 0, fi = 0, fil = 0, fill = 0, filll = 0, shrink = 0, adjust_stretch = 0, adjust_shrink = 0 },
1054            break_width                  = { size = 0, normal = 0, fi = 0, fil = 0, fill = 0, filll = 0, shrink = 0, adjust_stretch = 0, adjust_shrink = 0 },
1055            disc_width                   = { size = 0,                                                               adjust_stretch = 0, adjust_shrink = 0 },
1056            fill_width                   = {           normal = 0, fi = 0, fil = 0, fill = 0, filll = 0, shrink = 0                                        },
1057            background                   = { size = 0, normal = 0, fi = 0, fil = 0, fill = 0, filll = 0, shrink = 0                                        },
1058
1059            hang_indent                  = hang_indent,
1060            hsize                        = hsize,
1061            hang_after                   = hang_after,
1062            par_shape_ptr                = par_shape_ptr,
1063            left_skip                    = left_skip,
1064            right_skip                   = right_skip,
1065            pretolerance                 = pretolerance,
1066            tolerance                    = tolerance,
1067
1068            protrude_chars               = protrude_chars,
1069            adjust_spacing               = adjust_spacing,
1070            max_stretch_ratio            = adjust_spacing_status,
1071            max_shrink_ratio             = adjust_spacing_status,
1072            cur_font_step                = adjust_spacing_status,
1073            checked_expansion            = false,
1074            tracing_paragraphs           = texget("tracingparagraphs") > 0,
1075
1076            emergency_stretch            = texget("emergencystretch")     or 0,
1077            looseness                    = texget("looseness")            or 0,
1078            line_penalty                 = texget("linepenalty")          or 0,
1079            broken_penalty               = texget("brokenpenalty")        or 0,
1080            inter_line_penalty           = texget("interlinepenalty")     or 0,
1081            club_penalty                 = texget("clubpenalty")          or 0,
1082            widow_penalty                = texget("widowpenalty")         or 0,
1083            display_widow_penalty        = texget("displaywidowpenalty")  or 0,
1084
1085            adj_demerits                 = texget("adjdemerits")          or 0,
1086            double_hyphen_demerits       = texget("doublehyphendemerits") or 0,
1087            final_hyphen_demerits        = texget("finalhyphendemerits")  or 0,
1088
1089            first_line                   = texget("prevgraf"),
1090            prev_depth                   = texget("prevdepth"),
1091
1092            baseline_skip                = { texgetglue("baselineskip") },
1093            lineskip                     = { texgetglue("lineskip") },
1094            line_skip_limit              = texget("lineskiplimit"),
1095
1096            final_par_glue               = find_tail(head),
1097
1098            par_break_dir                = par_dir,
1099            line_break_dir               = par_dir,
1100
1101            internal_pen_inter           = 0,   -- running localinterlinepenalty
1102            internal_pen_broken          = 0,   -- running localbrokenpenalty
1103            internal_left_box            = nil, -- running localleftbox
1104            internal_left_box_width      = 0,   -- running localleftbox width
1105            init_internal_left_box       = nil, -- running localleftbox
1106            init_internal_left_box_width = 0,   -- running localleftbox width
1107            internal_right_box           = nil, -- running localrightbox
1108            internal_right_box_width     = 0,   -- running localrightbox width
1109
1110            best_place                   = { }, -- how to achieve minimal_demerits
1111            best_pl_line                 = { }, -- corresponding line number
1112            easy_line                    = 0,   -- line numbers easy_line are equivalent in break nodes
1113            last_special_line            = 0,   -- line numbers last_special_line all have the same width
1114            first_width                  = 0,   -- the width of all lines last_special_line, if no parshape has been specified
1115            second_width                 = 0,   -- the width of all lines last_special_line
1116            first_indent                 = 0,   -- left margin to go with first_width
1117            second_indent                = 0,   -- left margin to go with second_width
1118
1119            best_bet                     = nil, -- use this passive node and its predecessors
1120            fewest_demerits              = 0,   -- the demerits associated with best_bet
1121            best_line                    = 0,   -- line number following the last line of the new paragraph
1122            line_diff                    = 0,   -- the difference between the current line number and the optimum best_line
1123
1124            -- not yet used
1125
1126            best_pl_short                = { }, -- shortfall corresponding to minimal_demerits
1127            best_pl_glue                 = { }, -- corresponding glue stretch or shrink
1128            do_last_line_fit             = false,
1129            last_line_fit                = last_line_fit,
1130
1131            minimum_demerits             = awful_badness,
1132
1133            minimal_demerits             = {
1134
1135                [fit_very_loose_class] = awful_badness,
1136                [fit_loose_class]      = awful_badness,
1137                [fit_decent_class]     = awful_badness,
1138                [fit_tight_class]      = awful_badness,
1139
1140            },
1141
1142            prev_char_p                  = nil,
1143
1144            statistics                   = {
1145
1146                noflines          = 0,
1147                nofprotrudedlines = 0,
1148                nofadjustedlines  = 0,
1149
1150            },
1151
1152         -- -- just a thought ... parshape functions ... it would be nice to
1153         -- -- also store the height so far (probably not too hard) although
1154         -- -- in most cases we work on grids in such cases
1155         --
1156         -- adapt_width = function(par,line)
1157         --     -- carry attribute, so that we can accumulate
1158         --     local left  = 655360 * (line - 1)
1159         --     local right = 655360 * (line - 1)
1160         --     return left, right
1161         -- end
1162
1163        }
1164
1165        -- so far
1166
1167        if adjust_spacing > 1 then
1168            local checked_expansion = { par = par }
1169            setmetatableindex(checked_expansion,check_expand_pars)
1170            par.checked_expansion = checked_expansion
1171
1172            if par.tolerance < hztolerance then
1173                if not hzwarned then
1174                    report_parbuilders("setting tolerance to %a for hz",hztolerance)
1175                    hzwarned = true
1176                end
1177                par.tolerance = hztolerance
1178            end
1179
1180            expand_kerns = expand_kerns_mode or (adjust_spacing == 2) -- why not > 1 ?
1181
1182        end
1183
1184        -- we need par for the error message
1185
1186        local background = par.background
1187
1188        local lwidth, lstretch, lshrink, lstretch_order, lshrink_order = unpack(left_skip)
1189        local rwidth, rstretch, rshrink, rstretch_order, rshrink_order = unpack(right_skip)
1190
1191        if lshrink_order ~= 0 and lshrink ~= 0 then
1192            infinite_shrinkage_error(par)
1193            lshrink_order = 0
1194        end
1195        if rshrink_order ~= 0 and rshrink ~= 0 then
1196            infinite_shrinkage_error(par)
1197            rshrink_order = 0
1198        end
1199
1200        local l_order = fillcodes[lstretch_order]
1201        local r_order = fillcodes[rstretch_order]
1202
1203        background.size     = lwidth   + rwidth
1204        background.shrink   = lshrink  + rshrink
1205        background[l_order] = lstretch
1206        background[r_order] = rstretch + background[r_order]
1207
1208        -- this will move up so that we can assign the whole par table
1209
1210        if not par_shape_ptr then
1211            if hang_indent == 0 then
1212                par.second_width  = hsize
1213                par.second_indent = 0
1214            else
1215                local abs_hang_after  = hang_after  > 0 and hang_after  or -hang_after
1216                local abs_hang_indent = hang_indent > 0 and hang_indent or -hang_indent
1217                par.last_special_line = abs_hang_after
1218                if hang_after < 0 then
1219                    par.first_width = hsize - abs_hang_indent
1220                    if hang_indent >= 0 then
1221                        par.first_indent = hang_indent
1222                    else
1223                        par.first_indent = 0
1224                    end
1225                    par.second_width  = hsize
1226                    par.second_indent = 0
1227                else
1228                    par.first_width  = hsize
1229                    par.first_indent = 0
1230                    par.second_width = hsize - abs_hang_indent
1231                    if hang_indent >= 0 then
1232                        par.second_indent = hang_indent
1233                    else
1234                        par.second_indent = 0
1235                    end
1236                end
1237            end
1238        else
1239            local last_special_line = #par_shape_ptr
1240            par.last_special_line = last_special_line
1241            local parshape = par_shape_ptr[last_special_line]
1242            par.second_width  = parshape[2]
1243            par.second_indent = parshape[1]
1244        end
1245
1246        if par.looseness == 0 then
1247            par.easy_line = par.last_special_line
1248        else
1249            par.easy_line = max_halfword
1250        end
1251
1252        if pretolerance >= 0 then
1253            par.threshold   = pretolerance
1254            par.second_pass = false
1255            par.final_pass  = false
1256        else
1257            par.threshold   = tolerance
1258            par.second_pass = true
1259            par.final_pass  = par.emergency_stretch <= 0
1260            if trace_basic then
1261                if par.final_pass then
1262                    report_parbuilders("enabling second and final pass")
1263                else
1264                    report_parbuilders("enabling second pass")
1265                end
1266            end
1267        end
1268
1269        if last_line_fit > 0 then
1270            local final_par_glue = par.final_par_glue
1271            local stretch        = getfield(final_par_glue,"stretch")
1272            local stretch_order  = getfield(final_par_glue,"stretch_order")
1273            if stretch > 0 and stretch_order > 0 and background.fi == 0 and background.fil == 0 and background.fill == 0 and background.filll == 0 then
1274                par.do_last_line_fit = true
1275                local si = fillcodes[stretch_order]
1276                if trace_lastlinefit or trace_basic then
1277                    report_parbuilders("enabling last line fit, stretch order %a set to %a, linefit is %a",si,stretch,last_line_fit)
1278                end
1279                par.fill_width[si] = stretch
1280            end
1281        end
1282
1283        return par
1284    end
1285
1286    -- there are still all kind of artefacts in here (a side effect I guess of pdftex,
1287    -- etex, omega and other extensions that got obscured by patching)
1288
1289    local function post_line_break(par)
1290
1291        local prevgraf       = par.first_line -- or texget("prevgraf")
1292        local current_line   = prevgraf + 1 -- the current line number being justified
1293        local adjust_spacing = par.adjust_spacing
1294        local protrude_chars = par.protrude_chars
1295        local statistics     = par.statistics
1296        local leftskip       = par.left_skip
1297        local rightskip      = par.right_skip
1298        local parshape       = par.par_shape_ptr
1299     -- local adapt_width    = par.adapt_width
1300        local hsize          = par.hsize
1301
1302        local dirstack       = par.dirstack
1303        local normalize      = getnormalizeline()
1304
1305        -- reverse the links of the relevant passive nodes, goto first breakpoint
1306
1307        local current_break  = nil
1308
1309        local break_node = par.best_bet.break_node
1310        repeat
1311            local first_break = break_node
1312            break_node = break_node.prev_break
1313            first_break.prev_break = current_break
1314            current_break = first_break
1315        until not break_node
1316
1317        local head = par.head
1318
1319        -- when we normalize and have no content still ls/rs gets appended while
1320        -- the engine doesnt' do that so there is some test missing that prevents
1321        -- entering here
1322
1323        while current_break do
1324
1325            -- hm, here we have head == par and in the engine it's a temp node
1326
1327            head = inject_dirs_at_begin_of_line(dirstack,head)
1328
1329            local disc_break      = false
1330            local post_disc_break = false
1331            local glue_break      = false
1332
1333            local lineend         = nil                     -- lineend : the last node of the line (and paragraph)
1334            local lastnode        = current_break.cur_break -- lastnode: the node after which the dir nodes should be closed
1335            if not lastnode then
1336                -- only at the end
1337                lastnode = find_tail(head)
1338                if lastnode == par.final_par_glue then
1339                    lineend  = lastnode
1340                    lastnode = getprev(lastnode)
1341                end
1342            else -- todo: use insert_list_after
1343                local id = getid(lastnode)
1344                if id == glue_code then
1345                    local r = new_rightskip(unpack(rightskip))
1346                    setattributelist(r,lastnode)
1347                    lastnode   = replace_node(lastnode,r)
1348                    glue_break = true
1349                    lineend    = lastnode
1350                    lastnode   = getprev(lastnode)
1351                elseif id == disc_code then
1352                    local prevlast, nextlast = getboth(lastnode)
1353                    local pre, post, replace, pretail, posttail, replacetail = getdisc(lastnode,true)
1354                    local subtype = getsubtype(lastnode)
1355                    if subtype == seconddisc_code then
1356                        if not (getid(prevlast) == disc_code and getsubtype(prevlast) == firstdisc_code) then
1357                            report_parbuilders('unsupported disc at location %a',3)
1358                        end
1359                        if pre then
1360                            flushnodelist(pre)
1361                            pre = nil -- signal
1362                        end
1363                        if replace then
1364                            setlink(prevlast,replace)
1365                            setlink(replacetail,lastnode)
1366                            replace = nil -- signal
1367                        end
1368                        setdisc(lastnode,pre,post,replace)
1369                        local pre, post, replace = getdisc(prevlast)
1370                        if pre then
1371                            flushnodelist(pre)
1372                        end
1373                        if replace then
1374                            flushnodelist(replace)
1375                        end
1376                        if post then
1377                            flushnodelist(post)
1378                        end
1379                        setdisc(prevlast) -- nil,nil,nil
1380                    elseif subtype == firstdisc_code then
1381                        -- what is v ... next probably
1382                        if not (getid(v) == disc_code and getsubtype(v) == seconddisc_code) then
1383                            report_parbuilders('unsupported disc at location %a',4)
1384                        end
1385                        setsubtype(nextlast,regulardisc_code)
1386                        setreplace(nextlast,post)
1387                        setpost(lastnode)
1388                    end
1389                    if replace then
1390                        flushnodelist(replace)
1391                    end
1392                    if pre then
1393                        setlink(prevlast,pre)
1394                        setlink(pretail,lastnode)
1395                    end
1396                    if post then
1397                        setlink(lastnode,post)
1398                        setlink(posttail,nextlast)
1399                        post_disc_break = true
1400                    end
1401                    setdisc(lastnode) -- nil, nil, nil
1402                    disc_break = true
1403                elseif id == kern_code then
1404                    setkern(lastnode,0)
1405                elseif id == math_code then
1406                    setkern(lastnode,0) -- surround
1407                    -- new in luatex
1408                    setglue(lastnode) -- zeros
1409                end
1410            end
1411            -- todo: clean up this mess which results from all kind of engine merges
1412            -- (start/end nodes)
1413            -- hm, head ?
1414            lastnode = inject_dirs_at_end_of_line(dirstack,lastnode,getnext(head),current_break.cur_break)
1415            local rightbox = current_break.passive_right_box
1416            if rightbox then
1417                lastnode = insertnodeafter(lastnode,lastnode,copy_node(rightbox))
1418            end
1419            if not lineend then
1420                lineend = lastnode
1421            end
1422            if lineend and lineend ~= head and protrude_chars > 0 then
1423                if par.line_break_dir == righttoleft_code then
1424                    if protrude_chars > 2 then
1425                        local p = lineend
1426                        local l = nil
1427                        -- Backtrack over the last zero glues and dirs.
1428                        while p do
1429                            local id = getid(p)
1430                            if id == dir_code then
1431                                 if getsubtype(p) ~= cancel_code then
1432                                     break
1433                                 end
1434                                 p = getprev(p)
1435                            elseif id == glue_code then
1436                                if getwidth(p) == 0 then
1437                                    p = getprev(p)
1438                                else
1439                                    p = nil
1440                                    break
1441                                end
1442                            elseif id == glyph_code then
1443                                 break
1444                            else
1445                                 p = nil
1446                                 break
1447                            end
1448                        end
1449                         -- When |p| is non zero we have something.
1450                        while p do
1451                            local id = getid(p)
1452                            if id == glyph_code then
1453                                l = p
1454                            elseif id == glue_code then
1455                                if getwidth(p) == 0 then
1456                                    -- No harm done.
1457                                else
1458                                    l = nil
1459                                end
1460                            elseif id == dir_code then
1461                                if getdirection(p) ~= righttoleft_code then
1462                                    p = nil
1463                                end
1464                                break
1465                            elseif id == par_code then
1466                                break
1467                            elseif id == temp_code then
1468                                -- Go on.
1469                            else
1470                                l = nil
1471                            end
1472                            p = getprev(p)
1473                        end
1474                        if l and p then
1475                            local w, last_rightmost_char = right_pw(l)
1476                            if last_rightmost_char and w ~= 0 then
1477                                local k = new_rightmarginkern(copy_node(last_rightmost_char),-w)
1478                                setattributelist(k,l)
1479                                setlink(p,k,l)
1480                            end
1481                        end
1482                    end
1483                else
1484                    local id = getid(lineend)
1485                    local c = nil
1486                    if disc_break and (id == glyph_code or id ~= disc_code) then
1487                        c = lineend
1488                    else
1489                        c = getprev(lineend)
1490                    end
1491                    local p = find_protchar_right(getnext(head),c)
1492                    if p and getid(p) == glyph_code then
1493                        local w, last_rightmost_char = right_pw(p)
1494                        if last_rightmost_char and w ~= 0 then
1495                            -- so we inherit attributes, lineend is new pseudo head
1496                            local k = new_rightmarginkern(copy_node(last_rightmost_char),-w)
1497                            setattributelist(k,p)
1498--                             insertnodeafter(c,c,k)
1499                            insertnodeafter(p,p,k)
1500--                             if c == lineend then
1501--                                 lineend = getnext(c)
1502--                             end
1503                        end
1504                    end
1505                end
1506            end
1507            -- we finish the line
1508            local r = getnext(lineend)
1509            setnext(lineend) -- lineend moves on as pseudo head
1510            local start = getnext(head)
1511            setlink(head,r)
1512            if not glue_break then
1513                local rs = new_rightskip(unpack(rightskip))
1514                setattributelist(rs,lineend)
1515                start, lineend = insertnodeafter(start,lineend,rs)
1516            end
1517            local rs = lineend
1518            -- insert leftbox (if needed after parindent)
1519            local leftbox = current_break.passive_left_box
1520            if leftbox then
1521                local first = getnext(start)
1522                if first and current_line == (par.first_line + 1) and getid(first) == hlist_code and not getlist(first) then
1523                    insertnodeafter(start,start,copy_node(leftbox))
1524                else
1525                    start = insertnodebefore(start,start,copy_node(leftbox))
1526                end
1527            end
1528            if protrude_chars > 0 then
1529                if par.line_break_dir == righttoleft_code then
1530                    if protrude_chars > 2 then
1531                        local p = find_protchar_left(start)
1532                        if p then
1533                            local w, last_leftmost_char = right_pw(p)
1534                            if last_leftmost_char and w ~= 0 then
1535                                local k = new_rightmarginkern(copy_node(last_leftmost_char),-w)
1536                                setattributelist(k,p)
1537                                start = insertnodebefore(start,start,k)
1538                            end
1539                        end
1540                    end
1541                else
1542                    local p = find_protchar_left(start)
1543                    if p and getid(p) == glyph_code then
1544                        local w, last_leftmost_char = left_pw(p)
1545                        if last_leftmost_char and w ~= 0 then
1546                            -- so we inherit attributes, start is pseudo head and moves back
1547                            local k = new_leftmarginkern(copy_node(last_leftmost_char),-w)
1548                            setattributelist(k,p)
1549                            start = insertnodebefore(start,start,k)
1550                        end
1551                    end
1552                end
1553            end
1554            local ls
1555            if leftskip or normalize > 0 then
1556                -- we could check for non zero but we will normalize anyway
1557                ls = new_leftskip(unpack(leftskip))
1558                setattributelist(ls,start)
1559                start = insertnodebefore(start,start,ls)
1560            end
1561            if normalize > 0 then
1562                local par       = nil
1563                local dir       = nil
1564                local indent    = nil
1565                local pars      = nil
1566                local notflocal = 0
1567                for n, id, subtype in nextnode, start do
1568                    if id == hlist_code then
1569                        if normalize > 1 and subtype == indentlist_code then
1570                            indent = n
1571                        end
1572                    elseif id == par_code then
1573                        if startofpar(n) then --- maybe subtype check instead
1574                            par = n
1575                        elseif noflocals then
1576                            noflocals = noflocals + 1
1577                            pars[noflocals] = n
1578                        else
1579                            noflocals = 1
1580                            pars = { n }
1581                        end
1582                    elseif id == dir_code then
1583                        if par and not dir and subtype(n) == cancel_code then
1584                            dir = n
1585                        end
1586                    end
1587                end
1588                if indent then
1589                    local i = new_indentskip(getwidth(indent))
1590                    setattributelist(i,start)
1591                    replace_node(indent,i)
1592                end
1593                if dir then
1594                    local d = new_direction((getdirection(par)))
1595                    setattributelist(d,start)
1596                    replace_node(par,d)
1597                end
1598                if pars then
1599                    for i=1,noflocals do
1600                        start = remove_node(start,pars[i],true)
1601                    end
1602                end
1603            end
1604            local cur_width, cur_indent
1605            if current_line > par.last_special_line then
1606                cur_indent = par.second_indent
1607                cur_width  = par.second_width
1608            elseif parshape then
1609                local shape = parshape[current_line]
1610                cur_indent = shape[1]
1611                cur_width  = shape[2]
1612            else
1613                cur_indent = par.first_indent
1614                cur_width  = par.first_width
1615            end
1616            -- extension
1617         -- if adapt_width then
1618         --     local l, r = adapt_width(par,current_line)
1619         --     cur_indent = cur_indent + l
1620         --     cur_width  = cur_width  - l - r
1621         -- end
1622            --
1623            if normalize > 2 then
1624                local l = new_lefthangskip()
1625                local r = new_righthangskip()
1626                if cur_width ~= hsize then
1627                    cur_indent = hsize - cur_width
1628                end
1629                if cur_indent > 0 then
1630                    setwidth(l,cur_indent)
1631                elseif cur_indent < 0 then
1632                    setwidth(r,-cur_indent)
1633                end
1634                setattributelist(l,start)
1635                setattributelist(r,start)
1636                if normalize > 3 then
1637                    -- makes most sense
1638                    start = insertnodeafter(start,ls,l)
1639                    start = insertnodebefore(start,rs,r)
1640                else
1641                    start = insertnodebefore(start,ls,l)
1642                    start = insertnodeafter(start,rs,r)
1643                end
1644                cur_width = hsize
1645                cur_indent = 0
1646            end
1647            --
1648            statistics.noflines = statistics.noflines + 1
1649            --
1650            -- here we could cleanup: remove all if we have (zero) skips only
1651            --
1652            local finished_line = nil
1653            if adjust_spacing > 0 then
1654                statistics.nofadjustedlines = statistics.nofadjustedlines + 1
1655                finished_line = xpack_nodes(start,cur_width,packing_expanded,par.par_break_dir,par.first_line,current_line) -- ,current_break.analysis)
1656            else
1657                finished_line = xpack_nodes(start,cur_width,packing_exactly,par.par_break_dir,par.first_line,current_line) -- ,current_break.analysis)
1658            end
1659            if protrude_chars > 0 then
1660                statistics.nofprotrudedlines = statistics.nofprotrudedlines + 1
1661            end
1662            -- wrong:
1663            local adjust_head     = texlists.adjust_head
1664            local pre_adjust_head = texlists.pre_adjust_head
1665            --
1666            setshift(finished_line,cur_indent)
1667            --
1668            if texlists.pre_adjust_head ~= pre_adjust_head then
1669                append_list(par, texlists.pre_adjust_head)
1670                texlists.pre_adjust_head = pre_adjust_head
1671            end
1672            append_to_vlist(par,finished_line)
1673            if texlists.adjust_head ~= adjust_head then
1674                append_list(par, texlists.adjust_head)
1675                texlists.adjust_head = adjust_head
1676            end
1677            --
1678            local pen
1679            if current_line + 1 ~= par.best_line then
1680                if current_break.passive_pen_inter then
1681                    pen = current_break.passive_pen_inter
1682                else
1683                    pen = par.inter_line_penalty
1684                end
1685                if current_line == prevgraf + 1 then
1686                    pen = pen + par.club_penalty
1687                end
1688                if current_line + 2 == par.best_line then
1689                    if par.display then
1690                        pen = pen + par.display_widow_penalty
1691                    else
1692                        pen = pen + par.widow_penalty
1693                    end
1694                end
1695                if disc_break then
1696                    if current_break.passive_pen_broken ~= 0 then
1697                        pen = pen + current_break.passive_pen_broken
1698                    else
1699                        pen = pen + par.broken_penalty
1700                    end
1701                end
1702                if pen ~= 0 then
1703                    local p = new_penalty(pen)
1704                    setattributelist(p,par.head)
1705                    append_to_vlist(par,p)
1706                end
1707            end
1708            current_line  = current_line + 1
1709            current_break = current_break.prev_break
1710            if current_break and not post_disc_break then
1711                local current = head
1712                local next    = nil
1713                while true do
1714                    next = getnext(current)
1715                    if next == current_break.cur_break then
1716                        break
1717                    end
1718                    local id = getid(next)
1719                    if id == glyph_code then
1720                        break
1721                    elseif id == par_code then
1722                        -- nothing
1723                    elseif id < math_code then
1724                        -- messy criterium
1725                        break
1726                    elseif id == math_code then
1727                        -- keep the math node
1728                        setkern(next,0) -- surround
1729                        -- new in luatex
1730                        setglue(lastnode) -- zeros
1731                        break
1732                    elseif id == kern_code then
1733                        local subtype = getsubtype(next)
1734                        if subtype == fontkern_code or subtype == accentkern_code then
1735                            -- fontkerns and accent kerns as well as otf injections
1736                            break
1737                        end
1738                    end
1739                    current = next
1740                end
1741                if current ~= head then
1742                    setnext(current)
1743                    flushnodelist(getnext(head))
1744                    setlink(head,next)
1745                end
1746            end
1747par.head = head
1748        end
1749     -- if current_line ~= par.best_line then
1750     --     report_parbuilders("line breaking")
1751     -- end
1752        local h = par.head -- hm, head
1753        if h then
1754            if trace_basic then
1755                if getnext(h) then
1756                    report_parbuilders("something is left over")
1757                end
1758                if getid(h) ~= par_code then
1759                    report_parbuilders("no local par node")
1760                end
1761            end
1762            flushnode(h)
1763            par.head = nil -- needs checking
1764        end
1765        current_line = current_line - 1
1766        if trace_basic then
1767            report_parbuilders("paragraph broken into %a lines",current_line)
1768        end
1769        texset("prevgraf",current_line)
1770    end
1771
1772    local function wrap_up(par)
1773        if par.tracing_paragraphs then
1774            diagnostics.stop()
1775        end
1776        if par.do_last_line_fit then
1777            local best_bet     = par.best_bet
1778            local active_short = best_bet.active_short
1779            local active_glue  = best_bet.active_glue
1780            if active_short == 0 then
1781                if trace_lastlinefit then
1782                    report_parbuilders("disabling last line fit, no active_short")
1783                end
1784                par.do_last_line_fit = false
1785            else
1786                local glue = par.final_par_glue
1787                setwidth(glue,getwidth(glue) + active_short - active_glue)
1788                setfield(glue,"stretch",0)
1789                if trace_lastlinefit then
1790                    report_parbuilders("applying last line fit, short %a, glue %p",active_short,active_glue)
1791                end
1792            end
1793        end
1794        -- This differs from the engine, where the temp node is removed elsewhere.
1795        local head = par.head
1796        if head and getid(head) == temp_code then
1797            local next = getnext(head)
1798            par.head = next
1799            if next then
1800                setprev(next)
1801            end
1802            flushnode(head)
1803        end
1804        post_line_break(par)
1805        reset_meta(par)
1806        register_statistics(par)
1807        return par.head_field
1808    end
1809
1810    -- we could do active nodes differently ... table instead of linked list or a list
1811    -- with prev nodes but it doesn't save much (as we still need to keep indices then
1812    -- in next)
1813
1814    local function deactivate_node(par,prev_prev_r,prev_r,r,cur_active_width,checked_expansion) -- no need for adjust if disabled
1815        local active = par.active
1816        local active_width = par.active_width
1817        prev_r.next = r.next
1818        -- removes r
1819        -- r = nil
1820        if prev_r == active then
1821            r = active.next
1822            if r.id == delta_code then
1823                local aw = active_width.size   + r.size    active_width.size   = aw  cur_active_width.size   = aw
1824                local aw = active_width.normal + r.normal  active_width.normal = aw  cur_active_width.normal = aw
1825                local aw = active_width.fi     + r.fi      active_width.fi     = aw  cur_active_width.fi     = aw
1826                local aw = active_width.fil    + r.fil     active_width.fil    = aw  cur_active_width.fil    = aw
1827                local aw = active_width.fill   + r.fill    active_width.fill   = aw  cur_active_width.fill   = aw
1828                local aw = active_width.filll  + r.filll   active_width.filll  = aw  cur_active_width.filll  = aw
1829                local aw = active_width.shrink + r.shrink  active_width.shrink = aw  cur_active_width.shrink = aw
1830                if checked_expansion then
1831                    local aw = active_width.adjust_stretch + r.adjust_stretch  active_width.adjust_stretch = aw  cur_active_width.adjust_stretch = aw
1832                    local aw = active_width.adjust_shrink  + r.adjust_shrink   active_width.adjust_shrink  = aw  cur_active_width.adjust_shrink  = aw
1833                end
1834                active.next = r.next
1835                -- removes r
1836                -- r = nil
1837            end
1838        elseif prev_r.id == delta_code then
1839            r = prev_r.next
1840            if r == active then
1841                cur_active_width.size   = cur_active_width.size   - prev_r.size
1842                cur_active_width.normal = cur_active_width.normal - prev_r.normal
1843                cur_active_width.fi     = cur_active_width.fi     - prev_r.fi
1844                cur_active_width.fil    = cur_active_width.fil    - prev_r.fil
1845                cur_active_width.fill   = cur_active_width.fill   - prev_r.fill
1846                cur_active_width.filll  = cur_active_width.filll  - prev_r.filll
1847                cur_active_width.shrink = cur_active_width.shrink - prev_r.shrink
1848                if checked_expansion then
1849                    cur_active_width.adjust_stretch = cur_active_width.adjust_stretch - prev_r.adjust_stretch
1850                    cur_active_width.adjust_shrink  = cur_active_width.adjust_shrink  - prev_r.adjust_shrink
1851                end
1852                prev_prev_r.next = active
1853                -- removes prev_r
1854                -- prev_r = nil
1855                prev_r = prev_prev_r
1856            elseif r.id == delta_code then
1857                local rn = r.size     cur_active_width.size   = cur_active_width.size   + rn  prev_r.size   = prev_r.size    + rn
1858                local rn = r.normal   cur_active_width.normal = cur_active_width.normal + rn  prev_r.normal = prev_r.normal  + rn
1859                local rn = r.fi       cur_active_width.fi     = cur_active_width.fi     + rn  prev_r.fi     = prev_r.fi      + rn
1860                local rn = r.fil      cur_active_width.fil    = cur_active_width.fil    + rn  prev_r.fil    = prev_r.fil     + rn
1861                local rn = r.fill     cur_active_width.fill   = cur_active_width.fill   + rn  prev_r.fill   = prev_r.fill    + rn
1862                local rn = r.filll    cur_active_width.filll  = cur_active_width.filll  + rn  prev_r.filll  = prev_r.fill    + rn
1863                local rn = r.shrink   cur_active_width.shrink = cur_active_width.shrink + rn  prev_r.shrink = prev_r.shrink  + rn
1864                if checked_expansion then
1865                    local rn = r.adjust_stretch  cur_active_width.adjust_stretch = cur_active_width.adjust_stretch + rn  prev_r.adjust_stretch = prev_r.adjust_stretch    + rn
1866                    local rn = r.adjust_shrink   cur_active_width.adjust_shrink  = cur_active_width.adjust_shrink  + rn  prev_r.adjust_shrink  = prev_r.adjust_shrink     + rn
1867                end
1868                prev_r.next = r.next
1869                -- removes r
1870                -- r = nil
1871            end
1872        end
1873        return prev_r, r
1874    end
1875
1876    local function lastlinecrap(shortfall,active_short,active_glue,cur_active_width,fill_width,last_line_fit)
1877        if active_short == 0 or active_glue <= 0 then
1878            return false, 0, fit_decent_class, 0, 0
1879        end
1880        if cur_active_width.fi ~= fill_width.fi or cur_active_width.fil ~= fill_width.fil or cur_active_width.fill ~= fill_width.fill or cur_active_width.filll ~= fill_width.filll then
1881            return false, 0, fit_decent_class, 0, 0
1882        end
1883        local adjustment = active_short > 0 and cur_active_width.normal or cur_active_width.shrink
1884        if adjustment <= 0 then
1885            return false, 0, fit_decent_class, adjustment, 0
1886        end
1887        adjustment = calculate_fraction(adjustment,active_short,active_glue,maxdimen)
1888        if last_line_fit < 1000 then
1889            adjustment = calculate_fraction(adjustment,last_line_fit,1000,maxdimen) -- uses previous adjustment
1890        end
1891        local fit_class = fit_decent_class
1892        if adjustment > 0 then
1893            local stretch = cur_active_width.normal
1894            if adjustment > shortfall then
1895                adjustment = shortfall
1896            end
1897            if adjustment > 7230584 and stretch < 1663497 then
1898                return true, fit_very_loose_class, shortfall, adjustment, infinite_badness
1899            end
1900         -- if adjustment == 0 then -- badness = 0
1901         --     return true, shortfall, fit_decent_class, 0, 0
1902         -- elseif stretch <= 0 then -- badness = 10000
1903         --     return true, shortfall, fit_very_loose_class, adjustment, 10000
1904         -- end
1905         -- local badness = (adjustment == 0 and 0) or (stretch <= 0 and 10000) or calculate_badness(adjustment,stretch)
1906            local badness = calculate_badness(adjustment,stretch)
1907            if badness > 99 then
1908                return true, shortfall, fit_very_loose_class, adjustment, badness
1909            elseif badness > 12 then
1910                return true, shortfall, fit_loose_class, adjustment, badness
1911            else
1912                return true, shortfall, fit_decent_class, adjustment, badness
1913            end
1914        elseif adjustment < 0 then
1915            local shrink = cur_active_width.shrink
1916            if -adjustment > shrink then
1917                adjustment = -shrink
1918            end
1919            local badness = calculate_badness(-adjustment,shrink)
1920            if badness > 12 then
1921                return true, shortfall, fit_tight_class, adjustment, badness
1922            else
1923                return true, shortfall, fit_decent_class, adjustment, badness
1924            end
1925        else
1926            return false, 0, fit_decent_class, 0, 0
1927        end
1928    end
1929
1930    -- todo: statistics .. count tries and so
1931
1932    local trialcount = 0
1933
1934    local function try_break(pi, break_type, par, first_p, current, checked_expansion)
1935
1936    -- trialcount = trialcount + 1
1937    -- print(trialcount,pi,break_type,current,nuts.tostring(current))
1938
1939        if pi >= infinite_penalty then          -- this breakpoint is inhibited by infinite penalty
1940            local p_active = par.active
1941            return p_active, p_active and p_active.next
1942        elseif pi <= -infinite_penalty then     -- this breakpoint will be forced
1943            pi = eject_penalty
1944        end
1945
1946        local prev_prev_r         = nil         -- a step behind prev_r, if type(prev_r)=delta_code
1947        local prev_r              = par.active  -- stays a step behind r
1948        local r                   = nil         -- runs through the active list
1949        local no_break_yet        = true        -- have we found a feasible break at current?
1950        local node_r_stays_active = false       -- should node r remain in the active list?
1951        local line_width          = 0           -- the current line will be justified to this width
1952        local line_number         = 0           -- line number of current active node
1953        local old_line_number     = 0           -- maximum line number in current equivalence class of lines
1954
1955        local protrude_chars      = par.protrude_chars
1956        local checked_expansion   = par.checked_expansion
1957        local break_width         = par.break_width
1958        local active_width        = par.active_width
1959        local background          = par.background
1960        local minimal_demerits    = par.minimal_demerits
1961        local best_place          = par.best_place
1962        local best_pl_line        = par.best_pl_line
1963        local best_pl_short       = par.best_pl_short
1964        local best_pl_glue        = par.best_pl_glue
1965        local do_last_line_fit    = par.do_last_line_fit
1966        local final_pass          = par.final_pass
1967        local tracing_paragraphs  = par.tracing_paragraphs
1968     -- local par_active          = par.active
1969
1970     -- local adapt_width         = par.adapt_width
1971
1972        local parshape            = par.par_shape_ptr
1973
1974        local cur_active_width = checked_expansion and { -- distance from current active node
1975            size           = active_width.size,
1976            normal         = active_width.normal,
1977            fi             = active_width.fi,
1978            fil            = active_width.fil,
1979            fill           = active_width.fill,
1980            filll          = active_width.filll,
1981            shrink         = active_width.shrink,
1982            adjust_stretch = active_width.adjust_stretch,
1983            adjust_shrink  = active_width.adjust_shrink,
1984        } or {
1985            size           = active_width.size,
1986            normal         = active_width.normal,
1987            fi             = active_width.fi,
1988            fil            = active_width.fil,
1989            fill           = active_width.fill,
1990            filll          = active_width.filll,
1991            shrink         = active_width.shrink,
1992        }
1993
1994        while true do
1995            r = prev_r.next
1996            if r.id == delta_code then
1997                cur_active_width.size   = cur_active_width.size   + r.size
1998                cur_active_width.normal = cur_active_width.normal + r.normal
1999                cur_active_width.fi     = cur_active_width.fi     + r.fi
2000                cur_active_width.fil    = cur_active_width.fil    + r.fil
2001                cur_active_width.fill   = cur_active_width.fill   + r.fill
2002                cur_active_width.filll  = cur_active_width.filll  + r.filll
2003                cur_active_width.shrink = cur_active_width.shrink + r.shrink
2004                if checked_expansion then
2005                    cur_active_width.adjust_stretch = cur_active_width.adjust_stretch + r.adjust_stretch
2006                    cur_active_width.adjust_shrink  = cur_active_width.adjust_shrink  + r.adjust_shrink
2007                end
2008                prev_prev_r = prev_r
2009                prev_r = r
2010            else
2011                line_number = r.line_number
2012                if line_number > old_line_number then
2013                    local minimum_demerits = par.minimum_demerits
2014                    if minimum_demerits < awful_badness and (old_line_number ~= par.easy_line or r == par.active) then
2015                        if no_break_yet then
2016                            no_break_yet = false
2017                            break_width.size   = background.size
2018                            break_width.normal = background.normal
2019                            break_width.fi     = background.fi
2020                            break_width.fil    = background.fil
2021                            break_width.fill   = background.fill
2022                            break_width.filll  = background.filll
2023                            break_width.shrink = background.shrink
2024                            if checked_expansion then
2025                                break_width.adjust_stretch = 0
2026                                break_width.adjust_shrink  = 0
2027                            end
2028                            if current then
2029                                compute_break_width(par,break_type,current)
2030                            end
2031                        end
2032                        if prev_r.id == delta_code then
2033                            prev_r.size   = prev_r.size   - cur_active_width.size   + break_width.size
2034                            prev_r.normal = prev_r.normal - cur_active_width.normal + break_width.normal
2035                            prev_r.fi     = prev_r.fi     - cur_active_width.fi     + break_width.fi
2036                            prev_r.fil    = prev_r.fil    - cur_active_width.fil    + break_width.fil
2037                            prev_r.fill   = prev_r.fill   - cur_active_width.fill   + break_width.fill
2038                            prev_r.filll  = prev_r.filll  - cur_active_width.filll  + break_width.filll
2039                            prev_r.shrink = prev_r.shrink - cur_active_width.shrink + break_width.shrink
2040                            if checked_expansion then
2041                                prev_r.adjust_stretch = prev_r.adjust_stretch - cur_active_width.adjust_stretch + break_width.adjust_stretch
2042                                prev_r.adjust_shrink  = prev_r.adjust_shrink  - cur_active_width.adjust_shrink  + break_width.adjust_shrink
2043                            end
2044                        elseif prev_r == par.active then
2045                            active_width.size   = break_width.size
2046                            active_width.normal = break_width.normal
2047                            active_width.fi     = break_width.fi
2048                            active_width.fil    = break_width.fil
2049                            active_width.fill   = break_width.fill
2050                            active_width.filll  = break_width.filll
2051                            active_width.shrink = break_width.shrink
2052                            if checked_expansion then
2053                                active_width.adjust_stretch = break_width.adjust_stretch
2054                                active_width.adjust_shrink  = break_width.adjust_shrink
2055                            end
2056                        else
2057                            local q = checked_expansion and {
2058                                id             = delta_code,
2059                                subtype        = nosubtype_code,
2060                                next           = r,
2061                                size           = break_width.size           - cur_active_width.size,
2062                                normal         = break_width.normal         - cur_active_width.normal,
2063                                fi             = break_width.fi             - cur_active_width.fi,
2064                                fil            = break_width.fil            - cur_active_width.fil,
2065                                fill           = break_width.fill           - cur_active_width.fill,
2066                                filll          = break_width.filll          - cur_active_width.filll,
2067                                shrink         = break_width.shrink         - cur_active_width.shrink,
2068                                adjust_stretch = break_width.adjust_stretch - cur_active_width.adjust_stretch,
2069                                adjust_shrink  = break_width.adjust_shrink  - cur_active_width.adjust_shrink,
2070                            } or {
2071                                id      = delta_code,
2072                                subtype = nosubtype_code,
2073                                next    = r,
2074                                size    = break_width.size   - cur_active_width.size,
2075                                normal  = break_width.normal - cur_active_width.normal,
2076                                fi      = break_width.fi     - cur_active_width.fi,
2077                                fil     = break_width.fil    - cur_active_width.fil,
2078                                fill    = break_width.fill   - cur_active_width.fill,
2079                                filll   = break_width.filll  - cur_active_width.filll,
2080                                shrink  = break_width.shrink - cur_active_width.shrink,
2081                            }
2082                            prev_r.next = q
2083                            prev_prev_r = prev_r
2084                            prev_r = q
2085                        end
2086                        local adj_demerits     = par.adj_demerits
2087                        local abs_adj_demerits = adj_demerits > 0 and adj_demerits or -adj_demerits
2088                        if abs_adj_demerits >= awful_badness - minimum_demerits then
2089                            minimum_demerits = awful_badness - 1
2090                        else
2091                            minimum_demerits = minimum_demerits + abs_adj_demerits
2092                        end
2093                        for fit_class = fit_very_loose_class, fit_tight_class do
2094                            if minimal_demerits[fit_class] <= minimum_demerits then
2095                                -- insert a new active node from best_place[fit_class] to current
2096                                par.pass_number = par.pass_number + 1
2097                                local prev_break = best_place[fit_class]
2098                                local passive = {
2099                                    id                          = passive_code,
2100                                    subtype                     = nosubtype_code,
2101                                    next                        = par.passive,
2102                                    cur_break                   = current,
2103                                    serial                      = par.pass_number,
2104                                    prev_break                  = prev_break,
2105                                    passive_pen_inter           = par.internal_pen_inter,
2106                                    passive_pen_broken          = par.internal_pen_broken,
2107                                    passive_last_left_box       = par.internal_left_box,
2108                                    passive_last_left_box_width = par.internal_left_box_width,
2109                                    passive_left_box            = prev_break and prev_break.passive_last_left_box or par.init_internal_left_box,
2110                                    passive_left_box_width      = prev_break and prev_break.passive_last_left_box_width or par.init_internal_left_box_width,
2111                                    passive_right_box           = par.internal_right_box,
2112                                    passive_right_box_width     = par.internal_right_box_width,
2113                                }
2114                                par.passive = passive
2115                                local q = {
2116                                    id             = break_type,
2117                                    subtype        = fit_class,
2118                                    break_node     = passive,
2119                                    line_number    = best_pl_line[fit_class] + 1,
2120                                    total_demerits = minimal_demerits[fit_class], --  or 0,
2121                                    next           = r,
2122                                }
2123                                if do_last_line_fit then
2124                                    local active_short = best_pl_short[fit_class]
2125                                    local active_glue  = best_pl_glue[fit_class]
2126                                    q.active_short = active_short
2127                                    q.active_glue  = active_glue
2128                                    if trace_lastlinefit then
2129                                        report_parbuilders("setting short to %i and glue to %p using class %a",active_short,active_glue,fit_class)
2130                                    end
2131                                end
2132                             -- q.next = r -- already done
2133                                prev_r.next = q
2134                                prev_r = q
2135                                if tracing_paragraphs then
2136                                    diagnostics.break_node(par,q,fit_class,break_type,current)
2137                                end
2138                            end
2139                            minimal_demerits[fit_class] = awful_badness
2140                        end
2141                        par.minimum_demerits = awful_badness
2142                        if r ~= par.active then
2143                            local q = checked_expansion and {
2144                                id             = delta_code,
2145                                subtype        = nosubtype_code,
2146                                next           = r,
2147                                size           = cur_active_width.size           - break_width.size,
2148                                normal         = cur_active_width.normal         - break_width.normal,
2149                                fi             = cur_active_width.fi             - break_width.fi,
2150                                fil            = cur_active_width.fil            - break_width.fil,
2151                                fill           = cur_active_width.fill           - break_width.fill,
2152                                filll          = cur_active_width.filll          - break_width.filll,
2153                                shrink         = cur_active_width.shrink         - break_width.shrink,
2154                                adjust_stretch = cur_active_width.adjust_stretch - break_width.adjust_stretch,
2155                                adjust_shrink  = cur_active_width.adjust_shrink  - break_width.adjust_shrink,
2156                            } or {
2157                                id      = delta_code,
2158                                subtype = nosubtype_code,
2159                                next    = r,
2160                                size    = cur_active_width.size   - break_width.size,
2161                                normal  = cur_active_width.normal - break_width.normal,
2162                                fi      = cur_active_width.fi     - break_width.fi,
2163                                fil     = cur_active_width.fil    - break_width.fil,
2164                                fill    = cur_active_width.fill   - break_width.fill,
2165                                filll   = cur_active_width.filll  - break_width.filll,
2166                                shrink  = cur_active_width.shrink - break_width.shrink,
2167                            }
2168                         -- q.next = r -- already done
2169                            prev_r.next = q
2170                            prev_prev_r = prev_r
2171                            prev_r = q
2172                        end
2173                    end
2174                    if r == par.active then
2175                        return r, r and r.next -- p_active, n_active
2176                    end
2177                    if line_number > par.easy_line then
2178                        old_line_number = max_halfword - 1
2179                        line_width = par.second_width
2180                    else
2181                        old_line_number = line_number
2182                        if line_number > par.last_special_line then
2183                            line_width = par.second_width
2184                        elseif parshape then
2185                            line_width = parshape[line_number][2]
2186                        else
2187                            line_width = par.first_width
2188                        end
2189                    end
2190                 -- if adapt_width then
2191                 --     local l, r = adapt_width(par,line_number)
2192                 --     line_width = line_width  - l - r
2193                 -- end
2194                end
2195                local artificial_demerits = false -- has d been forced to zero
2196                local shortfall = line_width - cur_active_width.size - par.internal_right_box_width -- used in badness calculations
2197                if not r.break_node then
2198                    shortfall = shortfall - par.init_internal_left_box_width
2199                else
2200                    shortfall = shortfall - (r.break_node.passive_last_left_box_width or 0)
2201                end
2202                if protrude_chars > 1 then
2203                    if par.line_break_dir == righttoleft_code then
2204                        -- not now, we need to keep more track
2205                    else
2206                        -- this is quite time consuming
2207                        local b = r.break_node
2208                        local l = b and b.cur_break or first_p
2209                        local o = current and getprev(current)
2210                        if current and getid(current) == disc_code then
2211                            local pre, _, _, pretail = getdisc(current,true)
2212                            if pre then
2213                                o = pretail
2214                            else
2215                                o = find_protchar_right(l,o)
2216                            end
2217                        else
2218                            o = find_protchar_right(l,o)
2219                        end
2220                        if o and getid(o) == glyph_code then
2221                            shortfall = shortfall + right_pw(o)
2222                        end
2223                        local id = getid(l)
2224                        if id == glyph_code then
2225                            -- ok ?
2226                        elseif id == disc_code and getpost(l) then
2227                            l = getpost(l) -- TODO: first char could be a disc
2228                        else
2229                            l = find_protchar_left(l)
2230                        end
2231                        if l and getid(l) == glyph_code then
2232                            shortfall = shortfall + left_pw(l)
2233                        end
2234                    end
2235                end
2236                if checked_expansion and shortfall ~= 0 then
2237                    if shortfall > 0 then
2238                        local total = cur_active_width.adjust_stretch
2239                        if total > 0 then
2240                            if total > shortfall then
2241                                shortfall = total / (par.max_stretch_ratio / par.cur_font_step) / 2
2242                            else
2243                                shortfall = shortfall - total
2244                            end
2245                        end
2246                    elseif shortfall < 0 then
2247                        local total = cur_active_width.adjust_shrink
2248                        if total > 0 then
2249                            if total > - shortfall then
2250                                shortfall = - total / (par.max_shrink_ratio / par.cur_font_step) / 2
2251                            else
2252                                shortfall = shortfall + total
2253                            end
2254                        end
2255                    end
2256                end
2257                local b = 0
2258                local g = 0
2259                local fit_class = fit_decent_class
2260                local found = false
2261                if shortfall > 0  then
2262                    if cur_active_width.fi ~= 0 or cur_active_width.fil ~= 0 or cur_active_width.fill ~= 0 or cur_active_width.filll ~= 0 then
2263                        if not do_last_line_fit then
2264                            -- okay
2265                        elseif not current then
2266                            found, shortfall, fit_class, g, b = lastlinecrap(shortfall,r.active_short,r.active_glue,cur_active_width,par.fill_width,par.last_line_fit)
2267                        else
2268                            shortfall = 0
2269                        end
2270                    else
2271                        local stretch = cur_active_width.normal
2272                        if shortfall > 7230584 and stretch < 1663497 then
2273                            b = infinite_badness
2274                            fit_class = fit_very_loose_class
2275                        else
2276                            b = calculate_badness(shortfall,stretch)
2277                            if b > 99 then
2278                                fit_class = fit_very_loose_class
2279                            elseif b > 12 then
2280                                fit_class = fit_loose_class
2281                            else
2282                                fit_class = fit_decent_class
2283                            end
2284                        end
2285                    end
2286                else
2287                    local shrink = cur_active_width.shrink
2288                    if -shortfall > shrink then
2289                        b = infinite_badness + 1
2290                    else
2291                        b = calculate_badness(-shortfall,shrink)
2292                    end
2293                    if b > 12 then
2294                        fit_class = fit_tight_class
2295                    else
2296                        fit_class = fit_decent_class
2297                    end
2298                end
2299                if do_last_line_fit and not found then
2300                    if not current then
2301                     -- g = 0
2302                        shortfall = 0
2303                    elseif shortfall > 0 then
2304                        g = cur_active_width.normal
2305                    elseif shortfall < 0 then
2306                        g = cur_active_width.shrink
2307                    else
2308                        g = 0
2309                    end
2310                end
2311                -- ::FOUND::
2312                local continue_only = false -- brrr
2313                if b > infinite_badness or pi == eject_penalty then
2314                    if final_pass and par.minimum_demerits == awful_badness and r.next == par.active and prev_r == par.active then
2315                        artificial_demerits = true -- set demerits zero, this break is forced
2316                        node_r_stays_active = false
2317                    elseif b > par.threshold then
2318                        prev_r, r = deactivate_node(par,prev_prev_r,prev_r,r,cur_active_width,checked_expansion)
2319                        continue_only = true
2320                    else
2321                        node_r_stays_active = false
2322                    end
2323                else
2324                    prev_r = r
2325                    if b > par.threshold then
2326                        continue_only = true
2327                    else
2328                        node_r_stays_active = true
2329                    end
2330                end
2331                if not continue_only then
2332                    local d = 0
2333                    if not artificial_demerits then
2334                        d = par.line_penalty + b
2335                        if (d >= 0 and d or -d) >= 10000 then -- abs(d)
2336                            d = 100000000
2337                        else
2338                            d = d * d
2339                        end
2340                        if pi == 0 then
2341                            -- nothing
2342                        elseif pi > 0 then
2343                            d = d + pi * pi
2344                        elseif pi > eject_penalty then
2345                            d = d - pi * pi
2346                        end
2347                        if break_type == hyphenated_code and r.id == hyphenated_code then
2348                            if current then
2349                                d = d + par.double_hyphen_demerits
2350                            else
2351                                d = d + par.final_hyphen_demerits
2352                            end
2353                        end
2354                        local delta = fit_class - r.subtype
2355                        if (delta >= 0 and delta or -delta) > 1 then -- abs(delta)
2356                            d = d + par.adj_demerits
2357                        end
2358                    end
2359                    if tracing_paragraphs then
2360                        diagnostics.feasible_break(par,current,r,b,pi,d,artificial_demerits)
2361                    end
2362                    d = d + r.total_demerits -- this is the minimum total demerits from the beginning to current via r
2363                    if d <= minimal_demerits[fit_class] then
2364                        minimal_demerits[fit_class] = d
2365                        best_place      [fit_class] = r.break_node
2366                        best_pl_line    [fit_class] = line_number
2367                        if do_last_line_fit then
2368                            best_pl_short[fit_class] = shortfall
2369                            best_pl_glue [fit_class] = g
2370                            if trace_lastlinefit then
2371                                report_parbuilders("storing last line fit short %a and glue %p in class %a",shortfall,g,fit_class)
2372                            end
2373                        end
2374                        if d < par.minimum_demerits then
2375                            par.minimum_demerits = d
2376                        end
2377                    end
2378                    if not node_r_stays_active then
2379                        prev_r, r = deactivate_node(par,prev_prev_r,prev_r,r,cur_active_width,checked_expansion)
2380                    end
2381                end
2382            end
2383        end
2384    end
2385
2386    -- we can call the normal one for simple box building in the otr so we need
2387    -- frequent enabling/disabling
2388
2389    local temp_head = new_temp()
2390
2391    function constructors.methods.basic(head,d)
2392        if trace_basic then
2393            report_parbuilders("starting at %a",head)
2394        end
2395        local par = initialize_line_break(head,d)
2396
2397        local checked_expansion  = par.checked_expansion
2398        local active_width       = par.active_width
2399        local disc_width         = par.disc_width
2400        local background         = par.background
2401        local tracing_paragraphs = par.tracing_paragraphs
2402        local dirstack           = { n = 0 }
2403
2404        par.dirstack = dirstack
2405
2406        if tracing_paragraphs then
2407            diagnostics.start()
2408            if par.pretolerance >= 0 then
2409                diagnostics.current_pass(par,"firstpass")
2410            end
2411        end
2412
2413        while true do
2414            reset_meta(par)
2415            if par.threshold > infinite_badness then
2416                par.threshold = infinite_badness
2417            end
2418            par.active.next = {
2419                id             = unhyphenated_code,
2420                subtype        = fit_decent_class,
2421                next           = par.active,
2422                break_node     = nil,
2423                line_number    = par.first_line + 1,
2424                total_demerits = 0,
2425                active_short   = 0,
2426                active_glue    = 0,
2427            }
2428            active_width.size   = background.size
2429            active_width.normal = background.normal
2430            active_width.fi     = background.fi
2431            active_width.fil    = background.fil
2432            active_width.fill   = background.fill
2433            active_width.filll  = background.filll
2434            active_width.shrink = background.shrink
2435
2436            if checked_expansion then
2437                active_width.adjust_stretch = 0
2438                active_width.adjust_shrink  = 0
2439            end
2440
2441            par.passive                 = nil -- = 0
2442            par.printed_node            = temp_head -- only when tracing, shared
2443            par.pass_number             = 0
2444         -- par.auto_breaking           = true
2445
2446            setnext(temp_head,head)
2447
2448            local current               = head
2449            local first_p               = current
2450            local auto_breaking         = true
2451
2452            par.font_in_short_display   = 0
2453
2454            if current then
2455                local id = getid(current)
2456                if id == par_code then
2457                    par.init_internal_left_box       = getfield(current,"box_left")
2458                    par.init_internal_left_box_width = getfield(current,"box_left_width")
2459                    par.internal_pen_inter           = getfield(current,"pen_inter")
2460                    par.internal_pen_broken          = getfield(current,"pen_broken")
2461                    par.internal_left_box            = par.init_internal_left_box
2462                    par.internal_left_box_width      = par.init_internal_left_box_width
2463                    par.internal_right_box           = getfield(current,"box_right")
2464                    par.internal_right_box_width     = getfield(current,"box_right_width")
2465                end
2466            end
2467
2468            -- all passes are combined in this loop so maybe we should split this into
2469            -- three function calls; we then also need to do the wrap_up elsewhere
2470
2471            -- split into normal and expansion loop
2472
2473            -- use an active local
2474
2475            local fontexp, lastfont -- we can pass fontexp to calculate width if needed
2476
2477            -- i flattened the inner loop over glyphs .. it looks nicer and the extra p_active ~= n_active
2478            -- test is fast enough (and try_break now returns the updated values); the kern helper has been
2479            -- inlined as it did a double check on id so in fact we had hardly any code to share
2480
2481            local p_active    = par.active
2482            local n_active    = p_active and p_active.next
2483            local second_pass = par.second_pass
2484
2485            trialcount = 0
2486
2487            while current and p_active ~= n_active do
2488                local char, id = isglyph(current)
2489                if char then
2490                    active_width.size = active_width.size + getwidth(current)
2491                    if checked_expansion then
2492                        local font = id -- == font
2493                        local data = checked_expansion[font]
2494                        if data then
2495                            if font ~= lastfont then
2496                                fontexps = checked_expansion[font] -- a bit redundant for the par line packer
2497                                lastfont = currentfont
2498                            end
2499                            if fontexps then
2500                                local expansion = fontexps[char]
2501                                if expansion then
2502                                    active_width.adjust_stretch = active_width.adjust_stretch + expansion.glyphstretch
2503                                    active_width.adjust_shrink  = active_width.adjust_shrink  + expansion.glyphshrink
2504                                end
2505                            end
2506                        end
2507                    end
2508                elseif id == hlist_code or id == vlist_code then
2509                    active_width.size = active_width.size + getwidth(current)
2510                elseif id == glue_code then
2511                    goto glue
2512                elseif id == disc_code then
2513                    local subtype = getsubtype(current)
2514                    if subtype ~= seconddisc_code then
2515                        local line_break_dir = par.line_break_dir
2516                        if second_pass or subtype <= automaticdisc_code then
2517                            local actual_pen = getpenalty(current)
2518                            local pre, post, replace = getdisc(current)
2519                            if not pre then    --  trivial pre-break
2520                                disc_width.size = 0
2521                                if checked_expansion then
2522                                    disc_width.adjust_stretch = 0
2523                                    disc_width.adjust_shrink  = 0
2524                                end
2525                                p_active, n_active = try_break(actual_pen, hyphenated_code, par, first_p, current, checked_expansion)
2526                            else
2527                                local size, adjust_stretch, adjust_shrink = add_to_width(line_break_dir,checked_expansion,pre)
2528                                disc_width.size   = size
2529                                active_width.size = active_width.size + size
2530                                if checked_expansion then
2531                                    disc_width.adjust_stretch   = adjust_stretch
2532                                    disc_width.adjust_shrink    = adjust_shrink
2533                                    active_width.adjust_stretch = active_width.adjust_stretch + adjust_stretch
2534                                    active_width.adjust_shrink  = active_width.adjust_shrink  + adjust_shrink
2535                                else
2536                                 -- disc_width.adjust_stretch = 0
2537                                 -- disc_width.adjust_shrink  = 0
2538                                end
2539                                p_active, n_active = try_break(actual_pen, hyphenated_code, par, first_p, current, checked_expansion)
2540                                if subtype == firstdisc_code then
2541                                    local cur_p_next = getnext(current)
2542                                    if getid(cur_p_next) ~= disc_code or getsubtype(cur_p_next) ~= seconddisc_code then
2543                                        report_parbuilders("unsupported disc at location %a",1)
2544                                    else
2545                                        local pre = getpre(cur_p_next)
2546                                        if pre then
2547                                            local size, adjust_stretch, adjust_shrink = add_to_width(line_break_dir,checked_expansion,pre)
2548                                            disc_width.size = disc_width.size + size
2549                                            if checked_expansion then
2550                                                disc_width.adjust_stretch = disc_width.adjust_stretch + adjust_stretch
2551                                                disc_width.adjust_shrink  = disc_width.adjust_shrink  + adjust_shrink
2552                                            end
2553                                            p_active, n_active = try_break(actual_pen, hyphenated_code, par, first_p, cur_p_next, checked_expansion)
2554                                            -- there is a comment about something messy here in the source
2555                                        else
2556                                            report_parbuilders("unsupported disc at location %a",2)
2557                                        end
2558                                    end
2559                                end
2560                                -- beware, we cannot restore to a saved value as the try_break adapts active_width
2561                                active_width.size = active_width.size - disc_width.size
2562                                if checked_expansion then
2563                                    active_width.adjust_stretch = active_width.adjust_stretch - disc_width.adjust_stretch
2564                                    active_width.adjust_shrink  = active_width.adjust_shrink  - disc_width.adjust_shrink
2565                                end
2566                            end
2567                        end
2568                        if replace then
2569                            local size, adjust_stretch, adjust_shrink = add_to_width(line_break_dir,checked_expansion,replace)
2570                            active_width.size = active_width.size + size
2571                            if checked_expansion then
2572                                active_width.adjust_stretch = active_width.adjust_stretch + adjust_stretch
2573                                active_width.adjust_shrink  = active_width.adjust_shrink  + adjust_shrink
2574                            end
2575                        end
2576                    end
2577                elseif id == kern_code then
2578                    local s = getsubtype(current)
2579                    local kern = getkern(current)
2580                    if s == userkern_code or s == italickern_code then
2581                        local v = getnext(current)
2582                        if auto_breaking and getid(v) == glue_code then
2583                            p_active, n_active = try_break(0, unhyphenated_code, par, first_p, current, checked_expansion)
2584                        end
2585                        local active_width = par.active_width
2586                        active_width.size = active_width.size + kern
2587                    elseif kern ~= 0 then
2588                        active_width.size = active_width.size + kern
2589                        if checked_expansion and expand_kerns and s == fontkern_code then
2590                            local stretch, shrink = kern_stretch_shrink(current,kern)
2591                            if expand_kerns == "stretch" then
2592                                active_width.adjust_stretch = active_width.adjust_stretch + stretch
2593                            elseif expand_kerns == "shrink" then
2594                                active_width.adjust_shrink  = active_width.adjust_shrink  + shrink
2595                            else
2596                                active_width.adjust_stretch = active_width.adjust_stretch + stretch
2597                                active_width.adjust_shrink  = active_width.adjust_shrink  + shrink
2598                            end
2599                        end
2600                    end
2601                elseif id == math_code then
2602                    auto_breaking = getsubtype(current) == endmath_code
2603                    if iszeroglue(current) or ignoremathskip(current) then
2604                        local v = getnext(current)
2605                        if auto_breaking and getid(v) == glue_code then
2606                            p_active, n_active = try_break(0, unhyphenated_code, par, first_p, current, checked_expansion)
2607                        end
2608                        local active_width = par.active_width
2609                        active_width.size = active_width.size + getkern(current) + getwidth(current)
2610                    else
2611                        goto glue
2612                    end
2613                elseif id == rule_code then
2614                    active_width.size = active_width.size + getwidth(current)
2615                elseif id == penalty_code then
2616                    p_active, n_active = try_break(getpenalty(current), unhyphenated_code, par, first_p, current, checked_expansion)
2617                elseif id == dir_code then
2618                    par.line_break_dir = checked_line_dir(dirstack,current) or par.line_break_dir
2619                elseif id == par_code then
2620                    par.internal_pen_inter       = getfield(current,"pen_inter")
2621                    par.internal_pen_broken      = getfield(current,"pen_broken")
2622                    par.internal_left_box        = getfield(current,"box_left")
2623                    par.internal_left_box_width  = getfield(current,"box_left_width")
2624                    par.internal_right_box       = getfield(current,"box_right")
2625                    par.internal_right_box_width = getfield(current,"box_right_width")
2626                elseif trace_unsupported then
2627                    if id == mark_code or id == insert_code or id == adjust_code then
2628                        -- skip
2629                    else
2630                        report_parbuilders("node of type %a found in paragraph",type(id))
2631                    end
2632                end
2633                goto done
2634              ::glue::
2635                do
2636                    if auto_breaking then
2637                        local prev_p = getprev(current)
2638                        if prev_p and prev_p ~= temp_head then
2639                            local id = getid(prev_p)
2640                            -- we need to check this with the latest patches to the tex kernel
2641                            if (id == glyph_code) or (id < math_code) then
2642                                p_active, n_active = try_break(0, unhyphenated_code, par, first_p, current, checked_expansion)
2643                            elseif id == kern_code then
2644                                local s = getsubtype(prev_p)
2645                                if s ~= userkern_code and s ~= italickern_code then
2646                                    p_active, n_active = try_break(0, unhyphenated_code, par, first_p, current, checked_expansion)
2647                                end
2648                            end
2649                        end
2650                    end
2651                    local width, stretch, shrink, stretch_order, shrink_order = getglue(current)
2652                    if shrink_order ~= 0 and shrink ~= 0 then
2653                        infinite_shrinkage_error(par)
2654                        shrink_order = 0
2655                    end
2656                    local order = fillcodes[stretch_order]
2657                    active_width.size   = active_width.size   + width
2658                    active_width[order] = active_width[order] + stretch
2659                    active_width.shrink = active_width.shrink + shrink
2660                end
2661              ::done::
2662                current = getnext(current)
2663            end
2664            if not current then
2665                local p_active, n_active = try_break(eject_penalty, hyphenated_code, par, first_p, current, checked_expansion)
2666                if n_active ~= p_active then
2667                    local r = n_active
2668                    par.fewest_demerits = awful_badness
2669                    repeat -- use local d
2670                        if r.id ~= delta_code and r.total_demerits < par.fewest_demerits then
2671                            par.fewest_demerits = r.total_demerits
2672                            par.best_bet = r
2673                        end
2674                        r = r.next
2675                    until r == p_active
2676                    par.best_line = par.best_bet.line_number
2677                    local asked_looseness = par.looseness
2678                    if asked_looseness == 0 then
2679                        return wrap_up(par)
2680                    end
2681                    local r = n_active
2682                    local actual_looseness = 0
2683                    -- minimize assignments to par but happens seldom
2684                    repeat
2685                        if r.id ~= delta_code then
2686                            local line_diff = r.line_number - par.best_line
2687                            par.line_diff = line_diff
2688                            if (line_diff < actual_looseness and asked_looseness <= line_diff)   or
2689                               (line_diff > actual_looseness and asked_looseness >= line_diff) then
2690                                par.best_bet = r
2691                                actual_looseness = line_diff
2692                                par.fewest_demerits = r.total_demerits
2693                            elseif line_diff == actual_looseness and r.total_demerits < par.fewest_demerits then
2694                                par.best_bet = r
2695                                par.fewest_demerits = r.total_demerits
2696                            end
2697                        end
2698                        r = r.next
2699                    until r == p_active
2700                    par.best_line = par.best_bet.line_number
2701                    if actual_looseness == asked_looseness or par.final_pass then
2702                        return wrap_up(par)
2703                    end
2704                end
2705            end
2706            reset_meta(par) -- clean up the memory by removing the break nodes
2707            if not second_pass then
2708                if tracing_paragraphs then
2709                    diagnostics.current_pass(par,"secondpass")
2710                end
2711                par.threshold   = par.tolerance
2712                par.second_pass = true
2713                par.final_pass  = par.emergency_stretch <= 0
2714            else
2715                if tracing_paragraphs then
2716                    diagnostics.current_pass(par,"emergencypass")
2717                end
2718                par.background.normal = par.background.normal + par.emergency_stretch
2719                par.final_pass        = true
2720            end
2721        end
2722        return wrap_up(par)
2723    end
2724
2725end
2726
2727-- standard tex logging .. will be adapted ..
2728
2729do
2730
2731    local tonumber   = tonumber
2732    local utfchar    = utf.char
2733    local write      = texio.write
2734    local write_nl   = texio.write_nl
2735    local formatters = string.formatters
2736
2737    local function write_esc(cs)
2738        local esc = texget("escapechar")
2739        if esc then
2740            write("log",utfchar(esc),cs)
2741        else
2742            write("log",cs)
2743        end
2744    end
2745
2746    function diagnostics.start()
2747    end
2748
2749    function diagnostics.stop()
2750        write_nl("log",'')
2751    end
2752
2753    function diagnostics.current_pass(par,what)
2754        write_nl("log",formatters["@%s"](what))
2755    end
2756
2757    local verbose = false -- true
2758
2759    local function short_display(target,a,font_in_short_display)
2760        while a do
2761            local char, id = isglyph(a)
2762            if char then
2763                -- id == font
2764                if id ~= font_in_short_display then
2765                    write(target,tex.fontidentifier(id) .. ' ')
2766                    font_in_short_display = id
2767                end
2768                local u = chardata[id][char]
2769                local u = u.unicode or char
2770                if type(u) == "table" then
2771                    for i=1,#u do
2772                        write(target,utfchar(u[i]))
2773                    end
2774                else
2775                    write(target,utfchar(u))
2776                end
2777            elseif id == disc_code then
2778                local pre, post, replace = getdisc(a)
2779                font_in_short_display = short_display(target,pre,font_in_short_display)
2780                font_in_short_display = short_display(target,post,font_in_short_display)
2781            elseif verbose then
2782                write(target,formatters["[%s]"](nodecodes[id]))
2783            elseif id == rule_code then
2784                write(target,"|")
2785            elseif id == glue_code then
2786                write(target," ")
2787            elseif id == kern_code then
2788                local s = getsubtype(a)
2789                if s == fontkern_code or s == accentkern_code then
2790                    if verbose then
2791                        write(target,"[|]")
2792                 -- else
2793                 --     write(target,"")
2794                    end
2795                else
2796                    write(target,"[]")
2797                end
2798            elseif id == math_code then
2799                write(target,"$")
2800            else
2801                write(target,"[]")
2802            end
2803            a = getnext(a)
2804        end
2805        return font_in_short_display
2806    end
2807
2808    diagnostics.short_display = short_display
2809
2810    function diagnostics.break_node(par, q, fit_class, break_type, current) -- %d ?
2811        local passive = par.passive
2812        local typ_ind = break_type == hyphenated_code and '-' or ""
2813        if par.do_last_line_fit then
2814            local s = q.active_short
2815            local g = q.active_glue
2816            if current then
2817                write_nl("log",formatters["@@%d: line %d.%d%s t=%s s=%p g=%p"](
2818                    passive.serial or 0,q.line_number-1,fit_class,typ_ind,q.total_demerits,s,g))
2819            else
2820                write_nl("log",formatters["@@%d: line %d.%d%s t=%s s=%p a=%p"](
2821                    passive.serial or 0,q.line_number-1,fit_class,typ_ind,q.total_demerits,s,g))
2822            end
2823        else
2824            write_nl("log",formatters["@@%d: line %d.%d%s t=%s"](
2825                passive.serial or 0,q.line_number-1,fit_class,typ_ind,q.total_demerits))
2826        end
2827        if not passive.prev_break then
2828            write("log"," -> @0")
2829        else
2830            write("log",formatters[" -> @%d"](passive.prev_break.serial or 0))
2831        end
2832    end
2833
2834    function diagnostics.feasible_break(par, current, r, b, pi, d, artificial_demerits)
2835        local printed_node = par.printed_node
2836        if printed_node ~= current then
2837            write_nl("log","")
2838            if not current then
2839                par.font_in_short_display = short_display("log",getnext(printed_node),par.font_in_short_display)
2840            else
2841                local save_link = getnext(current)
2842                setnext(current)
2843                write_nl("log","")
2844                par.font_in_short_display = short_display("log",getnext(printed_node),par.font_in_short_display)
2845                setnext(current,save_link)
2846            end
2847            par.printed_node = current
2848        end
2849        write_nl("log","@")
2850        if not current then
2851            write_esc("par")
2852        else
2853            local id = getid(current)
2854            if id == glue_code then
2855                -- print nothing
2856            elseif id == penalty_code then
2857                write_esc("penalty")
2858            elseif id == disc_code then
2859                write_esc("discretionary")
2860            elseif id == kern_code then
2861                write_esc("kern")
2862            elseif id == math_code then
2863                write_esc("math")
2864            else
2865                write_esc("unknown")
2866            end
2867        end
2868        local via, badness, demerits = 0, '*', '*'
2869        if r.break_node then
2870            via = r.break_node.serial or 0
2871        end
2872        if b <= infinite_badness then
2873            badness = tonumber(d)
2874        end
2875        if not artificial_demerits then
2876            demerits = tonumber(d)
2877        end
2878        write("log",formatters[" via @%d b=%s p=%s d=%s"](via,badness,pi,demerits))
2879    end
2880
2881    --
2882
2883    local function common_message(hlist,line,str)
2884        write_nl("")
2885        if CONTEXTLMTXMODE > 0 and tex.getoutputactive() or status.output_active then
2886            write(str," has occurred while \\output is active")
2887        else
2888            write(str)
2889        end
2890        local fileline = status.linenumber
2891        if line > 0 then
2892            write(formatters[" in paragraph at lines %s--%s"](fileline,"--",fileline+line-1))
2893        elseif line < 0 then
2894            write(formatters[" in alignment at lines "](fileline,"--",fileline-line-1))
2895        else
2896            write(formatters[" detected at line %s"](fileline))
2897        end
2898        write_nl("")
2899        diagnostics.short_display(getlist(hlist),false)
2900        write_nl("")
2901     -- diagnostics.start()
2902     -- show_box(getlist(hlist))
2903     -- diagnostics.stop()
2904    end
2905
2906    function diagnostics.overfull_hbox(hlist,line,d)
2907        common_message(hlist,line,formatters["Overfull \\hbox (%p too wide)"](d))
2908    end
2909
2910    function diagnostics.bad_hbox(hlist,line,b)
2911        common_message(hlist,line,formatters["Tight \\hbox (badness %i)"](b))
2912    end
2913
2914    function diagnostics.underfull_hbox(hlist,line,b)
2915        common_message(hlist,line,formatters["Underfull \\hbox (badness %i)"](b))
2916    end
2917
2918    function diagnostics.loose_hbox(hlist,line,b)
2919        common_message(hlist,line,formatters["Loose \\hbox (badness %i)"](b))
2920    end
2921
2922    -- reporting --
2923
2924    statistics.register("alternative parbuilders", function()
2925        if nofpars > 0 then
2926            return formatters["%s paragraphs, %s lines (%s protruded, %s adjusted)"](nofpars,noflines,nofprotrudedlines,nofadjustedlines)
2927        end
2928    end)
2929
2930end
2931
2932do
2933
2934    -- actually scaling kerns is not such a good idea and it will become
2935    -- configureable
2936
2937    -- This is no way a replacement for the built in (fast) packer
2938    -- it's just an alternative for special (testing) purposes.
2939    --
2940    -- We could use two hpacks: one to be used in the par builder
2941    -- and one to be used for other purposes. The one in the par
2942    -- builder is much more simple as it does not need the expansion
2943    -- code but only need to register the effective expansion factor
2944    -- with the glyph.
2945
2946    local setnodecolor = nodes.tracers.colors.set
2947
2948    local function hpack(head,width,method,direction,firstline,line) -- fast version when head = nil
2949
2950        -- we can pass the adjust_width and adjust_height so that we don't need to recalculate them but
2951        -- with the glue mess it's less trivial as we lack detail .. challenge
2952
2953        local hlist = new_hlist()
2954
2955        setdirection(hlist,direction)
2956        setattributelist(hlist,head)
2957
2958        if head == nil then
2959            setwidth(hlist,width)
2960            return hlist, 0
2961        else
2962            setlist(hlist,head)
2963        end
2964
2965        local cal_expand_ratio  = method == packing_expanded or method == packing_substitute
2966
2967        direction               = direction or texget("textdir")
2968
2969        local line              = 0
2970
2971        local height            = 0
2972        local depth             = 0
2973        local natural           = 0
2974        local font_stretch      = 0
2975        local font_shrink       = 0
2976        local font_expand_ratio = 0
2977        local last_badness      = 0
2978        local expansion_stack   = cal_expand_ratio and { } -- todo: optionally pass this
2979        local expansion_index   = 0
2980        local total_stretch     = { [0] = 0, 0, 0, 0, 0 }
2981        local total_shrink      = { [0] = 0, 0, 0, 0, 0 }
2982
2983        local hpack_dir         = direction
2984
2985        local adjust_head       = texlists.adjust_head
2986        local pre_adjust_head   = texlists.pre_adjust_head
2987        local adjust_tail       = adjust_head and find_tail(adjust_head)
2988        local pre_adjust_tail   = pre_adjust_head and find_tail(pre_adjust_head)
2989
2990        local checked_expansion = false
2991
2992        if cal_expand_ratio then
2993            checked_expansion = { }
2994            setmetatableindex(checked_expansion,check_expand_lines)
2995        end
2996
2997        -- this one also needs to check the font, so in the end indeed we might end up with two variants
2998
2999        -- we now have fast loops so maybe no longer a need for an expansion stack
3000
3001        local fontexps, lastfont
3002
3003        local function process(current) -- called nested in disc replace
3004            while current do
3005                local char, id = isglyph(current)
3006                if char then
3007                    if cal_expand_ratio then
3008                        local font = id -- == font
3009                        if font ~= lastfont then
3010                            fontexps = checked_expansion[font] -- a bit redundant for the par line packer
3011                            lastfont = font
3012                        end
3013                        if fontexps then
3014                            local expansion = fontexps[char]
3015                            if expansion then
3016                                font_stretch = font_stretch + expansion.glyphstretch
3017                                font_shrink  = font_shrink  + expansion.glyphshrink
3018                                expansion_index = expansion_index + 1
3019                                expansion_stack[expansion_index] = current
3020                            end
3021                        end
3022                    end
3023                    local wd, ht, dp = getwhd(current)
3024                    if ht > height then
3025                        height = ht
3026                    end
3027                    if dp > depth then
3028                        depth = dp
3029                    end
3030                    natural = natural + wd
3031                elseif id == kern_code then
3032                    local kern = getkern(current)
3033                    if kern == 0 then
3034                        -- no kern
3035                    elseif getsubtype(current) == fontkern_code then
3036                        if cal_expand_ratio then
3037                            local stretch, shrink = kern_stretch_shrink(current,kern)
3038                            font_stretch = font_stretch + stretch
3039                            font_shrink  = font_shrink + shrink
3040                            expansion_index = expansion_index + 1
3041                            expansion_stack[expansion_index] = current
3042                        end
3043                        natural = natural + kern
3044                    else
3045                        natural = natural + kern
3046                    end
3047                elseif id == disc_code then
3048                    local subtype = getsubtype(current)
3049                    if subtype ~= seconddisc_code then
3050                        -- todo : local stretch, shrink = char_stretch_shrink(s)
3051                        local replace = getreplace(current)
3052                        if replace then
3053                            process(replace)
3054                        end
3055                    end
3056                elseif id == glue_code then
3057                    local wd, stretch, shrink, stretch_order, shrink_order = getglue(current)
3058                    total_stretch[stretch_order] = total_stretch[stretch_order] + stretch
3059                    total_shrink [shrink_order]  = total_shrink[shrink_order]   + shrink
3060                    if getsubtype(current) >= leaders_code then
3061                        local wd, ht, dp = getwhd(leader)
3062                        local leader = getleader(current)
3063                        if ht > height then
3064                            height = ht
3065                        end
3066                        if dp > depth then
3067                            depth = dp
3068                        end
3069                    end
3070                    natural = natural + wd
3071                elseif id == hlist_code or id == vlist_code then
3072                    local wd, ht, dp = getwhd(current)
3073                    local sh = getshift(current)
3074                    local hs = ht - sh
3075                    local ds = dp + sh
3076                    if hs > height then
3077                        height = hs
3078                    end
3079                    if ds > depth then
3080                        depth = ds
3081                    end
3082                    natural = natural + wd
3083                elseif id == rule_code or id == unset_code then
3084                    local wd, ht, dp = getwhd(current)
3085                    if ht > height then
3086                        height = ht
3087                    end
3088                    if dp > depth then
3089                        depth = dp
3090                    end
3091                    natural = natural + wd
3092                elseif id == math_code then
3093                    if iszeroglue(current) or ignoremathskip(current) then
3094                        natural = natural + getkern(current)
3095                    else
3096                        local wd, stretch, shrink, stretch_order, shrink_order = getglue(current)
3097                        total_stretch[stretch_order] = total_stretch[stretch_order] + stretch
3098                        total_shrink [shrink_order]  = total_shrink[shrink_order]   + shrink
3099                        natural = natural + wd
3100                    end
3101                elseif id == insert_code or id == mark_code then
3102                    local prev, next = getboth(current)
3103                    if adjust_tail then -- todo
3104                        setlink(prev,next)
3105                        setlink(adjust_tail,current)
3106                        setnext(current)
3107                        adjust_tail = current
3108                    else
3109                        adjust_head = current
3110                        adjust_tail = current
3111                        setboth(current)
3112                    end
3113                elseif id == adjust_code then
3114                    local list = getlist(current)
3115                    if adjust_tail then
3116                        setnext(adjust_tail,list)
3117                    else
3118                        adjust_head = list
3119                    end
3120                    adjust_tail = find_tail(list)
3121                elseif id == dir_code then
3122                    -- no need to deal with directions here (as we only support two)
3123                elseif id == marginkern_code then
3124                    -- not in lmtx
3125                    natural = natural + getwidth(current)
3126                end
3127                current = getnext(current)
3128            end
3129
3130        end
3131
3132        process(head)
3133
3134        if adjust_tail then
3135            adjust_tail.next = nil -- todo
3136        end
3137        if pre_adjust_tail then
3138            pre_adjust_tail.next = nil -- todo
3139        end
3140        if method == packing_additional then
3141            width = width + natural
3142        end
3143        setwhd(hlist,width,height,depth)
3144        local delta  = width - natural
3145        if delta == 0 then
3146            setglue(hlist,0,0,0) -- set order sign
3147        elseif delta > 0 then
3148            -- natural width smaller than requested width
3149            local order = (total_stretch[4] ~= 0 and 4) or (total_stretch[3] ~= 0 and 3) or
3150                          (total_stretch[2] ~= 0 and 2) or (total_stretch[1] ~= 0 and 1) or 0
3151            if cal_expand_ratio and order == 0 and font_stretch > 0 then -- check sign of font_stretch
3152                font_expand_ratio = delta/font_stretch
3153                if font_expand_ratio > 1 then
3154                    font_expand_ratio = 1
3155                elseif font_expand_ratio < -1 then
3156                    font_expand_ratio = -1
3157                end
3158                local fontexps, lastfont
3159                for i=1,expansion_index do
3160                    local g = expansion_stack[i]
3161                    local e = 0
3162                    local char, font = isglyph(g)
3163                    if char then
3164                        if font ~= lastfont then
3165                            fontexps = expansions[font]
3166                            lastfont = font
3167                        end
3168                        local data = fontexps[char]
3169                        if data then
3170                            if trace_expansion then
3171                                setnodecolor(g,"hz:positive")
3172                            end
3173                            e = font_expand_ratio * data.glyphstretch
3174                        end
3175                    else
3176                        local kern = getkern(g)
3177                        local stretch, shrink = kern_stretch_shrink(g,kern)
3178                        e = font_expand_ratio * stretch
3179                    end
3180                    setexpansion(g,e)
3181                end
3182                font_stretch = font_expand_ratio * font_stretch
3183                delta = delta - font_stretch
3184            end
3185            local tso = total_stretch[order]
3186            if tso ~= 0 then
3187                setglue(hlist,delta/tso,order,1) -- set order sign
3188            else
3189                setglue(hlist,0,order,0) -- set order sign
3190            end
3191            if font_expand_ratio ~= 0 then
3192                -- todo
3193            elseif order == 0 then -- and getlist(hlist) then
3194                last_badness = calculate_badness(delta,total_stretch[0])
3195                if last_badness > texget("hbadness") then
3196                    if last_badness > 100 then
3197                        diagnostics.underfull_hbox(hlist,line,last_badness)
3198                    else
3199                        diagnostics.loose_hbox(hlist,line,last_badness)
3200                    end
3201                end
3202            end
3203        else
3204            -- natural width larger than requested width
3205            local order = (total_shrink[4] ~= 0 and 4) or (total_shrink[3] ~= 0 and 3)
3206                       or (total_shrink[2] ~= 0 and 2) or (total_shrink[1] ~= 0 and 1) or 0
3207            if cal_expand_ratio and order == 0 and font_shrink > 0 then -- check sign of font_shrink
3208                font_expand_ratio = delta/font_shrink
3209                if font_expand_ratio > 1 then
3210                    font_expand_ratio = 1
3211                elseif font_expand_ratio < -1 then
3212                    font_expand_ratio = -1
3213                end
3214                local fontexps, lastfont
3215                for i=1,expansion_index do
3216                    local g = expansion_stack[i]
3217                    local e = 0
3218                    local char, font = isglyph(g)
3219                    if char then
3220                        if font ~= lastfont then
3221                            fontexps = expansions[font]
3222                            lastfont = font
3223                        end
3224                        local data = fontexps[char]
3225                        if data then
3226                            if trace_expansion then
3227                                setnodecolor(g,"hz:negative")
3228                            end
3229                            e = font_expand_ratio * data.glyphshrink
3230                        end
3231                    else
3232                        local kern = getkern(g)
3233                        local stretch, shrink = kern_stretch_shrink(g,kern)
3234                        e = font_expand_ratio * shrink
3235                    end
3236                    setexpansion(g,e)
3237                end
3238                font_shrink = font_expand_ratio * font_shrink
3239                delta = delta - font_shrink
3240            end
3241            local tso = total_shrink[order]
3242            if tso ~= 0 then
3243                setglue(hlist,-delta/tso,order,2) -- set order sign
3244            else
3245                setglue(hlist,0,order,0) -- set order sign
3246            end
3247            if font_expand_ratio ~= 0 then
3248                -- todo
3249            elseif tso < -delta and order == 0 then
3250                last_badness = 1000000
3251                setfield(hlist,"glue_set",1)
3252                local fuzz  = - delta - tso
3253                local hfuzz = texget("hfuzz")
3254                if fuzz > hfuzz or texget("hbadness") < 100 then
3255                    local overfullrule = texget("overfullrule")
3256                    if fuzz > hfuzz and overfullrule > 0 then
3257                        -- weird, is always called and no rules shows up
3258                        setnext(find_tail(list),new_rule(overfullrule,nil,nil,getdirection(hlist)))
3259                    end
3260                    diagnostics.overfull_hbox(hlist,line,fuzz)
3261                    if head and getnormalizeline() > 4 then
3262                        -- we need to get rid of this one when we unpack a box but on the
3263                        -- other hand, we only do this when a specific width is set so
3264                        -- probably we have a fixed box then
3265                        local h = getnext(head)
3266                        if h then
3267                            local found = find_node(glue_code,rightskip_code)
3268                            if found then
3269                                local p = getprev(found)
3270                                local g = new_correctionskip(-fuzz)
3271                                setattributelist(g,found)
3272                                if p and getid(p) == marginkern_code then
3273                                    found = p
3274                                end
3275                                insertnodebefore(head,found,g)
3276                            end
3277                        end
3278                    end
3279                end
3280            elseif order == 0 and getlist(hlist) and last_badness > texget("hbadness") then
3281                diagnostics.bad_hbox(hlist,line,last_badness)
3282            end
3283        end
3284        return hlist, last_badness
3285    end
3286
3287    xpack_nodes = hpack -- comment this for old fashioned expansion (we need to fix float mess)
3288
3289    constructors.methods.hpack = hpack
3290
3291end
3292