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