| 1 | # /=====================================================================\ # | ||
| 2 | # | LaTeXML::Post::MathML::Linebreaker | # | ||
| 3 | # | MathML generator for LaTeXML | # | ||
| 4 | # |=====================================================================| # | ||
| 5 | # | Part of LaTeXML: | # | ||
| 6 | # | Public domain software, produced as part of work done by the | # | ||
| 7 | # | United States Government & not subject to copyright in the US. | # | ||
| 8 | # |---------------------------------------------------------------------| # | ||
| 9 | # | Bruce Miller <bruce.miller@nist.gov> #_# | # | ||
| 10 | # | http://dlmf.nist.gov/LaTeXML/ (o o) | # | ||
| 11 | # \=========================================================ooo==U==ooo=/ # | ||
| 12 | package LaTeXML::Post::MathML::Linebreaker; | ||
| 13 | use strict; | ||
| 14 | use warnings; | ||
| 15 | use LaTeXML::Common::XML; | ||
| 16 | use LaTeXML::Common::Error; | ||
| 17 | use List::Util qw(min max); | ||
| 18 | |||
| 19 | #====================================================================== | ||
| 20 | # General MathML Line-Breaking Strategy. | ||
| 21 | # | ||
| 22 | # (1) Preparations: if top-level has trailing punctuation, | ||
| 23 | # remove it to be added back, later. | ||
| 24 | # | ||
| 25 | # (2) Find all layouts that fit within a specified width. | ||
| 26 | # This is done top-down by finding possible breaks within the current | ||
| 27 | # node, along with (recursively) the possible layouts for children. | ||
| 28 | # The pattern of possible breaks and which children are allowed to break | ||
| 29 | # depends on the tag of the current node; eg. sub/superscripts don't break. | ||
| 30 | # [handlers for each tag are defined at end of file] | ||
| 31 | # | ||
| 32 | # Each combination of these breaks is then considered by | ||
| 33 | # computing the effective size & penalty. | ||
| 34 | # The penalty is generally determined by the number of breaks, | ||
| 35 | # but possibly weighted. | ||
| 36 | # | ||
| 37 | # These layouts are sorted in increasing width, and increasing penalty | ||
| 38 | # for a given width. Layouts which are too wide, or have higher penalty | ||
| 39 | # than the previous layout are pruned. | ||
| 40 | # | ||
| 41 | # (3) Apply the breaks specified by the best layout. | ||
| 42 | # The last layout in a list of layouts will be the best in the sense | ||
| 43 | # that it is the longest layout not longer than the target width, | ||
| 44 | # and has least penalty of its width. | ||
| 45 | #====================================================================== | ||
| 46 | # NOTE This takes the array form for the MathML, before it has been | ||
| 47 | # converted to a proper DOM tree. | ||
| 48 | |||
| 49 | ####################################################################### | ||
| 50 | # Parameters | ||
| 51 | ####################################################################### | ||
| 52 | my $NOBREAK = 99999999; # penalty=$NOBREAK means don't break at all. [CONSTANT] | ||
| 53 | my $POORBREAK_FACTOR = 20; # to make breaks less desirable.[CONSTANT] | ||
| 54 | my $BADBREAK_FACTOR = 100; # to make breaks much less desirable.[CONSTANT] | ||
| 55 | my $PENALTY_OK = 5; # [CONSTANT] | ||
| 56 | my $PENALTY_LIMIT = 1000; # worst penalty we'll tolerate; prune anything above.[CONSTANT] | ||
| 57 | my $CONVERSION_FACTOR = 2; # to make breaks at converted ops less desirable[CONSTANT] | ||
| 58 | |||
| 59 | DebuggableFeature('linebreaking', "MathML Linebreaking"); | ||
| 60 | # TODO: Integrate default operator dictionary, and recognize attributes | ||
| 61 | # TODO: all addops, relops, | ||
| 62 | # TODO: mult ops, but less desirable | ||
| 63 | sub UTF { | ||
| 64 | my ($code) = @_; | ||
| 65 | return pack('U', $code); } | ||
| 66 | |||
| 67 | my %BREAKBEFOREOPS = map { ($_ => 1) } # [CONSTANT] | ||
| 68 | # Various addops | ||
| 69 | "+", "-", UTF(0xB1), "\x{2212}", "\x{2213}"; | ||
| 70 | my %BREAKAFTEROPS = map { ($_ => 1) } # [CONSTANT] | ||
| 71 | ","; | ||
| 72 | my %RELATIONOPS = map { ($_ => 1) } # [CONSTANT] | ||
| 73 | # Various relops | ||
| 74 | "=", "<", ">", "\x{2264}", "\x{2265}", "\x{2260}", "\x{226A}", | ||
| 75 | "\x{2261}", "\x{223C}", "\x{2243}", "\x{224D}", "\x{2248}", "\x{2260}", "\x{221D}"; | ||
| 76 | my %CONVERTOPS = ( # [CONSTANT] | ||
| 77 | "\x{2062}" => UTF(0xD7), # Invisible (discretionary) times | ||
| 78 | ); | ||
| 79 | my %FENCEOPS = map { ($_ => 1) } # [CONSTANT] | ||
| 80 | "(", ")", "[", "]", "{", "}", "|", "||", "|||", | ||
| 81 | "\x{2018}", "\x{2019}", "\x{201C}", "\x{201D}", "\x{2016}", "\x{2016}", "\x{2308}", | ||
| 82 | "\x{2309}", "\x{230A}", "\x{230B}", "\x{2772}", "\x{2773}", "\x{27E6}", "\x{27E7}", | ||
| 83 | "\x{27E8}", "\x{27E9}", "\x{27EA}", "\x{27EB}", "\x{27EC}", "\x{27ED}", "\x{27EE}", | ||
| 84 | "\x{27EF}", "\x{2980}", "\x{2980}", "\x{2983}", "\x{2984}", "\x{2985}", "\x{2986}", | ||
| 85 | "\x{2987}", "\x{2988}", "\x{2989}", "\x{298A}", "\x{298B}", "\x{298C}", "\x{298D}", | ||
| 86 | "\x{298E}", "\x{298F}", "\x{2990}", "\x{2991}", "\x{2992}", "\x{2993}", "\x{2994}", | ||
| 87 | "\x{2995}", "\x{2996}", "\x{2997}", "\x{2998}", "\x{29FC}", "\x{29FD}"; | ||
| 88 | my %SEPARATOROPS = map { ($_ => 1) } # [CONSTANT] | ||
| 89 | ",", ";", ".", "\x{2063}"; | ||
| 90 | |||
| 91 | ####################################################################### | ||
| 92 | # Top-level interface | ||
| 93 | ####################################################################### | ||
| 94 | |||
| 95 | sub new { | ||
| 96 | my ($class) = @_; | ||
| 97 | my $self = bless {}, $class; | ||
| 98 | return $self; } | ||
| 99 | |||
| 100 | sub fitToWidth { | ||
| 101 | my ($self, $math, $mml, $width, $displaystyle) = @_; | ||
| 102 | # Check for end punctuation; Remove it, if found. | ||
| 103 | my @n; | ||
| 104 | local $LaTeXML::Post::MathML::Linebreaker::MATH = $math; | ||
| 105 | local $LaTeXML::Post::MathML::Linebreaker::PUNCT = undef; | ||
| 106 | local @LaTeXML::Post::MathML::Linebreaker::CLOSE = (); | ||
| 107 | local $LaTeXML::DISPLAYSTYLE = $displaystyle || 0; | ||
| 108 | local $LaTeXML::SCRIPTLEVEL = 0; | ||
| 109 | |||
| 110 | if ((nodeName($mml) eq 'm:mrow') && (scalar(@n = nodeChildren($mml)) == 2) && isSeparator($n[1])) { | ||
| 111 | $mml = $n[0]; | ||
| 112 | $LaTeXML::Post::MathML::Linebreaker::PUNCT = $n[1]; } | ||
| 113 | |||
| 114 | # Compute the possible layouts | ||
| 115 | Debug("Starting layout of " . showNode($mml)) if $LaTeXML::DEBUG{linebreaking}; | ||
| 116 | my $layouts = layout($mml, $width, 0, 1); | ||
| 117 | if ($LaTeXML::DEBUG{linebreaking}) { | ||
| 118 | Debug("Got " . scalar(@$layouts) . " layouts:"); | ||
| 119 | map { showLayout($_) } @$layouts; } | ||
| 120 | |||
| 121 | # Apply the best layout | ||
| 122 | my $best = $$layouts[-1]; | ||
| 123 | # Is there a case where $best is so bad we shouldn't even apply it? | ||
| 124 | applyLayout_rec($best); | ||
| 125 | # If nobody has yet eaten the punctuation, add it back on. | ||
| 126 | if ($LaTeXML::Post::MathML::Linebreaker::PUNCT) { | ||
| 127 | $mml = ['m:mrow', {}, $mml, $LaTeXML::Post::MathML::Linebreaker::PUNCT]; } | ||
| 128 | |||
| 129 | layout_warn("Got width $$best{width} > $width") if $$best{width} > $width + 1; | ||
| 130 | return $mml; } | ||
| 131 | |||
| 132 | sub bestFitToWidth { | ||
| 133 | my ($self, $math, $mml, $width, $displaystyle) = @_; | ||
| 134 | # Check for end punctuation; Remove it, if found. | ||
| 135 | my @n; | ||
| 136 | local $LaTeXML::Post::MathML::Linebreaker::MATH = $math; | ||
| 137 | local $LaTeXML::DISPLAYSTYLE = $displaystyle || 0; | ||
| 138 | local $LaTeXML::SCRIPTLEVEL = 0; | ||
| 139 | |||
| 140 | # Extract math without trailing punctuation (if any). | ||
| 141 | if ((nodeName($mml) eq 'm:mrow') && (scalar(@n = nodeChildren($mml)) == 2) && isSeparator($n[1])) { | ||
| 142 | $mml = $n[0]; } | ||
| 143 | |||
| 144 | # Compute the possible layouts | ||
| 145 | Debug("Starting layout of " . showNode($mml)) if $LaTeXML::DEBUG{linebreaking}; | ||
| 146 | my @layouts = @{ layout($mml, $width, 0, 1) }; | ||
| 147 | |||
| 148 | # Add a penalty for larger overall area. | ||
| 149 | my ($maxarea, $minarea) = (0, 999999999); | ||
| 150 | map { $$_{area} = $$_{width} * ($$_{depth} + $$_{height}) } @layouts; | ||
| 151 | map { $maxarea = max($maxarea, $$_{area}) } @layouts; | ||
| 152 | map { $minarea = min($minarea, $$_{area}) } @layouts; | ||
| 153 | map { $$_{penalty} *= (1 + ($$_{area} - $minarea) / ($maxarea - $minarea)) } @layouts | ||
| 154 | if $maxarea > $minarea; | ||
| 155 | |||
| 156 | if ($LaTeXML::DEBUG{linebreaking}) { | ||
| 157 | Debug("Got " . scalar(@layouts) . " layouts:"); | ||
| 158 | map { showLayout($_) } @layouts; } | ||
| 159 | |||
| 160 | # Depending on the pruning algorithm & parameters used, | ||
| 161 | # we may have layouts above $width, and some below $width may have really bad breaks. | ||
| 162 | |||
| 163 | # If the widest layout is less than target width, | ||
| 164 | # it should have lowest penalty --maybe even unbroken-- so use it. | ||
| 165 | my $best = $layouts[-1]; | ||
| 166 | return $best if $$best{width} < $width; | ||
| 167 | |||
| 168 | # If the lowest penalty layout that fits has a not-very-bad penalty, let's go with it. | ||
| 169 | my @fit = sort { $$a{penalty} <=> $$b{penalty} } grep { $$_{width} < $width } @layouts; | ||
| 170 | if (@fit && ($fit[0]->{penalty} < $PENALTY_OK)) { | ||
| 171 | return $fit[0]; } | ||
| 172 | |||
| 173 | # Otherwise, let's try to weight the over-width against the penalty. | ||
| 174 | # How to weight over-width against penalty? | ||
| 175 | # Since "Nice breaks" end up with a penalty of just "a few" | ||
| 176 | # and a handfull of ems is not too bad either. | ||
| 177 | # let's just try weighting them nominally equally.... let's try | ||
| 178 | my $weight = 2; | ||
| 179 | my @sorted = sort { ($weight * $$a{penalty} + $$a{width}) <=> ($weight * $$b{penalty} + $$b{width}) } | ||
| 180 | @layouts; | ||
| 181 | $best = $sorted[0]; | ||
| 182 | |||
| 183 | layout_warn("Got width $$best{width} > $width") if $$best{width} > $width + 1; | ||
| 184 | # Return the best layout | ||
| 185 | return $best; } | ||
| 186 | |||
| 187 | sub applyLayout { | ||
| 188 | my ($self, $mml, $layout) = @_; | ||
| 189 | my @n; | ||
| 190 | # Extract trailing punctuation which might be placed during layout | ||
| 191 | local $LaTeXML::Post::MathML::Linebreaker::PUNCT = undef; | ||
| 192 | if ((nodeName($mml) eq 'm:mrow') && (scalar(@n = nodeChildren($mml)) == 2) && isSeparator($n[1])) { | ||
| 193 | $mml = $n[0]; | ||
| 194 | $LaTeXML::Post::MathML::Linebreaker::PUNCT = $n[1]; } | ||
| 195 | |||
| 196 | # Is there a case where $best is so bad we shouldn't even apply it? | ||
| 197 | applyLayout_rec($layout); | ||
| 198 | # If nobody has yet eaten the punctuation, add it back on. | ||
| 199 | if ($LaTeXML::Post::MathML::Linebreaker::PUNCT) { | ||
| 200 | $mml = ['m:mrow', {}, $mml, $LaTeXML::Post::MathML::Linebreaker::PUNCT]; } | ||
| 201 | |||
| 202 | return $mml; } | ||
| 203 | |||
| 204 | # (only called during layout; not applying layout) | ||
| 205 | sub layout_warn { | ||
| 206 | my ($message) = @_; | ||
| 207 | my $p = $LaTeXML::Post::MathML::Linebreaker::MATH; | ||
| 208 | while ($p && !$p->hasAttribute('xml:id')) { | ||
| 209 | $p = $p->parentNode; } | ||
| 210 | my $id = $p && $p->getAttribute('xml:id') || '?'; | ||
| 211 | my $nm = $p && $p->getAttribute('refnum') || ''; | ||
| 212 | Info('unexpected', 'toowide', "id=$id", $message); | ||
| 213 | return; } | ||
| 214 | |||
| 215 | ####################################################################### | ||
| 216 | # Apply the breaks described in a layout to the MathML. | ||
| 217 | ####################################################################### | ||
| 218 | # Modify the mathml to incorporate a set of breaks. | ||
| 219 | |||
| 220 | # This strategy uses mtable. | ||
| 221 | # NOTE: There's an alignment issue. | ||
| 222 | # In principle, a row could be broken that resides within another row. | ||
| 223 | # In such a case, you'd want the table to align the 1st row's baseline to the material | ||
| 224 | # on the left, but the material following should align to the last row's baseline!!! | ||
| 225 | # MathML spec doesn't give any way of saying that! | ||
| 226 | # So, currently, we've got code in asRow that forbids a break within anything | ||
| 227 | # but the _LAST_ item within a line. | ||
| 228 | sub applyLayout_rec { | ||
| 229 | my ($layout) = @_; | ||
| 230 | return unless $$layout{hasbreak}; | ||
| 231 | my $node = $$layout{node}; | ||
| 232 | my @children = nodeChildren($node); | ||
| 233 | |||
| 234 | # Check for opening/closing delimiters that may need special treatment. | ||
| 235 | my $close; | ||
| 236 | if ((nodeName($node) eq 'm:mrow') && $$layout{hasbreak}) { | ||
| 237 | my $size = ($$layout{rowheight} + $$layout{rowdepth}) . "em"; | ||
| 238 | if (isFence($children[0])) { | ||
| 239 | # if(($children[0][1]{stretchy}||'true') eq 'true'){ # If delimiter WAS stretchy. | ||
| 240 | if (!($children[0][1]{size} || $children[0][1]{maxsize} || $children[0][1]{minsize})) { # If delimiter WAS stretchy. | ||
| 241 | $children[0][1]{stretchy} = undef; | ||
| 242 | $children[0][1]{minsize} = $size; | ||
| 243 | $children[0][1]{maxsize} = $size; } } | ||
| 244 | if (isFence($children[-1])) { | ||
| 245 | if (!$$layout{breakset}) { # If we're breaking HERE, not sure what we should do special? | ||
| 246 | $close = $children[-1]; } | ||
| 247 | ## if(($children[-1][1]{stretchy}||'true') eq 'true'){ # If delimiter WAS stretchy. | ||
| 248 | if (!($children[-1][1]{size} || $children[-1][1]{maxsize} || $children[-1][1]{minsize})) { # If delimiter WAS stretchy. | ||
| 249 | $children[-1][1]{stretchy} = undef; | ||
| 250 | $children[-1][1]{minsize} = $size; | ||
| 251 | $children[-1][1]{maxsize} = $size; } } | ||
| 252 | } | ||
| 253 | # Do children first, so if there is punctuation & last child breaks, it can take up the punct. | ||
| 254 | if ($$layout{children}) { | ||
| 255 | my @children_layout = @{ $$layout{children} }; | ||
| 256 | my $lastchild = pop(@children_layout); | ||
| 257 | { local $LaTeXML::Post::MathML::Linebreaker::PUNCT = undef; # Hide from all but last child | ||
| 258 | local @LaTeXML::Post::MathML::Linebreaker::CLOSE = (); # Hide from all but last child | ||
| 259 | map { applyLayout_rec($_) } @children_layout; } | ||
| 260 | # Now, do last child; Maybe it will absorb the closing & punctuation! | ||
| 261 | if ($close) { | ||
| 262 | unshift(@LaTeXML::Post::MathML::Linebreaker::CLOSE, $close); | ||
| 263 | applyLayout_rec($lastchild); | ||
| 264 | # If the close was taken up by a child, remove it here. | ||
| 265 | if (!grep { $_ eq $close } @LaTeXML::Post::MathML::Linebreaker::CLOSE) { | ||
| 266 | pop(@$node); } | ||
| 267 | else { | ||
| 268 | shift(@LaTeXML::Post::MathML::Linebreaker::CLOSE); } } | ||
| 269 | else { | ||
| 270 | applyLayout_rec($lastchild); } } | ||
| 271 | if (my $breakset = $$layout{breakset}) { | ||
| 272 | applyLayout_break($breakset, $layout, $node, @children); | ||
| 273 | } | ||
| 274 | return; } | ||
| 275 | |||
| 276 | sub applyLayout_break { | ||
| 277 | my ($breakset, $layout, $node, @children) = @_; | ||
| 278 | # If this is a fenced row, we've got to manually fixup the fence size! | ||
| 279 | my $sawfences; | ||
| 280 | if (nodeName($node) eq 'm:mrow') { | ||
| 281 | # Really should only set size here if it had been stretchy! | ||
| 282 | my $size = ($$layout{rowheight} + $$layout{rowdepth}) . "em"; | ||
| 283 | if (isFence($children[0])) { | ||
| 284 | ## $children[0][1]{mathsize}=$size; | ||
| 285 | $sawfences = 1; | ||
| 286 | ### $children[0][1]{symmetric} = 'false'; | ||
| 287 | $children[0][1]{minsize} = $size; | ||
| 288 | $children[0][1]{maxsize} = $size; | ||
| 289 | } | ||
| 290 | if (isFence($children[-1])) { | ||
| 291 | ## $children[-1][1]{mathsize}=$$layout{rowheight}."em"; | ||
| 292 | $sawfences = 1; | ||
| 293 | # $children[-1][1]{symmetric} = 'false'; | ||
| 294 | $children[-1][1]{minsize} = $size; | ||
| 295 | $children[-1][1]{maxsize} = $size; | ||
| 296 | } | ||
| 297 | } | ||
| 298 | my @rows = split_row($breakset, @children); | ||
| 299 | # Replace any "converted" leading operators (ie. invisible times => \times) | ||
| 300 | foreach my $row (@rows[1 .. $#rows]) { | ||
| 301 | my $op = $$row[0]; | ||
| 302 | my $newop; | ||
| 303 | if ((nodeName($op) eq 'm:mo') && ($newop = $CONVERTOPS{ textContent($op) })) { | ||
| 304 | splice(@$op, 2, scalar(@$op) - 2, $newop); } } | ||
| 305 | if (@LaTeXML::Post::MathML::Linebreaker::CLOSE) { | ||
| 306 | $rows[-1] = [@{ $rows[-1] }, @LaTeXML::Post::MathML::Linebreaker::CLOSE]; | ||
| 307 | @LaTeXML::Post::MathML::Linebreaker::CLOSE = (); } | ||
| 308 | |||
| 309 | if ($LaTeXML::Post::MathML::Linebreaker::PUNCT) { | ||
| 310 | $rows[-1] = [@{ $rows[-1] }, $LaTeXML::Post::MathML::Linebreaker::PUNCT]; | ||
| 311 | $LaTeXML::Post::MathML::Linebreaker::PUNCT = undef; } | ||
| 312 | |||
| 313 | my @firstrow = @{ shift(@rows) }; | ||
| 314 | # the mtable should have displaystyle IFF the original object was in displaystyle! | ||
| 315 | # (but we haven't recorded that anywhere!) | ||
| 316 | splice(@$node, 2, scalar(@children), | ||
| 317 | ($$layout{lhs_pos} | ||
| 318 | ? ["m:mtable", { align => 'baseline 1', columnalign => 'left', columnspacing => '0.1em', | ||
| 319 | ($$layout{displaystyle} ? (displaystyle => 'true') : ()) }, | ||
| 320 | ["m:mtr", {}, | ||
| 321 | ["m:mtd", { class => 'ltx_align_left' }, @firstrow[0 .. $$layout{lhs_pos} - 1]], | ||
| 322 | ["m:mtd", { class => 'ltx_align_left' }, @firstrow[$$layout{lhs_pos} .. $#firstrow]]], | ||
| 323 | map { ["m:mtr", {}, | ||
| 324 | ["m:mtd", { class => 'ltx_align_left' }], | ||
| 325 | ["m:mtd", { class => 'ltx_align_left' }, @$_]] } @rows] | ||
| 326 | : ["m:mtable", { align => 'baseline 1', columnalign => 'left', | ||
| 327 | ($$layout{displaystyle} ? (displaystyle => 'true') : ()) }, | ||
| 328 | ["m:mtr", {}, ["m:mtd", { class => 'ltx_align_left' }, @firstrow]], | ||
| 329 | map { ["m:mtr", {}, | ||
| 330 | ["m:mtd", { class => 'ltx_align_left' }, ["m:mspace", { width => $$layout{indentation} . "em" }], @$_]] } | ||
| 331 | @rows])); | ||
| 332 | return; } | ||
| 333 | |||
| 334 | # This would use <mspace> with linebreak attribute to break a row. | ||
| 335 | # Unfortunately, Mozillae ignore this attribute... | ||
| 336 | sub XXXXapplyLayout_rec { | ||
| 337 | my ($layout) = @_; | ||
| 338 | map { applyLayout_rec($_) } @{ $$layout{children} } if $$layout{children}; | ||
| 339 | if (my $breakset = $$layout{breakset}) { | ||
| 340 | my $node = $$layout{node}; | ||
| 341 | my @children = nodeChildren($node); | ||
| 342 | my @lines = | ||
| 343 | my @newchildren = (); | ||
| 344 | foreach my $line (split_row($breakset, @children)) { | ||
| 345 | push(@newchildren, ["m:mspace", { linebreak => "indentingnewline" }]) if @newchildren; | ||
| 346 | push(@newchildren, @$line); } | ||
| 347 | splice(@$node, 2, scalar(@children), @newchildren); | ||
| 348 | } | ||
| 349 | return; } | ||
| 350 | |||
| 351 | ####################################################################### | ||
| 352 | # Utilities & Debugging aids | ||
| 353 | ####################################################################### | ||
| 354 | |||
| 355 | sub nodeName { | ||
| 356 | my ($node) = @_; | ||
| 357 | my ($tag, $attr, @children) = @$node; | ||
| 358 | return $tag; } | ||
| 359 | |||
| 360 | sub getAttribute { | ||
| 361 | my ($node, $key) = @_; | ||
| 362 | my ($tag, $attr, @children) = @$node; | ||
| 363 | return $$attr{$key}; } | ||
| 364 | |||
| 365 | sub nodeChildren { | ||
| 366 | my ($node) = @_; | ||
| 367 | my ($tag, $attr, @children) = @$node; | ||
| 368 | return @children; } | ||
| 369 | |||
| 370 | sub textContent { | ||
| 371 | my ($node) = @_; | ||
| 372 | my $ref = ref $node; | ||
| 373 | if (!$ref) { | ||
| 374 | return $node; } | ||
| 375 | elsif ($ref eq 'ARRAY') { | ||
| 376 | my ($tag, $attr, @children) = @$node; | ||
| 377 | if ($tag eq 'ltx:XMath') { | ||
| 378 | return ''; } | ||
| 379 | else { | ||
| 380 | return join('', map { textContent($_) } @children); } } | ||
| 381 | elsif ($ref =~ /^XML::LibXML/) { | ||
| 382 | my $type = $node->nodeType; | ||
| 383 | if ($type == XML_ELEMENT_NODE) { | ||
| 384 | my $tag = $node->localname; | ||
| 385 | if ($tag eq 'XMath') { | ||
| 386 | return ''; } | ||
| 387 | else { | ||
| 388 | return join('', map { textContent($_) } $node->childNodes); } } | ||
| 389 | elsif ($type == XML_TEXT_NODE) { | ||
| 390 | return $node->textContent; } | ||
| 391 | else { | ||
| 392 | return ''; } } | ||
| 393 | else { | ||
| 394 | return ''; } } | ||
| 395 | |||
| 396 | sub isFence { | ||
| 397 | my ($node) = @_; | ||
| 398 | my ($tag, $attr, @children) = @$node; | ||
| 399 | my $t = $$attr{fence} || ''; | ||
| 400 | return ($tag eq 'm:mo') | ||
| 401 | && (($t eq 'true') || (($t ne 'false') && $FENCEOPS{ join('', @children) })); } | ||
| 402 | |||
| 403 | sub isSeparator { | ||
| 404 | my ($node) = @_; | ||
| 405 | my ($tag, $attr, @children) = @$node; | ||
| 406 | my $t = $$attr{separator} || ''; | ||
| 407 | return ($tag eq 'm:mo') | ||
| 408 | && (($t eq 'true') || (($t ne 'false') && $SEPARATOROPS{ join('', @children) })); } | ||
| 409 | |||
| 410 | sub describeLayouts { | ||
| 411 | my ($self, $layouts) = @_; | ||
| 412 | my @layouts = @$layouts; | ||
| 413 | my $min = $layouts[0]; | ||
| 414 | my $max = $layouts[-1]; | ||
| 415 | Debug("Layout " . scalar(@layouts) . " layout options\n" | ||
| 416 | . " best = $$max{width} x ($$max{height} + $$max{depth}) penalty = $$max{penalty}\n" | ||
| 417 | . " narrowest = $$min{width} x ($$min{height} + $$min{depth}) penalty = $$min{penalty}"); | ||
| 418 | showLayout($max); | ||
| 419 | return; } | ||
| 420 | |||
| 421 | sub showLayout { | ||
| 422 | my ($layout, $indent, $pos) = @_; | ||
| 423 | $indent = 0 unless $indent; | ||
| 424 | my $pre = (' ') x (2 * $indent) . (defined $pos ? "[$pos] " : ""); | ||
| 425 | Debug($pre . layoutDescriptor($layout)); | ||
| 426 | if ($$layout{children}) { | ||
| 427 | my $p = 0; | ||
| 428 | foreach my $child (@{ $$layout{children} }) { | ||
| 429 | showLayout($child, $indent + 1, $p) if $$child{penalty}; | ||
| 430 | $p++; } } | ||
| 431 | return; } | ||
| 432 | |||
| 433 | sub layoutDescriptor { | ||
| 434 | my ($layout) = @_; | ||
| 435 | return $$layout{type} . " " | ||
| 436 | . "(" . $$layout{width} . " x " . $$layout{height} . " + " . $$layout{depth} . ")" | ||
| 437 | . "@" . $$layout{penalty} | ||
| 438 | . ($$layout{breakset} | ||
| 439 | ? ", b@" . join(",", map { "[" . join(',', @$_) . "]" } @{ $$layout{breakset} }) | ||
| 440 | : ""); } | ||
| 441 | |||
| 442 | ####################################################################### | ||
| 443 | # Permutation things | ||
| 444 | ####################################################################### | ||
| 445 | # multiplex(@layouts) | ||
| 446 | # Given a list of layouts arrays, (each representing the possible layouts of | ||
| 447 | # each of the children of a node), multiplex them to return a list of | ||
| 448 | # arrays containing one layout choice for each child. | ||
| 449 | # That is to say, form all combinations choosing one $layout | ||
| 450 | # from each of the $layouts lists in @layouts. | ||
| 451 | sub multiplex { | ||
| 452 | my ($layouts, @siblings_layouts) = @_; | ||
| 453 | if (@siblings_layouts) { | ||
| 454 | my @multiplexed_siblings_layouts = multiplex(@siblings_layouts); | ||
| 455 | my @multiplexed = (); | ||
| 456 | foreach my $layout (@$layouts) { | ||
| 457 | foreach my $multiplexed_sibling_layout (@multiplexed_siblings_layouts) { | ||
| 458 | push(@multiplexed, [$layout, @$multiplexed_sibling_layout]); } } | ||
| 459 | return @multiplexed; } | ||
| 460 | else { | ||
| 461 | return map { [$_] } @$layouts; } } | ||
| 462 | |||
| 463 | # Given a list of break's (in order), form all choices of breaks. | ||
| 464 | # WHOA: this is incredibly inefficient to BUILD the list of all these choices | ||
| 465 | # [for n @breaks, there are 2^n choices!] | ||
| 466 | sub choices { | ||
| 467 | my (@breaks) = @_; | ||
| 468 | if (@breaks) { | ||
| 469 | my $break = shift(@breaks); | ||
| 470 | return map { ($_, [$break, @$_]) } choices(@breaks); } | ||
| 471 | else { | ||
| 472 | return ([]); } } | ||
| 473 | |||
| 474 | ####################################################################### | ||
| 475 | # Layout determination code | ||
| 476 | ####################################################################### | ||
| 477 | # The current code computes pretty much every possible layout, | ||
| 478 | # which we'd select from later. | ||
| 479 | # If it turns out this is too expensive, it would be good | ||
| 480 | # to work out some kind of lazy expansion that could prune | ||
| 481 | # ridiculous layouts before computing everything, or even layouts | ||
| 482 | # that are worse than the current best for a given size. | ||
| 483 | # Of course, at this point, we don't know anything about the size | ||
| 484 | # of something till we do the full expansion, so... | ||
| 485 | #====================================================================== | ||
| 486 | # "layouts" == [ layout, ...] | ||
| 487 | # represents a list of layout descriptors representing possible | ||
| 488 | # arrangements & breakpoints for a given node. | ||
| 489 | # Generally sorted by increasing width, and increasing penalty | ||
| 490 | # "layout" aka layout descriptor | ||
| 491 | # is a hash describing a possible layout arrangment. | ||
| 492 | # The fields are: | ||
| 493 | # node == the node that this layout applies to. | ||
| 494 | # type == the tag name of the node, for convenience & debugging. | ||
| 495 | # width == width of this layout (in extremely rough ems) | ||
| 496 | # height == height of this layout box above baseline | ||
| 497 | # depth == depth below baseline | ||
| 498 | # penalty == undesirability of this layout | ||
| 499 | # children == [ layout, ...] | ||
| 500 | # being the layout descriptor for each child | ||
| 501 | # breakset == [ break,...] | ||
| 502 | # being a list of points to break at | ||
| 503 | # hasbreak = 1 if this node, or any children have a line-break. | ||
| 504 | # break = [pos,content,demerit] where pos is the (0 based) index of a breakpoint | ||
| 505 | # ie. make child[pos] start the next line. | ||
| 506 | #====================================================================== | ||
| 507 | sub layout { | ||
| 508 | my ($node, $target, $level, $demerits) = @_; | ||
| 509 | |||
| 510 | # Get the Handler for this tag | ||
| 511 | my $name = nodeName($node); | ||
| 512 | $name =~ s/\w://; | ||
| 513 | my $handler = "layout_$name"; | ||
| 514 | $handler = eval { | ||
| 515 | local $LaTeXML::IGNORE_ERRORS = 1; | ||
| 516 | \&$handler; }; | ||
| 517 | if (!$handler) { | ||
| 518 | Fatal("unexpected", $name, $node, | ||
| 519 | "Can't find layout handler for $name"); } | ||
| 520 | Debug((' ' x $level) . "layout $name: " . $node . "...") if $LaTeXML::DEBUG{linebreaking}; | ||
| 521 | # Get the handler to compute the layouts | ||
| 522 | my $layouts = &$handler($node, $target, $level, $demerits || 1); | ||
| 523 | my $nlayouts = scalar(@$layouts); | ||
| 524 | |||
| 525 | # Sort & prune the layouts | ||
| 526 | my @layouts = prunesort($target, @$layouts); | ||
| 527 | my $pruned = scalar(@layouts); | ||
| 528 | Debug((' ' x $level) . "$name: $nlayouts layouts" | ||
| 529 | . ($pruned < $nlayouts ? " pruned to $pruned" : "") | ||
| 530 | . " " . layoutDescriptor($$layouts[0]) | ||
| 531 | . ($nlayouts > 1 ? "..." . layoutDescriptor($$layouts[$nlayouts - 1]) : "") | ||
| 532 | ) if $LaTeXML::DEBUG{linebreaking}; | ||
| 533 | return [@layouts]; } | ||
| 534 | |||
| 535 | # Note that this sorts first by width, then penalty. | ||
| 536 | # It prunes layouts wider than the target width (or now, twice it?) | ||
| 537 | # and those with higher penalty than preceding layout (w/narrower or equal width) | ||
| 538 | # BUT, it AT LEAST returns the shortest layout, no matter how bad the penalty! | ||
| 539 | # meaning that a much better layout, particularly if it exceeds the target, will be pruned! | ||
| 540 | sub prunesort { | ||
| 541 | my ($target, @layouts) = @_; | ||
| 542 | @layouts = sort { ($$a{width} <=> $$b{width}) || ($$a{penalty} <=> $$b{penalty}) } @layouts; | ||
| 543 | my @goodlayouts = (shift(@layouts)); # always include at least the shortest/best | ||
| 544 | my $pp = $goodlayouts[0]->{penalty}; | ||
| 545 | my $p; | ||
| 546 | |||
| 547 | # Cut out any layouts whose penalty is too bad. | ||
| 548 | # (Hopefully the one we've already pulled off isn't that bad!?!?!) | ||
| 549 | @layouts = grep { $$_{penalty} < $PENALTY_LIMIT } @layouts; | ||
| 550 | my $cutoff = 2 * $target + 5; # ? | ||
| 551 | foreach my $layout (@layouts) { | ||
| 552 | if (($$layout{width} < $cutoff) # If not too wide | ||
| 553 | && ($pp > ($p = $$layout{penalty}))) { # not worse than prev | ||
| 554 | push(@goodlayouts, $layout); $pp = $p; } } | ||
| 555 | return @goodlayouts; } | ||
| 556 | |||
| 557 | ####################################################################### | ||
| 558 | # Row line breaker. | ||
| 559 | # This is the real workhorse. | ||
| 560 | ####################################################################### | ||
| 561 | # Here, of course, is where the Interesting stuff will happen, | ||
| 562 | # as rows are essentially the only place where linebreaking occurs. | ||
| 563 | |||
| 564 | sub showNode { | ||
| 565 | my ($node) = @_; | ||
| 566 | if (ref $node) { | ||
| 567 | my ($e, $a, @c) = @$node; | ||
| 568 | return join(' ', "<$e", map { "$_=$$a{$_}" } keys %$a) . ">" | ||
| 569 | . join('', map { showNode($_) } @c) . "</$e>"; } | ||
| 570 | else { | ||
| 571 | return "$node"; } } | ||
| 572 | |||
| 573 | sub asRow { | ||
| 574 | my ($node, $target, $level, $demerits) = @_; | ||
| 575 | my $type = nodeName($node); | ||
| 576 | my @children = nodeChildren($node); | ||
| 577 | if (my (@invalid) = grep { ref $_ ne 'ARRAY' } @children) { | ||
| 578 | Fatal('unexpected', $invalid[0], $node, | ||
| 579 | "Math row has non-element: " . nodeName($node)); } | ||
| 580 | |||
| 581 | # Since we can't vertically align independently on both sides of an mtable, | ||
| 582 | # we're forbidding breaks in children that won't appear at the END of their line. | ||
| 583 | # A trailing close delimiter (handled specially, anyway) would thus inhibit | ||
| 584 | # a break in the preceding child, so we pretend it isn't there at all. | ||
| 585 | my $hasfences = 0; | ||
| 586 | if (@children && isFence($children[0])) { | ||
| 587 | $hasfences = 1; } | ||
| 588 | if (@children && isFence($children[-1])) { | ||
| 589 | $hasfences = 1; | ||
| 590 | pop(@children); } | ||
| 591 | |||
| 592 | my $n = scalar(@children); | ||
| 593 | if (!$n) { | ||
| 594 | return [{ node => $node, type => $type, | ||
| 595 | penalty => 0, width => 0, height => 0, depth => 0 }]; } | ||
| 596 | |||
| 597 | # Multiple children, possibly with breaks | ||
| 598 | # Get the set of layouts for each child | ||
| 599 | my @child_layouts = map { layout($_, $target, $level + 1, $demerits + 1) } | ||
| 600 | @children; | ||
| 601 | |||
| 602 | # Now, we need all possible break points within the row itself. | ||
| 603 | my @breaks = (); | ||
| 604 | my $lhs_pos; | ||
| 605 | my $normal_indentation = 2; | ||
| 606 | my $next_indentation = 0; | ||
| 607 | if ($demerits < $NOBREAK) { | ||
| 608 | my $pass_indent = 2 * $normal_indentation; # minimum width to pass next indentation | ||
| 609 | my $running = $child_layouts[0]->[-1]{width}; | ||
| 610 | for (my $i = 1 ; $i < $n - 1 ; $i++) { | ||
| 611 | my $child = $children[$i]; | ||
| 612 | my $content = (nodeName($child) eq 'm:mo') && textContent($child); | ||
| 613 | if (!$content) { } | ||
| 614 | elsif ($RELATIONOPS{$content}) { | ||
| 615 | push(@breaks, [$i, $content, $demerits]) if $running > $pass_indent; | ||
| 616 | if (!defined $lhs_pos) { | ||
| 617 | if ($running < $target / 4) { | ||
| 618 | $lhs_pos = $i; $next_indentation = $running; } | ||
| 619 | else { | ||
| 620 | $lhs_pos = 0; $next_indentation = $normal_indentation; } } } | ||
| 621 | elsif ($BREAKBEFOREOPS{$content}) { | ||
| 622 | $lhs_pos = 0; | ||
| 623 | $next_indentation = $normal_indentation; | ||
| 624 | push(@breaks, [$i, $content, $demerits]) if $running > $pass_indent; } | ||
| 625 | elsif ($BREAKAFTEROPS{$content}) { | ||
| 626 | $lhs_pos = 0; | ||
| 627 | $next_indentation = 0; | ||
| 628 | push(@breaks, [$i + 1, $content, $demerits]) if $running > $pass_indent; } | ||
| 629 | elsif ($CONVERTOPS{$content}) { | ||
| 630 | $lhs_pos = 0; | ||
| 631 | $next_indentation = $normal_indentation; | ||
| 632 | push(@breaks, [$i, $content, $demerits + $CONVERSION_FACTOR]) if $running > $pass_indent; } | ||
| 633 | $running += $child_layouts[$i]->[-1]{width}; | ||
| 634 | } } | ||
| 635 | my $indentation = $next_indentation; | ||
| 636 | # | ||
| 637 | # The Classic linebreaking algorithm simply accumulates rows of material | ||
| 638 | # until the line is too long and then starts a new one; essentially O(n). | ||
| 639 | # But that makes it harder to get alignments within groups, and doesn't | ||
| 640 | # provide alternative layouts of this level to upper levels which would | ||
| 641 | # enable the upper levels to make nicer choices. | ||
| 642 | # | ||
| 643 | # Here we'd like to try "all" alternatives, but with N potential breakpoints, | ||
| 644 | # there are 2^N possible sets of breaks! This does NOT scale well!!! | ||
| 645 | # So, we'll examine the breaksets in order of the number of breaks (nobreaks, 1 break, ..) | ||
| 646 | # and quit as soon as we get reasonable layouts; Pruning is _essential_!!! | ||
| 647 | my $nbreaks = scalar(@breaks); | ||
| 648 | my $nbreaksets = 2**$nbreaks; | ||
| 649 | Debug((" " x $level) . $type . " " | ||
| 650 | . join("x", map { scalar(@$_) } @child_layouts) . " layouts" | ||
| 651 | . (@breaks | ||
| 652 | ? ", breaks@" . join(",", map { "[" . join(',', @$_) . "]" } @breaks) | ||
| 653 | . "(" . $nbreaksets . " sets;" | ||
| 654 | . product((map { scalar(@$_) } @child_layouts), $nbreaksets) . " combinations" | ||
| 655 | . ")" | ||
| 656 | : "")) | ||
| 657 | if $LaTeXML::DEBUG{linebreaking}; | ||
| 658 | |||
| 659 | my @layouts = (); | ||
| 660 | # For each set of breaks within this row | ||
| 661 | # And for each layout of children | ||
| 662 | # Form composite layouts, computing the size, penalty, and pruning. | ||
| 663 | # NOTE: Would we like to prefer more evenly balanced splits? | ||
| 664 | my $pruned = 0; | ||
| 665 | my @children_layouts = multiplex(@child_layouts); | ||
| 666 | my $breakpositions = []; | ||
| 667 | BREAKSET: while (1) { | ||
| 668 | my $breakset = [map { $breaks[$_] } @$breakpositions]; | ||
| 669 | my $breakpenalty = sum(map { $$_[2] } @$breakset); | ||
| 670 | # PRUNE if we've gotten a reasonable layout or are getting too many breaks | ||
| 671 | if (scalar(@$breakpositions) > 4) { | ||
| 672 | foreach my $layout (@layouts) { | ||
| 673 | if (($$layout{width} < $target) && ($breakpenalty > $$layout{penalty})) { # | ||
| 674 | last BREAKSET; } } } | ||
| 675 | LAYOUT: foreach my $children_layout (@children_layouts) { | ||
| 676 | my ($width, $height, $depth, $penalty, $indent, $rowheight, $rowdepth) = (0, 0, 0, 0, 0, 0, 0); | ||
| 677 | # $penalty = sum(map { $$_[2] } @$breakset); | ||
| 678 | $penalty = $breakpenalty; # penalty due to breaks, we may add more! | ||
| 679 | # Last (best) layout, for comparison & pruning | ||
| 680 | my $last = (@layouts && $layouts[-1]); | ||
| 681 | # Apply the breaks to split the children (actually their layout) into lines. | ||
| 682 | foreach my $line (split_row($breakset, @$children_layout)) { | ||
| 683 | my ($w, $h, $d) = (0, 0, 0); | ||
| 684 | my @line_children_layout = @$line; | ||
| 685 | # If ANY but LAST child on line have a break, skip this layout. | ||
| 686 | # [since MathML can't describe this left/right alignment for an mtable!] | ||
| 687 | if (grep { $$_{hasbreak} } @line_children_layout[0 .. $#line_children_layout - 1]) { | ||
| 688 | next LAYOUT; } | ||
| 689 | while (@line_children_layout) { # For each line of nodes, compute sizes, possibly prune | ||
| 690 | my $child_layout = shift(@line_children_layout); | ||
| 691 | $w += $$child_layout{width}; | ||
| 692 | $penalty += $$child_layout{penalty} || 0; | ||
| 693 | # Skip to next breakset if we've gotten too wide, or worse than previous | ||
| 694 | if ($last && (($w > 1.5 * $target) | ||
| 695 | # || (($$last{width} < 1.5*$target) && ($penalty > $$last{penalty})))){ | ||
| 696 | || (($$last{width} <= $w) && ($penalty > $$last{penalty})))) { | ||
| 697 | $pruned++; | ||
| 698 | # [next layout? or next breakset???] | ||
| 699 | next LAYOUT; } | ||
| 700 | |||
| 701 | $h = max($h, $$child_layout{height}); | ||
| 702 | $d = max($d, $$child_layout{depth}); | ||
| 703 | $rowheight = max($rowheight, $$child_layout{rowheight} || $$child_layout{height}); | ||
| 704 | $rowdepth = max($rowdepth, $$child_layout{rowdepth} || $$child_layout{depth}); | ||
| 705 | } | ||
| 706 | # Then combine the lines | ||
| 707 | $width = max($width, $w + $indent); | ||
| 708 | $indent = $indentation; | ||
| 709 | if ($height == 0) { | ||
| 710 | $height = $h; | ||
| 711 | $depth = $d; } | ||
| 712 | else { | ||
| 713 | $depth += $h + $d; } } | ||
| 714 | push(@layouts, { node => $node, type => $type, | ||
| 715 | penalty => $penalty, | ||
| 716 | width => $width, height => $height, depth => $depth, | ||
| 717 | indentation => $indentation, | ||
| 718 | rowheight => ($hasfences ? 1.2 * $rowheight : $rowheight), | ||
| 719 | rowdepth => ($hasfences ? 1.2 * $rowdepth : $rowdepth), | ||
| 720 | lhs_pos => $lhs_pos, | ||
| 721 | (scalar(@$breakset) ? (breakset => $breakset) : ()), | ||
| 722 | hasbreak => scalar(@$breakset) || scalar(grep { $$_{hasbreak} } @$children_layout), | ||
| 723 | children => [@$children_layout], | ||
| 724 | displaystyle => $LaTeXML::DISPLAYSTYLE }); | ||
| 725 | @layouts = prunesort($target, @layouts); } | ||
| 726 | # } | ||
| 727 | last unless $breakpositions = breakstepper($nbreaks, $breakpositions); } | ||
| 728 | |||
| 729 | ## }} | ||
| 730 | ## @layouts = prunesort($target,@layouts); | ||
| 731 | |||
| 732 | ## Add a penalty for smallest area (?) | ||
| 733 | ## TRY PUTTING THIS AT TOP LEVEL | ||
| 734 | ## my($maxarea,$minarea) = (0,999999999); | ||
| 735 | ## map { $maxarea = max($maxarea,$$_{area}) } @layouts; | ||
| 736 | ## map { $minarea = min($minarea,$$_{area}) } @layouts; | ||
| 737 | ## map { $$_{penalty} *= (1+($$_{area} -$minarea)/$maxarea) } @layouts if $maxarea > $minarea; | ||
| 738 | |||
| 739 | @layouts = prunesort($target, @layouts); | ||
| 740 | layout_warn("Row (" . nodeName($node) . ") got no layouts!") unless @layouts; | ||
| 741 | return [@layouts]; } | ||
| 742 | |||
| 743 | sub split_row { | ||
| 744 | my ($breakset, @stuff) = @_; | ||
| 745 | my @lines = (); | ||
| 746 | my $pos = 0; | ||
| 747 | foreach my $break (@$breakset) { | ||
| 748 | my ($breakpos, $content, $demerit) = @$break; | ||
| 749 | push(@lines, [@stuff[$pos .. $breakpos - 1]]); | ||
| 750 | $pos = $breakpos; } | ||
| 751 | push(@lines, [@stuff[$pos .. $#stuff]]); | ||
| 752 | return @lines; } | ||
| 753 | |||
| 754 | # Given N possible breakpoints, there are 2^N layouts! This does NOT scale well!!! | ||
| 755 | # We'll try to process breaks in order of 0 breaks, 1 break, 2 breaks... | ||
| 756 | # so that we can stop when we get too many breaks | ||
| 757 | # [Could conceivably estimate the _minimum_ number of breaks required, too?] | ||
| 758 | sub breakstepper { | ||
| 759 | my ($nbreaks, $breaks, $delta) = @_; | ||
| 760 | my $last = $$breaks[-1]; | ||
| 761 | $delta = 0 unless $delta; | ||
| 762 | if (!$nbreaks) { | ||
| 763 | return; } | ||
| 764 | elsif (!defined $last) { | ||
| 765 | return $breaks = [0]; } | ||
| 766 | elsif ($last < $nbreaks - $delta - 1) { | ||
| 767 | $$breaks[-1]++; # increment last break point | ||
| 768 | return $breaks; } | ||
| 769 | else { | ||
| 770 | pop(@$breaks); # Remove last break point. | ||
| 771 | $breaks = breakstepper($nbreaks, $breaks, $delta + 1); # step the previous break point. | ||
| 772 | return unless $breaks; | ||
| 773 | my $prev = $$breaks[-1]; | ||
| 774 | if ($prev < $nbreaks - $delta - 1) { # Still room to add this break? | ||
| 775 | push(@$breaks, $prev + 1); | ||
| 776 | return $breaks; } | ||
| 777 | else { # step to more breaks | ||
| 778 | my $nb = scalar(@$breaks) + 1; | ||
| 779 | if ($nb > $nbreaks) { | ||
| 780 | return; } | ||
| 781 | else { | ||
| 782 | return $breaks = [0 .. $nb - 1]; } } } } | ||
| 783 | |||
| 784 | ####################################################################### | ||
| 785 | # Layout handlers for various MathML tags | ||
| 786 | # These are called layout_<tag> | ||
| 787 | ####################################################################### | ||
| 788 | |||
| 789 | #====================================================================== | ||
| 790 | # Trivial cases. | ||
| 791 | #====================================================================== | ||
| 792 | # These are just empty. | ||
| 793 | sub layout_none { | ||
| 794 | my ($node, $target, $level, $demerits) = @_; | ||
| 795 | my $content = textContent($node); | ||
| 796 | return [{ node => $node, type => "none", | ||
| 797 | penalty => 0, width => 0, height => 0, depth => 0 }]; } | ||
| 798 | |||
| 799 | sub layout_empty { | ||
| 800 | my ($node, $target, $level, $demerits) = @_; | ||
| 801 | my $content = textContent($node); | ||
| 802 | return [{ node => $node, type => "empty", | ||
| 803 | penalty => 0, width => 0, height => 0, depth => 0 }]; } | ||
| 804 | |||
| 805 | #====================================================================== | ||
| 806 | # Simple cases. | ||
| 807 | #====================================================================== | ||
| 808 | # These are just simple boxes that don't break. | ||
| 809 | # Approximate their size. | ||
| 810 | |||
| 811 | my @SIZE = ( # [CONSTANT] | ||
| 812 | 1.0, 0.71, 0.71 * 0.71, 0.71 * 0.71 * 0.71); | ||
| 813 | # TODO: spacing ? | ||
| 814 | # TODO for mo: largeop ? | ||
| 815 | sub simpleSize { | ||
| 816 | my ($node, $target, $level, $demerits) = @_; | ||
| 817 | my $content = textContent($node); | ||
| 818 | ### my $scriptlevel = min(0, max($LaTeXML::SCRIPTLEVEL + ($LaTeXML::DISPLAYSTYLE ? -1 : 0), 3)); | ||
| 819 | my $scriptlevel = min(0, max($LaTeXML::SCRIPTLEVEL, 3)); | ||
| 820 | my $len = length($content); | ||
| 821 | my $size = $SIZE[$scriptlevel]; | ||
| 822 | return [{ node => $node, type => nodeName($node), penalty => 0, | ||
| 823 | # width => $len * $size, height => $size, depth => 0, | ||
| 824 | # width => 0.75 * $len * $size, height => 0.7 * $size, depth => 0.2 * $size | ||
| 825 | width => $len * $size, height => 0.7 * $size, depth => 0.2 * $size | ||
| 826 | |||
| 827 | }]; } | ||
| 828 | |||
| 829 | sub layout_mi { my (@args) = @_; return simpleSize(@args); } | ||
| 830 | sub layout_mo { my (@args) = @_; return simpleSize(@args); } | ||
| 831 | sub layout_mn { my (@args) = @_; return simpleSize(@args); } | ||
| 832 | sub layout_mspace { my (@args) = @_; return simpleSize(@args); } | ||
| 833 | sub layout_mtext { my (@args) = @_; return simpleSize(@args); } | ||
| 834 | sub layout_merror { my (@args) = @_; return simpleSize(@args); } | ||
| 835 | |||
| 836 | #====================================================================== | ||
| 837 | # Various row-line things. | ||
| 838 | #====================================================================== | ||
| 839 | sub layout_mrow { my (@args) = @_; return asRow(@args); } | ||
| 840 | sub layout_mpadded { my (@args) = @_; return asRow(@args); } | ||
| 841 | sub layout_mphantom { my (@args) = @_; return asRow(@args); } | ||
| 842 | sub layout_menclose { my (@args) = @_; return asRow(@args); } | ||
| 843 | sub layout_mfenced { my (@args) = @_; return asRow(@args); } # Close enough? | ||
| 844 | |||
| 845 | sub layout_maction { | ||
| 846 | my ($node, $target, $level, $demerits) = @_; | ||
| 847 | my $selection = getAttribute($node, 'selection') || 0; | ||
| 848 | my @children = nodeChildren($node); | ||
| 849 | return layout($children[$selection], $target, $level, $demerits); } | ||
| 850 | |||
| 851 | sub layout_mstyle { | ||
| 852 | my ($node, $target, $level, $demerits) = @_; | ||
| 853 | local $LaTeXML::DISPLAYSTYLE = $LaTeXML::DISPLAYSTYLE; | ||
| 854 | local $LaTeXML::SCRIPTLEVEL = $LaTeXML::SCRIPTLEVEL; | ||
| 855 | if (my $d = getAttribute($node, 'displaystyle')) { | ||
| 856 | $LaTeXML::DISPLAYSTYLE = ($d eq 'true'); } | ||
| 857 | if (my $s = getAttribute($node, 'scriptlevel')) { | ||
| 858 | if ($s =~ /^\+(\d+)$/) { $LaTeXML::SCRIPTLEVEL += $1; } | ||
| 859 | elsif ($s =~ /^\-(\d+)$/) { $LaTeXML::SCRIPTLEVEL -= $1; } | ||
| 860 | elsif ($s =~ /^(\d+)$/) { $LaTeXML::SCRIPTLEVEL = $1; } } | ||
| 861 | return asRow($node, $target, $level, $demerits); } | ||
| 862 | |||
| 863 | #====================================================================== | ||
| 864 | # Fractions & Roots | ||
| 865 | #====================================================================== | ||
| 866 | # These allow the children to break, but with heavier penalty. | ||
| 867 | |||
| 868 | sub layout_mfrac { | ||
| 869 | my ($node, $target, $level, $demerits) = @_; | ||
| 870 | # No break of mfrac itself | ||
| 871 | # 2 children; break of children is poor | ||
| 872 | local $LaTeXML::SCRIPTLEVEL = ($LaTeXML::DISPLAYSTYLE | ||
| 873 | ? $LaTeXML::SCRIPTLEVEL | ||
| 874 | : $LaTeXML::SCRIPTLEVEL + 1); | ||
| 875 | local $LaTeXML::DISPLAYSTYLE = 0; | ||
| 876 | return [map { | ||
| 877 | { node => $node, type => 'mfrac', | ||
| 878 | penalty => $$_[0]->{penalty} + $$_[1]->{penalty}, | ||
| 879 | width => max($$_[0]->{width}, $$_[1]->{width}), | ||
| 880 | height => $$_[0]->{height} + $$_[0]->{depth} + 0.1 + 0.5, # (1ex) | ||
| 881 | depth => $$_[1]->{height} + $$_[1]->{depth} - 0.5, | ||
| 882 | hasbreak => $$_[0]->{hasbreak} || $$_[1]->{hasbreak}, | ||
| 883 | children => $_ } } | ||
| 884 | multiplex(map { layout($_, $target, $level + 1, $demerits * $POORBREAK_FACTOR) } | ||
| 885 | nodeChildren($node))]; } | ||
| 886 | |||
| 887 | sub layout_mroot { | ||
| 888 | my ($node, $target, $level, $demerits) = @_; | ||
| 889 | # no break of mroot itself, index doesn't break, break of base is bad | ||
| 890 | my ($base, $index) = nodeChildren($node); | ||
| 891 | local $LaTeXML::DISPLAYSTYLE = 0; | ||
| 892 | my $indexlayout; | ||
| 893 | { local $LaTeXML::SCRIPTLEVEL = $LaTeXML::SCRIPTLEVEL + 1; | ||
| 894 | $indexlayout = layout($index, $target, $level + 1, $NOBREAK)->[0]; } | ||
| 895 | $target -= $$indexlayout{width}; | ||
| 896 | my $baselayouts = layout($base, $target, $level + 1, $demerits * $BADBREAK_FACTOR); | ||
| 897 | return [map { | ||
| 898 | { node => $node, type => 'mroot', | ||
| 899 | penalty => $$_[0]->{penalty} + $$_[1]->{penalty}, | ||
| 900 | width => $$_[0]->{width} + $$_[1]->{width}, | ||
| 901 | height => $$_[0]->{height}, | ||
| 902 | depth => $$_[0]->{depth}, | ||
| 903 | hasbreak => $$_[0]->{hasbreak} || $$_[1]->{hasbreak}, | ||
| 904 | children => $_ } } | ||
| 905 | multiplex($baselayouts, [$indexlayout])]; } | ||
| 906 | |||
| 907 | sub layout_msqrt { | ||
| 908 | my ($node, $target, $level, $demerits) = @_; | ||
| 909 | # no break of msqrt itself, | ||
| 910 | # 1 child or implied mrow; bad to break | ||
| 911 | return asRow($node, $target, $level + 1, $demerits * $BADBREAK_FACTOR); } | ||
| 912 | |||
| 913 | #====================================================================== | ||
| 914 | # Tables | ||
| 915 | #====================================================================== | ||
| 916 | # We're not allowing breaks within tables, but we still have a mess of sums & max's | ||
| 917 | |||
| 918 | sub layout_mtable { | ||
| 919 | my ($node, $target, $level, $demerits) = @_; | ||
| 920 | local $LaTeXML::DISPLAYSTYLE = 0; | ||
| 921 | local $LaTeXML::SCRIPTLEVEL = $LaTeXML::SCRIPTLEVEL + 1; | ||
| 922 | my @widths = (); | ||
| 923 | my @heights = (); | ||
| 924 | my @depths = (); | ||
| 925 | foreach my $row (nodeChildren($node)) { | ||
| 926 | my ($h, $d) = (0, 0); | ||
| 927 | my $i = 0; | ||
| 928 | foreach my $col (nodeChildren($row)) { | ||
| 929 | my $layout = layout($col, $target, $level + 1, $NOBREAK)->[0]; | ||
| 930 | $widths[$i] = max($widths[$i] || 0, $$layout{width}); | ||
| 931 | $h = max($h, $$layout{height}); | ||
| 932 | $d = max($d, $$layout{depth}); | ||
| 933 | $i++; } | ||
| 934 | push(@heights, $h); push(@depths, $d); } | ||
| 935 | my $width = sum(@widths); | ||
| 936 | my ($height, $depth); | ||
| 937 | my $align = getAttribute($node, 'align') || 'axis'; | ||
| 938 | my $n = scalar(@heights); | ||
| 939 | if ($align =~ s/(\d+)//) { | ||
| 940 | my $i = $1; | ||
| 941 | ($height, $depth) = tableVAlignment($align, $heights[$i - 1], $depths[$i - 1]); | ||
| 942 | $height += sum(@heights[0 .. $i - 2]) + sum(@depths[0 .. $i - 2]) if $i > 1; | ||
| 943 | $depth += sum(@heights[$i .. $n - 1]) + sum(@depths[$i .. $n - 1]) if $i < $n; } | ||
| 944 | else { | ||
| 945 | $height = (sum(@heights) + sum(@depths)) / 2; $depth = $height; | ||
| 946 | ($height, $depth) = tableVAlignment($align, $height, $depth); } | ||
| 947 | return [{ node => $node, type => nodeName($node), | ||
| 948 | penalty => 0, width => $width, height => $height, depth => $depth }]; } | ||
| 949 | |||
| 950 | sub tableVAlignment { | ||
| 951 | my ($align, $height, $depth) = @_; | ||
| 952 | if ($align eq 'top') { $depth = $height + $depth; $height = 0; } | ||
| 953 | elsif ($align eq 'bottom') { $height = $height + $depth; $depth = 0; } | ||
| 954 | elsif ($align eq 'center') { $height = ($height + $depth) / 2; $depth = $height; } | ||
| 955 | elsif ($align eq 'axis') { $height = ($height + $depth) / 2; $depth = $height; } | ||
| 956 | elsif ($align eq 'baseline') { } | ||
| 957 | return ($height, $depth); } | ||
| 958 | |||
| 959 | sub sum { | ||
| 960 | my (@x) = @_; | ||
| 961 | my $sum = 0; | ||
| 962 | foreach my $x (@x) { | ||
| 963 | $sum += $x || 0; } | ||
| 964 | return $sum; } | ||
| 965 | |||
| 966 | sub product { | ||
| 967 | my (@x) = @_; | ||
| 968 | my $prod = 1; | ||
| 969 | foreach my $x (@x) { | ||
| 970 | $prod *= $x || 1; } | ||
| 971 | return $prod; } | ||
| 972 | |||
| 973 | #sub layout_mtr {} | ||
| 974 | #sub layout_mlabeledtr {} | ||
| 975 | sub layout_mtd { my (@args) = @_; return asRow(@args); } | ||
| 976 | |||
| 977 | #====================================================================== | ||
| 978 | # Various sub & super scripts | ||
| 979 | #====================================================================== | ||
| 980 | # TODO: What about movablelimits, accent on base ? | ||
| 981 | sub asScripts { | ||
| 982 | my ($node, $target, $level, $demerits, | ||
| 983 | $stacked, $basenode, @scriptnodes) = @_; | ||
| 984 | # Scripts do not break, base is poor to break. | ||
| 985 | my @layouts = (); | ||
| 986 | my $baselayouts = layout($basenode, $target, $level + 1, $demerits * $POORBREAK_FACTOR); | ||
| 987 | my @scriptslayouts; | ||
| 988 | { local $LaTeXML::DISPLAYSTYLE = 0; | ||
| 989 | local $LaTeXML::SCRIPTLEVEL = $LaTeXML::SCRIPTLEVEL + 1; | ||
| 990 | @scriptslayouts = map { layout($_, $target, $level + 1, $NOBREAK) } @scriptnodes; } | ||
| 991 | foreach my $layoutset (multiplex($baselayouts, @scriptslayouts)) { | ||
| 992 | my ($base, @scripts) = @$layoutset; | ||
| 993 | my ($width, $height, $depth, $penalty) = (0, 0, 0, 0); | ||
| 994 | while (@scripts) { | ||
| 995 | my $sub = shift(@scripts); | ||
| 996 | my $sup = shift(@scripts); | ||
| 997 | $width += max($$sub{width}, $$sup{width}); | ||
| 998 | $height += max($height, $$sup{depth} + $$sup{height}); # Roughly.. | ||
| 999 | $depth += max($depth, $$sub{depth} + $$sub{height}); | ||
| 1000 | $penalty += $$sub{penalty} + $$sup{penalty}; } | ||
| 1001 | $penalty += $$base{penalty}; | ||
| 1002 | if ($stacked) { | ||
| 1003 | $width = max($width, $$base{width}); | ||
| 1004 | $height += $$base{height}; | ||
| 1005 | $depth += $$base{depth}; } | ||
| 1006 | else { | ||
| 1007 | $width += $$base{width}; | ||
| 1008 | $height = $$base{height} + 0.5 * $height; | ||
| 1009 | $depth = $$base{depth} + 0.5 * $depth; } | ||
| 1010 | push(@layouts, { node => $node, type => nodeName($node), | ||
| 1011 | penalty => $penalty, width => $width, height => $height, depth => $depth, | ||
| 1012 | hasbreak => scalar(grep { $$_{hasbreak} } @$layoutset), | ||
| 1013 | children => $layoutset }); } | ||
| 1014 | return [@layouts]; } | ||
| 1015 | |||
| 1016 | sub layout_msub { | ||
| 1017 | my ($node, $target, $level, $demerits) = @_; | ||
| 1018 | my ($base, $sub) = nodeChildren($node); | ||
| 1019 | return asScripts($node, $target, $level, $demerits, 0, $base, $sub, ['m:mrow']); } | ||
| 1020 | |||
| 1021 | sub layout_msup { | ||
| 1022 | my ($node, $target, $level, $demerits) = @_; | ||
| 1023 | my ($base, $sup) = nodeChildren($node); | ||
| 1024 | return asScripts($node, $target, $level, $demerits, 0, $base, ['m:mrow'], $sup); } | ||
| 1025 | |||
| 1026 | sub layout_msubsup { | ||
| 1027 | my ($node, $target, $level, $demerits) = @_; | ||
| 1028 | my ($base, $sub, $sup) = nodeChildren($node); | ||
| 1029 | return asScripts($node, $target, $level, $demerits, 0, $base, $sub, $sup); } | ||
| 1030 | |||
| 1031 | sub layout_munder { | ||
| 1032 | my ($node, $target, $level, $demerits) = @_; | ||
| 1033 | my ($base, $sub) = nodeChildren($node); | ||
| 1034 | return asScripts($node, $target, $level, $demerits, 1, $base, $sub, ['m:mrow']); } | ||
| 1035 | |||
| 1036 | sub layout_mover { | ||
| 1037 | my ($node, $target, $level, $demerits) = @_; | ||
| 1038 | my ($base, $sup) = nodeChildren($node); | ||
| 1039 | return asScripts($node, $target, $level, $demerits, 1, $base, ['m:mrow'], $sup); } | ||
| 1040 | |||
| 1041 | sub layout_munderover { | ||
| 1042 | my ($node, $target, $level, $demerits) = @_; | ||
| 1043 | my ($base, $sub, $sup) = nodeChildren($node); | ||
| 1044 | return asScripts($node, $target, $level, $demerits, 1, $base, $sub, $sup); } | ||
| 1045 | |||
| 1046 | sub layout_mmultiscripts { | ||
| 1047 | my ($node, $target, $level, $demerits) = @_; | ||
| 1048 | my ($base, @scripts) = nodeChildren($node); | ||
| 1049 | @scripts = grep { nodeName($_) ne "m:mprescripts" } @scripts; # Remove prescripts marker (if any). | ||
| 1050 | return asScripts($node, $target, $level, $demerits, 0, $base, @scripts); } | ||
| 1051 | |||
| 1052 | #====================================================================== | ||
| 1053 | 1; |