src/tac.c

   1 /* tac - concatenate and print files in reverse
   2    Copyright (C) 1988-1991, 1995-2004 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 "system.h"
  44
  45 #include <regex.h>
  46
  47 #include "error.h"
  48 #include "quote.h"
  49 #include "safe-read.h"
  50
  51 /* The official name of this program (e.g., no `g' prefix).  */
  52 #define PROGRAM_NAME "tac"
  53
  54 #define AUTHORS "Jay Lepreau", "David MacKenzie"
  55
  56 #if defined __MSDOS__ || defined _WIN32
  57 /* Define this to non-zero on systems for which the regular mechanism
  58    (of unlinking an open file and expecting to be able to write, seek
  59    back to the beginning, then reread it) doesn't work.  E.g., on Windows
  60    and DOS systems.  */
  61 # define DONT_UNLINK_WHILE_OPEN 1
  62 #endif
  63
  64
  65 #ifndef DEFAULT_TMPDIR
  66 # define DEFAULT_TMPDIR "/tmp"
  67 #endif
  68
  69 /* The number of bytes per atomic read. */
  70 #define INITIAL_READSIZE 8192
  71
  72 /* The number of bytes per atomic write. */
  73 #define WRITESIZE 8192
  74
  75 /* The name this program was run with. */
  76 char *program_name;
  77
  78 /* The string that separates the records of the file. */
  79 static char *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
 112 static struct option const longopts[] =
 113 {
 114   {"before", no_argument, NULL, 'b'},
 115   {"regex", no_argument, NULL, 'r'},
 116   {"separator", required_argument, NULL, 's'},
 117   {GETOPT_HELP_OPTION_DECL},
 118   {GETOPT_VERSION_OPTION_DECL},
 119   {NULL, 0, NULL, 0}
 120 };
 121
 122 void
 123 usage (int status)
 124 {
 125   if (status != EXIT_SUCCESS)
 126     fprintf (stderr, _("Try `%s --help' for more information.\n"),
 127              program_name);
 128   else
 129     {
 130       printf (_("\
 131 Usage: %s [OPTION]... [FILE]...\n\
 132 "),
 133               program_name);
 134       fputs (_("\
 135 Write each FILE to standard output, last line first.\n\
 136 With no FILE, or when FILE is -, read standard input.\n\
 137 \n\
 138 "), stdout);
 139       fputs (_("\
 140 Mandatory arguments to long options are mandatory for short options too.\n\
 141 "), stdout);
 142       fputs (_("\
 143   -b, --before             attach the separator before instead of after\n\
 144   -r, --regex              interpret the separator as a regular expression\n\
 145   -s, --separator=STRING   use STRING as the separator instead of newline\n\
 146 "), stdout);
 147       fputs (HELP_OPTION_DESCRIPTION, stdout);
 148       fputs (VERSION_OPTION_DESCRIPTION, stdout);
 149       printf (_("\nReport bugs to <%s>.\n"), PACKAGE_BUGREPORT);
 150     }
 151   exit (status);
 152 }
 153
 154 /* Print the characters from START to PAST_END - 1.
 155    If START is NULL, just flush the buffer. */
 156
 157 static void
 158 output (const char *start, const char *past_end)
 159 {
 160   static char buffer[WRITESIZE];
 161   static size_t bytes_in_buffer = 0;
 162   size_t bytes_to_add = past_end - start;
 163   size_t bytes_available = WRITESIZE - bytes_in_buffer;
 164
 165   if (start == 0)
 166     {
 167       fwrite (buffer, 1, bytes_in_buffer, stdout);
 168       bytes_in_buffer = 0;
 169       return;
 170     }
 171
 172   /* Write out as many full buffers as possible. */
 173   while (bytes_to_add >= bytes_available)
 174     {
 175       memcpy (buffer + bytes_in_buffer, start, bytes_available);
 176       bytes_to_add -= bytes_available;
 177       start += bytes_available;
 178       fwrite (buffer, 1, WRITESIZE, stdout);
 179       bytes_in_buffer = 0;
 180       bytes_available = WRITESIZE;
 181     }
 182
 183   memcpy (buffer + bytes_in_buffer, start, bytes_to_add);
 184   bytes_in_buffer += bytes_to_add;
 185 }
 186
 187 /* Print in reverse the file open on descriptor FD for reading FILE.
 188    Return true if successful.  */
 189
 190 static bool
 191 tac_seekable (int input_fd, const char *file)
 192 {
 193   /* Pointer to the location in `G_buffer' where the search for
 194      the next separator will begin. */
 195   char *match_start;
 196
 197   /* Pointer to one past the rightmost character in `G_buffer' that
 198      has not been printed yet. */
 199   char *past_end;
 200
 201   /* Length of the record growing in `G_buffer'. */
 202   size_t saved_record_size;
 203
 204   /* Offset in the file of the next read. */
 205   off_t file_pos;
 206
 207   /* True if `output' has not been called yet for any file.
 208      Only used when the separator is attached to the preceding record. */
 209   bool first_time = true;
 210   char first_char = *separator; /* Speed optimization, non-regexp. */
 211   char *separator1 = separator + 1; /* Speed optimization, non-regexp. */
 212   size_t match_length1 = match_length - 1; /* Speed optimization, non-regexp. */
 213   struct re_registers regs;
 214
 215   /* Find the size of the input file. */
 216   file_pos = lseek (input_fd, (off_t) 0, SEEK_END);
 217   if (file_pos < 1)
 218     return true;                        /* It's an empty file. */
 219
 220   /* Arrange for the first read to lop off enough to leave the rest of the
 221      file a multiple of `read_size'.  Since `read_size' can change, this may
 222      not always hold during the program run, but since it usually will, leave
 223      it here for i/o efficiency (page/sector boundaries and all that).
 224      Note: the efficiency gain has not been verified. */
 225   saved_record_size = file_pos % read_size;
 226   if (saved_record_size == 0)
 227     saved_record_size = read_size;
 228   file_pos -= saved_record_size;
 229   /* `file_pos' now points to the start of the last (probably partial) block
 230      in the input file. */
 231
 232   if (lseek (input_fd, file_pos, SEEK_SET) < 0)
 233     error (0, errno, _("%s: seek failed"), quote (file));
 234
 235   if (safe_read (input_fd, G_buffer, saved_record_size) != saved_record_size)
 236     {
 237       error (0, errno, "%s", quote (file));
 238       return false;
 239     }
 240
 241   match_start = past_end = G_buffer + saved_record_size;
 242   /* For non-regexp search, move past impossible positions for a match. */
 243   if (sentinel_length)
 244     match_start -= match_length1;
 245
 246   for (;;)
 247     {
 248       /* Search backward from `match_start' - 1 to `G_buffer' for a match
 249          with `separator'; for speed, use strncmp if `separator' contains no
 250          metacharacters.
 251          If the match succeeds, set `match_start' to point to the start of
 252          the match and `match_length' to the length of the match.
 253          Otherwise, make `match_start' < `G_buffer'. */
 254       if (sentinel_length == 0)
 255         {
 256           ptrdiff_t i = match_start - G_buffer;
 257           int ret;
 258
 259           if (! (INT_MIN < i && i <= INT_MAX))
 260             error (EXIT_FAILURE, 0, _("record too large"));
 261
 262           ret = re_search (&compiled_separator, G_buffer, i, i - 1, -i, &regs);
 263           if (ret == -1)
 264             match_start = G_buffer - 1;
 265           else if (ret == -2)
 266             {
 267               error (EXIT_FAILURE, 0,
 268                      _("error in regular expression search"));
 269             }
 270           else
 271             {
 272               match_start = G_buffer + regs.start[0];
 273               match_length = regs.end[0] - regs.start[0];
 274             }
 275         }
 276       else
 277         {
 278           /* `match_length' is constant for non-regexp boundaries. */
 279           while (*--match_start != first_char
 280                  || (match_length1 && strncmp (match_start + 1, separator1,
 281                                                match_length1)))
 282             /* Do nothing. */ ;
 283         }
 284
 285       /* Check whether we backed off the front of `G_buffer' without finding
 286          a match for `separator'. */
 287       if (match_start < G_buffer)
 288         {
 289           if (file_pos == 0)
 290             {
 291               /* Hit the beginning of the file; print the remaining record. */
 292               output (G_buffer, past_end);
 293               return true;
 294             }
 295
 296           saved_record_size = past_end - G_buffer;
 297           if (saved_record_size > read_size)
 298             {
 299               /* `G_buffer_size' is about twice `read_size', so since
 300                  we want to read in another `read_size' bytes before
 301                  the data already in `G_buffer', we need to increase
 302                  `G_buffer_size'. */
 303               char *newbuffer;
 304               size_t offset = sentinel_length ? sentinel_length : 1;
 305               ptrdiff_t match_start_offset = match_start - G_buffer;
 306               ptrdiff_t past_end_offset = past_end - G_buffer;
 307               size_t old_G_buffer_size = G_buffer_size;
 308
 309               read_size *= 2;
 310               G_buffer_size = read_size * 2 + sentinel_length + 2;
 311               if (G_buffer_size < old_G_buffer_size)
 312                 xalloc_die ();
 313               newbuffer = xrealloc (G_buffer - offset, G_buffer_size);
 314               newbuffer += offset;
 315               /* Adjust the pointers for the new buffer location.  */
 316               match_start = newbuffer + match_start_offset;
 317               past_end = newbuffer + past_end_offset;
 318               G_buffer = newbuffer;
 319             }
 320
 321           /* Back up to the start of the next bufferfull of the file.  */
 322           if (file_pos >= read_size)
 323             file_pos -= read_size;
 324           else
 325             {
 326               read_size = file_pos;
 327               file_pos = 0;
 328             }
 329           if (lseek (input_fd, file_pos, SEEK_SET) < 0)
 330             error (0, errno, _("%s: seek failed"), quote (file));
 331
 332           /* Shift the pending record data right to make room for the new.
 333              The source and destination regions probably overlap.  */
 334           memmove (G_buffer + read_size, G_buffer, saved_record_size);
 335           past_end = G_buffer + read_size + saved_record_size;
 336           /* For non-regexp searches, avoid unneccessary scanning. */
 337           if (sentinel_length)
 338             match_start = G_buffer + read_size;
 339           else
 340             match_start = past_end;
 341
 342           if (safe_read (input_fd, G_buffer, read_size) != read_size)
 343             {
 344               error (0, errno, "%s", quote (file));
 345               return false;
 346             }
 347         }
 348       else
 349         {
 350           /* Found a match of `separator'. */
 351           if (separator_ends_record)
 352             {
 353               char *match_end = match_start + match_length;
 354
 355               /* If this match of `separator' isn't at the end of the
 356                  file, print the record. */
 357               if (!first_time || match_end != past_end)
 358                 output (match_end, past_end);
 359               past_end = match_end;
 360               first_time = false;
 361             }
 362           else
 363             {
 364               output (match_start, past_end);
 365               past_end = match_start;
 366             }
 367
 368           /* For non-regex matching, we can back up.  */
 369           if (sentinel_length > 0)
 370             match_start -= match_length - 1;
 371         }
 372     }
 373 }
 374
 375 #if DONT_UNLINK_WHILE_OPEN
 376
 377 static const char *file_to_remove;
 378 static FILE *fp_to_close;
 379
 380 static void
 381 unlink_tempfile (void)
 382 {
 383   fclose (fp_to_close);
 384   unlink (file_to_remove);
 385 }
 386
 387 static void
 388 record_tempfile (const char *fn, FILE *fp)
 389 {
 390   if (!file_to_remove)
 391     {
 392       file_to_remove = fn;
 393       fp_to_close = fp;
 394       atexit (unlink_tempfile);
 395     }
 396 }
 397
 398 #endif
 399
 400 /* Copy from file descriptor INPUT_FD (corresponding to the named FILE) to
 401    a temporary file, and set *G_TMP and *G_TEMPFILE to the resulting stream
 402    and file name.  Exit upon any failure.  */
 403 /* FIXME: don't exit upon failure!!!  */
 404
 405 static void
 406 copy_to_temp (FILE **g_tmp, char **g_tempfile, int input_fd, char const *file)
 407 {
 408   static char *template = NULL;
 409   static char *tempdir;
 410   char *tempfile;
 411   FILE *tmp;
 412   int fd;
 413
 414   if (template == NULL)
 415     {
 416       tempdir = getenv ("TMPDIR");
 417       if (tempdir == NULL)
 418         tempdir = DEFAULT_TMPDIR;
 419       template = xmalloc (strlen (tempdir) + 11);
 420     }
 421   sprintf (template, "%s/tacXXXXXX", tempdir);
 422   tempfile = template;
 423   fd = mkstemp (template);
 424   if (fd == -1)
 425     error (EXIT_FAILURE, errno, "%s", quote (tempfile));
 426
 427   tmp = fdopen (fd, "w+");
 428   if (tmp == NULL)
 429     error (EXIT_FAILURE, errno, "%s", quote (tempfile));
 430
 431 #if DONT_UNLINK_WHILE_OPEN
 432   record_tempfile (tempfile, tmp);
 433 #else
 434   unlink (tempfile);
 435 #endif
 436
 437   while (1)
 438     {
 439       size_t bytes_read = safe_read (input_fd, G_buffer, read_size);
 440       if (bytes_read == 0)
 441         break;
 442       if (bytes_read == SAFE_READ_ERROR)
 443         error (EXIT_FAILURE, errno, _("%s: read error"), quote (file));
 444
 445       if (fwrite (G_buffer, 1, bytes_read, tmp) != bytes_read)
 446         error (EXIT_FAILURE, errno, "%s", quote (tempfile));
 447     }
 448
 449   if (fflush (tmp) != 0)
 450     error (EXIT_FAILURE, errno, "%s", quote (tempfile));
 451
 452   SET_BINARY (fileno (tmp));
 453   *g_tmp = tmp;
 454   *g_tempfile = tempfile;
 455 }
 456
 457 /* Copy INPUT_FD to a temporary, then tac that file.
 458    Return true if successful.  */
 459
 460 static bool
 461 tac_nonseekable (int input_fd, const char *file)
 462 {
 463   FILE *tmp_stream;
 464   char *tmp_file;
 465   copy_to_temp (&tmp_stream, &tmp_file, input_fd, file);
 466   return tac_seekable (fileno (tmp_stream), tmp_file);
 467 }
 468
 469 /* Print FILE in reverse, copying it to a temporary
 470    file first if it is not seekable.
 471    Return true if successful.  */
 472
 473 static bool
 474 tac_file (const char *filename)
 475 {
 476   bool ok;
 477   off_t file_size;
 478   int fd;
 479
 480   if (STREQ (filename, "-"))
 481     {
 482       have_read_stdin = true;
 483       fd = STDIN_FILENO;
 484       filename = _("standard input");
 485     }
 486   else
 487     {
 488       fd = open (filename, O_RDONLY);
 489       if (fd < 0)
 490         {
 491           error (0, errno, _("cannot open %s for reading"), quote (filename));
 492           return false;
 493         }
 494     }
 495
 496   /* We need binary I/O, since `tac' relies
 497      on `lseek' and byte counts.
 498
 499      Binary output will leave the lines' ends (NL or
 500      CR/LF) intact when the output is a disk file.
 501      Writing a file with CR/LF pairs at end of lines in
 502      text mode has no visible effect on console output,
 503      since two CRs in a row are just like one CR.  */
 504   SET_BINARY2 (fd, STDOUT_FILENO);
 505
 506   file_size = lseek (fd, (off_t) 0, SEEK_END);
 507
 508   ok = (0 <= file_size
 509         ? tac_seekable (fd, filename)
 510         : tac_nonseekable (fd, filename));
 511
 512   if (fd != STDIN_FILENO && close (fd) == -1)
 513     {
 514       error (0, errno, _("closing %s"), quote (filename));
 515       ok = false;
 516     }
 517   return ok;
 518 }
 519
 520 #if 0
 521 /* BUF_END points one byte past the end of the buffer to be searched.  */
 522
 523 /* FIXME: describe */
 524
 525 static void
 526 tac_mem (const char *buf, size_t n_bytes, FILE *out)
 527 {
 528   const char *nl;
 529   const char *bol;
 530
 531   if (n_bytes == 0)
 532     return;
 533
 534   nl = memrchr (buf, buf + n_bytes, '\n');
 535   bol = (nl == NULL ? buf : nl + 1);
 536
 537   /* If the last line of the input file has no terminating newline,
 538      treat it as a special case.  */
 539   if (bol < buf + n_bytes)
 540     {
 541       /* Print out the line from bol to end of input.  */
 542       fwrite (bol, 1, (buf + n_bytes) - bol, out);
 543
 544       /* Add a newline here.  Otherwise, the first and second lines
 545          of output would appear to have been joined.  */
 546       fputc ('\n', out);
 547     }
 548
 549   while ((nl = memrchr (buf, bol - 1, '\n')) != NULL)
 550     {
 551       /* Output the line (which includes a trailing newline)
 552          from NL+1 to BOL-1.  */
 553       fwrite (nl + 1, 1, bol - (nl + 1), out);
 554
 555       bol = nl + 1;
 556     }
 557
 558   /* If there's anything left, output the last line: BUF .. BOL-1.
 559      When the first byte of the input is a newline, there is nothing
 560      left to do here.  */
 561   if (buf < bol)
 562     fwrite (buf, 1, bol - buf, out);
 563
 564   /* FIXME: this is work in progress.... */
 565 }
 566
 567 /* FIXME: describe */
 568
 569 static bool
 570 tac_stdin_to_mem (void)
 571 {
 572   char *buf = NULL;
 573   size_t bufsiz = 8 * BUFSIZ;
 574   size_t delta = 8 * BUFSIZ;
 575   size_t n_bytes = 0;
 576
 577   while (1)
 578     {
 579       size_t bytes_read;
 580       char *new_buf = realloc (buf, bufsiz);
 581
 582       if (new_buf == NULL)
 583         {
 584           /* Write contents of buf to a temporary file, ... */
 585           /* FIXME */
 586
 587           /* Free the buffer and fall back on the code that relies on a
 588              temporary file.  */
 589           free (buf);
 590           /* FIXME */
 591           abort ();
 592         }
 593
 594       buf = new_buf;
 595       bytes_read = safe_read (STDIN_FILENO, buf + n_bytes, bufsiz - n_bytes);
 596       if (bytes_read == 0)
 597         break;
 598       if (bytes_read == SAFE_READ_ERROR)
 599         error (EXIT_FAILURE, errno, _("stdin: read error"));
 600       n_bytes += bytes_read;
 601
 602       bufsiz += delta;
 603     }
 604
 605   tac_mem (buf, n_bytes, stdout);
 606
 607   return true;
 608 }
 609 #endif
 610
 611 int
 612 main (int argc, char **argv)
 613 {
 614   const char *error_message;    /* Return value from re_compile_pattern. */
 615   int optc;
 616   bool ok;
 617   size_t half_buffer_size;
 618
 619   /* Initializer for file_list if no file-arguments
 620      were specified on the command line.  */
 621   static char const *const default_file_list[] = {"-", NULL};
 622   char const *const *file;
 623
 624   initialize_main (&argc, &argv);
 625   program_name = argv[0];
 626   setlocale (LC_ALL, "");
 627   bindtextdomain (PACKAGE, LOCALEDIR);
 628   textdomain (PACKAGE);
 629
 630   atexit (close_stdout);
 631
 632   separator = "\n";
 633   sentinel_length = 1;
 634   separator_ends_record = true;
 635
 636   while ((optc = getopt_long (argc, argv, "brs:", longopts, NULL)) != -1)
 637     {
 638       switch (optc)
 639         {
 640         case 'b':
 641           separator_ends_record = false;
 642           break;
 643         case 'r':
 644           sentinel_length = 0;
 645           break;
 646         case 's':
 647           separator = optarg;
 648           if (*separator == 0)
 649             error (EXIT_FAILURE, 0, _("separator cannot be empty"));
 650           break;
 651         case_GETOPT_HELP_CHAR;
 652         case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
 653         default:
 654           usage (EXIT_FAILURE);
 655         }
 656     }
 657
 658   if (sentinel_length == 0)
 659     {
 660       compiled_separator.allocated = 100;
 661       compiled_separator.buffer = xmalloc (compiled_separator.allocated);
 662       compiled_separator.fastmap = xmalloc (256);
 663       compiled_separator.translate = 0;
 664       error_message = re_compile_pattern (separator, strlen (separator),
 665                                           &compiled_separator);
 666       if (error_message)
 667         error (EXIT_FAILURE, 0, "%s", error_message);
 668     }
 669   else
 670     match_length = sentinel_length = strlen (separator);
 671
 672   read_size = INITIAL_READSIZE;
 673   while (sentinel_length >= read_size / 2)
 674     {
 675       if (SIZE_MAX / 2 < read_size)
 676         xalloc_die ();
 677       read_size *= 2;
 678     }
 679   half_buffer_size = read_size + sentinel_length + 1;
 680   G_buffer_size = 2 * half_buffer_size;
 681   if (! (read_size < half_buffer_size && half_buffer_size < G_buffer_size))
 682     xalloc_die ();
 683   G_buffer = xmalloc (G_buffer_size);
 684   if (sentinel_length)
 685     {
 686       strcpy (G_buffer, separator);
 687       G_buffer += sentinel_length;
 688     }
 689   else
 690     {
 691       ++G_buffer;
 692     }
 693
 694   file = (optind < argc
 695           ? (char const *const *) &argv[optind]
 696           : default_file_list);
 697
 698   {
 699     size_t i;
 700     ok = true;
 701     for (i = 0; file[i]; ++i)
 702       ok &= tac_file (file[i]);
 703   }
 704
 705   /* Flush the output buffer. */
 706   output ((char *) NULL, (char *) NULL);
 707
 708   if (have_read_stdin && close (STDIN_FILENO) < 0)
 709     error (EXIT_FAILURE, errno, "-");
 710   exit (ok ? EXIT_SUCCESS : EXIT_FAILURE);
 711 }