src/tac.c

   1 /* tac - concatenate and print files in reverse
   2    Copyright (C) 1988-1991, 1995-1999 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 "long-options.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 #if defined __MSDOS__ || defined _WIN32
  55 /* Define this to non-zero on systems for which the regular mechanism
  56    (of unlinking an open file and expecting to be able to write, seek
  57    back to the beginning, then reread it) doesn't work.  E.g., on Windows
  58    and DOS systems.  */
  59 # define DONT_UNLINK_WHILE_OPEN 1
  60 #endif
  61
  62
  63 #ifndef DEFAULT_TMPDIR
  64 # define DEFAULT_TMPDIR "/tmp"
  65 #endif
  66
  67 /* The number of bytes per atomic read. */
  68 #define INITIAL_READSIZE 8192
  69
  70 /* The number of bytes per atomic write. */
  71 #define WRITESIZE 8192
  72
  73 char *mktemp ();
  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   {NULL, 0, NULL, 0}
 115 };
 116
 117 void
 118 usage (int status)
 119 {
 120   if (status != 0)
 121     fprintf (stderr, _("Try `%s --help' for more information.\n"),
 122              program_name);
 123   else
 124     {
 125       printf (_("\
 126 Usage: %s [OPTION]... [FILE]...\n\
 127 "),
 128               program_name);
 129       printf (_("\
 130 Write each FILE to standard output, last line first.\n\
 131 With no FILE, or when FILE is -, read standard input.\n\
 132 \n\
 133   -b, --before             attach the separator before instead of after\n\
 134   -r, --regex              interpret the separator as a regular expression\n\
 135   -s, --separator=STRING   use STRING as the separator instead of newline\n\
 136       --help               display this help and exit\n\
 137       --version            output version information and exit\n\
 138 "));
 139       puts (_("\nReport bugs to <bug-textutils@gnu.org>."));
 140     }
 141   exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
 142 }
 143
 144 /* Print the characters from START to PAST_END - 1.
 145    If START is NULL, just flush the buffer. */
 146
 147 static void
 148 output (const char *start, const char *past_end)
 149 {
 150   static char buffer[WRITESIZE];
 151   static int bytes_in_buffer = 0;
 152   int bytes_to_add = past_end - start;
 153   int bytes_available = WRITESIZE - bytes_in_buffer;
 154
 155   if (start == 0)
 156     {
 157       fwrite (buffer, 1, bytes_in_buffer, stdout);
 158       bytes_in_buffer = 0;
 159       return;
 160     }
 161
 162   /* Write out as many full buffers as possible. */
 163   while (bytes_to_add >= bytes_available)
 164     {
 165       memcpy (buffer + bytes_in_buffer, start, bytes_available);
 166       bytes_to_add -= bytes_available;
 167       start += bytes_available;
 168       fwrite (buffer, 1, WRITESIZE, stdout);
 169       bytes_in_buffer = 0;
 170       bytes_available = WRITESIZE;
 171     }
 172
 173   memcpy (buffer + bytes_in_buffer, start, bytes_to_add);
 174   bytes_in_buffer += bytes_to_add;
 175 }
 176
 177 /* Print in reverse the file open on descriptor FD for reading FILE.
 178    Return 0 if ok, 1 if an error occurs. */
 179
 180 static int
 181 tac_seekable (int input_fd, const char *file)
 182 {
 183   /* Pointer to the location in `G_buffer' where the search for
 184      the next separator will begin. */
 185   char *match_start;
 186
 187   /* Pointer to one past the rightmost character in `G_buffer' that
 188      has not been printed yet. */
 189   char *past_end;
 190
 191   /* Length of the record growing in `G_buffer'. */
 192   size_t saved_record_size;
 193
 194   /* Offset in the file of the next read. */
 195   off_t file_pos;
 196
 197   /* Nonzero if `output' has not been called yet for any file.
 198      Only used when the separator is attached to the preceding record. */
 199   int first_time = 1;
 200   char first_char = *separator; /* Speed optimization, non-regexp. */
 201   char *separator1 = separator + 1; /* Speed optimization, non-regexp. */
 202   int match_length1 = match_length - 1; /* Speed optimization, non-regexp. */
 203   struct re_registers regs;
 204
 205   /* Find the size of the input file. */
 206   file_pos = lseek (input_fd, (off_t) 0, SEEK_END);
 207   if (file_pos < 1)
 208     return 0;                   /* It's an empty file. */
 209
 210   /* Arrange for the first read to lop off enough to leave the rest of the
 211      file a multiple of `read_size'.  Since `read_size' can change, this may
 212      not always hold during the program run, but since it usually will, leave
 213      it here for i/o efficiency (page/sector boundaries and all that).
 214      Note: the efficiency gain has not been verified. */
 215   saved_record_size = file_pos % read_size;
 216   if (saved_record_size == 0)
 217     saved_record_size = read_size;
 218   file_pos -= saved_record_size;
 219   /* `file_pos' now points to the start of the last (probably partial) block
 220      in the input file. */
 221
 222   if (lseek (input_fd, file_pos, SEEK_SET) < 0)
 223     error (0, errno, "%s: seek failed", file);
 224
 225   if (safe_read (input_fd, G_buffer, saved_record_size) != saved_record_size)
 226     {
 227       error (0, errno, "%s", file);
 228       return 1;
 229     }
 230
 231   match_start = past_end = G_buffer + saved_record_size;
 232   /* For non-regexp search, move past impossible positions for a match. */
 233   if (sentinel_length)
 234     match_start -= match_length1;
 235
 236   for (;;)
 237     {
 238       /* Search backward from `match_start' - 1 to `G_buffer' for a match
 239          with `separator'; for speed, use strncmp if `separator' contains no
 240          metacharacters.
 241          If the match succeeds, set `match_start' to point to the start of
 242          the match and `match_length' to the length of the match.
 243          Otherwise, make `match_start' < `G_buffer'. */
 244       if (sentinel_length == 0)
 245         {
 246           int i = match_start - G_buffer;
 247           int ret;
 248
 249           ret = re_search (&compiled_separator, G_buffer, i, i - 1, -i, &regs);
 250           if (ret == -1)
 251             match_start = G_buffer - 1;
 252           else if (ret == -2)
 253             {
 254               error (EXIT_FAILURE, 0,
 255                      _("error in regular expression search"));
 256             }
 257           else
 258             {
 259               match_start = G_buffer + regs.start[0];
 260               match_length = regs.end[0] - regs.start[0];
 261             }
 262         }
 263       else
 264         {
 265           /* `match_length' is constant for non-regexp boundaries. */
 266           while (*--match_start != first_char
 267                  || (match_length1 && strncmp (match_start + 1, separator1,
 268                                                match_length1)))
 269             /* Do nothing. */ ;
 270         }
 271
 272       /* Check whether we backed off the front of `G_buffer' without finding
 273          a match for `separator'. */
 274       if (match_start < G_buffer)
 275         {
 276           if (file_pos == 0)
 277             {
 278               /* Hit the beginning of the file; print the remaining record. */
 279               output (G_buffer, past_end);
 280               return 0;
 281             }
 282
 283           saved_record_size = past_end - G_buffer;
 284           if (saved_record_size > read_size)
 285             {
 286               /* `G_buffer_size' is about twice `read_size', so since
 287                  we want to read in another `read_size' bytes before
 288                  the data already in `G_buffer', we need to increase
 289                  `G_buffer_size'. */
 290               char *newbuffer;
 291               int offset = sentinel_length ? sentinel_length : 1;
 292
 293               read_size *= 2;
 294               G_buffer_size = read_size * 2 + sentinel_length + 2;
 295               newbuffer = xrealloc (G_buffer - offset, G_buffer_size);
 296               newbuffer += offset;
 297               /* Adjust the pointers for the new buffer location.  */
 298               match_start += newbuffer - G_buffer;
 299               past_end += newbuffer - G_buffer;
 300               G_buffer = newbuffer;
 301             }
 302
 303           /* Back up to the start of the next bufferfull of the file.  */
 304           if (file_pos >= read_size)
 305             file_pos -= read_size;
 306           else
 307             {
 308               read_size = file_pos;
 309               file_pos = 0;
 310             }
 311           lseek (input_fd, file_pos, SEEK_SET);
 312
 313           /* Shift the pending record data right to make room for the new.
 314              The source and destination regions probably overlap.  */
 315           memmove (G_buffer + read_size, G_buffer, saved_record_size);
 316           past_end = G_buffer + read_size + saved_record_size;
 317           /* For non-regexp searches, avoid unneccessary scanning. */
 318           if (sentinel_length)
 319             match_start = G_buffer + read_size;
 320           else
 321             match_start = past_end;
 322
 323           if (safe_read (input_fd, G_buffer, read_size) != read_size)
 324             {
 325               error (0, errno, "%s", file);
 326               return 1;
 327             }
 328         }
 329       else
 330         {
 331           /* Found a match of `separator'. */
 332           if (separator_ends_record)
 333             {
 334               char *match_end = match_start + match_length;
 335
 336               /* If this match of `separator' isn't at the end of the
 337                  file, print the record. */
 338               if (first_time == 0 || match_end != past_end)
 339                 output (match_end, past_end);
 340               past_end = match_end;
 341               first_time = 0;
 342             }
 343           else
 344             {
 345               output (match_start, past_end);
 346               past_end = match_start;
 347             }
 348
 349           /* For non-regex matching, we can back up.  */
 350           if (sentinel_length > 0)
 351             match_start -= match_length - 1;
 352         }
 353     }
 354 }
 355
 356 /* Print FILE in reverse.
 357    Return 0 if ok, 1 if an error occurs. */
 358
 359 static int
 360 tac_file (const char *file)
 361 {
 362   int errors;
 363   FILE *in;
 364
 365   in = fopen (file, "r");
 366   if (in == NULL)
 367     {
 368       error (0, errno, "%s", file);
 369       return 1;
 370     }
 371   SET_BINARY (fileno (in));
 372   errors = tac_seekable (fileno (in), file);
 373   if (ferror (in) || fclose (in) == EOF)
 374     {
 375       error (0, errno, "%s", file);
 376       return 1;
 377     }
 378   return errors;
 379 }
 380
 381 #if DONT_UNLINK_WHILE_OPEN
 382
 383 static const char *file_to_remove;
 384 static FILE *fp_to_close;
 385
 386 static void
 387 unlink_tempfile (void)
 388 {
 389   fclose (fp_to_close);
 390   unlink (file_to_remove);
 391 }
 392
 393 static void
 394 record_tempfile (const char *fn, FILE *fp)
 395 {
 396   if (!file_to_remove)
 397     {
 398       file_to_remove = fn;
 399       fp_to_close = fp;
 400       atexit (unlink_tempfile);
 401     }
 402 }
 403
 404 #endif
 405
 406 /* Make a copy of the standard input in `FIXME'. */
 407
 408 static void
 409 save_stdin (FILE **g_tmp, char **g_tempfile)
 410 {
 411   static char *template = NULL;
 412   static char *tempdir;
 413   static char *tempfile;
 414   FILE *tmp;
 415   ssize_t bytes_read;
 416   int fd;
 417
 418   if (template == NULL)
 419     {
 420       tempdir = getenv ("TMPDIR");
 421       if (tempdir == NULL)
 422         tempdir = DEFAULT_TMPDIR;
 423       template = xmalloc (strlen (tempdir) + 11);
 424     }
 425   sprintf (template, "%s/tacXXXXXX", tempdir);
 426   tempfile = mktemp (template);
 427
 428   /*  Open temporary file exclusively, to foil a common
 429       denial-of-service attack.  */
 430   fd = open (tempfile, O_RDWR | O_CREAT | O_TRUNC | O_EXCL, 0600);
 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 /* BUF_END points one byte past the end of the buffer to be searched.  */
 502
 503 static void *
 504 memrchr (const char *buf_start, const char *buf_end, int c)
 505 {
 506   const char *p = buf_end;
 507   while (buf_start <= --p)
 508     {
 509       if (*(const unsigned char *) p == c)
 510         return (void *) p;
 511     }
 512   return NULL;
 513 }
 514
 515 #if 0
 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   parse_long_options (argc, argv, PROGRAM_NAME, GNU_PACKAGE, VERSION,
 616                       "Jay Lepreau and David MacKenzie", usage);
 617
 618   errors = 0;
 619   separator = "\n";
 620   sentinel_length = 1;
 621   separator_ends_record = 1;
 622
 623   while ((optc = getopt_long (argc, argv, "brs:", longopts, NULL)) != -1)
 624     {
 625       switch (optc)
 626         {
 627         case 0:
 628           break;
 629         case 'b':
 630           separator_ends_record = 0;
 631           break;
 632         case 'r':
 633           sentinel_length = 0;
 634           break;
 635         case 's':
 636           separator = optarg;
 637           if (*separator == 0)
 638             error (EXIT_FAILURE, 0, _("separator cannot be empty"));
 639           break;
 640         default:
 641           usage (1);
 642         }
 643     }
 644
 645   if (sentinel_length == 0)
 646     {
 647       compiled_separator.allocated = 100;
 648       compiled_separator.buffer = (unsigned char *)
 649         xmalloc (compiled_separator.allocated);
 650       compiled_separator.fastmap = xmalloc (256);
 651       compiled_separator.translate = 0;
 652       error_message = re_compile_pattern (separator, strlen (separator),
 653                                           &compiled_separator);
 654       if (error_message)
 655         error (EXIT_FAILURE, 0, "%s", error_message);
 656     }
 657   else
 658     match_length = sentinel_length = strlen (separator);
 659
 660   read_size = INITIAL_READSIZE;
 661   /* A precaution that will probably never be needed. */
 662   while (sentinel_length * 2 >= read_size)
 663     read_size *= 2;
 664   G_buffer_size = read_size * 2 + sentinel_length + 2;
 665   G_buffer = xmalloc (G_buffer_size);
 666   if (sentinel_length)
 667     {
 668       strcpy (G_buffer, separator);
 669       G_buffer += sentinel_length;
 670     }
 671   else
 672     {
 673       ++G_buffer;
 674     }
 675
 676   if (optind == argc)
 677     {
 678       have_read_stdin = 1;
 679       /* We need binary I/O, since `tac' relies
 680          on `lseek' and byte counts.  */
 681       SET_BINARY2 (STDIN_FILENO, STDOUT_FILENO);
 682       errors = tac_stdin ();
 683     }
 684   else
 685     {
 686       for (; optind < argc; ++optind)
 687         {
 688           if (STREQ (argv[optind], "-"))
 689             {
 690               have_read_stdin = 1;
 691               SET_BINARY2 (STDIN_FILENO, STDOUT_FILENO);
 692               errors |= tac_stdin ();
 693             }
 694           else
 695             {
 696               /* Binary output will leave the lines' ends (NL or
 697                  CR/LF) intact when the output is a disk file.
 698                  Writing a file with CR/LF pairs at end of lines in
 699                  text mode has no visible effect on console output,
 700                  since two CRs in a row are just like one CR.  */
 701               SET_BINARY (STDOUT_FILENO);
 702               errors |= tac_file (argv[optind]);
 703             }
 704         }
 705     }
 706
 707   /* Flush the output buffer. */
 708   output ((char *) NULL, (char *) NULL);
 709
 710   if (have_read_stdin && close (0) < 0)
 711     error (EXIT_FAILURE, errno, "-");
 712   if (ferror (stdout) || fclose (stdout) == EOF)
 713     error (EXIT_FAILURE, errno, _("write error"));
 714   exit (errors == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
 715 }