src/tac.c

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