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