1 /* $OpenBSD: out.c,v 1.58 2025/01/05 18:03:51 schwarze Exp $ */
2 /*
3 * Copyright (c) 2009, 2010, 2011 Kristaps Dzonsons <kristaps@bsd.lv>
4 * Copyright (c) 2011, 2014, 2015, 2017, 2018, 2019, 2021
5 * Ingo Schwarze <schwarze@openbsd.org>
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19 #include <sys/types.h>
20
21 #include <assert.h>
22 #include <ctype.h>
23 #include <stdint.h>
24 #include <stdio.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <time.h>
28
29 #include "mandoc_aux.h"
30 #include "mandoc.h"
31 #include "tbl.h"
32 #include "out.h"
33
34 struct tbl_colgroup {
35 struct tbl_colgroup *next;
36 size_t wanted;
37 int startcol;
38 int endcol;
39 };
40
41 static size_t tblcalc_data(struct rofftbl *, struct roffcol *,
42 const struct tbl_opts *, const struct tbl_dat *,
43 size_t);
44 static size_t tblcalc_literal(struct rofftbl *, struct roffcol *,
45 const struct tbl_dat *, size_t);
46 static size_t tblcalc_number(struct rofftbl *, struct roffcol *,
47 const struct tbl_opts *, const struct tbl_dat *);
48
49
50 /*
51 * Parse the *src string and store a scaling unit into *dst.
52 * If the string doesn't specify the unit, use the default.
53 * If no default is specified, fail.
54 * Return a pointer to the byte after the last byte used,
55 * or NULL on total failure.
56 */
57 const char *
a2roffsu(const char * src,struct roffsu * dst,enum roffscale def)58 a2roffsu(const char *src, struct roffsu *dst, enum roffscale def)
59 {
60 char *endptr;
61
62 dst->unit = def == SCALE_MAX ? SCALE_BU : def;
63 dst->scale = strtod(src, &endptr);
64 if (endptr == src)
65 return NULL;
66
67 switch (*endptr++) {
68 case 'c':
69 dst->unit = SCALE_CM;
70 break;
71 case 'i':
72 dst->unit = SCALE_IN;
73 break;
74 case 'f':
75 dst->unit = SCALE_FS;
76 break;
77 case 'M':
78 dst->unit = SCALE_MM;
79 break;
80 case 'm':
81 dst->unit = SCALE_EM;
82 break;
83 case 'n':
84 dst->unit = SCALE_EN;
85 break;
86 case 'P':
87 dst->unit = SCALE_PC;
88 break;
89 case 'p':
90 dst->unit = SCALE_PT;
91 break;
92 case 'u':
93 dst->unit = SCALE_BU;
94 break;
95 case 'v':
96 dst->unit = SCALE_VS;
97 break;
98 default:
99 endptr--;
100 if (SCALE_MAX == def)
101 return NULL;
102 dst->unit = def;
103 break;
104 }
105 return endptr;
106 }
107
108 /*
109 * Calculate the abstract widths and decimal positions of columns in a
110 * table. This routine allocates the columns structures then runs over
111 * all rows and cells in the table. The function pointers in "tbl" are
112 * used for the actual width calculations.
113 */
114 void
tblcalc(struct rofftbl * tbl,const struct tbl_span * sp_first,size_t offset,size_t rmargin)115 tblcalc(struct rofftbl *tbl, const struct tbl_span *sp_first,
116 size_t offset, size_t rmargin)
117 {
118 const struct tbl_opts *opts;
119 const struct tbl_span *sp;
120 const struct tbl_dat *dp;
121 struct roffcol *col;
122 struct tbl_colgroup *first_group, **gp, *g;
123 size_t *colwidth;
124 size_t ewidth, min1, min2, wanted, width, xwidth;
125 int done, icol, maxcol, necol, nxcol, quirkcol;
126
127 /*
128 * Allocate the master column specifiers. These will hold the
129 * widths and decimal positions for all cells in the column. It
130 * must be freed and nullified by the caller.
131 */
132
133 assert(tbl->cols == NULL);
134 tbl->cols = mandoc_calloc((size_t)sp_first->opts->cols,
135 sizeof(struct roffcol));
136 opts = sp_first->opts;
137
138 maxcol = -1;
139 first_group = NULL;
140 for (sp = sp_first; sp != NULL; sp = sp->next) {
141 if (sp->pos != TBL_SPAN_DATA)
142 continue;
143
144 /*
145 * Account for the data cells in the layout, matching it
146 * to data cells in the data section.
147 */
148
149 for (dp = sp->first; dp != NULL; dp = dp->next) {
150 icol = dp->layout->col;
151 while (maxcol < icol + dp->hspans)
152 tbl->cols[++maxcol].spacing = SIZE_MAX;
153 col = tbl->cols + icol;
154 col->flags |= dp->layout->flags;
155 if (dp->layout->flags & TBL_CELL_WIGN)
156 continue;
157
158 /* Handle explicit width specifications. */
159 if (col->width < dp->layout->width)
160 col->width = dp->layout->width;
161 if (dp->layout->spacing != SIZE_MAX &&
162 (col->spacing == SIZE_MAX ||
163 col->spacing < dp->layout->spacing))
164 col->spacing = dp->layout->spacing;
165
166 /*
167 * Calculate an automatic width.
168 * Except for spanning cells, apply it.
169 */
170
171 width = tblcalc_data(tbl,
172 dp->hspans == 0 ? col : NULL,
173 opts, dp,
174 dp->block == 0 ? 0 :
175 dp->layout->width ? dp->layout->width :
176 rmargin ? (rmargin + sp->opts->cols / 2)
177 / (sp->opts->cols + 1) : 0);
178 if (dp->hspans == 0)
179 continue;
180
181 /*
182 * Build a singly linked list
183 * of all groups of columns joined by spans,
184 * recording the minimum width for each group.
185 */
186
187 gp = &first_group;
188 while (*gp != NULL && ((*gp)->startcol != icol ||
189 (*gp)->endcol != icol + dp->hspans))
190 gp = &(*gp)->next;
191 if (*gp == NULL) {
192 g = mandoc_malloc(sizeof(*g));
193 g->next = *gp;
194 g->wanted = width;
195 g->startcol = icol;
196 g->endcol = icol + dp->hspans;
197 *gp = g;
198 } else if ((*gp)->wanted < width)
199 (*gp)->wanted = width;
200 }
201 }
202
203 /*
204 * The minimum width of columns explicitly specified
205 * in the layout is 1n.
206 */
207
208 if (maxcol < sp_first->opts->cols - 1)
209 maxcol = sp_first->opts->cols - 1;
210 for (icol = 0; icol <= maxcol; icol++) {
211 col = tbl->cols + icol;
212 if (col->width < 1)
213 col->width = 1;
214
215 /*
216 * Column spacings are needed for span width
217 * calculations, so set the default values now.
218 */
219
220 if (col->spacing == SIZE_MAX || icol == maxcol)
221 col->spacing = 3;
222 }
223
224 /*
225 * Replace the minimum widths with the missing widths,
226 * and dismiss groups that are already wide enough.
227 */
228
229 gp = &first_group;
230 while ((g = *gp) != NULL) {
231 done = 0;
232 for (icol = g->startcol; icol <= g->endcol; icol++) {
233 width = tbl->cols[icol].width;
234 if (icol < g->endcol)
235 width += tbl->cols[icol].spacing;
236 if (g->wanted <= width) {
237 done = 1;
238 break;
239 } else
240 g->wanted -= width;
241 }
242 if (done) {
243 *gp = g->next;
244 free(g);
245 } else
246 gp = &g->next;
247 }
248
249 colwidth = mandoc_reallocarray(NULL, maxcol + 1, sizeof(*colwidth));
250 while (first_group != NULL) {
251
252 /*
253 * Rebuild the array of the widths of all columns
254 * participating in spans that require expansion.
255 */
256
257 for (icol = 0; icol <= maxcol; icol++)
258 colwidth[icol] = SIZE_MAX;
259 for (g = first_group; g != NULL; g = g->next)
260 for (icol = g->startcol; icol <= g->endcol; icol++)
261 colwidth[icol] = tbl->cols[icol].width;
262
263 /*
264 * Find the smallest and second smallest column width
265 * among the columns which may need expamsion.
266 */
267
268 min1 = min2 = SIZE_MAX;
269 for (icol = 0; icol <= maxcol; icol++) {
270 width = colwidth[icol];
271 if (min1 > width) {
272 min2 = min1;
273 min1 = width;
274 } else if (min1 < width && min2 > width)
275 min2 = width;
276 }
277
278 /*
279 * Find the minimum wanted width
280 * for any one of the narrowest columns,
281 * and mark the columns wanting that width.
282 */
283
284 wanted = min2;
285 for (g = first_group; g != NULL; g = g->next) {
286 necol = 0;
287 for (icol = g->startcol; icol <= g->endcol; icol++)
288 if (colwidth[icol] == min1)
289 necol++;
290 if (necol == 0)
291 continue;
292 width = min1 + (g->wanted - 1) / necol + 1;
293 if (width > min2)
294 width = min2;
295 if (wanted > width)
296 wanted = width;
297 }
298
299 /* Record the effect of the widening. */
300
301 gp = &first_group;
302 while ((g = *gp) != NULL) {
303 done = 0;
304 for (icol = g->startcol; icol <= g->endcol; icol++) {
305 if (colwidth[icol] != min1)
306 continue;
307 if (g->wanted <= wanted - min1) {
308 tbl->cols[icol].width += g->wanted;
309 done = 1;
310 break;
311 }
312 tbl->cols[icol].width = wanted;
313 g->wanted -= wanted - min1;
314 }
315 if (done) {
316 *gp = g->next;
317 free(g);
318 } else
319 gp = &g->next;
320 }
321 }
322 free(colwidth);
323
324 /*
325 * Align numbers with text.
326 * Count columns to equalize and columns to maximize.
327 * Find maximum width of the columns to equalize.
328 * Find total width of the columns *not* to maximize.
329 */
330
331 necol = nxcol = 0;
332 ewidth = xwidth = 0;
333 for (icol = 0; icol <= maxcol; icol++) {
334 col = tbl->cols + icol;
335 if (col->width > col->nwidth)
336 col->decimal += (col->width - col->nwidth) / 2;
337 if (col->flags & TBL_CELL_EQUAL) {
338 necol++;
339 if (ewidth < col->width)
340 ewidth = col->width;
341 }
342 if (col->flags & TBL_CELL_WMAX)
343 nxcol++;
344 else
345 xwidth += col->width;
346 }
347
348 /*
349 * Equalize columns, if requested for any of them.
350 * Update total width of the columns not to maximize.
351 */
352
353 if (necol) {
354 for (icol = 0; icol <= maxcol; icol++) {
355 col = tbl->cols + icol;
356 if ( ! (col->flags & TBL_CELL_EQUAL))
357 continue;
358 if (col->width == ewidth)
359 continue;
360 if (nxcol && rmargin)
361 xwidth += ewidth - col->width;
362 col->width = ewidth;
363 }
364 }
365
366 /*
367 * If there are any columns to maximize, find the total
368 * available width, deducting 3n margins between columns.
369 * Distribute the available width evenly.
370 */
371
372 if (nxcol && rmargin) {
373 xwidth += 3*maxcol +
374 (opts->opts & (TBL_OPT_BOX | TBL_OPT_DBOX) ?
375 2 : !!opts->lvert + !!opts->rvert);
376 if (rmargin <= offset + xwidth)
377 return;
378 xwidth = rmargin - offset - xwidth;
379
380 /*
381 * Emulate a bug in GNU tbl width calculation that
382 * manifests itself for large numbers of x-columns.
383 * Emulating it for 5 x-columns gives identical
384 * behaviour for up to 6 x-columns.
385 */
386
387 if (nxcol == 5) {
388 quirkcol = xwidth % nxcol + 2;
389 if (quirkcol != 3 && quirkcol != 4)
390 quirkcol = -1;
391 } else
392 quirkcol = -1;
393
394 necol = 0;
395 ewidth = 0;
396 for (icol = 0; icol <= maxcol; icol++) {
397 col = tbl->cols + icol;
398 if ( ! (col->flags & TBL_CELL_WMAX))
399 continue;
400 col->width = (double)xwidth * ++necol / nxcol
401 - ewidth + 0.4995;
402 if (necol == quirkcol)
403 col->width--;
404 ewidth += col->width;
405 }
406 }
407 }
408
409 static size_t
tblcalc_data(struct rofftbl * tbl,struct roffcol * col,const struct tbl_opts * opts,const struct tbl_dat * dp,size_t mw)410 tblcalc_data(struct rofftbl *tbl, struct roffcol *col,
411 const struct tbl_opts *opts, const struct tbl_dat *dp, size_t mw)
412 {
413 size_t sz;
414
415 /* Branch down into data sub-types. */
416
417 switch (dp->layout->pos) {
418 case TBL_CELL_HORIZ:
419 case TBL_CELL_DHORIZ:
420 sz = (*tbl->len)(1, tbl->arg);
421 if (col != NULL && col->width < sz)
422 col->width = sz;
423 return sz;
424 case TBL_CELL_LONG:
425 case TBL_CELL_CENTRE:
426 case TBL_CELL_LEFT:
427 case TBL_CELL_RIGHT:
428 return tblcalc_literal(tbl, col, dp, mw);
429 case TBL_CELL_NUMBER:
430 return tblcalc_number(tbl, col, opts, dp);
431 case TBL_CELL_DOWN:
432 return 0;
433 default:
434 abort();
435 }
436 }
437
438 static size_t
tblcalc_literal(struct rofftbl * tbl,struct roffcol * col,const struct tbl_dat * dp,size_t mw)439 tblcalc_literal(struct rofftbl *tbl, struct roffcol *col,
440 const struct tbl_dat *dp, size_t mw)
441 {
442 const char *str; /* Beginning of the first line. */
443 const char *beg; /* Beginning of the current line. */
444 char *end; /* End of the current line. */
445 size_t lsz; /* Length of the current line. */
446 size_t wsz; /* Length of the current word. */
447 size_t msz; /* Length of the longest line. */
448
449 if (dp->string == NULL || *dp->string == '\0')
450 return 0;
451 str = mw ? mandoc_strdup(dp->string) : dp->string;
452 msz = lsz = 0;
453 for (beg = str; beg != NULL && *beg != '\0'; beg = end) {
454 end = mw ? strchr(beg, ' ') : NULL;
455 if (end != NULL) {
456 *end++ = '\0';
457 while (*end == ' ')
458 end++;
459 }
460 wsz = (*tbl->slen)(beg, tbl->arg);
461 if (mw && lsz && lsz + 1 + wsz <= mw)
462 lsz += 1 + wsz;
463 else
464 lsz = wsz;
465 if (msz < lsz)
466 msz = lsz;
467 }
468 if (mw)
469 free((void *)str);
470 if (col != NULL && col->width < msz)
471 col->width = msz;
472 return msz;
473 }
474
475 static size_t
tblcalc_number(struct rofftbl * tbl,struct roffcol * col,const struct tbl_opts * opts,const struct tbl_dat * dp)476 tblcalc_number(struct rofftbl *tbl, struct roffcol *col,
477 const struct tbl_opts *opts, const struct tbl_dat *dp)
478 {
479 const char *cp, *lastdigit, *lastpoint;
480 size_t intsz, totsz;
481 char buf[2];
482
483 if (dp->string == NULL || *dp->string == '\0')
484 return 0;
485
486 totsz = (*tbl->slen)(dp->string, tbl->arg);
487 if (col == NULL)
488 return totsz;
489
490 /*
491 * Find the last digit and
492 * the last decimal point that is adjacent to a digit.
493 * The alignment indicator "\&" overrides everything.
494 */
495
496 lastdigit = lastpoint = NULL;
497 for (cp = dp->string; cp[0] != '\0'; cp++) {
498 if (cp[0] == '\\' && cp[1] == '&') {
499 lastdigit = lastpoint = cp;
500 break;
501 } else if (cp[0] == opts->decimal &&
502 (isdigit((unsigned char)cp[1]) ||
503 (cp > dp->string && isdigit((unsigned char)cp[-1]))))
504 lastpoint = cp;
505 else if (isdigit((unsigned char)cp[0]))
506 lastdigit = cp;
507 }
508
509 /* Not a number, treat as a literal string. */
510
511 if (lastdigit == NULL) {
512 if (col != NULL && col->width < totsz)
513 col->width = totsz;
514 return totsz;
515 }
516
517 /* Measure the width of the integer part. */
518
519 if (lastpoint == NULL)
520 lastpoint = lastdigit + 1;
521 intsz = 0;
522 buf[1] = '\0';
523 for (cp = dp->string; cp < lastpoint; cp++) {
524 buf[0] = cp[0];
525 intsz += (*tbl->slen)(buf, tbl->arg);
526 }
527
528 /*
529 * If this number has more integer digits than all numbers
530 * seen on earlier lines, shift them all to the right.
531 * If it has fewer, shift this number to the right.
532 */
533
534 if (intsz > col->decimal) {
535 col->nwidth += intsz - col->decimal;
536 col->decimal = intsz;
537 } else
538 totsz += col->decimal - intsz;
539
540 /* Update the maximum total width seen so far. */
541
542 if (totsz > col->nwidth)
543 col->nwidth = totsz;
544 if (col->nwidth > col->width)
545 col->width = col->nwidth;
546 return totsz;
547 }
548