lib/LaTeXML/Post/MathML/Linebreaker.pm untested

filter: Statementstmt 0.0% 0 / 682 Branchbran 0.0% 0 / 216 Conditioncond 0.0% 0 / 137 MC/DCmcdc 0.0% 0 / 80 Subroutinesub 0.0% 0 / 63 Podpod 0.0% 0 / 58 totaltotal 0.0% 0 / 1236 CC 109 SCAR 52.1
CC
109
Cov
0%
asRow
870.0
applyLayout_rec
156.0
applyLayout_break
110.0
CRAP 183.9
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;