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 hyphenating some of them), and, if
   6  * requested, adjusting the space between words in a line.  In this
   7  * file the first step is referred to as filling.
   8  *
   9  * Inputs are specified via these functions:
  10  * + fmt_word(): for appending space-separated words.
  11  * + fmt_space(): for appending spaces.
  12  * + fmt_newline(): for appending new lines.
  13  *
  14  */
  15 #include <stdio.h>
  16 #include <stdlib.h>
  17 #include <string.h>
  18 #include "roff.h"
  19
  20 #define FMT_LLEN(f)     MAX(0, (f)->ll - (f)->li)
  21 #define FMT_FILL(f)     (!n_ce && n_u)
  22 #define FMT_ADJ(f)      (n_u && !n_na && !n_ce && (n_j & AD_B) == AD_B)
  23 #define FMT_SWID(f)     (spacewid(n_f, n_s))
  24
  25 struct word {
  26         char *s;
  27         int wid;        /* word's width */
  28         int elsn, elsp; /* els_neg and els_pos */
  29         int gap;        /* the space before this word */
  30         int hy;         /* hyphen width if inserted after this word */
  31         int str;        /* does the spece before it stretch */
  32 };
  33
  34 struct line {
  35         struct sbuf sbuf;
  36         int wid, li, ll;
  37         int elsn, elsp;
  38 };
  39
  40 struct fmt {
  41         /* queued words */
  42         struct word words[NWORDS];
  43         int nwords;
  44         /* queued lines */
  45         struct line lines[NLINES];
  46         int l_head, l_tail;
  47         /* for paragraph adjustment */
  48         long best[NWORDS];
  49         int best_pos[NWORDS];
  50         int best_dep[NWORDS];
  51         /* current line */
  52         int gap;                /* space before the next word */
  53         int nls;                /* newlines before the next word */
  54         int li, ll;             /* current line indentation and length */
  55         int filled;             /* filled all words in the last fmt_fill() */
  56         int eos;                /* last word ends a sentence */
  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 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 /* return the next line in the buffer */
 134 int fmt_nextline(struct fmt *f, struct sbuf *sbuf, int *w,
 135                 int *li, int *ll, int *els_neg, int *els_pos)
 136 {
 137         struct line *l;
 138         l = &f->lines[f->l_tail];
 139         if (f->l_head == f->l_tail)
 140                 return 1;
 141         *li = l->li;
 142         *ll = l->ll;
 143         *w = l->wid;
 144         *els_neg = l->elsn;
 145         *els_pos = l->elsp;
 146         sbuf_append(sbuf, sbuf_buf(&l->sbuf));
 147         sbuf_done(&l->sbuf);
 148         f->l_tail = (f->l_tail + 1) % NLINES;
 149         return 0;
 150 }
 151
 152 static struct line *fmt_mkline(struct fmt *f)
 153 {
 154         struct line *l = &f->lines[f->l_head];
 155         if ((f->l_head + 1) % NLINES == f->l_tail)
 156                 return NULL;
 157         f->l_head = (f->l_head + 1) % NLINES;
 158         l->li = f->li;
 159         l->ll = f->ll;
 160         sbuf_init(&l->sbuf);
 161         return l;
 162 }
 163
 164 static int fmt_sp(struct fmt *f)
 165 {
 166         struct line *l;
 167         fmt_fill(f, 0, 0);
 168         l = fmt_mkline(f);
 169         if (!l)
 170                 return 1;
 171         f->filled = 0;
 172         f->nls--;
 173         l->wid = fmt_wordscopy(f, 0, f->nwords, &l->sbuf, &l->elsn, &l->elsp);
 174         f->nwords = 0;
 175         return 0;
 176 }
 177
 178 void fmt_br(struct fmt *f)
 179 {
 180         fmt_fill(f, 0, 0);
 181         f->filled = 0;
 182         if (f->nwords)
 183                 fmt_sp(f);
 184 }
 185
 186 void fmt_space(struct fmt *fmt)
 187 {
 188         fmt->gap += FMT_SWID(fmt);
 189 }
 190
 191 void fmt_newline(struct fmt *f)
 192 {
 193         f->nls++;
 194         f->gap = 0;
 195         if (!FMT_FILL(f)) {
 196                 fmt_sp(f);
 197                 return;
 198         }
 199         if (f->nls == 1 && !f->filled && !f->nwords)
 200                 fmt_sp(f);
 201         if (f->nls > 1) {
 202                 if (!f->filled)
 203                         fmt_sp(f);
 204                 fmt_sp(f);
 205         }
 206 }
 207
 208 static void fmt_wb2word(struct fmt *f, struct word *word, struct wb *wb,
 209                         int hy, int str, int gap)
 210 {
 211         int len = strlen(wb_buf(wb));
 212         word->s = malloc(len + 1);
 213         memcpy(word->s, wb_buf(wb), len + 1);
 214         word->wid = wb_wid(wb);
 215         word->elsn = wb->els_neg;
 216         word->elsp = wb->els_pos;
 217         word->hy = hy ? wb_dashwid(wb) : 0;
 218         word->str = str;
 219         word->gap = gap;
 220 }
 221
 222 static void fmt_insertword(struct fmt *f, struct wb *wb, int gap)
 223 {
 224         int hyidx[NHYPHS];
 225         int hyins[NHYPHS] = {0};
 226         char *src = wb_buf(wb);
 227         struct wb wbc;
 228         char *beg;
 229         char *end;
 230         int n, i;
 231         int cf, cs, cm;
 232         int hy = 0;             /* insert hyphens */
 233         n = wb_hyphmark(src, hyidx, hyins);
 234         if (!n && n_hy && (n = wb_hyph(src, hyidx, n_hy)) > 0)
 235                 hy = 1;
 236         if (n <= 0) {
 237                 fmt_wb2word(f, &f->words[f->nwords++], wb, 0, 1, gap);
 238                 return;
 239         }
 240         wb_init(&wbc);
 241         for (i = 0; i <= n; i++) {
 242                 beg = src + (i > 0 ? hyidx[i - 1] : 0);
 243                 end = src + (i < n ? hyidx[i] : strlen(src));
 244                 wb_catstr(&wbc, beg, end);
 245                 fmt_wb2word(f, &f->words[f->nwords++], &wbc,
 246                         i < n && (hy || hyins[i]), i == 0, i == 0 ? gap : 0);
 247                 /* restoring wbc */
 248                 wb_fnszget(&wbc, &cs, &cf, &cm);
 249                 wb_reset(&wbc);
 250                 wb_fnszset(&wbc, cs, cf, cm);
 251         }
 252         wb_done(&wbc);
 253 }
 254
 255 /* insert wb into fmt */
 256 void fmt_word(struct fmt *f, struct wb *wb)
 257 {
 258         if (f->nwords == NWORDS || fmt_confchanged(f))
 259                 fmt_fill(f, 0, 0);
 260         if (wb_empty(wb) || f->nwords == NWORDS)
 261                 return;
 262         if (FMT_FILL(f) && f->nls && f->gap)
 263                 fmt_sp(f);
 264         if (!f->nwords)         /* apply the new .l and .i */
 265                 fmt_confupdate(f);
 266         if (f->nls && !f->gap && f->nwords >= 1)
 267                 f->gap = (f->nwords && f->eos) ? FMT_SWID(f) * 2 : FMT_SWID(f);
 268         f->eos = wb_eos(wb);
 269         fmt_insertword(f, wb, f->filled ? 0 : f->gap);
 270         f->filled = 0;
 271         f->nls = 0;
 272         f->gap = 0;
 273 }
 274
 275 /* assuming an empty line has cost 10000; take care of integer overflow */
 276 #define POW2(x)                         ((x) * (x))
 277 #define FMT_COST(lwid, llen, pen)       (POW2(((llen) - (lwid)) * 1000l / (llen)) / 100l + (pen) * 10l)
 278
 279 /* the cost of putting a line break before word pos */
 280 static long fmt_findcost(struct fmt *f, int pos)
 281 {
 282         int i, pen = 0;
 283         long cur;
 284         int lwid = 0;
 285         int llen = FMT_LLEN(f);
 286         if (pos <= 0)
 287                 return 0;
 288         if (f->best_pos[pos] >= 0)
 289                 return f->best[pos];
 290         i = pos - 1;
 291         lwid = 0;
 292         if (f->words[i].hy)     /* the last word is hyphenated */
 293                 lwid += f->words[i].hy;
 294         if (f->words[i].hy)
 295                 pen = n_hyp;
 296         while (i >= 0) {
 297                 lwid += f->words[i].wid;
 298                 if (i + 1 < pos)
 299                         lwid += f->words[i + 1].gap;
 300                 if (lwid > llen && pos - i > 1)
 301                         break;
 302                 cur = fmt_findcost(f, i) + FMT_COST(lwid, llen, pen);
 303                 if (f->best_pos[pos] < 0 || cur < f->best[pos]) {
 304                         f->best_pos[pos] = i;
 305                         f->best_dep[pos] = f->best_dep[i] + 1;
 306                         f->best[pos] = cur;
 307                 }
 308                 i--;
 309         }
 310         return f->best[pos];
 311 }
 312
 313 static int fmt_bestpos(struct fmt *f, int pos)
 314 {
 315         fmt_findcost(f, pos);
 316         return MAX(0, f->best_pos[pos]);
 317 }
 318
 319 /* return the last filled word */
 320 static int fmt_breakparagraph(struct fmt *f, int pos, int all)
 321 {
 322         int i;
 323         int best = -1;
 324         int llen = FMT_LLEN(f);
 325         int lwid = 0;
 326         if (all || (pos > 0 && f->words[pos - 1].wid >= llen)) {
 327                 fmt_findcost(f, pos);
 328                 return pos;
 329         }
 330         i = pos - 1;
 331         lwid = 0;
 332         if (f->words[i].hy)     /* the last word is hyphenated */
 333                 lwid += f->words[i].hy;
 334         while (i >= 0) {
 335                 lwid += f->words[i].wid;
 336                 if (i + 1 < pos)
 337                         lwid += f->words[i + 1].gap;
 338                 if (lwid > llen && pos - i > 1)
 339                         break;
 340                 if (best < 0 || fmt_findcost(f, i) < fmt_findcost(f, best))
 341                         best = i;
 342                 i--;
 343         }
 344         return best;
 345 }
 346
 347 static int fmt_head(struct fmt *f, int nreq, int pos)
 348 {
 349         int best = -1;
 350         int i;
 351         if (nreq <= 0 || f->best_dep[pos] < nreq)
 352                 return pos;
 353         for (i = 1; i < pos && f->best_dep[i] <= nreq; i++) {
 354                 fmt_findcost(f, i);
 355                 if (f->best_dep[i] == nreq && !f->words[i - 1].hy)
 356                         best = i;
 357         }
 358         return best >= 0 ? best : i - 1;
 359 }
 360
 361 /* break f->words[0..end] into lines according to fmt_bestpos() */
 362 static int fmt_break(struct fmt *f, int end)
 363 {
 364         int llen, fmt_div, fmt_rem, beg;
 365         int w, i, nspc;
 366         struct line *l;
 367         int ret = 0;
 368         beg = fmt_bestpos(f, end);
 369         if (beg > 0)
 370                 ret += fmt_break(f, beg);
 371         l = fmt_mkline(f);
 372         if (!l)
 373                 return ret;
 374         llen = FMT_LLEN(f);
 375         f->words[beg].gap = 0;
 376         w = fmt_wordslen(f, beg, end);
 377         nspc = fmt_spaces(f, beg, end);
 378         if (FMT_ADJ(f) && nspc) {
 379                 fmt_div = (llen - w) / nspc;
 380                 fmt_rem = (llen - w) % nspc;
 381                 for (i = beg + 1; i < end; i++)
 382                         if (f->words[i].str)
 383                                 f->words[i].gap += fmt_div + (fmt_rem-- > 0);
 384         }
 385         l->wid = fmt_wordscopy(f, beg, end, &l->sbuf, &l->elsn, &l->elsp);
 386         if (beg > 0)
 387                 fmt_confupdate(f);
 388         return ret + (end - beg);
 389 }
 390
 391 /*
 392  * fill the words collected in the buffer
 393  *
 394  * The argument nreq, when nonzero, limits the number of lines
 395  * to format.  It also tells fmt_fill() not to hyphenate the
 396  * last word of nreq-th line.  This is used in ren.c to prevent
 397  * hyphenating last lines of pages.
 398  *
 399  * The all argument forces fmt_fill() to fill all of the words.
 400  * This is used for the \p escape sequence.
 401  */
 402 int fmt_fill(struct fmt *f, int nreq, int all)
 403 {
 404         int end;        /* the final line ends before this word */
 405         int end_head;   /* like end, but only the first nreq lines included */
 406         int head = 0;   /* only nreq first lines have been formatted */
 407         int n, i;
 408         if (!FMT_FILL(f))
 409                 return 0;
 410         /* not enough words to fill */
 411         if (!all && fmt_wordslen(f, 0, f->nwords) <= FMT_LLEN(f))
 412                 return 0;
 413         if (nreq > 0 && nreq <= fmt_nlines(f))
 414                 return 0;
 415         /* resetting positions */
 416         for (i = 0; i < f->nwords + 1; i++)
 417                 f->best_pos[i] = -1;
 418         end = fmt_breakparagraph(f, f->nwords, all);
 419         if (nreq > 0) {
 420                 end_head = fmt_head(f, nreq - fmt_nlines(f), end);
 421                 head = end_head < end;
 422                 end = end_head;
 423         }
 424         /* recursively add lines */
 425         n = fmt_break(f, end);
 426         f->nwords -= n;
 427         fmt_movewords(f, 0, n, f->nwords);
 428         f->filled = n && !f->nwords;
 429         if (f->nwords)
 430                 f->words[0].gap = 0;
 431         if (f->nwords)          /* apply the new .l and .i */
 432                 fmt_confupdate(f);
 433         return head || n != end;
 434 }
 435
 436 struct fmt *fmt_alloc(void)
 437 {
 438         struct fmt *fmt = malloc(sizeof(*fmt));
 439         memset(fmt, 0, sizeof(*fmt));
 440         return fmt;
 441 }
 442
 443 void fmt_free(struct fmt *fmt)
 444 {
 445         free(fmt);
 446 }
 447
 448 int fmt_wid(struct fmt *fmt)
 449 {
 450         return fmt_wordslen(fmt, 0, fmt->nwords) +
 451                 (fmt->nls ? FMT_SWID(fmt) : fmt->gap);
 452 }
 453
 454 int fmt_morewords(struct fmt *fmt)
 455 {
 456         return fmt_morelines(fmt) || fmt->nwords;
 457 }
 458
 459 int fmt_morelines(struct fmt *fmt)
 460 {
 461         return fmt->l_head != fmt->l_tail;
 462 }