out.c

   1 /*      $Id: out.c,v 1.76 2018/12/12 21:54:35 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 "mandoc.h"
  31 #include "tbl.h"
  32 #include "out.h"
  33
  34 struct  tbl_colgroup {
  35         struct tbl_colgroup     *next;
  36         size_t                   wanted;
  37         int                      startcol;
  38         int                      endcol;
  39 };
  40
  41 static  size_t  tblcalc_data(struct rofftbl *, struct roffcol *,
  42                         const struct tbl_opts *, const struct tbl_dat *,
  43                         size_t);
  44 static  size_t  tblcalc_literal(struct rofftbl *, struct roffcol *,
  45                         const struct tbl_dat *, size_t);
  46 static  size_t  tblcalc_number(struct rofftbl *, struct roffcol *,
  47                         const struct tbl_opts *, const struct tbl_dat *);
  48
  49
  50 /*
  51  * Parse the *src string and store a scaling unit into *dst.
  52  * If the string doesn't specify the unit, use the default.
  53  * If no default is specified, fail.
  54  * Return a pointer to the byte after the last byte used,
  55  * or NULL on total failure.
  56  */
  57 const char *
  58 a2roffsu(const char *src, struct roffsu *dst, enum roffscale def)
  59 {
  60         char            *endptr;
  61
  62         dst->unit = def == SCALE_MAX ? SCALE_BU : def;
  63         dst->scale = strtod(src, &endptr);
  64         if (endptr == src)
  65                 return NULL;
  66
  67         switch (*endptr++) {
  68         case 'c':
  69                 dst->unit = SCALE_CM;
  70                 break;
  71         case 'i':
  72                 dst->unit = SCALE_IN;
  73                 break;
  74         case 'f':
  75                 dst->unit = SCALE_FS;
  76                 break;
  77         case 'M':
  78                 dst->unit = SCALE_MM;
  79                 break;
  80         case 'm':
  81                 dst->unit = SCALE_EM;
  82                 break;
  83         case 'n':
  84                 dst->unit = SCALE_EN;
  85                 break;
  86         case 'P':
  87                 dst->unit = SCALE_PC;
  88                 break;
  89         case 'p':
  90                 dst->unit = SCALE_PT;
  91                 break;
  92         case 'u':
  93                 dst->unit = SCALE_BU;
  94                 break;
  95         case 'v':
  96                 dst->unit = SCALE_VS;
  97                 break;
  98         default:
  99                 endptr--;
 100                 if (SCALE_MAX == def)
 101                         return NULL;
 102                 dst->unit = def;
 103                 break;
 104         }
 105         return endptr;
 106 }
 107
 108 /*
 109  * Calculate the abstract widths and decimal positions of columns in a
 110  * table.  This routine allocates the columns structures then runs over
 111  * all rows and cells in the table.  The function pointers in "tbl" are
 112  * used for the actual width calculations.
 113  */
 114 void
 115 tblcalc(struct rofftbl *tbl, const struct tbl_span *sp_first,
 116     size_t offset, size_t rmargin)
 117 {
 118         struct roffsu            su;
 119         const struct tbl_opts   *opts;
 120         const struct tbl_span   *sp;
 121         const struct tbl_dat    *dp;
 122         struct roffcol          *col;
 123         struct tbl_colgroup     *first_group, **gp, *g;
 124         size_t                  *colwidth;
 125         size_t                   ewidth, min1, min2, wanted, width, xwidth;
 126         int                      done, icol, maxcol, necol, nxcol, quirkcol;
 127
 128         /*
 129          * Allocate the master column specifiers.  These will hold the
 130          * widths and decimal positions for all cells in the column.  It
 131          * must be freed and nullified by the caller.
 132          */
 133
 134         assert(tbl->cols == NULL);
 135         tbl->cols = mandoc_calloc((size_t)sp_first->opts->cols,
 136             sizeof(struct roffcol));
 137         opts = sp_first->opts;
 138
 139         maxcol = -1;
 140         first_group = NULL;
 141         for (sp = sp_first; sp != NULL; sp = sp->next) {
 142                 if (sp->pos != TBL_SPAN_DATA)
 143                         continue;
 144
 145                 /*
 146                  * Account for the data cells in the layout, matching it
 147                  * to data cells in the data section.
 148                  */
 149
 150                 gp = &first_group;
 151                 for (dp = sp->first; dp != NULL; dp = dp->next) {
 152                         icol = dp->layout->col;
 153                         while (icol > maxcol)
 154                                 tbl->cols[++maxcol].spacing = SIZE_MAX;
 155                         col = tbl->cols + icol;
 156                         col->flags |= dp->layout->flags;
 157                         if (dp->layout->flags & TBL_CELL_WIGN)
 158                                 continue;
 159
 160                         /* Handle explicit width specifications. */
 161
 162                         if (dp->layout->wstr != NULL &&
 163                             dp->layout->width == 0 &&
 164                             a2roffsu(dp->layout->wstr, &su, SCALE_EN)
 165                             != NULL)
 166                                 dp->layout->width =
 167                                     (*tbl->sulen)(&su, tbl->arg);
 168                         if (col->width < dp->layout->width)
 169                                 col->width = dp->layout->width;
 170                         if (dp->layout->spacing != SIZE_MAX &&
 171                             (col->spacing == SIZE_MAX ||
 172                              col->spacing < dp->layout->spacing))
 173                                 col->spacing = dp->layout->spacing;
 174
 175                         /*
 176                          * Calculate an automatic width.
 177                          * Except for spanning cells, apply it.
 178                          */
 179
 180                         width = tblcalc_data(tbl,
 181                             dp->hspans == 0 ? col : NULL,
 182                             opts, dp,
 183                             dp->block == 0 ? 0 :
 184                             dp->layout->width ? dp->layout->width :
 185                             rmargin ? (rmargin + sp->opts->cols / 2)
 186                             / (sp->opts->cols + 1) : 0);
 187                         if (dp->hspans == 0)
 188                                 continue;
 189
 190                         /*
 191                          * Build an ordered, singly linked list
 192                          * of all groups of columns joined by spans,
 193                          * recording the minimum width for each group.
 194                          */
 195
 196                         while (*gp != NULL && ((*gp)->startcol < icol ||
 197                             (*gp)->endcol < icol + dp->hspans))
 198                                 gp = &(*gp)->next;
 199                         if (*gp == NULL || (*gp)->startcol > icol ||
 200                             (*gp)->endcol > icol + dp->hspans) {
 201                                 g = mandoc_malloc(sizeof(*g));
 202                                 g->next = *gp;
 203                                 g->wanted = width;
 204                                 g->startcol = icol;
 205                                 g->endcol = icol + dp->hspans;
 206                                 *gp = g;
 207                         } else if ((*gp)->wanted < width)
 208                                 (*gp)->wanted = width;
 209                 }
 210         }
 211
 212         /*
 213          * Column spacings are needed for span width calculations,
 214          * so set the default values now.
 215          */
 216
 217         for (icol = 0; icol <= maxcol; icol++)
 218                 if (tbl->cols[icol].spacing == SIZE_MAX || icol == maxcol)
 219                         tbl->cols[icol].spacing = 3;
 220
 221         /*
 222          * Replace the minimum widths with the missing widths,
 223          * and dismiss groups that are already wide enough.
 224          */
 225
 226         gp = &first_group;
 227         while ((g = *gp) != NULL) {
 228                 done = 0;
 229                 for (icol = g->startcol; icol <= g->endcol; icol++) {
 230                         width = tbl->cols[icol].width;
 231                         if (icol < g->endcol)
 232                                 width += tbl->cols[icol].spacing;
 233                         if (g->wanted <= width) {
 234                                 done = 1;
 235                                 break;
 236                         } else
 237                                 (*gp)->wanted -= width;
 238                 }
 239                 if (done) {
 240                         *gp = g->next;
 241                         free(g);
 242                 } else
 243                         gp = &(*gp)->next;
 244         }
 245
 246         colwidth = mandoc_reallocarray(NULL, maxcol + 1, sizeof(*colwidth));
 247         while (first_group != NULL) {
 248
 249                 /*
 250                  * Rebuild the array of the widths of all columns
 251                  * participating in spans that require expansion.
 252                  */
 253
 254                 for (icol = 0; icol <= maxcol; icol++)
 255                         colwidth[icol] = SIZE_MAX;
 256                 for (g = first_group; g != NULL; g = g->next)
 257                         for (icol = g->startcol; icol <= g->endcol; icol++)
 258                                 colwidth[icol] = tbl->cols[icol].width;
 259
 260                 /*
 261                  * Find the smallest and second smallest column width
 262                  * among the columns which may need expamsion.
 263                  */
 264
 265                 min1 = min2 = SIZE_MAX;
 266                 for (icol = 0; icol <= maxcol; icol++) {
 267                         if (min1 > colwidth[icol]) {
 268                                 min2 = min1;
 269                                 min1 = colwidth[icol];
 270                         } else if (min1 < colwidth[icol] &&
 271                             min2 > colwidth[icol])
 272                                 min2 = colwidth[icol];
 273                 }
 274
 275                 /*
 276                  * Find the minimum wanted width
 277                  * for any one of the narrowest columns,
 278                  * and mark the columns wanting that width.
 279                  */
 280
 281                 wanted = min2;
 282                 for (g = first_group; g != NULL; g = g->next) {
 283                         necol = 0;
 284                         for (icol = g->startcol; icol <= g->endcol; icol++)
 285                                 if (tbl->cols[icol].width == min1)
 286                                         necol++;
 287                         if (necol == 0)
 288                                 continue;
 289                         width = min1 + (g->wanted - 1) / necol + 1;
 290                         if (width > min2)
 291                                 width = min2;
 292                         if (wanted > width)
 293                                 wanted = width;
 294                         for (icol = g->startcol; icol <= g->endcol; icol++)
 295                                 if (colwidth[icol] == min1 ||
 296                                     (colwidth[icol] < min2 &&
 297                                      colwidth[icol] > width))
 298                                         colwidth[icol] = width;
 299                 }
 300
 301                 /* Record the effect of the widening on the group list. */
 302
 303                 gp = &first_group;
 304                 while ((g = *gp) != NULL) {
 305                         done = 0;
 306                         for (icol = g->startcol; icol <= g->endcol; icol++) {
 307                                 if (colwidth[icol] != wanted ||
 308                                     tbl->cols[icol].width == wanted)
 309                                         continue;
 310                                 if (g->wanted <= wanted - min1) {
 311                                         done = 1;
 312                                         break;
 313                                 }
 314                                 g->wanted -= wanted - min1;
 315                         }
 316                         if (done) {
 317                                 *gp = g->next;
 318                                 free(g);
 319                         } else
 320                                 gp = &(*gp)->next;
 321                 }
 322
 323                 /* Record the effect of the widening on the columns. */
 324
 325                 for (icol = 0; icol <= maxcol; icol++)
 326                         if (colwidth[icol] == wanted)
 327                                 tbl->cols[icol].width = wanted;
 328         }
 329         free(colwidth);
 330
 331         /*
 332          * Align numbers with text.
 333          * Count columns to equalize and columns to maximize.
 334          * Find maximum width of the columns to equalize.
 335          * Find total width of the columns *not* to maximize.
 336          */
 337
 338         necol = nxcol = 0;
 339         ewidth = xwidth = 0;
 340         for (icol = 0; icol <= maxcol; icol++) {
 341                 col = tbl->cols + icol;
 342                 if (col->width > col->nwidth)
 343                         col->decimal += (col->width - col->nwidth) / 2;
 344                 else
 345                         col->width = col->nwidth;
 346                 if (col->flags & TBL_CELL_EQUAL) {
 347                         necol++;
 348                         if (ewidth < col->width)
 349                                 ewidth = col->width;
 350                 }
 351                 if (col->flags & TBL_CELL_WMAX)
 352                         nxcol++;
 353                 else
 354                         xwidth += col->width;
 355         }
 356
 357         /*
 358          * Equalize columns, if requested for any of them.
 359          * Update total width of the columns not to maximize.
 360          */
 361
 362         if (necol) {
 363                 for (icol = 0; icol <= maxcol; icol++) {
 364                         col = tbl->cols + icol;
 365                         if ( ! (col->flags & TBL_CELL_EQUAL))
 366                                 continue;
 367                         if (col->width == ewidth)
 368                                 continue;
 369                         if (nxcol && rmargin)
 370                                 xwidth += ewidth - col->width;
 371                         col->width = ewidth;
 372                 }
 373         }
 374
 375         /*
 376          * If there are any columns to maximize, find the total
 377          * available width, deducting 3n margins between columns.
 378          * Distribute the available width evenly.
 379          */
 380
 381         if (nxcol && rmargin) {
 382                 xwidth += 3*maxcol +
 383                     (opts->opts & (TBL_OPT_BOX | TBL_OPT_DBOX) ?
 384                      2 : !!opts->lvert + !!opts->rvert);
 385                 if (rmargin <= offset + xwidth)
 386                         return;
 387                 xwidth = rmargin - offset - xwidth;
 388
 389                 /*
 390                  * Emulate a bug in GNU tbl width calculation that
 391                  * manifests itself for large numbers of x-columns.
 392                  * Emulating it for 5 x-columns gives identical
 393                  * behaviour for up to 6 x-columns.
 394                  */
 395
 396                 if (nxcol == 5) {
 397                         quirkcol = xwidth % nxcol + 2;
 398                         if (quirkcol != 3 && quirkcol != 4)
 399                                 quirkcol = -1;
 400                 } else
 401                         quirkcol = -1;
 402
 403                 necol = 0;
 404                 ewidth = 0;
 405                 for (icol = 0; icol <= maxcol; icol++) {
 406                         col = tbl->cols + icol;
 407                         if ( ! (col->flags & TBL_CELL_WMAX))
 408                                 continue;
 409                         col->width = (double)xwidth * ++necol / nxcol
 410                             - ewidth + 0.4995;
 411                         if (necol == quirkcol)
 412                                 col->width--;
 413                         ewidth += col->width;
 414                 }
 415         }
 416 }
 417
 418 static size_t
 419 tblcalc_data(struct rofftbl *tbl, struct roffcol *col,
 420     const struct tbl_opts *opts, const struct tbl_dat *dp, size_t mw)
 421 {
 422         size_t           sz;
 423
 424         /* Branch down into data sub-types. */
 425
 426         switch (dp->layout->pos) {
 427         case TBL_CELL_HORIZ:
 428         case TBL_CELL_DHORIZ:
 429                 sz = (*tbl->len)(1, tbl->arg);
 430                 if (col != NULL && col->width < sz)
 431                         col->width = sz;
 432                 return sz;
 433         case TBL_CELL_LONG:
 434         case TBL_CELL_CENTRE:
 435         case TBL_CELL_LEFT:
 436         case TBL_CELL_RIGHT:
 437                 return tblcalc_literal(tbl, col, dp, mw);
 438         case TBL_CELL_NUMBER:
 439                 return tblcalc_number(tbl, col, opts, dp);
 440         case TBL_CELL_DOWN:
 441                 return 0;
 442         default:
 443                 abort();
 444         }
 445 }
 446
 447 static size_t
 448 tblcalc_literal(struct rofftbl *tbl, struct roffcol *col,
 449     const struct tbl_dat *dp, size_t mw)
 450 {
 451         const char      *str;   /* Beginning of the first line. */
 452         const char      *beg;   /* Beginning of the current line. */
 453         char            *end;   /* End of the current line. */
 454         size_t           lsz;   /* Length of the current line. */
 455         size_t           wsz;   /* Length of the current word. */
 456         size_t           msz;   /* Length of the longest line. */
 457
 458         if (dp->string == NULL || *dp->string == '\0')
 459                 return 0;
 460         str = mw ? mandoc_strdup(dp->string) : dp->string;
 461         msz = lsz = 0;
 462         for (beg = str; beg != NULL && *beg != '\0'; beg = end) {
 463                 end = mw ? strchr(beg, ' ') : NULL;
 464                 if (end != NULL) {
 465                         *end++ = '\0';
 466                         while (*end == ' ')
 467                                 end++;
 468                 }
 469                 wsz = (*tbl->slen)(beg, tbl->arg);
 470                 if (mw && lsz && lsz + 1 + wsz <= mw)
 471                         lsz += 1 + wsz;
 472                 else
 473                         lsz = wsz;
 474                 if (msz < lsz)
 475                         msz = lsz;
 476         }
 477         if (mw)
 478                 free((void *)str);
 479         if (col != NULL && col->width < msz)
 480                 col->width = msz;
 481         return msz;
 482 }
 483
 484 static size_t
 485 tblcalc_number(struct rofftbl *tbl, struct roffcol *col,
 486                 const struct tbl_opts *opts, const struct tbl_dat *dp)
 487 {
 488         const char      *cp, *lastdigit, *lastpoint;
 489         size_t           intsz, totsz;
 490         char             buf[2];
 491
 492         if (dp->string == NULL || *dp->string == '\0')
 493                 return 0;
 494
 495         totsz = (*tbl->slen)(dp->string, tbl->arg);
 496         if (col == NULL)
 497                 return totsz;
 498
 499         /*
 500          * Find the last digit and
 501          * the last decimal point that is adjacent to a digit.
 502          * The alignment indicator "\&" overrides everything.
 503          */
 504
 505         lastdigit = lastpoint = NULL;
 506         for (cp = dp->string; cp[0] != '\0'; cp++) {
 507                 if (cp[0] == '\\' && cp[1] == '&') {
 508                         lastdigit = lastpoint = cp;
 509                         break;
 510                 } else if (cp[0] == opts->decimal &&
 511                     (isdigit((unsigned char)cp[1]) ||
 512                      (cp > dp->string && isdigit((unsigned char)cp[-1]))))
 513                         lastpoint = cp;
 514                 else if (isdigit((unsigned char)cp[0]))
 515                         lastdigit = cp;
 516         }
 517
 518         /* Not a number, treat as a literal string. */
 519
 520         if (lastdigit == NULL) {
 521                 if (col != NULL && col->width < totsz)
 522                         col->width = totsz;
 523                 return totsz;
 524         }
 525
 526         /* Measure the width of the integer part. */
 527
 528         if (lastpoint == NULL)
 529                 lastpoint = lastdigit + 1;
 530         intsz = 0;
 531         buf[1] = '\0';
 532         for (cp = dp->string; cp < lastpoint; cp++) {
 533                 buf[0] = cp[0];
 534                 intsz += (*tbl->slen)(buf, tbl->arg);
 535         }
 536
 537         /*
 538          * If this number has more integer digits than all numbers
 539          * seen on earlier lines, shift them all to the right.
 540          * If it has fewer, shift this number to the right.
 541          */
 542
 543         if (intsz > col->decimal) {
 544                 col->nwidth += intsz - col->decimal;
 545                 col->decimal = intsz;
 546         } else
 547                 totsz += col->decimal - intsz;
 548
 549         /* Update the maximum total width seen so far. */
 550
 551         if (totsz > col->nwidth)
 552                 col->nwidth = totsz;
 553         return totsz;
 554 }