xref: /freebsd/contrib/mandoc/out.c (revision 6be3386466ab79a84b48429ae66244f21526d3df) 
1 /*	$Id: out.c,v 1.78 2019/03/29 21:27:06 schwarze Exp $ */
2 /*
3  * Copyright (c) 2009, 2010, 2011 Kristaps Dzonsons <kristaps@bsd.lv>
4  * Copyright (c) 2011,2014,2015,2017,2018 Ingo Schwarze <schwarze@openbsd.org>
5  *
6  * Permission to use, copy, modify, and distribute this software for any
7  * purpose with or without fee is hereby granted, provided that the above
8  * copyright notice and this permission notice appear in all copies.
9  *
10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17  */
18 #include "config.h"
19 
20 #include <sys/types.h>
21 
22 #include <assert.h>
23 #include <ctype.h>
24 #include <stdint.h>
25 #include <stdlib.h>
26 #include <string.h>
27 #include <time.h>
28 
29 #include "mandoc_aux.h"
30 #include "tbl.h"
31 #include "out.h"
32 
33 struct	tbl_colgroup {
34 	struct tbl_colgroup	*next;
35 	size_t			 wanted;
36 	int			 startcol;
37 	int			 endcol;
38 };
39 
40 static	size_t	tblcalc_data(struct rofftbl *, struct roffcol *,
41 			const struct tbl_opts *, const struct tbl_dat *,
42 			size_t);
43 static	size_t	tblcalc_literal(struct rofftbl *, struct roffcol *,
44 			const struct tbl_dat *, size_t);
45 static	size_t	tblcalc_number(struct rofftbl *, struct roffcol *,
46 			const struct tbl_opts *, const struct tbl_dat *);
47 
48 
49 /*
50  * Parse the *src string and store a scaling unit into *dst.
51  * If the string doesn't specify the unit, use the default.
52  * If no default is specified, fail.
53  * Return a pointer to the byte after the last byte used,
54  * or NULL on total failure.
55  */
56 const char *
57 a2roffsu(const char *src, struct roffsu *dst, enum roffscale def)
58 {
59 	char		*endptr;
60 
61 	dst->unit = def == SCALE_MAX ? SCALE_BU : def;
62 	dst->scale = strtod(src, &endptr);
63 	if (endptr == src)
64 		return NULL;
65 
66 	switch (*endptr++) {
67 	case 'c':
68 		dst->unit = SCALE_CM;
69 		break;
70 	case 'i':
71 		dst->unit = SCALE_IN;
72 		break;
73 	case 'f':
74 		dst->unit = SCALE_FS;
75 		break;
76 	case 'M':
77 		dst->unit = SCALE_MM;
78 		break;
79 	case 'm':
80 		dst->unit = SCALE_EM;
81 		break;
82 	case 'n':
83 		dst->unit = SCALE_EN;
84 		break;
85 	case 'P':
86 		dst->unit = SCALE_PC;
87 		break;
88 	case 'p':
89 		dst->unit = SCALE_PT;
90 		break;
91 	case 'u':
92 		dst->unit = SCALE_BU;
93 		break;
94 	case 'v':
95 		dst->unit = SCALE_VS;
96 		break;
97 	default:
98 		endptr--;
99 		if (SCALE_MAX == def)
100 			return NULL;
101 		dst->unit = def;
102 		break;
103 	}
104 	return endptr;
105 }
106 
107 /*
108  * Calculate the abstract widths and decimal positions of columns in a
109  * table.  This routine allocates the columns structures then runs over
110  * all rows and cells in the table.  The function pointers in "tbl" are
111  * used for the actual width calculations.
112  */
113 void
114 tblcalc(struct rofftbl *tbl, const struct tbl_span *sp_first,
115     size_t offset, size_t rmargin)
116 {
117 	struct roffsu		 su;
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 		gp = &first_group;
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 an ordered, singly linked list
191 			 * of all groups of columns joined by spans,
192 			 * recording the minimum width for each group.
193 			 */
194 
195 			while (*gp != NULL && ((*gp)->startcol < icol ||
196 			    (*gp)->endcol < icol + dp->hspans))
197 				gp = &(*gp)->next;
198 			if (*gp == NULL || (*gp)->startcol > icol ||
199                             (*gp)->endcol > icol + dp->hspans) {
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 	 * Column spacings are needed for span width calculations,
213 	 * so set the default values now.
214 	 */
215 
216 	for (icol = 0; icol <= maxcol; icol++)
217 		if (tbl->cols[icol].spacing == SIZE_MAX || icol == maxcol)
218 			tbl->cols[icol].spacing = 3;
219 
220 	/*
221 	 * Replace the minimum widths with the missing widths,
222 	 * and dismiss groups that are already wide enough.
223 	 */
224 
225 	gp = &first_group;
226 	while ((g = *gp) != NULL) {
227 		done = 0;
228 		for (icol = g->startcol; icol <= g->endcol; icol++) {
229 			width = tbl->cols[icol].width;
230 			if (icol < g->endcol)
231 				width += tbl->cols[icol].spacing;
232 			if (g->wanted <= width) {
233 				done = 1;
234 				break;
235 			} else
236 				(*gp)->wanted -= width;
237 		}
238 		if (done) {
239 			*gp = g->next;
240 			free(g);
241 		} else
242 			gp = &(*gp)->next;
243 	}
244 
245 	colwidth = mandoc_reallocarray(NULL, maxcol + 1, sizeof(*colwidth));
246 	while (first_group != NULL) {
247 
248 		/*
249 		 * Rebuild the array of the widths of all columns
250 		 * participating in spans that require expansion.
251 		 */
252 
253 		for (icol = 0; icol <= maxcol; icol++)
254 			colwidth[icol] = SIZE_MAX;
255 		for (g = first_group; g != NULL; g = g->next)
256 			for (icol = g->startcol; icol <= g->endcol; icol++)
257 				colwidth[icol] = tbl->cols[icol].width;
258 
259 		/*
260 		 * Find the smallest and second smallest column width
261 		 * among the columns which may need expamsion.
262 		 */
263 
264 		min1 = min2 = SIZE_MAX;
265 		for (icol = 0; icol <= maxcol; icol++) {
266 			if (min1 > colwidth[icol]) {
267 				min2 = min1;
268 				min1 = colwidth[icol];
269 			} else if (min1 < colwidth[icol] &&
270 			    min2 > colwidth[icol])
271 				min2 = colwidth[icol];
272 		}
273 
274 		/*
275 		 * Find the minimum wanted width
276 		 * for any one of the narrowest columns,
277 		 * and mark the columns wanting that width.
278 		 */
279 
280 		wanted = min2;
281 		for (g = first_group; g != NULL; g = g->next) {
282 			necol = 0;
283 			for (icol = g->startcol; icol <= g->endcol; icol++)
284 				if (tbl->cols[icol].width == min1)
285 					necol++;
286 			if (necol == 0)
287 				continue;
288 			width = min1 + (g->wanted - 1) / necol + 1;
289 			if (width > min2)
290 				width = min2;
291 			if (wanted > width)
292 				wanted = width;
293 			for (icol = g->startcol; icol <= g->endcol; icol++)
294 				if (colwidth[icol] == min1 ||
295 				    (colwidth[icol] < min2 &&
296 				     colwidth[icol] > width))
297 					colwidth[icol] = width;
298 		}
299 
300 		/* Record the effect of the widening on the group list. */
301 
302 		gp = &first_group;
303 		while ((g = *gp) != NULL) {
304 			done = 0;
305 			for (icol = g->startcol; icol <= g->endcol; icol++) {
306 				if (colwidth[icol] != wanted ||
307 				    tbl->cols[icol].width == wanted)
308 					continue;
309 				if (g->wanted <= wanted - min1) {
310 					done = 1;
311 					break;
312 				}
313 				g->wanted -= wanted - min1;
314 			}
315 			if (done) {
316 				*gp = g->next;
317 				free(g);
318 			} else
319 				gp = &(*gp)->next;
320 		}
321 
322 		/* Record the effect of the widening on the columns. */
323 
324 		for (icol = 0; icol <= maxcol; icol++)
325 			if (colwidth[icol] == wanted)
326 				tbl->cols[icol].width = wanted;
327 	}
328 	free(colwidth);
329 
330 	/*
331 	 * Align numbers with text.
332 	 * Count columns to equalize and columns to maximize.
333 	 * Find maximum width of the columns to equalize.
334 	 * Find total width of the columns *not* to maximize.
335 	 */
336 
337 	necol = nxcol = 0;
338 	ewidth = xwidth = 0;
339 	for (icol = 0; icol <= maxcol; icol++) {
340 		col = tbl->cols + icol;
341 		if (col->width > col->nwidth)
342 			col->decimal += (col->width - col->nwidth) / 2;
343 		else
344 			col->width = col->nwidth;
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
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
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
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 	return totsz;
553 }
554