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 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       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 int bytes_in_buffer = 0;
 159   int bytes_to_add = past_end - start;
 160   int 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   ssize_t bytes_read;
 423   int fd;
 424
 425   if (template == NULL)
 426     {
 427       tempdir = getenv ("TMPDIR");
 428       if (tempdir == NULL)
 429         tempdir = DEFAULT_TMPDIR;
 430       template = xmalloc (strlen (tempdir) + 11);
 431     }
 432   sprintf (template, "%s/tacXXXXXX", tempdir);
 433   tempfile = template;
 434   fd = mkstemp (template);
 435   if (fd == -1)
 436     error (EXIT_FAILURE, errno, "%s", tempfile);
 437
 438   tmp = fdopen (fd, "w+");
 439   if (tmp == NULL)
 440     error (EXIT_FAILURE, errno, "%s", tempfile);
 441
 442 #if DONT_UNLINK_WHILE_OPEN
 443   record_tempfile (tempfile, tmp);
 444 #else
 445   unlink (tempfile);
 446 #endif
 447
 448   while (1)
 449     {
 450       bytes_read = safe_read (STDIN_FILENO, G_buffer, read_size);
 451       if (bytes_read == 0)
 452         break;
 453       if (bytes_read < 0)
 454         error (EXIT_FAILURE, errno, _("stdin: read error"));
 455
 456       if (fwrite (G_buffer, 1, bytes_read, tmp) != bytes_read)
 457         break;
 458     }
 459
 460   if (ferror (tmp) || fflush (tmp) == EOF)
 461     error (EXIT_FAILURE, errno, "%s", tempfile);
 462
 463   SET_BINARY (fileno (tmp));
 464   *g_tmp = tmp;
 465   *g_tempfile = tempfile;
 466 }
 467
 468 /* Print the standard input in reverse, saving it to temporary
 469    file first if it is a pipe.
 470    Return 0 if ok, 1 if an error occurs. */
 471
 472 static int
 473 tac_stdin (void)
 474 {
 475   int errors;
 476   struct stat stats;
 477
 478   /* No tempfile is needed for "tac < file".
 479      Use fstat instead of checking for errno == ESPIPE because
 480      lseek doesn't work on some special files but doesn't return an
 481      error, either. */
 482   if (fstat (STDIN_FILENO, &stats))
 483     {
 484       error (0, errno, _("standard input"));
 485       return 1;
 486     }
 487
 488   if (S_ISREG (stats.st_mode))
 489     {
 490       errors = tac_seekable (fileno (stdin), _("standard input"));
 491     }
 492   else
 493     {
 494       FILE *tmp_stream;
 495       char *tmp_file;
 496       save_stdin (&tmp_stream, &tmp_file);
 497       errors = tac_seekable (fileno (tmp_stream), tmp_file);
 498     }
 499
 500   return errors;
 501 }
 502
 503 #if 0
 504 /* BUF_END points one byte past the end of the buffer to be searched.  */
 505
 506 static void *
 507 memrchr (const char *buf_start, const char *buf_end, int c)
 508 {
 509   const char *p = buf_end;
 510   while (buf_start <= --p)
 511     {
 512       if (*(const unsigned char *) p == c)
 513         return (void *) p;
 514     }
 515   return NULL;
 516 }
 517
 518 /* FIXME: describe */
 519
 520 static int
 521 tac_mem (const char *buf, size_t n_bytes, FILE *out)
 522 {
 523   const char *nl;
 524   const char *bol;
 525
 526   if (n_bytes == 0)
 527     return 0;
 528
 529   nl = memrchr (buf, buf + n_bytes, '\n');
 530   bol = (nl == NULL ? buf : nl + 1);
 531
 532   /* If the last line of the input file has no terminating newline,
 533      treat it as a special case.  */
 534   if (bol < buf + n_bytes)
 535     {
 536       /* Print out the line from bol to end of input.  */
 537       fwrite (bol, 1, (buf + n_bytes) - bol, out);
 538
 539       /* Add a newline here.  Otherwise, the first and second lines
 540          of output would appear to have been joined.  */
 541       fputc ('\n', out);
 542     }
 543
 544   while ((nl = memrchr (buf, bol - 1, '\n')) != NULL)
 545     {
 546       /* Output the line (which includes a trailing newline)
 547          from NL+1 to BOL-1.  */
 548       fwrite (nl + 1, 1, bol - (nl + 1), out);
 549
 550       bol = nl + 1;
 551     }
 552
 553   /* If there's anything left, output the last line: BUF .. BOL-1.
 554      When the first byte of the input is a newline, there is nothing
 555      left to do here.  */
 556   if (buf < bol)
 557     fwrite (buf, 1, bol - buf, out);
 558
 559   /* FIXME: this is work in progress.... */
 560   return ferror (out);
 561 }
 562
 563 /* FIXME: describe */
 564
 565 static int
 566 tac_stdin_to_mem (void)
 567 {
 568   char *buf = NULL;
 569   size_t bufsiz = 8 * BUFSIZ;
 570   size_t delta = 8 * BUFSIZ;
 571   size_t n_bytes = 0;
 572
 573   while (1)
 574     {
 575       ssize_t bytes_read;
 576       if (buf == NULL)
 577         buf = (char *) malloc (bufsiz);
 578       else
 579         buf = (char *) realloc (buf, bufsiz);
 580
 581       if (buf == NULL)
 582         {
 583           /* Free the buffer and fall back on the code that relies on a
 584              temporary file.  */
 585           free (buf);
 586           /* FIXME */
 587           abort ();
 588         }
 589       bytes_read = safe_read (STDIN_FILENO, buf + n_bytes, bufsiz - n_bytes);
 590       if (bytes_read == 0)
 591         break;
 592       if (bytes_read < 0)
 593         error (EXIT_FAILURE, errno, _("stdin: read error"));
 594       n_bytes += bytes_read;
 595
 596       bufsiz += delta;
 597     }
 598
 599   tac_mem (buf, n_bytes, stdout);
 600
 601   return 0;
 602 }
 603 #endif
 604
 605 int
 606 main (int argc, char **argv)
 607 {
 608   const char *error_message;    /* Return value from re_compile_pattern. */
 609   int optc, errors;
 610   int have_read_stdin = 0;
 611
 612   program_name = argv[0];
 613   setlocale (LC_ALL, "");
 614   bindtextdomain (PACKAGE, LOCALEDIR);
 615   textdomain (PACKAGE);
 616
 617   atexit (close_stdout);
 618
 619   errors = 0;
 620   separator = "\n";
 621   sentinel_length = 1;
 622   separator_ends_record = 1;
 623
 624   while ((optc = getopt_long (argc, argv, "brs:", longopts, NULL)) != -1)
 625     {
 626       switch (optc)
 627         {
 628         case 0:
 629           break;
 630         case 'b':
 631           separator_ends_record = 0;
 632           break;
 633         case 'r':
 634           sentinel_length = 0;
 635           break;
 636         case 's':
 637           separator = optarg;
 638           if (*separator == 0)
 639             error (EXIT_FAILURE, 0, _("separator cannot be empty"));
 640           break;
 641         case_GETOPT_HELP_CHAR;
 642         case_GETOPT_VERSION_CHAR (PROGRAM_NAME, AUTHORS);
 643         default:
 644           usage (1);
 645         }
 646     }
 647
 648   if (sentinel_length == 0)
 649     {
 650       compiled_separator.allocated = 100;
 651       compiled_separator.buffer = (unsigned char *)
 652         xmalloc (compiled_separator.allocated);
 653       compiled_separator.fastmap = xmalloc (256);
 654       compiled_separator.translate = 0;
 655       error_message = re_compile_pattern (separator, strlen (separator),
 656                                           &compiled_separator);
 657       if (error_message)
 658         error (EXIT_FAILURE, 0, "%s", error_message);
 659     }
 660   else
 661     match_length = sentinel_length = strlen (separator);
 662
 663   read_size = INITIAL_READSIZE;
 664   /* A precaution that will probably never be needed. */
 665   while (sentinel_length * 2 >= read_size)
 666     read_size *= 2;
 667   G_buffer_size = read_size * 2 + sentinel_length + 2;
 668   G_buffer = xmalloc (G_buffer_size);
 669   if (sentinel_length)
 670     {
 671       strcpy (G_buffer, separator);
 672       G_buffer += sentinel_length;
 673     }
 674   else
 675     {
 676       ++G_buffer;
 677     }
 678
 679   if (optind == argc)
 680     {
 681       have_read_stdin = 1;
 682       /* We need binary I/O, since `tac' relies
 683          on `lseek' and byte counts.  */
 684       SET_BINARY2 (STDIN_FILENO, STDOUT_FILENO);
 685       errors = tac_stdin ();
 686     }
 687   else
 688     {
 689       for (; optind < argc; ++optind)
 690         {
 691           if (STREQ (argv[optind], "-"))
 692             {
 693               have_read_stdin = 1;
 694               SET_BINARY2 (STDIN_FILENO, STDOUT_FILENO);
 695               errors |= tac_stdin ();
 696             }
 697           else
 698             {
 699               /* Binary output will leave the lines' ends (NL or
 700                  CR/LF) intact when the output is a disk file.
 701                  Writing a file with CR/LF pairs at end of lines in
 702                  text mode has no visible effect on console output,
 703                  since two CRs in a row are just like one CR.  */
 704               SET_BINARY (STDOUT_FILENO);
 705               errors |= tac_file (argv[optind]);
 706             }
 707         }
 708     }
 709
 710   /* Flush the output buffer. */
 711   output ((char *) NULL, (char *) NULL);
 712
 713   if (have_read_stdin && close (0) < 0)
 714     error (EXIT_FAILURE, errno, "-");
 715   exit (errors == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
 716 }