src/tac.c

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