2 * line formatting buffer for line adjustment and hyphenation
4 * The line formatting buffer does two main functions: breaking
5 * words into lines (possibly after hyphenating some of them),
6 * and, if requested, adjusting the space between words in a line.
7 * In this file the first step is referred to as filling.
9 * Functions like fmt_word() return nonzero on failure, which
10 * means the call should be repeated after fetching previously
11 * formatted lines via fmt_nextline().
18 #define FMT_LLEN(f) MAX(0, (f)->ll - (f)->li)
19 #define FMT_FILL(f) (!n_ce && n_u)
20 #define FMT_ADJ(f) (n_u && !n_na && !n_ce && (n_j & AD_B) == AD_B)
24 int wid
; /* word's width */
25 int elsn
, elsp
; /* els_neg and els_pos */
26 int gap
; /* the space before this word */
27 int hy
; /* hyphen width if inserted after this word */
28 int str
; /* does the space before it stretch */
39 struct word words
[NWORDS
];
42 struct line lines
[NLINES
];
44 /* for paragraph adjustment */
49 int gap
; /* space before the next word */
50 int nls
; /* newlines before the next word */
51 int nls_sup
; /* suppressed newlines */
52 int li
, ll
; /* current line indentation and length */
53 int filled
; /* filled all words in the last fmt_fill() */
54 int eos
; /* last word ends a sentence */
55 int fillreq
; /* fill after the last word (\p) */
58 /* .ll, .in and .ti are delayed until the partial line is output */
59 static void fmt_confupdate(struct fmt
*f
)
62 f
->li
= n_ti
>= 0 ? n_ti
: n_i
;
66 static int fmt_confchanged(struct fmt
*f
)
68 return f
->ll
!= n_l
|| f
->li
!= (n_ti
>= 0 ? n_ti
: n_i
);
71 /* move words inside an fmt struct */
72 static void fmt_movewords(struct fmt
*a
, int dst
, int src
, int len
)
74 memmove(a
->words
+ dst
, a
->words
+ src
, len
* sizeof(a
->words
[0]));
77 /* move words from the buffer to s */
78 static int fmt_wordscopy(struct fmt
*f
, int beg
, int end
,
79 struct sbuf
*s
, int *els_neg
, int *els_pos
)
86 for (i
= beg
; i
< end
; i
++) {
88 sbuf_printf(s
, "%ch'%du'", c_ec
, wcur
->gap
);
89 sbuf_append(s
, wcur
->s
);
90 w
+= wcur
->wid
+ wcur
->gap
;
91 if (wcur
->elsn
< *els_neg
)
92 *els_neg
= wcur
->elsn
;
93 if (wcur
->elsp
> *els_pos
)
94 *els_pos
= wcur
->elsp
;
98 wcur
= &f
->words
[end
- 1];
100 sbuf_append(s
, "\\(hy");
106 static int fmt_nlines(struct fmt
*f
)
108 if (f
->l_tail
<= f
->l_head
)
109 return f
->l_head
- f
->l_tail
;
110 return NLINES
- f
->l_tail
+ f
->l_head
;
113 /* the total width of the specified words in f->words[] */
114 static int fmt_wordslen(struct fmt
*f
, int beg
, int end
)
117 for (i
= beg
; i
< end
; i
++)
118 w
+= f
->words
[i
].wid
+ f
->words
[i
].gap
;
119 return beg
< end
? w
+ f
->words
[end
- 1].hy
: 0;
122 /* the number of stretchable spaces in f */
123 static int fmt_spaces(struct fmt
*f
, int beg
, int end
)
126 for (i
= beg
+ 1; i
< end
; i
++)
132 /* the amount of stretchable spaces in f */
133 static int fmt_spacessum(struct fmt
*f
, int beg
, int end
)
136 for (i
= beg
+ 1; i
< end
; i
++)
138 n
+= f
->words
[i
].gap
;
142 /* return the next line in the buffer */
143 int fmt_nextline(struct fmt
*f
, struct sbuf
*sbuf
, int *w
,
144 int *li
, int *ll
, int *els_neg
, int *els_pos
)
147 l
= &f
->lines
[f
->l_tail
];
148 if (f
->l_head
== f
->l_tail
)
155 sbuf_append(sbuf
, sbuf_buf(&l
->sbuf
));
157 f
->l_tail
= (f
->l_tail
+ 1) % NLINES
;
161 static struct line
*fmt_mkline(struct fmt
*f
)
163 struct line
*l
= &f
->lines
[f
->l_head
];
164 if ((f
->l_head
+ 1) % NLINES
== f
->l_tail
)
166 f
->l_head
= (f
->l_head
+ 1) % NLINES
;
173 static int fmt_sp(struct fmt
*f
)
184 l
->wid
= fmt_wordscopy(f
, 0, f
->nwords
, &l
->sbuf
, &l
->elsn
, &l
->elsp
);
190 int fmt_br(struct fmt
*f
)
200 void fmt_space(struct fmt
*fmt
)
202 fmt
->gap
+= N_SS(n_f
, n_s
);
205 int fmt_newline(struct fmt
*f
)
216 if (f
->nls
== 0 && !f
->filled
&& !f
->nwords
)
222 /* format the paragraph after the next word (\p) */
223 int fmt_fillreq(struct fmt
*f
)
228 f
->fillreq
= f
->nwords
+ 1;
232 static void fmt_wb2word(struct fmt
*f
, struct word
*word
, struct wb
*wb
,
233 int hy
, int str
, int gap
)
235 int len
= strlen(wb_buf(wb
));
236 word
->s
= xmalloc(len
+ 1);
237 memcpy(word
->s
, wb_buf(wb
), len
+ 1);
238 word
->wid
= wb_wid(wb
);
239 word
->elsn
= wb
->els_neg
;
240 word
->elsp
= wb
->els_pos
;
241 word
->hy
= hy
? wb_dashwid(wb
) : 0;
246 static void fmt_insertword(struct fmt
*f
, struct wb
*wb
, int gap
)
248 int hyidx
[NHYPHSWORD
];
249 int hyins
[NHYPHSWORD
] = {0};
250 char *src
= wb_buf(wb
);
256 int hy
= 0; /* insert hyphens */
257 n
= wb_hyphmark(src
, hyidx
, hyins
);
258 if (!n
&& n_hy
&& (n
= wb_hyph(src
, hyidx
, n_hy
)) > 0)
261 fmt_wb2word(f
, &f
->words
[f
->nwords
++], wb
, 0, 1, gap
);
265 for (i
= 0; i
<= n
; i
++) {
266 beg
= src
+ (i
> 0 ? hyidx
[i
- 1] : 0);
267 end
= src
+ (i
< n
? hyidx
[i
] : strlen(src
));
268 wb_catstr(&wbc
, beg
, end
);
269 fmt_wb2word(f
, &f
->words
[f
->nwords
++], &wbc
,
270 i
< n
&& (hy
|| hyins
[i
]), i
== 0, i
== 0 ? gap
: 0);
272 wb_fnszget(&wbc
, &cs
, &cf
, &cm
);
274 wb_fnszset(&wbc
, cs
, cf
, cm
);
279 /* the amount of space necessary before the next word */
280 static int fmt_wordgap(struct fmt
*f
)
282 int nls
= f
->nls
|| f
->nls_sup
;
283 if (f
->eos
&& f
->nwords
)
284 if ((nls
&& !f
->gap
) || (!nls
&& f
->gap
== 2 * N_SS(n_f
, n_s
)))
285 return N_SS(n_f
, n_s
) + N_SSS(n_f
, n_s
);
286 return (nls
&& !f
->gap
&& f
->nwords
) ? N_SS(n_f
, n_s
) : f
->gap
;
289 /* insert wb into fmt */
290 int fmt_word(struct fmt
*f
, struct wb
*wb
)
294 if (f
->nwords
+ NHYPHSWORD
>= NWORDS
|| fmt_confchanged(f
))
297 if (FMT_FILL(f
) && f
->nls
&& f
->gap
)
300 if (!f
->nwords
) /* apply the new .l and .i */
302 f
->gap
= fmt_wordgap(f
);
304 fmt_insertword(f
, wb
, f
->filled
? 0 : f
->gap
);
312 /* assuming an empty line has cost 10000; take care of integer overflow */
313 #define POW2(x) ((x) * (x))
314 #define FMT_COST(lwid, llen, pen) (POW2(((llen) - (lwid)) * 1000l / (llen)) / 100l + (pen) * 10l)
316 /* the cost of putting a line break before word pos */
317 static long fmt_findcost(struct fmt
*f
, int pos
)
321 int lwid
= 0; /* current line length */
322 int swid
= 0; /* amount of spaces */
323 int llen
= MAX(1, FMT_LLEN(f
));
326 if (f
->best_pos
[pos
] >= 0)
330 if (f
->words
[i
].hy
) /* the last word is hyphenated */
331 lwid
+= f
->words
[i
].hy
;
335 lwid
+= f
->words
[i
].wid
;
337 lwid
+= f
->words
[i
+ 1].gap
;
338 if (i
+ 1 < pos
&& f
->words
[i
+ 1].str
)
339 swid
+= f
->words
[i
+ 1].gap
;
340 if (lwid
- (swid
* n_ssh
/ 100) > llen
)
343 cur
= fmt_findcost(f
, i
) + FMT_COST(lwid
, llen
, pen
);
344 if (f
->best_pos
[pos
] < 0 || cur
< f
->best
[pos
]) {
345 f
->best_pos
[pos
] = i
;
346 f
->best_dep
[pos
] = f
->best_dep
[i
] + 1;
354 static int fmt_bestpos(struct fmt
*f
, int pos
)
356 fmt_findcost(f
, pos
);
357 return MAX(0, f
->best_pos
[pos
]);
360 static int fmt_bestdep(struct fmt
*f
, int pos
)
362 fmt_findcost(f
, pos
);
363 return MAX(0, f
->best_dep
[pos
]);
366 /* return the last filled word */
367 static int fmt_breakparagraph(struct fmt
*f
, int pos
)
371 int llen
= FMT_LLEN(f
);
373 if (f
->fillreq
> 0 && f
->fillreq
<= f
->nwords
) {
374 fmt_findcost(f
, f
->fillreq
);
377 if (pos
> 0 && f
->words
[pos
- 1].wid
>= llen
) {
378 fmt_findcost(f
, pos
);
383 if (f
->words
[i
].hy
) /* the last word is hyphenated */
384 lwid
+= f
->words
[i
].hy
;
386 lwid
+= f
->words
[i
].wid
;
388 lwid
+= f
->words
[i
+ 1].gap
;
389 if (lwid
> llen
&& i
+ 1 < pos
)
391 if (best
< 0 || fmt_findcost(f
, i
) < fmt_findcost(f
, best
))
398 /* extract the first nreq formatted lines before the word at pos */
399 static int fmt_head(struct fmt
*f
, int nreq
, int pos
)
401 int best
= pos
; /* best line break for nreq-th line */
402 int prev
, next
; /* best line breaks without hyphenation */
403 if (nreq
<= 0 || fmt_bestdep(f
, pos
) < nreq
)
405 /* finding the optimal line break for nreq-th line */
406 while (best
> 0 && fmt_bestdep(f
, best
) > nreq
)
407 best
= fmt_bestpos(f
, best
);
410 /* finding closest line breaks without hyphenation */
411 while (prev
> 1 && f
->words
[prev
- 1].hy
&&
412 fmt_bestdep(f
, prev
- 1) == nreq
)
414 while (next
< pos
&& f
->words
[next
- 1].hy
&&
415 fmt_bestdep(f
, next
+ 1) == nreq
)
417 /* choosing the best of them */
418 if (!f
->words
[prev
- 1].hy
&& !f
->words
[next
- 1].hy
)
419 return fmt_findcost(f
, prev
) <= fmt_findcost(f
, next
) ? prev
: next
;
420 if (!f
->words
[prev
- 1].hy
)
422 if (!f
->words
[next
- 1].hy
)
427 /* break f->words[0..end] into lines according to fmt_bestpos() */
428 static int fmt_break(struct fmt
*f
, int end
)
430 int llen
, fmt_div
, fmt_rem
, beg
;
434 beg
= fmt_bestpos(f
, end
);
436 ret
+= fmt_break(f
, beg
);
441 f
->words
[beg
].gap
= 0;
442 w
= fmt_wordslen(f
, beg
, end
);
443 nspc
= fmt_spaces(f
, beg
, end
);
444 if (FMT_ADJ(f
) && nspc
) {
445 fmt_div
= (llen
- w
) / nspc
;
446 fmt_rem
= (llen
- w
) % nspc
;
451 for (i
= beg
+ 1; i
< end
; i
++)
453 f
->words
[i
].gap
+= fmt_div
+ (fmt_rem
-- > 0);
455 l
->wid
= fmt_wordscopy(f
, beg
, end
, &l
->sbuf
, &l
->elsn
, &l
->elsp
);
458 return ret
+ (end
- beg
);
461 /* estimated number of lines until traps or the end of a page */
462 static int fmt_safelines(void)
464 int lnht
= MAX(1, n_L
) * n_v
;
465 return (f_nexttrap() + lnht
- 1) / lnht
;
468 /* fill the words collected in the buffer */
469 int fmt_fill(struct fmt
*f
)
471 int nreq
; /* the number of lines until a trap */
472 int end
; /* the final line ends before this word */
473 int end_head
; /* like end, but only the first nreq lines included */
474 int head
= 0; /* only nreq first lines have been formatted */
475 int llen
; /* line length, taking shrinkable spaces into account */
479 llen
= fmt_wordslen(f
, 0, f
->nwords
) -
480 fmt_spacessum(f
, 0, f
->nwords
) * n_ssh
/ 100;
481 /* not enough words to fill */
482 if ((f
->fillreq
<= 0 || f
->nwords
< f
->fillreq
) && llen
<= FMT_LLEN(f
))
484 nreq
= (n_hy
& HY_LAST
) ? fmt_safelines() : 0;
485 if (nreq
> 0 && nreq
<= fmt_nlines(f
))
487 /* resetting positions */
488 for (i
= 0; i
< f
->nwords
+ 1; i
++)
490 end
= fmt_breakparagraph(f
, f
->nwords
);
492 end_head
= fmt_head(f
, nreq
- fmt_nlines(f
), end
);
493 head
= end_head
< end
;
496 /* recursively add lines */
497 n
= fmt_break(f
, end
);
500 fmt_movewords(f
, 0, n
, f
->nwords
);
501 f
->filled
= n
&& !f
->nwords
;
504 if (f
->nwords
) /* apply the new .l and .i */
506 return head
|| n
!= end
;
509 struct fmt
*fmt_alloc(void)
511 struct fmt
*fmt
= xmalloc(sizeof(*fmt
));
512 memset(fmt
, 0, sizeof(*fmt
));
516 void fmt_free(struct fmt
*fmt
)
521 int fmt_wid(struct fmt
*fmt
)
523 return fmt_wordslen(fmt
, 0, fmt
->nwords
) + fmt_wordgap(fmt
);
526 int fmt_morewords(struct fmt
*fmt
)
528 return fmt_morelines(fmt
) || fmt
->nwords
;
531 int fmt_morelines(struct fmt
*fmt
)
533 return fmt
->l_head
!= fmt
->l_tail
;
536 /* suppress the last newline */
537 void fmt_suppressnl(struct fmt
*fmt
)