src/tac.c

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