src/tac.c

   1 /* tac - concatenate and print files in reverse
   2    Copyright (C) 1988-1991, 1995-2006, 2008 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 3 of the License, or
   7    (at your option) 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, see <http://www.gnu.org/licenses/>.  */
  16
  17 /* Written by Jay Lepreau (lepreau@cs.utah.edu).
  18    GNU enhancements by David MacKenzie (djm@gnu.ai.mit.edu). */
  19
  20 /* Copy each FILE, or the standard input if none are given or when a
  21    FILE name of "-" is encountered, to the standard output with the
  22    order of the records reversed.  The records are separated by
  23    instances of a string, or a newline if none is given.  By default, the
  24    separator string is attached to the end of the record that it
  25    follows in the file.
  26
  27    Options:
  28    -b, --before                 The separator is attached to the beginning
  29                                 of the record that it precedes in the file.
  30    -r, --regex                  The separator is a regular expression.
  31    -s, --separator=separator    Use SEPARATOR as the record separator.
  32
  33    To reverse a file byte by byte, use (in bash, ksh, or sh):
  34 tac -r -s '.\|
  35 ' file */
  36
  37 #include <config.h>
  38
  39 #include <stdio.h>
  40 #include <getopt.h>
  41 #include <sys/types.h>
  42 #include "system.h"
  43
  44 #include <regex.h>
  45
  46 #include "error.h"
  47 #include "quote.h"
  48 #include "quotearg.h"
  49 #include "safe-read.h"
  50 #include "stdlib--.h"
  51
  52 /* The official name of this program (e.g., no `g' prefix).  */
  53 #define PROGRAM_NAME "tac"
  54
  55 #define AUTHORS \
  56   proper_name ("Jay Lepreau"), \
  57   proper_name ("David MacKenzie")
  58
  59 #if defined __MSDOS__ || defined _WIN32
  60 /* Define this to non-zero on systems for which the regular mechanism
  61    (of unlinking an open file and expecting to be able to write, seek
  62    back to the beginning, then reread it) doesn't work.  E.g., on Windows
  63    and DOS systems.  */
  64 # define DONT_UNLINK_WHILE_OPEN 1
  65 #endif
  66
  67
  68 #ifndef DEFAULT_TMPDIR
  69 # define DEFAULT_TMPDIR "/tmp"
  70 #endif
  71
  72 /* The number of bytes per atomic read. */
  73 #define INITIAL_READSIZE 8192
  74
  75 /* The number of bytes per atomic write. */
  76 #define WRITESIZE 8192
  77
  78 /* The string that separates the records of the file. */
  79 static char const *separator;
  80
  81 /* True if we have ever read standard input.  */
  82 static bool have_read_stdin = false;
  83
  84 /* If true, print `separator' along with the record preceding it
  85    in the file; otherwise with the record following it. */
  86 static bool separator_ends_record;
  87
  88 /* 0 if `separator' is to be matched as a regular expression;
  89    otherwise, the length of `separator', used as a sentinel to
  90    stop the search. */
  91 static size_t sentinel_length;
  92
  93 /* The length of a match with `separator'.  If `sentinel_length' is 0,
  94    `match_length' is computed every time a match succeeds;
  95    otherwise, it is simply the length of `separator'. */
  96 static size_t match_length;
  97
  98 /* The input buffer. */
  99 static char *G_buffer;
 100
 101 /* The number of bytes to read at once into `buffer'. */
 102 static size_t read_size;
 103
 104 /* The size of `buffer'.  This is read_size * 2 + sentinel_length + 2.
 105    The extra 2 bytes allow `past_end' to have a value beyond the
 106    end of `G_buffer' and `match_start' to run off the front of `G_buffer'. */
 107 static size_t G_buffer_size;
 108
 109 /* The compiled regular expression representing `separator'. */
 110 static struct re_pattern_buffer compiled_separator;
 111 static char compiled_separator_fastmap[UCHAR_MAX + 1];
 112 static struct re_registers regs;
 113
 114 static struct option const longopts[] =
 115 {
 116   {"before", no_argument, NULL, 'b'},
 117   {"regex", no_argument, NULL, 'r'},
 118   {"separator", required_argument, NULL, 's'},
 119   {GETOPT_HELP_OPTION_DECL},
 120   {GETOPT_VERSION_OPTION_DECL},
 121   {NULL, 0, NULL, 0}
 122 };
 123
 124 void
 125 usage (int status)
 126 {
 127   if (status != EXIT_SUCCESS)
 128     fprintf (stderr, _("Try `%s --help' for more information.\n"),
 129              program_name);
 130   else
 131     {
 132       printf (_("\
 133 Usage: %s [OPTION]... [FILE]...\n\
 134 "),
 135               program_name);
 136       fputs (_("\
 137 Write each FILE to standard output, last line first.\n\
 138 With no FILE, or when FILE is -, read standard input.\n\
 139 \n\
 140 "), stdout);
 141       fputs (_("\
 142 Mandatory arguments to long options are mandatory for short options too.\n\
 143 "), stdout);
 144       fputs (_("\
 145   -b, --before             attach the separator before instead of after\n\
 146   -r, --regex              interpret the separator as a regular expression\n\
 147   -s, --separator=STRING   use STRING as the separator instead of newline\n\
 148 "), stdout);
 149       fputs (HELP_OPTION_DESCRIPTION, stdout);
 150       fputs (VERSION_OPTION_DESCRIPTION, stdout);
 151       emit_bug_reporting_address ();
 152     }
 153   exit (status);
 154 }
 155
 156 /* Print the characters from START to PAST_END - 1.
 157    If START is NULL, just flush the buffer. */
 158
 159 static void
 160 output (const char *start, const char *past_end)
 161 {
 162   static char buffer[WRITESIZE];
 163   static size_t bytes_in_buffer = 0;
 164   size_t bytes_to_add = past_end - start;
 165   size_t bytes_available = WRITESIZE - bytes_in_buffer;
 166
 167   if (start == 0)
 168     {
 169       fwrite (buffer, 1, bytes_in_buffer, stdout);
 170       bytes_in_buffer = 0;
 171       return;
 172     }
 173
 174   /* Write out as many full buffers as possible. */
 175   while (bytes_to_add >= bytes_available)
 176     {
 177       memcpy (buffer + bytes_in_buffer, start, bytes_available);
 178       bytes_to_add -= bytes_available;
 179       start += bytes_available;
 180       fwrite (buffer, 1, WRITESIZE, stdout);
 181       bytes_in_buffer = 0;
 182       bytes_available = WRITESIZE;
 183     }
 184
 185   memcpy (buffer + bytes_in_buffer, start, bytes_to_add);
 186   bytes_in_buffer += bytes_to_add;
 187 }
 188
 189 /* Print in reverse the file open on descriptor FD for reading FILE.
 190    Return true if successful.  */
 191
 192 static bool
 193 tac_seekable (int input_fd, const char *file)
 194 {
 195   /* Pointer to the location in `G_buffer' where the search for
 196      the next separator will begin. */
 197   char *match_start;
 198
 199   /* Pointer to one past the rightmost character in `G_buffer' that
 200      has not been printed yet. */
 201   char *past_end;
 202
 203   /* Length of the record growing in `G_buffer'. */
 204   size_t saved_record_size;
 205
 206   /* Offset in the file of the next read. */
 207   off_t file_pos;
 208
 209   /* True if `output' has not been called yet for any file.
 210      Only used when the separator is attached to the preceding record. */
 211   bool first_time = true;
 212   char first_char = *separator; /* Speed optimization, non-regexp. */
 213   char const *separator1 = separator + 1; /* Speed optimization, non-regexp. */
 214   size_t match_length1 = match_length - 1; /* Speed optimization, non-regexp. */
 215
 216   /* Find the size of the input file. */
 217   file_pos = lseek (input_fd, (off_t) 0, SEEK_END);
 218   if (file_pos < 1)
 219     return true;                        /* It's an empty file. */
 220
 221   /* Arrange for the first read to lop off enough to leave the rest of the
 222      file a multiple of `read_size'.  Since `read_size' can change, this may
 223      not always hold during the program run, but since it usually will, leave
 224      it here for i/o efficiency (page/sector boundaries and all that).
 225      Note: the efficiency gain has not been verified. */
 226   saved_record_size = file_pos % read_size;
 227   if (saved_record_size == 0)
 228     saved_record_size = read_size;
 229   file_pos -= saved_record_size;
 230   /* `file_pos' now points to the start of the last (probably partial) block
 231      in the input file. */
 232
 233   if (lseek (input_fd, file_pos, SEEK_SET) < 0)
 234     error (0, errno, _("%s: seek failed"), quotearg_colon (file));
 235
 236   if (safe_read (input_fd, G_buffer, saved_record_size) != saved_record_size)
 237     {
 238       error (0, errno, _("%s: read error"), quotearg_colon (file));
 239       return false;
 240     }
 241
 242   match_start = past_end = G_buffer + saved_record_size;
 243   /* For non-regexp search, move past impossible positions for a match. */
 244   if (sentinel_length)
 245     match_start -= match_length1;
 246
 247   for (;;)
 248     {
 249       /* Search backward from `match_start' - 1 to `G_buffer' for a match
 250          with `separator'; for speed, use strncmp if `separator' contains no
 251          metacharacters.
 252          If the match succeeds, set `match_start' to point to the start of
 253          the match and `match_length' to the length of the match.
 254          Otherwise, make `match_start' < `G_buffer'. */
 255       if (sentinel_length == 0)
 256         {
 257           size_t i = match_start - G_buffer;
 258           regoff_t ri = i;
 259           regoff_t range = 1 - ri;
 260           regoff_t ret;
 261
 262           if (1 < range)
 263             error (EXIT_FAILURE, 0, _("record too large"));
 264
 265           if (range == 1
 266               || ((ret = re_search (&compiled_separator, G_buffer,
 267                                     i, i - 1, range, &regs))
 268                   == -1))
 269             match_start = G_buffer - 1;
 270           else if (ret == -2)
 271             {
 272               error (EXIT_FAILURE, 0,
 273                      _("error in regular expression search"));
 274             }
 275           else
 276             {
 277               match_start = G_buffer + regs.start[0];
 278               match_length = regs.end[0] - regs.start[0];
 279             }
 280         }
 281       else
 282         {
 283           /* `match_length' is constant for non-regexp boundaries. */
 284           while (*--match_start != first_char
 285                  || (match_length1 && strncmp (match_start + 1, separator1,
 286                                                match_length1)))
 287             /* Do nothing. */ ;
 288         }
 289
 290       /* Check whether we backed off the front of `G_buffer' without finding
 291          a match for `separator'. */
 292       if (match_start < G_buffer)
 293         {
 294           if (file_pos == 0)
 295             {
 296               /* Hit the beginning of the file; print the remaining record. */
 297               output (G_buffer, past_end);
 298               return true;
 299             }
 300
 301           saved_record_size = past_end - G_buffer;
 302           if (saved_record_size > read_size)
 303             {
 304               /* `G_buffer_size' is about twice `read_size', so since
 305                  we want to read in another `read_size' bytes before
 306                  the data already in `G_buffer', we need to increase
 307                  `G_buffer_size'. */
 308               char *newbuffer;
 309               size_t offset = sentinel_length ? sentinel_length : 1;
 310               ptrdiff_t match_start_offset = match_start - G_buffer;
 311               ptrdiff_t past_end_offset = past_end - G_buffer;
 312               size_t old_G_buffer_size = G_buffer_size;
 313
 314               read_size *= 2;
 315               G_buffer_size = read_size * 2 + sentinel_length + 2;
 316               if (G_buffer_size < old_G_buffer_size)
 317                 xalloc_die ();
 318               newbuffer = xrealloc (G_buffer - offset, G_buffer_size);
 319               newbuffer += offset;
 320               /* Adjust the pointers for the new buffer location.  */
 321               match_start = newbuffer + match_start_offset;
 322               past_end = newbuffer + past_end_offset;
 323               G_buffer = newbuffer;
 324             }
 325
 326           /* Back up to the start of the next bufferfull of the file.  */
 327           if (file_pos >= read_size)
 328             file_pos -= read_size;
 329           else
 330             {
 331               read_size = file_pos;
 332               file_pos = 0;
 333             }
 334           if (lseek (input_fd, file_pos, SEEK_SET) < 0)
 335             error (0, errno, _("%s: seek failed"), quotearg_colon (file));
 336
 337           /* Shift the pending record data right to make room for the new.
 338              The source and destination regions probably overlap.  */
 339           memmove (G_buffer + read_size, G_buffer, saved_record_size);
 340           past_end = G_buffer + read_size + saved_record_size;
 341           /* For non-regexp searches, avoid unneccessary scanning. */
 342           if (sentinel_length)
 343             match_start = G_buffer + read_size;
 344           else
 345             match_start = past_end;
 346
 347           if (safe_read (input_fd, G_buffer, read_size) != read_size)
 348             {
 349               error (0, errno, _("%s: read error"), quotearg_colon (file));
 350               return false;
 351             }
 352         }
 353       else
 354         {
 355           /* Found a match of `separator'. */
 356           if (separator_ends_record)
 357             {
 358               char *match_end = match_start + match_length;
 359
 360               /* If this match of `separator' isn't at the end of the
 361                  file, print the record. */
 362               if (!first_time || match_end != past_end)
 363                 output (match_end, past_end);
 364               past_end = match_end;
 365               first_time = false;
 366             }
 367           else
 368             {
 369               output (match_start, past_end);
 370               past_end = match_start;
 371             }
 372
 373           /* For non-regex matching, we can back up.  */
 374           if (sentinel_length > 0)
 375             match_start -= match_length - 1;
 376         }
 377     }
 378 }
 379
 380 #if DONT_UNLINK_WHILE_OPEN
 381
 382 /* FIXME-someday: remove all of this DONT_UNLINK_WHILE_OPEN junk.
 383    Using atexit like this is wrong, since it can fail
 384    when called e.g. 32 or more times.
 385    But this isn't a big deal, since the code is used only on WOE/DOS
 386    systems, and few people invoke tac on that many nonseekable files.  */
 387
 388 static const char *file_to_remove;
 389 static FILE *fp_to_close;
 390
 391 static void
 392 unlink_tempfile (void)
 393 {
 394   fclose (fp_to_close);
 395   unlink (file_to_remove);
 396 }
 397
 398 static void
 399 record_or_unlink_tempfile (char const *fn, FILE *fp)
 400 {
 401   if (!file_to_remove)
 402     {
 403       file_to_remove = fn;
 404       fp_to_close = fp;
 405       atexit (unlink_tempfile);
 406     }
 407 }
 408
 409 #else
 410
 411 static void
 412 record_or_unlink_tempfile (char const *fn, FILE *fp ATTRIBUTE_UNUSED)
 413 {
 414   unlink (fn);
 415 }
 416
 417 #endif
 418
 419 /* Copy from file descriptor INPUT_FD (corresponding to the named FILE) to
 420    a temporary file, and set *G_TMP and *G_TEMPFILE to the resulting stream
 421    and file name.  Return true if successful.  */
 422
 423 static bool
 424 copy_to_temp (FILE **g_tmp, char **g_tempfile, int input_fd, char const *file)
 425 {
 426   static char *template = NULL;
 427   static char const *tempdir;
 428   char *tempfile;
 429   FILE *tmp;
 430   int fd;
 431
 432   if (template == NULL)
 433     {
 434       char const * const Template = "%s/tacXXXXXX";
 435       tempdir = getenv ("TMPDIR");
 436       if (tempdir == NULL)
 437         tempdir = DEFAULT_TMPDIR;
 438
 439       /* Subtract 2 for `%s' and add 1 for the trailing NUL byte.  */
 440       template = xmalloc (strlen (tempdir) + strlen (Template) - 2 + 1);
 441       sprintf (template, Template, tempdir);
 442     }
 443
 444   /* FIXME: there's a small window between a successful mkstemp call
 445      and the unlink that's performed by record_or_unlink_tempfile.
 446      If we're interrupted in that interval, this code fails to remove
 447      the temporary file.  On systems that define DONT_UNLINK_WHILE_OPEN,
 448      the window is much larger -- it extends to the atexit-called
 449      unlink_tempfile.
 450      FIXME: clean up upon fatal signal.  Don't block them, in case
 451      $TMPFILE is a remote file system.  */
 452
 453   tempfile = template;
 454   fd = mkstemp (template);
 455   if (fd < 0)
 456     {
 457       error (0, errno, _("cannot create temporary file in %s"),
 458              quote (tempdir));
 459       return false;
 460     }
 461
 462   tmp = fdopen (fd, (O_BINARY ? "w+b" : "w+"));
 463   if (! tmp)
 464     {
 465       error (0, errno, _("cannot open %s for writing"), quote (tempfile));
 466       close (fd);
 467       unlink (tempfile);
 468       return false;
 469     }
 470
 471   record_or_unlink_tempfile (tempfile, tmp);
 472
 473   while (1)
 474     {
 475       size_t bytes_read = safe_read (input_fd, G_buffer, read_size);
 476       if (bytes_read == 0)
 477         break;
 478       if (bytes_read == SAFE_READ_ERROR)
 479         {
 480           error (0, errno, _("%s: read error"), quotearg_colon (file));
 481           goto Fail;
 482         }
 483
 484       if (fwrite (G_buffer, 1, bytes_read, tmp) != bytes_read)
 485         {
 486           error (0, errno, _("%s: write error"), quotearg_colon (tempfile));
 487           goto Fail;
 488         }
 489     }
 490
 491   if (fflush (tmp) != 0)
 492     {
 493       error (0, errno, _("%s: write error"), quotearg_colon (tempfile));
 494       goto Fail;
 495     }
 496
 497   *g_tmp = tmp;
 498   *g_tempfile = tempfile;
 499   return true;
 500
 501  Fail:
 502   fclose (tmp);
 503   return false;
 504 }
 505
 506 /* Copy INPUT_FD to a temporary, then tac that file.
 507    Return true if successful.  */
 508
 509 static bool
 510 tac_nonseekable (int input_fd, const char *file)
 511 {
 512   FILE *tmp_stream;
 513   char *tmp_file;
 514   return (copy_to_temp (&tmp_stream, &tmp_file, input_fd, file)
 515           && tac_seekable (fileno (tmp_stream), tmp_file));
 516 }
 517
 518 /* Print FILE in reverse, copying it to a temporary
 519    file first if it is not seekable.
 520    Return true if successful.  */
 521
 522 static bool
 523 tac_file (const char *filename)
 524 {
 525   bool ok;
 526   off_t file_size;
 527   int fd;
 528   bool is_stdin = STREQ (filename, "-");
 529
 530   if (is_stdin)
 531     {
 532       have_read_stdin = true;
 533       fd = STDIN_FILENO;
 534       filename = _("standard input");
 535       if (O_BINARY && ! isatty (STDIN_FILENO))
 536         freopen (NULL, "rb", stdin);
 537     }
 538   else
 539     {
 540       fd = open (filename, O_RDONLY | O_BINARY);
 541       if (fd < 0)
 542         {
 543           error (0, errno, _("cannot open %s for reading"), quote (filename));
 544           return false;
 545         }
 546     }
 547
 548   file_size = lseek (fd, (off_t) 0, SEEK_END);
 549
 550   ok = (file_size < 0 || isatty (fd)
 551         ? tac_nonseekable (fd, filename)
 552         : tac_seekable (fd, filename));
 553
 554   if (!is_stdin && close (fd) != 0)
 555     {
 556       error (0, errno, _("%s: read error"), quotearg_colon (filename));
 557       ok = false;
 558     }
 559   return ok;
 560 }
 561
 562 int
 563 main (int argc, char **argv)
 564 {
 565   const char *error_message;    /* Return value from re_compile_pattern. */
 566   int optc;
 567   bool ok;
 568   size_t half_buffer_size;
 569
 570   /* Initializer for file_list if no file-arguments
 571      were specified on the command line.  */
 572   static char const *const default_file_list[] = {"-", NULL};
 573   char const *const *file;
 574
 575   initialize_main (&argc, &argv);
 576   set_program_name (argv[0]);
 577   setlocale (LC_ALL, "");
 578   bindtextdomain (PACKAGE, LOCALEDIR);
 579   textdomain (PACKAGE);
 580
 581   atexit (close_stdout);
 582
 583   separator = "\n";
 584   sentinel_length = 1;
 585   separator_ends_record = true;
 586
 587   while ((optc = getopt_long (argc, argv, "brs:", longopts, NULL)) != -1)
 588     {
 589       switch (optc)
 590         {
 591         case 'b':
 592           separator_ends_record = false;
 593           break;
 594         case 'r':
 595           sentinel_length = 0;
 596           break;
 597         case 's':
 598           separator = optarg;
 599           if (*separator == 0)
 600             error (EXIT_FAILURE, 0, _("separator cannot be empty"));
 601           break;
 602         case_GETOPT_HELP_CHAR;
 603         case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
 604         default:
 605           usage (EXIT_FAILURE);
 606         }
 607     }
 608
 609   if (sentinel_length == 0)
 610     {
 611       compiled_separator.buffer = NULL;
 612       compiled_separator.allocated = 0;
 613       compiled_separator.fastmap = compiled_separator_fastmap;
 614       compiled_separator.translate = NULL;
 615       error_message = re_compile_pattern (separator, strlen (separator),
 616                                           &compiled_separator);
 617       if (error_message)
 618         error (EXIT_FAILURE, 0, "%s", error_message);
 619     }
 620   else
 621     match_length = sentinel_length = strlen (separator);
 622
 623   read_size = INITIAL_READSIZE;
 624   while (sentinel_length >= read_size / 2)
 625     {
 626       if (SIZE_MAX / 2 < read_size)
 627         xalloc_die ();
 628       read_size *= 2;
 629     }
 630   half_buffer_size = read_size + sentinel_length + 1;
 631   G_buffer_size = 2 * half_buffer_size;
 632   if (! (read_size < half_buffer_size && half_buffer_size < G_buffer_size))
 633     xalloc_die ();
 634   G_buffer = xmalloc (G_buffer_size);
 635   if (sentinel_length)
 636     {
 637       strcpy (G_buffer, separator);
 638       G_buffer += sentinel_length;
 639     }
 640   else
 641     {
 642       ++G_buffer;
 643     }
 644
 645   file = (optind < argc
 646           ? (char const *const *) &argv[optind]
 647           : default_file_list);
 648
 649   if (O_BINARY && ! isatty (STDOUT_FILENO))
 650     freopen (NULL, "wb", stdout);
 651
 652   {
 653     size_t i;
 654     ok = true;
 655     for (i = 0; file[i]; ++i)
 656       ok &= tac_file (file[i]);
 657   }
 658
 659   /* Flush the output buffer. */
 660   output ((char *) NULL, (char *) NULL);
 661
 662   if (have_read_stdin && close (STDIN_FILENO) < 0)
 663     error (EXIT_FAILURE, errno, "-");
 664   exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
 665 }