plan9port

fork of plan9port with libvec, libstr and libsdb
Log | Files | Refs | README | LICENSE

range.cc (12710B)

      1 #include	<math.h>
      2 #include	"misc.h"
      3 #include	"slug.h"
      4 #include	"range.h"
      5 
      6 void sprange::reheight(int *cv, int *mv)
      7 {
      8 	if (*cv != *mv)
      9 		ERROR "slug %d: an imbedded SP, line %d\n",
     10 			first->serialno(), first->lineno() WARNING;
     11 	*cv += dv;
     12 	*mv = max(*mv, *cv);
     13 }
     14 
     15 void sprange::rerawht(int *cv, int *mv)
     16 {
     17 	*cv += rawht();
     18 	*mv = max(*mv, *cv);
     19 }
     20 
     21 void nestrange::restore()
     22 {
     23 	subrange->restoreall();
     24 }
     25 
     26 void stream::freeall()	// not a destructor;  called explicitly
     27 {
     28 	strblk *p, *q;
     29 	for (p = first; p; p = q) {
     30 		q = p->next;
     31 		delete p;
     32 	}
     33 	first = last = curr = 0;
     34 }
     35 
     36 void stream::dump()
     37 {
     38 	for (stream s = *this; s.more(); s.advance())
     39 		s.current()->dump();
     40 }
     41 
     42 void stream::rdump()
     43 {
     44 	for (stream s = *this; s.more(); s.advance())
     45 		s.current()->rdump();
     46 }
     47 
     48 int stream::restoreall()
     49 {
     50 	for (stream s = *this; s.more(); s.advance())
     51 		s.current()->restore();
     52 	return measure(this);
     53 }
     54 
     55 range *stream::append(range *r)
     56 {
     57 	if (last == 0)
     58 		curr = first = last = new strblk;
     59 	else {
     60 		last->next = new strblk;
     61 		last = last->next;
     62 		if (curr == 0)
     63 			curr = last;
     64 	}
     65 	last->next = 0;
     66 	return last->rp = r;
     67 }
     68 
     69 void stream::split()	// duplicate current() range
     70 {
     71 	strblk *s2 = new strblk;
     72 	range *r2 = curr->rp->clone();
     73 	s2->rp = r2;
     74 	s2->next = curr->next;
     75 	if (last == curr)
     76 		last = s2;
     77 	curr->next = s2;
     78 	curr->rp->killkids();		// children only in the 2nd one
     79 	// r2->crosslink(r1);
     80 }
     81 
     82 int stream::height()
     83 {
     84 	int h;
     85 	stream s = *this;
     86 	for (h = 0; s.more(); s.advance())
     87 		h += s.current()->height();
     88 	return h;
     89 }
     90 
     91 int stream::rawht()
     92 {
     93 	int h;
     94 	stream s = *this;
     95 	for (h = 0; s.more(); s.advance())
     96 		h += s.current()->rawht();
     97 	return h;
     98 }
     99 
    100 int measure(stream *sp)		// record high-water mark of stream
    101 {				// sets nested stream heights
    102 	stream s = *sp;
    103 	int curv, maxv;
    104 	for (maxv = curv = 0; s.more(); s.advance())
    105 		s.current()->reheight(&curv, &maxv);
    106 	return maxv;
    107 }
    108 
    109 int rawmeasure(stream *sp)
    110 {
    111 	stream s = *sp;
    112 	int curv, maxv;
    113 	for (maxv = curv = 0; s.more(); s.advance())
    114 		s.current()->rerawht(&curv, &maxv);
    115 	return maxv;
    116 }
    117 
    118 void nestrange::rdump()
    119 {
    120 	dump();
    121 	if (subrange)
    122 		subrange->rdump();
    123 }
    124 
    125 void nestrange::killkids()
    126 {
    127 	subrange = new stream;
    128 }
    129 
    130 int nestrange::print(int curv, int col)
    131 {
    132 	int ocurv = curv;
    133 	first->slugout(col);
    134 	for (stream s = *subrange; s.more(); s.advance())
    135 		curv = s.current()->print(curv, col);
    136 	return ocurv + height();
    137 }
    138 
    139 #define macroclone(rangetype) range *rangetype::clone() {\
    140 	rangetype *t = new rangetype;\
    141 	*t = *this;\
    142 	return t; }
    143 
    144 macroclone(usrange);
    145 macroclone(ufrange);
    146 macroclone(bfrange);
    147 
    148 #undef macroclone
    149 
    150 #define macropickgoal(rangetype) void rangetype::pickgoal(int acv, double scale) {\
    151 	if (scale > 1) {\
    152 		goalV = (int)(scale*goalV);\
    153 		goal2 = (int)(scale*goal2);\
    154 	}\
    155 	if (abs(acv - goalV) > abs(acv-goal2))\
    156 		goalV = goal2; }
    157 
    158 macropickgoal(ufrange)
    159 macropickgoal(bfrange)
    160 
    161 #undef macropickgoal
    162 
    163 range *generator::next()
    164 {
    165 	range *r;
    166 	if (child) {
    167 		if ((r = child->next()) != 0)
    168 			return r;
    169 		delete child;
    170 		child = 0;
    171 	}
    172 	if (!s.more())
    173 		return 0;
    174 	r = s.current();
    175 	if (r->isnested())
    176 		child = new generator(r->children());
    177 	s.advance();
    178 	return r;
    179 }
    180 
    181 range *queue::enqueue(range *r)
    182 {
    183 	if (dbg & 8)
    184 		printf("#entering queue::enqueue()\n");
    185 	check("queue::enqueue");
    186 	if (!last || last->rp->serialno() < r->serialno())	// common case
    187 		return append(r);
    188 	if (dbg & 8)
    189 		printf("#queue::enqueue() pushing back\n");
    190 	newguy = new strblk;
    191 	newguy->rp = r;
    192 	if (r->serialno() < first->rp->serialno()) {
    193 		newguy->next = first;
    194 		curr = first = newguy;
    195 		return newguy->rp;
    196 	}
    197 	if (dbg & 8)
    198 		printf("#queue::enqueue() searching down queue\n");
    199 	for (curr = first;
    200 		next() && next()->serialno() < r->serialno();
    201 		curr = curr->next)
    202 		;
    203 	newguy->next = curr->next;
    204 	curr->next = newguy;
    205 	curr = first;			// restore important queue condition
    206 	return newguy->rp;
    207 }
    208 
    209 range *queue::dequeue()
    210 {
    211 	if (dbg & 8)
    212 		printf("#entering queue::dequeue()\n");
    213 	check("queue::dequeue");
    214 	curr = first->next;
    215 	range *retval = first->rp;
    216 	delete first;
    217 	first = curr;
    218 	if (!curr)
    219 		last = 0;
    220 	return retval;
    221 }
    222 
    223 // ================================================================================
    224 
    225 //	functions that munge the troff output stored in slugs[]
    226 
    227 // ================================================================================
    228 
    229 static void doprefix(FILE *fp) // copy 1st "x" commands to output
    230 {
    231 	int c;
    232 
    233 	while ((c = getc(fp)) != EOF) {
    234 		if (c != 'x') {
    235 			ungetc(c, fp);
    236 			break;
    237 		}
    238 		putchar(c);
    239 		do {
    240 			putchar(c = getc(fp));
    241 		} while (c != '\n');
    242 		linenum++;
    243 	}
    244 //	printf("x font 1 R\n");	// horrible kludge: ensure a font for first f1 command 
    245 }
    246 
    247 #define	DELTASLUGS	15000
    248 
    249 static slug	*slugs = 0;
    250 static int	nslugs = 0;	// slugs has nslugs slots
    251 static slug	*slugp = 0;	// next free slug in slugs
    252 
    253 static void readslugs(FILE *fp)
    254 {
    255 	if ((slugs = (slug *) malloc((nslugs = DELTASLUGS)*sizeof(slug))) == NULL)
    256 		ERROR "no room for %d-slug array\n", nslugs FATAL;
    257 	slugp = slugs;
    258 	for (slugp = slugs; ; slugp++) {
    259 		if (slugp >= slugs+nslugs-2) {
    260 			int where = slugp - slugs;
    261 			if ((slugs = (slug *) realloc((char *) slugs, (nslugs += DELTASLUGS)*sizeof(slug))) == NULL)
    262 				ERROR "no room for %d slugs\n", nslugs FATAL;
    263 			ERROR "now slug array can hold %d slugs\n", nslugs WARNING;
    264 			slugp = slugs + where;
    265 		}
    266 		*slugp = getslug(fp);
    267 		if (slugp->type == EOF)
    268 			break;
    269 	}
    270 	*++slugp = eofslug();
    271 	printf("# %d slugs\n", slugp-slugs);
    272 }
    273 
    274 static slug *findend(slug *sp)
    275 {
    276 	slug *p;
    277 	for (p = sp; p->type == sp->type; p++)	// skip runs
    278 		;				// espec UF UF UF 
    279 	for ( ; p < slugp; p++)
    280 		switch (p->type) {
    281 		case US:
    282 		case UF:
    283 		case BF:
    284 		case PT:
    285 		case BT:
    286 			p = findend(p);
    287 			break;
    288 		case END:
    289 			return p;
    290 		}
    291 	ERROR "walked past EOF in findend looking for %d (%s), line %d\n",
    292 		sp->type, sp->typename(), sp->lineno() FATAL;
    293 	return sp;
    294 }
    295 
    296 static int markp(int i, int n, int parm)
    297 {	// should VBOX i of n be marked to brevent breaking after it?
    298 	if (i >= n-1)
    299 		return 0;
    300 	return i <= parm-2 || i >= n-parm;
    301 }
    302 
    303 static void markbreak(slug *p)
    304 {
    305 	// Mark impermissible breakpoints in BS's.
    306 	// The parm field of a VBOX is >0 if we shouldn't break after it.
    307 	int parm = 0;		// how many lines must stay on page
    308 	int goahead = 1;	// true until we see the next BS
    309 	int nowmark = 0;	// true when we should be marking
    310 	int n = 0;
    311 	while (p->type == BS)
    312 		parm = p++->parm;	// latest BS parm applies
    313 	slug *op = p;
    314 	while (goahead) {
    315 		switch (p->type) {
    316 		case VBOX:		// count VBOXes so second pass knows
    317 			if (p->dv > 0)	// knows how far to end of BS
    318 				n++;
    319 			break;
    320 		case US:		// mark around EQ/EN, etc.
    321 			nowmark = 1;
    322 			p = findend(p);
    323 			break;
    324 		case UF:		// but not around floats, PTs, and BTs
    325 		case BF:
    326 		case PT:
    327 		case BT:
    328 			p = findend(p);
    329 			break;
    330 		case SP:		// naked SP:  probable macro botch
    331 			nowmark = 1;	// mark around it anyhow
    332 			break;
    333 		case BS:		// beginning of next paragraph
    334 		case END:		// probable macro botch
    335 		case EOF:
    336 			goahead = 0;	// stop work after marking
    337 			nowmark = 1;
    338 		default:
    339 			break;
    340 		}
    341 		p++;
    342 		if (nowmark) {
    343 			int i = 0;	// VBOX counter for second pass
    344 			while (op < p) {
    345 				switch (op->type) {
    346 				case VBOX:
    347 					if (op->dv > 0)
    348 						op->parm = markp(i, n, parm);
    349 					i++;
    350 					break;
    351 				case US:	// caused second pass to begin
    352 				case SP:
    353 				case BS:
    354 				case END:
    355 				case EOF:
    356 					op = p;
    357 					break;
    358 				case UF:	// skip on this pass too
    359 				case BF:
    360 				case PT:
    361 				case BT:
    362 					op = findend(op);
    363 					break;
    364 				default:
    365 					break;
    366 				}
    367 			op++;
    368 			}
    369 			if (i != n)
    370 				ERROR "markbreak failed : i %d n %d\n",
    371 					i, n WARNING;
    372 			op = p;
    373 			nowmark = n = 0;
    374 		}
    375 	}
    376 }
    377 
    378 static void fixslugs()		// adjust bases and dv's, set parameters, etc.
    379 {
    380 	slug *p, *prevV = 0;
    381 	for (p = slugs; p < slugp; p++) {
    382 		if (p->type == VBOX) {
    383 			prevV = p;
    384 			continue;
    385 		}
    386 		if (p->base != 0) {
    387 			ERROR "%s slug (type %d) has base = %d, line %d\n",
    388 				p->typename(), p->type, p->base, p->lineno() WARNING;
    389 		}
    390 		if ((p->type == SP) || (p->type == NE))
    391 			continue;
    392 		if (p->type == PAGE)
    393 			prevV = 0;
    394 		if (p->dv != 0)
    395 			if (prevV) {
    396 				prevV->base = max(prevV->base, p->dv);
    397 				p->dv = 0;
    398 			} else {
    399 				ERROR "%s slug (type %d) has dv = %d, line %d\n",
    400 					p->typename(), p->type, p->dv, p->lineno() WARNING;
    401 			}
    402 	}
    403 	prevV = 0;
    404 	int firstNP = 0, firstFO = 0, firstPL = 0;
    405 	for (p = slugs; p < slugp; p++) {
    406 		switch (p->type) {
    407 		// adjust the dv in a sequence of VBOXes
    408 		// by subtracting from each the base of the preceding VBOX
    409 		case VBOX:
    410 			if (prevV)
    411 				p->dv -= prevV->base;
    412 			prevV = p;
    413 			break;
    414 		case SP:
    415 			p->dv = max(p->dv, 0);
    416 			break;
    417 		case PAGE:
    418 			p->neutralize();
    419 			prevV = 0;
    420 			break;
    421 		// record only first "declarations" of Page Top and bottom (FO);
    422 		case PARM:
    423 			switch (p->parm) {
    424 			case NP:
    425 				if (firstNP++ == 0)
    426 					pagetop = p->parm2;
    427 				p->neutralize();
    428 				break;
    429 			case FO:
    430 				if (firstFO++ == 0)
    431 					pagebot = p->parm2;
    432 				p->neutralize();
    433 				break;
    434 			case PL:
    435 				if (firstPL++ == 0)
    436 					physbot = p->parm2;
    437 				p->neutralize();
    438 				break;
    439 			}
    440 			break;
    441 		// things that begin groups; not US, which should nest properly
    442 		case UF:
    443 		case BF:
    444 			while ((p+1)->type == p->type) {
    445 							// join adjacent identical
    446 				(p+1)->parm2 = p->parm;	// parm is latest
    447 							// parm2 is previous
    448 				p->neutralize();	// so it's not seen later
    449 				p++;
    450 			}
    451 			break;
    452 		// none of the above
    453 		case US:
    454 		case PT:
    455 		case BT:
    456 		case BS:
    457 		case END:
    458 		case TM:
    459 		case COORD:
    460 		case NE:
    461 		case MC:
    462 		case CMD:
    463 		case EOF:
    464 			break;
    465 		default:
    466 			ERROR "Unknown slug type %d in fixslugs, line %d\n",
    467 				p->type, p->lineno() WARNING;
    468 			break;
    469 		}
    470 	}
    471 	int pagesize = pagebot - pagetop;
    472 	if (pagesize == 0)
    473 		ERROR "Page dimensions not declared\n" FATAL;
    474 	if (physbot == 0)
    475 		physbot = pagebot + pagetop;
    476 	printf("# page top %d bot %d size %d physbot %d\n",
    477 		pagetop, pagebot, pagesize, physbot);
    478 	for (p = slugs; p < slugp; p++) {
    479 		switch (p->type) {
    480 		// normalize float parameters
    481 		case BF:
    482 		case UF:
    483 					// primary goal
    484 			p->parm = max(min(p->parm-pagetop, pagesize), 0);
    485 					// secondary goal
    486 			p->parm2 = max(min(p->parm2-pagetop, pagesize), 0);
    487 			break;
    488 		// normalize need parameters
    489 		case NE:
    490 			p->dv = max( min(p->dv, pagesize), 0);
    491 			break;
    492 		// mark permissible breaks
    493 		case BS:
    494 			markbreak(p);
    495 			break;
    496 		}
    497 		if (dbg & 1)
    498 			p->dump();
    499 	}
    500 }
    501 
    502 void checkout()
    503 {
    504 	for (slug *p = slugs; p < slugp; p++)
    505 		switch (p->type) {
    506 		case PT:
    507 		case BT:
    508 			p = findend(p);
    509 			break;
    510 		case SP:
    511 		case VBOX:
    512 			if (p->seen != 1)
    513 				ERROR "%s slug %d seen %d times\n",
    514 					p->typename(), p->serialno(),
    515 					p->seen WARNING;
    516 			break;
    517 		}
    518 }
    519 
    520 eofrange *lastrange;
    521 stream	ptlist, btlist;
    522 
    523 static slug *makeranges(slug *p, stream *s, int level)
    524 {
    525 	stream *t;
    526 
    527 	for ( ; p < slugp; p++)
    528 		switch (p->type) {
    529 		case VBOX:
    530 			s->append(new vboxrange(p));
    531 			break;
    532 		case SP:
    533 			s->append(new sprange(p));
    534 			break;
    535 		case BS:
    536 			s->append(new bsrange(p));
    537 			break;
    538 		case US:
    539 			s->append(new usrange(p, t = new stream));
    540 			p = makeranges(p+1, t, level+1);
    541 			break;
    542 		case BF:
    543 			s->append(new bfrange(p, t = new stream));
    544 			p = makeranges(p+1, t, level+1);
    545 			break;
    546 		case UF:
    547 			s->append(new ufrange(p, t = new stream));
    548 			p = makeranges(p+1, t, level+1);
    549 			break;
    550 		case PT:
    551 			ptlist.append(new ptrange(p, t = new stream));
    552 			p = makeranges(p+1, t, level+1);
    553 			break;
    554 		case BT:
    555 			btlist.append(new btrange(p, t = new stream));
    556 			p = makeranges(p+1, t, level+1);
    557 			break;
    558 		case END:
    559 			s->append(new endrange(p));
    560 			return p;
    561 		case TM:
    562 			s->append(new tmrange(p));
    563 			break;
    564 		case COORD:
    565 			s->append(new coordrange(p));
    566 			break;
    567 		case NE:
    568 			if (level) {
    569 				ERROR "Nested NE commands are ignored, line %d\n",
    570 					p->lineno() WARNING;
    571 				p->dv = 0;
    572 			}
    573 			s->append(new nerange(p));
    574 			break;
    575 		case MC:
    576 			s->append(new mcrange(p));
    577 			break;
    578 		case CMD:
    579 			if (level)
    580 				ERROR "Nested command ignored, line %d\n",
    581 					p->lineno() WARNING;
    582 			s->append(new cmdrange(p));
    583 			break;
    584 		case PARM:
    585 			if (level)
    586 				ERROR "Nested parameter ignored, line %d\n",
    587 					p->lineno() WARNING;
    588 			s->append(new parmrange(p));
    589 			break;
    590 		case EOF:
    591 			lastrange = new eofrange(p);
    592 			return 0;
    593 		}
    594 	return p;
    595 }
    596 
    597 static queue text;			// unexamined input ranges; the real data
    598 
    599 void startup(FILE *fp)
    600 {
    601 	doprefix(fp);			// peel off 'x' commands
    602 	readslugs(fp);			// read everything into slugs[]
    603 	fixslugs();			// measure parameters and clean up
    604 	makeranges(slugs, &text, 0);	// add range superstructure
    605 	measure(&text);		// heights of nested things
    606 	rawmeasure(&text);
    607 	while (text.more()) {
    608 		range *r = text.dequeue();
    609 		if (dbg & 2)
    610 			r->dump();
    611 		r->enqueue();
    612 	}
    613 }