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(paragraph
*sourceform
) {
219 for (p
= sourceform
; p
; p
= p
->next
) {
221 for (w
= p
->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
));
237 * This function implements the optimal paragraph wrapping
238 * algorithm, pretty much as used in TeX. A cost function is
239 * defined for each line of the wrapped paragraph (typically some
240 * convex function of the difference between the line's length and
241 * its desired length), and a dynamic programming approach is used
242 * to optimise globally across all possible layouts of the
243 * paragraph to find the one with the minimum total cost.
245 * The function as implemented here gives a choice of two options
246 * for the cost function:
248 * - If `natural_space' is zero, then the algorithm attempts to
249 * make each line the maximum possible width (either `width' or
250 * `subsequentwidth' depending on whether it's the first line of
251 * the paragraph or not), and the cost function is simply the
252 * square of the unused space at the end of each line. This is a
253 * simple mechanism suitable for use in fixed-pitch environments
254 * such as plain text displayed on a terminal.
256 * - However, if `natural_space' is positive, the algorithm
257 * assumes the medium is fully graphical and that the width of
258 * space characters can be adjusted finely, and it attempts to
259 * make each _space character_ the width given in
260 * `natural_space'. (The provided width function should return
261 * the _minimum_ acceptable width of a space character in this
262 * case.) Therefore, the cost function for a line is dependent
263 * on the number of spaces on that line as well as the amount by
264 * which the line width differs from the optimum.
266 wrappedline
*wrap_para(word
*text
, int width
, int subsequentwidth
,
267 int (*widthfn
)(void *, word
*), void *ctx
,
269 wrappedline
*head
= NULL
, **ptr
= &head
;
270 int nwords
, wordsize
;
281 * Break the line up into wrappable components.
283 nwords
= wordsize
= 0;
286 if (nwords
>= wordsize
) {
287 wordsize
= nwords
+ 64;
288 wrapwords
= srealloc(wrapwords
, wordsize
* sizeof(*wrapwords
));
290 wrapwords
[nwords
].width
= 0;
291 wrapwords
[nwords
].begin
= text
;
293 wrapwords
[nwords
].width
+= widthfn(ctx
, text
);
294 wrapwords
[nwords
].end
= text
->next
;
295 if (text
->next
&& (text
->next
->type
== word_WhiteSpace
||
296 text
->next
->type
== word_EmphSpace
||
301 if (text
&& text
->next
&& (text
->next
->type
== word_WhiteSpace
||
302 text
->next
->type
== word_EmphSpace
)) {
303 wrapwords
[nwords
].spacewidth
= widthfn(ctx
, text
->next
);
306 wrapwords
[nwords
].spacewidth
= 0;
314 * Perform the dynamic wrapping algorithm: work backwards from
315 * nwords-1, determining the optimal wrapping for each terminal
316 * subsequence of the paragraph.
318 for (i
= nwords
; i
-- ;) {
322 int linelen
= 0, spacewidth
= 0, minspacewidth
= 0;
324 int thiswidth
= (i
== 0 ? width
: subsequentwidth
);
328 while (i
+j
< nwords
) {
330 * See what happens if we put j+1 words on this line.
334 minspacewidth
= spacewidth
;
336 linelen
+= spacewidth
+ wrapwords
[i
+j
].width
;
337 spacewidth
= wrapwords
[i
+j
].spacewidth
;
339 if (linelen
> thiswidth
) {
341 * If we're over the width limit, abandon ship,
342 * _unless_ there is no best-effort yet (which will
343 * only happen if the first word is too long all by
351 * Compute the cost of this line. The method of doing
352 * this differs hugely depending on whether
353 * natural_space is nonzero or not.
356 if (!nspaces
&& linelen
> thiswidth
) {
358 * Special case: if there are no spaces at all
359 * on the line because one single word is too
360 * long for its line, cost is zero because
361 * there's nothing we can do about it anyway.
365 int shortfall
= thiswidth
- linelen
;
366 int spaceextra
= shortfall
/ (nspaces ? nspaces
: 1);
367 int spaceshortfall
= natural_space
-
368 (minspacewidth
+ spaceextra
);
370 if (i
+j
== nwords
&& spaceshortfall
< 0) {
372 * Special case: on the very last line of
373 * the paragraph, we don't score penalty
374 * points for having to _stretch_ the line,
375 * since we won't stretch it anyway.
376 * However, we score penalties as normal
377 * for having to squeeze it.
382 * Squaring this number is tricky since
383 * it's liable to be quite big. Let's
384 * divide it through by 256.
386 int x
= spaceshortfall
>> 8;
387 int xf
= spaceshortfall
& 0xFF;
390 * Not counting strange variable-fixed-
391 * point oddities, we are computing
393 * (x+xf)^2 = x^2 + 2*x*xf + xf*xf
395 * except that _our_ xf is 256 times the
400 cost
+= (2 * x
* xf
) >> 8;
406 * Special case: if we're at the very end of the
407 * paragraph, we don't score penalty points for the
408 * white space left on the line.
412 cost
= (thiswidth
-linelen
) * (thiswidth
-linelen
);
417 * Add in the cost of wrapping all lines after this
421 cost
+= wrapwords
[i
+j
].cost
;
424 * We compare bestcost >= cost, not bestcost > cost,
425 * because in cases where the costs are identical we
426 * want to try to look like the greedy algorithm,
427 * because readers are likely to have spent a lot of
428 * time looking at greedy-wrapped paragraphs and
429 * there's no point violating the Principle of Least
430 * Surprise if it doesn't actually gain anything.
432 if (best
< 0 || bestcost
>= cost
) {
438 * Now we know the optimal answer for this terminal
439 * subsequence, so put it in wrapwords.
441 wrapwords
[i
].cost
= bestcost
;
442 wrapwords
[i
].nwords
= best
;
446 * We've wrapped the paragraph. Now build the output
447 * `wrappedline' list.
451 wrappedline
*w
= mknew(wrappedline
);
456 n
= wrapwords
[i
].nwords
;
457 w
->begin
= wrapwords
[i
].begin
;
458 w
->end
= wrapwords
[i
+n
-1].end
;
461 * Count along the words to find nspaces and shortfall.
464 w
->shortfall
= width
;
465 for (j
= 0; j
< n
; j
++) {
466 w
->shortfall
-= wrapwords
[i
+j
].width
;
467 if (j
< n
-1 && wrapwords
[i
+j
].spacewidth
) {
469 w
->shortfall
-= wrapwords
[i
+j
].spacewidth
;
480 void wrap_free(wrappedline
*w
) {
482 wrappedline
*t
= w
->next
;
488 void cmdline_cfg_add(paragraph
*cfg
, char *string
)
491 int upos
, ulen
, pos
, len
;
494 while (cfg
->keyword
[ulen
])
495 ulen
+= 1 + ustrlen(cfg
->keyword
+ulen
);
497 while (cfg
->origkeyword
[len
])
498 len
+= 1 + strlen(cfg
->origkeyword
+len
);
500 ustring
= ufroma_locale_dup(string
);
503 ulen
+= 2 + ustrlen(ustring
);
504 cfg
->keyword
= resize(cfg
->keyword
, ulen
);
505 ustrcpy(cfg
->keyword
+upos
, ustring
);
506 cfg
->keyword
[ulen
-1] = L
'\0';
509 len
+= 2 + strlen(string
);
510 cfg
->origkeyword
= resize(cfg
->origkeyword
, len
);
511 strcpy(cfg
->origkeyword
+pos
, string
);
512 cfg
->origkeyword
[len
-1] = '\0';
517 paragraph
*cmdline_cfg_new(void)
521 p
= mknew(paragraph
);
522 memset(p
, 0, sizeof(*p
));
523 p
->type
= para_Config
;
525 p
->fpos
.filename
= "<command line>";
526 p
->fpos
.line
= p
->fpos
.col
= -1;
527 p
->keyword
= ustrdup(L
"\0");
528 p
->origkeyword
= dupstr("\0");
533 paragraph
*cmdline_cfg_simple(char *string
, ...)
539 p
= cmdline_cfg_new();
540 cmdline_cfg_add(p
, string
);
542 va_start(ap
, string
);
543 while ((s
= va_arg(ap
, char *)) != NULL
)
544 cmdline_cfg_add(p
, s
);