1 /*
2 * Changes by Gunnar Ritter, Freiburg i. Br., Germany, October 2005.
3 *
4 * Derived from Plan 9 source code published at the 9fans list by Rob Pike,
5 * <http://lists.cse.psu.edu/archives/9fans/2002-February/015773.html>
6 *
7 * Copyright (C) 2003, Lucent Technologies Inc. and others.
8 * All Rights Reserved.
9 *
10 * Distributed under the terms of the Lucent Public License Version 1.02.
11 */
12
13 /* Sccsid @(#)page.cc 1.4 (gritter) 10/30/05 */
14 #include <locale.h>
15 #include "misc.h"
16 #include "slug.h"
17 #include "range.h"
18 #include "page.h"
19
20 const int MAXRANGES = 1000;
21 static range *ptemp[MAXRANGES]; // for movefloats()
22
swapright(int n)23 static void swapright(int n) // used by movefloats()
24 {
25 range *t = ptemp[n];
26 ptemp[n] = ptemp[n+1];
27 ptemp[n+1] = t;
28 ptemp[n]->setaccum( ptemp[n+1]->accum() -
29 ptemp[n+1]->rawht() + ptemp[n]->rawht() );
30 ptemp[n+1]->setaccum( ptemp[n]->accum() + ptemp[n+1]->rawht() );
31 }
32
33 // Figure out the goal position for each floating range on scratch,
34 // and move it past stream ranges until it's as close to its goal as possible.
movefloats(stream * scratch,double scale)35 static void movefloats(stream *scratch, double scale)
36 {
37 const int Huge = 10000000;
38 int nranges;
39 for (nranges = 0; scratch->more(); scratch->advance())
40 ptemp[nranges++] = scratch->current();
41 scratch->freeall();
42 ufrange rtemp;
43 ptemp[nranges] = &rtemp;
44 rtemp.setgoal(Huge);
45 int accumV = 0; // compute accum values and
46 int i;
47 for (i = 0; i < nranges; i++) { // pick closest goal for floats
48 ptemp[i]->pickgoal(accumV, scale);
49 ptemp[i]->setaccum(accumV += ptemp[i]->rawht());
50 }
51 int j; // index for inner loop below:
52 for (i = nranges; --i >= 0; ) // stably sort floats to bottom
53 for (j = i; j < nranges; j++)
54 if (ptemp[j]->goal() > ptemp[j+1]->goal())
55 swapright(j);
56 else
57 break;
58 if (dbg & 16)
59 printf("#movefloats: before floating, from bottom:\n");
60 for (i = nranges; --i >= 0; ) { // find topmost float
61 if (ptemp[i]->goal() == NOGOAL)
62 break;
63 if (dbg & 16)
64 printf("# serialno %d goal %d height %d\n",
65 ptemp[i]->serialno(), ptemp[i]->goal(),
66 ptemp[i]->rawht());
67 } // i+1 is topmost float
68 for (i++ ; i < nranges; i++) // move each float up the page
69 for (j = i; j > 0; j--) // as long as closer to its goal
70 if (ptemp[j]->goal()
71 <= ptemp[j-1]->accum() + ptemp[j]->rawht()/2
72 && ptemp[j-1]->goal() == NOGOAL)
73 swapright(j-1);
74 else
75 break;
76 if (ptemp[nranges] != &rtemp)
77 FATAL("goal sentinel has disappeared from movefloats");
78 for (i = 0; i < nranges; i++) // copy sorted list back
79 scratch->append(ptemp[i]);
80 }
81
82 // Traverse the leaves of a tree of ranges, filtering out only SP and VBOX.
filter(generator * g)83 static range *filter(generator *g)
84 {
85 range *r;
86 while ((r = g->next()))
87 if (r->isvbox() || r->issp())
88 break;
89 return r;
90 }
91
92 // Zero out leading and trailing spaces; coalesce adjacent SP's.
trimspace(stream * scratch)93 static void trimspace(stream *scratch)
94 {
95 range *r, *prevr = 0;
96 generator g;
97 for (g = scratch; (r = filter(&g)) != 0 && r->issp(); prevr = r)
98 r->setheight(0); // zap leading SP
99 for ( ; (r = filter(&g)) != 0; prevr = r)
100 if (r->issp())
101 {
102 if (prevr && prevr->issp()) {
103 // coalesce adjacent SPs
104 r->setheight(max(r->rawht(), prevr->height()));
105 prevr->setheight(0);
106 } else // a VBOX intervened
107 r->setheight(r->rawht());
108 }
109 if (prevr && prevr->issp()) // zap *all* trailing space
110 prevr->setheight(0); // (since it all coalesced
111 // into the last one)
112 }
113
114 // Pad the non-zero SP's in scratch so the total height is wantht.
115 // Note that the SP values in scratch are not the raw values, and
116 // indeed may already have been padded.
justify(stream * scratch,int wantht)117 static void justify(stream *scratch, int wantht)
118 {
119 range *r;
120 int nsp = 0, hsp = 0;
121
122 int adjht = scratch->height();
123 // Find all the spaces.
124 generator g;
125 for (g = scratch; (r = g.next()); )
126 if (r->issp() && r->height() > 0) {
127 nsp++;
128 hsp += r->height();
129 }
130 int excess = wantht - adjht;
131 if (excess < 0)
132 WARNING("something on page %d is oversize by %d\n",
133 userpn, -excess);
134 if (dbg & 16)
135 printf("# justify %d: excess %d nsp %d hsp %d adjht %d\n",
136 userpn, excess, nsp, hsp, adjht);
137 if (excess <= 0 || nsp == 0)
138 return;
139 // Redistribute the excess space.
140 for (g = scratch; (r = g.next()); )
141 if (r->issp() && r->height() > 0) {
142 int delta = (int) ((float)(r->height()*excess)/hsp + 0.5);
143 if (dbg & 16)
144 printf("# pad space %d by %d: hsp %d excess %d\n",
145 r->height(), delta, hsp, excess);
146 r->setheight(r->height() + delta);
147 }
148 }
149
150 // If r were added to s, would the height of the composed result be at most maxht?
wouldfit(range * r,stream * s,int maxht)151 int wouldfit(range *r, stream *s, int maxht)
152 {
153 if (r->rawht() + s->rawht() <= maxht)
154 return 1; // the conservative test succeeded
155 stream scratch; // local playground for costly test
156 for (stream cd = *s; cd.more(); cd.advance())
157 scratch.append(cd.current());
158 scratch.append(r);
159 movefloats(&scratch, ((double) scratch.rawht())/maxht);
160 trimspace(&scratch);
161 int retval = scratch.height() <= maxht;
162 scratch.freeall();
163 return retval;
164 }
165
166 // If s1 were added to s, would the height of the composed result be at most maxht?
167 // The computational structure is similar to that above.
wouldfit(stream * s1,stream * s,int maxht)168 int wouldfit(stream *s1, stream *s, int maxht)
169 {
170 if (s1->rawht() + s->rawht() <= maxht)
171 return 1;
172 stream scratch, cd;
173 for (cd = *s; cd.more(); cd.advance())
174 scratch.append(cd.current());
175 for (cd = *s1; cd.more(); cd.advance())
176 scratch.append(cd.current());
177 movefloats(&scratch, ((double) scratch.rawht())/maxht);
178 trimspace(&scratch);
179 int retval = scratch.height() <= maxht;
180 scratch.freeall();
181 return retval;
182 }
183
184 // All of stream *s is destined for one column or the other; which is it to be?
choosecol(stream * s,int goalht)185 void multicol::choosecol(stream *s, int goalht)
186 {
187 stream *dest;
188 if (!leftblocked && wouldfit(s, &(column[0]), goalht))
189 dest = &(column[0]);
190 else {
191 dest = &(column[1]);
192 if (!s->current()->floatable())
193 // a stream item is going into the right
194 // column, so no more can go into the left.
195 leftblocked = 1;
196 }
197 for (stream cd = *s; cd.more(); cd.advance())
198 dest->append(cd.current());
199 }
200
201 double coltol = 0.5;
202
203 // Try, very hard, to put everything in the multicol into two columns
204 // so that the total height is at most htavail.
compose(int defonly)205 void multicol::compose(int defonly)
206 {
207 if (!nonempty()) {
208 setheight(0);
209 return;
210 }
211 scratch.freeall(); // fill scratch with everything destined
212 // for either column
213 stream cd;
214 for (cd = definite; cd.more(); cd.advance())
215 scratch.append(cd.current());
216 if (!defonly)
217 for (cd = *(currpage->stage); cd.more(); cd.advance())
218 if (cd.current()->numcol() == 2)
219 scratch.append(cd.current());
220 scratch.restoreall(); // in particular, floatables' goals
221 int rawht = scratch.rawht();
222 int halfheight = (int)(coltol*rawht);
223 // choose a goal height
224 int maxht = defonly ? halfheight : htavail;
225 secondtry:
226 int i;
227 for (i = 0; i < 2; i++)
228 column[i].freeall();
229 leftblocked = 0;
230 cd = scratch;
231 while (cd.more()) {
232 queue ministage; // for the minimally acceptable chunks
233 ministage.freeall(); // that are to be added to either column
234 while (cd.more() && !cd.current()->issentinel()) {
235 ministage.enqueue(cd.current());
236 cd.advance();
237 }
238 choosecol(&ministage, maxht);
239 if (cd.more() && cd.current()->issentinel())
240 cd.advance(); // past sentinel
241 }
242 if (height() > htavail && maxht != htavail) {
243 // We tried to balance the columns, but
244 // the result was too tall. Go back
245 // and try again with the less ambitious
246 // goal of fitting the space available.
247 maxht = htavail;
248 goto secondtry;
249 }
250 for (i = 0; i < 2; i++) {
251 movefloats(&(column[i]), ((double) column[i].rawht())/currpage->pagesize);
252 trimspace(&(column[i]));
253 }
254 if (dbg & 32) {
255 printf("#multicol::compose: htavail %d maxht %d dv %d\n",
256 htavail, maxht, height());
257 dump();
258 }
259 if (defonly)
260 stretch(height());
261 }
262
263 // A sequence of two-column ranges waits on the stage.
264 // So long as the page's skeleton hasn't changed--that is, the maximum height
265 // available to the two-column chunk is the same--we just use the columns that
266 // have been built up so far, and choose a column into which to put the stage.
267 // If the skeleton has changed, however, then we may need to make entirely
268 // new decisions about which column gets what, so we recompose the whole page.
tryout()269 void multicol::tryout()
270 {
271 if (htavail == prevhtavail)
272 choosecol(currpage->stage, htavail);
273 else
274 currpage->compose(DRAFT);
275 prevhtavail = htavail;
276 }
277
278 // Make both columns the same height.
279 // (Maybe this should also be governed by minfull,
280 // to prevent padding very underfull columns.)
stretch(int wantht)281 void multicol::stretch(int wantht)
282 {
283 if (wantht < height())
284 FATAL("page %d: two-column chunk cannot shrink\n", userpn);
285 for (int i = 0; i < 2; i++)
286 justify(&(column[i]), wantht);
287 if (dbg & 16)
288 printf("#col hts: left %d right %d\n",
289 column[0].height(), column[1].height());
290 }
291
292 // Report an upper bound on how tall the current two-column object is.
293 // The (possibly composed) heights of the two columns give a crude upper
294 // bound on the total height. If the result is more than the height
295 // available for the two-column object, then the columns are each
296 // composed to give a better estimate of their heights.
height()297 int multicol::height()
298 {
299 int retval = max(column[0].height(), column[1].height());
300 if (retval < htavail)
301 return retval;
302 for (int i = 0; i < 2; i++) {
303 movefloats(&(column[i]), ((double) column[i].height())/currpage->pagesize);
304 trimspace(&(column[i]));
305 }
306 return max(column[0].height(), column[1].height());
307 }
308
dump()309 void multicol::dump()
310 {
311 printf("####2COL dv %d\n", height());
312 printf("# left column:\n");
313 column[0].dump();
314 printf("# right column:\n");
315 column[1].dump();
316 }
317
318 // From the head of queue qp, peel off a piece whose raw height is at most space.
peeloff(stream * qp,int space)319 int peeloff(stream *qp, int space)
320 {
321 stream *s1 = qp->current()->children();
322 if (!(s1 && s1->more() && s1->current()->height() <= space))
323 // in other words, either qp's head is
324 // not nested, or its first subrange
325 return 0; // is also too big, so we give up
326 qp->split();
327 s1 = qp->current()->children();
328 stream *s2 = qp->next()->children();
329 while (s2->more() && s2->current()->rawht() <= space) {
330 s1->append(s2->current());
331 space -= s2->current()->rawht();
332 s2->advance();
333 }
334 return 1;
335 }
336
337 // There are four possibilities for consecutive calls to tryout().
338 // If we're processing a sequence of single-column ranges, tryout()
339 // uses the original algorithm: (1) conservative test; (2) costly test;
340 // (3) split a breakable item.
341 // If we're processing a sequence of double-column ranges, tryout()
342 // defers to twocol->tryout(), which gradually builds up the contents
343 // of the two columns until they're as tall as they can be without
344 // exceeding twocol->htavail.
345 // If we're processing a sequence of single-column ranges and we
346 // get a double-column range, then we use compose() to build a
347 // skeleton page and set twocol->htavail, the maximum height that
348 // should be occupied by twocol.
349 // If we're processing a sequence of double-column ranges and we
350 // get a single-column range, then we should go back and squish
351 // the double-column chunk as short as possible before we see if
352 // we can fit the single-column range.
tryout()353 void page::tryout()
354 {
355 if (!stage->more())
356 FATAL("empty stage in page::tryout()\n");
357 int curnumcol = stage->current()->numcol();
358 if (dbg & 32) {
359 printf("#page::tryout(): ncol = %d, prevncol = %d; on stage:\n",
360 curnumcol, prevncol);
361 stage->dump();
362 printf("#END of stage contents\n");
363 }
364 switch(curnumcol) {
365 default:
366 FATAL("unexpected number of columns in tryout(): %d\n",
367 stage->current()->numcol());
368 break;
369 case 1:
370 if (prevncol == 2)
371 compose(FINAL);
372 if (wouldfit(stage, &definite, pagesize - twocol->height()))
373 commit();
374 else if (stage->current()->breakable() || (blank()
375 && peeloff(stage,
376 pagesize - (definite.height() +
377 twocol->height())))) {
378 // first add the peeled-off part that fits
379 adddef(stage->dequeue());
380 // then send the rest back for later
381 stage->current()->setbreaking();
382 welsh();
383 } else if (blank()) {
384 stage->current()->rdump();
385 FATAL("A %s is too big to continue.\n",
386 stage->current()->typname());
387 } else
388 welsh();
389 break;
390 case 2:
391 if (prevncol == 1)
392 compose(DRAFT);
393 else
394 twocol->tryout();
395 if (scratch.height() <= pagesize)
396 commit();
397 else
398 welsh();
399 break;
400 }
401 prevncol = curnumcol;
402 }
403
404 // To compose the page, we (1) fill scratch with the stuff that's meant to
405 // go on the page; (2) compose scratch as best we can; (3) set the maximum
406 // height available to the two-column part of the page; (4) have the two-
407 // column part compose itself.
408 // In the computation of twocol->htavail, it does not matter that
409 // twocol->height() is merely an upper bound, because it is merely being
410 // subtracted out to give the exact total height of the single-column stuff.
compose(int final)411 void page::compose(int final)
412 {
413 makescratch(final);
414 int adjht = scratch.rawht();
415 if (dbg & 16)
416 printf("# page %d measure %d\n", userpn, adjht);
417 movefloats(&scratch, ((double) adjht)/pagesize);
418 trimspace(&scratch);
419 twocol->htavail = pagesize - (scratch.height() - twocol->height());
420 twocol->compose(final);
421 adjht = scratch.height();
422 if (dbg & 16)
423 printf("# page %d measure %d after trim\n", userpn, adjht);
424 }
425
426 // Fill the scratch area with ranges destined for the page.
427 // If defonly == 0, then add anything that's on stage--this is a trial run.
428 // If defonly != 0, use only what's definitely on the page.
makescratch(int defonly)429 void page::makescratch(int defonly)
430 {
431 scratch.freeall();
432 stream cd;
433 for (cd = definite; cd.more(); cd.advance())
434 scratch.append(cd.current());
435 if (!defonly)
436 for (cd = *stage; cd.more(); cd.advance())
437 if (cd.current()->numcol() == 1)
438 scratch.append(cd.current());
439 if (twocol->nonempty())
440 scratch.append(twocol);
441 }
442
443 // Accept the current contents of the stage.
444 // If the stage contains two-column ranges, add a sentinel to indicate the end
445 // of a chunk of stage contents.
commit()446 void page::commit()
447 {
448 if (dbg & 4)
449 printf("#entering page::commit()\n");
450 int numcol = 0;
451 while (stage->more()) {
452 numcol = stage->current()->numcol();
453 adddef(stage->dequeue());
454 }
455 if (numcol == 2)
456 adddef(new sentrange);
457 }
458
459 // Send the current contents of the stage back to its source.
welsh()460 void page::welsh()
461 {
462 if (dbg & 4)
463 printf("#entering page::welsh()\n");
464 while (stage->more()) {
465 range *r = stage->dequeue();
466 r->enqueue(ANDBLOCK);
467 }
468 }
469
470 enum { USonly = 1 };
471
472 // So long as anything is eligible to go onto the page, keep trying.
473 // Once nothing is eligible, compose and justify the page.
fill()474 void page::fill()
475 {
476 while (stage->prime())
477 stage->pend();
478 compose(FINAL);
479 if (dbg & 16)
480 scratch.dump();
481 if (anymore()) {
482 int adjht = scratch.height();
483 if (adjht > minfull*pagesize) {
484 justify(&scratch, pagesize);
485 adjht = scratch.height();
486 int stretchamt = max(pagesize - adjht, 0);
487 twocol->stretch(twocol->height() + stretchamt);
488 // in case the page's stretchability lies
489 // entirely in its two-column part
490 } else
491 WARNING("page %d only %.0f%% full; will not be adjusted\n",
492 userpn, 100*(double) adjht/pagesize);
493 }
494 }
495
adddef(range * r)496 void page::adddef(range *r)
497 {
498 if (dbg & 4)
499 printf("#entering page::adddef()\n");
500 switch (r->numcol()) {
501 case 1: definite.append(r);
502 break;
503 case 2: twocol->definite.append(r);
504 break;
505 default: FATAL("%d-column range unexpected\n", r->numcol());
506 }
507 }
508
print(int cv,int col)509 int multicol::print(int cv, int col)
510 {
511 if (col != 0)
512 FATAL("multicolumn output must start in left column\n");
513 int curv = cv, maxv = cv; // print left column
514 for ( ; column[0].more(); column[0].advance()) {
515 curv = column[0].current()->print(curv, 0);
516 maxv = max(maxv, curv);
517 }
518 curv = cv; // print right column
519 for ( ; column[1].more(); column[1].advance()) {
520 curv = column[1].current()->print(curv, 1);
521 maxv = max(maxv, curv);
522 }
523 return maxv;
524 }
525
print()526 void page::print()
527 {
528 static int tops = 1, bots = 1;
529 if (!scratch.more()) {
530 WARNING("## Here's what's left on squeue:\n");
531 squeue.dump();
532 WARNING("## Here's what's left on bfqueue:\n");
533 bfqueue.dump();
534 WARNING("## Here's what's left on ufqueue:\n");
535 ufqueue.dump();
536 WARNING("page %d appears to be empty\n", userpn);
537 fflush(stderr), fflush(stdout), exit(0);
538 // something is very wrong if this happens
539 }
540 printf("p%d\n", userpn); // print troff output page number
541 if (ptlist.more()) { // print page header
542 ptlist.current()->print(0, 0);
543 ptlist.advance();
544 } else if (tops) {
545 WARNING("ran out of page titles at %d\n", userpn);
546 tops = 0;
547 }
548 int curv = 0;
549 printf("V%d\n", curv = pagetop);// print page contents
550 for ( ; scratch.more(); scratch.advance()) {
551 curv = scratch.current()->print(curv, 0);
552 }
553 if (btlist.more()) { // print page footer
554 btlist.current()->print(0, 0);
555 btlist.advance();
556 } else if (bots) {
557 WARNING("ran out of page bottoms at %d\n", userpn);
558 bots = 0;
559 }
560 printf("V%d\n", physbot); // finish troff output page
561 }
562
563 int pagetop = 0; // top printing margin
564 int pagebot = 0; // bottom printing margin
565 int physbot = 0; // physical bottom of page
566
567 double minfull = 0.9; // minimum fullness before padding
568
569 int pn = 0; // cardinal page number
570 int userpn = 0; // page number derived from PT slugs
571
makepage()572 static void makepage()
573 {
574 page pg(pagebot - pagetop);
575 ++pn;
576 userpn = ptlist.more() ? ptlist.current()->pn() : pn;
577 pg.fill();
578 pg.print();
579 }
580
conv(FILE * fp)581 static void conv(FILE *fp)
582 {
583 startup(fp); // read slugs, etc.
584 while (anymore())
585 makepage();
586 lastrange->print(0, 0); // trailer
587 checkout(); // check that everything was printed
588 }
589
590 int
main(int argc,char ** argv)591 main(int argc, char **argv)
592 {
593 static FILE *fp = stdin;
594 setlocale(LC_CTYPE, "");
595 progname = argv[0];
596 while (argc > 1 && argv[1][0] == '-') {
597 switch (argv[1][1]) {
598 case 'd':
599 dbg = atoi(&argv[1][2]);
600 if (dbg == 0)
601 dbg = ~0;
602 break;
603 case 'm':
604 minfull = 0.01*atof(&argv[1][2]);
605 break;
606 case 'c':
607 coltol = 0.01*atof(&argv[1][2]);
608 break;
609 case 'w':
610 wantwarn = 1;
611 break;
612 }
613 argc--;
614 argv++;
615 }
616 if (argc <= 1)
617 conv(stdin);
618 else
619 while (--argc > 0) {
620 if (strcmp(*++argv, "-") == 0)
621 fp = stdin;
622 else if ((fp = fopen(*argv, "r")) == NULL)
623 FATAL("can't open %s\n", *argv);
624 conv(fp);
625 fclose(fp);
626 }
627 exit(0);
628 }
629