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