src/tac.c

   1 /* tac - concatenate and print files in reverse
   2    Copyright (C) 1988, 1989, 1990, 1991 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17
  18 /* Written by Jay Lepreau (lepreau@cs.utah.edu).
  19    GNU enhancements by David MacKenzie (djm@gnu.ai.mit.edu). */
  20
  21 /* Copy each FILE, or the standard input if none are given or when a
  22    FILE name of "-" is encountered, to the standard output with the
  23    order of the records reversed.  The records are separated by
  24    instances of a string, or a newline if none is given.  By default, the
  25    separator string is attached to the end of the record that it
  26    follows in the file.
  27
  28    Options:
  29    -b, --before                 The separator is attached to the beginning
  30                                 of the record that it precedes in the file.
  31    -r, --regex                  The separator is a regular expression.
  32    -s, --separator=separator    Use SEPARATOR as the record separator.
  33
  34    To reverse a file byte by byte, use (in bash, ksh, or sh):
  35 tac -r -s '.\|
  36 ' file */
  37
  38 #include <config.h>
  39
  40 #include <stdio.h>
  41 #include <getopt.h>
  42 #include <sys/types.h>
  43 #include <signal.h>
  44 #include <regex.h>
  45 #include "system.h"
  46 #include "version.h"
  47 #include "error.h"
  48
  49 #ifndef STDC_HEADERS
  50 char *malloc ();
  51 char *realloc ();
  52 #endif
  53
  54 /* The number of bytes per atomic read. */
  55 #define INITIAL_READSIZE 8192
  56
  57 /* The number of bytes per atomic write. */
  58 #define WRITESIZE 8192
  59
  60 char *mktemp ();
  61
  62 static RETSIGTYPE cleanup ();
  63 static int tac ();
  64 static int tac_file ();
  65 static int tac_stdin ();
  66 static char *xmalloc ();
  67 static char *xrealloc ();
  68 static void output ();
  69 static void save_stdin ();
  70 static void xwrite ();
  71
  72 int full_write ();
  73 int safe_read ();
  74
  75 /* The name this program was run with. */
  76 char *program_name;
  77
  78 /* The string that separates the records of the file. */
  79 static char *separator;
  80
  81 /* If nonzero, print `separator' along with the record preceding it
  82    in the file; otherwise with the record following it. */
  83 static int separator_ends_record;
  84
  85 /* 0 if `separator' is to be matched as a regular expression;
  86    otherwise, the length of `separator', used as a sentinel to
  87    stop the search. */
  88 static int sentinel_length;
  89
  90 /* The length of a match with `separator'.  If `sentinel_length' is 0,
  91    `match_length' is computed every time a match succeeds;
  92    otherwise, it is simply the length of `separator'. */
  93 static int match_length;
  94
  95 /* The input buffer. */
  96 static char *buffer;
  97
  98 /* The number of bytes to read at once into `buffer'. */
  99 static unsigned read_size;
 100
 101 /* The size of `buffer'.  This is read_size * 2 + sentinel_length + 2.
 102    The extra 2 bytes allow `past_end' to have a value beyond the
 103    end of `buffer' and `match_start' to run off the front of `buffer'. */
 104 static unsigned buffer_size;
 105
 106 /* The compiled regular expression representing `separator'. */
 107 static struct re_pattern_buffer compiled_separator;
 108
 109 /* If non-zero, display usage information and exit.  */
 110 static int show_help;
 111
 112 /* If non-zero, print the version on standard output then exit.  */
 113 static int show_version;
 114
 115 static struct option const longopts[] =
 116 {
 117   {"before", no_argument, &separator_ends_record, 0},
 118   {"regex", no_argument, &sentinel_length, 0},
 119   {"separator", required_argument, NULL, 's'},
 120   {"help", no_argument, &show_help, 1},
 121   {"version", no_argument, &show_version, 1},
 122   {NULL, 0, NULL, 0}
 123 };
 124
 125 static void
 126 usage (status)
 127      int status;
 128 {
 129   if (status != 0)
 130     fprintf (stderr, "Try `%s --help' for more information.\n",
 131              program_name);
 132   else
 133     {
 134       printf ("\
 135 Usage: %s [OPTION]... [FILE]...\n\
 136 ",
 137               program_name);
 138       printf ("\
 139 \n\
 140   -b, --before             attach the separator before instead of after\n\
 141   -r, --regex              interpret the separator as a regular expression\n\
 142   -s, --separator=STRING   use STRING as the separator instead of newline\n\
 143       --help               display this help and exit\n\
 144       --version            output version information and exit\n\
 145 \n\
 146 With no FILE, or when FILE is -, read standard input.\n\
 147 ");
 148     }
 149   exit (status);
 150 }
 151
 152 void
 153 main (argc, argv)
 154      int argc;
 155      char **argv;
 156 {
 157   const char *error_message;    /* Return value from re_compile_pattern. */
 158   int optc, errors;
 159   int have_read_stdin = 0;
 160
 161   program_name = argv[0];
 162   errors = 0;
 163   separator = "\n";
 164   sentinel_length = 1;
 165   separator_ends_record = 1;
 166
 167   while ((optc = getopt_long (argc, argv, "brs:", longopts, (int *) 0))
 168          != EOF)
 169     {
 170       switch (optc)
 171         {
 172         case 0:
 173           break;
 174         case 'b':
 175           separator_ends_record = 0;
 176           break;
 177         case 'r':
 178           sentinel_length = 0;
 179           break;
 180         case 's':
 181           separator = optarg;
 182           if (*separator == 0)
 183             error (1, 0, "separator cannot be empty");
 184           break;
 185         default:
 186           usage (1);
 187         }
 188     }
 189
 190   if (show_version)
 191     {
 192       printf ("tac - %s\n", version_string);
 193       exit (0);
 194     }
 195
 196   if (show_help)
 197     usage (0);
 198
 199   if (sentinel_length == 0)
 200     {
 201       compiled_separator.allocated = 100;
 202       compiled_separator.buffer = (unsigned char *)
 203         xmalloc (compiled_separator.allocated);
 204       compiled_separator.fastmap = xmalloc (256);
 205       compiled_separator.translate = 0;
 206       error_message = re_compile_pattern (separator, strlen (separator),
 207                                           &compiled_separator);
 208       if (error_message)
 209         error (1, 0, "%s", error_message);
 210     }
 211   else
 212     match_length = sentinel_length = strlen (separator);
 213
 214   read_size = INITIAL_READSIZE;
 215   /* A precaution that will probably never be needed. */
 216   while (sentinel_length * 2 >= read_size)
 217     read_size *= 2;
 218   buffer_size = read_size * 2 + sentinel_length + 2;
 219   buffer = xmalloc (buffer_size);
 220   if (sentinel_length)
 221     {
 222       strcpy (buffer, separator);
 223       buffer += sentinel_length;
 224     }
 225   else
 226     ++buffer;
 227
 228   if (optind == argc)
 229     {
 230       have_read_stdin = 1;
 231       errors = tac_stdin ();
 232     }
 233   else
 234     for (; optind < argc; ++optind)
 235       {
 236         if (strcmp (argv[optind], "-") == 0)
 237           {
 238             have_read_stdin = 1;
 239             errors |= tac_stdin ();
 240           }
 241         else
 242           errors |= tac_file (argv[optind]);
 243       }
 244
 245   /* Flush the output buffer. */
 246   output ((char *) NULL, (char *) NULL);
 247
 248   if (have_read_stdin && close (0) < 0)
 249     error (1, errno, "-");
 250   if (close (1) < 0)
 251     error (1, errno, "write error");
 252   exit (errors);
 253 }
 254
 255 /* The name of a temporary file containing a copy of pipe input. */
 256 char *tempfile;
 257
 258 /* Print the standard input in reverse, saving it to temporary
 259    file `tempfile' first if it is a pipe.
 260    Return 0 if ok, 1 if an error occurs. */
 261
 262 static int
 263 tac_stdin ()
 264 {
 265   /* Previous values of signal handlers. */
 266   RETSIGTYPE (*sigint) (), (*sighup) (), (*sigpipe) (), (*sigterm) ();
 267   int errors;
 268   struct stat stats;
 269 #ifdef _POSIX_VERSION
 270     struct sigaction oldact, newact;
 271 #endif                          /* _POSIX_VERSION */
 272
 273   /* No tempfile is needed for "tac < file".
 274      Use fstat instead of checking for errno == ESPIPE because
 275      lseek doesn't work on some special files but doesn't return an
 276      error, either. */
 277   if (fstat (0, &stats))
 278     {
 279       error (0, errno, "standard input");
 280       return 1;
 281     }
 282   if (S_ISREG (stats.st_mode))
 283     return tac (0, "standard input");
 284
 285 #ifdef _POSIX_VERSION
 286   newact.sa_handler = cleanup;
 287   sigemptyset (&newact.sa_mask);
 288   newact.sa_flags = 0;
 289
 290   sigaction (SIGINT, NULL, &oldact);
 291   sigint = oldact.sa_handler;
 292   if (sigint != SIG_IGN)
 293     sigaction (SIGINT, &newact, NULL);
 294
 295   sigaction (SIGHUP, NULL, &oldact);
 296   sighup = oldact.sa_handler;
 297   if (sighup != SIG_IGN)
 298     sigaction (SIGHUP, &newact, NULL);
 299
 300   sigaction (SIGPIPE, NULL, &oldact);
 301   sigpipe = oldact.sa_handler;
 302   if (sigpipe != SIG_IGN)
 303     sigaction (SIGPIPE, &newact, NULL);
 304
 305   sigaction (SIGTERM, NULL, &oldact);
 306   sigterm = oldact.sa_handler;
 307   if (sigterm != SIG_IGN)
 308     sigaction (SIGTERM, &newact, NULL);
 309 #else                           /* !_POSIX_VERSION */
 310   sigint = signal (SIGINT, SIG_IGN);
 311   if (sigint != SIG_IGN)
 312     signal (SIGINT, cleanup);
 313
 314   sighup = signal (SIGHUP, SIG_IGN);
 315   if (sighup != SIG_IGN)
 316     signal (SIGHUP, cleanup);
 317
 318   sigpipe = signal (SIGPIPE, SIG_IGN);
 319   if (sigpipe != SIG_IGN)
 320     signal (SIGPIPE, cleanup);
 321
 322   sigterm = signal (SIGTERM, SIG_IGN);
 323   if (sigterm != SIG_IGN)
 324     signal (SIGTERM, cleanup);
 325 #endif                          /* _POSIX_VERSION */
 326
 327   save_stdin ();
 328
 329   errors = tac_file (tempfile);
 330
 331   unlink (tempfile);
 332
 333 #ifdef _POSIX_VERSION
 334   newact.sa_handler = sigint;
 335   sigaction (SIGINT, &newact, NULL);
 336   newact.sa_handler = sighup;
 337   sigaction (SIGHUP, &newact, NULL);
 338   newact.sa_handler = sigterm;
 339   sigaction (SIGTERM, &newact, NULL);
 340   newact.sa_handler = sigpipe;
 341   sigaction (SIGPIPE, &newact, NULL);
 342 #else                           /* !_POSIX_VERSION */
 343   signal (SIGINT, sigint);
 344   signal (SIGHUP, sighup);
 345   signal (SIGTERM, sigterm);
 346   signal (SIGPIPE, sigpipe);
 347 #endif                          /* _POSIX_VERSION */
 348
 349   return errors;
 350 }
 351
 352 /* Make a copy of the standard input in `tempfile'. */
 353
 354 static void
 355 save_stdin ()
 356 {
 357   static char *template = NULL;
 358   static char *tempdir;
 359   int fd;
 360   int bytes_read;
 361
 362   if (template == NULL)
 363     {
 364       tempdir = getenv ("TMPDIR");
 365       if (tempdir == NULL)
 366         tempdir = "/tmp";
 367       template = xmalloc (strlen (tempdir) + 11);
 368     }
 369   sprintf (template, "%s/tacXXXXXX", tempdir);
 370   tempfile = mktemp (template);
 371
 372   fd = creat (tempfile, 0600);
 373   if (fd == -1)
 374     {
 375       error (0, errno, "%s", tempfile);
 376       cleanup ();
 377     }
 378   while ((bytes_read = safe_read (0, buffer, read_size)) > 0)
 379     if (full_write (fd, buffer, bytes_read) < 0)
 380       {
 381         error (0, errno, "%s", tempfile);
 382         cleanup ();
 383       }
 384   if (close (fd) < 0)
 385     {
 386       error (0, errno, "%s", tempfile);
 387       cleanup ();
 388     }
 389   if (bytes_read == -1)
 390     {
 391       error (0, errno, "read error");
 392       cleanup ();
 393     }
 394 }
 395
 396 /* Print FILE in reverse.
 397    Return 0 if ok, 1 if an error occurs. */
 398
 399 static int
 400 tac_file (file)
 401      char *file;
 402 {
 403   int fd, errors;
 404
 405   fd = open (file, O_RDONLY);
 406   if (fd == -1)
 407     {
 408       error (0, errno, "%s", file);
 409       return 1;
 410     }
 411   errors = tac (fd, file);
 412   if (close (fd) < 0)
 413     {
 414       error (0, errno, "%s", file);
 415       return 1;
 416     }
 417   return errors;
 418 }
 419
 420 /* Print in reverse the file open on descriptor FD for reading FILE.
 421    Return 0 if ok, 1 if an error occurs. */
 422
 423 static int
 424 tac (fd, file)
 425      int fd;
 426      char *file;
 427 {
 428   /* Pointer to the location in `buffer' where the search for
 429      the next separator will begin. */
 430   char *match_start;
 431   /* Pointer to one past the rightmost character in `buffer' that
 432      has not been printed yet. */
 433   char *past_end;
 434   unsigned saved_record_size;   /* Length of the record growing in `buffer'. */
 435   off_t file_pos;               /* Offset in the file of the next read. */
 436   /* Nonzero if `output' has not been called yet for any file.
 437      Only used when the separator is attached to the preceding record. */
 438   int first_time = 1;
 439   char first_char = *separator; /* Speed optimization, non-regexp. */
 440   char *separator1 = separator + 1; /* Speed optimization, non-regexp. */
 441   int match_length1 = match_length - 1; /* Speed optimization, non-regexp. */
 442   struct re_registers regs;
 443
 444   /* Find the size of the input file. */
 445   file_pos = lseek (fd, (off_t) 0, SEEK_END);
 446   if (file_pos < 1)
 447     return 0;                   /* It's an empty file. */
 448
 449   /* Arrange for the first read to lop off enough to leave the rest of the
 450      file a multiple of `read_size'.  Since `read_size' can change, this may
 451      not always hold during the program run, but since it usually will, leave
 452      it here for i/o efficiency (page/sector boundaries and all that).
 453      Note: the efficiency gain has not been verified. */
 454   saved_record_size = file_pos % read_size;
 455   if (saved_record_size == 0)
 456     saved_record_size = read_size;
 457   file_pos -= saved_record_size;
 458   /* `file_pos' now points to the start of the last (probably partial) block
 459      in the input file. */
 460
 461   lseek (fd, file_pos, SEEK_SET);
 462   if (safe_read (fd, buffer, saved_record_size) != saved_record_size)
 463     {
 464       error (0, errno, "%s", file);
 465       return 1;
 466     }
 467
 468   match_start = past_end = buffer + saved_record_size;
 469   /* For non-regexp search, move past impossible positions for a match. */
 470   if (sentinel_length)
 471     match_start -= match_length1;
 472
 473   for (;;)
 474     {
 475       /* Search backward from `match_start' - 1 to `buffer' for a match
 476          with `separator'; for speed, use strncmp if `separator' contains no
 477          metacharacters.
 478          If the match succeeds, set `match_start' to point to the start of
 479          the match and `match_length' to the length of the match.
 480          Otherwise, make `match_start' < `buffer'. */
 481       if (sentinel_length == 0)
 482         {
 483           int i = match_start - buffer;
 484           int ret;
 485
 486           ret = re_search (&compiled_separator, buffer, i, i - 1, -i, &regs);
 487           if (ret == -1)
 488             match_start = buffer - 1;
 489           else if (ret == -2)
 490             {
 491               error (0, 0, "error in regular expression search");
 492               cleanup ();
 493             }
 494           else
 495             {
 496               match_start = buffer + regs.start[0];
 497               match_length = regs.end[0] - regs.start[0];
 498             }
 499         }
 500       else
 501         {
 502           /* `match_length' is constant for non-regexp boundaries. */
 503           while (*--match_start != first_char
 504                  || (match_length1 && strncmp (match_start + 1, separator1,
 505                                                match_length1)))
 506             /* Do nothing. */ ;
 507         }
 508
 509       /* Check whether we backed off the front of `buffer' without finding
 510          a match for `separator'. */
 511       if (match_start < buffer)
 512         {
 513           if (file_pos == 0)
 514             {
 515               /* Hit the beginning of the file; print the remaining record. */
 516               output (buffer, past_end);
 517               return 0;
 518             }
 519
 520           saved_record_size = past_end - buffer;
 521           if (saved_record_size > read_size)
 522             {
 523               /* `buffer_size' is about twice `read_size', so since
 524                  we want to read in another `read_size' bytes before
 525                  the data already in `buffer', we need to increase
 526                  `buffer_size'. */
 527               char *newbuffer;
 528               int offset = sentinel_length ? sentinel_length : 1;
 529
 530               read_size *= 2;
 531               buffer_size = read_size * 2 + sentinel_length + 2;
 532               newbuffer = xrealloc (buffer - offset, buffer_size) + offset;
 533               /* Adjust the pointers for the new buffer location.  */
 534               match_start += newbuffer - buffer;
 535               past_end += newbuffer - buffer;
 536               buffer = newbuffer;
 537             }
 538
 539           /* Back up to the start of the next bufferfull of the file.  */
 540           if (file_pos >= read_size)
 541             file_pos -= read_size;
 542           else
 543             {
 544               read_size = file_pos;
 545               file_pos = 0;
 546             }
 547           lseek (fd, file_pos, SEEK_SET);
 548
 549           /* Shift the pending record data right to make room for the new. */
 550           bcopy (buffer, buffer + read_size, saved_record_size);
 551           past_end = buffer + read_size + saved_record_size;
 552           /* For non-regexp searches, avoid unneccessary scanning. */
 553           if (sentinel_length)
 554             match_start = buffer + read_size;
 555           else
 556             match_start = past_end;
 557
 558           if (safe_read (fd, buffer, read_size) != read_size)
 559             {
 560               error (0, errno, "%s", file);
 561               return 1;
 562             }
 563         }
 564       else
 565         {
 566           /* Found a match of `separator'. */
 567           if (separator_ends_record)
 568             {
 569               char *match_end = match_start + match_length;
 570
 571               /* If this match of `separator' isn't at the end of the
 572                  file, print the record. */
 573               if (first_time == 0 || match_end != past_end)
 574                 output (match_end, past_end);
 575               past_end = match_end;
 576               first_time = 0;
 577             }
 578           else
 579             {
 580               output (match_start, past_end);
 581               past_end = match_start;
 582             }
 583           match_start -= match_length - 1;
 584         }
 585     }
 586 }
 587
 588 /* Print the characters from START to PAST_END - 1.
 589    If START is NULL, just flush the buffer. */
 590
 591 static void
 592 output (start, past_end)
 593      char *start;
 594      char *past_end;
 595 {
 596   static char buffer[WRITESIZE];
 597   static int bytes_in_buffer = 0;
 598   int bytes_to_add = past_end - start;
 599   int bytes_available = WRITESIZE - bytes_in_buffer;
 600
 601   if (start == 0)
 602     {
 603       xwrite (STDOUT_FILENO, buffer, bytes_in_buffer);
 604       bytes_in_buffer = 0;
 605       return;
 606     }
 607
 608   /* Write out as many full buffers as possible. */
 609   while (bytes_to_add >= bytes_available)
 610     {
 611       bcopy (start, buffer + bytes_in_buffer, bytes_available);
 612       bytes_to_add -= bytes_available;
 613       start += bytes_available;
 614       xwrite (STDOUT_FILENO, buffer, WRITESIZE);
 615       bytes_in_buffer = 0;
 616       bytes_available = WRITESIZE;
 617     }
 618
 619   bcopy (start, buffer + bytes_in_buffer, bytes_to_add);
 620   bytes_in_buffer += bytes_to_add;
 621 }
 622
 623 static RETSIGTYPE
 624 cleanup ()
 625 {
 626   unlink (tempfile);
 627   exit (1);
 628 }
 629
 630 static void
 631 xwrite (desc, buffer, size)
 632      int desc;
 633      char *buffer;
 634      int size;
 635 {
 636   if (full_write (desc, buffer, size) < 0)
 637     {
 638       error (0, errno, "write error");
 639       cleanup ();
 640     }
 641 }
 642
 643 /* Allocate N bytes of memory dynamically, with error checking.  */
 644
 645 static char *
 646 xmalloc (n)
 647      unsigned n;
 648 {
 649   char *p;
 650
 651   p = malloc (n);
 652   if (p == 0)
 653     {
 654       error (0, 0, "virtual memory exhausted");
 655       cleanup ();
 656     }
 657   return p;
 658 }
 659
 660 /* Change the size of memory area P to N bytes, with error checking. */
 661
 662 static char *
 663 xrealloc (p, n)
 664      char *p;
 665      unsigned n;
 666 {
 667   p = realloc (p, n);
 668   if (p == 0)
 669     {
 670       error (0, 0, "virtual memory exhausted");
 671       cleanup ();
 672     }
 673   return p;
 674 }