out.c

   1 /*      $Id: out.c,v 1.79 2019/12/31 22:58:41 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          * 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 }