1 /* tr -- a filter to translate characters
2 Copyright (C) 91, 95, 96, 1997, 1998 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 */
22 /* Get isblank from GNU libc. */
29 #include <sys/types.h>
35 #define N_CHARS (UCHAR_MAX + 1)
37 /* A pointer to a function that returns an int. */
38 typedef int (*PFI) ();
40 /* Convert from character C to its index in the collating
41 sequence array. Just cast to an unsigned int to avoid
42 problems with sign-extension. */
43 #define ORD(c) (unsigned int)(c)
45 /* The inverse of ORD. */
46 #define CHR(i) (unsigned char)(i)
48 /* The value for Spec_list->state that indicates to
49 get_next that it should initialize the tail pointer.
50 Its value should be as large as possible to avoid conflict
51 a valid value for the state field -- and that may be as
52 large as any valid repeat_count. */
53 #define BEGIN_STATE (INT_MAX - 1)
55 /* The value for Spec_list->state that indicates to
56 get_next that the element pointed to by Spec_list->tail is
57 being considered for the first time on this pass through the
58 list -- it indicates that get_next should make any necessary
60 #define NEW_ELEMENT (BEGIN_STATE + 1)
62 /* A value distinct from any character that may have been stored in a
63 buffer as the result of a block-read in the function squeeze_filter. */
64 #define NOT_A_CHAR (unsigned int)(-1)
66 /* The following (but not CC_NO_CLASS) are indices into the array of
67 valid character class strings. */
70 CC_ALNUM = 0, CC_ALPHA = 1, CC_BLANK = 2, CC_CNTRL = 3,
71 CC_DIGIT = 4, CC_GRAPH = 5, CC_LOWER = 6, CC_PRINT = 7,
72 CC_PUNCT = 8, CC_SPACE = 9, CC_UPPER = 10, CC_XDIGIT = 11,
76 /* Character class to which a character (returned by get_next) belonged;
77 but it is set only if the construct from which the character was obtained
78 was one of the character classes [:upper:] or [:lower:]. The value
79 is used only when translating and then, only to make sure that upper
80 and lower class constructs have the same relative positions in string1
82 enum Upper_Lower_class
89 /* A shortcut to ensure that when constructing the translation array,
90 one of the values returned by paired calls to get_next (from s1 and s2)
91 is from [:upper:] and the other is from [:lower:], or neither is from
92 upper or lower. By default, GNU tr permits the identity mappings: from
93 [:upper:] to [:upper:] and [:lower:] to [:lower:]. But when
94 POSIXLY_CORRECT is set, those evoke diagnostics. This array is indexed
95 by values of type enum Upper_Lower_class. */
96 static int const class_ok[3][3] =
103 /* The type of a List_element. See build_spec_list for more details. */
104 enum Range_element_type
114 /* One construct in one of tr's argument strings.
115 For example, consider the POSIX version of the classic tr command:
116 tr -cs 'a-zA-Z_' '[\n*]'
117 String1 has 3 constructs, two of which are ranges (a-z and A-Z),
118 and a single normal character, `_'. String2 has one construct. */
121 enum Range_element_type type;
122 struct List_element *next;
128 unsigned int first_char;
129 unsigned int last_char;
132 enum Char_class char_class;
136 unsigned int the_repeated_char;
144 /* Each of tr's argument strings is parsed into a form that is easier
145 to work with: a linked list of constructs (struct List_element).
146 Each Spec_list structure also encapsulates various attributes of
147 the corresponding argument string. The attributes are used mainly
148 to verify that the strings are valid in the context of any options
149 specified (like -s, -d, or -c). The main exception is the member
150 `tail', which is first used to construct the list. After construction,
151 it is used by get_next to save its state when traversing the list.
152 The member `state' serves a similar function. */
155 /* Points to the head of the list of range elements.
156 The first struct is a dummy; its members are never used. */
157 struct List_element *head;
159 /* When appending, points to the last element. When traversing via
160 get_next(), points to the element to process next. Setting
161 Spec_list.state to the value BEGIN_STATE before calling get_next
162 signals get_next to initialize tail to point to head->next. */
163 struct List_element *tail;
165 /* Used to save state between calls to get_next(). */
168 /* Length, in the sense that length ('a-z[:digit:]123abc')
169 is 42 ( = 26 + 10 + 6). */
172 /* The number of [c*] and [c*0] constructs that appear in this spec. */
173 int n_indefinite_repeats;
175 /* If n_indefinite_repeats is nonzero, this points to the List_element
176 corresponding to the last [c*] or [c*0] construct encountered in
177 this spec. Otherwise it is undefined. */
178 struct List_element *indefinite_repeat_element;
180 /* Non-zero if this spec contains at least one equivalence
181 class construct e.g. [=c=]. */
184 /* Non-zero if this spec contains at least one character class
185 construct. E.g. [:digit:]. */
188 /* Non-zero if this spec contains at least one of the character class
189 constructs (all but upper and lower) that aren't allowed in s2. */
190 int has_restricted_char_class;
193 /* A representation for escaped string1 or string2. As a string is parsed,
194 any backslash-escaped characters (other than octal or \a, \b, \f, \n,
195 etc.) are marked as such in this structure by setting the corresponding
196 entry in the ESCAPED vector. */
204 /* Return nonzero if the Ith character of escaped string ES matches C
205 and is not escaped itself. */
206 #define ES_MATCH(ES, I, C) ((ES)->s[(I)] == (C) && !(ES)->escaped[(I)])
210 /* The name by which this program was run. */
213 /* When nonzero, each sequence in the input of a repeated character
214 (call it c) is replaced (in the output) by a single occurrence of c
215 for every c in the squeeze set. */
216 static int squeeze_repeats = 0;
218 /* When nonzero, removes characters in the delete set from input. */
219 static int delete = 0;
221 /* Use the complement of set1 in place of set1. */
222 static int complement = 0;
224 /* When nonzero, this flag causes GNU tr to provide strict
225 compliance with POSIX draft 1003.2.11.2. The POSIX spec
226 says that when -d is used without -s, string2 (if present)
227 must be ignored. Silently ignoring arguments is a bad idea.
228 The default GNU behavior is to give a usage message and exit.
229 Additionally, when this flag is nonzero, tr prints warnings
230 on stderr if it is being used in a manner that is not portable.
231 Applicable warnings are given by default, but are suppressed
232 if the environment variable `POSIXLY_CORRECT' is set, since
233 being POSIX conformant means we can't issue such messages.
234 Warnings on the following topics are suppressed when this
236 1. Ambiguous octal escapes. */
237 static int posix_pedantic;
239 /* When tr is performing translation and string1 is longer than string2,
240 POSIX says that the result is undefined. That gives the implementor
241 of a POSIX conforming version of tr two reasonable choices for the
242 semantics of this case.
244 * The BSD tr pads string2 to the length of string1 by
245 repeating the last character in string2.
247 * System V tr ignores characters in string1 that have no
248 corresponding character in string2. That is, string1 is effectively
249 truncated to the length of string2.
251 When nonzero, this flag causes GNU tr to imitate the behavior
252 of System V tr when translating with string1 longer than string2.
253 The default is to emulate BSD tr. This flag is ignored in modes where
254 no translation is performed. Emulating the System V tr
255 in this exceptional case causes the relatively common BSD idiom:
257 tr -cs A-Za-z0-9 '\012'
259 to break (it would convert only zero bytes, rather than all
260 non-alphanumerics, to newlines).
262 WARNING: This switch does not provide general BSD or System V
263 compatibility. For example, it doesn't disable the interpretation
264 of the POSIX constructs [:alpha:], [=c=], and [c*10], so if by
265 some unfortunate coincidence you use such constructs in scripts
266 expecting to use some other version of tr, the scripts will break. */
267 static int truncate_set1 = 0;
269 /* An alias for (!delete && non_option_args == 2).
270 It is set in main and used there and in validate(). */
271 static int translating;
277 #define IO_BUF_SIZE BUFSIZ
278 static unsigned char io_buf[IO_BUF_SIZE];
280 static char const *const char_class_name[] =
282 "alnum", "alpha", "blank", "cntrl", "digit", "graph",
283 "lower", "print", "punct", "space", "upper", "xdigit"
285 #define N_CHAR_CLASSES (sizeof(char_class_name) / sizeof(char_class_name[0]))
287 typedef char SET_TYPE;
289 /* Array of boolean values. A character `c' is a member of the
290 squeeze set if and only if in_squeeze_set[c] is true. The squeeze
291 set is defined by the last (possibly, the only) string argument
292 on the command line when the squeeze option is given. */
293 static SET_TYPE in_squeeze_set[N_CHARS];
295 /* Array of boolean values. A character `c' is a member of the
296 delete set if and only if in_delete_set[c] is true. The delete
297 set is defined by the first (or only) string argument on the
298 command line when the delete option is given. */
299 static SET_TYPE in_delete_set[N_CHARS];
301 /* Array of character values defining the translation (if any) that
302 tr is to perform. Translation is performed only when there are
303 two specification strings and the delete switch is not given. */
304 static char xlate[N_CHARS];
306 /* If nonzero, display usage information and exit. */
307 static int show_help;
309 /* If nonzero, print the version on standard output then exit. */
310 static int show_version;
312 static struct option const long_options[] =
314 {"complement", no_argument, NULL, 'c'},
315 {"delete", no_argument, NULL, 'd'},
316 {"squeeze-repeats", no_argument, NULL, 's'},
317 {"truncate-set1", no_argument, NULL, 't'},
318 {"help", no_argument, &show_help, 1},
319 {"version", no_argument, &show_version, 1},
327 fprintf (stderr, _("Try `%s --help' for more information.\n"),
332 Usage: %s [OPTION]... SET1 [SET2]\n\
336 Translate, squeeze, and/or delete characters from standard input,\n\
337 writing to standard output.\n\
339 -c, --complement first complement SET1\n\
340 -d, --delete delete characters in SET1, do not translate\n\
341 -s, --squeeze-repeats replace sequence of characters with one\n\
342 -t, --truncate-set1 first truncate SET1 to length of SET2\n\
343 --help display this help and exit\n\
344 --version output version information and exit\n\
348 SETs are specified as strings of characters. Most represent themselves.\n\
349 Interpreted sequences are:\n\
351 \\NNN character with octal value NNN (1 to 3 octal digits)\n\
358 \\t horizontal tab\n\
360 CHAR1-CHAR2 all characters from CHAR1 to CHAR2 in ascending order\n\
361 [CHAR1-CHAR2] same as CHAR1-CHAR2, if both SET1 and SET2 use this\n\
362 [CHAR*] in SET2, copies of CHAR until length of SET1\n\
363 [CHAR*REPEAT] REPEAT copies of CHAR, REPEAT octal if starting with 0\n\
364 [:alnum:] all letters and digits\n\
365 [:alpha:] all letters\n\
366 [:blank:] all horizontal whitespace\n\
367 [:cntrl:] all control characters\n\
368 [:digit:] all digits\n\
369 [:graph:] all printable characters, not including space\n\
370 [:lower:] all lower case letters\n\
371 [:print:] all printable characters, including space\n\
372 [:punct:] all punctuation characters\n\
373 [:space:] all horizontal or vertical whitespace\n\
374 [:upper:] all upper case letters\n\
375 [:xdigit:] all hexadecimal digits\n\
376 [=CHAR=] all characters which are equivalent to CHAR\n\
380 Translation occurs if -d is not given and both SET1 and SET2 appear.\n\
381 -t may be used only when translating. SET2 is extended to length of\n\
382 SET1 by repeating its last character as necessary. Excess characters\n\
383 of SET2 are ignored. Only [:lower:] and [:upper:] are guaranteed to\n\
384 expand in ascending order; used in SET2 while translating, they may\n\
385 only be used in pairs to specify case conversion. -s uses SET1 if not\n\
386 translating nor deleting; else squeezing uses SET2 and occurs after\n\
387 translation or deletion.\n\
389 puts (_("\nReport bugs to <textutils-bugs@gnu.org>."));
391 exit (status == 0 ? EXIT_SUCCESS : EXIT_FAILURE);
394 /* Return nonzero if the character C is a member of the
395 equivalence class containing the character EQUIV_CLASS. */
398 is_equiv_class_member (unsigned int equiv_class, unsigned int c)
400 return (equiv_class == c);
403 /* Return nonzero if the character C is a member of the
404 character class CHAR_CLASS. */
407 is_char_class_member (enum Char_class char_class, unsigned int c)
414 result = ISALNUM (c);
417 result = ISALPHA (c);
420 result = ISBLANK (c);
423 result = ISCNTRL (c);
426 result = ISDIGIT_LOCALE (c);
429 result = ISGRAPH (c);
432 result = ISLOWER (c);
435 result = ISPRINT (c);
438 result = ISPUNCT (c);
441 result = ISSPACE (c);
444 result = ISUPPER (c);
447 result = ISXDIGIT (c);
457 es_free (struct E_string *es)
463 /* Perform the first pass over each range-spec argument S, converting all
464 \c and \ddd escapes to their one-byte representations. The conversion
465 is done in-place, so S must point to writable storage. If an invalid
466 quote sequence is found print an error message and return nonzero.
467 Otherwise set *LEN to the length of the resulting string and return
468 zero. The resulting array of characters may contain zero-bytes;
469 however, on input, S is assumed to be null-terminated, and hence
470 cannot contain actual (non-escaped) zero bytes. */
473 unquote (const unsigned char *s, struct E_string *es)
478 len = strlen ((char *) s);
480 es->s = (unsigned char *) xmalloc (len);
481 es->escaped = (int *) xmalloc (len * sizeof (es->escaped[0]));
482 for (i = 0; i < len; i++)
486 for (i = 0; s[i]; i++)
528 oct_digit = s[i + 2] - '0';
529 if (0 <= oct_digit && oct_digit <= 7)
531 c = 8 * c + oct_digit;
533 oct_digit = s[i + 2] - '0';
534 if (0 <= oct_digit && oct_digit <= 7)
536 if (8 * c + oct_digit < N_CHARS)
538 c = 8 * c + oct_digit;
541 else if (!posix_pedantic)
543 /* Any octal number larger than 0377 won't
544 fit in 8 bits. So we stop when adding the
545 next digit would put us over the limit and
546 give a warning about the ambiguity. POSIX
547 isn't clear on this, but one person has said
548 that in his interpretation, POSIX says tr
549 can't even give a warning. */
550 error (0, 0, _("warning: the ambiguous octal escape \
551 \\%c%c%c is being\n\tinterpreted as the 2-byte sequence \\0%c%c, `%c'"),
552 s[i], s[i + 1], s[i + 2],
553 s[i], s[i + 1], s[i + 2]);
559 error (0, 0, _("invalid backslash escape at end of string"));
565 error (0, 0, _("invalid backslash escape `\\%c'"), s[i + 1]);
586 /* If CLASS_STR is a valid character class string, return its index
587 in the global char_class_name array. Otherwise, return CC_NO_CLASS. */
589 static enum Char_class
590 look_up_char_class (const unsigned char *class_str, size_t len)
594 for (i = 0; i < N_CHAR_CLASSES; i++)
595 if (strncmp ((const char *) class_str, char_class_name[i], len) == 0
596 && strlen (char_class_name[i]) == len)
597 return (enum Char_class) i;
601 /* Return a newly allocated string with a printable version of C.
602 This function is used solely for formatting error messages. */
605 make_printable_char (unsigned int c)
607 char *buf = xmalloc (5);
609 assert (c < N_CHARS);
617 sprintf (buf, "\\%03o", c);
622 /* Return a newly allocated copy of S which is suitable for printing.
623 LEN is the number of characters in S. Most non-printing
624 (isprint) characters are represented by a backslash followed by
625 3 octal digits. However, the characters represented by \c escapes
626 where c is one of [abfnrtv] are represented by their 2-character \c
627 sequences. This function is used solely for printing error messages. */
630 make_printable_str (const unsigned char *s, size_t len)
632 /* Worst case is that every character expands to a backslash
633 followed by a 3-character octal escape sequence. */
634 char *printable_buf = xmalloc (4 * len + 1);
635 char *p = printable_buf;
638 for (i = 0; i < len; i++)
676 sprintf (buf, "\\%03o", s[i]);
682 return printable_buf;
685 /* Append a newly allocated structure representing a
686 character C to the specification list LIST. */
689 append_normal_char (struct Spec_list *list, unsigned int c)
691 struct List_element *new;
693 new = (struct List_element *) xmalloc (sizeof (struct List_element));
695 new->type = RE_NORMAL_CHAR;
696 new->u.normal_char = c;
698 list->tail->next = new;
702 /* Append a newly allocated structure representing the range
703 of characters from FIRST to LAST to the specification list LIST.
704 Return nonzero if LAST precedes FIRST in the collating sequence,
705 zero otherwise. This means that '[c-c]' is acceptable. */
708 append_range (struct Spec_list *list, unsigned int first, unsigned int last)
710 struct List_element *new;
712 if (ORD (first) > ORD (last))
714 char *tmp1 = make_printable_char (first);
715 char *tmp2 = make_printable_char (last);
718 _("range-endpoints of `%s-%s' are in reverse collating sequence order"),
724 new = (struct List_element *) xmalloc (sizeof (struct List_element));
726 new->type = RE_RANGE;
727 new->u.range.first_char = first;
728 new->u.range.last_char = last;
730 list->tail->next = new;
735 /* If CHAR_CLASS_STR is a valid character class string, append a
736 newly allocated structure representing that character class to the end
737 of the specification list LIST and return 0. If CHAR_CLASS_STR is not
738 a valid string return nonzero. */
741 append_char_class (struct Spec_list *list,
742 const unsigned char *char_class_str, size_t len)
744 enum Char_class char_class;
745 struct List_element *new;
747 char_class = look_up_char_class (char_class_str, len);
748 if (char_class == CC_NO_CLASS)
750 new = (struct List_element *) xmalloc (sizeof (struct List_element));
752 new->type = RE_CHAR_CLASS;
753 new->u.char_class = char_class;
755 list->tail->next = new;
760 /* Append a newly allocated structure representing a [c*n]
761 repeated character construct to the specification list LIST.
762 THE_CHAR is the single character to be repeated, and REPEAT_COUNT
763 is a non-negative repeat count. */
766 append_repeated_char (struct Spec_list *list, unsigned int the_char,
769 struct List_element *new;
771 new = (struct List_element *) xmalloc (sizeof (struct List_element));
773 new->type = RE_REPEATED_CHAR;
774 new->u.repeated_char.the_repeated_char = the_char;
775 new->u.repeated_char.repeat_count = repeat_count;
777 list->tail->next = new;
781 /* Given a string, EQUIV_CLASS_STR, from a [=str=] context and
782 the length of that string, LEN, if LEN is exactly one, append
783 a newly allocated structure representing the specified
784 equivalence class to the specification list, LIST and return zero.
785 If LEN is not 1, return nonzero. */
788 append_equiv_class (struct Spec_list *list,
789 const unsigned char *equiv_class_str, size_t len)
791 struct List_element *new;
795 new = (struct List_element *) xmalloc (sizeof (struct List_element));
797 new->type = RE_EQUIV_CLASS;
798 new->u.equiv_code = *equiv_class_str;
800 list->tail->next = new;
805 /* Return a newly allocated copy of the substring P[FIRST_IDX..LAST_IDX].
806 The returned string has length LAST_IDX - FIRST_IDX + 1, may contain
807 NUL bytes, and is *not* NUL-terminated. */
809 static unsigned char *
810 substr (const unsigned char *p, size_t first_idx, size_t last_idx)
815 assert (first_idx <= last_idx);
816 len = last_idx - first_idx + 1;
817 tmp = (unsigned char *) xmalloc (len);
819 assert (first_idx <= last_idx);
820 /* Use memcpy rather than strncpy because `p' may contain zero-bytes. */
821 memcpy (tmp, p + first_idx, len);
825 /* Search forward starting at START_IDX for the 2-char sequence
826 (PRE_BRACKET_CHAR,']') in the string P of length P_LEN. If such
827 a sequence is found, set *RESULT_IDX to the index of the first
828 character and return nonzero. Otherwise return zero. P may contain
832 find_closing_delim (const struct E_string *es, size_t start_idx,
833 unsigned int pre_bracket_char, size_t *result_idx)
837 for (i = start_idx; i < es->len - 1; i++)
838 if (es->s[i] == pre_bracket_char && es->s[i + 1] == ']'
839 && !es->escaped[i] && !es->escaped[i + 1])
847 /* Convert a string S with explicit length LEN, possibly
848 containing embedded zero bytes, to a long integer value.
849 If the string represents a negative value, a value larger
850 than LONG_MAX, or if all LEN characters do not represent a
851 valid integer, return nonzero and do not modify *VAL.
852 Otherwise, return zero and set *VAL to the converted value. */
855 non_neg_strtol (const unsigned char *s, size_t len, size_t *val)
858 unsigned long sum = 0;
865 else if (ISDIGIT (s[0]))
870 for (i = 0; i < len; i++)
881 if (sum > (LONG_MAX - c) / base)
883 sum = sum * base + c;
889 /* Parse the bracketed repeat-char syntax. If the P_LEN characters
890 beginning with P[ START_IDX ] comprise a valid [c*n] construct,
891 then set *CHAR_TO_REPEAT, *REPEAT_COUNT, and *CLOSING_BRACKET_IDX
892 and return zero. If the second character following
893 the opening bracket is not `*' or if no closing bracket can be
894 found, return -1. If a closing bracket is found and the
895 second char is `*', but the string between the `*' and `]' isn't
896 empty, an octal number, or a decimal number, print an error message
900 find_bracketed_repeat (const struct E_string *es, size_t start_idx,
901 unsigned int *char_to_repeat, size_t *repeat_count,
902 size_t *closing_bracket_idx)
906 assert (start_idx + 1 < es->len);
907 if (!ES_MATCH (es, start_idx + 1, '*'))
910 for (i = start_idx + 2; i < es->len; i++)
912 if (ES_MATCH (es, i, ']'))
914 const unsigned char *digit_str;
915 size_t digit_str_len = i - start_idx - 2;
917 *char_to_repeat = es->s[start_idx];
918 if (digit_str_len == 0)
920 /* We've matched [c*] -- no explicit repeat count. */
922 *closing_bracket_idx = i;
926 /* Here, we have found [c*s] where s should be a string
927 of octal or decimal digits. */
928 digit_str = &es->s[start_idx + 2];
929 if (non_neg_strtol (digit_str, digit_str_len, repeat_count)
930 || *repeat_count > BEGIN_STATE)
932 char *tmp = make_printable_str (digit_str, digit_str_len);
933 error (0, 0, _("invalid repeat count `%s' in [c*n] construct"),
938 *closing_bracket_idx = i;
942 return -1; /* No bracket found. */
945 /* Return nonzero if the string at ES->s[IDX] matches the regular
946 expression `\*[0-9]*\]', zero otherwise. To match, the `*' and
947 the `]' must not be escaped. */
950 star_digits_closebracket (const struct E_string *es, size_t idx)
954 if (!ES_MATCH (es, idx, '*'))
957 for (i = idx + 1; i < es->len; i++)
959 if (!ISDIGIT (es->s[i]))
961 if (ES_MATCH (es, i, ']'))
969 /* Convert string UNESACPED_STRING (which has been preprocessed to
970 convert backslash-escape sequences) of length LEN characters into
971 a linked list of the following 5 types of constructs:
972 - [:str:] Character class where `str' is one of the 12 valid strings.
973 - [=c=] Equivalence class where `c' is any single character.
974 - [c*n] Repeat the single character `c' `n' times. n may be omitted.
975 However, if `n' is present, it must be a non-negative octal or
977 - r-s Range of characters from `r' to `s'. The second endpoint must
978 not precede the first in the current collating sequence.
979 - c Any other character is interpreted as itself. */
982 build_spec_list (const struct E_string *es, struct Spec_list *result)
984 const unsigned char *p;
989 /* The main for-loop below recognizes the 4 multi-character constructs.
990 A character that matches (in its context) none of the multi-character
991 constructs is classified as `normal'. Since all multi-character
992 constructs have at least 3 characters, any strings of length 2 or
993 less are composed solely of normal characters. Hence, the index of
994 the outer for-loop runs only as far as LEN-2. */
996 for (i = 0; i + 2 < es->len; /* empty */)
998 if (ES_MATCH (es, i, '['))
1000 int matched_multi_char_construct;
1001 size_t closing_bracket_idx;
1002 unsigned int char_to_repeat;
1003 size_t repeat_count;
1006 matched_multi_char_construct = 1;
1007 if (ES_MATCH (es, i + 1, ':')
1008 || ES_MATCH (es, i + 1, '='))
1010 size_t closing_delim_idx;
1013 found = find_closing_delim (es, i + 2, p[i + 1],
1014 &closing_delim_idx);
1018 unsigned char *opnd_str = substr (p, i + 2,
1019 closing_delim_idx - 1);
1020 size_t opnd_str_len = closing_delim_idx - 1 - (i + 2) + 1;
1022 if (p[i + 1] == ':')
1024 parse_failed = append_char_class (result, opnd_str,
1027 /* FIXME: big comment. */
1030 if (star_digits_closebracket (es, i + 2))
1033 goto try_bracketed_repeat;
1037 char *tmp = make_printable_str (opnd_str,
1039 error (0, 0, _("invalid character class `%s'"),
1048 parse_failed = append_equiv_class (result, opnd_str,
1051 /* FIXME: big comment. */
1054 if (star_digits_closebracket (es, i + 2))
1057 goto try_bracketed_repeat;
1061 char *tmp = make_printable_str (opnd_str,
1064 _("%s: equivalence class operand must be a single character"),
1073 /* Return nonzero if append_*_class reports a problem. */
1077 i = closing_delim_idx + 2;
1080 /* Else fall through. This could be [:*] or [=*]. */
1083 try_bracketed_repeat:
1085 /* Determine whether this is a bracketed repeat range
1086 matching the RE \[.\*(dec_or_oct_number)?\]. */
1087 err = find_bracketed_repeat (es, i + 1, &char_to_repeat,
1089 &closing_bracket_idx);
1092 append_repeated_char (result, char_to_repeat, repeat_count);
1093 i = closing_bracket_idx + 1;
1097 matched_multi_char_construct = 0;
1101 /* Found a string that looked like [c*n] but the
1102 numeric part was invalid. */
1106 if (matched_multi_char_construct)
1109 /* We reach this point if P does not match [:str:], [=c=],
1110 [c*n], or [c*]. Now, see if P looks like a range `[-c'
1111 (from `[' to `c'). */
1114 /* Look ahead one char for ranges like a-z. */
1115 if (ES_MATCH (es, i + 1, '-'))
1117 if (append_range (result, p[i], p[i + 2]))
1123 append_normal_char (result, p[i]);
1128 /* Now handle the (2 or fewer) remaining characters p[i]..p[es->len - 1]. */
1129 for (; i < es->len; i++)
1130 append_normal_char (result, p[i]);
1135 /* Given a Spec_list S (with its saved state implicit in the values
1136 of its members `tail' and `state'), return the next single character
1137 in the expansion of S's constructs. If the last character of S was
1138 returned on the previous call or if S was empty, this function
1139 returns -1. For example, successive calls to get_next where S
1140 represents the spec-string 'a-d[y*3]' will return the sequence
1141 of values a, b, c, d, y, y, y, -1. Finally, if the construct from
1142 which the returned character comes is [:upper:] or [:lower:], the
1143 parameter CLASS is given a value to indicate which it was. Otherwise
1144 CLASS is set to UL_NONE. This value is used only when constructing
1145 the translation table to verify that any occurrences of upper and
1146 lower class constructs in the spec-strings appear in the same relative
1150 get_next (struct Spec_list *s, enum Upper_Lower_class *class)
1152 struct List_element *p;
1159 if (s->state == BEGIN_STATE)
1161 s->tail = s->head->next;
1162 s->state = NEW_ELEMENT;
1171 case RE_NORMAL_CHAR:
1172 return_val = p->u.normal_char;
1173 s->state = NEW_ELEMENT;
1178 if (s->state == NEW_ELEMENT)
1179 s->state = ORD (p->u.range.first_char);
1182 return_val = CHR (s->state);
1183 if (s->state == ORD (p->u.range.last_char))
1186 s->state = NEW_ELEMENT;
1194 switch (p->u.char_class)
1212 s->state = NEW_ELEMENT;
1218 if (s->state == NEW_ELEMENT)
1220 for (i = 0; i < N_CHARS; i++)
1221 if (is_char_class_member (p->u.char_class, i))
1223 assert (i < N_CHARS);
1226 assert (is_char_class_member (p->u.char_class, s->state));
1227 return_val = CHR (s->state);
1228 for (i = s->state + 1; i < N_CHARS; i++)
1229 if (is_char_class_member (p->u.char_class, i))
1236 s->state = NEW_ELEMENT;
1240 case RE_EQUIV_CLASS:
1241 /* FIXME: this assumes that each character is alone in its own
1242 equivalence class (which appears to be correct for my
1243 LC_COLLATE. But I don't know of any function that allows
1244 one to determine a character's equivalence class. */
1246 return_val = p->u.equiv_code;
1247 s->state = NEW_ELEMENT;
1251 case RE_REPEATED_CHAR:
1252 /* Here, a repeat count of n == 0 means don't repeat at all. */
1253 if (p->u.repeated_char.repeat_count == 0)
1256 s->state = NEW_ELEMENT;
1257 return_val = get_next (s, class);
1261 if (s->state == NEW_ELEMENT)
1266 return_val = p->u.repeated_char.the_repeated_char;
1267 if (p->u.repeated_char.repeat_count > 0
1268 && s->state == p->u.repeated_char.repeat_count)
1271 s->state = NEW_ELEMENT;
1288 /* This is a minor kludge. This function is called from
1289 get_spec_stats to determine the cardinality of a set derived
1290 from a complemented string. It's a kludge in that some of the
1291 same operations are (duplicated) performed in set_initialize. */
1294 card_of_complement (struct Spec_list *s)
1297 int cardinality = N_CHARS;
1298 SET_TYPE in_set[N_CHARS];
1300 memset (in_set, 0, N_CHARS * sizeof (in_set[0]));
1301 s->state = BEGIN_STATE;
1302 while ((c = get_next (s, NULL)) != -1)
1308 /* Gather statistics about the spec-list S in preparation for the tests
1309 in validate that determine the consistency of the specs. This function
1310 is called at most twice; once for string1, and again for any string2.
1311 LEN_S1 < 0 indicates that this is the first call and that S represents
1312 string1. When LEN_S1 >= 0, it is the length of the expansion of the
1313 constructs in string1, and we can use its value to resolve any
1314 indefinite repeat construct in S (which represents string2). Hence,
1315 this function has the side-effect that it converts a valid [c*]
1316 construct in string2 to [c*n] where n is large enough (or 0) to give
1317 string2 the same length as string1. For example, with the command
1318 tr a-z 'A[\n*]Z' on the second call to get_spec_stats, LEN_S1 would
1319 be 26 and S (representing string2) would be converted to 'A[\n*24]Z'. */
1322 get_spec_stats (struct Spec_list *s)
1324 struct List_element *p;
1327 s->n_indefinite_repeats = 0;
1328 s->has_equiv_class = 0;
1329 s->has_restricted_char_class = 0;
1330 s->has_char_class = 0;
1331 for (p = s->head->next; p; p = p->next)
1336 case RE_NORMAL_CHAR:
1341 assert (p->u.range.last_char >= p->u.range.first_char);
1342 len += p->u.range.last_char - p->u.range.first_char + 1;
1346 s->has_char_class = 1;
1347 for (i = 0; i < N_CHARS; i++)
1348 if (is_char_class_member (p->u.char_class, i))
1350 switch (p->u.char_class)
1356 s->has_restricted_char_class = 1;
1361 case RE_EQUIV_CLASS:
1362 for (i = 0; i < N_CHARS; i++)
1363 if (is_equiv_class_member (p->u.equiv_code, i))
1365 s->has_equiv_class = 1;
1368 case RE_REPEATED_CHAR:
1369 if (p->u.repeated_char.repeat_count > 0)
1370 len += p->u.repeated_char.repeat_count;
1371 else if (p->u.repeated_char.repeat_count == 0)
1373 s->indefinite_repeat_element = p;
1374 ++(s->n_indefinite_repeats);
1388 get_s1_spec_stats (struct Spec_list *s1)
1390 get_spec_stats (s1);
1392 s1->length = card_of_complement (s1);
1396 get_s2_spec_stats (struct Spec_list *s2, size_t len_s1)
1398 get_spec_stats (s2);
1399 if (len_s1 >= s2->length && s2->n_indefinite_repeats == 1)
1401 s2->indefinite_repeat_element->u.repeated_char.repeat_count =
1402 len_s1 - s2->length;
1403 s2->length = len_s1;
1408 spec_init (struct Spec_list *spec_list)
1410 spec_list->head = spec_list->tail =
1411 (struct List_element *) xmalloc (sizeof (struct List_element));
1412 spec_list->head->next = NULL;
1415 /* This function makes two passes over the argument string S. The first
1416 one converts all \c and \ddd escapes to their one-byte representations.
1417 The second constructs a linked specification list, SPEC_LIST, of the
1418 characters and constructs that comprise the argument string. If either
1419 of these passes detects an error, this function returns nonzero. */
1422 parse_str (const unsigned char *s, struct Spec_list *spec_list)
1427 fail = unquote (s, &es);
1429 fail = build_spec_list (&es, spec_list);
1434 /* Given two specification lists, S1 and S2, and assuming that
1435 S1->length > S2->length, append a single [c*n] element to S2 where c
1436 is the last character in the expansion of S2 and n is the difference
1437 between the two lengths.
1438 Upon successful completion, S2->length is set to S1->length. The only
1439 way this function can fail to make S2 as long as S1 is when S2 has
1440 zero-length, since in that case, there is no last character to repeat.
1441 So S2->length is required to be at least 1.
1443 Providing this functionality allows the user to do some pretty
1444 non-BSD (and non-portable) things: For example, the command
1445 tr -cs '[:upper:]0-9' '[:lower:]'
1446 is almost guaranteed to give results that depend on your collating
1450 string2_extend (const struct Spec_list *s1, struct Spec_list *s2)
1452 struct List_element *p;
1456 assert (translating);
1457 assert (s1->length > s2->length);
1458 assert (s2->length > 0);
1463 case RE_NORMAL_CHAR:
1464 char_to_repeat = p->u.normal_char;
1467 char_to_repeat = p->u.range.last_char;
1470 for (i = N_CHARS; i >= 0; i--)
1471 if (is_char_class_member (p->u.char_class, i))
1474 char_to_repeat = CHR (i);
1477 case RE_REPEATED_CHAR:
1478 char_to_repeat = p->u.repeated_char.the_repeated_char;
1481 case RE_EQUIV_CLASS:
1482 /* This shouldn't happen, because validate exits with an error
1483 if it finds an equiv class in string2 when translating. */
1496 append_repeated_char (s2, char_to_repeat, s1->length - s2->length);
1497 s2->length = s1->length;
1500 /* Return non-zero if S is a non-empty list in which exactly one
1501 character (but potentially, many instances of it) appears.
1502 E.g. [X*] or xxxxxxxx. */
1505 homogeneous_spec_list (struct Spec_list *s)
1509 s->state = BEGIN_STATE;
1511 if ((b = get_next (s, NULL)) == -1)
1514 while ((c = get_next (s, NULL)) != -1)
1521 /* Die with an error message if S1 and S2 describe strings that
1522 are not valid with the given command line switches.
1523 A side effect of this function is that if a valid [c*] or
1524 [c*0] construct appears in string2, it is converted to [c*n]
1525 with a value for n that makes s2->length == s1->length. By
1526 the same token, if the --truncate-set1 option is not
1527 given, S2 may be extended. */
1530 validate (struct Spec_list *s1, struct Spec_list *s2)
1532 get_s1_spec_stats (s1);
1533 if (s1->n_indefinite_repeats > 0)
1535 error (EXIT_FAILURE, 0,
1536 _("the [c*] repeat construct may not appear in string1"));
1541 get_s2_spec_stats (s2, s1->length);
1543 if (s2->n_indefinite_repeats > 1)
1545 error (EXIT_FAILURE, 0,
1546 _("only one [c*] repeat construct may appear in string2"));
1551 if (s2->has_equiv_class)
1553 error (EXIT_FAILURE, 0,
1554 _("[=c=] expressions may not appear in string2 \
1555 when translating"));
1558 if (s1->length > s2->length)
1562 /* string2 must be non-empty unless --truncate-set1 is
1563 given or string1 is empty. */
1565 if (s2->length == 0)
1566 error (EXIT_FAILURE, 0,
1567 _("when not truncating set1, string2 must be non-empty"));
1568 string2_extend (s1, s2);
1572 if (complement && s1->has_char_class
1573 && ! (s2->length == s1->length && homogeneous_spec_list (s2)))
1575 error (EXIT_FAILURE, 0,
1576 _("when translating with complemented character classes,\
1577 \nstring2 must map all characters in the domain to one"));
1580 if (s2->has_restricted_char_class)
1582 error (EXIT_FAILURE, 0,
1583 _("when translating, the only character classes that may \
1584 appear in\nstring2 are `upper' and `lower'"));
1588 /* Not translating. */
1590 if (s2->n_indefinite_repeats > 0)
1591 error (EXIT_FAILURE, 0,
1592 _("the [c*] construct may appear in string2 only \
1593 when translating"));
1598 /* Read buffers of SIZE bytes via the function READER (if READER is
1599 NULL, read from stdin) until EOF. When non-NULL, READER is either
1600 read_and_delete or read_and_xlate. After each buffer is read, it is
1601 processed and written to stdout. The buffers are processed so that
1602 multiple consecutive occurrences of the same character in the input
1603 stream are replaced by a single occurrence of that character if the
1604 character is in the squeeze set. */
1607 squeeze_filter (unsigned char *buf, long int size, PFI reader)
1609 unsigned int char_to_squeeze = NOT_A_CHAR;
1620 nr = safe_read (0, (char *) buf, size);
1622 nr = (*reader) (buf, size, NULL);
1625 error (EXIT_FAILURE, errno, _("read error"));
1633 if (char_to_squeeze == NOT_A_CHAR)
1636 /* Here, by being a little tricky, we can get a significant
1637 performance increase in most cases when the input is
1638 reasonably large. Since tr will modify the input only
1639 if two consecutive (and identical) input characters are
1640 in the squeeze set, we can step by two through the data
1641 when searching for a character in the squeeze set. This
1642 means there may be a little more work in a few cases and
1643 perhaps twice as much work in the worst cases where most
1644 of the input is removed by squeezing repeats. But most
1645 uses of this functionality seem to remove less than 20-30%
1647 for (; i < nr && !in_squeeze_set[buf[i]]; i += 2)
1650 /* There is a special case when i == nr and we've just
1651 skipped a character (the last one in buf) that is in
1653 if (i == nr && in_squeeze_set[buf[i - 1]])
1657 out_len = nr - begin;
1660 char_to_squeeze = buf[i];
1661 /* We're about to output buf[begin..i]. */
1662 out_len = i - begin + 1;
1664 /* But since we stepped by 2 in the loop above,
1665 out_len may be one too large. */
1666 if (i > 0 && buf[i - 1] == char_to_squeeze)
1669 /* Advance i to the index of first character to be
1670 considered when looking for a char different from
1675 && fwrite ((char *) &buf[begin], 1, out_len, stdout) == 0)
1676 error (EXIT_FAILURE, errno, _("write error"));
1679 if (char_to_squeeze != NOT_A_CHAR)
1681 /* Advance i to index of first char != char_to_squeeze
1682 (or to nr if all the rest of the characters in this
1683 buffer are the same as char_to_squeeze). */
1684 for (; i < nr && buf[i] == char_to_squeeze; i++)
1687 char_to_squeeze = NOT_A_CHAR;
1688 /* If (i >= nr) we've squeezed the last character in this buffer.
1689 So now we have to read a new buffer and continue comparing
1690 characters against char_to_squeeze. */
1695 /* Read buffers of SIZE bytes from stdin until one is found that
1696 contains at least one character not in the delete set. Store
1697 in the array BUF, all characters from that buffer that are not
1698 in the delete set, and return the number of characters saved
1702 read_and_delete (unsigned char *buf, long int size, PFI not_used)
1705 static int hit_eof = 0;
1707 assert (not_used == NULL);
1713 /* This enclosing do-while loop is to make sure that
1714 we don't return zero (indicating EOF) when we've
1715 just deleted all the characters in a buffer. */
1719 int nr = safe_read (0, (char *) buf, size);
1722 error (EXIT_FAILURE, errno, _("read error"));
1729 /* This first loop may be a waste of code, but gives much
1730 better performance when no characters are deleted in
1731 the beginning of a buffer. It just avoids the copying
1732 of buf[i] into buf[n_saved] when it would be a NOP. */
1734 for (i = 0; i < nr && !in_delete_set[buf[i]]; i++)
1738 for (++i; i < nr; i++)
1739 if (!in_delete_set[buf[i]])
1740 buf[n_saved++] = buf[i];
1742 while (n_saved == 0);
1747 /* Read at most SIZE bytes from stdin into the array BUF. Then
1748 perform the in-place and one-to-one mapping specified by the global
1749 array `xlate'. Return the number of characters read, or 0 upon EOF. */
1752 read_and_xlate (unsigned char *buf, long int size, PFI not_used)
1754 long chars_read = 0;
1755 static int hit_eof = 0;
1758 assert (not_used == NULL);
1764 chars_read = safe_read (0, (char *) buf, size);
1766 error (EXIT_FAILURE, errno, _("read error"));
1767 if (chars_read == 0)
1773 for (i = 0; i < chars_read; i++)
1774 buf[i] = xlate[buf[i]];
1779 /* Initialize a boolean membership set IN_SET with the character
1780 values obtained by traversing the linked list of constructs S
1781 using the function `get_next'. If COMPLEMENT_THIS_SET is
1782 nonzero the resulting set is complemented. */
1785 set_initialize (struct Spec_list *s, int complement_this_set, SET_TYPE *in_set)
1790 memset (in_set, 0, N_CHARS * sizeof (in_set[0]));
1791 s->state = BEGIN_STATE;
1792 while ((c = get_next (s, NULL)) != -1)
1794 if (complement_this_set)
1795 for (i = 0; i < N_CHARS; i++)
1796 in_set[i] = (!in_set[i]);
1800 main (int argc, char **argv)
1803 int non_option_args;
1804 struct Spec_list buf1, buf2;
1805 struct Spec_list *s1 = &buf1;
1806 struct Spec_list *s2 = &buf2;
1808 program_name = argv[0];
1809 setlocale (LC_ALL, "");
1810 bindtextdomain (PACKAGE, LOCALEDIR);
1811 textdomain (PACKAGE);
1813 while ((c = getopt_long (argc, argv, "cdst", long_options, NULL)) != -1)
1829 squeeze_repeats = 1;
1844 printf ("tr (%s) %s\n", GNU_PACKAGE, VERSION);
1845 exit (EXIT_SUCCESS);
1851 posix_pedantic = (getenv ("POSIXLY_CORRECT") != NULL);
1853 non_option_args = argc - optind;
1854 translating = (non_option_args == 2 && !delete);
1856 /* Change this test if it is valid to give tr no options and
1857 no args at all. POSIX doesn't specifically say anything
1858 either way, but it looks like they implied it's invalid
1859 by omission. If you want to make tr do a slow imitation
1860 of `cat' use `tr a a'. */
1861 if (non_option_args > 2)
1863 error (0, 0, _("too many arguments"));
1867 if (!delete && !squeeze_repeats && non_option_args != 2)
1868 error (EXIT_FAILURE, 0, _("two strings must be given when translating"));
1870 if (delete && squeeze_repeats && non_option_args != 2)
1871 error (EXIT_FAILURE, 0, _("two strings must be given when both \
1872 deleting and squeezing repeats"));
1874 /* If --delete is given without --squeeze-repeats, then
1875 only one string argument may be specified. But POSIX
1876 says to ignore any string2 in this case, so if POSIXLY_CORRECT
1877 is set, pretend we never saw string2. But I think
1878 this deserves a fatal error, so that's the default. */
1879 if ((delete && !squeeze_repeats) && non_option_args != 1)
1881 if (posix_pedantic && non_option_args == 2)
1884 error (EXIT_FAILURE, 0,
1885 _("only one string may be given when deleting \
1886 without squeezing repeats"));
1889 if (squeeze_repeats && non_option_args == 0)
1890 error (EXIT_FAILURE, 0,
1891 _("at least one string must be given when squeezing repeats"));
1894 if (parse_str ((unsigned char *) argv[optind], s1))
1895 exit (EXIT_FAILURE);
1897 if (non_option_args == 2)
1900 if (parse_str ((unsigned char *) argv[optind + 1], s2))
1901 exit (EXIT_FAILURE);
1908 if (squeeze_repeats && non_option_args == 1)
1910 set_initialize (s1, complement, in_squeeze_set);
1911 squeeze_filter (io_buf, IO_BUF_SIZE, NULL);
1913 else if (delete && non_option_args == 1)
1917 set_initialize (s1, complement, in_delete_set);
1920 nr = read_and_delete (io_buf, IO_BUF_SIZE, NULL);
1921 if (nr > 0 && fwrite ((char *) io_buf, 1, nr, stdout) == 0)
1922 error (EXIT_FAILURE, errno, _("write error"));
1926 else if (squeeze_repeats && delete && non_option_args == 2)
1928 set_initialize (s1, complement, in_delete_set);
1929 set_initialize (s2, 0, in_squeeze_set);
1930 squeeze_filter (io_buf, IO_BUF_SIZE, (PFI) read_and_delete);
1932 else if (translating)
1937 SET_TYPE *in_s1 = in_delete_set;
1939 set_initialize (s1, 0, in_s1);
1940 s2->state = BEGIN_STATE;
1941 for (i = 0; i < N_CHARS; i++)
1943 for (i = 0; i < N_CHARS; i++)
1947 int ch = get_next (s2, NULL);
1948 assert (ch != -1 || truncate_set1);
1951 /* This will happen when tr is invoked like e.g.
1952 tr -cs A-Za-z0-9 '\012'. */
1958 assert (get_next (s2, NULL) == -1 || truncate_set1);
1964 enum Upper_Lower_class class_s1;
1965 enum Upper_Lower_class class_s2;
1967 for (i = 0; i < N_CHARS; i++)
1969 s1->state = BEGIN_STATE;
1970 s2->state = BEGIN_STATE;
1973 c1 = get_next (s1, &class_s1);
1974 c2 = get_next (s2, &class_s2);
1975 if (!class_ok[(int) class_s1][(int) class_s2])
1976 error (EXIT_FAILURE, 0,
1977 _("misaligned [:upper:] and/or [:lower:] construct"));
1979 if (class_s1 == UL_LOWER && class_s2 == UL_UPPER)
1981 for (i = 0; i < N_CHARS; i++)
1983 xlate[i] = toupper (i);
1985 else if (class_s1 == UL_UPPER && class_s2 == UL_LOWER)
1987 for (i = 0; i < N_CHARS; i++)
1989 xlate[i] = tolower (i);
1991 else if ((class_s1 == UL_LOWER && class_s2 == UL_LOWER)
1992 || (class_s1 == UL_UPPER && class_s2 == UL_UPPER))
1994 /* By default, GNU tr permits the identity mappings: from
1995 [:upper:] to [:upper:] and [:lower:] to [:lower:]. But
1996 when POSIXLY_CORRECT is set, those evoke diagnostics. */
1999 error (EXIT_FAILURE, 0,
2001 invalid identity mapping; when translating, any [:lower:] or [:upper:]\n\
2002 construct in string1 must be aligned with a corresponding construct\n\
2003 ([:upper:] or [:lower:], respectively) in string2"));
2008 /* The following should have been checked by validate... */
2009 if (c1 == -1 || c2 == -1)
2014 assert (c1 == -1 || truncate_set1);
2016 if (squeeze_repeats)
2018 set_initialize (s2, 0, in_squeeze_set);
2019 squeeze_filter (io_buf, IO_BUF_SIZE, (PFI) read_and_xlate);
2027 chars_read = read_and_xlate (io_buf, IO_BUF_SIZE, NULL);
2029 && fwrite ((char *) io_buf, 1, chars_read, stdout) == 0)
2030 error (EXIT_FAILURE, errno, _("write error"));
2032 while (chars_read > 0);
2036 if (fclose (stdout) == EOF)
2037 error (EXIT_FAILURE, errno, _("write error"));
2040 error (EXIT_FAILURE, errno, _("standard input"));
2042 exit (EXIT_SUCCESS);