src/tac.c

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