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