trange.cc - plan9port - [fork] Plan 9 from user space
HTML git clone git://src.adamsgaard.dk/plan9port
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
trange.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 }