1 /* tr -- a filter to translate characters
2 Copyright (C) 1991, 1995 Free Software Foundation, Inc.
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)
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.
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. */
18 /* Written by Jim Meyering, meyering@cs.utexas.edu. */
22 /* Get isblank from GNU libc. */
29 #include <sys/types.h>
40 #define ULONG_MAX ((unsigned long) ~(unsigned long) 0)
44 #define LONG_MAX ((long int) (ULONG_MAX >> 1))
48 # define UINT_MAX ((unsigned int) ~(unsigned int) 0)
52 # define INT_MAX ((int) (UINT_MAX >> 1))
56 #define UCHAR_MAX 0xFF
59 #define N_CHARS (UCHAR_MAX + 1)
61 /* A pointer to a function that returns an int. */
62 typedef int (*PFI) ();
64 /* Convert from character C to its index in the collating
65 sequence array. Just cast to an unsigned int to avoid
66 problems with sign-extension. */
67 #define ORD(c) (unsigned int)(c)
69 /* The inverse of ORD. */
70 #define CHR(i) (unsigned char)(i)
72 /* The value for Spec_list->state that indicates to
73 get_next that it should initialize the tail pointer.
74 Its value should be as large as possible to avoid conflict
75 a valid value for the state field -- and that may be as
76 large as any valid repeat_count. */
77 #define BEGIN_STATE (INT_MAX - 1)
79 /* The value for Spec_list->state that indicates to
80 get_next that the element pointed to by Spec_list->tail is
81 being considered for the first time on this pass through the
82 list -- it indicates that get_next should make any necessary
84 #define NEW_ELEMENT (BEGIN_STATE + 1)
86 /* A value distinct from any character that may have been stored in a
87 buffer as the result of a block-read in the function squeeze_filter. */
88 #define NOT_A_CHAR (unsigned int)(-1)
90 /* The following (but not CC_NO_CLASS) are indices into the array of
91 valid character class strings. */
94 CC_ALNUM = 0, CC_ALPHA = 1, CC_BLANK = 2, CC_CNTRL = 3,
95 CC_DIGIT = 4, CC_GRAPH = 5, CC_LOWER = 6, CC_PRINT = 7,
96 CC_PUNCT = 8, CC_SPACE = 9, CC_UPPER = 10, CC_XDIGIT = 11,
100 /* Character class to which a character (returned by get_next) belonged;
101 but it is set only if the construct from which the character was obtained
102 was one of the character classes [:upper:] or [:lower:]. The value
103 is used only when translating and then, only to make sure that upper
104 and lower class constructs have the same relative positions in string1
106 enum Upper_Lower_class
113 /* A shortcut to ensure that when constructing the translation array,
114 one of the values returned by paired calls to get_next (from s1 and s2)
115 is from [:upper:] and the other is from [:lower:], or neither is from
116 upper or lower. In fact, no other character classes are allowed when
117 translating, but that condition is tested elsewhere. This array is
118 indexed by values of type enum Upper_Lower_class. */
119 static int const class_ok[3][3] =
126 /* The type of a List_element. See build_spec_list for more details. */
127 enum Range_element_type
137 /* One construct in one of tr's argument strings.
138 For example, consider the POSIX version of the classic tr command:
139 tr -cs 'a-zA-Z_' '[\n*]'
140 String1 has 3 constructs, two of which are ranges (a-z and A-Z),
141 and a single normal character, `_'. String2 has one construct. */
144 enum Range_element_type type;
145 struct List_element *next;
151 unsigned int first_char;
152 unsigned int last_char;
155 enum Char_class char_class;
159 unsigned int the_repeated_char;
167 /* Each of tr's argument strings is parsed into a form that is easier
168 to work with: a linked list of constructs (struct List_element).
169 Each Spec_list structure also encapsulates various attributes of
170 the corresponding argument string. The attributes are used mainly
171 to verify that the strings are valid in the context of any options
172 specified (like -s, -d, or -c). The main exception is the member
173 `tail', which is first used to construct the list. After construction,
174 it is used by get_next to save its state when traversing the list.
175 The member `state' serves a similar function. */
178 /* Points to the head of the list of range elements.
179 The first struct is a dummy; its members are never used. */
180 struct List_element *head;
182 /* When appending, points to the last element. When traversing via
183 get_next(), points to the element to process next. Setting
184 Spec_list.state to the value BEGIN_STATE before calling get_next
185 signals get_next to initialize tail to point to head->next. */
186 struct List_element *tail;
188 /* Used to save state between calls to get_next(). */
191 /* Length, in the sense that length ('a-z[:digit:]123abc')
192 is 42 ( = 26 + 10 + 6). */
195 /* The number of [c*] and [c*0] constructs that appear in this spec. */
196 int n_indefinite_repeats;
198 /* If n_indefinite_repeats is nonzero, this points to the List_element
199 corresponding to the last [c*] or [c*0] construct encountered in
200 this spec. Otherwise it is undefined. */
201 struct List_element *indefinite_repeat_element;
203 /* Non-zero if this spec contains at least one equivalence
204 class construct e.g. [=c=]. */
207 /* Non-zero if this spec contains at least one of [:upper:] or
208 [:lower:] class constructs. */
209 int has_upper_or_lower;
211 /* Non-zero if this spec contains at least one of the character class
212 constructs (all but upper and lower) that aren't allowed in s2. */
213 int has_restricted_char_class;
216 /* A representation for escaped string1 or string2. As a string is parsed,
217 any backslash-escaped characters (other than octal or \a, \b, \f, \n,
218 etc.) are marked as such in this structure by setting the corresponding
219 entry in the ESCAPED vector. */
227 /* Return nonzero if the Ith character of escaped string ES matches C
228 and is not escaped itself. */
229 #define ES_MATCH(ES, I, C) ((ES)->s[(I)] == (C) && !(ES)->escaped[(I)])
236 /* The name by which this program was run. */
239 /* When nonzero, each sequence in the input of a repeated character
240 (call it c) is replaced (in the output) by a single occurrence of c
241 for every c in the squeeze set. */
242 static int squeeze_repeats = 0;
244 /* When nonzero, removes characters in the delete set from input. */
245 static int delete = 0;
247 /* Use the complement of set1 in place of set1. */
248 static int complement = 0;
250 /* When nonzero, this flag causes GNU tr to provide strict
251 compliance with POSIX draft 1003.2.11.2. The POSIX spec
252 says that when -d is used without -s, string2 (if present)
253 must be ignored. Silently ignoring arguments is a bad idea.
254 The default GNU behavior is to give a usage message and exit.
255 Additionally, when this flag is nonzero, tr prints warnings
256 on stderr if it is being used in a manner that is not portable.
257 Applicable warnings are given by default, but are suppressed
258 if the environment variable `POSIXLY_CORRECT' is set, since
259 being POSIX conformant means we can't issue such messages.
260 Warnings on the following topics are suppressed when this
262 1. Ambiguous octal escapes. */
263 static int posix_pedantic;
265 /* When tr is performing translation and string1 is longer than string2,
266 POSIX says that the result is undefined. That gives the implementor
267 of a POSIX conforming version of tr two reasonable choices for the
268 semantics of this case.
270 * The BSD tr pads string2 to the length of string1 by
271 repeating the last character in string2.
273 * System V tr ignores characters in string1 that have no
274 corresponding character in string2. That is, string1 is effectively
275 truncated to the length of string2.
277 When nonzero, this flag causes GNU tr to imitate the behavior
278 of System V tr when translating with string1 longer than string2.
279 The default is to emulate BSD tr. This flag is ignored in modes where
280 no translation is performed. Emulating the System V tr
281 in this exceptional case causes the relatively common BSD idiom:
283 tr -cs A-Za-z0-9 '\012'
285 to break (it would convert only zero bytes, rather than all
286 non-alphanumerics, to newlines).
288 WARNING: This switch does not provide general BSD or System V
289 compatibility. For example, it doesn't disable the interpretation
290 of the POSIX constructs [:alpha:], [=c=], and [c*10], so if by
291 some unfortunate coincidence you use such constructs in scripts
292 expecting to use some other version of tr, the scripts will break. */
293 static int truncate_set1 = 0;
295 /* An alias for (!delete && non_option_args == 2).
296 It is set in main and used there and in validate(). */
297 static int translating;
303 #define IO_BUF_SIZE BUFSIZ
304 static unsigned char io_buf[IO_BUF_SIZE];
306 static char const *const char_class_name[] =
308 "alnum", "alpha", "blank", "cntrl", "digit", "graph",
309 "lower", "print", "punct", "space", "upper", "xdigit"
311 #define N_CHAR_CLASSES (sizeof(char_class_name) / sizeof(char_class_name[0]))
313 typedef char SET_TYPE;
315 /* Array of boolean values. A character `c' is a member of the
316 squeeze set if and only if in_squeeze_set[c] is true. The squeeze
317 set is defined by the last (possibly, the only) string argument
318 on the command line when the squeeze option is given. */
319 static SET_TYPE in_squeeze_set[N_CHARS];
321 /* Array of boolean values. A character `c' is a member of the
322 delete set if and only if in_delete_set[c] is true. The delete
323 set is defined by the first (or only) string argument on the
324 command line when the delete option is given. */
325 static SET_TYPE in_delete_set[N_CHARS];
327 /* Array of character values defining the translation (if any) that
328 tr is to perform. Translation is performed only when there are
329 two specification strings and the delete switch is not given. */
330 static char xlate[N_CHARS];
332 /* If nonzero, display usage information and exit. */
333 static int show_help;
335 /* If nonzero, print the version on standard output then exit. */
336 static int show_version;
338 static struct option const long_options[] =
340 {"complement", no_argument, NULL, 'c'},
341 {"delete", no_argument, NULL, 'd'},
342 {"squeeze-repeats", no_argument, NULL, 's'},
343 {"truncate-set1", no_argument, NULL, 't'},
344 {"help", no_argument, &show_help, 1},
345 {"version", no_argument, &show_version, 1},
353 fprintf (stderr, _("Try `%s --help' for more information.\n"),
358 Usage: %s [OPTION]... SET1 [SET2]\n\
362 Translate, squeeze, and/or delete characters from standard input,\n\
363 writing to standard output.\n\
365 -c, --complement first complement SET1\n\
366 -d, --delete delete characters in SET1, do not translate\n\
367 -s, --squeeze-repeats replace sequence of characters with one\n\
368 -t, --truncate-set1 first truncate SET1 to length of SET2\n\
369 --help display this help and exit\n\
370 --version output version information and exit\n\
374 SETs are specified as strings of characters. Most represent themselves.\n\
375 Interpreted sequences are:\n\
377 \\NNN character with octal value NNN (1 to 3 octal digits)\n\
384 \\t horizontal tab\n\
386 CHAR1-CHAR2 all characters from CHAR1 to CHAR2 in ascending order\n\
387 [CHAR1-CHAR2] same as CHAR1-CHAR2, if both SET1 and SET2 use this\n\
388 [CHAR*] in SET2, copies of CHAR until length of SET1\n\
389 [CHAR*REPEAT] REPEAT copies of CHAR, REPEAT octal if starting with 0\n\
390 [:alnum:] all letters and digits\n\
391 [:alpha:] all letters\n\
392 [:blank:] all horizontal whitespace\n\
393 [:cntrl:] all control characters\n\
394 [:digit:] all digits\n\
395 [:graph:] all printable characters, not including space\n\
396 [:lower:] all lower case letters\n\
397 [:print:] all printable characters, including space\n\
398 [:punct:] all punctuation characters\n\
399 [:space:] all horizontal or vertical whitespace\n\
400 [:upper:] all upper case letters\n\
401 [:xdigit:] all hexadecimal digits\n\
402 [=CHAR=] all characters which are equivalent to CHAR\n\
406 Translation occurs if -d is not given and both SET1 and SET2 appear.\n\
407 -t may be used only when translating. SET2 is extended to length of\n\
408 SET1 by repeating its last character as necessary. Excess characters\n\
409 of SET2 are ignored. Only [:lower:] and [:upper:] are guaranteed to\n\
410 expand in ascending order; used in SET2 while translating, they may\n\
411 only be used in pairs to specify case conversion. -s uses SET1 if not\n\
412 translating nor deleting; else squeezing uses SET2 and occurs after\n\
413 translation or deletion.\n\
419 /* Return nonzero if the character C is a member of the
420 equivalence class containing the character EQUIV_CLASS. */
423 is_equiv_class_member (unsigned int equiv_class, unsigned int c)
425 return (equiv_class == c);
428 /* Return nonzero if the character C is a member of the
429 character class CHAR_CLASS. */
432 is_char_class_member (enum Char_class char_class, unsigned int c)
439 result = ISALNUM (c);
442 result = ISALPHA (c);
445 result = ISBLANK (c);
448 result = ISCNTRL (c);
451 result = ISDIGIT (c);
454 result = ISGRAPH (c);
457 result = ISLOWER (c);
460 result = ISPRINT (c);
463 result = ISPUNCT (c);
466 result = ISSPACE (c);
469 result = ISUPPER (c);
472 result = ISXDIGIT (c);
481 /* Perform the first pass over each range-spec argument S, converting all
482 \c and \ddd escapes to their one-byte representations. The conversion
483 is done in-place, so S must point to writable storage. If an invalid
484 quote sequence is found print an error message and return nonzero.
485 Otherwise set *LEN to the length of the resulting string and return
486 zero. The resulting array of characters may contain zero-bytes;
487 however, on input, S is assumed to be null-terminated, and hence
488 cannot contain actual (non-escaped) zero bytes. */
491 unquote (const unsigned char *s, struct E_string *es)
496 len = strlen ((char *) s);
498 es->s = (unsigned char *) xmalloc (len);
499 es->escaped = (int *) xmalloc (len * sizeof (es->escaped[0]));
500 for (i = 0; i < len; i++)
504 for (i = 0; s[i]; i++)
546 oct_digit = s[i + 2] - '0';
547 if (0 <= oct_digit && oct_digit <= 7)
549 c = 8 * c + oct_digit;
551 oct_digit = s[i + 2] - '0';
552 if (0 <= oct_digit && oct_digit <= 7)
554 if (8 * c + oct_digit < N_CHARS)
556 c = 8 * c + oct_digit;
559 else if (!posix_pedantic)
561 /* Any octal number larger than 0377 won't
562 fit in 8 bits. So we stop when adding the
563 next digit would put us over the limit and
564 give a warning about the ambiguity. POSIX
565 isn't clear on this, but one person has said
566 that in his interpretation, POSIX says tr
567 can't even give a warning. */
568 error (0, 0, _("warning: the ambiguous octal escape \
569 \\%c%c%c is being\n\tinterpreted as the 2-byte sequence \\0%c%c, `%c'"),
570 s[i], s[i + 1], s[i + 2],
571 s[i], s[i + 1], s[i + 2]);
577 error (0, 0, _("invalid backslash escape at end of string"));
583 error (0, 0, _("invalid backslash escape `\\%c'"), s[i + 1]);
604 /* If CLASS_STR is a valid character class string, return its index
605 in the global char_class_name array. Otherwise, return CC_NO_CLASS. */
607 static enum Char_class
608 look_up_char_class (const unsigned char *class_str, size_t len)
612 for (i = 0; i < N_CHAR_CLASSES; i++)
613 if (strncmp ((const char *) class_str, char_class_name[i], len) == 0
614 && strlen (char_class_name[i]) == len)
615 return (enum Char_class) i;
619 /* Return a newly allocated string with a printable version of C.
620 This function is used solely for formatting error messages. */
623 make_printable_char (unsigned int c)
625 char *buf = xmalloc (5);
627 assert (c < N_CHARS);
635 sprintf (buf, "\\%03o", c);
640 /* Return a newly allocated copy of S which is suitable for printing.
641 LEN is the number of characters in S. Most non-printing
642 (isprint) characters are represented by a backslash followed by
643 3 octal digits. However, the characters represented by \c escapes
644 where c is one of [abfnrtv] are represented by their 2-character \c
645 sequences. This function is used solely for printing error messages. */
648 make_printable_str (const unsigned char *s, size_t len)
650 /* Worst case is that every character expands to a backslash
651 followed by a 3-character octal escape sequence. */
652 char *printable_buf = xmalloc (4 * len + 1);
653 char *p = printable_buf;
656 for (i = 0; i < len; i++)
694 sprintf (buf, "\\%03o", s[i]);
700 return printable_buf;
703 /* Append a newly allocated structure representing a
704 character C to the specification list LIST. */
707 append_normal_char (struct Spec_list *list, unsigned int c)
709 struct List_element *new;
711 new = (struct List_element *) xmalloc (sizeof (struct List_element));
713 new->type = RE_NORMAL_CHAR;
714 new->u.normal_char = c;
716 list->tail->next = new;
720 /* Append a newly allocated structure representing the range
721 of characters from FIRST to LAST to the specification list LIST.
722 Return nonzero if LAST precedes FIRST in the collating sequence,
723 zero otherwise. This means that '[c-c]' is acceptable. */
726 append_range (struct Spec_list *list, unsigned int first, unsigned int last)
728 struct List_element *new;
730 if (ORD (first) > ORD (last))
732 char *tmp1 = make_printable_char (first);
733 char *tmp2 = make_printable_char (last);
736 _("range-endpoints of `%s-%s' are in reverse collating sequence order"),
742 new = (struct List_element *) xmalloc (sizeof (struct List_element));
744 new->type = RE_RANGE;
745 new->u.range.first_char = first;
746 new->u.range.last_char = last;
748 list->tail->next = new;
753 /* If CHAR_CLASS_STR is a valid character class string, append a
754 newly allocated structure representing that character class to the end
755 of the specification list LIST and return 0. If CHAR_CLASS_STR is not
756 a valid string return nonzero. */
759 append_char_class (struct Spec_list *list,
760 const unsigned char *char_class_str, size_t len)
762 enum Char_class char_class;
763 struct List_element *new;
765 char_class = look_up_char_class (char_class_str, len);
766 if (char_class == CC_NO_CLASS)
768 new = (struct List_element *) xmalloc (sizeof (struct List_element));
770 new->type = RE_CHAR_CLASS;
771 new->u.char_class = char_class;
773 list->tail->next = new;
778 /* Append a newly allocated structure representing a [c*n]
779 repeated character construct to the specification list LIST.
780 THE_CHAR is the single character to be repeated, and REPEAT_COUNT
781 is a non-negative repeat count. */
784 append_repeated_char (struct Spec_list *list, unsigned int the_char,
787 struct List_element *new;
789 new = (struct List_element *) xmalloc (sizeof (struct List_element));
791 new->type = RE_REPEATED_CHAR;
792 new->u.repeated_char.the_repeated_char = the_char;
793 new->u.repeated_char.repeat_count = repeat_count;
795 list->tail->next = new;
799 /* Given a string, EQUIV_CLASS_STR, from a [=str=] context and
800 the length of that string, LEN, if LEN is exactly one, append
801 a newly allocated structure representing the specified
802 equivalence class to the specification list, LIST and return zero.
803 If LEN is not 1, return nonzero. */
806 append_equiv_class (struct Spec_list *list,
807 const unsigned char *equiv_class_str, size_t len)
809 struct List_element *new;
813 new = (struct List_element *) xmalloc (sizeof (struct List_element));
815 new->type = RE_EQUIV_CLASS;
816 new->u.equiv_code = *equiv_class_str;
818 list->tail->next = new;
823 /* Return a newly allocated copy of the substring P[FIRST_IDX..LAST_IDX].
824 The returned string has length LAST_IDX - FIRST_IDX + 1, may contain
825 NUL bytes, and is *not* NUL-terminated. */
827 static unsigned char *
828 substr (const unsigned char *p, size_t first_idx, size_t last_idx)
833 assert (first_idx <= last_idx);
834 len = last_idx - first_idx + 1;
835 tmp = (unsigned char *) xmalloc (len);
837 assert (first_idx <= last_idx);
838 /* Use memcpy rather than strncpy because `p' may contain zero-bytes. */
839 memcpy (tmp, p + first_idx, len);
843 /* Search forward starting at START_IDX for the 2-char sequence
844 (PRE_BRACKET_CHAR,']') in the string P of length P_LEN. If such
845 a sequence is found, set *RESULT_IDX to the index of the first
846 character and return nonzero. Otherwise return zero. P may contain
850 find_closing_delim (const struct E_string *es, size_t start_idx,
851 unsigned int pre_bracket_char, size_t *result_idx)
855 for (i = start_idx; i < es->len - 1; i++)
856 if (es->s[i] == pre_bracket_char && es->s[i + 1] == ']'
857 && !es->escaped[i] && !es->escaped[i + 1])
865 /* Convert a string S with explicit length LEN, possibly
866 containing embedded zero bytes, to a long integer value.
867 If the string represents a negative value, a value larger
868 than LONG_MAX, or if all LEN characters do not represent a
869 valid integer, return nonzero and do not modify *VAL.
870 Otherwise, return zero and set *VAL to the converted value. */
873 non_neg_strtol (const unsigned char *s, size_t len, size_t *val)
876 unsigned long sum = 0;
883 else if (ISDIGIT (s[0]))
888 for (i = 0; i < len; i++)
899 if (sum > (LONG_MAX - c) / base)
901 sum = sum * base + c;
907 /* Parse the bracketed repeat-char syntax. If the P_LEN characters
908 beginning with P[ START_IDX ] comprise a valid [c*n] construct,
909 then set *CHAR_TO_REPEAT, *REPEAT_COUNT, and *CLOSING_BRACKET_IDX
910 and return zero. If the second character following
911 the opening bracket is not `*' or if no closing bracket can be
912 found, return -1. If a closing bracket is found and the
913 second char is `*', but the string between the `*' and `]' isn't
914 empty, an octal number, or a decimal number, print an error message
918 find_bracketed_repeat (const struct E_string *es, size_t start_idx,
919 unsigned int *char_to_repeat, size_t *repeat_count,
920 size_t *closing_bracket_idx)
924 assert (start_idx + 1 < es->len);
925 if (!ES_MATCH (es, start_idx + 1, '*'))
928 for (i = start_idx + 2; i < es->len; i++)
930 if (ES_MATCH (es, i, ']'))
932 const unsigned char *digit_str;
933 size_t digit_str_len = i - start_idx - 2;
935 *char_to_repeat = es->s[start_idx];
936 if (digit_str_len == 0)
938 /* We've matched [c*] -- no explicit repeat count. */
940 *closing_bracket_idx = i;
944 /* Here, we have found [c*s] where s should be a string
945 of octal or decimal digits. */
946 digit_str = &es->s[start_idx + 2];
947 if (non_neg_strtol (digit_str, digit_str_len, repeat_count)
948 || *repeat_count > BEGIN_STATE)
950 char *tmp = make_printable_str (digit_str, digit_str_len);
951 error (0, 0, _("invalid repeat count `%s' in [c*n] construct"),
956 *closing_bracket_idx = i;
960 return -1; /* No bracket found. */
963 /* Return nonzero if the string at ES->s[IDX] matches the regular
964 expression `\*[0-9]*\]', zero otherwise. To match, the `*' and
965 the `]' must not be escaped. */
968 star_digits_closebracket (const struct E_string *es, size_t idx)
972 if (!ES_MATCH (es, idx, '*'))
975 for (i = idx + 1; i < es->len; i++)
977 if (!ISDIGIT (es->s[i]))
979 if (ES_MATCH (es, i, ']'))
987 /* Convert string UNESACPED_STRING (which has been preprocessed to
988 convert backslash-escape sequences) of length LEN characters into
989 a linked list of the following 5 types of constructs:
990 - [:str:] Character class where `str' is one of the 12 valid strings.
991 - [=c=] Equivalence class where `c' is any single character.
992 - [c*n] Repeat the single character `c' `n' times. n may be omitted.
993 However, if `n' is present, it must be a non-negative octal or
995 - r-s Range of characters from `r' to `s'. The second endpoint must
996 not precede the first in the current collating sequence.
997 - c Any other character is interpreted as itself. */
1000 build_spec_list (const struct E_string *es, struct Spec_list *result)
1002 const unsigned char *p;
1007 /* The main for-loop below recognizes the 4 multi-character constructs.
1008 A character that matches (in its context) none of the multi-character
1009 constructs is classified as `normal'. Since all multi-character
1010 constructs have at least 3 characters, any strings of length 2 or
1011 less are composed solely of normal characters. Hence, the index of
1012 the outer for-loop runs only as far as LEN-2. */
1014 for (i = 0; i + 2 < es->len; /* empty */)
1016 if (ES_MATCH (es, i, '['))
1018 int matched_multi_char_construct;
1019 size_t closing_bracket_idx;
1020 unsigned int char_to_repeat;
1021 size_t repeat_count;
1024 matched_multi_char_construct = 1;
1025 if (ES_MATCH (es, i + 1, ':')
1026 || ES_MATCH (es, i + 1, '='))
1028 size_t closing_delim_idx;
1031 found = find_closing_delim (es, i + 2, p[i + 1],
1032 &closing_delim_idx);
1036 unsigned char *opnd_str = substr (p, i + 2,
1037 closing_delim_idx - 1);
1038 size_t opnd_str_len = closing_delim_idx - 1 - (i + 2) + 1;
1040 if (p[i + 1] == ':')
1042 parse_failed = append_char_class (result, opnd_str,
1045 /* FIXME: big comment. */
1048 if (star_digits_closebracket (es, i + 2))
1051 goto try_bracketed_repeat;
1055 char *tmp = make_printable_str (opnd_str,
1057 error (0, 0, _("invalid character class `%s'"),
1066 parse_failed = append_equiv_class (result, opnd_str,
1069 /* FIXME: big comment. */
1072 if (star_digits_closebracket (es, i + 2))
1075 goto try_bracketed_repeat;
1079 char *tmp = make_printable_str (opnd_str,
1082 _("%s: equivalence class operand must be a single character"),
1091 /* Return nonzero if append_*_class reports a problem. */
1095 i = closing_delim_idx + 2;
1098 /* Else fall through. This could be [:*] or [=*]. */
1101 try_bracketed_repeat:
1103 /* Determine whether this is a bracketed repeat range
1104 matching the RE \[.\*(dec_or_oct_number)?\]. */
1105 err = find_bracketed_repeat (es, i + 1, &char_to_repeat,
1107 &closing_bracket_idx);
1110 append_repeated_char (result, char_to_repeat, repeat_count);
1111 i = closing_bracket_idx + 1;
1115 matched_multi_char_construct = 0;
1119 /* Found a string that looked like [c*n] but the
1120 numeric part was invalid. */
1124 if (matched_multi_char_construct)
1127 /* We reach this point if P does not match [:str:], [=c=],
1128 [c*n], or [c*]. Now, see if P looks like a range `[-c'
1129 (from `[' to `c'). */
1132 /* Look ahead one char for ranges like a-z. */
1133 if (ES_MATCH (es, i + 1, '-'))
1135 if (append_range (result, p[i], p[i + 2]))
1141 append_normal_char (result, p[i]);
1146 /* Now handle the (2 or fewer) remaining characters p[i]..p[es->len - 1]. */
1147 for (; i < es->len; i++)
1148 append_normal_char (result, p[i]);
1153 /* Given a Spec_list S (with its saved state implicit in the values
1154 of its members `tail' and `state'), return the next single character
1155 in the expansion of S's constructs. If the last character of S was
1156 returned on the previous call or if S was empty, this function
1157 returns -1. For example, successive calls to get_next where S
1158 represents the spec-string 'a-d[y*3]' will return the sequence
1159 of values a, b, c, d, y, y, y, -1. Finally, if the construct from
1160 which the returned character comes is [:upper:] or [:lower:], the
1161 parameter CLASS is given a value to indicate which it was. Otherwise
1162 CLASS is set to UL_NONE. This value is used only when constructing
1163 the translation table to verify that any occurrences of upper and
1164 lower class constructs in the spec-strings appear in the same relative
1168 get_next (struct Spec_list *s, enum Upper_Lower_class *class)
1170 struct List_element *p;
1177 if (s->state == BEGIN_STATE)
1179 s->tail = s->head->next;
1180 s->state = NEW_ELEMENT;
1189 case RE_NORMAL_CHAR:
1190 return_val = p->u.normal_char;
1191 s->state = NEW_ELEMENT;
1196 if (s->state == NEW_ELEMENT)
1197 s->state = ORD (p->u.range.first_char);
1200 return_val = CHR (s->state);
1201 if (s->state == ORD (p->u.range.last_char))
1204 s->state = NEW_ELEMENT;
1209 if (s->state == NEW_ELEMENT)
1211 for (i = 0; i < N_CHARS; i++)
1212 if (is_char_class_member (p->u.char_class, i))
1214 assert (i < N_CHARS);
1217 assert (is_char_class_member (p->u.char_class, s->state));
1218 return_val = CHR (s->state);
1219 for (i = s->state + 1; i < N_CHARS; i++)
1220 if (is_char_class_member (p->u.char_class, i))
1227 s->state = NEW_ELEMENT;
1231 switch (p->u.char_class)
1246 case RE_EQUIV_CLASS:
1247 /* FIXME: this assumes that each character is alone in its own
1248 equivalence class (which appears to be correct for my
1249 LC_COLLATE. But I don't know of any function that allows
1250 one to determine a character's equivalence class. */
1252 return_val = p->u.equiv_code;
1253 s->state = NEW_ELEMENT;
1257 case RE_REPEATED_CHAR:
1258 /* Here, a repeat count of n == 0 means don't repeat at all. */
1259 if (p->u.repeated_char.repeat_count == 0)
1262 s->state = NEW_ELEMENT;
1263 return_val = get_next (s, class);
1267 if (s->state == NEW_ELEMENT)
1272 return_val = p->u.repeated_char.the_repeated_char;
1273 if (p->u.repeated_char.repeat_count > 0
1274 && s->state == p->u.repeated_char.repeat_count)
1277 s->state = NEW_ELEMENT;
1294 /* This is a minor kludge. This function is called from
1295 get_spec_stats to determine the cardinality of a set derived
1296 from a complemented string. It's a kludge in that some of the
1297 same operations are (duplicated) performed in set_initialize. */
1300 card_of_complement (struct Spec_list *s)
1303 int cardinality = N_CHARS;
1304 SET_TYPE in_set[N_CHARS];
1306 memset (in_set, 0, N_CHARS * sizeof (in_set[0]));
1307 s->state = BEGIN_STATE;
1308 while ((c = get_next (s, NULL)) != -1)
1314 /* Gather statistics about the spec-list S in preparation for the tests
1315 in validate that determine the consistency of the specs. This function
1316 is called at most twice; once for string1, and again for any string2.
1317 LEN_S1 < 0 indicates that this is the first call and that S represents
1318 string1. When LEN_S1 >= 0, it is the length of the expansion of the
1319 constructs in string1, and we can use its value to resolve any
1320 indefinite repeat construct in S (which represents string2). Hence,
1321 this function has the side-effect that it converts a valid [c*]
1322 construct in string2 to [c*n] where n is large enough (or 0) to give
1323 string2 the same length as string1. For example, with the command
1324 tr a-z 'A[\n*]Z' on the second call to get_spec_stats, LEN_S1 would
1325 be 26 and S (representing string2) would be converted to 'A[\n*24]Z'. */
1328 get_spec_stats (struct Spec_list *s)
1330 struct List_element *p;
1333 s->n_indefinite_repeats = 0;
1334 s->has_equiv_class = 0;
1335 s->has_restricted_char_class = 0;
1336 s->has_upper_or_lower = 0;
1337 for (p = s->head->next; p; p = p->next)
1342 case RE_NORMAL_CHAR:
1347 assert (p->u.range.last_char >= p->u.range.first_char);
1348 len += p->u.range.last_char - p->u.range.first_char + 1;
1352 for (i = 0; i < N_CHARS; i++)
1353 if (is_char_class_member (p->u.char_class, i))
1355 switch (p->u.char_class)
1359 s->has_upper_or_lower = 1;
1362 s->has_restricted_char_class = 1;
1367 case RE_EQUIV_CLASS:
1368 for (i = 0; i < N_CHARS; i++)
1369 if (is_equiv_class_member (p->u.equiv_code, i))
1371 s->has_equiv_class = 1;
1374 case RE_REPEATED_CHAR:
1375 if (p->u.repeated_char.repeat_count > 0)
1376 len += p->u.repeated_char.repeat_count;
1377 else if (p->u.repeated_char.repeat_count == 0)
1379 s->indefinite_repeat_element = p;
1380 ++(s->n_indefinite_repeats);
1394 get_s1_spec_stats (struct Spec_list *s1)
1396 get_spec_stats (s1);
1398 s1->length = card_of_complement (s1);
1402 get_s2_spec_stats (struct Spec_list *s2, size_t len_s1)
1404 get_spec_stats (s2);
1405 if (len_s1 >= s2->length && s2->n_indefinite_repeats == 1)
1407 s2->indefinite_repeat_element->u.repeated_char.repeat_count =
1408 len_s1 - s2->length;
1409 s2->length = len_s1;
1414 spec_init (struct Spec_list *spec_list)
1416 spec_list->head = spec_list->tail =
1417 (struct List_element *) xmalloc (sizeof (struct List_element));
1418 spec_list->head->next = NULL;
1421 /* This function makes two passes over the argument string S. The first
1422 one converts all \c and \ddd escapes to their one-byte representations.
1423 The second constructs a linked specification list, SPEC_LIST, of the
1424 characters and constructs that comprise the argument string. If either
1425 of these passes detects an error, this function returns nonzero. */
1428 parse_str (const unsigned char *s, struct Spec_list *spec_list)
1432 if (unquote (s, &es))
1434 if (build_spec_list (&es, spec_list))
1439 /* Given two specification lists, S1 and S2, and assuming that
1440 S1->length > S2->length, append a single [c*n] element to S2 where c
1441 is the last character in the expansion of S2 and n is the difference
1442 between the two lengths.
1443 Upon successful completion, S2->length is set to S1->length. The only
1444 way this function can fail to make S2 as long as S1 is when S2 has
1445 zero-length, since in that case, there is no last character to repeat.
1446 So S2->length is required to be at least 1.
1448 Providing this functionality allows the user to do some pretty
1449 non-BSD (and non-portable) things: For example, the command
1450 tr -cs '[:upper:]0-9' '[:lower:]'
1451 is almost guaranteed to give results that depend on your collating
1455 string2_extend (const struct Spec_list *s1, struct Spec_list *s2)
1457 struct List_element *p;
1461 assert (translating);
1462 assert (s1->length > s2->length);
1463 assert (s2->length > 0);
1468 case RE_NORMAL_CHAR:
1469 char_to_repeat = p->u.normal_char;
1472 char_to_repeat = p->u.range.last_char;
1475 for (i = N_CHARS; i >= 0; i--)
1476 if (is_char_class_member (p->u.char_class, i))
1479 char_to_repeat = CHR (i);
1482 case RE_REPEATED_CHAR:
1483 char_to_repeat = p->u.repeated_char.the_repeated_char;
1486 case RE_EQUIV_CLASS:
1487 /* This shouldn't happen, because validate exits with an error
1488 if it finds an equiv class in string2 when translating. */
1501 append_repeated_char (s2, char_to_repeat, s1->length - s2->length);
1502 s2->length = s1->length;
1505 /* Die with an error message if S1 and S2 describe strings that
1506 are not valid with the given command line switches.
1507 A side effect of this function is that if a valid [c*] or
1508 [c*0] construct appears in string2, it is converted to [c*n]
1509 with a value for n that makes s2->length == s1->length. By
1510 the same token, if the --truncate-set1 option is not
1511 given, S2 may be extended. */
1514 validate (struct Spec_list *s1, struct Spec_list *s2)
1516 get_s1_spec_stats (s1);
1517 if (s1->n_indefinite_repeats > 0)
1519 error (1, 0, _("the [c*] repeat construct may not appear in string1"));
1522 /* FIXME: it isn't clear from the POSIX spec that this is invalid,
1523 but in the spirit of the other restrictions put on translation
1524 with character classes, this seems a logical interpretation. */
1525 if (complement && s1->has_upper_or_lower)
1528 _("character classes may not be used when translating \
1529 and complementing"));
1534 get_s2_spec_stats (s2, s1->length);
1535 if (s2->has_restricted_char_class)
1538 _("when translating, the only character classes that may \
1539 appear in\n\tstring2 are `upper' and `lower'"));
1542 if (s2->n_indefinite_repeats > 1)
1545 _("only one [c*] repeat construct may appear in string2"));
1550 if (s2->has_equiv_class)
1553 _("[=c=] expressions may not appear in string2 \
1554 when translating"));
1557 if (s1->length > s2->length)
1561 /* string2 must be non-empty unless --truncate-set1 is
1562 given or string1 is empty. */
1564 if (s2->length == 0)
1566 _("when not truncating set1, string2 must be non-empty"));
1567 string2_extend (s1, s2);
1571 if (complement && s2->has_upper_or_lower)
1573 _("character classes may not be used when translating \
1574 and complementing"));
1577 /* Not translating. */
1579 if (s2->n_indefinite_repeats > 0)
1581 _("the [c*] construct may appear in string2 only \
1582 when translating"));
1587 /* Read buffers of SIZE bytes via the function READER (if READER is
1588 NULL, read from stdin) until EOF. When non-NULL, READER is either
1589 read_and_delete or read_and_xlate. After each buffer is read, it is
1590 processed and written to stdout. The buffers are processed so that
1591 multiple consecutive occurrences of the same character in the input
1592 stream are replaced by a single occurrence of that character if the
1593 character is in the squeeze set. */
1596 squeeze_filter (unsigned char *buf, long int size, PFI reader)
1598 unsigned int char_to_squeeze = NOT_A_CHAR;
1609 nr = safe_read (0, (char *) buf, size);
1611 nr = (*reader) (buf, size, NULL);
1614 error (1, errno, _("read error"));
1622 if (char_to_squeeze == NOT_A_CHAR)
1625 /* Here, by being a little tricky, we can get a significant
1626 performance increase in most cases when the input is
1627 reasonably large. Since tr will modify the input only
1628 if two consecutive (and identical) input characters are
1629 in the squeeze set, we can step by two through the data
1630 when searching for a character in the squeeze set. This
1631 means there may be a little more work in a few cases and
1632 perhaps twice as much work in the worst cases where most
1633 of the input is removed by squeezing repeats. But most
1634 uses of this functionality seem to remove less than 20-30%
1636 for (; i < nr && !in_squeeze_set[buf[i]]; i += 2)
1639 /* There is a special case when i == nr and we've just
1640 skipped a character (the last one in buf) that is in
1642 if (i == nr && in_squeeze_set[buf[i - 1]])
1646 out_len = nr - begin;
1649 char_to_squeeze = buf[i];
1650 /* We're about to output buf[begin..i]. */
1651 out_len = i - begin + 1;
1653 /* But since we stepped by 2 in the loop above,
1654 out_len may be one too large. */
1655 if (i > 0 && buf[i - 1] == char_to_squeeze)
1658 /* Advance i to the index of first character to be
1659 considered when looking for a char different from
1664 && fwrite ((char *) &buf[begin], 1, out_len, stdout) == 0)
1665 error (1, errno, _("write error"));
1668 if (char_to_squeeze != NOT_A_CHAR)
1670 /* Advance i to index of first char != char_to_squeeze
1671 (or to nr if all the rest of the characters in this
1672 buffer are the same as char_to_squeeze). */
1673 for (; i < nr && buf[i] == char_to_squeeze; i++)
1676 char_to_squeeze = NOT_A_CHAR;
1677 /* If (i >= nr) we've squeezed the last character in this buffer.
1678 So now we have to read a new buffer and continue comparing
1679 characters against char_to_squeeze. */
1684 /* Read buffers of SIZE bytes from stdin until one is found that
1685 contains at least one character not in the delete set. Store
1686 in the array BUF, all characters from that buffer that are not
1687 in the delete set, and return the number of characters saved
1691 read_and_delete (unsigned char *buf, long int size, PFI not_used)
1694 static int hit_eof = 0;
1696 assert (not_used == NULL);
1702 /* This enclosing do-while loop is to make sure that
1703 we don't return zero (indicating EOF) when we've
1704 just deleted all the characters in a buffer. */
1708 int nr = safe_read (0, (char *) buf, size);
1711 error (1, errno, _("read error"));
1718 /* This first loop may be a waste of code, but gives much
1719 better performance when no characters are deleted in
1720 the beginning of a buffer. It just avoids the copying
1721 of buf[i] into buf[n_saved] when it would be a NOP. */
1723 for (i = 0; i < nr && !in_delete_set[buf[i]]; i++)
1727 for (++i; i < nr; i++)
1728 if (!in_delete_set[buf[i]])
1729 buf[n_saved++] = buf[i];
1731 while (n_saved == 0);
1736 /* Read at most SIZE bytes from stdin into the array BUF. Then
1737 perform the in-place and one-to-one mapping specified by the global
1738 array `xlate'. Return the number of characters read, or 0 upon EOF. */
1741 read_and_xlate (unsigned char *buf, long int size, PFI not_used)
1743 long chars_read = 0;
1744 static int hit_eof = 0;
1747 assert (not_used == NULL);
1753 chars_read = safe_read (0, (char *) buf, size);
1755 error (1, errno, _("read error"));
1756 if (chars_read == 0)
1762 for (i = 0; i < chars_read; i++)
1763 buf[i] = xlate[buf[i]];
1768 /* Initialize a boolean membership set IN_SET with the character
1769 values obtained by traversing the linked list of constructs S
1770 using the function `get_next'. If COMPLEMENT_THIS_SET is
1771 nonzero the resulting set is complemented. */
1774 set_initialize (struct Spec_list *s, int complement_this_set, SET_TYPE *in_set)
1779 memset (in_set, 0, N_CHARS * sizeof (in_set[0]));
1780 s->state = BEGIN_STATE;
1781 while ((c = get_next (s, NULL)) != -1)
1783 if (complement_this_set)
1784 for (i = 0; i < N_CHARS; i++)
1785 in_set[i] = (!in_set[i]);
1789 main (int argc, char **argv)
1792 int non_option_args;
1793 struct Spec_list buf1, buf2;
1794 struct Spec_list *s1 = &buf1;
1795 struct Spec_list *s2 = &buf2;
1797 program_name = argv[0];
1798 setlocale (LC_ALL, "");
1799 bindtextdomain (PACKAGE, LOCALEDIR);
1800 textdomain (PACKAGE);
1802 while ((c = getopt_long (argc, argv, "cdst", long_options,
1819 squeeze_repeats = 1;
1834 printf ("tr - %s\n", PACKAGE_VERSION);
1841 posix_pedantic = (getenv ("POSIXLY_CORRECT") != NULL);
1843 non_option_args = argc - optind;
1844 translating = (non_option_args == 2 && !delete);
1846 /* Change this test if it is valid to give tr no options and
1847 no args at all. POSIX doesn't specifically say anything
1848 either way, but it looks like they implied it's invalid
1849 by omission. If you want to make tr do a slow imitation
1850 of `cat' use `tr a a'. */
1851 if (non_option_args > 2)
1853 error (0, 0, _("too many arguments"));
1857 if (!delete && !squeeze_repeats && non_option_args != 2)
1858 error (1, 0, _("two strings must be given when translating"));
1860 if (delete && squeeze_repeats && non_option_args != 2)
1861 error (1, 0, _("two strings must be given when both \
1862 deleting and squeezing repeats"));
1864 /* If --delete is given without --squeeze-repeats, then
1865 only one string argument may be specified. But POSIX
1866 says to ignore any string2 in this case, so if POSIXLY_CORRECT
1867 is set, pretend we never saw string2. But I think
1868 this deserves a fatal error, so that's the default. */
1869 if ((delete && !squeeze_repeats) && non_option_args != 1)
1871 if (posix_pedantic && non_option_args == 2)
1875 _("only one string may be given when deleting \
1876 without squeezing repeats"));
1879 if (squeeze_repeats && non_option_args == 0)
1881 _("at least one string must be given when squeezing repeats"));
1884 if (parse_str ((unsigned char *) argv[optind], s1))
1887 if (non_option_args == 2)
1890 if (parse_str ((unsigned char *) argv[optind + 1], s2))
1898 if (squeeze_repeats && non_option_args == 1)
1900 set_initialize (s1, complement, in_squeeze_set);
1901 squeeze_filter (io_buf, IO_BUF_SIZE, NULL);
1903 else if (delete && non_option_args == 1)
1907 set_initialize (s1, complement, in_delete_set);
1910 nr = read_and_delete (io_buf, IO_BUF_SIZE, NULL);
1911 if (nr > 0 && fwrite ((char *) io_buf, 1, nr, stdout) == 0)
1912 error (1, errno, _("write error"));
1916 else if (squeeze_repeats && delete && non_option_args == 2)
1918 set_initialize (s1, complement, in_delete_set);
1919 set_initialize (s2, 0, in_squeeze_set);
1920 squeeze_filter (io_buf, IO_BUF_SIZE, (PFI) read_and_delete);
1922 else if (translating)
1927 SET_TYPE *in_s1 = in_delete_set;
1929 set_initialize (s1, 0, in_s1);
1930 s2->state = BEGIN_STATE;
1931 for (i = 0; i < N_CHARS; i++)
1933 for (i = 0; i < N_CHARS; i++)
1937 int ch = get_next (s2, NULL);
1938 assert (ch != -1 || truncate_set1);
1941 /* This will happen when tr is invoked like e.g.
1942 tr -cs A-Za-z0-9 '\012'. */
1948 assert (get_next (s2, NULL) == -1 || truncate_set1);
1954 enum Upper_Lower_class class_s1;
1955 enum Upper_Lower_class class_s2;
1957 for (i = 0; i < N_CHARS; i++)
1959 s1->state = BEGIN_STATE;
1960 s2->state = BEGIN_STATE;
1963 c1 = get_next (s1, &class_s1);
1964 c2 = get_next (s2, &class_s2);
1965 if (!class_ok[(int) class_s1][(int) class_s2])
1967 _("misaligned or mismatched upper and/or lower classes"));
1968 /* The following should have been checked by validate... */
1973 assert (c1 == -1 || truncate_set1);
1975 if (squeeze_repeats)
1977 set_initialize (s2, 0, in_squeeze_set);
1978 squeeze_filter (io_buf, IO_BUF_SIZE, (PFI) read_and_xlate);
1986 chars_read = read_and_xlate (io_buf, IO_BUF_SIZE, NULL);
1988 && fwrite ((char *) io_buf, 1, chars_read, stdout) == 0)
1989 error (1, errno, _("write error"));
1991 while (chars_read > 0);
1995 if (fclose (stdout) == EOF)
1996 error (2, errno, _("write error"));
1999 error (2, errno, _("standard input"));