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), and, if
6 * requested, adjusting the space between words in a line. In this
7 * file the first step is referred to as filling.
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.
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))
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 */
42 struct word words
[NWORDS
];
45 struct line lines
[NLINES
];
47 /* for paragraph adjustment */
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 */
59 /* .ll, .in and .ti are delayed until the partial line is output */
60 static void fmt_confupdate(struct fmt
*f
)
63 f
->li
= n_ti
>= 0 ? n_ti
: n_i
;
67 static int fmt_confchanged(struct fmt
*f
)
69 return f
->ll
!= n_l
|| f
->li
!= (n_ti
>= 0 ? n_ti
: n_i
);
72 /* move words inside an fmt struct */
73 static void fmt_movewords(struct fmt
*a
, int dst
, int src
, int len
)
75 memmove(a
->words
+ dst
, a
->words
+ src
, len
* sizeof(a
->words
[0]));
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
)
87 for (i
= beg
; i
< end
; 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
;
99 wcur
= &f
->words
[end
- 1];
101 sbuf_append(s
, "\\(hy");
107 static int fmt_nlines(struct fmt
*f
)
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
;
114 /* the total width of the specified words in f->words[] */
115 static int fmt_wordslen(struct fmt
*f
, int beg
, int end
)
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;
123 /* the number stretchable spaces in f */
124 static int fmt_spaces(struct fmt
*f
, int beg
, int end
)
127 for (i
= beg
+ 1; i
< end
; i
++)
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
)
138 l
= &f
->lines
[f
->l_tail
];
139 if (f
->l_head
== f
->l_tail
)
146 sbuf_append(sbuf
, sbuf_buf(&l
->sbuf
));
148 f
->l_tail
= (f
->l_tail
+ 1) % NLINES
;
152 static struct line
*fmt_mkline(struct fmt
*f
)
154 struct line
*l
= &f
->lines
[f
->l_head
];
155 if ((f
->l_head
+ 1) % NLINES
== f
->l_tail
)
157 f
->l_head
= (f
->l_head
+ 1) % NLINES
;
164 static int fmt_sp(struct fmt
*f
)
173 l
->wid
= fmt_wordscopy(f
, 0, f
->nwords
, &l
->sbuf
, &l
->elsn
, &l
->elsp
);
178 void fmt_br(struct fmt
*f
)
186 void fmt_space(struct fmt
*fmt
)
188 fmt
->gap
+= FMT_SWID(fmt
);
191 void fmt_newline(struct fmt
*f
)
199 if (f
->nls
== 1 && !f
->filled
&& !f
->nwords
)
208 static void fmt_wb2word(struct fmt
*f
, struct word
*word
, struct wb
*wb
,
209 int hy
, int str
, int gap
)
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;
222 static void fmt_insertword(struct fmt
*f
, struct wb
*wb
, int gap
)
225 int hyins
[NHYPHS
] = {0};
226 char *src
= wb_buf(wb
);
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)
237 fmt_wb2word(f
, &f
->words
[f
->nwords
++], wb
, 0, 1, gap
);
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);
248 wb_fnszget(&wbc
, &cs
, &cf
, &cm
);
250 wb_fnszset(&wbc
, cs
, cf
, cm
);
255 /* insert wb into fmt */
256 void fmt_word(struct fmt
*f
, struct wb
*wb
)
258 if (f
->nwords
== NWORDS
|| fmt_confchanged(f
))
260 if (wb_empty(wb
) || f
->nwords
== NWORDS
)
262 if (FMT_FILL(f
) && f
->nls
&& f
->gap
)
264 if (!f
->nwords
) /* apply the new .l and .i */
266 if (f
->nls
&& !f
->gap
&& f
->nwords
>= 1)
267 f
->gap
= (f
->nwords
&& f
->eos
) ? FMT_SWID(f
) * 2 : FMT_SWID(f
);
269 fmt_insertword(f
, wb
, f
->filled
? 0 : f
->gap
);
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)
279 /* the cost of putting a line break before word pos */
280 static long fmt_findcost(struct fmt
*f
, int pos
)
285 int llen
= FMT_LLEN(f
);
288 if (f
->best_pos
[pos
] >= 0)
292 if (f
->words
[i
].hy
) /* the last word is hyphenated */
293 lwid
+= f
->words
[i
].hy
;
297 lwid
+= f
->words
[i
].wid
;
299 lwid
+= f
->words
[i
+ 1].gap
;
300 if (lwid
> llen
&& pos
- i
> 1)
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;
313 static int fmt_bestpos(struct fmt
*f
, int pos
)
315 fmt_findcost(f
, pos
);
316 return MAX(0, f
->best_pos
[pos
]);
319 /* return the last filled word */
320 static int fmt_breakparagraph(struct fmt
*f
, int pos
, int all
)
324 int llen
= FMT_LLEN(f
);
326 if (all
|| (pos
> 0 && f
->words
[pos
- 1].wid
>= llen
)) {
327 fmt_findcost(f
, pos
);
332 if (f
->words
[i
].hy
) /* the last word is hyphenated */
333 lwid
+= f
->words
[i
].hy
;
335 lwid
+= f
->words
[i
].wid
;
337 lwid
+= f
->words
[i
+ 1].gap
;
338 if (lwid
> llen
&& pos
- i
> 1)
340 if (best
< 0 || fmt_findcost(f
, i
) < fmt_findcost(f
, best
))
347 static int fmt_head(struct fmt
*f
, int nreq
, int pos
)
351 if (nreq
<= 0 || f
->best_dep
[pos
] < nreq
)
353 for (i
= 1; i
< pos
&& f
->best_dep
[i
] <= nreq
; i
++) {
355 if (f
->best_dep
[i
] == nreq
&& !f
->words
[i
- 1].hy
)
358 return best
>= 0 ? best
: i
- 1;
361 /* break f->words[0..end] into lines according to fmt_bestpos() */
362 static int fmt_break(struct fmt
*f
, int end
)
364 int llen
, fmt_div
, fmt_rem
, beg
;
368 beg
= fmt_bestpos(f
, end
);
370 ret
+= fmt_break(f
, beg
);
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
++)
383 f
->words
[i
].gap
+= fmt_div
+ (fmt_rem
-- > 0);
385 l
->wid
= fmt_wordscopy(f
, beg
, end
, &l
->sbuf
, &l
->elsn
, &l
->elsp
);
388 return ret
+ (end
- beg
);
392 * fill the words collected in the buffer
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.
399 * The all argument forces fmt_fill() to fill all of the words.
400 * This is used for the \p escape sequence.
402 int fmt_fill(struct fmt
*f
, int nreq
, int all
)
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 */
410 /* not enough words to fill */
411 if (!all
&& fmt_wordslen(f
, 0, f
->nwords
) <= FMT_LLEN(f
))
413 if (nreq
> 0 && nreq
<= fmt_nlines(f
))
415 /* resetting positions */
416 for (i
= 0; i
< f
->nwords
+ 1; i
++)
418 end
= fmt_breakparagraph(f
, f
->nwords
, all
);
420 end_head
= fmt_head(f
, nreq
- fmt_nlines(f
), end
);
421 head
= end_head
< end
;
424 /* recursively add lines */
425 n
= fmt_break(f
, end
);
427 fmt_movewords(f
, 0, n
, f
->nwords
);
428 f
->filled
= n
&& !f
->nwords
;
431 if (f
->nwords
) /* apply the new .l and .i */
433 return head
|| n
!= end
;
436 struct fmt
*fmt_alloc(void)
438 struct fmt
*fmt
= malloc(sizeof(*fmt
));
439 memset(fmt
, 0, sizeof(*fmt
));
443 void fmt_free(struct fmt
*fmt
)
448 int fmt_wid(struct fmt
*fmt
)
450 return fmt_wordslen(fmt
, 0, fmt
->nwords
) +
451 (fmt
->nls
? FMT_SWID(fmt
) : fmt
->gap
);
454 int fmt_morewords(struct fmt
*fmt
)
456 return fmt_morelines(fmt
) || fmt
->nwords
;
459 int fmt_morelines(struct fmt
*fmt
)
461 return fmt
->l_head
!= fmt
->l_tail
;