src/tac.c

   1 /* tac - concatenate and print files in reverse
   2    Copyright (C) 1988-1991, 1995-2000 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 "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 char *mktemp ();
  76
  77 /* The name this program was run with. */
  78 char *program_name;
  79
  80 /* The string that separates the records of the file. */
  81 static char *separator;
  82
  83 /* If nonzero, print `separator' along with the record preceding it
  84    in the file; otherwise with the record following it. */
  85 static int separator_ends_record;
  86
  87 /* 0 if `separator' is to be matched as a regular expression;
  88    otherwise, the length of `separator', used as a sentinel to
  89    stop the search. */
  90 static int sentinel_length;
  91
  92 /* The length of a match with `separator'.  If `sentinel_length' is 0,
  93    `match_length' is computed every time a match succeeds;
  94    otherwise, it is simply the length of `separator'. */
  95 static int match_length;
  96
  97 /* The input buffer. */
  98 static char *G_buffer;
  99
 100 /* The number of bytes to read at once into `buffer'. */
 101 static size_t read_size;
 102
 103 /* The size of `buffer'.  This is read_size * 2 + sentinel_length + 2.
 104    The extra 2 bytes allow `past_end' to have a value beyond the
 105    end of `G_buffer' and `match_start' to run off the front of `G_buffer'. */
 106 static unsigned G_buffer_size;
 107
 108 /* The compiled regular expression representing `separator'. */
 109 static struct re_pattern_buffer compiled_separator;
 110
 111 static struct option const longopts[] =
 112 {
 113   {"before", no_argument, NULL, 'b'},
 114   {"regex", no_argument, NULL, 'r'},
 115   {"separator", required_argument, NULL, 's'},
 116   {GETOPT_HELP_OPTION_DECL},
 117   {GETOPT_VERSION_OPTION_DECL},
 118   {NULL, 0, NULL, 0}
 119 };
 120
 121 void
 122 usage (int status)
 123 {
 124   if (status != 0)
 125     fprintf (stderr, _("Try `%s --help' for more information.\n"),
 126              program_name);
 127   else
 128     {
 129       printf (_("\
 130 Usage: %s [OPTION]... [FILE]...\n\
 131 "),
 132               program_name);
 133       printf (_("\
 134 Write each FILE to standard output, last line first.\n\
 135 With no FILE, or when FILE is -, read standard input.\n\
 136 \n\
 137   -b, --before             attach the separator before instead of after\n\
 138   -r, --regex              interpret the separator as a regular expression\n\
 139   -s, --separator=STRING   use STRING as the separator instead of newline\n\
 140       --help               display this help and exit\n\
 141       --version            output version information and exit\n\
 142 "));
 143       puts (_("\nReport bugs to <bug-textutils@gnu.org>."));
 144     }
 145   exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
 146 }
 147
 148 /* Print the characters from START to PAST_END - 1.
 149    If START is NULL, just flush the buffer. */
 150
 151 static void
 152 output (const char *start, const char *past_end)
 153 {
 154   static char buffer[WRITESIZE];
 155   static int bytes_in_buffer = 0;
 156   int bytes_to_add = past_end - start;
 157   int bytes_available = WRITESIZE - bytes_in_buffer;
 158
 159   if (start == 0)
 160     {
 161       fwrite (buffer, 1, bytes_in_buffer, stdout);
 162       bytes_in_buffer = 0;
 163       return;
 164     }
 165
 166   /* Write out as many full buffers as possible. */
 167   while (bytes_to_add >= bytes_available)
 168     {
 169       memcpy (buffer + bytes_in_buffer, start, bytes_available);
 170       bytes_to_add -= bytes_available;
 171       start += bytes_available;
 172       fwrite (buffer, 1, WRITESIZE, stdout);
 173       bytes_in_buffer = 0;
 174       bytes_available = WRITESIZE;
 175     }
 176
 177   memcpy (buffer + bytes_in_buffer, start, bytes_to_add);
 178   bytes_in_buffer += bytes_to_add;
 179 }
 180
 181 /* Print in reverse the file open on descriptor FD for reading FILE.
 182    Return 0 if ok, 1 if an error occurs. */
 183
 184 static int
 185 tac_seekable (int input_fd, const char *file)
 186 {
 187   /* Pointer to the location in `G_buffer' where the search for
 188      the next separator will begin. */
 189   char *match_start;
 190
 191   /* Pointer to one past the rightmost character in `G_buffer' that
 192      has not been printed yet. */
 193   char *past_end;
 194
 195   /* Length of the record growing in `G_buffer'. */
 196   size_t saved_record_size;
 197
 198   /* Offset in the file of the next read. */
 199   off_t file_pos;
 200
 201   /* Nonzero if `output' has not been called yet for any file.
 202      Only used when the separator is attached to the preceding record. */
 203   int first_time = 1;
 204   char first_char = *separator; /* Speed optimization, non-regexp. */
 205   char *separator1 = separator + 1; /* Speed optimization, non-regexp. */
 206   int match_length1 = match_length - 1; /* Speed optimization, non-regexp. */
 207   struct re_registers regs;
 208
 209   /* Find the size of the input file. */
 210   file_pos = lseek (input_fd, (off_t) 0, SEEK_END);
 211   if (file_pos < 1)
 212     return 0;                   /* It's an empty file. */
 213
 214   /* Arrange for the first read to lop off enough to leave the rest of the
 215      file a multiple of `read_size'.  Since `read_size' can change, this may
 216      not always hold during the program run, but since it usually will, leave
 217      it here for i/o efficiency (page/sector boundaries and all that).
 218      Note: the efficiency gain has not been verified. */
 219   saved_record_size = file_pos % read_size;
 220   if (saved_record_size == 0)
 221     saved_record_size = read_size;
 222   file_pos -= saved_record_size;
 223   /* `file_pos' now points to the start of the last (probably partial) block
 224      in the input file. */
 225
 226   if (lseek (input_fd, file_pos, SEEK_SET) < 0)
 227     error (0, errno, "%s: seek failed", file);
 228
 229   if (safe_read (input_fd, G_buffer, saved_record_size) != saved_record_size)
 230     {
 231       error (0, errno, "%s", file);
 232       return 1;
 233     }
 234
 235   match_start = past_end = G_buffer + saved_record_size;
 236   /* For non-regexp search, move past impossible positions for a match. */
 237   if (sentinel_length)
 238     match_start -= match_length1;
 239
 240   for (;;)
 241     {
 242       /* Search backward from `match_start' - 1 to `G_buffer' for a match
 243          with `separator'; for speed, use strncmp if `separator' contains no
 244          metacharacters.
 245          If the match succeeds, set `match_start' to point to the start of
 246          the match and `match_length' to the length of the match.
 247          Otherwise, make `match_start' < `G_buffer'. */
 248       if (sentinel_length == 0)
 249         {
 250           int i = match_start - G_buffer;
 251           int ret;
 252
 253           ret = re_search (&compiled_separator, G_buffer, i, i - 1, -i, &regs);
 254           if (ret == -1)
 255             match_start = G_buffer - 1;
 256           else if (ret == -2)
 257             {
 258               error (EXIT_FAILURE, 0,
 259                      _("error in regular expression search"));
 260             }
 261           else
 262             {
 263               match_start = G_buffer + regs.start[0];
 264               match_length = regs.end[0] - regs.start[0];
 265             }
 266         }
 267       else
 268         {
 269           /* `match_length' is constant for non-regexp boundaries. */
 270           while (*--match_start != first_char
 271                  || (match_length1 && strncmp (match_start + 1, separator1,
 272                                                match_length1)))
 273             /* Do nothing. */ ;
 274         }
 275
 276       /* Check whether we backed off the front of `G_buffer' without finding
 277          a match for `separator'. */
 278       if (match_start < G_buffer)
 279         {
 280           if (file_pos == 0)
 281             {
 282               /* Hit the beginning of the file; print the remaining record. */
 283               output (G_buffer, past_end);
 284               return 0;
 285             }
 286
 287           saved_record_size = past_end - G_buffer;
 288           if (saved_record_size > read_size)
 289             {
 290               /* `G_buffer_size' is about twice `read_size', so since
 291                  we want to read in another `read_size' bytes before
 292                  the data already in `G_buffer', we need to increase
 293                  `G_buffer_size'. */
 294               char *newbuffer;
 295               int offset = sentinel_length ? sentinel_length : 1;
 296
 297               read_size *= 2;
 298               G_buffer_size = read_size * 2 + sentinel_length + 2;
 299               newbuffer = xrealloc (G_buffer - offset, G_buffer_size);
 300               newbuffer += offset;
 301               /* Adjust the pointers for the new buffer location.  */
 302               match_start += newbuffer - G_buffer;
 303               past_end += newbuffer - G_buffer;
 304               G_buffer = newbuffer;
 305             }
 306
 307           /* Back up to the start of the next bufferfull of the file.  */
 308           if (file_pos >= read_size)
 309             file_pos -= read_size;
 310           else
 311             {
 312               read_size = file_pos;
 313               file_pos = 0;
 314             }
 315           lseek (input_fd, file_pos, SEEK_SET);
 316
 317           /* Shift the pending record data right to make room for the new.
 318              The source and destination regions probably overlap.  */
 319           memmove (G_buffer + read_size, G_buffer, saved_record_size);
 320           past_end = G_buffer + read_size + saved_record_size;
 321           /* For non-regexp searches, avoid unneccessary scanning. */
 322           if (sentinel_length)
 323             match_start = G_buffer + read_size;
 324           else
 325             match_start = past_end;
 326
 327           if (safe_read (input_fd, G_buffer, read_size) != read_size)
 328             {
 329               error (0, errno, "%s", file);
 330               return 1;
 331             }
 332         }
 333       else
 334         {
 335           /* Found a match of `separator'. */
 336           if (separator_ends_record)
 337             {
 338               char *match_end = match_start + match_length;
 339
 340               /* If this match of `separator' isn't at the end of the
 341                  file, print the record. */
 342               if (first_time == 0 || match_end != past_end)
 343                 output (match_end, past_end);
 344               past_end = match_end;
 345               first_time = 0;
 346             }
 347           else
 348             {
 349               output (match_start, past_end);
 350               past_end = match_start;
 351             }
 352
 353           /* For non-regex matching, we can back up.  */
 354           if (sentinel_length > 0)
 355             match_start -= match_length - 1;
 356         }
 357     }
 358 }
 359
 360 /* Print FILE in reverse.
 361    Return 0 if ok, 1 if an error occurs. */
 362
 363 static int
 364 tac_file (const char *file)
 365 {
 366   int errors;
 367   FILE *in;
 368
 369   in = fopen (file, "r");
 370   if (in == NULL)
 371     {
 372       error (0, errno, "%s", file);
 373       return 1;
 374     }
 375   SET_BINARY (fileno (in));
 376   errors = tac_seekable (fileno (in), file);
 377   if (ferror (in) || fclose (in) == EOF)
 378     {
 379       error (0, errno, "%s", file);
 380       return 1;
 381     }
 382   return errors;
 383 }
 384
 385 #if DONT_UNLINK_WHILE_OPEN
 386
 387 static const char *file_to_remove;
 388 static FILE *fp_to_close;
 389
 390 static void
 391 unlink_tempfile (void)
 392 {
 393   fclose (fp_to_close);
 394   unlink (file_to_remove);
 395 }
 396
 397 static void
 398 record_tempfile (const char *fn, FILE *fp)
 399 {
 400   if (!file_to_remove)
 401     {
 402       file_to_remove = fn;
 403       fp_to_close = fp;
 404       atexit (unlink_tempfile);
 405     }
 406 }
 407
 408 #endif
 409
 410 /* Make a copy of the standard input in `FIXME'. */
 411
 412 static void
 413 save_stdin (FILE **g_tmp, char **g_tempfile)
 414 {
 415   static char *template = NULL;
 416   static char *tempdir;
 417   static char *tempfile;
 418   FILE *tmp;
 419   ssize_t bytes_read;
 420   int fd;
 421
 422   if (template == NULL)
 423     {
 424       tempdir = getenv ("TMPDIR");
 425       if (tempdir == NULL)
 426         tempdir = DEFAULT_TMPDIR;
 427       template = xmalloc (strlen (tempdir) + 11);
 428     }
 429   sprintf (template, "%s/tacXXXXXX", tempdir);
 430   tempfile = mktemp (template);
 431
 432   /*  Open temporary file exclusively, to foil a common
 433       denial-of-service attack.  */
 434   fd = open (tempfile, O_RDWR | O_CREAT | O_TRUNC | O_EXCL, 0600);
 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 }