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