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