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