From c7c1e843dca195d32cb6d976f4f75ffd942d573a Mon Sep 17 00:00:00 2001 From: Karl Berry Date: Sun, 20 Feb 2022 21:21:01 +0000 Subject: linebreaker (20feb22) git-svn-id: svn://tug.org/texlive/trunk@62106 c570f23f-e606-0410-a88d-b1316a301751 --- .../tex/lualatex/linebreaker/linebreaker.lua | 453 +++++++++++++++++++++ 1 file changed, 453 insertions(+) create mode 100644 Master/texmf-dist/tex/lualatex/linebreaker/linebreaker.lua (limited to 'Master/texmf-dist/tex/lualatex/linebreaker/linebreaker.lua') diff --git a/Master/texmf-dist/tex/lualatex/linebreaker/linebreaker.lua b/Master/texmf-dist/tex/lualatex/linebreaker/linebreaker.lua new file mode 100644 index 00000000000..e6c05d4fdf7 --- /dev/null +++ b/Master/texmf-dist/tex/lualatex/linebreaker/linebreaker.lua @@ -0,0 +1,453 @@ +local linebreaker = {} + +local hlist_id = node.id "hlist" +local glyph_id = node.id "glyph" +local glue_id = node.id "glue" +local vlist_id = node.id "vlist" +local maxval = 0x10FFFF + +local fonts = fonts or {} +fonts.hashes = fonts.hashes or {} +local font_identifiers = fonts.hashes.identifiers or {} + + +-- debugging function, it can be redefined to print debug info if needed +-- it discards arguments by default +function linebreaker.debug_print(...) + if linebreaker.debug then + print(table.concat({...}, "\t")) + end +end + +linebreaker.debug = false + +-- max allowed value of tolerance +linebreaker.max_tolerance = 9999 +-- maximal allowed emergencystretch +linebreaker.max_emergencystretch = tex.sp("3em") +-- line breaking function is customizable +linebreaker.breaker = tex.linebreak -- linebreak function +linebreaker.max_cycles = 30 -- max # of attempts to find best solution + -- the number is totally arbitrary + +linebreaker.boxsize = 65536 -- it is used in river detection. default box size is 1pt. + -- value is in scaled points +linebreaker.vertical_point = tex.baselineskip.width -- vertical matrix +linebreaker.previous_points = linebreaker.vertical_point / linebreaker.boxsize + -- number of + -- points which will be taken into account in + -- calculating river value. these points will + -- be processed in both directions +-- factor which will multiply the parindent value to get the minimal allowed width +-- of a last line in a paragraph +linebreaker.width_factor = 1.5 +-- will be linebreaker active? +linebreaker.active = true +-- return array with default parameters +function linebreaker.parameters() + return {} +end + +-- diagnostic function for traversing nodes returned by linebreaking +-- function. only top level nodes are processed, not sublists +function linebreaker.traverse(head) + --for n in node.traverse(node.tail(head).head) do + for n in node.traverse(head) do + linebreaker.debug_print(n.id, n.subtype) + if n.id == 10 then + local x = n.spec or {} + --x.shrink = 111222 + linebreaker.debug_print("glue", x.shrink,x.stretch) + end + end + linebreaker.debug_print "****************" + return head +end + + +local utfchar = unicode.utf8.char + +local getchar = function(n) + local t = {} + local xchar = font_identifiers[n.font].characters[n.char].unicode + + if type(xchar) == "table" then + for k,v in pairs(xchar) do + t[#t+1] = utfchar(v) + end + else + -- 8-bit fonts don't contain the unicode value, so just return the char + -- value of node. In some cases it will be good, for math it will be mostly wrong + return utfchar(xchar or n.char) + end + return table.concat(t) +end + +-- get text content of node list +local function get_text(line) + local t = {} + for n in node.traverse(line) do + if n.id == glue_id then t[#t+1] = " " + elseif n.id == glyph_id then t[#t+1] = getchar(n) + elseif n.id == hlist_id or n.id == vlist_id then t[#t+1] = get_text(n.head) + end + end + return table.concat(t) +end + +-- find badness of a line +function linebreaker.par_badness(head) + local n = 0 + for line in node.traverse_id(hlist_id, head) do + -- print(get_text(line.head), line.glue_order, line.glue_sign, line.glue_set) + -- glue_sign: > 0 = normal, 1 = stretch, 2 = shrink + -- we count only shrink, but stretch may result in overfull box as well + -- I just don't know, how to detect which value of glue_set means error + if line.glue_sign == 2 and line.glue_set >= 1 then n = n + 1 end + end; + return n +end + +-- we have table with guessed param tables. we loop over them and find one with +-- lowest value of badness. this situation shouldn't happen, as at the moment +-- tolerance may be as high as 9999 and this should fix all overfulls +-- this code is remain of older method of guessing right value of tolerance +local function find_best(params) + local min = 10000 -- arbitrary high value + local n = params[1] or {} + for _, p in ipairs(params) do + local badness = p.badness or min + if badness <= min then + n = p + min = badness + end + end + linebreaker.debug_print "best solution" + for k,v in pairs(n) do + linebreaker.debug_print(k,v) + end + return n +end + +-- all glue_spec nodes has .width key, but it is the same all the time. real +-- width depends on line shrink and stretch +-- this will be used in river detection +local function glue_calc(n, sign,set) + -- function for calculating glue width + local size + if sign ==2 then + size=n.spec.width - n.spec.shrink*set + else + size=n.spec.width + n.spec.stretch*set + end + return size +end + + +-- calculate new tolerance +-- max_tolerance / max_cycles is added to the current tolerance value +local function calc_tolerance(previous) + local previous = previous or tex.tolerance + local max_cycles = linebreaker.max_cycles + local max_tolerance = linebreaker.max_tolerance + local new = previous + (max_tolerance / max_cycles)-- + math.sqrt(previous * 4) + return (new < max_tolerance) and new or max_tolerance +end + +-- river detection -- it doesn't work at the moment, maybe in the future? +-- idea is following: +-- 1. count widths of words and spaces +-- 2. divide widths to segments of some width (1pt?) +-- 3. assign number to segments: full glyph in the midle of a word:0 +-- full glue: 1 +-- edges of words: fraction depending on glyph dimensions +-- (it would be nice to incorporate glyph shapes, but it is +-- unrealistic, we don't have access) +-- 4. add numbers from previous line, probably sum of segments in some +-- distance (baselineskip / segments per sp = 45°?) +-- 5. sum segments for a glue / glue width = river ratio? +-- 6. find right threshold for telling which value of river ratio is a real +-- river +-- 7. calculate river ratio for whole paragraph (sum of over threshold +-- river ratios?) +-- I am not a mathematician, so I don't know whether this method is accurate, +-- correct, or efficient, +-- +-- +function linebreaker.detect_rivers(head) + local lines = {} -- + local boxsize = linebreaker.boxsize + local vertical_point = linebreaker.vertical_point + local previous_points = math.ceil(linebreaker.previous_points) + -- calculate river for current node `n` and insert values to + local calc_river = function(line,n, lines) + -- get previous line + local previous = lines and lines[#lines] or {} + local get_point = function(i) + return previous[i] or 0 + end + local x = #line + --print("soucasna delka line", x) + local sum = 0 + for i = 1, #n do + local v = n[i] or 0 + if v > 0 then + v = v + get_point(i) + -- ve add values from previous line + --for c = 1, previous_points do + local c = previous_points + v = v + (get_point(i+x+c)) + (get_point(i+x-c)) + --print("adding",v) + --end + end + line[i+x] = v + sum = sum + v + --print("Calculate for", i,v) + --print("celkem v", i+x,v) + end + return line, sum / #n + end + for n in node.traverse_id(0, head) do + local line = {} + -- glue parameters + local set = n.glue_set + local sign = n.glue_sign + local order = n.glue_order + local first_node = n.head + local first_glyph = nil + local first = true + local word_count = 0 + local last_glyph = nil + local last_glue = n.head + local position = 0 + local remain = 0 + local get_glyph_black = function(glyph) + -- only calculate blackness for glyphs + if glyph and glyph.id == glyph_id then + local w,h,d = node.dimensions(glyph, glyph.next) + -- 1 is maximal white + local blackness = 1 - ((h+d) / vertical_point) + -- print(char(glyph.char), blackness) return w / boxsize or 0, blackness + end + return 0,0 + end + -- get width of nodes + local get_width = function(start,fin) + local w = node.dimensions(set,sign,order,start, fin) + return w / boxsize -- get width in pt + end + local add_word = function(start,fin) + word_count = word_count + 1 + local t = {} + local width = get_width(start,fin) + -- first and last glyph are taken into account for blackness calculation + local w1, f = get_glyph_black(first_glyph) + local w2, l = get_glyph_black(last_glyph) + w1 = math.ceil(w1 + remain) + w2 = math.ceil(w2) + if word_count <= 1 then + w1 = 0 + end + width = width + remain + remain = width - math.floor(width) + width = width - remain + for i=1, w1 do + t[#t+1] = f/i -- add more black at the end of glyph + end + -- middle of the word + for i=1, (width-w1-w2) do + t[#t+1] = 0 + end + -- last glyph + for i=1, w2 do + t[#t+1] = l/(w2-i+1) + end + line = calc_river(line, t, lines) + --print("black", f,l) + end + add_glue = function(x) + local t = {} + local r + local width = get_width(x,x.next) + remain + remain = width - math.floor(width) + width = width - remain + for i=1, width do + t[#t+1] = 1 + end + --print("glue",#t) + line, r = calc_river(line,t, lines) + if r > 1 then + local w = node.new("whatsit","pdf_literal") + local color = 1 / r + w.data = string.format("q 1 %f 1 rg 0 0 m 0 5 l 5 5 l 5 0 l f Q", color) + -- print("color",w.data) + node.insert_before(n.head,x,w) + end + return r + end + for x in node.traverse(n.head) do + if x.id == glue_id and x.subtype == 0 then + --print("glue width", get_width(x,x.next)) + add_word(last_glue, x, first_glyph,last_glyph) + local river_value = add_glue(x) + -- print("riverness", river_value) + first = true + last_glue = x.next -- calculate width of next word from here + elseif x.id == glyph_id then + if first then + first_glyph = x + end + first = false + last_glyph = x + end + end + add_word(last_glue, x, first_glyph, last_glyph) + --table.insert(lines, calc_river(t,lines)) + --for k,v in pairs(line) do print(k,v) end + table.insert(lines,line) + -- print(table.concat(lines[#lines],",")) + -- local width, h, d = node.dimensions(set, sign, order, n.head, node.tail(n.head)) + -- print(width,table.concat(t)) + end + return 0 +end + +-- End of river detection + + +function linebreaker.last_line_width(head) + -- measure length of the last line in a paragraph + local w, w1 + local last = node.tail(head) + local n = node.copy(last) + -- last node is not node list, return negative number + if not n.head then return -1 end + n.head = node.remove(n.head, node.tail(n.head)) + for x in node.traverse(n.head) do + if x.id == glue_id then + if x.subtype == 15 then + n.head = node.remove(n.head, x) + end + end + end + -- something went wrong, so discard this solution + if not n.head then return 0 end + w, _, _ = node.dimensions(n.glue_set, n.glue_sign, n.glue_order, n.head) + w1, _, _ = node.dimensions(n.glue_set, n.glue_sign, n.glue_order, n) + return w +end + + +-- try to linebreak current paragraph with increasing tolerance and +-- emergencystretch +function linebreaker.best_solution(par, parameters) + -- save current node list, because call to the linebreaker modifies it + -- and we wouldn't be able to run it multiple times + local head = node.copy_list(par) + -- this shouldn't happen + if #parameters > linebreaker.max_cycles then + -- we couldn't find a solution without badness + -- break paragraph with the least bad parameters + return linebreaker.breaker(head,find_best(parameters)) + end + local params = parameters[#parameters] -- newest parameters are last in the + -- table that will be used in recursive invocations of this function + -- it holds updated parameters + local newparams = {} + -- this value is set by hpack_quality callback that is executed by + -- tex.linebreak when overflow or underflow happens + linebreaker.badness = 0 + -- break paragraph + local newhead, info = linebreaker.breaker(head, params) + -- calc badness -- we don't use this anymore, badness of the currently + -- processed node list is set by hpack_filter + local badness = linebreaker.badness or 0 + -- don't allow lines shorter than the paragraph indent + local last_line_width = linebreaker.last_line_width(newhead) + linebreaker.debug_print("last line width", last_line_width, "parindent:", tex.parindent * linebreaker.width_factor) + if last_line_width > 0 and last_line_width < tex.parindent * linebreaker.width_factor then + linebreaker.debug_print "too short last line" + badness = 10000 + end + + params.badness = badness + if badness > 0 then + -- calc new value of tolerance + local tolerance = calc_tolerance(params.tolerance) -- or 10000 + -- save tolerance to newparams so this value will be used in next run + newparams.tolerance = tolerance + newparams.emergencystretch = (params.emergencystretch or 0) + linebreaker.max_emergencystretch / linebreaker.max_cycles + table.insert(parameters, newparams) + -- run linebreaker again + return linebreaker.best_solution(par, parameters) + end + -- river detection doesn't work, so we don't execute ths code anymore + -- detect rivers only for paragraphs without overflow boxes + -- local rivers = linebreaker.detect_rivers(newhead) + -- print("rivers", rivers) + -- print "normal return" + --]] + return newhead, info +end + +-- this is just reporting function which print lines with glue widths. +-- this may be useful in river detection +local function glue_width(head) + for n in node.traverse_id(hlist_id, head) do + local t = {} + local set = n.glue_set + local sign = n.glue_sign + local order = n.glue_order + for x in node.traverse(n.head) do + if x.id == glue_id then + local g = x.spec + local size = glue_calc(x, sign, set) + t[#t+1] = ":"..size.."." + elseif x.id == glyph_id then + t[#t+1] = getchar(x) + end + end + local width, h, d = node.dimensions(set, sign, order, n.head, node.tail(n.head)) + end +end + +local function fix_nest(info) + tex.nest[tex.nest.ptr].prevdepth=info.prevdepth + tex.nest[tex.nest.ptr].prevgraf=info.prevgraf +end + +-- test whether the current overfull box message occurs inside our linebreaker function +local is_inside_linebreaker = false +function linebreaker.linebreak(head,is_display) + -- we can disable linebreaker processing + if linebreaker.active == false then + local newhead, info = linebreaker.breaker(head) + fix_nest(info) + return newhead + end + local parameters = linebreaker.parameters() + is_inside_linebreaker = true + local newhead, info = linebreaker.best_solution(head, {parameters}) + is_inside_linebreaker = false + fix_nest(info) + return newhead +end + +function linebreaker.hpack_quality(incl, detail, head, first, last) + if not is_inside_linebreaker then + local detail_msg = incl=="overfull" and "overflow" or "badness" + linebreaker.debug_print( incl .. " box at lines: " .. first .." -- " .. last ..". " .. detail_msg .. ": " .. detail .."\n text:" .. get_text(head) ) + end + linebreaker.badness = (linebreaker.badness or 0) + detail +end + +-- It seems necessary to call the post_linebreak filter in order to support floats +-- Even if it does nothing but to return the node list. I don't understand why... +function linebreaker.post_linebreak(head) + return true +end + +linebreaker.get_text = get_text + +return linebreaker + -- cgit v1.2.3