fmt.c

   1 /*
   2  * line formatting buffer for line adjustment and hyphenation
   3  *
   4  * The line formatting buffer does two main functions: breaking
   5  * words into lines (possibly after breaking them at their
   6  * hyphenation points), and, if requested, adjusting the space
   7  * between words in a line.  In this file the first step is
   8  * referred to as filling.
   9  *
  10  * Functions like fmt_word() return nonzero on failure, which
  11  * means the call should be repeated after fetching previously
  12  * formatted lines via fmt_nextline().
  13  */
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <string.h>
  17 #include "roff.h"
  18
  19 #define FMT_LLEN(f)     MAX(0, (f)->ll - (f)->li)
  20 #define FMT_FILL(f)     (!n_ce && n_u)
  21 #define FMT_ADJ(f)      (n_u && !n_na && !n_ce && (n_j & AD_B) == AD_B)
  22
  23 struct word {
  24         char *s;
  25         int wid;        /* word's width */
  26         int elsn, elsp; /* els_neg and els_pos */
  27         int gap;        /* the space before this word */
  28         int hy;         /* hyphen width if inserted after this word */
  29         int str;        /* does the space before it stretch */
  30 };
  31
  32 struct line {
  33         struct sbuf sbuf;
  34         int wid, li, ll;
  35         int elsn, elsp;
  36 };
  37
  38 struct fmt {
  39         /* queued words */
  40         struct word words[NWORDS];
  41         int nwords;
  42         /* queued lines */
  43         struct line lines[NLINES];
  44         int l_head, l_tail;
  45         /* for paragraph adjustment */
  46         long best[NWORDS];
  47         int best_pos[NWORDS];
  48         int best_dep[NWORDS];
  49         /* current line */
  50         int gap;                /* space before the next word */
  51         int nls;                /* newlines before the next word */
  52         int nls_sup;            /* suppressed newlines */
  53         int li, ll;             /* current line indentation and length */
  54         int filled;             /* filled all words in the last fmt_fill() */
  55         int eos;                /* last word ends a sentence */
  56         int fillreq;            /* fill after the last word (\p) */
  57 };
  58
  59 /* .ll, .in and .ti are delayed until the partial line is output */
  60 static void fmt_confupdate(struct fmt *f)
  61 {
  62         f->ll = n_l;
  63         f->li = n_ti >= 0 ? n_ti : n_i;
  64         n_ti = -1;
  65 }
  66
  67 static int fmt_confchanged(struct fmt *f)
  68 {
  69         return f->ll != n_l || f->li != (n_ti >= 0 ? n_ti : n_i);
  70 }
  71
  72 /* move words inside an fmt struct */
  73 static void fmt_movewords(struct fmt *a, int dst, int src, int len)
  74 {
  75         memmove(a->words + dst, a->words + src, len * sizeof(a->words[0]));
  76 }
  77
  78 /* move words from the buffer to s */
  79 static int fmt_wordscopy(struct fmt *f, int beg, int end,
  80                 struct sbuf *s, int *els_neg, int *els_pos)
  81 {
  82         struct word *wcur;
  83         int w = 0;
  84         int i;
  85         *els_neg = 0;
  86         *els_pos = 0;
  87         for (i = beg; i < end; i++) {
  88                 wcur = &f->words[i];
  89                 sbuf_printf(s, "%ch'%du'", c_ec, wcur->gap);
  90                 sbuf_append(s, wcur->s);
  91                 w += wcur->wid + wcur->gap;
  92                 if (wcur->elsn < *els_neg)
  93                         *els_neg = wcur->elsn;
  94                 if (wcur->elsp > *els_pos)
  95                         *els_pos = wcur->elsp;
  96                 free(wcur->s);
  97         }
  98         if (beg < end) {
  99                 wcur = &f->words[end - 1];
 100                 if (wcur->hy)
 101                         sbuf_append(s, "\\(hy");
 102                 w += wcur->hy;
 103         }
 104         return w;
 105 }
 106
 107 static int fmt_nlines(struct fmt *f)
 108 {
 109         if (f->l_tail <= f->l_head)
 110                 return f->l_head - f->l_tail;
 111         return NLINES - f->l_tail + f->l_head;
 112 }
 113
 114 /* the total width of the specified words in f->words[] */
 115 static int fmt_wordslen(struct fmt *f, int beg, int end)
 116 {
 117         int i, w = 0;
 118         for (i = beg; i < end; i++)
 119                 w += f->words[i].wid + f->words[i].gap;
 120         return beg < end ? w + f->words[end - 1].hy : 0;
 121 }
 122
 123 /* the number of stretchable spaces in f */
 124 static int fmt_spaces(struct fmt *f, int beg, int end)
 125 {
 126         int i, n = 0;
 127         for (i = beg + 1; i < end; i++)
 128                 if (f->words[i].str)
 129                         n++;
 130         return n;
 131 }
 132
 133 /* the amount of stretchable spaces in f */
 134 static int fmt_spacessum(struct fmt *f, int beg, int end)
 135 {
 136         int i, n = 0;
 137         for (i = beg + 1; i < end; i++)
 138                 if (f->words[i].str)
 139                         n += f->words[i].gap;
 140         return n;
 141 }
 142
 143 /* return the next line in the buffer */
 144 int fmt_nextline(struct fmt *f, struct sbuf *sbuf, int *w,
 145                 int *li, int *ll, int *els_neg, int *els_pos)
 146 {
 147         struct line *l;
 148         l = &f->lines[f->l_tail];
 149         if (f->l_head == f->l_tail)
 150                 return 1;
 151         *li = l->li;
 152         *ll = l->ll;
 153         *w = l->wid;
 154         *els_neg = l->elsn;
 155         *els_pos = l->elsp;
 156         sbuf_append(sbuf, sbuf_buf(&l->sbuf));
 157         sbuf_done(&l->sbuf);
 158         f->l_tail = (f->l_tail + 1) % NLINES;
 159         return 0;
 160 }
 161
 162 static struct line *fmt_mkline(struct fmt *f)
 163 {
 164         struct line *l = &f->lines[f->l_head];
 165         if ((f->l_head + 1) % NLINES == f->l_tail)
 166                 return NULL;
 167         f->l_head = (f->l_head + 1) % NLINES;
 168         l->li = f->li;
 169         l->ll = f->ll;
 170         sbuf_init(&l->sbuf);
 171         return l;
 172 }
 173
 174 static int fmt_sp(struct fmt *f)
 175 {
 176         struct line *l;
 177         if (fmt_fill(f))
 178                 return 1;
 179         l = fmt_mkline(f);
 180         if (!l)
 181                 return 1;
 182         f->filled = 0;
 183         f->nls--;
 184         f->nls_sup = 0;
 185         l->wid = fmt_wordscopy(f, 0, f->nwords, &l->sbuf, &l->elsn, &l->elsp);
 186         f->nwords = 0;
 187         f->fillreq = 0;
 188         return 0;
 189 }
 190
 191 int fmt_br(struct fmt *f)
 192 {
 193         if (fmt_fill(f))
 194                 return 1;
 195         f->filled = 0;
 196         if (f->nwords)
 197                 fmt_sp(f);
 198         return 0;
 199 }
 200
 201 void fmt_space(struct fmt *fmt)
 202 {
 203         fmt->gap += N_SS(n_f, n_s);
 204 }
 205
 206 int fmt_newline(struct fmt *f)
 207 {
 208         f->gap = 0;
 209         if (!FMT_FILL(f)) {
 210                 f->nls++;
 211                 fmt_sp(f);
 212                 return 0;
 213         }
 214         if (f->nls >= 1)
 215                 if (fmt_sp(f))
 216                         return 1;
 217         if (f->nls == 0 && !f->filled && !f->nwords)
 218                 fmt_sp(f);
 219         f->nls++;
 220         return 0;
 221 }
 222
 223 /* format the paragraph after the next word (\p) */
 224 int fmt_fillreq(struct fmt *f)
 225 {
 226         if (f->fillreq > 0)
 227                 if (fmt_fill(f))
 228                         return 1;
 229         f->fillreq = f->nwords + 1;
 230         return 0;
 231 }
 232
 233 static void fmt_wb2word(struct fmt *f, struct word *word, struct wb *wb,
 234                         int hy, int str, int gap)
 235 {
 236         int len = strlen(wb_buf(wb));
 237         word->s = xmalloc(len + 1);
 238         memcpy(word->s, wb_buf(wb), len + 1);
 239         word->wid = wb_wid(wb);
 240         word->elsn = wb->els_neg;
 241         word->elsp = wb->els_pos;
 242         word->hy = hy ? wb_dashwid(wb) : 0;
 243         word->str = str;
 244         word->gap = gap;
 245 }
 246
 247 /* find explicit hyphenation positions: dashes, \: and \% */
 248 static int fmt_hyphmarks(char *word, int *hyidx, int *hyins)
 249 {
 250         char d[ILNLEN];
 251         char *s = word;
 252         int c, n = 0;
 253         while ((c = escread(&s, d)) > 0)
 254                 ;
 255         if (c < 0 || !strcmp(c_hc, d))
 256                 return -1;
 257         while ((c = escread(&s, d)) >= 0 && n < NHYPHSWORD) {
 258                 if (!c && !strcmp(c_hc, d)) {
 259                         hyins[n] = 1;
 260                         hyidx[n++] = s - word;
 261                 }
 262                 if (!c && (!strcmp(c_bp, d) || c_isdash(d))) {
 263                         hyins[n] = 0;
 264                         hyidx[n++] = s - word;
 265                 }
 266         }
 267         return n;
 268 }
 269
 270 static void fmt_insertword(struct fmt *f, struct wb *wb, int gap)
 271 {
 272         int hyidx[NHYPHSWORD];
 273         int hyins[NHYPHSWORD] = {0};
 274         char *src = wb_buf(wb);
 275         struct wb wbc;
 276         char *beg;
 277         char *end;
 278         int n, i;
 279         int cf, cs, cm;
 280         n = fmt_hyphmarks(src, hyidx, hyins);
 281         if (n <= 0) {
 282                 fmt_wb2word(f, &f->words[f->nwords++], wb, 0, 1, gap);
 283                 return;
 284         }
 285         wb_init(&wbc);
 286         for (i = 0; i <= n; i++) {
 287                 beg = src + (i > 0 ? hyidx[i - 1] : 0);
 288                 end = src + (i < n ? hyidx[i] : strlen(src));
 289                 wb_catstr(&wbc, beg, end);
 290                 fmt_wb2word(f, &f->words[f->nwords++], &wbc,
 291                         i < n && hyins[i], i == 0, i == 0 ? gap : 0);
 292                 /* restoring wbc */
 293                 wb_fnszget(&wbc, &cs, &cf, &cm);
 294                 wb_reset(&wbc);
 295                 wb_fnszset(&wbc, cs, cf, cm);
 296         }
 297         wb_done(&wbc);
 298 }
 299
 300 /* the amount of space necessary before the next word */
 301 static int fmt_wordgap(struct fmt *f)
 302 {
 303         int nls = f->nls || f->nls_sup;
 304         if (f->eos && f->nwords)
 305                 if ((nls && !f->gap) || (!nls && f->gap == 2 * N_SS(n_f, n_s)))
 306                         return N_SS(n_f, n_s) + N_SSS(n_f, n_s);
 307         return (nls && !f->gap && f->nwords) ? N_SS(n_f, n_s) : f->gap;
 308 }
 309
 310 /* insert wb into fmt */
 311 int fmt_word(struct fmt *f, struct wb *wb)
 312 {
 313         if (wb_empty(wb))
 314                 return 0;
 315         if (f->nwords + NHYPHSWORD >= NWORDS || fmt_confchanged(f))
 316                 if (fmt_fill(f))
 317                         return 1;
 318         if (FMT_FILL(f) && f->nls && f->gap)
 319                 if (fmt_sp(f))
 320                         return 1;
 321         if (!f->nwords)         /* apply the new .l and .i */
 322                 fmt_confupdate(f);
 323         f->gap = fmt_wordgap(f);
 324         f->eos = wb_eos(wb);
 325         fmt_insertword(f, wb, f->filled ? 0 : f->gap);
 326         f->filled = 0;
 327         f->nls = 0;
 328         f->nls_sup = 0;
 329         f->gap = 0;
 330         return 0;
 331 }
 332
 333 /* assuming an empty line has cost 10000; take care of integer overflow */
 334 #define POW2(x)                         ((x) * (x))
 335 #define FMT_COST(lwid, llen, pen)       (POW2(((llen) - (lwid)) * 1000l / (llen)) / 100l + (pen) * 10l)
 336
 337 /* the cost of putting a line break before word pos */
 338 static long fmt_findcost(struct fmt *f, int pos)
 339 {
 340         int i, pen = 0;
 341         long cur;
 342         int lwid = 0;                   /* current line length */
 343         int swid = 0;                   /* amount of spaces */
 344         int llen = MAX(1, FMT_LLEN(f));
 345         if (pos <= 0)
 346                 return 0;
 347         if (f->best_pos[pos] >= 0)
 348                 return f->best[pos];
 349         i = pos - 1;
 350         lwid = 0;
 351         if (f->words[i].hy)     /* the last word is hyphenated */
 352                 lwid += f->words[i].hy;
 353         if (f->words[i].hy)
 354                 pen = n_hyp;
 355         while (i >= 0) {
 356                 lwid += f->words[i].wid;
 357                 if (i + 1 < pos)
 358                         lwid += f->words[i + 1].gap;
 359                 if (i + 1 < pos && f->words[i + 1].str)
 360                         swid += f->words[i + 1].gap;
 361                 if (lwid - (swid * n_ssh / 100) > llen)
 362                         if (pos - i > 1)
 363                                 break;
 364                 cur = fmt_findcost(f, i) + FMT_COST(lwid, llen, pen);
 365                 if (f->best_pos[pos] < 0 || cur < f->best[pos]) {
 366                         f->best_pos[pos] = i;
 367                         f->best_dep[pos] = f->best_dep[i] + 1;
 368                         f->best[pos] = cur;
 369                 }
 370                 i--;
 371         }
 372         return f->best[pos];
 373 }
 374
 375 static int fmt_bestpos(struct fmt *f, int pos)
 376 {
 377         fmt_findcost(f, pos);
 378         return MAX(0, f->best_pos[pos]);
 379 }
 380
 381 static int fmt_bestdep(struct fmt *f, int pos)
 382 {
 383         fmt_findcost(f, pos);
 384         return MAX(0, f->best_dep[pos]);
 385 }
 386
 387 /* return the last filled word */
 388 static int fmt_breakparagraph(struct fmt *f, int pos)
 389 {
 390         int i;
 391         int best = -1;
 392         int llen = FMT_LLEN(f);
 393         int lwid = 0;
 394         if (f->fillreq > 0 && f->fillreq <= f->nwords) {
 395                 fmt_findcost(f, f->fillreq);
 396                 return f->fillreq;
 397         }
 398         if (pos > 0 && f->words[pos - 1].wid >= llen) {
 399                 fmt_findcost(f, pos);
 400                 return pos;
 401         }
 402         i = pos - 1;
 403         lwid = 0;
 404         if (f->words[i].hy)     /* the last word is hyphenated */
 405                 lwid += f->words[i].hy;
 406         while (i >= 0) {
 407                 lwid += f->words[i].wid;
 408                 if (i + 1 < pos)
 409                         lwid += f->words[i + 1].gap;
 410                 if (lwid > llen && i + 1 < pos)
 411                         break;
 412                 if (best < 0 || fmt_findcost(f, i) < fmt_findcost(f, best))
 413                         best = i;
 414                 i--;
 415         }
 416         return best;
 417 }
 418
 419 /* extract the first nreq formatted lines before the word at pos */
 420 static int fmt_head(struct fmt *f, int nreq, int pos)
 421 {
 422         int best = pos;         /* best line break for nreq-th line */
 423         int prev, next;         /* best line breaks without hyphenation */
 424         if (nreq <= 0 || fmt_bestdep(f, pos) < nreq)
 425                 return pos;
 426         /* finding the optimal line break for nreq-th line */
 427         while (best > 0 && fmt_bestdep(f, best) > nreq)
 428                 best = fmt_bestpos(f, best);
 429         prev = best;
 430         next = best;
 431         /* finding closest line breaks without hyphenation */
 432         while (prev > 1 && f->words[prev - 1].hy &&
 433                         fmt_bestdep(f, prev - 1) == nreq)
 434                 prev--;
 435         while (next < pos && f->words[next - 1].hy &&
 436                         fmt_bestdep(f, next + 1) == nreq)
 437                 next++;
 438         /* choosing the best of them */
 439         if (!f->words[prev - 1].hy && !f->words[next - 1].hy)
 440                 return fmt_findcost(f, prev) <= fmt_findcost(f, next) ? prev : next;
 441         if (!f->words[prev - 1].hy)
 442                 return prev;
 443         if (!f->words[next - 1].hy)
 444                 return next;
 445         return best;
 446 }
 447
 448 /* break f->words[0..end] into lines according to fmt_bestpos() */
 449 static int fmt_break(struct fmt *f, int end)
 450 {
 451         int llen, fmt_div, fmt_rem, beg;
 452         int w, i, nspc;
 453         struct line *l;
 454         int ret = 0;
 455         beg = fmt_bestpos(f, end);
 456         if (beg > 0)
 457                 ret += fmt_break(f, beg);
 458         l = fmt_mkline(f);
 459         if (!l)
 460                 return ret;
 461         llen = FMT_LLEN(f);
 462         f->words[beg].gap = 0;
 463         w = fmt_wordslen(f, beg, end);
 464         nspc = fmt_spaces(f, beg, end);
 465         if (FMT_ADJ(f) && nspc) {
 466                 fmt_div = (llen - w) / nspc;
 467                 fmt_rem = (llen - w) % nspc;
 468                 if (fmt_rem < 0) {
 469                         fmt_div--;
 470                         fmt_rem += nspc;
 471                 }
 472                 for (i = beg + 1; i < end; i++)
 473                         if (f->words[i].str)
 474                                 f->words[i].gap += fmt_div + (fmt_rem-- > 0);
 475         }
 476         l->wid = fmt_wordscopy(f, beg, end, &l->sbuf, &l->elsn, &l->elsp);
 477         if (beg > 0)
 478                 fmt_confupdate(f);
 479         return ret + (end - beg);
 480 }
 481
 482 /* estimated number of lines until traps or the end of a page */
 483 static int fmt_safelines(void)
 484 {
 485         int lnht = MAX(1, n_L) * n_v;
 486         return (f_nexttrap() + lnht - 1) / lnht;
 487 }
 488
 489 /* fill the words collected in the buffer */
 490 int fmt_fill(struct fmt *f)
 491 {
 492         int nreq;       /* the number of lines until a trap */
 493         int end;        /* the final line ends before this word */
 494         int end_head;   /* like end, but only the first nreq lines included */
 495         int head = 0;   /* only nreq first lines have been formatted */
 496         int llen;       /* line length, taking shrinkable spaces into account */
 497         int n, i;
 498         if (!FMT_FILL(f))
 499                 return 0;
 500         llen = fmt_wordslen(f, 0, f->nwords) -
 501                 fmt_spacessum(f, 0, f->nwords) * n_ssh / 100;
 502         /* not enough words to fill */
 503         if ((f->fillreq <= 0 || f->nwords < f->fillreq) && llen <= FMT_LLEN(f))
 504                 return 0;
 505         nreq = (n_hy & HY_LAST) ? fmt_safelines() : 0;
 506         if (nreq > 0 && nreq <= fmt_nlines(f))
 507                 return 1;
 508         /* resetting positions */
 509         for (i = 0; i < f->nwords + 1; i++)
 510                 f->best_pos[i] = -1;
 511         end = fmt_breakparagraph(f, f->nwords);
 512         if (nreq > 0) {
 513                 end_head = fmt_head(f, nreq - fmt_nlines(f), end);
 514                 head = end_head < end;
 515                 end = end_head;
 516         }
 517         /* recursively add lines */
 518         n = fmt_break(f, end);
 519         f->nwords -= n;
 520         f->fillreq -= n;
 521         fmt_movewords(f, 0, n, f->nwords);
 522         f->filled = n && !f->nwords;
 523         if (f->nwords)
 524                 f->words[0].gap = 0;
 525         if (f->nwords)          /* apply the new .l and .i */
 526                 fmt_confupdate(f);
 527         return head || n != end;
 528 }
 529
 530 struct fmt *fmt_alloc(void)
 531 {
 532         struct fmt *fmt = xmalloc(sizeof(*fmt));
 533         memset(fmt, 0, sizeof(*fmt));
 534         return fmt;
 535 }
 536
 537 void fmt_free(struct fmt *fmt)
 538 {
 539         free(fmt);
 540 }
 541
 542 int fmt_wid(struct fmt *fmt)
 543 {
 544         return fmt_wordslen(fmt, 0, fmt->nwords) + fmt_wordgap(fmt);
 545 }
 546
 547 int fmt_morewords(struct fmt *fmt)
 548 {
 549         return fmt_morelines(fmt) || fmt->nwords;
 550 }
 551
 552 int fmt_morelines(struct fmt *fmt)
 553 {
 554         return fmt->l_head != fmt->l_tail;
 555 }
 556
 557 /* suppress the last newline */
 558 void fmt_suppressnl(struct fmt *fmt)
 559 {
 560         if (fmt->nls) {
 561                 fmt->nls--;
 562                 fmt->nls_sup = 1;
 563         }
 564 }