usr.bin/col/col.c

   1 /*-
   2  * Copyright (c) 1990, 1993, 1994
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Michael Rendell of the Memorial University of Newfoundland.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. Neither the name of the University nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  *
  32  * @(#) Copyright (c) 1990, 1993, 1994 The Regents of the University of California.  All rights reserved.
  33  * @(#)col.c    8.5 (Berkeley) 5/4/95
  34  * $FreeBSD: head/usr.bin/col/col.c 282722 2015-05-10 11:41:38Z bapt $
  35  */
  36
  37 #include <err.h>
  38 #include <errno.h>
  39 #include <locale.h>
  40 #include <stdio.h>
  41 #include <stdlib.h>
  42 #include <string.h>
  43 #include <termios.h>
  44 #include <unistd.h>
  45 #include <wchar.h>
  46 #include <wctype.h>
  47
  48 #define BS      '\b'            /* backspace */
  49 #define TAB     '\t'            /* tab */
  50 #define SPACE   ' '             /* space */
  51 #define NL      '\n'            /* newline */
  52 #define CR      '\r'            /* carriage return */
  53 #define ESC     '\033'          /* escape */
  54 #define SI      '\017'          /* shift in to normal character set */
  55 #define SO      '\016'          /* shift out to alternate character set */
  56 #define VT      '\013'          /* vertical tab (aka reverse line feed) */
  57 #define RLF     '7'             /* ESC-7 reverse line feed */
  58 #define RHLF    '8'             /* ESC-8 reverse half-line feed */
  59 #define FHLF    '9'             /* ESC-9 forward half-line feed */
  60
  61 /* build up at least this many lines before flushing them out */
  62 #define BUFFER_MARGIN           32
  63
  64 typedef char CSET;
  65
  66 typedef struct char_str {
  67 #define CS_NORMAL       1
  68 #define CS_ALTERNATE    2
  69         short           c_column;       /* column character is in */
  70         CSET            c_set;          /* character set (currently only 2) */
  71         wchar_t         c_char;         /* character in question */
  72         int             c_width;        /* character width */
  73 } CHAR;
  74
  75 typedef struct line_str LINE;
  76 struct line_str {
  77         CHAR    *l_line;                /* characters on the line */
  78         LINE    *l_prev;                /* previous line */
  79         LINE    *l_next;                /* next line */
  80         int     l_lsize;                /* allocated sizeof l_line */
  81         int     l_line_len;             /* strlen(l_line) */
  82         int     l_needs_sort;           /* set if chars went in out of order */
  83         int     l_max_col;              /* max column in the line */
  84 };
  85
  86 static void     addto_lineno(int *, int);
  87 static LINE    *alloc_line(void);
  88 static void     dowarn(int);
  89 static void     flush_line(LINE *);
  90 static void     flush_lines(int);
  91 static void     flush_blanks(void);
  92 static void     free_line(LINE *);
  93 static void     usage(void);
  94
  95 static CSET     last_set;               /* char_set of last char printed */
  96 static LINE    *lines;
  97 static int      compress_spaces;        /* if doing space -> tab conversion */
  98 static int      fine;                   /* if `fine' resolution (half lines) */
  99 static int      max_bufd_lines;         /* max # of half lines to keep in memory */
 100 static int      nblank_lines;           /* # blanks after last flushed line */
 101 static int      no_backspaces;          /* if not to output any backspaces */
 102 static int      pass_unknown_seqs;      /* pass unknown control sequences */
 103
 104 #define PUTC(ch) \
 105         do {                                    \
 106                 if (putwchar(ch) == WEOF)       \
 107                         errx(1, "write error"); \
 108         } while (0)
 109
 110 int
 111 main(int argc, char **argv)
 112 {
 113         wint_t ch;
 114         CHAR *c;
 115         CSET cur_set;                   /* current character set */
 116         LINE *l;                        /* current line */
 117         int extra_lines;                /* # of lines above first line */
 118         int cur_col;                    /* current column */
 119         int cur_line;                   /* line number of current position */
 120         int max_line;                   /* max value of cur_line */
 121         int this_line;                  /* line l points to */
 122         int nflushd_lines;              /* number of lines that were flushed */
 123         int adjust, opt, warned, width;
 124         const char *errstr;
 125
 126         setlocale(LC_CTYPE, "");
 127
 128         max_bufd_lines = 256;
 129         compress_spaces = 1;            /* compress spaces into tabs */
 130         while ((opt = getopt(argc, argv, "bfhl:px")) != -1)
 131                 switch (opt) {
 132                 case 'b':               /* do not output backspaces */
 133                         no_backspaces = 1;
 134                         break;
 135                 case 'f':               /* allow half forward line feeds */
 136                         fine = 1;
 137                         break;
 138                 case 'h':               /* compress spaces into tabs */
 139                         compress_spaces = 1;
 140                         break;
 141                 case 'l':               /* buffered line count */
 142                         max_bufd_lines = strtonum(optarg, 1,
 143                             (INT_MAX - BUFFER_MARGIN) / 2, &errstr) * 2;
 144                         if (errstr != NULL)
 145                                 errx(1, "bad -l argument, %s: %s", errstr,
 146                                         optarg);
 147                         break;
 148                 case 'p':               /* pass unknown control sequences */
 149                         pass_unknown_seqs = 1;
 150                         break;
 151                 case 'x':               /* do not compress spaces into tabs */
 152                         compress_spaces = 0;
 153                         break;
 154                 case '?':
 155                 default:
 156                         usage();
 157                 }
 158
 159         if (optind != argc)
 160                 usage();
 161
 162         adjust = cur_col = extra_lines = warned = 0;
 163         cur_line = max_line = nflushd_lines = this_line = 0;
 164         cur_set = last_set = CS_NORMAL;
 165         lines = l = alloc_line();
 166
 167         while ((ch = getwchar()) != WEOF) {
 168                 if (!iswgraph(ch)) {
 169                         switch (ch) {
 170                         case BS:                /* can't go back further */
 171                                 if (cur_col == 0)
 172                                         continue;
 173                                 --cur_col;
 174                                 continue;
 175                         case CR:
 176                                 cur_col = 0;
 177                                 continue;
 178                         case ESC:               /* just ignore EOF */
 179                                 switch (getwchar()) {
 180                                 /*
 181                                  * In the input stream, accept both the
 182                                  * XPG5 sequences ESC-digit and the
 183                                  * traditional BSD sequences ESC-ctrl.
 184                                  */
 185                                 case '\007':
 186                                         /* FALLTHROUGH */
 187                                 case RLF:
 188                                         addto_lineno(&cur_line, -2);
 189                                         break;
 190                                 case '\010':
 191                                         /* FALLTHROUGH */
 192                                 case RHLF:
 193                                         addto_lineno(&cur_line, -1);
 194                                         break;
 195                                 case '\011':
 196                                         /* FALLTHROUGH */
 197                                 case FHLF:
 198                                         addto_lineno(&cur_line, 1);
 199                                         if (cur_line > max_line)
 200                                                 max_line = cur_line;
 201                                 }
 202                                 continue;
 203                         case NL:
 204                                 addto_lineno(&cur_line, 2);
 205                                 if (cur_line > max_line)
 206                                         max_line = cur_line;
 207                                 cur_col = 0;
 208                                 continue;
 209                         case SPACE:
 210                                 ++cur_col;
 211                                 continue;
 212                         case SI:
 213                                 cur_set = CS_NORMAL;
 214                                 continue;
 215                         case SO:
 216                                 cur_set = CS_ALTERNATE;
 217                                 continue;
 218                         case TAB:               /* adjust column */
 219                                 cur_col |= 7;
 220                                 ++cur_col;
 221                                 continue;
 222                         case VT:
 223                                 addto_lineno(&cur_line, -2);
 224                                 continue;
 225                         }
 226                         if (iswspace(ch)) {
 227                                 if ((width = wcwidth(ch)) > 0)
 228                                         cur_col += width;
 229                                 continue;
 230                         }
 231                         if (!pass_unknown_seqs)
 232                                 continue;
 233                 }
 234
 235                 /* Must stuff ch in a line - are we at the right one? */
 236                 if (cur_line + adjust != this_line) {
 237                         LINE *lnew;
 238
 239                         /* round up to next line */
 240                         adjust = !fine && (cur_line & 1);
 241
 242                         if (cur_line + adjust < this_line) {
 243                                 while (cur_line + adjust < this_line &&
 244                                     l->l_prev != NULL) {
 245                                         l = l->l_prev;
 246                                         this_line--;
 247                                 }
 248                                 if (cur_line + adjust < this_line) {
 249                                         if (nflushd_lines == 0) {
 250                                                 /*
 251                                                  * Allow backup past first
 252                                                  * line if nothing has been
 253                                                  * flushed yet.
 254                                                  */
 255                                                 while (cur_line + adjust
 256                                                     < this_line) {
 257                                                         lnew = alloc_line();
 258                                                         l->l_prev = lnew;
 259                                                         lnew->l_next = l;
 260                                                         l = lines = lnew;
 261                                                         extra_lines++;
 262                                                         this_line--;
 263                                                 }
 264                                         } else {
 265                                                 if (!warned++)
 266                                                         dowarn(cur_line);
 267                                                 cur_line = this_line - adjust;
 268                                         }
 269                                 }
 270                         } else {
 271                                 /* may need to allocate here */
 272                                 while (cur_line + adjust > this_line) {
 273                                         if (l->l_next == NULL) {
 274                                                 l->l_next = alloc_line();
 275                                                 l->l_next->l_prev = l;
 276                                         }
 277                                         l = l->l_next;
 278                                         this_line++;
 279                                 }
 280                         }
 281                         if (this_line > nflushd_lines &&
 282                             this_line - nflushd_lines >=
 283                             max_bufd_lines + BUFFER_MARGIN) {
 284                                 if (extra_lines) {
 285                                         flush_lines(extra_lines);
 286                                         extra_lines = 0;
 287                                 }
 288                                 flush_lines(this_line - nflushd_lines -
 289                                     max_bufd_lines);
 290                                 nflushd_lines = this_line - max_bufd_lines;
 291                         }
 292                 }
 293                 /* grow line's buffer? */
 294                 if (l->l_line_len + 1 >= l->l_lsize) {
 295                         int need;
 296
 297                         need = l->l_lsize ? l->l_lsize * 2 : 90;
 298                         if ((l->l_line = realloc(l->l_line,
 299                             (unsigned)need * sizeof(CHAR))) == NULL)
 300                                 err(1, NULL);
 301                         l->l_lsize = need;
 302                 }
 303                 c = &l->l_line[l->l_line_len++];
 304                 c->c_char = ch;
 305                 c->c_set = cur_set;
 306                 c->c_column = cur_col;
 307                 c->c_width = wcwidth(ch);
 308                 /*
 309                  * If things are put in out of order, they will need sorting
 310                  * when it is flushed.
 311                  */
 312                 if (cur_col < l->l_max_col)
 313                         l->l_needs_sort = 1;
 314                 else
 315                         l->l_max_col = cur_col;
 316                 if (c->c_width > 0)
 317                         cur_col += c->c_width;
 318         }
 319         if (ferror(stdin))
 320                 err(1, NULL);
 321         if (extra_lines)
 322                 flush_lines(extra_lines);
 323
 324         /* goto the last line that had a character on it */
 325         for (; l->l_next; l = l->l_next)
 326                 this_line++;
 327         flush_lines(this_line - nflushd_lines + 1);
 328
 329         /* make sure we leave things in a sane state */
 330         if (last_set != CS_NORMAL)
 331                 PUTC(SI);
 332
 333         /* flush out the last few blank lines */
 334         if (max_line > this_line)
 335                 nblank_lines = max_line - this_line;
 336         if (max_line & 1)
 337                 nblank_lines++;
 338         flush_blanks();
 339         exit(0);
 340 }
 341
 342 static void
 343 flush_lines(int nflush)
 344 {
 345         LINE *l;
 346
 347         while (--nflush >= 0) {
 348                 l = lines;
 349                 lines = l->l_next;
 350                 if (l->l_line) {
 351                         flush_blanks();
 352                         flush_line(l);
 353                 }
 354                 if (l->l_line || l->l_next)
 355                         nblank_lines++;
 356                 if (l->l_line)
 357                         free(l->l_line);
 358                 free_line(l);
 359         }
 360         if (lines)
 361                 lines->l_prev = NULL;
 362 }
 363
 364 /*
 365  * Print a number of newline/half newlines.  If fine flag is set, nblank_lines
 366  * is the number of half line feeds, otherwise it is the number of whole line
 367  * feeds.
 368  */
 369 static void
 370 flush_blanks(void)
 371 {
 372         int half, i, nb;
 373
 374         half = 0;
 375         nb = nblank_lines;
 376         if (nb & 1) {
 377                 if (fine)
 378                         half = 1;
 379                 else
 380                         nb++;
 381         }
 382         nb /= 2;
 383         for (i = nb; --i >= 0;)
 384                 PUTC('\n');
 385         if (half) {
 386                 PUTC(ESC);
 387                 PUTC(FHLF);
 388                 if (!nb)
 389                         PUTC('\r');
 390         }
 391         nblank_lines = 0;
 392 }
 393
 394 /*
 395  * Write a line to stdout taking care of space to tab conversion (-h flag)
 396  * and character set shifts.
 397  */
 398 static void
 399 flush_line(LINE *l)
 400 {
 401         CHAR *c, *endc;
 402         int i, j, nchars, last_col, save, this_col, tot;
 403
 404         last_col = 0;
 405         nchars = l->l_line_len;
 406
 407         if (l->l_needs_sort) {
 408                 static CHAR *sorted;
 409                 static int count_size, *count, sorted_size;
 410
 411                 /*
 412                  * Do an O(n) sort on l->l_line by column being careful to
 413                  * preserve the order of characters in the same column.
 414                  */
 415                 if (l->l_lsize > sorted_size) {
 416                         sorted_size = l->l_lsize;
 417                         if ((sorted = realloc(sorted,
 418                             (unsigned)sizeof(CHAR) * sorted_size)) == NULL)
 419                                 err(1, NULL);
 420                 }
 421                 if (l->l_max_col >= count_size) {
 422                         count_size = l->l_max_col + 1;
 423                         if ((count = realloc(count,
 424                             (unsigned)sizeof(int) * count_size)) == NULL)
 425                                 err(1, NULL);
 426                 }
 427                 memset(count, 0, sizeof(int) * l->l_max_col + 1);
 428                 for (i = nchars, c = l->l_line; --i >= 0; c++)
 429                         count[c->c_column]++;
 430
 431                 /*
 432                  * calculate running total (shifted down by 1) to use as
 433                  * indices into new line.
 434                  */
 435                 for (tot = 0, i = 0; i <= l->l_max_col; i++) {
 436                         save = count[i];
 437                         count[i] = tot;
 438                         tot += save;
 439                 }
 440
 441                 for (i = nchars, c = l->l_line; --i >= 0; c++)
 442                         sorted[count[c->c_column]++] = *c;
 443                 c = sorted;
 444         } else
 445                 c = l->l_line;
 446         while (nchars > 0) {
 447                 this_col = c->c_column;
 448                 endc = c;
 449                 do {
 450                         ++endc;
 451                 } while (--nchars > 0 && this_col == endc->c_column);
 452
 453                 /* if -b only print last character */
 454                 if (no_backspaces) {
 455                         c = endc - 1;
 456                         if (nchars > 0 &&
 457                             this_col + c->c_width > endc->c_column)
 458                                 continue;
 459                 }
 460
 461                 if (this_col > last_col) {
 462                         int nspace = this_col - last_col;
 463
 464                         if (compress_spaces && nspace > 1) {
 465                                 while (1) {
 466                                         int tab_col, tab_size;
 467
 468                                         tab_col = (last_col + 8) & ~7;
 469                                         if (tab_col > this_col)
 470                                                 break;
 471                                         tab_size = tab_col - last_col;
 472                                         if (tab_size == 1)
 473                                                 PUTC(' ');
 474                                         else
 475                                                 PUTC('\t');
 476                                         nspace -= tab_size;
 477                                         last_col = tab_col;
 478                                 }
 479                         }
 480                         while (--nspace >= 0)
 481                                 PUTC(' ');
 482                         last_col = this_col;
 483                 }
 484
 485                 for (;;) {
 486                         if (c->c_set != last_set) {
 487                                 switch (c->c_set) {
 488                                 case CS_NORMAL:
 489                                         PUTC(SI);
 490                                         break;
 491                                 case CS_ALTERNATE:
 492                                         PUTC(SO);
 493                                 }
 494                                 last_set = c->c_set;
 495                         }
 496                         PUTC(c->c_char);
 497                         if ((c + 1) < endc)
 498                                 for (j = 0; j < c->c_width; j++)
 499                                         PUTC('\b');
 500                         if (++c >= endc)
 501                                 break;
 502                 }
 503                 last_col += (c - 1)->c_width;
 504         }
 505 }
 506
 507 /*
 508  * Increment or decrement a line number, checking for overflow.
 509  * Stop one below INT_MAX such that the adjust variable is safe.
 510  */
 511 void
 512 addto_lineno(int *lno, int offset)
 513 {
 514         if (offset > 0) {
 515                 if (*lno >= INT_MAX - offset)
 516                         errx(1, "too many lines");
 517         } else {
 518                 if (*lno < INT_MIN - offset)
 519                         errx(1, "too many reverse line feeds");
 520         }
 521         *lno += offset;
 522 }
 523
 524 #define NALLOC 64
 525
 526 static LINE *line_freelist;
 527
 528 static LINE *
 529 alloc_line(void)
 530 {
 531         LINE *l;
 532         int i;
 533
 534         if (!line_freelist) {
 535                 if ((l = realloc(NULL, sizeof(LINE) * NALLOC)) == NULL)
 536                         err(1, NULL);
 537                 line_freelist = l;
 538                 for (i = 1; i < NALLOC; i++, l++)
 539                         l->l_next = l + 1;
 540                 l->l_next = NULL;
 541         }
 542         l = line_freelist;
 543         line_freelist = l->l_next;
 544
 545         memset(l, 0, sizeof(LINE));
 546         return (l);
 547 }
 548
 549 static void
 550 free_line(LINE *l)
 551 {
 552
 553         l->l_next = line_freelist;
 554         line_freelist = l;
 555 }
 556
 557 static void
 558 usage(void)
 559 {
 560
 561         fprintf(stderr, "usage: col [-bfhpx] [-l nline]\n");
 562         exit(1);
 563 }
 564
 565 static void
 566 dowarn(int line)
 567 {
 568
 569         warnx("warning: can't back up %s",
 570                 line < 0 ? "past first line" : "-- line already flushed");
 571 }