out.c

   1 /*      $Id: out.c,v 1.83 2021/09/28 17:06:59 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                 gp = &first_group;
 153                 for (dp = sp->first; dp != NULL; dp = dp->next) {
 154                         icol = dp->layout->col;
 155                         while (maxcol < icol + dp->hspans)
 156                                 tbl->cols[++maxcol].spacing = SIZE_MAX;
 157                         col = tbl->cols + icol;
 158                         col->flags |= dp->layout->flags;
 159                         if (dp->layout->flags & TBL_CELL_WIGN)
 160                                 continue;
 161
 162                         /* Handle explicit width specifications. */
 163
 164                         if (dp->layout->wstr != NULL &&
 165                             dp->layout->width == 0 &&
 166                             a2roffsu(dp->layout->wstr, &su, SCALE_EN)
 167                             != NULL)
 168                                 dp->layout->width =
 169                                     (*tbl->sulen)(&su, tbl->arg);
 170                         if (col->width < dp->layout->width)
 171                                 col->width = dp->layout->width;
 172                         if (dp->layout->spacing != SIZE_MAX &&
 173                             (col->spacing == SIZE_MAX ||
 174                              col->spacing < dp->layout->spacing))
 175                                 col->spacing = dp->layout->spacing;
 176
 177                         /*
 178                          * Calculate an automatic width.
 179                          * Except for spanning cells, apply it.
 180                          */
 181
 182                         width = tblcalc_data(tbl,
 183                             dp->hspans == 0 ? col : NULL,
 184                             opts, dp,
 185                             dp->block == 0 ? 0 :
 186                             dp->layout->width ? dp->layout->width :
 187                             rmargin ? (rmargin + sp->opts->cols / 2)
 188                             / (sp->opts->cols + 1) : 0);
 189                         if (dp->hspans == 0)
 190                                 continue;
 191
 192                         /*
 193                          * Build an ordered, singly linked list
 194                          * of all groups of columns joined by spans,
 195                          * recording the minimum width for each group.
 196                          */
 197
 198                         while (*gp != NULL && ((*gp)->startcol < icol ||
 199                             (*gp)->endcol < icol + dp->hspans))
 200                                 gp = &(*gp)->next;
 201                         if (*gp == NULL || (*gp)->startcol > icol ||
 202                             (*gp)->endcol > icol + dp->hspans) {
 203                                 g = mandoc_malloc(sizeof(*g));
 204                                 g->next = *gp;
 205                                 g->wanted = width;
 206                                 g->startcol = icol;
 207                                 g->endcol = icol + dp->hspans;
 208                                 *gp = g;
 209                         } else if ((*gp)->wanted < width)
 210                                 (*gp)->wanted = width;
 211                 }
 212         }
 213
 214         /*
 215          * The minimum width of columns explicitly specified
 216          * in the layout is 1n.
 217          */
 218
 219         if (maxcol < sp_first->opts->cols - 1)
 220                 maxcol = sp_first->opts->cols - 1;
 221         for (icol = 0; icol <= maxcol; icol++) {
 222                 col = tbl->cols + icol;
 223                 if (col->width < 1)
 224                         col->width = 1;
 225
 226                 /*
 227                  * Column spacings are needed for span width
 228                  * calculations, so set the default values now.
 229                  */
 230
 231                 if (col->spacing == SIZE_MAX || icol == maxcol)
 232                         col->spacing = 3;
 233         }
 234
 235         /*
 236          * Replace the minimum widths with the missing widths,
 237          * and dismiss groups that are already wide enough.
 238          */
 239
 240         gp = &first_group;
 241         while ((g = *gp) != NULL) {
 242                 done = 0;
 243                 for (icol = g->startcol; icol <= g->endcol; icol++) {
 244                         width = tbl->cols[icol].width;
 245                         if (icol < g->endcol)
 246                                 width += tbl->cols[icol].spacing;
 247                         if (g->wanted <= width) {
 248                                 done = 1;
 249                                 break;
 250                         } else
 251                                 (*gp)->wanted -= width;
 252                 }
 253                 if (done) {
 254                         *gp = g->next;
 255                         free(g);
 256                 } else
 257                         gp = &(*gp)->next;
 258         }
 259
 260         colwidth = mandoc_reallocarray(NULL, maxcol + 1, sizeof(*colwidth));
 261         while (first_group != NULL) {
 262
 263                 /*
 264                  * Rebuild the array of the widths of all columns
 265                  * participating in spans that require expansion.
 266                  */
 267
 268                 for (icol = 0; icol <= maxcol; icol++)
 269                         colwidth[icol] = SIZE_MAX;
 270                 for (g = first_group; g != NULL; g = g->next)
 271                         for (icol = g->startcol; icol <= g->endcol; icol++)
 272                                 colwidth[icol] = tbl->cols[icol].width;
 273
 274                 /*
 275                  * Find the smallest and second smallest column width
 276                  * among the columns which may need expamsion.
 277                  */
 278
 279                 min1 = min2 = SIZE_MAX;
 280                 for (icol = 0; icol <= maxcol; icol++) {
 281                         width = colwidth[icol];
 282                         if (min1 > width) {
 283                                 min2 = min1;
 284                                 min1 = width;
 285                         } else if (min1 < width && min2 > width)
 286                                 min2 = width;
 287                 }
 288
 289                 /*
 290                  * Find the minimum wanted width
 291                  * for any one of the narrowest columns,
 292                  * and mark the columns wanting that width.
 293                  */
 294
 295                 wanted = min2;
 296                 for (g = first_group; g != NULL; g = g->next) {
 297                         necol = 0;
 298                         for (icol = g->startcol; icol <= g->endcol; icol++)
 299                                 if (colwidth[icol] == min1)
 300                                         necol++;
 301                         if (necol == 0)
 302                                 continue;
 303                         width = min1 + (g->wanted - 1) / necol + 1;
 304                         if (width > min2)
 305                                 width = min2;
 306                         if (wanted > width)
 307                                 wanted = width;
 308                 }
 309
 310                 /* Record the effect of the widening. */
 311
 312                 gp = &first_group;
 313                 while ((g = *gp) != NULL) {
 314                         done = 0;
 315                         for (icol = g->startcol; icol <= g->endcol; icol++) {
 316                                 if (colwidth[icol] != min1)
 317                                         continue;
 318                                 if (g->wanted <= wanted - min1) {
 319                                         tbl->cols[icol].width += g->wanted;
 320                                         done = 1;
 321                                         break;
 322                                 }
 323                                 tbl->cols[icol].width = wanted;
 324                                 g->wanted -= wanted - min1;
 325                         }
 326                         if (done) {
 327                                 *gp = g->next;
 328                                 free(g);
 329                         } else
 330                                 gp = &(*gp)->next;
 331                 }
 332         }
 333         free(colwidth);
 334
 335         /*
 336          * Align numbers with text.
 337          * Count columns to equalize and columns to maximize.
 338          * Find maximum width of the columns to equalize.
 339          * Find total width of the columns *not* to maximize.
 340          */
 341
 342         necol = nxcol = 0;
 343         ewidth = xwidth = 0;
 344         for (icol = 0; icol <= maxcol; icol++) {
 345                 col = tbl->cols + icol;
 346                 if (col->width > col->nwidth)
 347                         col->decimal += (col->width - col->nwidth) / 2;
 348                 if (col->flags & TBL_CELL_EQUAL) {
 349                         necol++;
 350                         if (ewidth < col->width)
 351                                 ewidth = col->width;
 352                 }
 353                 if (col->flags & TBL_CELL_WMAX)
 354                         nxcol++;
 355                 else
 356                         xwidth += col->width;
 357         }
 358
 359         /*
 360          * Equalize columns, if requested for any of them.
 361          * Update total width of the columns not to maximize.
 362          */
 363
 364         if (necol) {
 365                 for (icol = 0; icol <= maxcol; icol++) {
 366                         col = tbl->cols + icol;
 367                         if ( ! (col->flags & TBL_CELL_EQUAL))
 368                                 continue;
 369                         if (col->width == ewidth)
 370                                 continue;
 371                         if (nxcol && rmargin)
 372                                 xwidth += ewidth - col->width;
 373                         col->width = ewidth;
 374                 }
 375         }
 376
 377         /*
 378          * If there are any columns to maximize, find the total
 379          * available width, deducting 3n margins between columns.
 380          * Distribute the available width evenly.
 381          */
 382
 383         if (nxcol && rmargin) {
 384                 xwidth += 3*maxcol +
 385                     (opts->opts & (TBL_OPT_BOX | TBL_OPT_DBOX) ?
 386                      2 : !!opts->lvert + !!opts->rvert);
 387                 if (rmargin <= offset + xwidth)
 388                         return;
 389                 xwidth = rmargin - offset - xwidth;
 390
 391                 /*
 392                  * Emulate a bug in GNU tbl width calculation that
 393                  * manifests itself for large numbers of x-columns.
 394                  * Emulating it for 5 x-columns gives identical
 395                  * behaviour for up to 6 x-columns.
 396                  */
 397
 398                 if (nxcol == 5) {
 399                         quirkcol = xwidth % nxcol + 2;
 400                         if (quirkcol != 3 && quirkcol != 4)
 401                                 quirkcol = -1;
 402                 } else
 403                         quirkcol = -1;
 404
 405                 necol = 0;
 406                 ewidth = 0;
 407                 for (icol = 0; icol <= maxcol; icol++) {
 408                         col = tbl->cols + icol;
 409                         if ( ! (col->flags & TBL_CELL_WMAX))
 410                                 continue;
 411                         col->width = (double)xwidth * ++necol / nxcol
 412                             - ewidth + 0.4995;
 413                         if (necol == quirkcol)
 414                                 col->width--;
 415                         ewidth += col->width;
 416                 }
 417         }
 418 }
 419
 420 static size_t
 421 tblcalc_data(struct rofftbl *tbl, struct roffcol *col,
 422     const struct tbl_opts *opts, const struct tbl_dat *dp, size_t mw)
 423 {
 424         size_t           sz;
 425
 426         /* Branch down into data sub-types. */
 427
 428         switch (dp->layout->pos) {
 429         case TBL_CELL_HORIZ:
 430         case TBL_CELL_DHORIZ:
 431                 sz = (*tbl->len)(1, tbl->arg);
 432                 if (col != NULL && col->width < sz)
 433                         col->width = sz;
 434                 return sz;
 435         case TBL_CELL_LONG:
 436         case TBL_CELL_CENTRE:
 437         case TBL_CELL_LEFT:
 438         case TBL_CELL_RIGHT:
 439                 return tblcalc_literal(tbl, col, dp, mw);
 440         case TBL_CELL_NUMBER:
 441                 return tblcalc_number(tbl, col, opts, dp);
 442         case TBL_CELL_DOWN:
 443                 return 0;
 444         default:
 445                 abort();
 446         }
 447 }
 448
 449 static size_t
 450 tblcalc_literal(struct rofftbl *tbl, struct roffcol *col,
 451     const struct tbl_dat *dp, size_t mw)
 452 {
 453         const char      *str;   /* Beginning of the first line. */
 454         const char      *beg;   /* Beginning of the current line. */
 455         char            *end;   /* End of the current line. */
 456         size_t           lsz;   /* Length of the current line. */
 457         size_t           wsz;   /* Length of the current word. */
 458         size_t           msz;   /* Length of the longest line. */
 459
 460         if (dp->string == NULL || *dp->string == '\0')
 461                 return 0;
 462         str = mw ? mandoc_strdup(dp->string) : dp->string;
 463         msz = lsz = 0;
 464         for (beg = str; beg != NULL && *beg != '\0'; beg = end) {
 465                 end = mw ? strchr(beg, ' ') : NULL;
 466                 if (end != NULL) {
 467                         *end++ = '\0';
 468                         while (*end == ' ')
 469                                 end++;
 470                 }
 471                 wsz = (*tbl->slen)(beg, tbl->arg);
 472                 if (mw && lsz && lsz + 1 + wsz <= mw)
 473                         lsz += 1 + wsz;
 474                 else
 475                         lsz = wsz;
 476                 if (msz < lsz)
 477                         msz = lsz;
 478         }
 479         if (mw)
 480                 free((void *)str);
 481         if (col != NULL && col->width < msz)
 482                 col->width = msz;
 483         return msz;
 484 }
 485
 486 static size_t
 487 tblcalc_number(struct rofftbl *tbl, struct roffcol *col,
 488                 const struct tbl_opts *opts, const struct tbl_dat *dp)
 489 {
 490         const char      *cp, *lastdigit, *lastpoint;
 491         size_t           intsz, totsz;
 492         char             buf[2];
 493
 494         if (dp->string == NULL || *dp->string == '\0')
 495                 return 0;
 496
 497         totsz = (*tbl->slen)(dp->string, tbl->arg);
 498         if (col == NULL)
 499                 return totsz;
 500
 501         /*
 502          * Find the last digit and
 503          * the last decimal point that is adjacent to a digit.
 504          * The alignment indicator "\&" overrides everything.
 505          */
 506
 507         lastdigit = lastpoint = NULL;
 508         for (cp = dp->string; cp[0] != '\0'; cp++) {
 509                 if (cp[0] == '\\' && cp[1] == '&') {
 510                         lastdigit = lastpoint = cp;
 511                         break;
 512                 } else if (cp[0] == opts->decimal &&
 513                     (isdigit((unsigned char)cp[1]) ||
 514                      (cp > dp->string && isdigit((unsigned char)cp[-1]))))
 515                         lastpoint = cp;
 516                 else if (isdigit((unsigned char)cp[0]))
 517                         lastdigit = cp;
 518         }
 519
 520         /* Not a number, treat as a literal string. */
 521
 522         if (lastdigit == NULL) {
 523                 if (col != NULL && col->width < totsz)
 524                         col->width = totsz;
 525                 return totsz;
 526         }
 527
 528         /* Measure the width of the integer part. */
 529
 530         if (lastpoint == NULL)
 531                 lastpoint = lastdigit + 1;
 532         intsz = 0;
 533         buf[1] = '\0';
 534         for (cp = dp->string; cp < lastpoint; cp++) {
 535                 buf[0] = cp[0];
 536                 intsz += (*tbl->slen)(buf, tbl->arg);
 537         }
 538
 539         /*
 540          * If this number has more integer digits than all numbers
 541          * seen on earlier lines, shift them all to the right.
 542          * If it has fewer, shift this number to the right.
 543          */
 544
 545         if (intsz > col->decimal) {
 546                 col->nwidth += intsz - col->decimal;
 547                 col->decimal = intsz;
 548         } else
 549                 totsz += col->decimal - intsz;
 550
 551         /* Update the maximum total width seen so far. */
 552
 553         if (totsz > col->nwidth)
 554                 col->nwidth = totsz;
 555         if (col->nwidth > col->width)
 556                 col->width = col->nwidth;
 557         return totsz;
 558 }