1 /* $OpenBSD: out.c,v 1.57 2021/10/17 21:03:05 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 struct roffsu su;
119 const struct tbl_opts *opts;
120 const struct tbl_span *sp;
121 const struct tbl_dat *dp;
122 struct roffcol *col;
123 struct tbl_colgroup *first_group, **gp, *g;
124 size_t *colwidth;
125 size_t ewidth, min1, min2, wanted, width, xwidth;
126 int done, icol, maxcol, necol, nxcol, quirkcol;
127
128 /*
129 * Allocate the master column specifiers. These will hold the
130 * widths and decimal positions for all cells in the column. It
131 * must be freed and nullified by the caller.
132 */
133
134 assert(tbl->cols == NULL);
135 tbl->cols = mandoc_calloc((size_t)sp_first->opts->cols,
136 sizeof(struct roffcol));
137 opts = sp_first->opts;
138
139 maxcol = -1;
140 first_group = NULL;
141 for (sp = sp_first; sp != NULL; sp = sp->next) {
142 if (sp->pos != TBL_SPAN_DATA)
143 continue;
144
145 /*
146 * Account for the data cells in the layout, matching it
147 * to data cells in the data section.
148 */
149
150 for (dp = sp->first; dp != NULL; dp = dp->next) {
151 icol = dp->layout->col;
152 while (maxcol < icol + dp->hspans)
153 tbl->cols[++maxcol].spacing = SIZE_MAX;
154 col = tbl->cols + icol;
155 col->flags |= dp->layout->flags;
156 if (dp->layout->flags & TBL_CELL_WIGN)
157 continue;
158
159 /* Handle explicit width specifications. */
160
161 if (dp->layout->wstr != NULL &&
162 dp->layout->width == 0 &&
163 a2roffsu(dp->layout->wstr, &su, SCALE_EN)
164 != NULL)
165 dp->layout->width =
166 (*tbl->sulen)(&su, tbl->arg);
167 if (col->width < dp->layout->width)
168 col->width = dp->layout->width;
169 if (dp->layout->spacing != SIZE_MAX &&
170 (col->spacing == SIZE_MAX ||
171 col->spacing < dp->layout->spacing))
172 col->spacing = dp->layout->spacing;
173
174 /*
175 * Calculate an automatic width.
176 * Except for spanning cells, apply it.
177 */
178
179 width = tblcalc_data(tbl,
180 dp->hspans == 0 ? col : NULL,
181 opts, dp,
182 dp->block == 0 ? 0 :
183 dp->layout->width ? dp->layout->width :
184 rmargin ? (rmargin + sp->opts->cols / 2)
185 / (sp->opts->cols + 1) : 0);
186 if (dp->hspans == 0)
187 continue;
188
189 /*
190 * Build a singly linked list
191 * of all groups of columns joined by spans,
192 * recording the minimum width for each group.
193 */
194
195 gp = &first_group;
196 while (*gp != NULL && ((*gp)->startcol != icol ||
197 (*gp)->endcol != icol + dp->hspans))
198 gp = &(*gp)->next;
199 if (*gp == NULL) {
200 g = mandoc_malloc(sizeof(*g));
201 g->next = *gp;
202 g->wanted = width;
203 g->startcol = icol;
204 g->endcol = icol + dp->hspans;
205 *gp = g;
206 } else if ((*gp)->wanted < width)
207 (*gp)->wanted = width;
208 }
209 }
210
211 /*
212 * The minimum width of columns explicitly specified
213 * in the layout is 1n.
214 */
215
216 if (maxcol < sp_first->opts->cols - 1)
217 maxcol = sp_first->opts->cols - 1;
218 for (icol = 0; icol <= maxcol; icol++) {
219 col = tbl->cols + icol;
220 if (col->width < 1)
221 col->width = 1;
222
223 /*
224 * Column spacings are needed for span width
225 * calculations, so set the default values now.
226 */
227
228 if (col->spacing == SIZE_MAX || icol == maxcol)
229 col->spacing = 3;
230 }
231
232 /*
233 * Replace the minimum widths with the missing widths,
234 * and dismiss groups that are already wide enough.
235 */
236
237 gp = &first_group;
238 while ((g = *gp) != NULL) {
239 done = 0;
240 for (icol = g->startcol; icol <= g->endcol; icol++) {
241 width = tbl->cols[icol].width;
242 if (icol < g->endcol)
243 width += tbl->cols[icol].spacing;
244 if (g->wanted <= width) {
245 done = 1;
246 break;
247 } else
248 g->wanted -= width;
249 }
250 if (done) {
251 *gp = g->next;
252 free(g);
253 } else
254 gp = &g->next;
255 }
256
257 colwidth = mandoc_reallocarray(NULL, maxcol + 1, sizeof(*colwidth));
258 while (first_group != NULL) {
259
260 /*
261 * Rebuild the array of the widths of all columns
262 * participating in spans that require expansion.
263 */
264
265 for (icol = 0; icol <= maxcol; icol++)
266 colwidth[icol] = SIZE_MAX;
267 for (g = first_group; g != NULL; g = g->next)
268 for (icol = g->startcol; icol <= g->endcol; icol++)
269 colwidth[icol] = tbl->cols[icol].width;
270
271 /*
272 * Find the smallest and second smallest column width
273 * among the columns which may need expamsion.
274 */
275
276 min1 = min2 = SIZE_MAX;
277 for (icol = 0; icol <= maxcol; icol++) {
278 width = colwidth[icol];
279 if (min1 > width) {
280 min2 = min1;
281 min1 = width;
282 } else if (min1 < width && min2 > width)
283 min2 = width;
284 }
285
286 /*
287 * Find the minimum wanted width
288 * for any one of the narrowest columns,
289 * and mark the columns wanting that width.
290 */
291
292 wanted = min2;
293 for (g = first_group; g != NULL; g = g->next) {
294 necol = 0;
295 for (icol = g->startcol; icol <= g->endcol; icol++)
296 if (colwidth[icol] == min1)
297 necol++;
298 if (necol == 0)
299 continue;
300 width = min1 + (g->wanted - 1) / necol + 1;
301 if (width > min2)
302 width = min2;
303 if (wanted > width)
304 wanted = width;
305 }
306
307 /* Record the effect of the widening. */
308
309 gp = &first_group;
310 while ((g = *gp) != NULL) {
311 done = 0;
312 for (icol = g->startcol; icol <= g->endcol; icol++) {
313 if (colwidth[icol] != min1)
314 continue;
315 if (g->wanted <= wanted - min1) {
316 tbl->cols[icol].width += g->wanted;
317 done = 1;
318 break;
319 }
320 tbl->cols[icol].width = wanted;
321 g->wanted -= wanted - min1;
322 }
323 if (done) {
324 *gp = g->next;
325 free(g);
326 } else
327 gp = &g->next;
328 }
329 }
330 free(colwidth);
331
332 /*
333 * Align numbers with text.
334 * Count columns to equalize and columns to maximize.
335 * Find maximum width of the columns to equalize.
336 * Find total width of the columns *not* to maximize.
337 */
338
339 necol = nxcol = 0;
340 ewidth = xwidth = 0;
341 for (icol = 0; icol <= maxcol; icol++) {
342 col = tbl->cols + icol;
343 if (col->width > col->nwidth)
344 col->decimal += (col->width - col->nwidth) / 2;
345 if (col->flags & TBL_CELL_EQUAL) {
346 necol++;
347 if (ewidth < col->width)
348 ewidth = col->width;
349 }
350 if (col->flags & TBL_CELL_WMAX)
351 nxcol++;
352 else
353 xwidth += col->width;
354 }
355
356 /*
357 * Equalize columns, if requested for any of them.
358 * Update total width of the columns not to maximize.
359 */
360
361 if (necol) {
362 for (icol = 0; icol <= maxcol; icol++) {
363 col = tbl->cols + icol;
364 if ( ! (col->flags & TBL_CELL_EQUAL))
365 continue;
366 if (col->width == ewidth)
367 continue;
368 if (nxcol && rmargin)
369 xwidth += ewidth - col->width;
370 col->width = ewidth;
371 }
372 }
373
374 /*
375 * If there are any columns to maximize, find the total
376 * available width, deducting 3n margins between columns.
377 * Distribute the available width evenly.
378 */
379
380 if (nxcol && rmargin) {
381 xwidth += 3*maxcol +
382 (opts->opts & (TBL_OPT_BOX | TBL_OPT_DBOX) ?
383 2 : !!opts->lvert + !!opts->rvert);
384 if (rmargin <= offset + xwidth)
385 return;
386 xwidth = rmargin - offset - xwidth;
387
388 /*
389 * Emulate a bug in GNU tbl width calculation that
390 * manifests itself for large numbers of x-columns.
391 * Emulating it for 5 x-columns gives identical
392 * behaviour for up to 6 x-columns.
393 */
394
395 if (nxcol == 5) {
396 quirkcol = xwidth % nxcol + 2;
397 if (quirkcol != 3 && quirkcol != 4)
398 quirkcol = -1;
399 } else
400 quirkcol = -1;
401
402 necol = 0;
403 ewidth = 0;
404 for (icol = 0; icol <= maxcol; icol++) {
405 col = tbl->cols + icol;
406 if ( ! (col->flags & TBL_CELL_WMAX))
407 continue;
408 col->width = (double)xwidth * ++necol / nxcol
409 - ewidth + 0.4995;
410 if (necol == quirkcol)
411 col->width--;
412 ewidth += col->width;
413 }
414 }
415 }
416
417 static size_t
tblcalc_data(struct rofftbl * tbl,struct roffcol * col,const struct tbl_opts * opts,const struct tbl_dat * dp,size_t mw)418 tblcalc_data(struct rofftbl *tbl, struct roffcol *col,
419 const struct tbl_opts *opts, const struct tbl_dat *dp, size_t mw)
420 {
421 size_t sz;
422
423 /* Branch down into data sub-types. */
424
425 switch (dp->layout->pos) {
426 case TBL_CELL_HORIZ:
427 case TBL_CELL_DHORIZ:
428 sz = (*tbl->len)(1, tbl->arg);
429 if (col != NULL && col->width < sz)
430 col->width = sz;
431 return sz;
432 case TBL_CELL_LONG:
433 case TBL_CELL_CENTRE:
434 case TBL_CELL_LEFT:
435 case TBL_CELL_RIGHT:
436 return tblcalc_literal(tbl, col, dp, mw);
437 case TBL_CELL_NUMBER:
438 return tblcalc_number(tbl, col, opts, dp);
439 case TBL_CELL_DOWN:
440 return 0;
441 default:
442 abort();
443 }
444 }
445
446 static size_t
tblcalc_literal(struct rofftbl * tbl,struct roffcol * col,const struct tbl_dat * dp,size_t mw)447 tblcalc_literal(struct rofftbl *tbl, struct roffcol *col,
448 const struct tbl_dat *dp, size_t mw)
449 {
450 const char *str; /* Beginning of the first line. */
451 const char *beg; /* Beginning of the current line. */
452 char *end; /* End of the current line. */
453 size_t lsz; /* Length of the current line. */
454 size_t wsz; /* Length of the current word. */
455 size_t msz; /* Length of the longest line. */
456
457 if (dp->string == NULL || *dp->string == '\0')
458 return 0;
459 str = mw ? mandoc_strdup(dp->string) : dp->string;
460 msz = lsz = 0;
461 for (beg = str; beg != NULL && *beg != '\0'; beg = end) {
462 end = mw ? strchr(beg, ' ') : NULL;
463 if (end != NULL) {
464 *end++ = '\0';
465 while (*end == ' ')
466 end++;
467 }
468 wsz = (*tbl->slen)(beg, tbl->arg);
469 if (mw && lsz && lsz + 1 + wsz <= mw)
470 lsz += 1 + wsz;
471 else
472 lsz = wsz;
473 if (msz < lsz)
474 msz = lsz;
475 }
476 if (mw)
477 free((void *)str);
478 if (col != NULL && col->width < msz)
479 col->width = msz;
480 return msz;
481 }
482
483 static size_t
tblcalc_number(struct rofftbl * tbl,struct roffcol * col,const struct tbl_opts * opts,const struct tbl_dat * dp)484 tblcalc_number(struct rofftbl *tbl, struct roffcol *col,
485 const struct tbl_opts *opts, const struct tbl_dat *dp)
486 {
487 const char *cp, *lastdigit, *lastpoint;
488 size_t intsz, totsz;
489 char buf[2];
490
491 if (dp->string == NULL || *dp->string == '\0')
492 return 0;
493
494 totsz = (*tbl->slen)(dp->string, tbl->arg);
495 if (col == NULL)
496 return totsz;
497
498 /*
499 * Find the last digit and
500 * the last decimal point that is adjacent to a digit.
501 * The alignment indicator "\&" overrides everything.
502 */
503
504 lastdigit = lastpoint = NULL;
505 for (cp = dp->string; cp[0] != '\0'; cp++) {
506 if (cp[0] == '\\' && cp[1] == '&') {
507 lastdigit = lastpoint = cp;
508 break;
509 } else if (cp[0] == opts->decimal &&
510 (isdigit((unsigned char)cp[1]) ||
511 (cp > dp->string && isdigit((unsigned char)cp[-1]))))
512 lastpoint = cp;
513 else if (isdigit((unsigned char)cp[0]))
514 lastdigit = cp;
515 }
516
517 /* Not a number, treat as a literal string. */
518
519 if (lastdigit == NULL) {
520 if (col != NULL && col->width < totsz)
521 col->width = totsz;
522 return totsz;
523 }
524
525 /* Measure the width of the integer part. */
526
527 if (lastpoint == NULL)
528 lastpoint = lastdigit + 1;
529 intsz = 0;
530 buf[1] = '\0';
531 for (cp = dp->string; cp < lastpoint; cp++) {
532 buf[0] = cp[0];
533 intsz += (*tbl->slen)(buf, tbl->arg);
534 }
535
536 /*
537 * If this number has more integer digits than all numbers
538 * seen on earlier lines, shift them all to the right.
539 * If it has fewer, shift this number to the right.
540 */
541
542 if (intsz > col->decimal) {
543 col->nwidth += intsz - col->decimal;
544 col->decimal = intsz;
545 } else
546 totsz += col->decimal - intsz;
547
548 /* Update the maximum total width seen so far. */
549
550 if (totsz > col->nwidth)
551 col->nwidth = totsz;
552 if (col->nwidth > col->width)
553 col->width = col->nwidth;
554 return totsz;
555 }
556