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