src/tac.c

   1 /* tac - concatenate and print files in reverse
   2    Copyright (C) 88,89,90,91,95,96,97, 1998 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 2, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software Foundation,
  16    Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
  17
  18 /* Written by Jay Lepreau (lepreau@cs.utah.edu).
  19    GNU enhancements by David MacKenzie (djm@gnu.ai.mit.edu). */
  20
  21 /* Copy each FILE, or the standard input if none are given or when a
  22    FILE name of "-" is encountered, to the standard output with the
  23    order of the records reversed.  The records are separated by
  24    instances of a string, or a newline if none is given.  By default, the
  25    separator string is attached to the end of the record that it
  26    follows in the file.
  27
  28    Options:
  29    -b, --before                 The separator is attached to the beginning
  30                                 of the record that it precedes in the file.
  31    -r, --regex                  The separator is a regular expression.
  32    -s, --separator=separator    Use SEPARATOR as the record separator.
  33
  34    To reverse a file byte by byte, use (in bash, ksh, or sh):
  35 tac -r -s '.\|
  36 ' file */
  37
  38 #include <config.h>
  39
  40 #include <stdio.h>
  41 #include <getopt.h>
  42 #include <sys/types.h>
  43 #include "system.h"
  44
  45 #if WITH_REGEX
  46 # include <regex.h>
  47 #else
  48 # include <rx.h>
  49 #endif
  50
  51 #include "error.h"
  52 #include "safe-read.h"
  53
  54 #ifndef DEFAULT_TMPDIR
  55 # define DEFAULT_TMPDIR "/tmp"
  56 #endif
  57
  58 /* The number of bytes per atomic read. */
  59 #define INITIAL_READSIZE 8192
  60
  61 /* The number of bytes per atomic write. */
  62 #define WRITESIZE 8192
  63
  64 char *mktemp ();
  65
  66 /* The name this program was run with. */
  67 char *program_name;
  68
  69 /* The string that separates the records of the file. */
  70 static char *separator;
  71
  72 /* If nonzero, print `separator' along with the record preceding it
  73    in the file; otherwise with the record following it. */
  74 static int separator_ends_record;
  75
  76 /* 0 if `separator' is to be matched as a regular expression;
  77    otherwise, the length of `separator', used as a sentinel to
  78    stop the search. */
  79 static int sentinel_length;
  80
  81 /* The length of a match with `separator'.  If `sentinel_length' is 0,
  82    `match_length' is computed every time a match succeeds;
  83    otherwise, it is simply the length of `separator'. */
  84 static int match_length;
  85
  86 /* The input buffer. */
  87 static char *G_buffer;
  88
  89 /* The number of bytes to read at once into `buffer'. */
  90 static size_t read_size;
  91
  92 /* The size of `buffer'.  This is read_size * 2 + sentinel_length + 2.
  93    The extra 2 bytes allow `past_end' to have a value beyond the
  94    end of `G_buffer' and `match_start' to run off the front of `G_buffer'. */
  95 static unsigned G_buffer_size;
  96
  97 /* The compiled regular expression representing `separator'. */
  98 static struct re_pattern_buffer compiled_separator;
  99
 100 /* If nonzero, display usage information and exit.  */
 101 static int show_help;
 102
 103 /* If nonzero, print the version on standard output then exit.  */
 104 static int show_version;
 105
 106 static struct option const longopts[] =
 107 {
 108   {"before", no_argument, NULL, 'b'},
 109   {"regex", no_argument, NULL, 'r'},
 110   {"separator", required_argument, NULL, 's'},
 111   {"help", no_argument, &show_help, 1},
 112   {"version", no_argument, &show_version, 1},
 113   {NULL, 0, NULL, 0}
 114 };
 115
 116 static void
 117 usage (int status)
 118 {
 119   if (status != 0)
 120     fprintf (stderr, _("Try `%s --help' for more information.\n"),
 121              program_name);
 122   else
 123     {
 124       printf (_("\
 125 Usage: %s [OPTION]... [FILE]...\n\
 126 "),
 127               program_name);
 128       printf (_("\
 129 Write each FILE to standard output, last line first.\n\
 130 With no FILE, or when FILE is -, read standard input.\n\
 131 \n\
 132   -b, --before             attach the separator before instead of after\n\
 133   -r, --regex              interpret the separator as a regular expression\n\
 134   -s, --separator=STRING   use STRING as the separator instead of newline\n\
 135       --help               display this help and exit\n\
 136       --version            output version information and exit\n\
 137 "));
 138       puts (_("\nReport bugs to <textutils-bugs@gnu.org>."));
 139     }
 140   exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
 141 }
 142
 143 /* Print the characters from START to PAST_END - 1.
 144    If START is NULL, just flush the buffer. */
 145
 146 static void
 147 output (const char *start, const char *past_end)
 148 {
 149   static char buffer[WRITESIZE];
 150   static int bytes_in_buffer = 0;
 151   int bytes_to_add = past_end - start;
 152   int bytes_available = WRITESIZE - bytes_in_buffer;
 153
 154   if (start == 0)
 155     {
 156       fwrite (buffer, 1, bytes_in_buffer, stdout);
 157       bytes_in_buffer = 0;
 158       return;
 159     }
 160
 161   /* Write out as many full buffers as possible. */
 162   while (bytes_to_add >= bytes_available)
 163     {
 164       memcpy (buffer + bytes_in_buffer, start, bytes_available);
 165       bytes_to_add -= bytes_available;
 166       start += bytes_available;
 167       fwrite (buffer, 1, WRITESIZE, stdout);
 168       bytes_in_buffer = 0;
 169       bytes_available = WRITESIZE;
 170     }
 171
 172   memcpy (buffer + bytes_in_buffer, start, bytes_to_add);
 173   bytes_in_buffer += bytes_to_add;
 174 }
 175
 176 /* Print in reverse the file open on descriptor FD for reading FILE.
 177    Return 0 if ok, 1 if an error occurs. */
 178
 179 static int
 180 tac_seekable (int input_fd, const char *file)
 181 {
 182   /* Pointer to the location in `G_buffer' where the search for
 183      the next separator will begin. */
 184   char *match_start;
 185
 186   /* Pointer to one past the rightmost character in `G_buffer' that
 187      has not been printed yet. */
 188   char *past_end;
 189
 190   /* Length of the record growing in `G_buffer'. */
 191   size_t saved_record_size;
 192
 193   /* Offset in the file of the next read. */
 194   off_t file_pos;
 195
 196   /* Nonzero if `output' has not been called yet for any file.
 197      Only used when the separator is attached to the preceding record. */
 198   int first_time = 1;
 199   char first_char = *separator; /* Speed optimization, non-regexp. */
 200   char *separator1 = separator + 1; /* Speed optimization, non-regexp. */
 201   int match_length1 = match_length - 1; /* Speed optimization, non-regexp. */
 202   struct re_registers regs;
 203
 204   /* Find the size of the input file. */
 205   file_pos = lseek (input_fd, (off_t) 0, SEEK_END);
 206   if (file_pos < 1)
 207     return 0;                   /* It's an empty file. */
 208
 209   /* Arrange for the first read to lop off enough to leave the rest of the
 210      file a multiple of `read_size'.  Since `read_size' can change, this may
 211      not always hold during the program run, but since it usually will, leave
 212      it here for i/o efficiency (page/sector boundaries and all that).
 213      Note: the efficiency gain has not been verified. */
 214   saved_record_size = file_pos % read_size;
 215   if (saved_record_size == 0)
 216     saved_record_size = read_size;
 217   file_pos -= saved_record_size;
 218   /* `file_pos' now points to the start of the last (probably partial) block
 219      in the input file. */
 220
 221   if (lseek (input_fd, file_pos, SEEK_SET) < 0)
 222     error (0, errno, "%s: seek failed", file);
 223
 224   if (safe_read (input_fd, G_buffer, saved_record_size) != saved_record_size)
 225     {
 226       error (0, errno, "%s", file);
 227       return 1;
 228     }
 229
 230   match_start = past_end = G_buffer + saved_record_size;
 231   /* For non-regexp search, move past impossible positions for a match. */
 232   if (sentinel_length)
 233     match_start -= match_length1;
 234
 235   for (;;)
 236     {
 237       /* Search backward from `match_start' - 1 to `G_buffer' for a match
 238          with `separator'; for speed, use strncmp if `separator' contains no
 239          metacharacters.
 240          If the match succeeds, set `match_start' to point to the start of
 241          the match and `match_length' to the length of the match.
 242          Otherwise, make `match_start' < `G_buffer'. */
 243       if (sentinel_length == 0)
 244         {
 245           int i = match_start - G_buffer;
 246           int ret;
 247
 248           ret = re_search (&compiled_separator, G_buffer, i, i - 1, -i, &regs);
 249           if (ret == -1)
 250             match_start = G_buffer - 1;
 251           else if (ret == -2)
 252             {
 253               error (EXIT_FAILURE, 0,
 254                      _("error in regular expression search"));
 255             }
 256           else
 257             {
 258               match_start = G_buffer + regs.start[0];
 259               match_length = regs.end[0] - regs.start[0];
 260             }
 261         }
 262       else
 263         {
 264           /* `match_length' is constant for non-regexp boundaries. */
 265           while (*--match_start != first_char
 266                  || (match_length1 && strncmp (match_start + 1, separator1,
 267                                                match_length1)))
 268             /* Do nothing. */ ;
 269         }
 270
 271       /* Check whether we backed off the front of `G_buffer' without finding
 272          a match for `separator'. */
 273       if (match_start < G_buffer)
 274         {
 275           if (file_pos == 0)
 276             {
 277               /* Hit the beginning of the file; print the remaining record. */
 278               output (G_buffer, past_end);
 279               return 0;
 280             }
 281
 282           saved_record_size = past_end - G_buffer;
 283           if (saved_record_size > read_size)
 284             {
 285               /* `G_buffer_size' is about twice `read_size', so since
 286                  we want to read in another `read_size' bytes before
 287                  the data already in `G_buffer', we need to increase
 288                  `G_buffer_size'. */
 289               char *newbuffer;
 290               int offset = sentinel_length ? sentinel_length : 1;
 291
 292               read_size *= 2;
 293               G_buffer_size = read_size * 2 + sentinel_length + 2;
 294               newbuffer = xrealloc (G_buffer - offset, G_buffer_size);
 295               newbuffer += offset;
 296               /* Adjust the pointers for the new buffer location.  */
 297               match_start += newbuffer - G_buffer;
 298               past_end += newbuffer - G_buffer;
 299               G_buffer = newbuffer;
 300             }
 301
 302           /* Back up to the start of the next bufferfull of the file.  */
 303           if (file_pos >= read_size)
 304             file_pos -= read_size;
 305           else
 306             {
 307               read_size = file_pos;
 308               file_pos = 0;
 309             }
 310           lseek (input_fd, file_pos, SEEK_SET);
 311
 312           /* Shift the pending record data right to make room for the new.
 313              The source and destination regions probably overlap.  */
 314           memmove (G_buffer + read_size, G_buffer, saved_record_size);
 315           past_end = G_buffer + read_size + saved_record_size;
 316           /* For non-regexp searches, avoid unneccessary scanning. */
 317           if (sentinel_length)
 318             match_start = G_buffer + read_size;
 319           else
 320             match_start = past_end;
 321
 322           if (safe_read (input_fd, G_buffer, read_size) != read_size)
 323             {
 324               error (0, errno, "%s", file);
 325               return 1;
 326             }
 327         }
 328       else
 329         {
 330           /* Found a match of `separator'. */
 331           if (separator_ends_record)
 332             {
 333               char *match_end = match_start + match_length;
 334
 335               /* If this match of `separator' isn't at the end of the
 336                  file, print the record. */
 337               if (first_time == 0 || match_end != past_end)
 338                 output (match_end, past_end);
 339               past_end = match_end;
 340               first_time = 0;
 341             }
 342           else
 343             {
 344               output (match_start, past_end);
 345               past_end = match_start;
 346             }
 347
 348           /* For non-regex matching, we can back up.  */
 349           if (sentinel_length > 0)
 350             match_start -= match_length - 1;
 351         }
 352     }
 353 }
 354
 355 /* Print FILE in reverse.
 356    Return 0 if ok, 1 if an error occurs. */
 357
 358 static int
 359 tac_file (const char *file)
 360 {
 361   int errors;
 362   FILE *in;
 363
 364   in = fopen (file, "r");
 365   if (in == NULL)
 366     {
 367       error (0, errno, "%s", file);
 368       return 1;
 369     }
 370   errors = tac_seekable (fileno (in), file);
 371   if (ferror (in) || fclose (in) == EOF)
 372     {
 373       error (0, errno, "%s", file);
 374       return 1;
 375     }
 376   return errors;
 377 }
 378
 379 /* Make a copy of the standard input in `FIXME'. */
 380
 381 static void
 382 save_stdin (FILE **g_tmp, char **g_tempfile)
 383 {
 384   static char *template = NULL;
 385   static char *tempdir;
 386   static char *tempfile;
 387   FILE *tmp;
 388   ssize_t bytes_read;
 389   int fd;
 390
 391   if (template == NULL)
 392     {
 393       tempdir = getenv ("TMPDIR");
 394       if (tempdir == NULL)
 395         tempdir = DEFAULT_TMPDIR;
 396       template = xmalloc (strlen (tempdir) + 11);
 397     }
 398   sprintf (template, "%s/tacXXXXXX", tempdir);
 399   tempfile = mktemp (template);
 400
 401   fd = open (tempfile, O_RDWR | O_CREAT | O_TRUNC | O_EXCL, 0600);
 402   if (fd == -1)
 403     error (EXIT_FAILURE, errno, "%s", tempfile);
 404
 405   tmp = fdopen (fd, "w+");
 406   if (tmp == NULL)
 407     error (EXIT_FAILURE, errno, "%s", tempfile);
 408
 409   unlink (tempfile);
 410
 411   while (1)
 412     {
 413       bytes_read = safe_read (STDIN_FILENO, G_buffer, read_size);
 414       if (bytes_read == 0)
 415         break;
 416       if (bytes_read < 0)
 417         error (EXIT_FAILURE, errno, _("stdin: read error"));
 418
 419       /* Don't bother checking for failure inside the loop -- check after.  */
 420       fwrite (G_buffer, 1, bytes_read, tmp);
 421     }
 422
 423   if (ferror (tmp) || fflush (tmp) == EOF)
 424     error (EXIT_FAILURE, errno, "%s", tempfile);
 425
 426   rewind (tmp);
 427
 428   *g_tmp = tmp;
 429   *g_tempfile = tempfile;
 430 }
 431
 432 /* Print the standard input in reverse, saving it to temporary
 433    file first if it is a pipe.
 434    Return 0 if ok, 1 if an error occurs. */
 435
 436 static int
 437 tac_stdin (void)
 438 {
 439   int errors;
 440   struct stat stats;
 441
 442   /* No tempfile is needed for "tac < file".
 443      Use fstat instead of checking for errno == ESPIPE because
 444      lseek doesn't work on some special files but doesn't return an
 445      error, either. */
 446   if (fstat (STDIN_FILENO, &stats))
 447     {
 448       error (0, errno, _("standard input"));
 449       return 1;
 450     }
 451
 452   if (S_ISREG (stats.st_mode))
 453     {
 454       errors = tac_seekable (fileno (stdin), _("standard input"));
 455     }
 456   else
 457     {
 458       FILE *tmp_stream;
 459       char *tmp_file;
 460       save_stdin (&tmp_stream, &tmp_file);
 461       errors = tac_seekable (fileno (tmp_stream), tmp_file);
 462     }
 463
 464   return errors;
 465 }
 466
 467 /* BUF_END points one byte past the end of the buffer to be searched.  */
 468
 469 static void *
 470 memrchr (const char *buf_start, const char *buf_end, int c)
 471 {
 472   const char *p = buf_end;
 473   while (buf_start <= --p)
 474     {
 475       if (*(const unsigned char *) p == c)
 476         return (void *) p;
 477     }
 478   return NULL;
 479 }
 480
 481 /* FIXME: describe */
 482
 483 static int
 484 tac_mem (const char *buf, size_t n_bytes, FILE *out)
 485 {
 486   const char *nl;
 487   const char *bol;
 488
 489   if (n_bytes == 0)
 490     return 0;
 491
 492   nl = memrchr (buf, buf + n_bytes, '\n');
 493   bol = (nl == NULL ? buf : nl + 1);
 494
 495   /* If the last line of the input file has no terminating newline,
 496      treat it as a special case.  */
 497   if (bol < buf + n_bytes)
 498     {
 499       /* Print out the line from bol to end of input.  */
 500       fwrite (bol, 1, (buf + n_bytes) - bol, out);
 501
 502       /* Add a newline here.  Otherwise, the first and second lines
 503          of output would appear to have been joined.  */
 504       fputc ('\n', out);
 505     }
 506
 507   while ((nl = memrchr (buf, bol - 1, '\n')) != NULL)
 508     {
 509       /* Output the line (which includes a trailing newline)
 510          from NL+1 to BOL-1.  */
 511       fwrite (nl + 1, 1, bol - (nl + 1), out);
 512
 513       bol = nl + 1;
 514     }
 515
 516   /* If there's anything left, output the last line: BUF .. BOL-1.
 517      When the first byte of the input is a newline, there is nothing
 518      left to do here.  */
 519   if (buf < bol)
 520     fwrite (buf, 1, bol - buf, out);
 521
 522   /* FIXME: this is work in progress.... */
 523   return ferror (out);
 524 }
 525
 526 /* FIXME: describe */
 527
 528 static int
 529 tac_stdin_to_mem (void)
 530 {
 531   char *buf = NULL;
 532   size_t bufsiz = 8 * BUFSIZ;
 533   size_t delta = 8 * BUFSIZ;
 534   size_t n_bytes = 0;
 535
 536   while (1)
 537     {
 538       ssize_t bytes_read;
 539       if (buf == NULL)
 540         buf = (char *) malloc (bufsiz);
 541       else
 542         buf = (char *) realloc (buf, bufsiz);
 543
 544       if (buf == NULL)
 545         {
 546           /* Free the buffer and fall back on the code that relies on a
 547              temporary file.  */
 548           free (buf);
 549           /* FIXME */
 550           abort ();
 551         }
 552       bytes_read = safe_read (STDIN_FILENO, buf + n_bytes, bufsiz - n_bytes);
 553       if (bytes_read == 0)
 554         break;
 555       if (bytes_read < 0)
 556         error (EXIT_FAILURE, errno, _("stdin: read error"));
 557       n_bytes += bytes_read;
 558
 559       bufsiz += delta;
 560     }
 561
 562   tac_mem (buf, n_bytes, stdout);
 563
 564   return 0;
 565 }
 566
 567 int
 568 main (int argc, char **argv)
 569 {
 570   const char *error_message;    /* Return value from re_compile_pattern. */
 571   int optc, errors;
 572   int have_read_stdin = 0;
 573
 574   program_name = argv[0];
 575   setlocale (LC_ALL, "");
 576   bindtextdomain (PACKAGE, LOCALEDIR);
 577   textdomain (PACKAGE);
 578
 579   errors = 0;
 580   separator = "\n";
 581   sentinel_length = 1;
 582   separator_ends_record = 1;
 583
 584   while ((optc = getopt_long (argc, argv, "brs:", longopts, NULL)) != -1)
 585     {
 586       switch (optc)
 587         {
 588         case 0:
 589           break;
 590         case 'b':
 591           separator_ends_record = 0;
 592           break;
 593         case 'r':
 594           sentinel_length = 0;
 595           break;
 596         case 's':
 597           separator = optarg;
 598           if (*separator == 0)
 599             error (EXIT_FAILURE, 0, _("separator cannot be empty"));
 600           break;
 601         default:
 602           usage (1);
 603         }
 604     }
 605
 606   if (show_version)
 607     {
 608       printf ("tac (%s) %s\n", GNU_PACKAGE, VERSION);
 609       exit (EXIT_SUCCESS);
 610     }
 611
 612   if (show_help)
 613     usage (0);
 614
 615   if (sentinel_length == 0)
 616     {
 617       compiled_separator.allocated = 100;
 618       compiled_separator.buffer = (unsigned char *)
 619         xmalloc (compiled_separator.allocated);
 620       compiled_separator.fastmap = xmalloc (256);
 621       compiled_separator.translate = 0;
 622       error_message = re_compile_pattern (separator, strlen (separator),
 623                                           &compiled_separator);
 624       if (error_message)
 625         error (EXIT_FAILURE, 0, "%s", error_message);
 626     }
 627   else
 628     match_length = sentinel_length = strlen (separator);
 629
 630   read_size = INITIAL_READSIZE;
 631   /* A precaution that will probably never be needed. */
 632   while (sentinel_length * 2 >= read_size)
 633     read_size *= 2;
 634   G_buffer_size = read_size * 2 + sentinel_length + 2;
 635   G_buffer = xmalloc (G_buffer_size);
 636   if (sentinel_length)
 637     {
 638       strcpy (G_buffer, separator);
 639       G_buffer += sentinel_length;
 640     }
 641   else
 642     {
 643       ++G_buffer;
 644     }
 645
 646   if (optind == argc)
 647     {
 648       have_read_stdin = 1;
 649       errors = tac_stdin ();
 650     }
 651   else
 652     {
 653       for (; optind < argc; ++optind)
 654         {
 655           if (STREQ (argv[optind], "-"))
 656             {
 657               have_read_stdin = 1;
 658               errors |= tac_stdin ();
 659             }
 660           else
 661             {
 662               errors |= tac_file (argv[optind]);
 663             }
 664         }
 665     }
 666
 667   /* Flush the output buffer. */
 668   output ((char *) NULL, (char *) NULL);
 669
 670   if (have_read_stdin && close (0) < 0)
 671     error (EXIT_FAILURE, errno, "-");
 672   if (ferror (stdout) || fclose (stdout) == EOF)
 673     error (EXIT_FAILURE, errno, _("write error"));
 674   exit (errors == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
 675 }