2 * misc.c: miscellaneous useful items
9 return s
+ 1 + strlen(s
);
21 s
= mknew(struct stackTag
);
29 void stk_free(stack s
) {
34 void stk_push(stack s
, void *item
) {
35 if (s
->size
<= s
->sp
) {
37 s
->data
= resize(s
->data
, s
->size
);
39 s
->data
[s
->sp
++] = item
;
42 void *stk_pop(stack s
) {
44 return s
->data
[--s
->sp
];
49 void *stk_top(stack s
) {
51 return s
->data
[s
->sp
-1];
57 * Small routines to amalgamate a string from an input source.
59 const rdstring empty_rdstring
= {0, 0, NULL
};
60 const rdstringc empty_rdstringc
= {0, 0, NULL
};
62 void rdadd(rdstring
*rs
, wchar_t c
) {
63 if (rs
->pos
>= rs
->size
-1) {
64 rs
->size
= rs
->pos
+ 128;
65 rs
->text
= resize(rs
->text
, rs
->size
);
67 rs
->text
[rs
->pos
++] = c
;
68 rs
->text
[rs
->pos
] = 0;
70 void rdadds(rdstring
*rs
, wchar_t const *p
) {
72 if (rs
->pos
>= rs
->size
- len
) {
73 rs
->size
= rs
->pos
+ len
+ 128;
74 rs
->text
= resize(rs
->text
, rs
->size
);
76 ustrcpy(rs
->text
+ rs
->pos
, p
);
79 wchar_t *rdtrim(rdstring
*rs
) {
80 rs
->text
= resize(rs
->text
, rs
->pos
+ 1);
84 void rdaddc(rdstringc
*rs
, char c
) {
85 if (rs
->pos
>= rs
->size
-1) {
86 rs
->size
= rs
->pos
+ 128;
87 rs
->text
= resize(rs
->text
, rs
->size
);
89 rs
->text
[rs
->pos
++] = c
;
90 rs
->text
[rs
->pos
] = 0;
92 void rdaddsc(rdstringc
*rs
, char const *p
) {
94 if (rs
->pos
>= rs
->size
- len
) {
95 rs
->size
= rs
->pos
+ len
+ 128;
96 rs
->text
= resize(rs
->text
, rs
->size
);
98 strcpy(rs
->text
+ rs
->pos
, p
);
101 char *rdtrimc(rdstringc
*rs
) {
102 rs
->text
= resize(rs
->text
, rs
->pos
+ 1);
106 static int compare_wordlists_literally(word
*a
, word
*b
) {
109 if (a
->type
!= b
->type
)
110 return (a
->type
< b
->type ?
-1 : +1); /* FIXME? */
112 if ((t
!= word_Normal
&& t
!= word_Code
&&
113 t
!= word_WeakCode
&& t
!= word_Emph
) ||
116 if (a
->text
&& b
->text
) {
117 c
= ustricmp(a
->text
, b
->text
);
121 c
= compare_wordlists_literally(a
->alt
, b
->alt
);
127 wchar_t *ap
= a
->text
, *bp
= b
->text
;
129 wchar_t ac
= utolower(*ap
), bc
= utolower(*bp
);
131 return (ac
< bc ?
-1 : +1);
132 if (!*++ap
&& a
->next
&& a
->next
->type
== t
&& !a
->next
->alt
)
133 a
= a
->next
, ap
= a
->text
;
134 if (!*++bp
&& b
->next
&& b
->next
->type
== t
&& !b
->next
->alt
)
135 b
= b
->next
, bp
= b
->text
;
138 return (*ap ?
+1 : -1);
145 return (a ?
+1 : -1);
150 int compare_wordlists(word
*a
, word
*b
) {
152 * First we compare only the alphabetic content of the word
153 * lists, with case not a factor. If that comes out equal,
154 * _then_ we compare the word lists literally.
164 pos
[0].i
= pos
[1].i
= 0;
168 * Find the next alphabetic character in each word list.
172 for (k
= 0; k
< 2; k
++) {
174 * Advance until we hit either an alphabetic character
175 * or the end of the word list.
179 /* End of word list. */
182 } else if (!pos
[k
].w
->text
|| !pos
[k
].w
->text
[pos
[k
].i
]) {
183 /* No characters remaining in this word; move on. */
184 pos
[k
].w
= pos
[k
].w
->next
;
186 } else if (!uisalpha(pos
[k
].w
->text
[pos
[k
].i
])) {
187 /* This character isn't alphabetic; move on. */
190 /* We have an alphabetic! Lowercase it and continue. */
191 pos
[k
].c
= utolower(pos
[k
].w
->text
[pos
[k
].i
]);
197 if (pos
[0].c
< pos
[1].c
)
199 else if (pos
[0].c
> pos
[1].c
)
203 break; /* they're equal */
210 * If we reach here, the strings were alphabetically equal, so
211 * compare in more detail.
213 return compare_wordlists_literally(a
, b
);
216 void mark_attr_ends(word
*words
)
221 for (w
= words
; w
; w
= w
->next
) {
222 if (isattr(w
->type
)) {
223 int before
= (wp
&& isattr(wp
->type
) &&
224 sameattr(wp
->type
, w
->type
));
225 int after
= (w
->next
&& isattr(w
->next
->type
) &&
226 sameattr(w
->next
->type
, w
->type
));
228 (after ? attr_Always
: attr_Last
) :
229 (after ? attr_First
: attr_Only
));
236 * This function implements the optimal paragraph wrapping
237 * algorithm, pretty much as used in TeX. A cost function is
238 * defined for each line of the wrapped paragraph (typically some
239 * convex function of the difference between the line's length and
240 * its desired length), and a dynamic programming approach is used
241 * to optimise globally across all possible layouts of the
242 * paragraph to find the one with the minimum total cost.
244 * The function as implemented here gives a choice of two options
245 * for the cost function:
247 * - If `natural_space' is zero, then the algorithm attempts to
248 * make each line the maximum possible width (either `width' or
249 * `subsequentwidth' depending on whether it's the first line of
250 * the paragraph or not), and the cost function is simply the
251 * square of the unused space at the end of each line. This is a
252 * simple mechanism suitable for use in fixed-pitch environments
253 * such as plain text displayed on a terminal.
255 * - However, if `natural_space' is positive, the algorithm
256 * assumes the medium is fully graphical and that the width of
257 * space characters can be adjusted finely, and it attempts to
258 * make each _space character_ the width given in
259 * `natural_space'. (The provided width function should return
260 * the _minimum_ acceptable width of a space character in this
261 * case.) Therefore, the cost function for a line is dependent
262 * on the number of spaces on that line as well as the amount by
263 * which the line width differs from the optimum.
265 wrappedline
*wrap_para(word
*text
, int width
, int subsequentwidth
,
266 int (*widthfn
)(void *, word
*), void *ctx
,
268 wrappedline
*head
= NULL
, **ptr
= &head
;
269 int nwords
, wordsize
;
280 * Break the line up into wrappable components.
282 nwords
= wordsize
= 0;
285 if (nwords
>= wordsize
) {
286 wordsize
= nwords
+ 64;
287 wrapwords
= srealloc(wrapwords
, wordsize
* sizeof(*wrapwords
));
289 wrapwords
[nwords
].width
= 0;
290 wrapwords
[nwords
].begin
= text
;
292 wrapwords
[nwords
].width
+= widthfn(ctx
, text
);
293 wrapwords
[nwords
].end
= text
->next
;
294 if (text
->next
&& (text
->next
->type
== word_WhiteSpace
||
295 text
->next
->type
== word_EmphSpace
||
300 if (text
&& text
->next
&& (text
->next
->type
== word_WhiteSpace
||
301 text
->next
->type
== word_EmphSpace
)) {
302 wrapwords
[nwords
].spacewidth
= widthfn(ctx
, text
->next
);
305 wrapwords
[nwords
].spacewidth
= 0;
313 * Perform the dynamic wrapping algorithm: work backwards from
314 * nwords-1, determining the optimal wrapping for each terminal
315 * subsequence of the paragraph.
317 for (i
= nwords
; i
-- ;) {
321 int linelen
= 0, spacewidth
= 0, minspacewidth
= 0;
323 int thiswidth
= (i
== 0 ? width
: subsequentwidth
);
327 while (i
+j
< nwords
) {
329 * See what happens if we put j+1 words on this line.
333 minspacewidth
= spacewidth
;
335 linelen
+= spacewidth
+ wrapwords
[i
+j
].width
;
336 spacewidth
= wrapwords
[i
+j
].spacewidth
;
338 if (linelen
> thiswidth
) {
340 * If we're over the width limit, abandon ship,
341 * _unless_ there is no best-effort yet (which will
342 * only happen if the first word is too long all by
350 * Compute the cost of this line. The method of doing
351 * this differs hugely depending on whether
352 * natural_space is nonzero or not.
355 if (!nspaces
&& linelen
> thiswidth
) {
357 * Special case: if there are no spaces at all
358 * on the line because one single word is too
359 * long for its line, cost is zero because
360 * there's nothing we can do about it anyway.
364 int shortfall
= thiswidth
- linelen
;
365 int spaceextra
= shortfall
/ (nspaces ? nspaces
: 1);
366 int spaceshortfall
= natural_space
-
367 (minspacewidth
+ spaceextra
);
369 if (i
+j
== nwords
&& spaceshortfall
< 0) {
371 * Special case: on the very last line of
372 * the paragraph, we don't score penalty
373 * points for having to _stretch_ the line,
374 * since we won't stretch it anyway.
375 * However, we score penalties as normal
376 * for having to squeeze it.
381 * Squaring this number is tricky since
382 * it's liable to be quite big. Let's
383 * divide it through by 256.
385 int x
= spaceshortfall
>> 8;
386 int xf
= spaceshortfall
& 0xFF;
389 * Not counting strange variable-fixed-
390 * point oddities, we are computing
392 * (x+xf)^2 = x^2 + 2*x*xf + xf*xf
394 * except that _our_ xf is 256 times the
399 cost
+= (2 * x
* xf
) >> 8;
405 * Special case: if we're at the very end of the
406 * paragraph, we don't score penalty points for the
407 * white space left on the line.
411 cost
= (thiswidth
-linelen
) * (thiswidth
-linelen
);
416 * Add in the cost of wrapping all lines after this
420 cost
+= wrapwords
[i
+j
].cost
;
423 * We compare bestcost >= cost, not bestcost > cost,
424 * because in cases where the costs are identical we
425 * want to try to look like the greedy algorithm,
426 * because readers are likely to have spent a lot of
427 * time looking at greedy-wrapped paragraphs and
428 * there's no point violating the Principle of Least
429 * Surprise if it doesn't actually gain anything.
431 if (best
< 0 || bestcost
>= cost
) {
437 * Now we know the optimal answer for this terminal
438 * subsequence, so put it in wrapwords.
440 wrapwords
[i
].cost
= bestcost
;
441 wrapwords
[i
].nwords
= best
;
445 * We've wrapped the paragraph. Now build the output
446 * `wrappedline' list.
450 wrappedline
*w
= mknew(wrappedline
);
455 n
= wrapwords
[i
].nwords
;
456 w
->begin
= wrapwords
[i
].begin
;
457 w
->end
= wrapwords
[i
+n
-1].end
;
460 * Count along the words to find nspaces and shortfall.
463 w
->shortfall
= width
;
464 for (j
= 0; j
< n
; j
++) {
465 w
->shortfall
-= wrapwords
[i
+j
].width
;
466 if (j
< n
-1 && wrapwords
[i
+j
].spacewidth
) {
468 w
->shortfall
-= wrapwords
[i
+j
].spacewidth
;
479 void wrap_free(wrappedline
*w
) {
481 wrappedline
*t
= w
->next
;
487 void cmdline_cfg_add(paragraph
*cfg
, char *string
)
490 int upos
, ulen
, pos
, len
;
493 while (cfg
->keyword
[ulen
])
494 ulen
+= 1 + ustrlen(cfg
->keyword
+ulen
);
496 while (cfg
->origkeyword
[len
])
497 len
+= 1 + strlen(cfg
->origkeyword
+len
);
499 ustring
= ufroma_locale_dup(string
);
502 ulen
+= 2 + ustrlen(ustring
);
503 cfg
->keyword
= resize(cfg
->keyword
, ulen
);
504 ustrcpy(cfg
->keyword
+upos
, ustring
);
505 cfg
->keyword
[ulen
-1] = L
'\0';
508 len
+= 2 + strlen(string
);
509 cfg
->origkeyword
= resize(cfg
->origkeyword
, len
);
510 strcpy(cfg
->origkeyword
+pos
, string
);
511 cfg
->origkeyword
[len
-1] = '\0';
516 paragraph
*cmdline_cfg_new(void)
520 p
= mknew(paragraph
);
521 memset(p
, 0, sizeof(*p
));
522 p
->type
= para_Config
;
524 p
->fpos
.filename
= "<command line>";
525 p
->fpos
.line
= p
->fpos
.col
= -1;
526 p
->keyword
= ustrdup(L
"\0");
527 p
->origkeyword
= dupstr("\0");
532 paragraph
*cmdline_cfg_simple(char *string
, ...)
538 p
= cmdline_cfg_new();
539 cmdline_cfg_add(p
, string
);
541 va_start(ap
, string
);
542 while ((s
= va_arg(ap
, char *)) != NULL
)
543 cmdline_cfg_add(p
, s
);