2 * misc.c: miscellaneous useful items
9 return s
+ 1 + strlen(s
);
21 s
= snew(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
= sresize(s
->data
, s
->size
, void *);
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
= sresize(rs
->text
, rs
->size
, wchar_t);
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
= sresize(rs
->text
, rs
->size
, wchar_t);
76 ustrcpy(rs
->text
+ rs
->pos
, p
);
79 wchar_t *rdtrim(rdstring
*rs
) {
80 rs
->text
= sresize(rs
->text
, rs
->pos
+ 1, wchar_t);
84 void rdaddc(rdstringc
*rs
, char c
) {
85 if (rs
->pos
>= rs
->size
-1) {
86 rs
->size
= rs
->pos
+ 128;
87 rs
->text
= sresize(rs
->text
, rs
->size
, char);
89 rs
->text
[rs
->pos
++] = c
;
90 rs
->text
[rs
->pos
] = 0;
92 void rdaddsc(rdstringc
*rs
, char const *p
) {
93 rdaddsn(rs
, p
, strlen(p
));
95 void rdaddsn(rdstringc
*rs
, char const *p
, int len
) {
96 if (rs
->pos
>= rs
->size
- len
) {
97 rs
->size
= rs
->pos
+ len
+ 128;
98 rs
->text
= sresize(rs
->text
, rs
->size
, char);
100 memcpy(rs
->text
+ rs
->pos
, p
, len
);
102 rs
->text
[rs
->pos
] = 0;
104 char *rdtrimc(rdstringc
*rs
) {
105 rs
->text
= sresize(rs
->text
, rs
->pos
+ 1, char);
109 static int compare_wordlists_literally(word
*a
, word
*b
) {
112 if (a
->type
!= b
->type
)
113 return (a
->type
< b
->type ?
-1 : +1); /* FIXME? */
115 if ((t
!= word_Normal
&& t
!= word_Code
&&
116 t
!= word_WeakCode
&& t
!= word_Emph
) ||
119 if (a
->text
&& b
->text
) {
120 c
= ustricmp(a
->text
, b
->text
);
124 c
= compare_wordlists_literally(a
->alt
, b
->alt
);
130 wchar_t *ap
= a
->text
, *bp
= b
->text
;
132 wchar_t ac
= *ap
, bc
= *bp
;
134 return (ac
< bc ?
-1 : +1);
135 if (!*++ap
&& a
->next
&& a
->next
->type
== t
&& !a
->next
->alt
)
136 a
= a
->next
, ap
= a
->text
;
137 if (!*++bp
&& b
->next
&& b
->next
->type
== t
&& !b
->next
->alt
)
138 b
= b
->next
, bp
= b
->text
;
141 return (*ap ?
+1 : -1);
148 return (a ?
+1 : -1);
153 int compare_wordlists(word
*a
, word
*b
) {
155 * First we compare only the alphabetic content of the word
156 * lists, with case not a factor. If that comes out equal,
157 * _then_ we compare the word lists literally.
167 pos
[0].i
= pos
[1].i
= 0;
171 * Find the next alphabetic character in each word list.
175 for (k
= 0; k
< 2; k
++) {
177 * Advance until we hit either an alphabetic character
178 * or the end of the word list.
182 /* End of word list. */
185 } else if (!pos
[k
].w
->text
|| !pos
[k
].w
->text
[pos
[k
].i
]) {
186 /* No characters remaining in this word; move on. */
187 pos
[k
].w
= pos
[k
].w
->next
;
189 } else if (!uisalpha(pos
[k
].w
->text
[pos
[k
].i
])) {
190 /* This character isn't alphabetic; move on. */
193 /* We have an alphabetic! Lowercase it and continue. */
194 pos
[k
].c
= utolower(pos
[k
].w
->text
[pos
[k
].i
]);
214 if (pos
[0].c
< pos
[1].c
)
216 else if (pos
[0].c
> pos
[1].c
)
221 break; /* they're equal */
228 * If we reach here, the strings were alphabetically equal, so
229 * compare in more detail.
231 return compare_wordlists_literally(a
, b
);
234 void mark_attr_ends(word
*words
)
239 for (w
= words
; w
; w
= w
->next
) {
242 /* Invisible elements should not affect this calculation */
244 both
= (isattr(w
->type
) &&
245 wp
&& isattr(wp
->type
) &&
246 sameattr(wp
->type
, w
->type
));
247 w
->aux
|= both ? attr_Always
: attr_First
;
249 /* If previous considered word turns out to have been
250 * the end of a run, tidy it up. */
251 int wp_attr
= attraux(wp
->aux
);
252 wp
->aux
= (wp
->aux
& ~attr_mask
) |
253 ((wp_attr
== attr_Always
) ? attr_Last
254 /* attr_First */ : attr_Only
);
259 /* Tidy up last word touched */
261 int wp_attr
= attraux(wp
->aux
);
262 wp
->aux
= (wp
->aux
& ~attr_mask
) |
263 ((wp_attr
== attr_Always
) ? attr_Last
264 /* attr_First */ : attr_Only
);
269 * This function implements the optimal paragraph wrapping
270 * algorithm, pretty much as used in TeX. A cost function is
271 * defined for each line of the wrapped paragraph (typically some
272 * convex function of the difference between the line's length and
273 * its desired length), and a dynamic programming approach is used
274 * to optimise globally across all possible layouts of the
275 * paragraph to find the one with the minimum total cost.
277 * The function as implemented here gives a choice of two options
278 * for the cost function:
280 * - If `natural_space' is zero, then the algorithm attempts to
281 * make each line the maximum possible width (either `width' or
282 * `subsequentwidth' depending on whether it's the first line of
283 * the paragraph or not), and the cost function is simply the
284 * square of the unused space at the end of each line. This is a
285 * simple mechanism suitable for use in fixed-pitch environments
286 * such as plain text displayed on a terminal.
288 * - However, if `natural_space' is positive, the algorithm
289 * assumes the medium is fully graphical and that the width of
290 * space characters can be adjusted finely, and it attempts to
291 * make each _space character_ the width given in
292 * `natural_space'. (The provided width function should return
293 * the _minimum_ acceptable width of a space character in this
294 * case.) Therefore, the cost function for a line is dependent
295 * on the number of spaces on that line as well as the amount by
296 * which the line width differs from the optimum.
298 wrappedline
*wrap_para(word
*text
, int width
, int subsequentwidth
,
299 int (*widthfn
)(void *, word
*), void *ctx
,
301 wrappedline
*head
= NULL
, **ptr
= &head
;
302 int nwords
, wordsize
;
313 * Break the line up into wrappable components.
315 nwords
= wordsize
= 0;
318 if (nwords
>= wordsize
) {
319 wordsize
= nwords
+ 64;
320 wrapwords
= srealloc(wrapwords
, wordsize
* sizeof(*wrapwords
));
322 wrapwords
[nwords
].width
= 0;
323 wrapwords
[nwords
].begin
= text
;
325 wrapwords
[nwords
].width
+= widthfn(ctx
, text
);
326 wrapwords
[nwords
].end
= text
->next
;
327 if (text
->next
&& (text
->next
->type
== word_WhiteSpace
||
328 text
->next
->type
== word_EmphSpace
||
333 if (text
&& text
->next
&& (text
->next
->type
== word_WhiteSpace
||
334 text
->next
->type
== word_EmphSpace
)) {
335 wrapwords
[nwords
].spacewidth
= widthfn(ctx
, text
->next
);
338 wrapwords
[nwords
].spacewidth
= 0;
346 * Perform the dynamic wrapping algorithm: work backwards from
347 * nwords-1, determining the optimal wrapping for each terminal
348 * subsequence of the paragraph.
350 for (i
= nwords
; i
-- ;) {
354 int linelen
= 0, spacewidth
= 0, minspacewidth
= 0;
356 int thiswidth
= (i
== 0 ? width
: subsequentwidth
);
360 while (i
+j
< nwords
) {
362 * See what happens if we put j+1 words on this line.
366 minspacewidth
= spacewidth
;
368 linelen
+= spacewidth
+ wrapwords
[i
+j
].width
;
369 spacewidth
= wrapwords
[i
+j
].spacewidth
;
371 if (linelen
> thiswidth
) {
373 * If we're over the width limit, abandon ship,
374 * _unless_ there is no best-effort yet (which will
375 * only happen if the first word is too long all by
383 * Compute the cost of this line. The method of doing
384 * this differs hugely depending on whether
385 * natural_space is nonzero or not.
388 if (!nspaces
&& linelen
> thiswidth
) {
390 * Special case: if there are no spaces at all
391 * on the line because one single word is too
392 * long for its line, cost is zero because
393 * there's nothing we can do about it anyway.
397 int shortfall
= thiswidth
- linelen
;
398 int spaceextra
= shortfall
/ (nspaces ? nspaces
: 1);
399 int spaceshortfall
= natural_space
-
400 (minspacewidth
+ spaceextra
);
402 if (i
+j
== nwords
&& spaceshortfall
< 0) {
404 * Special case: on the very last line of
405 * the paragraph, we don't score penalty
406 * points for having to _stretch_ the line,
407 * since we won't stretch it anyway.
408 * However, we score penalties as normal
409 * for having to squeeze it.
414 * Squaring this number is tricky since
415 * it's liable to be quite big. Let's
416 * divide it through by 256.
418 int x
= spaceshortfall
>> 8;
419 int xf
= spaceshortfall
& 0xFF;
422 * Not counting strange variable-fixed-
423 * point oddities, we are computing
425 * (x+xf)^2 = x^2 + 2*x*xf + xf*xf
427 * except that _our_ xf is 256 times the
432 cost
+= (2 * x
* xf
) >> 8;
438 * Special case: if we're at the very end of the
439 * paragraph, we don't score penalty points for the
440 * white space left on the line.
444 cost
= (thiswidth
-linelen
) * (thiswidth
-linelen
);
449 * Add in the cost of wrapping all lines after this
453 cost
+= wrapwords
[i
+j
].cost
;
456 * We compare bestcost >= cost, not bestcost > cost,
457 * because in cases where the costs are identical we
458 * want to try to look like the greedy algorithm,
459 * because readers are likely to have spent a lot of
460 * time looking at greedy-wrapped paragraphs and
461 * there's no point violating the Principle of Least
462 * Surprise if it doesn't actually gain anything.
464 if (best
< 0 || bestcost
>= cost
) {
470 * Now we know the optimal answer for this terminal
471 * subsequence, so put it in wrapwords.
473 wrapwords
[i
].cost
= bestcost
;
474 wrapwords
[i
].nwords
= best
;
478 * We've wrapped the paragraph. Now build the output
479 * `wrappedline' list.
483 wrappedline
*w
= snew(wrappedline
);
488 n
= wrapwords
[i
].nwords
;
489 w
->begin
= wrapwords
[i
].begin
;
490 w
->end
= wrapwords
[i
+n
-1].end
;
493 * Count along the words to find nspaces and shortfall.
496 w
->shortfall
= width
;
497 for (j
= 0; j
< n
; j
++) {
498 w
->shortfall
-= wrapwords
[i
+j
].width
;
499 if (j
< n
-1 && wrapwords
[i
+j
].spacewidth
) {
501 w
->shortfall
-= wrapwords
[i
+j
].spacewidth
;
512 void wrap_free(wrappedline
*w
) {
514 wrappedline
*t
= w
->next
;
520 void cmdline_cfg_add(paragraph
*cfg
, char *string
)
523 int upos
, ulen
, pos
, len
;
526 while (cfg
->keyword
[ulen
])
527 ulen
+= 1 + ustrlen(cfg
->keyword
+ulen
);
529 while (cfg
->origkeyword
[len
])
530 len
+= 1 + strlen(cfg
->origkeyword
+len
);
532 ustring
= ufroma_locale_dup(string
);
535 ulen
+= 2 + ustrlen(ustring
);
536 cfg
->keyword
= sresize(cfg
->keyword
, ulen
, wchar_t);
537 ustrcpy(cfg
->keyword
+upos
, ustring
);
538 cfg
->keyword
[ulen
-1] = L
'\0';
541 len
+= 2 + strlen(string
);
542 cfg
->origkeyword
= sresize(cfg
->origkeyword
, len
, char);
543 strcpy(cfg
->origkeyword
+pos
, string
);
544 cfg
->origkeyword
[len
-1] = '\0';
549 paragraph
*cmdline_cfg_new(void)
554 memset(p
, 0, sizeof(*p
));
555 p
->type
= para_Config
;
557 p
->fpos
.filename
= "<command line>";
558 p
->fpos
.line
= p
->fpos
.col
= -1;
559 p
->keyword
= ustrdup(L
"\0");
560 p
->origkeyword
= dupstr("\0");
565 paragraph
*cmdline_cfg_simple(char *string
, ...)
571 p
= cmdline_cfg_new();
572 cmdline_cfg_add(p
, string
);
574 va_start(ap
, string
);
575 while ((s
= va_arg(ap
, char *)) != NULL
)
576 cmdline_cfg_add(p
, s
);