/* tr -- a filter to translate characters
   Copyright (C) 91, 1995-2002 Free Software Foundation, Inc.

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software Foundation,
   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */

/* Written by Jim Meyering */

#include <config.h>

#include <stdio.h>
#include <assert.h>
#include <errno.h>
#include <sys/types.h>
#include <getopt.h>

#include "system.h"
#include "closeout.h"
#include "error.h"
#include "safe-read.h"
#include "xstrtol.h"

/* The official name of this program (e.g., no `g' prefix).  */
#define PROGRAM_NAME "tr"

#define AUTHORS "Jim Meyering"

#define N_CHARS (UCHAR_MAX + 1)

/* A pointer to a filtering function.  */
typedef size_t (*Filter) (/* unsigned char *, size_t, Filter */);

/* Convert from character C to its index in the collating
   sequence array.  Just cast to an unsigned int to avoid
   problems with sign-extension.  */
#define ORD(c) (unsigned int)(c)

/* The inverse of ORD.  */
#define CHR(i) (unsigned char)(i)

/* The value for Spec_list->state that indicates to
   get_next that it should initialize the tail pointer.
   Its value should be as large as possible to avoid conflict
   a valid value for the state field -- and that may be as
   large as any valid repeat_count.  */
#define BEGIN_STATE (INT_MAX - 1)

/* The value for Spec_list->state that indicates to
   get_next that the element pointed to by Spec_list->tail is
   being considered for the first time on this pass through the
   list -- it indicates that get_next should make any necessary
   initializations.  */
#define NEW_ELEMENT (BEGIN_STATE + 1)

/* A value distinct from any character that may have been stored in a
   buffer as the result of a block-read in the function squeeze_filter.  */
#define NOT_A_CHAR (unsigned int)(-1)

/* The following (but not CC_NO_CLASS) are indices into the array of
   valid character class strings.  */
enum Char_class
  {
    CC_ALNUM = 0, CC_ALPHA = 1, CC_BLANK = 2, CC_CNTRL = 3,
    CC_DIGIT = 4, CC_GRAPH = 5, CC_LOWER = 6, CC_PRINT = 7,
    CC_PUNCT = 8, CC_SPACE = 9, CC_UPPER = 10, CC_XDIGIT = 11,
    CC_NO_CLASS = 9999
  };

/* Character class to which a character (returned by get_next) belonged;
   but it is set only if the construct from which the character was obtained
   was one of the character classes [:upper:] or [:lower:].  The value
   is used only when translating and then, only to make sure that upper
   and lower class constructs have the same relative positions in string1
   and string2.  */
enum Upper_Lower_class
  {
    UL_LOWER = 0,
    UL_UPPER = 1,
    UL_NONE = 2
  };

/* A shortcut to ensure that when constructing the translation array,
   one of the values returned by paired calls to get_next (from s1 and s2)
   is from [:upper:] and the other is from [:lower:], or neither is from
   upper or lower.  By default, GNU tr permits the identity mappings: from
   [:upper:] to [:upper:] and [:lower:] to [:lower:].  But when
   POSIXLY_CORRECT is set, those evoke diagnostics. This array is indexed
   by values of type enum Upper_Lower_class.  */
static int const class_ok[3][3] =
{
  {1, 1, 0},
  {1, 1, 0},
  {0, 0, 1}
};

/* The type of a List_element.  See build_spec_list for more details.  */
enum Range_element_type
  {
    RE_NO_TYPE = 0,
    RE_NORMAL_CHAR,
    RE_RANGE,
    RE_CHAR_CLASS,
    RE_EQUIV_CLASS,
    RE_REPEATED_CHAR
  };

/* One construct in one of tr's argument strings.
   For example, consider the POSIX version of the classic tr command:
       tr -cs 'a-zA-Z_' '[\n*]'
   String1 has 3 constructs, two of which are ranges (a-z and A-Z),
   and a single normal character, `_'.  String2 has one construct.  */
struct List_element
  {
    enum Range_element_type type;
    struct List_element *next;
    union
      {
	int normal_char;
	struct			/* unnamed */
	  {
	    unsigned int first_char;
	    unsigned int last_char;
	  }
	range;
	enum Char_class char_class;
	int equiv_code;
	struct			/* unnamed */
	  {
	    unsigned int the_repeated_char;
	    size_t repeat_count;
	  }
	repeated_char;
      }
    u;
  };

/* Each of tr's argument strings is parsed into a form that is easier
   to work with: a linked list of constructs (struct List_element).
   Each Spec_list structure also encapsulates various attributes of
   the corresponding argument string.  The attributes are used mainly
   to verify that the strings are valid in the context of any options
   specified (like -s, -d, or -c).  The main exception is the member
   `tail', which is first used to construct the list.  After construction,
   it is used by get_next to save its state when traversing the list.
   The member `state' serves a similar function.  */
struct Spec_list
  {
    /* Points to the head of the list of range elements.
       The first struct is a dummy; its members are never used.  */
    struct List_element *head;

    /* When appending, points to the last element.  When traversing via
       get_next(), points to the element to process next.  Setting
       Spec_list.state to the value BEGIN_STATE before calling get_next
       signals get_next to initialize tail to point to head->next.  */
    struct List_element *tail;

    /* Used to save state between calls to get_next().  */
    unsigned int state;

    /* Length, in the sense that length ('a-z[:digit:]123abc')
       is 42 ( = 26 + 10 + 6).  */
    size_t length;

    /* The number of [c*] and [c*0] constructs that appear in this spec.  */
    int n_indefinite_repeats;

    /* If n_indefinite_repeats is nonzero, this points to the List_element
       corresponding to the last [c*] or [c*0] construct encountered in
       this spec.  Otherwise it is undefined.  */
    struct List_element *indefinite_repeat_element;

    /* Non-zero if this spec contains at least one equivalence
       class construct e.g. [=c=].  */
    int has_equiv_class;

    /* Non-zero if this spec contains at least one character class
       construct.  E.g. [:digit:].  */
    int has_char_class;

    /* Non-zero if this spec contains at least one of the character class
       constructs (all but upper and lower) that aren't allowed in s2.  */
    int has_restricted_char_class;
  };

/* A representation for escaped string1 or string2.  As a string is parsed,
   any backslash-escaped characters (other than octal or \a, \b, \f, \n,
   etc.) are marked as such in this structure by setting the corresponding
   entry in the ESCAPED vector.  */
struct E_string
{
  unsigned char *s;
  int *escaped;
  size_t len;
};

/* Return nonzero if the Ith character of escaped string ES matches C
   and is not escaped itself.  */
#define ES_MATCH(ES, I, C) ((ES)->s[(I)] == (C) && !(ES)->escaped[(I)])

/* The name by which this program was run.  */
char *program_name;

/* When nonzero, each sequence in the input of a repeated character
   (call it c) is replaced (in the output) by a single occurrence of c
   for every c in the squeeze set.  */
static int squeeze_repeats = 0;

/* When nonzero, removes characters in the delete set from input.  */
static int delete = 0;

/* Use the complement of set1 in place of set1.  */
static int complement = 0;

/* When nonzero, this flag causes GNU tr to provide strict
   compliance with POSIX draft 1003.2.11.2.  The POSIX spec
   says that when -d is used without -s, string2 (if present)
   must be ignored.  Silently ignoring arguments is a bad idea.
   The default GNU behavior is to give a usage message and exit.
   Additionally, when this flag is nonzero, tr prints warnings
   on stderr if it is being used in a manner that is not portable.
   Applicable warnings are given by default, but are suppressed
   if the environment variable `POSIXLY_CORRECT' is set, since
   being POSIX conformant means we can't issue such messages.
   Warnings on the following topics are suppressed when this
   variable is nonzero:
   1. Ambiguous octal escapes.  */
static int posix_pedantic;

/* When tr is performing translation and string1 is longer than string2,
   POSIX says that the result is undefined.  That gives the implementor
   of a POSIX conforming version of tr two reasonable choices for the
   semantics of this case.

   * The BSD tr pads string2 to the length of string1 by
   repeating the last character in string2.

   * System V tr ignores characters in string1 that have no
   corresponding character in string2.  That is, string1 is effectively
   truncated to the length of string2.

   When nonzero, this flag causes GNU tr to imitate the behavior
   of System V tr when translating with string1 longer than string2.
   The default is to emulate BSD tr.  This flag is ignored in modes where
   no translation is performed.  Emulating the System V tr
   in this exceptional case causes the relatively common BSD idiom:

       tr -cs A-Za-z0-9 '\012'

   to break (it would convert only zero bytes, rather than all
   non-alphanumerics, to newlines).

   WARNING: This switch does not provide general BSD or System V
   compatibility.  For example, it doesn't disable the interpretation
   of the POSIX constructs [:alpha:], [=c=], and [c*10], so if by
   some unfortunate coincidence you use such constructs in scripts
   expecting to use some other version of tr, the scripts will break.  */
static int truncate_set1 = 0;

/* An alias for (!delete && non_option_args == 2).
   It is set in main and used there and in validate().  */
static int translating;

#ifndef BUFSIZ
# define BUFSIZ 8192
#endif

#define IO_BUF_SIZE BUFSIZ
static unsigned char io_buf[IO_BUF_SIZE];

static char const *const char_class_name[] =
{
  "alnum", "alpha", "blank", "cntrl", "digit", "graph",
  "lower", "print", "punct", "space", "upper", "xdigit"
};
#define N_CHAR_CLASSES (sizeof(char_class_name) / sizeof(char_class_name[0]))

typedef char SET_TYPE;

/* Array of boolean values.  A character `c' is a member of the
   squeeze set if and only if in_squeeze_set[c] is true.  The squeeze
   set is defined by the last (possibly, the only) string argument
   on the command line when the squeeze option is given.  */
static SET_TYPE in_squeeze_set[N_CHARS];

/* Array of boolean values.  A character `c' is a member of the
   delete set if and only if in_delete_set[c] is true.  The delete
   set is defined by the first (or only) string argument on the
   command line when the delete option is given.  */
static SET_TYPE in_delete_set[N_CHARS];

/* Array of character values defining the translation (if any) that
   tr is to perform.  Translation is performed only when there are
   two specification strings and the delete switch is not given.  */
static char xlate[N_CHARS];

static struct option const long_options[] =
{
  {"complement", no_argument, NULL, 'c'},
  {"delete", no_argument, NULL, 'd'},
  {"squeeze-repeats", no_argument, NULL, 's'},
  {"truncate-set1", no_argument, NULL, 't'},
  {GETOPT_HELP_OPTION_DECL},
  {GETOPT_VERSION_OPTION_DECL},
  {NULL, 0, NULL, 0}
};
 

void
usage (int status)
{
  if (status != 0)
    fprintf (stderr, _("Try `%s --help' for more information.\n"),
	     program_name);
  else
    {
      printf (_("\
Usage: %s [OPTION]... SET1 [SET2]\n\
"),
	      program_name);
      fputs (_("\
Translate, squeeze, and/or delete characters from standard input,\n\
writing to standard output.\n\
\n\
  -c, --complement        first complement SET1\n\
  -d, --delete            delete characters in SET1, do not translate\n\
  -s, --squeeze-repeats   replace each input sequence of a repeated character\n\
                            that is listed in SET1 with a single occurrence\n\
                            of that character\n\
  -t, --truncate-set1     first truncate SET1 to length of SET2\n\
"), stdout);
      fputs (HELP_OPTION_DESCRIPTION, stdout);
      fputs (VERSION_OPTION_DESCRIPTION, stdout);
      fputs (_("\
\n\
SETs are specified as strings of characters.  Most represent themselves.\n\
Interpreted sequences are:\n\
\n\
  \\NNN            character with octal value NNN (1 to 3 octal digits)\n\
  \\\\              backslash\n\
  \\a              audible BEL\n\
  \\b              backspace\n\
  \\f              form feed\n\
  \\n              new line\n\
  \\r              return\n\
  \\t              horizontal tab\n\
"), stdout);
     fputs (_("\
  \\v              vertical tab\n\
  CHAR1-CHAR2     all characters from CHAR1 to CHAR2 in ascending order\n\
  [CHAR*]         in SET2, copies of CHAR until length of SET1\n\
  [CHAR*REPEAT]   REPEAT copies of CHAR, REPEAT octal if starting with 0\n\
  [:alnum:]       all letters and digits\n\
  [:alpha:]       all letters\n\
  [:blank:]       all horizontal whitespace\n\
  [:cntrl:]       all control characters\n\
  [:digit:]       all digits\n\
"), stdout);
     fputs (_("\
  [:graph:]       all printable characters, not including space\n\
  [:lower:]       all lower case letters\n\
  [:print:]       all printable characters, including space\n\
  [:punct:]       all punctuation characters\n\
  [:space:]       all horizontal or vertical whitespace\n\
  [:upper:]       all upper case letters\n\
  [:xdigit:]      all hexadecimal digits\n\
  [=CHAR=]        all characters which are equivalent to CHAR\n\
"), stdout);
     fputs (_("\
\n\
Translation occurs if -d is not given and both SET1 and SET2 appear.\n\
-t may be used only when translating.  SET2 is extended to length of\n\
SET1 by repeating its last character as necessary.  \
"), stdout);
     fputs (_("\
Excess characters\n\
of SET2 are ignored.  Only [:lower:] and [:upper:] are guaranteed to\n\
expand in ascending order; used in SET2 while translating, they may\n\
only be used in pairs to specify case conversion.  \
"), stdout);
     fputs (_("\
-s uses SET1 if not\n\
translating nor deleting; else squeezing uses SET2 and occurs after\n\
translation or deletion.\n\
"), stdout);
      printf (_("\nReport bugs to <%s>.\n"), PACKAGE_BUGREPORT);
    }
  exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
}

/* Return nonzero if the character C is a member of the
   equivalence class containing the character EQUIV_CLASS.  */

static int
is_equiv_class_member (unsigned int equiv_class, unsigned int c)
{
  return (equiv_class == c);
}

/* Return nonzero if the character C is a member of the
   character class CHAR_CLASS.  */

static int
is_char_class_member (enum Char_class char_class, unsigned int c)
{
  int result;

  switch (char_class)
    {
    case CC_ALNUM:
      result = ISALNUM (c);
      break;
    case CC_ALPHA:
      result = ISALPHA (c);
      break;
    case CC_BLANK:
      result = ISBLANK (c);
      break;
    case CC_CNTRL:
      result = ISCNTRL (c);
      break;
    case CC_DIGIT:
      result = ISDIGIT_LOCALE (c);
      break;
    case CC_GRAPH:
      result = ISGRAPH (c);
      break;
    case CC_LOWER:
      result = ISLOWER (c);
      break;
    case CC_PRINT:
      result = ISPRINT (c);
      break;
    case CC_PUNCT:
      result = ISPUNCT (c);
      break;
    case CC_SPACE:
      result = ISSPACE (c);
      break;
    case CC_UPPER:
      result = ISUPPER (c);
      break;
    case CC_XDIGIT:
      result = ISXDIGIT (c);
      break;
    default:
      abort ();
      break;
    }
  return result;
}

static void
es_free (struct E_string *es)
{
  free (es->s);
  free (es->escaped);
}

/* Perform the first pass over each range-spec argument S, converting all
   \c and \ddd escapes to their one-byte representations.  The conversion
   is done in-place, so S must point to writable storage.  If an invalid
   quote sequence is found print an error message and return nonzero.
   Otherwise set *LEN to the length of the resulting string and return
   zero.  The resulting array of characters may contain zero-bytes;
   however, on input, S is assumed to be null-terminated, and hence
   cannot contain actual (non-escaped) zero bytes.  */

static int
unquote (const unsigned char *s, struct E_string *es)
{
  size_t i, j;
  size_t len;

  len = strlen ((char *) s);

  es->s = (unsigned char *) xmalloc (len);
  es->escaped = (int *) xmalloc (len * sizeof (es->escaped[0]));
  for (i = 0; i < len; i++)
    es->escaped[i] = 0;

  j = 0;
  for (i = 0; s[i]; i++)
    {
      switch (s[i])
	{
	  int c;
	case '\\':
	  switch (s[i + 1])
	    {
	      int oct_digit;
	    case '\\':
	      c = '\\';
	      break;
	    case 'a':
	      c = '\007';
	      break;