1 /* $OpenBSD: out.c,v 1.52 2021/08/10 12:36:42 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 <sys/types.h> 19 20 #include <assert.h> 21 #include <ctype.h> 22 #include <stdint.h> 23 #include <stdio.h> 24 #include <stdlib.h> 25 #include <string.h> 26 #include <time.h> 27 28 #include "mandoc_aux.h" 29 #include "mandoc.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 * 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 (*gp)->wanted -= width; 249 } 250 if (done) { 251 *gp = g->next; 252 free(g); 253 } else 254 gp = &(*gp)->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 if (min1 > colwidth[icol]) { 279 min2 = min1; 280 min1 = colwidth[icol]; 281 } else if (min1 < colwidth[icol] && 282 min2 > colwidth[icol]) 283 min2 = colwidth[icol]; 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 (tbl->cols[icol].width == 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 for (icol = g->startcol; icol <= g->endcol; icol++) 306 if (colwidth[icol] == min1 || 307 (colwidth[icol] < min2 && 308 colwidth[icol] > width)) 309 colwidth[icol] = width; 310 } 311 312 /* Record the effect of the widening on the group list. */ 313 314 gp = &first_group; 315 while ((g = *gp) != NULL) { 316 done = 0; 317 for (icol = g->startcol; icol <= g->endcol; icol++) { 318 if (colwidth[icol] != wanted || 319 tbl->cols[icol].width == wanted) 320 continue; 321 if (g->wanted <= wanted - min1) { 322 done = 1; 323 break; 324 } 325 g->wanted -= wanted - min1; 326 } 327 if (done) { 328 *gp = g->next; 329 free(g); 330 } else 331 gp = &(*gp)->next; 332 } 333 334 /* Record the effect of the widening on the columns. */ 335 336 for (icol = 0; icol <= maxcol; icol++) 337 if (colwidth[icol] == wanted) 338 tbl->cols[icol].width = wanted; 339 } 340 free(colwidth); 341 342 /* 343 * Align numbers with text. 344 * Count columns to equalize and columns to maximize. 345 * Find maximum width of the columns to equalize. 346 * Find total width of the columns *not* to maximize. 347 */ 348 349 necol = nxcol = 0; 350 ewidth = xwidth = 0; 351 for (icol = 0; icol <= maxcol; icol++) { 352 col = tbl->cols + icol; 353 if (col->width > col->nwidth) 354 col->decimal += (col->width - col->nwidth) / 2; 355 else 356 col->width = col->nwidth; 357 if (col->flags & TBL_CELL_EQUAL) { 358 necol++; 359 if (ewidth < col->width) 360 ewidth = col->width; 361 } 362 if (col->flags & TBL_CELL_WMAX) 363 nxcol++; 364 else 365 xwidth += col->width; 366 } 367 368 /* 369 * Equalize columns, if requested for any of them. 370 * Update total width of the columns not to maximize. 371 */ 372 373 if (necol) { 374 for (icol = 0; icol <= maxcol; icol++) { 375 col = tbl->cols + icol; 376 if ( ! (col->flags & TBL_CELL_EQUAL)) 377 continue; 378 if (col->width == ewidth) 379 continue; 380 if (nxcol && rmargin) 381 xwidth += ewidth - col->width; 382 col->width = ewidth; 383 } 384 } 385 386 /* 387 * If there are any columns to maximize, find the total 388 * available width, deducting 3n margins between columns. 389 * Distribute the available width evenly. 390 */ 391 392 if (nxcol && rmargin) { 393 xwidth += 3*maxcol + 394 (opts->opts & (TBL_OPT_BOX | TBL_OPT_DBOX) ? 395 2 : !!opts->lvert + !!opts->rvert); 396 if (rmargin <= offset + xwidth) 397 return; 398 xwidth = rmargin - offset - xwidth; 399 400 /* 401 * Emulate a bug in GNU tbl width calculation that 402 * manifests itself for large numbers of x-columns. 403 * Emulating it for 5 x-columns gives identical 404 * behaviour for up to 6 x-columns. 405 */ 406 407 if (nxcol == 5) { 408 quirkcol = xwidth % nxcol + 2; 409 if (quirkcol != 3 && quirkcol != 4) 410 quirkcol = -1; 411 } else 412 quirkcol = -1; 413 414 necol = 0; 415 ewidth = 0; 416 for (icol = 0; icol <= maxcol; icol++) { 417 col = tbl->cols + icol; 418 if ( ! (col->flags & TBL_CELL_WMAX)) 419 continue; 420 col->width = (double)xwidth * ++necol / nxcol 421 - ewidth + 0.4995; 422 if (necol == quirkcol) 423 col->width--; 424 ewidth += col->width; 425 } 426 } 427 } 428 429 static size_t 430 tblcalc_data(struct rofftbl *tbl, struct roffcol *col, 431 const struct tbl_opts *opts, const struct tbl_dat *dp, size_t mw) 432 { 433 size_t sz; 434 435 /* Branch down into data sub-types. */ 436 437 switch (dp->layout->pos) { 438 case TBL_CELL_HORIZ: 439 case TBL_CELL_DHORIZ: 440 sz = (*tbl->len)(1, tbl->arg); 441 if (col != NULL && col->width < sz) 442 col->width = sz; 443 return sz; 444 case TBL_CELL_LONG: 445 case TBL_CELL_CENTRE: 446 case TBL_CELL_LEFT: 447 case TBL_CELL_RIGHT: 448 return tblcalc_literal(tbl, col, dp, mw); 449 case TBL_CELL_NUMBER: 450 return tblcalc_number(tbl, col, opts, dp); 451 case TBL_CELL_DOWN: 452 return 0; 453 default: 454 abort(); 455 } 456 } 457 458 static size_t 459 tblcalc_literal(struct rofftbl *tbl, struct roffcol *col, 460 const struct tbl_dat *dp, size_t mw) 461 { 462 const char *str; /* Beginning of the first line. */ 463 const char *beg; /* Beginning of the current line. */ 464 char *end; /* End of the current line. */ 465 size_t lsz; /* Length of the current line. */ 466 size_t wsz; /* Length of the current word. */ 467 size_t msz; /* Length of the longest line. */ 468 469 if (dp->string == NULL || *dp->string == '\0') 470 return 0; 471 str = mw ? mandoc_strdup(dp->string) : dp->string; 472 msz = lsz = 0; 473 for (beg = str; beg != NULL && *beg != '\0'; beg = end) { 474 end = mw ? strchr(beg, ' ') : NULL; 475 if (end != NULL) { 476 *end++ = '\0'; 477 while (*end == ' ') 478 end++; 479 } 480 wsz = (*tbl->slen)(beg, tbl->arg); 481 if (mw && lsz && lsz + 1 + wsz <= mw) 482 lsz += 1 + wsz; 483 else 484 lsz = wsz; 485 if (msz < lsz) 486 msz = lsz; 487 } 488 if (mw) 489 free((void *)str); 490 if (col != NULL && col->width < msz) 491 col->width = msz; 492 return msz; 493 } 494 495 static size_t 496 tblcalc_number(struct rofftbl *tbl, struct roffcol *col, 497 const struct tbl_opts *opts, const struct tbl_dat *dp) 498 { 499 const char *cp, *lastdigit, *lastpoint; 500 size_t intsz, totsz; 501 char buf[2]; 502 503 if (dp->string == NULL || *dp->string == '\0') 504 return 0; 505 506 totsz = (*tbl->slen)(dp->string, tbl->arg); 507 if (col == NULL) 508 return totsz; 509 510 /* 511 * Find the last digit and 512 * the last decimal point that is adjacent to a digit. 513 * The alignment indicator "\&" overrides everything. 514 */ 515 516 lastdigit = lastpoint = NULL; 517 for (cp = dp->string; cp[0] != '\0'; cp++) { 518 if (cp[0] == '\\' && cp[1] == '&') { 519 lastdigit = lastpoint = cp; 520 break; 521 } else if (cp[0] == opts->decimal && 522 (isdigit((unsigned char)cp[1]) || 523 (cp > dp->string && isdigit((unsigned char)cp[-1])))) 524 lastpoint = cp; 525 else if (isdigit((unsigned char)cp[0])) 526 lastdigit = cp; 527 } 528 529 /* Not a number, treat as a literal string. */ 530 531 if (lastdigit == NULL) { 532 if (col != NULL && col->width < totsz) 533 col->width = totsz; 534 return totsz; 535 } 536 537 /* Measure the width of the integer part. */ 538 539 if (lastpoint == NULL) 540 lastpoint = lastdigit + 1; 541 intsz = 0; 542 buf[1] = '\0'; 543 for (cp = dp->string; cp < lastpoint; cp++) { 544 buf[0] = cp[0]; 545 intsz += (*tbl->slen)(buf, tbl->arg); 546 } 547 548 /* 549 * If this number has more integer digits than all numbers 550 * seen on earlier lines, shift them all to the right. 551 * If it has fewer, shift this number to the right. 552 */ 553 554 if (intsz > col->decimal) { 555 col->nwidth += intsz - col->decimal; 556 col->decimal = intsz; 557 } else 558 totsz += col->decimal - intsz; 559 560 /* Update the maximum total width seen so far. */ 561 562 if (totsz > col->nwidth) 563 col->nwidth = totsz; 564 return totsz; 565 } 566