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 %s"), quote (tempfile));
 458       return false;
 459     }
 460
 461   tmp = fdopen (fd, (O_BINARY ? "w+b" : "w+"));
 462   if (! tmp)
 463     {
 464       error (0, errno, _("cannot open %s for writing"), quote (tempfile));
 465       close (fd);
 466       unlink (tempfile);
 467       return false;
 468     }
 469
 470   record_or_unlink_tempfile (tempfile, tmp);
 471
 472   while (1)
 473     {
 474       size_t bytes_read = safe_read (input_fd, G_buffer, read_size);
 475       if (bytes_read == 0)
 476         break;
 477       if (bytes_read == SAFE_READ_ERROR)
 478         {
 479           error (0, errno, _("%s: read error"), quotearg_colon (file));
 480           goto Fail;
 481         }
 482
 483       if (fwrite (G_buffer, 1, bytes_read, tmp) != bytes_read)
 484         {
 485           error (0, errno, _("%s: write error"), quotearg_colon (tempfile));
 486           goto Fail;
 487         }
 488     }
 489
 490   if (fflush (tmp) != 0)
 491     {
 492       error (0, errno, _("%s: write error"), quotearg_colon (tempfile));
 493       goto Fail;
 494     }
 495
 496   *g_tmp = tmp;
 497   *g_tempfile = tempfile;
 498   return true;
 499
 500  Fail:
 501   fclose (tmp);
 502   return false;
 503 }
 504
 505 /* Copy INPUT_FD to a temporary, then tac that file.
 506    Return true if successful.  */
 507
 508 static bool
 509 tac_nonseekable (int input_fd, const char *file)
 510 {
 511   FILE *tmp_stream;
 512   char *tmp_file;
 513   return (copy_to_temp (&tmp_stream, &tmp_file, input_fd, file)
 514           && tac_seekable (fileno (tmp_stream), tmp_file));
 515 }
 516
 517 /* Print FILE in reverse, copying it to a temporary
 518    file first if it is not seekable.
 519    Return true if successful.  */
 520
 521 static bool
 522 tac_file (const char *filename)
 523 {
 524   bool ok;
 525   off_t file_size;
 526   int fd;
 527   bool is_stdin = STREQ (filename, "-");
 528
 529   if (is_stdin)
 530     {
 531       have_read_stdin = true;
 532       fd = STDIN_FILENO;
 533       filename = _("standard input");
 534       if (O_BINARY && ! isatty (STDIN_FILENO))
 535         freopen (NULL, "rb", stdin);
 536     }
 537   else
 538     {
 539       fd = open (filename, O_RDONLY | O_BINARY);
 540       if (fd < 0)
 541         {
 542           error (0, errno, _("cannot open %s for reading"), quote (filename));
 543           return false;
 544         }
 545     }
 546
 547   file_size = lseek (fd, (off_t) 0, SEEK_END);
 548
 549   ok = (file_size < 0 || isatty (fd)
 550         ? tac_nonseekable (fd, filename)
 551         : tac_seekable (fd, filename));
 552
 553   if (!is_stdin && close (fd) != 0)
 554     {
 555       error (0, errno, _("%s: read error"), quotearg_colon (filename));
 556       ok = false;
 557     }
 558   return ok;
 559 }
 560
 561 int
 562 main (int argc, char **argv)
 563 {
 564   const char *error_message;    /* Return value from re_compile_pattern. */
 565   int optc;
 566   bool ok;
 567   size_t half_buffer_size;
 568
 569   /* Initializer for file_list if no file-arguments
 570      were specified on the command line.  */
 571   static char const *const default_file_list[] = {"-", NULL};
 572   char const *const *file;
 573
 574   initialize_main (&argc, &argv);
 575   set_program_name (argv[0]);
 576   setlocale (LC_ALL, "");
 577   bindtextdomain (PACKAGE, LOCALEDIR);
 578   textdomain (PACKAGE);
 579
 580   atexit (close_stdout);
 581
 582   separator = "\n";
 583   sentinel_length = 1;
 584   separator_ends_record = true;
 585
 586   while ((optc = getopt_long (argc, argv, "brs:", longopts, NULL)) != -1)
 587     {
 588       switch (optc)
 589         {
 590         case 'b':
 591           separator_ends_record = false;
 592           break;
 593         case 'r':
 594           sentinel_length = 0;
 595           break;
 596         case 's':
 597           separator = optarg;
 598           if (*separator == 0)
 599             error (EXIT_FAILURE, 0, _("separator cannot be empty"));
 600           break;
 601         case_GETOPT_HELP_CHAR;
 602         case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
 603         default:
 604           usage (EXIT_FAILURE);
 605         }
 606     }
 607
 608   if (sentinel_length == 0)
 609     {
 610       compiled_separator.buffer = NULL;
 611       compiled_separator.allocated = 0;
 612       compiled_separator.fastmap = compiled_separator_fastmap;
 613       compiled_separator.translate = NULL;
 614       error_message = re_compile_pattern (separator, strlen (separator),
 615                                           &compiled_separator);
 616       if (error_message)
 617         error (EXIT_FAILURE, 0, "%s", error_message);
 618     }
 619   else
 620     match_length = sentinel_length = strlen (separator);
 621
 622   read_size = INITIAL_READSIZE;
 623   while (sentinel_length >= read_size / 2)
 624     {
 625       if (SIZE_MAX / 2 < read_size)
 626         xalloc_die ();
 627       read_size *= 2;
 628     }
 629   half_buffer_size = read_size + sentinel_length + 1;
 630   G_buffer_size = 2 * half_buffer_size;
 631   if (! (read_size < half_buffer_size && half_buffer_size < G_buffer_size))
 632     xalloc_die ();
 633   G_buffer = xmalloc (G_buffer_size);
 634   if (sentinel_length)
 635     {
 636       strcpy (G_buffer, separator);
 637       G_buffer += sentinel_length;
 638     }
 639   else
 640     {
 641       ++G_buffer;
 642     }
 643
 644   file = (optind < argc
 645           ? (char const *const *) &argv[optind]
 646           : default_file_list);
 647
 648   if (O_BINARY && ! isatty (STDOUT_FILENO))
 649     freopen (NULL, "wb", stdout);
 650
 651   {
 652     size_t i;
 653     ok = true;
 654     for (i = 0; file[i]; ++i)
 655       ok &= tac_file (file[i]);
 656   }
 657
 658   /* Flush the output buffer. */
 659   output ((char *) NULL, (char *) NULL);
 660
 661   if (have_read_stdin && close (STDIN_FILENO) < 0)
 662     error (EXIT_FAILURE, errno, "-");
 663   exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
 664 }