src/tac.c

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