1 /* tr -- a filter to translate characters
2 Copyright (C) 91, 1995-1998, 1999 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 */
25 #include <sys/types.h>
30 #include "long-options.h"
31 #include "safe-read.h"
33 /* The official name of this program (e.g., no `g' prefix). */
34 #define PROGRAM_NAME "tr"
36 #define N_CHARS (UCHAR_MAX + 1)
38 /* A pointer to a function that returns an int. */
39 typedef int (*PFI) ();
41 /* Convert from character C to its index in the collating
42 sequence array. Just cast to an unsigned int to avoid
43 problems with sign-extension. */
44 #define ORD(c) (unsigned int)(c)
46 /* The inverse of ORD. */
47 #define CHR(i) (unsigned char)(i)
49 /* The value for Spec_list->state that indicates to
50 get_next that it should initialize the tail pointer.
51 Its value should be as large as possible to avoid conflict
52 a valid value for the state field -- and that may be as
53 large as any valid repeat_count. */
54 #define BEGIN_STATE (INT_MAX - 1)
56 /* The value for Spec_list->state that indicates to
57 get_next that the element pointed to by Spec_list->tail is
58 being considered for the first time on this pass through the
59 list -- it indicates that get_next should make any necessary
61 #define NEW_ELEMENT (BEGIN_STATE + 1)
63 /* A value distinct from any character that may have been stored in a
64 buffer as the result of a block-read in the function squeeze_filter. */
65 #define NOT_A_CHAR (unsigned int)(-1)
67 /* The following (but not CC_NO_CLASS) are indices into the array of
68 valid character class strings. */
71 CC_ALNUM = 0, CC_ALPHA = 1, CC_BLANK = 2, CC_CNTRL = 3,
72 CC_DIGIT = 4, CC_GRAPH = 5, CC_LOWER = 6, CC_PRINT = 7,
73 CC_PUNCT = 8, CC_SPACE = 9, CC_UPPER = 10, CC_XDIGIT = 11,
77 /* Character class to which a character (returned by get_next) belonged;
78 but it is set only if the construct from which the character was obtained
79 was one of the character classes [:upper:] or [:lower:]. The value
80 is used only when translating and then, only to make sure that upper
81 and lower class constructs have the same relative positions in string1
83 enum Upper_Lower_class
90 /* A shortcut to ensure that when constructing the translation array,
91 one of the values returned by paired calls to get_next (from s1 and s2)
92 is from [:upper:] and the other is from [:lower:], or neither is from
93 upper or lower. By default, GNU tr permits the identity mappings: from
94 [:upper:] to [:upper:] and [:lower:] to [:lower:]. But when
95 POSIXLY_CORRECT is set, those evoke diagnostics. This array is indexed
96 by values of type enum Upper_Lower_class. */
97 static int const class_ok[3][3] =
104 /* The type of a List_element. See build_spec_list for more details. */
105 enum Range_element_type
115 /* One construct in one of tr's argument strings.
116 For example, consider the POSIX version of the classic tr command:
117 tr -cs 'a-zA-Z_' '[\n*]'
118 String1 has 3 constructs, two of which are ranges (a-z and A-Z),
119 and a single normal character, `_'. String2 has one construct. */
122 enum Range_element_type type;
123 struct List_element *next;
129 unsigned int first_char;
130 unsigned int last_char;
133 enum Char_class char_class;
137 unsigned int the_repeated_char;
145 /* Each of tr's argument strings is parsed into a form that is easier
146 to work with: a linked list of constructs (struct List_element).
147 Each Spec_list structure also encapsulates various attributes of
148 the corresponding argument string. The attributes are used mainly
149 to verify that the strings are valid in the context of any options
150 specified (like -s, -d, or -c). The main exception is the member
151 `tail', which is first used to construct the list. After construction,
152 it is used by get_next to save its state when traversing the list.
153 The member `state' serves a similar function. */
156 /* Points to the head of the list of range elements.
157 The first struct is a dummy; its members are never used. */
158 struct List_element *head;
160 /* When appending, points to the last element. When traversing via
161 get_next(), points to the element to process next. Setting
162 Spec_list.state to the value BEGIN_STATE before calling get_next
163 signals get_next to initialize tail to point to head->next. */
164 struct List_element *tail;
166 /* Used to save state between calls to get_next(). */
169 /* Length, in the sense that length ('a-z[:digit:]123abc')
170 is 42 ( = 26 + 10 + 6). */
173 /* The number of [c*] and [c*0] constructs that appear in this spec. */
174 int n_indefinite_repeats;
176 /* If n_indefinite_repeats is nonzero, this points to the List_element
177 corresponding to the last [c*] or [c*0] construct encountered in
178 this spec. Otherwise it is undefined. */
179 struct List_element *indefinite_repeat_element;
181 /* Non-zero if this spec contains at least one equivalence
182 class construct e.g. [=c=]. */
185 /* Non-zero if this spec contains at least one character class
186 construct. E.g. [:digit:]. */
189 /* Non-zero if this spec contains at least one of the character class
190 constructs (all but upper and lower) that aren't allowed in s2. */
191 int has_restricted_char_class;
194 /* A representation for escaped string1 or string2. As a string is parsed,
195 any backslash-escaped characters (other than octal or \a, \b, \f, \n,
196 etc.) are marked as such in this structure by setting the corresponding
197 entry in the ESCAPED vector. */
205 /* Return nonzero if the Ith character of escaped string ES matches C
206 and is not escaped itself. */
207 #define ES_MATCH(ES, I, C) ((ES)->s[(I)] == (C) && !(ES)->escaped[(I)])
209 /* The name by which this program was run. */
212 /* When nonzero, each sequence in the input of a repeated character
213 (call it c) is replaced (in the output) by a single occurrence of c
214 for every c in the squeeze set. */
215 static int squeeze_repeats = 0;
217 /* When nonzero, removes characters in the delete set from input. */
218 static int delete = 0;
220 /* Use the complement of set1 in place of set1. */
221 static int complement = 0;
223 /* When nonzero, this flag causes GNU tr to provide strict
224 compliance with POSIX draft 1003.2.11.2. The POSIX spec
225 says that when -d is used without -s, string2 (if present)
226 must be ignored. Silently ignoring arguments is a bad idea.
227 The default GNU behavior is to give a usage message and exit.
228 Additionally, when this flag is nonzero, tr prints warnings
229 on stderr if it is being used in a manner that is not portable.
230 Applicable warnings are given by default, but are suppressed
231 if the environment variable `POSIXLY_CORRECT' is set, since
232 being POSIX conformant means we can't issue such messages.
233 Warnings on the following topics are suppressed when this
235 1. Ambiguous octal escapes. */
236 static int posix_pedantic;
238 /* When tr is performing translation and string1 is longer than string2,
239 POSIX says that the result is undefined. That gives the implementor
240 of a POSIX conforming version of tr two reasonable choices for the
241 semantics of this case.
243 * The BSD tr pads string2 to the length of string1 by
244 repeating the last character in string2.
246 * System V tr ignores characters in string1 that have no
247 corresponding character in string2. That is, string1 is effectively
248 truncated to the length of string2.
250 When nonzero, this flag causes GNU tr to imitate the behavior
251 of System V tr when translating with string1 longer than string2.
252 The default is to emulate BSD tr. This flag is ignored in modes where
253 no translation is performed. Emulating the System V tr
254 in this exceptional case causes the relatively common BSD idiom:
256 tr -cs A-Za-z0-9 '\012'
258 to break (it would convert only zero bytes, rather than all
259 non-alphanumerics, to newlines).
261 WARNING: This switch does not provide general BSD or System V
262 compatibility. For example, it doesn't disable the interpretation
263 of the POSIX constructs [:alpha:], [=c=], and [c*10], so if by
264 some unfortunate coincidence you use such constructs in scripts
265 expecting to use some other version of tr, the scripts will break. */
266 static int truncate_set1 = 0;
268 /* An alias for (!delete && non_option_args == 2).
269 It is set in main and used there and in validate(). */
270 static int translating;
276 #define IO_BUF_SIZE BUFSIZ
277 static unsigned char io_buf[IO_BUF_SIZE];
279 static char const *const char_class_name[] =
281 "alnum", "alpha", "blank", "cntrl", "digit", "graph",
282 "lower", "print", "punct", "space", "upper", "xdigit"
284 #define N_CHAR_CLASSES (sizeof(char_class_name) / sizeof(char_class_name[0]))
286 typedef char SET_TYPE;
288 /* Array of boolean values. A character `c' is a member of the
289 squeeze set if and only if in_squeeze_set[c] is true. The squeeze
290 set is defined by the last (possibly, the only) string argument
291 on the command line when the squeeze option is given. */
292 static SET_TYPE in_squeeze_set[N_CHARS];
294 /* Array of boolean values. A character `c' is a member of the
295 delete set if and only if in_delete_set[c] is true. The delete
296 set is defined by the first (or only) string argument on the
297 command line when the delete option is given. */
298 static SET_TYPE in_delete_set[N_CHARS];
300 /* Array of character values defining the translation (if any) that
301 tr is to perform. Translation is performed only when there are
302 two specification strings and the delete switch is not given. */
303 static char xlate[N_CHARS];
305 static struct option const long_options[] =
307 {"complement", no_argument, NULL, 'c'},
308 {"delete", no_argument, NULL, 'd'},
309 {"squeeze-repeats", no_argument, NULL, 's'},
310 {"truncate-set1", no_argument, NULL, 't'},
318 fprintf (stderr, _("Try `%s --help' for more information.\n"),
323 Usage: %s [OPTION]... SET1 [SET2]\n\
327 Translate, squeeze, and/or delete characters from standard input,\n\
328 writing to standard output.\n\
330 -c, --complement first complement SET1\n\
331 -d, --delete delete characters in SET1, do not translate\n\
332 -s, --squeeze-repeats replace sequence of characters with one\n\
333 -t, --truncate-set1 first truncate SET1 to length of SET2\n\
334 --help display this help and exit\n\
335 --version output version information and exit\n\
339 SETs are specified as strings of characters. Most represent themselves.\n\
340 Interpreted sequences are:\n\
342 \\NNN character with octal value NNN (1 to 3 octal digits)\n\
349 \\t horizontal tab\n\
351 CHAR1-CHAR2 all characters from CHAR1 to CHAR2 in ascending order\n\
352 [CHAR1-CHAR2] same as CHAR1-CHAR2, if both SET1 and SET2 use this\n\
353 [CHAR*] in SET2, copies of CHAR until length of SET1\n\
354 [CHAR*REPEAT] REPEAT copies of CHAR, REPEAT octal if starting with 0\n\
355 [:alnum:] all letters and digits\n\
356 [:alpha:] all letters\n\
357 [:blank:] all horizontal whitespace\n\
358 [:cntrl:] all control characters\n\
359 [:digit:] all digits\n\
360 [:graph:] all printable characters, not including space\n\
361 [:lower:] all lower case letters\n\
362 [:print:] all printable characters, including space\n\
363 [:punct:] all punctuation characters\n\
364 [:space:] all horizontal or vertical whitespace\n\
365 [:upper:] all upper case letters\n\
366 [:xdigit:] all hexadecimal digits\n\
367 [=CHAR=] all characters which are equivalent to CHAR\n\
371 Translation occurs if -d is not given and both SET1 and SET2 appear.\n\
372 -t may be used only when translating. SET2 is extended to length of\n\
373 SET1 by repeating its last character as necessary. Excess characters\n\
374 of SET2 are ignored. Only [:lower:] and [:upper:] are guaranteed to\n\
375 expand in ascending order; used in SET2 while translating, they may\n\
376 only be used in pairs to specify case conversion. -s uses SET1 if not\n\
377 translating nor deleting; else squeezing uses SET2 and occurs after\n\
378 translation or deletion.\n\
380 puts (_("\nReport bugs to <bug-textutils@gnu.org>."));
382 exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
385 /* Return nonzero if the character C is a member of the
386 equivalence class containing the character EQUIV_CLASS. */
389 is_equiv_class_member (unsigned int equiv_class, unsigned int c)
391 return (equiv_class == c);
394 /* Return nonzero if the character C is a member of the
395 character class CHAR_CLASS. */
398 is_char_class_member (enum Char_class char_class, unsigned int c)
405 result = ISALNUM (c);
408 result = ISALPHA (c);
411 result = ISBLANK (c);
414 result = ISCNTRL (c);
417 result = ISDIGIT_LOCALE (c);
420 result = ISGRAPH (c);
423 result = ISLOWER (c);
426 result = ISPRINT (c);
429 result = ISPUNCT (c);
432 result = ISSPACE (c);
435 result = ISUPPER (c);
438 result = ISXDIGIT (c);
448 es_free (struct E_string *es)
454 /* Perform the first pass over each range-spec argument S, converting all
455 \c and \ddd escapes to their one-byte representations. The conversion
456 is done in-place, so S must point to writable storage. If an invalid
457 quote sequence is found print an error message and return nonzero.
458 Otherwise set *LEN to the length of the resulting string and return
459 zero. The resulting array of characters may contain zero-bytes;
460 however, on input, S is assumed to be null-terminated, and hence
461 cannot contain actual (non-escaped) zero bytes. */
464 unquote (const unsigned char *s, struct E_string *es)
469 len = strlen ((char *) s);
471 es->s = (unsigned char *) xmalloc (len);
472 es->escaped = (int *) xmalloc (len * sizeof (es->escaped[0]));
473 for (i = 0; i < len; i++)
477 for (i = 0; s[i]; i++)
519 oct_digit = s[i + 2] - '0';
520 if (0 <= oct_digit && oct_digit <= 7)
522 c = 8 * c + oct_digit;
524 oct_digit = s[i + 2] - '0';
525 if (0 <= oct_digit && oct_digit <= 7)
527 if (8 * c + oct_digit < N_CHARS)
529 c = 8 * c + oct_digit;
532 else if (!posix_pedantic)
534 /* Any octal number larger than 0377 won't
535 fit in 8 bits. So we stop when adding the
536 next digit would put us over the limit and
537 give a warning about the ambiguity. POSIX
538 isn't clear on this, but one person has said
539 that in his interpretation, POSIX says tr
540 can't even give a warning. */
541 error (0, 0, _("warning: the ambiguous octal escape \
542 \\%c%c%c is being\n\tinterpreted as the 2-byte sequence \\0%c%c, `%c'"),
543 s[i], s[i + 1], s[i + 2],
544 s[i], s[i + 1], s[i + 2]);
550 error (0, 0, _("invalid backslash escape at end of string"));
556 error (0, 0, _("invalid backslash escape `\\%c'"), s[i + 1]);
577 /* If CLASS_STR is a valid character class string, return its index
578 in the global char_class_name array. Otherwise, return CC_NO_CLASS. */
580 static enum Char_class
581 look_up_char_class (const unsigned char *class_str, size_t len)
585 for (i = 0; i < N_CHAR_CLASSES; i++)
586 if (strncmp ((const char *) class_str, char_class_name[i], len) == 0
587 && strlen (char_class_name[i]) == len)
588 return (enum Char_class) i;
592 /* Return a newly allocated string with a printable version of C.
593 This function is used solely for formatting error messages. */
596 make_printable_char (unsigned int c)
598 char *buf = xmalloc (5);
600 assert (c < N_CHARS);
608 sprintf (buf, "\\%03o", c);
613 /* Return a newly allocated copy of S which is suitable for printing.
614 LEN is the number of characters in S. Most non-printing
615 (isprint) characters are represented by a backslash followed by
616 3 octal digits. However, the characters represented by \c escapes
617 where c is one of [abfnrtv] are represented by their 2-character \c
618 sequences. This function is used solely for printing error messages. */
621 make_printable_str (const unsigned char *s, size_t len)
623 /* Worst case is that every character expands to a backslash
624 followed by a 3-character octal escape sequence. */
625 char *printable_buf = xmalloc (4 * len + 1);
626 char *p = printable_buf;
629 for (i = 0; i < len; i++)
667 sprintf (buf, "\\%03o", s[i]);
673 return printable_buf;
676 /* Append a newly allocated structure representing a
677 character C to the specification list LIST. */
680 append_normal_char (struct Spec_list *list, unsigned int c)
682 struct List_element *new;
684 new = (struct List_element *) xmalloc (sizeof (struct List_element));
686 new->type = RE_NORMAL_CHAR;
687 new->u.normal_char = c;
689 list->tail->next = new;
693 /* Append a newly allocated structure representing the range
694 of characters from FIRST to LAST to the specification list LIST.
695 Return nonzero if LAST precedes FIRST in the collating sequence,
696 zero otherwise. This means that '[c-c]' is acceptable. */
699 append_range (struct Spec_list *list, unsigned int first, unsigned int last)
701 struct List_element *new;
703 if (ORD (first) > ORD (last))
705 char *tmp1 = make_printable_char (first);
706 char *tmp2 = make_printable_char (last);
709 _("range-endpoints of `%s-%s' are in reverse collating sequence order"),
715 new = (struct List_element *) xmalloc (sizeof (struct List_element));
717 new->type = RE_RANGE;
718 new->u.range.first_char = first;
719 new->u.range.last_char = last;
721 list->tail->next = new;
726 /* If CHAR_CLASS_STR is a valid character class string, append a
727 newly allocated structure representing that character class to the end
728 of the specification list LIST and return 0. If CHAR_CLASS_STR is not
729 a valid string return nonzero. */
732 append_char_class (struct Spec_list *list,
733 const unsigned char *char_class_str, size_t len)
735 enum Char_class char_class;
736 struct List_element *new;
738 char_class = look_up_char_class (char_class_str, len);
739 if (char_class == CC_NO_CLASS)
741 new = (struct List_element *) xmalloc (sizeof (struct List_element));
743 new->type = RE_CHAR_CLASS;
744 new->u.char_class = char_class;
746 list->tail->next = new;
751 /* Append a newly allocated structure representing a [c*n]
752 repeated character construct to the specification list LIST.
753 THE_CHAR is the single character to be repeated, and REPEAT_COUNT
754 is a non-negative repeat count. */
757 append_repeated_char (struct Spec_list *list, unsigned int the_char,
760 struct List_element *new;
762 new = (struct List_element *) xmalloc (sizeof (struct List_element));
764 new->type = RE_REPEATED_CHAR;
765 new->u.repeated_char.the_repeated_char = the_char;
766 new->u.repeated_char.repeat_count = repeat_count;
768 list->tail->next = new;
772 /* Given a string, EQUIV_CLASS_STR, from a [=str=] context and
773 the length of that string, LEN, if LEN is exactly one, append
774 a newly allocated structure representing the specified
775 equivalence class to the specification list, LIST and return zero.
776 If LEN is not 1, return nonzero. */
779 append_equiv_class (struct Spec_list *list,
780 const unsigned char *equiv_class_str, size_t len)
782 struct List_element *new;
786 new = (struct List_element *) xmalloc (sizeof (struct List_element));
788 new->type = RE_EQUIV_CLASS;
789 new->u.equiv_code = *equiv_class_str;
791 list->tail->next = new;
796 /* Return a newly allocated copy of the substring P[FIRST_IDX..LAST_IDX].
797 The returned string has length LAST_IDX - FIRST_IDX + 1, may contain
798 NUL bytes, and is *not* NUL-terminated. */
800 static unsigned char *
801 substr (const unsigned char *p, size_t first_idx, size_t last_idx)
806 assert (first_idx <= last_idx);
807 len = last_idx - first_idx + 1;
808 tmp = (unsigned char *) xmalloc (len);
810 assert (first_idx <= last_idx);
811 /* Use memcpy rather than strncpy because `p' may contain zero-bytes. */
812 memcpy (tmp, p + first_idx, len);
816 /* Search forward starting at START_IDX for the 2-char sequence
817 (PRE_BRACKET_CHAR,']') in the string P of length P_LEN. If such
818 a sequence is found, set *RESULT_IDX to the index of the first
819 character and return nonzero. Otherwise return zero. P may contain
823 find_closing_delim (const struct E_string *es, size_t start_idx,
824 unsigned int pre_bracket_char, size_t *result_idx)
828 for (i = start_idx; i < es->len - 1; i++)
829 if (es->s[i] == pre_bracket_char && es->s[i + 1] == ']'
830 && !es->escaped[i] && !es->escaped[i + 1])
838 /* Convert a string S with explicit length LEN, possibly
839 containing embedded zero bytes, to a long integer value.
840 If the string represents a negative value, a value larger
841 than LONG_MAX, or if all LEN characters do not represent a
842 valid integer, return nonzero and do not modify *VAL.
843 Otherwise, return zero and set *VAL to the converted value. */
846 non_neg_strtol (const unsigned char *s, size_t len, size_t *val)
849 unsigned long sum = 0;
856 else if (ISDIGIT (s[0]))
861 for (i = 0; i < len; i++)
872 if (sum > (LONG_MAX - c) / base)
874 sum = sum * base + c;
880 /* Parse the bracketed repeat-char syntax. If the P_LEN characters
881 beginning with P[ START_IDX ] comprise a valid [c*n] construct,
882 then set *CHAR_TO_REPEAT, *REPEAT_COUNT, and *CLOSING_BRACKET_IDX
883 and return zero. If the second character following
884 the opening bracket is not `*' or if no closing bracket can be
885 found, return -1. If a closing bracket is found and the
886 second char is `*', but the string between the `*' and `]' isn't
887 empty, an octal number, or a decimal number, print an error message
891 find_bracketed_repeat (const struct E_string *es, size_t start_idx,
892 unsigned int *char_to_repeat, size_t *repeat_count,
893 size_t *closing_bracket_idx)
897 assert (start_idx + 1 < es->len);
898 if (!ES_MATCH (es, start_idx + 1, '*'))
901 for (i = start_idx + 2; i < es->len; i++)
903 if (ES_MATCH (es, i, ']'))
905 const unsigned char *digit_str;
906 size_t digit_str_len = i - start_idx - 2;
908 *char_to_repeat = es->s[start_idx];
909 if (digit_str_len == 0)
911 /* We've matched [c*] -- no explicit repeat count. */
913 *closing_bracket_idx = i;
917 /* Here, we have found [c*s] where s should be a string
918 of octal or decimal digits. */
919 digit_str = &es->s[start_idx + 2];
920 if (non_neg_strtol (digit_str, digit_str_len, repeat_count)
921 || *repeat_count > BEGIN_STATE)
923 char *tmp = make_printable_str (digit_str, digit_str_len);
924 error (0, 0, _("invalid repeat count `%s' in [c*n] construct"),
929 *closing_bracket_idx = i;
933 return -1; /* No bracket found. */
936 /* Return nonzero if the string at ES->s[IDX] matches the regular
937 expression `\*[0-9]*\]', zero otherwise. To match, the `*' and
938 the `]' must not be escaped. */
941 star_digits_closebracket (const struct E_string *es, size_t idx)
945 if (!ES_MATCH (es, idx, '*'))
948 for (i = idx + 1; i < es->len; i++)
950 if (!ISDIGIT (es->s[i]))
952 if (ES_MATCH (es, i, ']'))
960 /* Convert string UNESACPED_STRING (which has been preprocessed to
961 convert backslash-escape sequences) of length LEN characters into
962 a linked list of the following 5 types of constructs:
963 - [:str:] Character class where `str' is one of the 12 valid strings.
964 - [=c=] Equivalence class where `c' is any single character.
965 - [c*n] Repeat the single character `c' `n' times. n may be omitted.
966 However, if `n' is present, it must be a non-negative octal or
968 - r-s Range of characters from `r' to `s'. The second endpoint must
969 not precede the first in the current collating sequence.
970 - c Any other character is interpreted as itself. */
973 build_spec_list (const struct E_string *es, struct Spec_list *result)
975 const unsigned char *p;
980 /* The main for-loop below recognizes the 4 multi-character constructs.
981 A character that matches (in its context) none of the multi-character
982 constructs is classified as `normal'. Since all multi-character
983 constructs have at least 3 characters, any strings of length 2 or
984 less are composed solely of normal characters. Hence, the index of
985 the outer for-loop runs only as far as LEN-2. */
987 for (i = 0; i + 2 < es->len; /* empty */)
989 if (ES_MATCH (es, i, '['))
991 int matched_multi_char_construct;
992 size_t closing_bracket_idx;
993 unsigned int char_to_repeat;
997 matched_multi_char_construct = 1;
998 if (ES_MATCH (es, i + 1, ':')
999 || ES_MATCH (es, i + 1, '='))
1001 size_t closing_delim_idx;
1004 found = find_closing_delim (es, i + 2, p[i + 1],
1005 &closing_delim_idx);
1009 unsigned char *opnd_str = substr (p, i + 2,
1010 closing_delim_idx - 1);
1011 size_t opnd_str_len = closing_delim_idx - 1 - (i + 2) + 1;
1013 if (p[i + 1] == ':')
1015 parse_failed = append_char_class (result, opnd_str,
1018 /* FIXME: big comment. */
1021 if (star_digits_closebracket (es, i + 2))
1024 goto try_bracketed_repeat;
1028 char *tmp = make_printable_str (opnd_str,
1030 error (0, 0, _("invalid character class `%s'"),
1039 parse_failed = append_equiv_class (result, opnd_str,
1042 /* FIXME: big comment. */
1045 if (star_digits_closebracket (es, i + 2))
1048 goto try_bracketed_repeat;
1052 char *tmp = make_printable_str (opnd_str,
1055 _("%s: equivalence class operand must be a single character"),
1064 /* Return nonzero if append_*_class reports a problem. */
1068 i = closing_delim_idx + 2;
1071 /* Else fall through. This could be [:*] or [=*]. */
1074 try_bracketed_repeat:
1076 /* Determine whether this is a bracketed repeat range
1077 matching the RE \[.\*(dec_or_oct_number)?\]. */
1078 err = find_bracketed_repeat (es, i + 1, &char_to_repeat,
1080 &closing_bracket_idx);
1083 append_repeated_char (result, char_to_repeat, repeat_count);
1084 i = closing_bracket_idx + 1;
1088 matched_multi_char_construct = 0;
1092 /* Found a string that looked like [c*n] but the
1093 numeric part was invalid. */
1097 if (matched_multi_char_construct)
1100 /* We reach this point if P does not match [:str:], [=c=],
1101 [c*n], or [c*]. Now, see if P looks like a range `[-c'
1102 (from `[' to `c'). */
1105 /* Look ahead one char for ranges like a-z. */
1106 if (ES_MATCH (es, i + 1, '-'))
1108 if (append_range (result, p[i], p[i + 2]))
1114 append_normal_char (result, p[i]);
1119 /* Now handle the (2 or fewer) remaining characters p[i]..p[es->len - 1]. */
1120 for (; i < es->len; i++)
1121 append_normal_char (result, p[i]);
1126 /* Given a Spec_list S (with its saved state implicit in the values
1127 of its members `tail' and `state'), return the next single character
1128 in the expansion of S's constructs. If the last character of S was
1129 returned on the previous call or if S was empty, this function
1130 returns -1. For example, successive calls to get_next where S
1131 represents the spec-string 'a-d[y*3]' will return the sequence
1132 of values a, b, c, d, y, y, y, -1. Finally, if the construct from
1133 which the returned character comes is [:upper:] or [:lower:], the
1134 parameter CLASS is given a value to indicate which it was. Otherwise
1135 CLASS is set to UL_NONE. This value is used only when constructing
1136 the translation table to verify that any occurrences of upper and
1137 lower class constructs in the spec-strings appear in the same relative
1141 get_next (struct Spec_list *s, enum Upper_Lower_class *class)
1143 struct List_element *p;
1150 if (s->state == BEGIN_STATE)
1152 s->tail = s->head->next;
1153 s->state = NEW_ELEMENT;
1162 case RE_NORMAL_CHAR:
1163 return_val = p->u.normal_char;
1164 s->state = NEW_ELEMENT;
1169 if (s->state == NEW_ELEMENT)
1170 s->state = ORD (p->u.range.first_char);
1173 return_val = CHR (s->state);
1174 if (s->state == ORD (p->u.range.last_char))
1177 s->state = NEW_ELEMENT;
1185 switch (p->u.char_class)
1203 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 case RE_EQUIV_CLASS:
1232 /* FIXME: this assumes that each character is alone in its own
1233 equivalence class (which appears to be correct for my
1234 LC_COLLATE. But I don't know of any function that allows
1235 one to determine a character's equivalence class. */
1237 return_val = p->u.equiv_code;
1238 s->state = NEW_ELEMENT;
1242 case RE_REPEATED_CHAR:
1243 /* Here, a repeat count of n == 0 means don't repeat at all. */
1244 if (p->u.repeated_char.repeat_count == 0)
1247 s->state = NEW_ELEMENT;
1248 return_val = get_next (s, class);
1252 if (s->state == NEW_ELEMENT)
1257 return_val = p->u.repeated_char.the_repeated_char;
1258 if (p->u.repeated_char.repeat_count > 0
1259 && s->state == p->u.repeated_char.repeat_count)
1262 s->state = NEW_ELEMENT;
1279 /* This is a minor kludge. This function is called from
1280 get_spec_stats to determine the cardinality of a set derived
1281 from a complemented string. It's a kludge in that some of the
1282 same operations are (duplicated) performed in set_initialize. */
1285 card_of_complement (struct Spec_list *s)
1288 int cardinality = N_CHARS;
1289 SET_TYPE in_set[N_CHARS];
1291 memset (in_set, 0, N_CHARS * sizeof (in_set[0]));
1292 s->state = BEGIN_STATE;
1293 while ((c = get_next (s, NULL)) != -1)
1299 /* Gather statistics about the spec-list S in preparation for the tests
1300 in validate that determine the consistency of the specs. This function
1301 is called at most twice; once for string1, and again for any string2.
1302 LEN_S1 < 0 indicates that this is the first call and that S represents
1303 string1. When LEN_S1 >= 0, it is the length of the expansion of the
1304 constructs in string1, and we can use its value to resolve any
1305 indefinite repeat construct in S (which represents string2). Hence,
1306 this function has the side-effect that it converts a valid [c*]
1307 construct in string2 to [c*n] where n is large enough (or 0) to give
1308 string2 the same length as string1. For example, with the command
1309 tr a-z 'A[\n*]Z' on the second call to get_spec_stats, LEN_S1 would
1310 be 26 and S (representing string2) would be converted to 'A[\n*24]Z'. */
1313 get_spec_stats (struct Spec_list *s)
1315 struct List_element *p;
1318 s->n_indefinite_repeats = 0;
1319 s->has_equiv_class = 0;
1320 s->has_restricted_char_class = 0;
1321 s->has_char_class = 0;
1322 for (p = s->head->next; p; p = p->next)
1327 case RE_NORMAL_CHAR:
1332 assert (p->u.range.last_char >= p->u.range.first_char);
1333 len += p->u.range.last_char - p->u.range.first_char + 1;
1337 s->has_char_class = 1;
1338 for (i = 0; i < N_CHARS; i++)
1339 if (is_char_class_member (p->u.char_class, i))
1341 switch (p->u.char_class)
1347 s->has_restricted_char_class = 1;
1352 case RE_EQUIV_CLASS:
1353 for (i = 0; i < N_CHARS; i++)
1354 if (is_equiv_class_member (p->u.equiv_code, i))
1356 s->has_equiv_class = 1;
1359 case RE_REPEATED_CHAR:
1360 if (p->u.repeated_char.repeat_count > 0)
1361 len += p->u.repeated_char.repeat_count;
1362 else if (p->u.repeated_char.repeat_count == 0)
1364 s->indefinite_repeat_element = p;
1365 ++(s->n_indefinite_repeats);
1379 get_s1_spec_stats (struct Spec_list *s1)
1381 get_spec_stats (s1);
1383 s1->length = card_of_complement (s1);
1387 get_s2_spec_stats (struct Spec_list *s2, size_t len_s1)
1389 get_spec_stats (s2);
1390 if (len_s1 >= s2->length && s2->n_indefinite_repeats == 1)
1392 s2->indefinite_repeat_element->u.repeated_char.repeat_count =
1393 len_s1 - s2->length;
1394 s2->length = len_s1;
1399 spec_init (struct Spec_list *spec_list)
1401 spec_list->head = spec_list->tail =
1402 (struct List_element *) xmalloc (sizeof (struct List_element));
1403 spec_list->head->next = NULL;
1406 /* This function makes two passes over the argument string S. The first
1407 one converts all \c and \ddd escapes to their one-byte representations.
1408 The second constructs a linked specification list, SPEC_LIST, of the
1409 characters and constructs that comprise the argument string. If either
1410 of these passes detects an error, this function returns nonzero. */
1413 parse_str (const unsigned char *s, struct Spec_list *spec_list)
1418 fail = unquote (s, &es);
1420 fail = build_spec_list (&es, spec_list);
1425 /* Given two specification lists, S1 and S2, and assuming that
1426 S1->length > S2->length, append a single [c*n] element to S2 where c
1427 is the last character in the expansion of S2 and n is the difference
1428 between the two lengths.
1429 Upon successful completion, S2->length is set to S1->length. The only
1430 way this function can fail to make S2 as long as S1 is when S2 has
1431 zero-length, since in that case, there is no last character to repeat.
1432 So S2->length is required to be at least 1.
1434 Providing this functionality allows the user to do some pretty
1435 non-BSD (and non-portable) things: For example, the command
1436 tr -cs '[:upper:]0-9' '[:lower:]'
1437 is almost guaranteed to give results that depend on your collating
1441 string2_extend (const struct Spec_list *s1, struct Spec_list *s2)
1443 struct List_element *p;
1447 assert (translating);
1448 assert (s1->length > s2->length);
1449 assert (s2->length > 0);
1454 case RE_NORMAL_CHAR:
1455 char_to_repeat = p->u.normal_char;
1458 char_to_repeat = p->u.range.last_char;
1461 for (i = N_CHARS; i >= 0; i--)
1462 if (is_char_class_member (p->u.char_class, i))
1465 char_to_repeat = CHR (i);
1468 case RE_REPEATED_CHAR:
1469 char_to_repeat = p->u.repeated_char.the_repeated_char;
1472 case RE_EQUIV_CLASS:
1473 /* This shouldn't happen, because validate exits with an error
1474 if it finds an equiv class in string2 when translating. */
1487 append_repeated_char (s2, char_to_repeat, s1->length - s2->length);
1488 s2->length = s1->length;
1491 /* Return non-zero if S is a non-empty list in which exactly one
1492 character (but potentially, many instances of it) appears.
1493 E.g. [X*] or xxxxxxxx. */
1496 homogeneous_spec_list (struct Spec_list *s)
1500 s->state = BEGIN_STATE;
1502 if ((b = get_next (s, NULL)) == -1)
1505 while ((c = get_next (s, NULL)) != -1)
1512 /* Die with an error message if S1 and S2 describe strings that
1513 are not valid with the given command line switches.
1514 A side effect of this function is that if a valid [c*] or
1515 [c*0] construct appears in string2, it is converted to [c*n]
1516 with a value for n that makes s2->length == s1->length. By
1517 the same token, if the --truncate-set1 option is not
1518 given, S2 may be extended. */
1521 validate (struct Spec_list *s1, struct Spec_list *s2)
1523 get_s1_spec_stats (s1);
1524 if (s1->n_indefinite_repeats > 0)
1526 error (EXIT_FAILURE, 0,
1527 _("the [c*] repeat construct may not appear in string1"));
1532 get_s2_spec_stats (s2, s1->length);
1534 if (s2->n_indefinite_repeats > 1)
1536 error (EXIT_FAILURE, 0,
1537 _("only one [c*] repeat construct may appear in string2"));
1542 if (s2->has_equiv_class)
1544 error (EXIT_FAILURE, 0,
1545 _("[=c=] expressions may not appear in string2 \
1546 when translating"));
1549 if (s1->length > s2->length)
1553 /* string2 must be non-empty unless --truncate-set1 is
1554 given or string1 is empty. */
1556 if (s2->length == 0)
1557 error (EXIT_FAILURE, 0,
1558 _("when not truncating set1, string2 must be non-empty"));
1559 string2_extend (s1, s2);
1563 if (complement && s1->has_char_class
1564 && ! (s2->length == s1->length && homogeneous_spec_list (s2)))
1566 error (EXIT_FAILURE, 0,
1567 _("when translating with complemented character classes,\
1568 \nstring2 must map all characters in the domain to one"));
1571 if (s2->has_restricted_char_class)
1573 error (EXIT_FAILURE, 0,
1574 _("when translating, the only character classes that may \
1575 appear in\nstring2 are `upper' and `lower'"));
1579 /* Not translating. */
1581 if (s2->n_indefinite_repeats > 0)
1582 error (EXIT_FAILURE, 0,
1583 _("the [c*] construct may appear in string2 only \
1584 when translating"));
1589 /* Read buffers of SIZE bytes via the function READER (if READER is
1590 NULL, read from stdin) until EOF. When non-NULL, READER is either
1591 read_and_delete or read_and_xlate. After each buffer is read, it is
1592 processed and written to stdout. The buffers are processed so that
1593 multiple consecutive occurrences of the same character in the input
1594 stream are replaced by a single occurrence of that character if the
1595 character is in the squeeze set. */
1598 squeeze_filter (unsigned char *buf, long int size, PFI reader)
1600 unsigned int char_to_squeeze = NOT_A_CHAR;
1611 nr = safe_read (0, (char *) buf, size);
1613 nr = (*reader) (buf, size, NULL);
1616 error (EXIT_FAILURE, errno, _("read error"));
1624 if (char_to_squeeze == NOT_A_CHAR)
1627 /* Here, by being a little tricky, we can get a significant
1628 performance increase in most cases when the input is
1629 reasonably large. Since tr will modify the input only
1630 if two consecutive (and identical) input characters are
1631 in the squeeze set, we can step by two through the data
1632 when searching for a character in the squeeze set. This
1633 means there may be a little more work in a few cases and
1634 perhaps twice as much work in the worst cases where most
1635 of the input is removed by squeezing repeats. But most
1636 uses of this functionality seem to remove less than 20-30%
1638 for (; i < nr && !in_squeeze_set[buf[i]]; i += 2)
1641 /* There is a special case when i == nr and we've just
1642 skipped a character (the last one in buf) that is in
1644 if (i == nr && in_squeeze_set[buf[i - 1]])
1648 out_len = nr - begin;
1651 char_to_squeeze = buf[i];
1652 /* We're about to output buf[begin..i]. */
1653 out_len = i - begin + 1;
1655 /* But since we stepped by 2 in the loop above,
1656 out_len may be one too large. */
1657 if (i > 0 && buf[i - 1] == char_to_squeeze)
1660 /* Advance i to the index of first character to be
1661 considered when looking for a char different from
1666 && fwrite ((char *) &buf[begin], 1, out_len, stdout) == 0)
1667 error (EXIT_FAILURE, errno, _("write error"));
1670 if (char_to_squeeze != NOT_A_CHAR)
1672 /* Advance i to index of first char != char_to_squeeze
1673 (or to nr if all the rest of the characters in this
1674 buffer are the same as char_to_squeeze). */
1675 for (; i < nr && buf[i] == char_to_squeeze; i++)
1678 char_to_squeeze = NOT_A_CHAR;
1679 /* If (i >= nr) we've squeezed the last character in this buffer.
1680 So now we have to read a new buffer and continue comparing
1681 characters against char_to_squeeze. */
1686 /* Read buffers of SIZE bytes from stdin until one is found that
1687 contains at least one character not in the delete set. Store
1688 in the array BUF, all characters from that buffer that are not
1689 in the delete set, and return the number of characters saved
1693 read_and_delete (unsigned char *buf, long int size, PFI not_used)
1696 static int hit_eof = 0;
1698 assert (not_used == NULL);
1704 /* This enclosing do-while loop is to make sure that
1705 we don't return zero (indicating EOF) when we've
1706 just deleted all the characters in a buffer. */
1710 int nr = safe_read (0, (char *) buf, size);
1713 error (EXIT_FAILURE, errno, _("read error"));
1720 /* This first loop may be a waste of code, but gives much
1721 better performance when no characters are deleted in
1722 the beginning of a buffer. It just avoids the copying
1723 of buf[i] into buf[n_saved] when it would be a NOP. */
1725 for (i = 0; i < nr && !in_delete_set[buf[i]]; i++)
1729 for (++i; i < nr; i++)
1730 if (!in_delete_set[buf[i]])
1731 buf[n_saved++] = buf[i];
1733 while (n_saved == 0);
1738 /* Read at most SIZE bytes from stdin into the array BUF. Then
1739 perform the in-place and one-to-one mapping specified by the global
1740 array `xlate'. Return the number of characters read, or 0 upon EOF. */
1743 read_and_xlate (unsigned char *buf, long int size, PFI not_used)
1745 long chars_read = 0;
1746 static int hit_eof = 0;
1749 assert (not_used == NULL);
1755 chars_read = safe_read (0, (char *) buf, size);
1757 error (EXIT_FAILURE, errno, _("read error"));
1758 if (chars_read == 0)
1764 for (i = 0; i < chars_read; i++)
1765 buf[i] = xlate[buf[i]];
1770 /* Initialize a boolean membership set IN_SET with the character
1771 values obtained by traversing the linked list of constructs S
1772 using the function `get_next'. If COMPLEMENT_THIS_SET is
1773 nonzero the resulting set is complemented. */
1776 set_initialize (struct Spec_list *s, int complement_this_set, SET_TYPE *in_set)
1781 memset (in_set, 0, N_CHARS * sizeof (in_set[0]));
1782 s->state = BEGIN_STATE;
1783 while ((c = get_next (s, NULL)) != -1)
1785 if (complement_this_set)
1786 for (i = 0; i < N_CHARS; i++)
1787 in_set[i] = (!in_set[i]);
1791 main (int argc, char **argv)
1794 int non_option_args;
1795 struct Spec_list buf1, buf2;
1796 struct Spec_list *s1 = &buf1;
1797 struct Spec_list *s2 = &buf2;
1799 program_name = argv[0];
1800 setlocale (LC_ALL, "");
1801 bindtextdomain (PACKAGE, LOCALEDIR);
1802 textdomain (PACKAGE);
1804 parse_long_options (argc, argv, PROGRAM_NAME, GNU_PACKAGE, VERSION,
1805 "Jim Meyering", usage);
1807 while ((c = getopt_long (argc, argv, "cdst", long_options, NULL)) != -1)
1823 squeeze_repeats = 1;
1836 posix_pedantic = (getenv ("POSIXLY_CORRECT") != NULL);
1838 non_option_args = argc - optind;
1839 translating = (non_option_args == 2 && !delete);
1841 /* Change this test if it is valid to give tr no options and
1842 no args at all. POSIX doesn't specifically say anything
1843 either way, but it looks like they implied it's invalid
1844 by omission. If you want to make tr do a slow imitation
1845 of `cat' use `tr a a'. */
1846 if (non_option_args > 2)
1848 error (0, 0, _("too many arguments"));
1852 if (!delete && !squeeze_repeats && non_option_args != 2)
1853 error (EXIT_FAILURE, 0, _("two strings must be given when translating"));
1855 if (delete && squeeze_repeats && non_option_args != 2)
1856 error (EXIT_FAILURE, 0, _("two strings must be given when both \
1857 deleting and squeezing repeats"));
1859 /* If --delete is given without --squeeze-repeats, then
1860 only one string argument may be specified. But POSIX
1861 says to ignore any string2 in this case, so if POSIXLY_CORRECT
1862 is set, pretend we never saw string2. But I think
1863 this deserves a fatal error, so that's the default. */
1864 if ((delete && !squeeze_repeats) && non_option_args != 1)
1866 if (posix_pedantic && non_option_args == 2)
1869 error (EXIT_FAILURE, 0,
1870 _("only one string may be given when deleting \
1871 without squeezing repeats"));
1874 if (squeeze_repeats && non_option_args == 0)
1875 error (EXIT_FAILURE, 0,
1876 _("at least one string must be given when squeezing repeats"));
1879 if (parse_str ((unsigned char *) argv[optind], s1))
1880 exit (EXIT_FAILURE);
1882 if (non_option_args == 2)
1885 if (parse_str ((unsigned char *) argv[optind + 1], s2))
1886 exit (EXIT_FAILURE);
1893 /* Use binary I/O, since `tr' is sometimes used to transliterate
1894 non-printable characters, or characters which are stripped away
1895 by text-mode reads (like CR and ^Z). */
1896 SET_BINARY2 (STDIN_FILENO, STDOUT_FILENO);
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 (EXIT_FAILURE, 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])
1966 error (EXIT_FAILURE, 0,
1967 _("misaligned [:upper:] and/or [:lower:] construct"));
1969 if (class_s1 == UL_LOWER && class_s2 == UL_UPPER)
1971 for (i = 0; i < N_CHARS; i++)
1973 xlate[i] = toupper (i);
1975 else if (class_s1 == UL_UPPER && class_s2 == UL_LOWER)
1977 for (i = 0; i < N_CHARS; i++)
1979 xlate[i] = tolower (i);
1981 else if ((class_s1 == UL_LOWER && class_s2 == UL_LOWER)
1982 || (class_s1 == UL_UPPER && class_s2 == UL_UPPER))
1984 /* By default, GNU tr permits the identity mappings: from
1985 [:upper:] to [:upper:] and [:lower:] to [:lower:]. But
1986 when POSIXLY_CORRECT is set, those evoke diagnostics. */
1989 error (EXIT_FAILURE, 0,
1991 invalid identity mapping; when translating, any [:lower:] or [:upper:]\n\
1992 construct in string1 must be aligned with a corresponding construct\n\
1993 ([:upper:] or [:lower:], respectively) in string2"));
1998 /* The following should have been checked by validate... */
1999 if (c1 == -1 || c2 == -1)
2004 assert (c1 == -1 || truncate_set1);
2006 if (squeeze_repeats)
2008 set_initialize (s2, 0, in_squeeze_set);
2009 squeeze_filter (io_buf, IO_BUF_SIZE, (PFI) read_and_xlate);
2017 chars_read = read_and_xlate (io_buf, IO_BUF_SIZE, NULL);
2019 && fwrite ((char *) io_buf, 1, chars_read, stdout) == 0)
2020 error (EXIT_FAILURE, errno, _("write error"));
2022 while (chars_read > 0);
2026 if (fclose (stdout) == EOF)
2027 error (EXIT_FAILURE, errno, _("write error"));
2030 error (EXIT_FAILURE, errno, _("standard input"));
2032 exit (EXIT_SUCCESS);