src/tac.c

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