1 files changed, 612 insertions, 0 deletions

diff --git a/src/cmd/mpm/page.cc b/src/cmd/mpm/page.cc
new file mode 100644
index 00000000..966edae9
--- /dev/null
+++ b/src/cmd/mpm/page.cc
@@ -0,0 +1,612 @@
+#include	"misc.h"
+#include	"slug.h"
+#include	"range.h"
+#include	"page.h"
+
+const int	MAXRANGES	= 1000;
+static range *ptemp[MAXRANGES];		// for movefloats()
+
+static void swapright(int n)		// used by movefloats()
+{
+	range *t = ptemp[n];
+	ptemp[n] = ptemp[n+1];
+	ptemp[n+1] = t;
+	ptemp[n]->setaccum( ptemp[n+1]->accum() -
+			    ptemp[n+1]->rawht() + ptemp[n]->rawht() );
+	ptemp[n+1]->setaccum( ptemp[n]->accum() + ptemp[n+1]->rawht() );
+}
+
+// Figure out the goal position for each floating range on scratch,
+// and move it past stream ranges until it's as close to its goal as possible.
+static void movefloats(stream *scratch, double scale)
+{
+	int nranges, i;
+	const int Huge = 100000;
+
+	for (nranges = 0; scratch->more(); scratch->advance())
+		ptemp[nranges++] = scratch->current();
+	scratch->freeall();
+	ufrange rtemp;
+	ptemp[nranges] = &rtemp;
+	rtemp.setgoal(Huge);
+	int accumV = 0;				// compute accum values and
+	for (i = 0; i < nranges; i++) {		// pick closest goal for floats
+		ptemp[i]->pickgoal(accumV, scale);
+		ptemp[i]->setaccum(accumV += ptemp[i]->rawht());
+	}
+	int j;					// index for inner loop below:
+	for (i = nranges; --i >= 0; )		// stably sort floats to bottom
+		for (j = i; j < nranges; j++)
+			if (ptemp[j]->goal() > ptemp[j+1]->goal())
+				swapright(j);
+			else
+				break;
+	if (dbg & 16)
+		printf("#movefloats:  before floating, from bottom:\n");
+	for (i = nranges; --i >= 0; ) {		// find topmost float
+		if (ptemp[i]->goal() == NOGOAL)
+			break;
+		if (dbg & 16)
+			printf("# serialno %d goal %d height %d\n",
+				ptemp[i]->serialno(), ptemp[i]->goal(),
+				ptemp[i]->rawht());
+	}					// i+1 is topmost float
+	for (i++ ; i < nranges; i++)		// move each float up the page
+		for (j = i; j > 0; j--)		// as long as closer to its goal
+			if (ptemp[j]->goal()
+			  <= ptemp[j-1]->accum() + ptemp[j]->rawht()/2
+			  && ptemp[j-1]->goal() == NOGOAL)
+				swapright(j-1);
+			else
+				break;
+	if (ptemp[nranges] != &rtemp)
+		ERROR "goal sentinel has disappeared from movefloats" FATAL;
+	for (i = 0; i < nranges; i++)		// copy sorted list back
+		scratch->append(ptemp[i]);
+}
+
+// Traverse the leaves of a tree of ranges, filtering out only SP and VBOX.
+static range *filter(generator *g)
+{
+	range *r;
+	while ((r = g->next()) != 0)
+		if (r->isvbox() || r->issp())
+			break;
+	return r;
+}
+
+// Zero out leading and trailing spaces; coalesce adjacent SP's.
+static void trimspace(stream *scratch)
+{
+	generator g;
+	range *r, *prevr = 0;
+
+	for (g = scratch; (r = filter(&g)) != 0 && r->issp(); prevr = r)
+		r->setheight(0);		// zap leading SP
+	for ( ; (r = filter(&g)) != 0; prevr = r)
+		if (r->issp())
+			if (prevr && prevr->issp()) {
+						// coalesce adjacent SPs
+				r->setheight(max(r->rawht(), prevr->height()));
+				prevr->setheight(0);
+			} else			// a VBOX intervened
+				r->setheight(r->rawht());
+	if (prevr && prevr->issp())		// zap *all* trailing space
+		prevr->setheight(0);		// (since it all coalesced
+						// into the last one)
+}
+
+// Pad the non-zero SP's in scratch so the total height is wantht.
+// Note that the SP values in scratch are not the raw values, and
+// indeed may already have been padded.
+static void justify(stream *scratch, int wantht)
+{
+	range *r;
+	int nsp = 0, hsp = 0;
+
+	int adjht = scratch->height();
+					// Find all the spaces.
+	generator g;
+	for (g = scratch; (r = g.next()) != 0; )
+		if (r->issp() && r->height() > 0) {
+			nsp++;
+			hsp += r->height();
+		}
+	int excess = wantht - adjht;
+	if (excess < 0)
+		ERROR "something on page %d is oversize by %d\n",
+			userpn, -excess WARNING;
+	if (dbg & 16)
+		printf("# justify %d: excess %d nsp %d hsp %d adjht %d\n",
+			userpn, excess, nsp, hsp, adjht);
+	if (excess <= 0 || nsp == 0)
+		return;
+					// Redistribute the excess space.
+	for (g = scratch; (r = g.next()) != 0; )
+		if (r->issp() && r->height() > 0) {
+			int delta = (int) ((float)(r->height()*excess)/hsp + 0.5);
+			if (dbg & 16)
+				printf("# pad space %d by %d: hsp %d excess %d\n",
+					r->height(), delta, hsp, excess);
+			r->setheight(r->height() + delta);
+		}
+}
+
+// If r were added to s, would the height of the composed result be at most maxht?
+int wouldfit(range *r, stream *s, int maxht)
+{
+	if (r->rawht() + s->rawht() <= maxht)
+		return 1;		// the conservative test succeeded
+	stream scratch;			// local playground for costly test
+	for (stream cd = *s; cd.more(); cd.advance())
+		scratch.append(cd.current());
+	scratch.append(r);
+	movefloats(&scratch, ((double) scratch.rawht())/maxht);
+	trimspace(&scratch);
+	int retval = scratch.height() <= maxht;
+	scratch.freeall();
+	return retval;
+}
+
+// If s1 were added to s, would the height of the composed result be at most maxht?
+// The computational structure is similar to that above.
+int wouldfit(stream *s1, stream *s, int maxht)
+{
+	if (s1->rawht() + s->rawht() <= maxht)
+		return 1;
+	stream scratch, cd;
+	for (cd = *s; cd.more(); cd.advance())
+		scratch.append(cd.current());
+	for (cd = *s1; cd.more(); cd.advance())
+		scratch.append(cd.current());
+	movefloats(&scratch, ((double) scratch.rawht())/maxht);
+	trimspace(&scratch);
+	int retval = scratch.height() <= maxht;
+	scratch.freeall();
+	return retval;
+}
+
+// All of stream *s is destined for one column or the other; which is it to be?
+void multicol::choosecol(stream *s, int goalht)
+{
+	stream *dest;
+	if (!leftblocked && wouldfit(s, &(column[0]), goalht))
+		dest = &(column[0]);
+	else {
+		dest = &(column[1]);
+		if (!s->current()->floatable())
+					// a stream item is going into the right
+					// column, so no more can go into the left.
+			leftblocked = 1;
+	}
+	for (stream cd = *s; cd.more(); cd.advance())
+		dest->append(cd.current());
+}
+
+double coltol = 0.5;
+
+// Try, very hard, to put everything in the multicol into two columns
+// so that the total height is at most htavail.
+void multicol::compose(int defonly)
+{
+	if (!nonempty()) {
+		setheight(0);
+		return;
+	}
+	scratch.freeall();	// fill scratch with everything destined
+				// for either column
+	stream cd;
+	for (cd = definite; cd.more(); cd.advance())
+		scratch.append(cd.current());
+	if (!defonly)
+		for (cd = *(currpage->stage); cd.more(); cd.advance())
+			if (cd.current()->numcol() == 2)
+				scratch.append(cd.current());
+	scratch.restoreall();		// in particular, floatables' goals
+	int i;
+	int rawht = scratch.rawht();
+	int halfheight = (int)(coltol*rawht);
+					// choose a goal height
+	int maxht = defonly ? halfheight : htavail;
+secondtry:
+	for (i = 0; i < 2; i++)
+		column[i].freeall();
+	leftblocked = 0;
+	cd = scratch;
+	while (cd.more()) {
+		queue ministage;	// for the minimally acceptable chunks
+		ministage.freeall();	// that are to be added to either column
+		while (cd.more() && !cd.current()->issentinel()) {
+			ministage.enqueue(cd.current());
+			cd.advance();
+		}
+		choosecol(&ministage, maxht);
+		if (cd.more() && cd.current()->issentinel())
+			cd.advance();	// past sentinel
+	}
+	if (height() > htavail && maxht != htavail) {
+					// We tried to balance the columns, but
+					// the result was too tall.  Go back
+					// and try again with the less ambitious
+					// goal of fitting the space available.
+		maxht = htavail;
+		goto secondtry;
+	}
+	for (i = 0; i < 2; i++) {
+		movefloats(&(column[i]), ((double) column[i].rawht())/currpage->pagesize);
+		trimspace(&(column[i]));
+	}
+	if (dbg & 32) {
+		printf("#multicol::compose: htavail %d maxht %d dv %d\n",
+			htavail, maxht, height());
+		dump();
+	}
+	if (defonly)
+		stretch(height());
+}
+
+// A sequence of two-column ranges waits on the stage.
+// So long as the page's skeleton hasn't changed--that is, the maximum height
+// available to the two-column chunk is the same--we just use the columns that
+// have been built up so far, and choose a column into which to put the stage.
+// If the skeleton has changed, however, then we may need to make entirely
+// new decisions about which column gets what, so we recompose the whole page.
+void multicol::tryout()
+{
+	if (htavail == prevhtavail)
+		choosecol(currpage->stage, htavail);
+	else
+		currpage->compose(DRAFT);
+	prevhtavail = htavail;
+}
+
+// Make both columns the same height.
+// (Maybe this should also be governed by minfull,
+// to prevent padding very underfull columns.)
+void multicol::stretch(int wantht)
+{
+	if (wantht < height())
+		ERROR "page %d: two-column chunk cannot shrink\n", userpn FATAL;
+	for (int i = 0; i < 2; i++)
+		justify(&(column[i]), wantht);
+	if (dbg & 16)
+		printf("#col hts: left %d right %d\n",
+			column[0].height(), column[1].height());
+}
+
+// Report an upper bound on how tall the current two-column object is.
+// The (possibly composed) heights of the two columns give a crude upper
+// bound on the total height.  If the result is more than the height
+// available for the two-column object, then the columns are each
+// composed to give a better estimate of their heights.
+int multicol::height()
+{
+	int retval = max(column[0].height(), column[1].height());
+	if (retval < htavail)
+		return retval;
+	for (int i = 0; i < 2; i++) {
+		movefloats(&(column[i]), ((double) column[i].height())/currpage->pagesize);
+		trimspace(&(column[i]));
+	}
+	return max(column[0].height(), column[1].height());
+}
+
+void multicol::dump()
+{
+	printf("####2COL dv %d\n", height());
+	printf("# left column:\n");
+	column[0].dump();
+	printf("# right column:\n");
+	column[1].dump();
+}
+
+// From the head of queue qp, peel off a piece whose raw height is at most space.
+int peeloff(stream *qp, int space)
+{
+	stream *s1 = qp->current()->children();
+	if (!(s1 && s1->more() && s1->current()->height() <= space))
+					// in other words, either qp's head is
+					// not nested, or its first subrange
+		return 0;		// is also too big, so we give up
+	qp->split();
+	s1 = qp->current()->children();
+	stream *s2 = qp->next()->children();
+	while (s2->more() && s2->current()->rawht() <= space) {
+		s1->append(s2->current());
+		space -= s2->current()->rawht();
+		s2->advance();
+	}
+	return 1;
+}
+
+// There are four possibilities for consecutive calls to tryout().
+// If we're processing a sequence of single-column ranges, tryout()
+// uses the original algorithm: (1) conservative test; (2) costly test;
+// (3) split a breakable item.
+// If we're processing a sequence of double-column ranges, tryout()
+// defers to twocol->tryout(), which gradually builds up the contents
+// of the two columns until they're as tall as they can be without
+// exceeding twocol->htavail.
+// If we're processing a sequence of single-column ranges and we
+// get a double-column range, then we use compose() to build a
+// skeleton page and set twocol->htavail, the maximum height that
+// should be occupied by twocol.
+// If we're processing a sequence of double-column ranges and we
+// get a single-column range, then we should go back and squish
+// the double-column chunk as short as possible before we see if
+// we can fit the single-column range.
+void page::tryout()
+{
+	if (!stage->more())
+		ERROR "empty stage in page::tryout()\n" FATAL;
+	int curnumcol = stage->current()->numcol();
+	if (dbg & 32) {
+		printf("#page::tryout(): ncol = %d, prevncol = %d; on stage:\n",
+			curnumcol, prevncol);
+		stage->dump();
+		printf("#END of stage contents\n");
+	}
+	switch(curnumcol) {
+	default:
+		ERROR "unexpected number of columns in tryout(): %d\n",
+			stage->current()->numcol() FATAL;
+		break;
+	case 1:
+		if (prevncol == 2)
+			compose(FINAL);
+		if (wouldfit(stage, &definite, pagesize - twocol->height()))
+			commit();
+		else if (stage->current()->breakable() || blank()
+			&& peeloff(stage,
+				pagesize - (definite.height() + twocol->height()))) {
+			// first add the peeled-off part that fits
+			adddef(stage->dequeue());
+			// then send the rest back for later
+			stage->current()->setbreaking();
+			welsh();
+		} else if (blank()) {
+			stage->current()->rdump();
+			ERROR "A %s is too big to continue.\n",
+			stage->current()->typename() FATAL;
+		} else
+			welsh();
+		break;
+	case 2:
+		if (prevncol == 1)
+			compose(DRAFT);
+		else
+			twocol->tryout();
+		if (scratch.height() <= pagesize)
+			commit();
+		else
+			welsh();
+		break;
+	}
+	prevncol = curnumcol;
+}
+
+// To compose the page, we (1) fill scratch with the stuff that's meant to
+// go on the page; (2) compose scratch as best we can; (3) set the maximum
+// height available to the two-column part of the page; (4) have the two-
+// column part compose itself.
+// In the computation of twocol->htavail, it does not matter that
+// twocol->height() is merely an upper bound, because it is merely being
+// subtracted out to give the exact total height of the single-column stuff.
+void page::compose(int final)
+{
+	makescratch(final);
+	int adjht = scratch.rawht();
+	if (dbg & 16)
+		printf("# page %d measure %d\n", userpn, adjht);
+	movefloats(&scratch, ((double) adjht)/pagesize);
+	trimspace(&scratch);
+	twocol->htavail = pagesize - (scratch.height() - twocol->height());
+	twocol->compose(final);
+	adjht = scratch.height();
+	if (dbg & 16)
+		printf("# page %d measure %d after trim\n", userpn, adjht);
+}
+
+// Fill the scratch area with ranges destined for the page.
+// If defonly == 0, then add anything that's on stage--this is a trial run.
+// If defonly != 0, use only what's definitely on the page.
+void page::makescratch(int defonly)
+{
+	scratch.freeall();
+	stream cd;
+	for (cd = definite; cd.more(); cd.advance())
+		scratch.append(cd.current());
+	if (!defonly)
+		for (cd = *stage; cd.more(); cd.advance())
+			if (cd.current()->numcol() == 1)
+				scratch.append(cd.current());
+	if (twocol->nonempty())
+		scratch.append(twocol);
+}
+
+// Accept the current contents of the stage.
+// If the stage contains two-column ranges, add a sentinel to indicate the end
+// of a chunk of stage contents.
+void page::commit()
+{
+	if (dbg & 4)
+		printf("#entering page::commit()\n");
+	int numcol = 0;
+	while (stage->more()) {
+		numcol = stage->current()->numcol();
+		adddef(stage->dequeue());
+	}
+	if (numcol == 2)
+		adddef(new sentrange);
+}
+
+// Send the current contents of the stage back to its source.
+void page::welsh()
+{
+	if (dbg & 4)
+		printf("#entering page::welsh()\n");
+	while (stage->more()) {
+		range *r = stage->dequeue();
+		r->enqueue(ANDBLOCK);
+	}
+}
+
+enum { USonly = 1 };
+
+// So long as anything is eligible to go onto the page, keep trying.
+// Once nothing is eligible, compose and justify the page.
+void page::fill()
+{
+	while (stage->prime())
+		stage->pend();
+	compose(FINAL);
+	if (dbg & 16)
+		scratch.dump();
+	if (anymore()) {
+		int adjht = scratch.height();
+		if (adjht > minfull*pagesize) {
+			justify(&scratch, pagesize);
+			adjht = scratch.height();
+			int stretchamt = max(pagesize - adjht, 0);
+			twocol->stretch(twocol->height() + stretchamt);
+					// in case the page's stretchability lies
+					// entirely in its two-column part
+		} else
+			ERROR "page %d only %.0f%% full; will not be adjusted\n",
+				userpn, 100*(double) adjht/pagesize WARNING;
+	}
+}
+
+void page::adddef(range *r)
+{
+	if (dbg & 4)
+		printf("#entering page::adddef()\n");
+	switch (r->numcol()) {
+	case 1:	definite.append(r);
+		break;
+	case 2: twocol->definite.append(r);
+		break;
+	default: ERROR "%d-column range unexpected\n", r->numcol() FATAL;
+	}
+}
+
+int multicol::print(int cv, int col)
+{
+	if (col != 0)
+		ERROR "multicolumn output must start in left column\n" FATAL;
+	int curv = cv, maxv = cv;	// print left column
+	for ( ; column[0].more(); column[0].advance()) {
+		curv = column[0].current()->print(curv, 0);
+		maxv = max(maxv, curv);
+	}
+	curv = cv;			// print right column
+	for ( ; column[1].more(); column[1].advance()) {
+		curv = column[1].current()->print(curv, 1);
+		maxv = max(maxv, curv);
+	}
+	return maxv;
+}
+
+void page::print()
+{
+	static int tops = 1, bots = 1;
+	if (!scratch.more()) {
+		ERROR "## Here's what's left on squeue:\n" WARNING;
+		squeue.dump();
+		ERROR "## Here's what's left on bfqueue:\n" WARNING;
+		bfqueue.dump();
+		ERROR "## Here's what's left on ufqueue:\n" WARNING;
+		ufqueue.dump();
+		ERROR "page %d appears to be empty\n", userpn WARNING;
+		fflush(stderr), fflush(stdout), exit(0);
+					// something is very wrong if this happens
+	}
+	printf("p%d\n", userpn);	// print troff output page number
+	if (ptlist.more()) {		// print page header
+		ptlist.current()->print(0, 0);
+		ptlist.advance();
+	} else if (tops) {
+		ERROR "ran out of page titles at %d\n", userpn WARNING;
+		tops = 0;
+	}
+	int curv = 0;
+	printf("V%d\n", curv = pagetop);// print page contents
+	for ( ; scratch.more(); scratch.advance()) {
+		curv = scratch.current()->print(curv, 0);
+	}
+	if (btlist.more()) {		// print page footer
+		btlist.current()->print(0, 0);
+		btlist.advance();
+	} else if (bots) {
+		ERROR "ran out of page bottoms at %d\n", userpn WARNING;
+		bots = 0;
+	}
+	printf("V%d\n", physbot);	// finish troff output page
+}
+
+int	pagetop	= 0;		// top printing margin
+int	pagebot = 0;		// bottom printing margin
+int	physbot = 0;		// physical bottom of page
+
+double minfull = 0.9;		// minimum fullness before padding
+
+int	pn	= 0;		// cardinal page number
+int	userpn	= 0;		// page number derived from PT slugs
+
+static void makepage()
+{
+	page pg(pagebot - pagetop);
+	++pn;
+	userpn = ptlist.more() ? ptlist.current()->pn() : pn;
+	pg.fill();
+	pg.print();
+}
+
+static void conv(FILE *fp)
+{
+	startup(fp);		// read slugs, etc.
+	while (anymore())
+		makepage();
+	lastrange->print(0, 0);	// trailer
+	checkout();		// check that everything was printed
+}
+
+int
+main(int argc, char **argv)
+{
+	static FILE *fp = stdin;
+	progname = argv[0];
+	while (argc > 1 && argv[1][0] == '-') {
+		switch (argv[1][1]) {
+		case 'd':
+			dbg = atoi(&argv[1][2]);
+			if (dbg == 0)
+				dbg = ~0;
+			break;
+		case 'm':
+			minfull = 0.01*atof(&argv[1][2]);
+			break;
+		case 'c':
+			coltol = 0.01*atof(&argv[1][2]);
+			break;
+		case 'w':
+			wantwarn = 1;
+			break;
+		}
+		argc--;
+		argv++;
+	}
+	if (argc <= 1)
+		conv(stdin);
+	else
+		while (--argc > 0) {
+			if (strcmp(*++argv, "-") == 0)
+				fp = stdin;
+			else if ((fp = fopen(*argv, "r")) == NULL)
+				ERROR "can't open %s\n", *argv FATAL;
+			conv(fp);
+			fclose(fp);
+		}
+	exit(0);
+	return 0;	/* gcc */
+}