1 /* tr -- a filter to translate characters
2 Copyright (C) 1991, 1995 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; either version 2, or (at your option)
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. */
18 /* Written by Jim Meyering, meyering@cs.utexas.edu. */
22 /* Get isblank from GNU libc. */
28 #include <sys/types.h>
36 #define ULONG_MAX ((unsigned long) ~(unsigned long) 0)
40 #define LONG_MAX ((long int) (ULONG_MAX >> 1))
44 #define UCHAR_MAX 0xFF
47 #define N_CHARS (UCHAR_MAX + 1)
49 /* A pointer to a function that returns an int. */
50 typedef int (*PFI) ();
52 /* Convert from character C to its index in the collating
53 sequence array. Just cast to an unsigned int to avoid
54 problems with sign-extension. */
55 #define ORD(c) (unsigned int)(c)
57 /* The inverse of ORD. */
58 #define CHR(i) (unsigned char)(i)
60 /* The value for Spec_list->state that indicates to
61 get_next that it should initialize the tail pointer.
62 Its value doesn't matter as long as it can't be
63 confused with a valid character code. */
64 #define BEGIN_STATE (2 * N_CHARS)
66 /* The value for Spec_list->state that indicates to
67 get_next that the element pointed to by Spec_list->tail is
68 being considered for the first time on this pass through the
69 list -- it indicates that get_next should make any necessary
71 #define NEW_ELEMENT (BEGIN_STATE + 1)
73 /* A value distinct from any character that may have been stored in a
74 buffer as the result of a block-read in the function squeeze_filter. */
75 #define NOT_A_CHAR (unsigned int)(-1)
77 /* The following (but not CC_NO_CLASS) are indices into the array of
78 valid character class strings. */
81 CC_ALNUM = 0, CC_ALPHA = 1, CC_BLANK = 2, CC_CNTRL = 3,
82 CC_DIGIT = 4, CC_GRAPH = 5, CC_LOWER = 6, CC_PRINT = 7,
83 CC_PUNCT = 8, CC_SPACE = 9, CC_UPPER = 10, CC_XDIGIT = 11,
87 /* Character class to which a character (returned by get_next) belonged;
88 but it is set only if the construct from which the character was obtained
89 was one of the character classes [:upper:] or [:lower:]. The value
90 is used only when translating and then, only to make sure that upper
91 and lower class constructs have the same relative positions in string1
93 enum Upper_Lower_class
100 /* A shortcut to ensure that when constructing the translation array,
101 one of the values returned by paired calls to get_next (from s1 and s2)
102 is from [:upper:] and the other is from [:lower:], or neither is from
103 upper or lower. In fact, no other character classes are allowed when
104 translating, but that condition is tested elsewhere. This array is
105 indexed by values of type enum Upper_Lower_class. */
106 static int const class_ok[3][3] =
113 /* The type of a List_element. See build_spec_list for more details. */
114 enum Range_element_type
124 /* One construct in one of tr's argument strings.
125 For example, consider the POSIX version of the classic tr command:
126 tr -cs 'a-zA-Z_' '[\n*]'
127 String1 has 3 constructs, two of which are ranges (a-z and A-Z),
128 and a single normal character, `_'. String2 has one construct. */
131 enum Range_element_type type;
132 struct List_element *next;
138 unsigned int first_char;
139 unsigned int last_char;
142 enum Char_class char_class;
146 unsigned int the_repeated_char;
154 /* Each of tr's argument strings is parsed into a form that is easier
155 to work with: a linked list of constructs (struct List_element).
156 Each Spec_list structure also encapsulates various attributes of
157 the corresponding argument string. The attributes are used mainly
158 to verify that the strings are valid in the context of any options
159 specified (like -s, -d, or -c). The main exception is the member
160 `tail', which is first used to construct the list. After construction,
161 it is used by get_next to save its state when traversing the list.
162 The member `state' serves a similar function. */
165 /* Points to the head of the list of range elements.
166 The first struct is a dummy; its members are never used. */
167 struct List_element *head;
169 /* When appending, points to the last element. When traversing via
170 get_next(), points to the element to process next. Setting
171 Spec_list.state to the value BEGIN_STATE before calling get_next
172 signals get_next to initialize tail to point to head->next. */
173 struct List_element *tail;
175 /* Used to save state between calls to get_next(). */
178 /* Length, in the sense that length('a-z[:digit:]123abc')
179 is 42 ( = 26 + 10 + 6). */
182 /* The number of [c*] and [c*0] constructs that appear in this spec. */
183 int n_indefinite_repeats;
185 /* Non-zero if this spec contains at least one equivalence
186 class construct e.g. [=c=]. */
189 /* Non-zero if this spec contains at least one of [:upper:] or
190 [:lower:] class constructs. */
191 int has_upper_or_lower;
193 /* Non-zero if this spec contains at least one of the character class
194 constructs (all but upper and lower) that aren't allowed in s2. */
195 int has_restricted_char_class;
202 /* The name by which this program was run. */
205 /* When non-zero, each sequence in the input of a repeated character
206 (call it c) is replaced (in the output) by a single occurrence of c
207 for every c in the squeeze set. */
208 static int squeeze_repeats = 0;
210 /* When non-zero, removes characters in the delete set from input. */
211 static int delete = 0;
213 /* Use the complement of set1 in place of set1. */
214 static int complement = 0;
216 /* When non-zero, this flag causes GNU tr to provide strict
217 compliance with POSIX draft 1003.2.11.2. The POSIX spec
218 says that when -d is used without -s, string2 (if present)
219 must be ignored. Silently ignoring arguments is a bad idea.
220 The default GNU behavior is to give a usage message and exit.
221 Additionally, when this flag is non-zero, tr prints warnings
222 on stderr if it is being used in a manner that is not portable.
223 Applicable warnings are given by default, but are suppressed
224 if the environment variable `POSIXLY_CORRECT' is set, since
225 being POSIX conformant means we can't issue such messages.
226 Warnings on the following topics are suppressed when this
227 variable is non-zero:
228 1. Ambiguous octal escapes. */
229 static int posix_pedantic;
231 /* When tr is performing translation and string1 is longer than string2,
232 POSIX says that the result is undefined. That gives the implementor
233 of a POSIX conforming version of tr two reasonable choices for the
234 semantics of this case.
236 * The BSD tr pads string2 to the length of string1 by
237 repeating the last character in string2.
239 * System V tr ignores characters in string1 that have no
240 corresponding character in string2. That is, string1 is effectively
241 truncated to the length of string2.
243 When non-zero, this flag causes GNU tr to imitate the behavior
244 of System V tr when translating with string1 longer than string2.
245 The default is to emulate BSD tr. This flag is ignored in modes where
246 no translation is performed. Emulating the System V tr
247 in this exceptional case causes the relatively common BSD idiom:
249 tr -cs A-Za-z0-9 '\012'
251 to break (it would convert only zero bytes, rather than all
252 non-alphanumerics, to newlines).
254 WARNING: This switch does not provide general BSD or System V
255 compatibility. For example, it doesn't disable the interpretation
256 of the POSIX constructs [:alpha:], [=c=], and [c*10], so if by
257 some unfortunate coincidence you use such constructs in scripts
258 expecting to use some other version of tr, the scripts will break. */
259 static int truncate_set1 = 0;
261 /* An alias for (!delete && non_option_args == 2).
262 It is set in main and used there and in validate(). */
263 static int translating;
269 #define IO_BUF_SIZE BUFSIZ
270 static unsigned char io_buf[IO_BUF_SIZE];
272 static char const *const char_class_name[] =
274 "alnum", "alpha", "blank", "cntrl", "digit", "graph",
275 "lower", "print", "punct", "space", "upper", "xdigit"
277 #define N_CHAR_CLASSES (sizeof(char_class_name) / sizeof(char_class_name[0]))
279 typedef char SET_TYPE;
281 /* Array of boolean values. A character `c' is a member of the
282 squeeze set if and only if in_squeeze_set[c] is true. The squeeze
283 set is defined by the last (possibly, the only) string argument
284 on the command line when the squeeze option is given. */
285 static SET_TYPE in_squeeze_set[N_CHARS];
287 /* Array of boolean values. A character `c' is a member of the
288 delete set if and only if in_delete_set[c] is true. The delete
289 set is defined by the first (or only) string argument on the
290 command line when the delete option is given. */
291 static SET_TYPE in_delete_set[N_CHARS];
293 /* Array of character values defining the translation (if any) that
294 tr is to perform. Translation is performed only when there are
295 two specification strings and the delete switch is not given. */
296 static char xlate[N_CHARS];
298 /* If non-zero, display usage information and exit. */
299 static int show_help;
301 /* If non-zero, print the version on standard output then exit. */
302 static int show_version;
304 static struct option const long_options[] =
306 {"complement", no_argument, NULL, 'c'},
307 {"delete", no_argument, NULL, 'd'},
308 {"squeeze-repeats", no_argument, NULL, 's'},
309 {"truncate-set1", no_argument, NULL, 't'},
310 {"help", no_argument, &show_help, 1},
311 {"version", no_argument, &show_version, 1},
320 fprintf (stderr, "Try `%s --help' for more information.\n",
325 Usage: %s [OPTION]... SET1 [SET2]\n\
329 Translate, squeeze, and/or delete characters from standard input,\n\
330 writing to standard output.\n\
332 -c, --complement first complement SET1\n\
333 -d, --delete delete characters in SET1, do not translate\n\
334 -s, --squeeze-repeats replace sequence of characters with one\n\
335 -t, --truncate-set1 first truncate SET1 to length of SET2\n\
336 --help display this help and exit\n\
337 --version output version information and exit\n\
341 SETs are specified as strings of characters. Most represent themselves.\n\
342 Interpreted sequences are:\n\
344 \\NNN character with octal value NNN (1 to 3 octal digits)\n\
351 \\t horizontal tab\n\
353 CHAR1-CHAR2 all characters from CHAR1 to CHAR2 in ascending order\n\
354 [CHAR1-CHAR2] same as CHAR1-CHAR2, if both SET1 and SET2 use this\n\
355 [CHAR*] in SET2, copies of CHAR until length of SET1\n\
356 [CHAR*REPEAT] REPEAT copies of CHAR, REPEAT octal if starting with 0\n\
357 [:alnum:] all letters and digits\n\
358 [:alpha:] all letters\n\
359 [:blank:] all horizontal whitespace\n\
360 [:cntrl:] all control characters\n\
361 [:digit:] all digits\n\
362 [:graph:] all printable characters, not including space\n\
363 [:lower:] all lower case letters\n\
364 [:print:] all printable characters, including space\n\
365 [:punct:] all punctuation characters\n\
366 [:space:] all horizontal or vertical whitespace\n\
367 [:upper:] all upper case letters\n\
368 [:xdigit:] all hexadecimal digits\n\
369 [=CHAR=] all characters which are equivalent to CHAR\n\
373 Translation occurs if -d is not given and both SET1 and SET2 appear.\n\
374 -t may be used only when translating. SET2 is extended to length of\n\
375 SET1 by repeating its last character as necessary. Excess characters\n\
376 of SET2 are ignored. Only [:lower:] and [:upper:] are guaranteed to\n\
377 expand in ascending order; used in SET2 while translating, they may\n\
378 only be used in pairs to specify case conversion. -s uses SET1 if not\n\
379 translating nor deleting; else squeezing uses SET2 and occurs after\n\
380 translation or deletion.\n\
386 /* Return non-zero if the character C is a member of the
387 equivalence class containing the character EQUIV_CLASS. */
390 is_equiv_class_member (equiv_class, c)
391 unsigned int equiv_class;
394 return (equiv_class == c);
397 /* Return non-zero if the character C is a member of the
398 character class CHAR_CLASS. */
401 is_char_class_member (char_class, c)
402 enum Char_class char_class;
449 /* Perform the first pass over each range-spec argument S, converting all
450 \c and \ddd escapes to their one-byte representations. The conversion
451 is done in-place, so S must point to writable storage. If an invalid
452 quote sequence is found print an error message and return non-zero.
453 Otherwise set *LEN to the length of the resulting string and return
454 zero. The resulting array of characters may contain zero-bytes;
455 however, on input, S is assumed to be null-terminated, and hence
456 cannot contain actual (non-escaped) zero bytes. */
466 for (i = 0; s[i]; i++)
508 oct_digit = s[i + 2] - '0';
509 if (0 <= oct_digit && oct_digit <= 7)
511 c = 8 * c + oct_digit;
513 oct_digit = s[i + 2] - '0';
514 if (0 <= oct_digit && oct_digit <= 7)
516 if (8 * c + oct_digit < N_CHARS)
518 c = 8 * c + oct_digit;
521 else if (!posix_pedantic)
523 /* Any octal number larger than 0377 won't
524 fit in 8 bits. So we stop when adding the
525 next digit would put us over the limit and
526 give a warning about the ambiguity. POSIX
527 isn't clear on this, but one person has said
528 that in his interpretation, POSIX says tr
529 can't even give a warning. */
530 error (0, 0, "warning: the ambiguous octal escape \
531 \\%c%c%c is being\n\tinterpreted as the 2-byte sequence \\0%c%c, `%c'",
532 s[i], s[i + 1], s[i + 2],
533 s[i], s[i + 1], s[i + 2]);
539 error (0, 0, "invalid backslash escape at end of string");
543 error (0, 0, "invalid backslash escape `\\%c'", s[i + 1]);
559 /* If CLASS_STR is a valid character class string, return its index
560 in the global char_class_name array. Otherwise, return CC_NO_CLASS. */
562 static enum Char_class
563 look_up_char_class (class_str)
564 unsigned char *class_str;
568 for (i = 0; i < N_CHAR_CLASSES; i++)
569 if (strcmp ((const char *) class_str, char_class_name[i]) == 0)
570 return (enum Char_class) i;
574 /* Return a newly allocated string with a printable version of C.
575 This function is used solely for formatting error messages. */
578 make_printable_char (c)
581 char *buf = xmalloc (5);
583 assert (c < N_CHARS);
591 sprintf (buf, "\\%03o", c);
596 /* Return a newly allocated copy of S which is suitable for printing.
597 LEN is the number of characters in S. Most non-printing
598 (isprint) characters are represented by a backslash followed by
599 3 octal digits. However, the characters represented by \c escapes
600 where c is one of [abfnrtv] are represented by their 2-character \c
601 sequences. This function is used solely for printing error messages. */
604 make_printable_str (s, len)
605 const unsigned char *s;
608 /* Worst case is that every character expands to a backslash
609 followed by a 3-character octal escape sequence. */
610 char *printable_buf = xmalloc (4 * len + 1);
611 char *p = printable_buf;
614 for (i = 0; i < len; i++)
652 sprintf (buf, "\\%03o", s[i]);
658 return printable_buf;
661 /* Append a newly allocated structure representing a
662 character C to the specification list LIST. */
665 append_normal_char (list, c)
666 struct Spec_list *list;
669 struct List_element *new;
671 new = (struct List_element *) xmalloc (sizeof (struct List_element));
673 new->type = RE_NORMAL_CHAR;
674 new->u.normal_char = c;
676 list->tail->next = new;
680 /* Append a newly allocated structure representing the range
681 of characters from FIRST to LAST to the specification list LIST.
682 Return non-zero if LAST precedes FIRST in the collating sequence,
683 zero otherwise. This means that '[c-c]' is acceptable. */
686 append_range (list, first, last)
687 struct Spec_list *list;
691 struct List_element *new;
693 if (ORD (first) > ORD (last))
695 char *tmp1 = make_printable_char (first);
696 char *tmp2 = make_printable_char (last);
699 "range-endpoints of `%s-%s' are in reverse collating sequence order",
705 new = (struct List_element *) xmalloc (sizeof (struct List_element));
707 new->type = RE_RANGE;
708 new->u.range.first_char = first;
709 new->u.range.last_char = last;
711 list->tail->next = new;
716 /* If CHAR_CLASS_STR is a valid character class string, append a
717 newly allocated structure representing that character class to the end
718 of the specification list LIST and return 0. If CHAR_CLASS_STR is not
719 a valid string, print an error message and return non-zero. */
722 append_char_class (list, char_class_str, len)
723 struct Spec_list *list;
724 unsigned char *char_class_str;
727 enum Char_class char_class;
728 struct List_element *new;
730 char_class = look_up_char_class (char_class_str);
731 if (char_class == CC_NO_CLASS)
733 char *tmp = make_printable_str (char_class_str, len);
735 error (0, 0, "invalid character class `%s'", tmp);
739 new = (struct List_element *) xmalloc (sizeof (struct List_element));
741 new->type = RE_CHAR_CLASS;
742 new->u.char_class = char_class;
744 list->tail->next = new;
749 /* Append a newly allocated structure representing a [c*n]
750 repeated character construct to the specification list LIST.
751 THE_CHAR is the single character to be repeated, and REPEAT_COUNT
752 is a non-negative repeat count. */
755 append_repeated_char (list, the_char, repeat_count)
756 struct Spec_list *list;
757 unsigned int the_char;
758 long int repeat_count;
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, issue an error message and return non-zero. */
779 append_equiv_class (list, equiv_class_str, len)
780 struct Spec_list *list;
781 unsigned char *equiv_class_str;
784 struct List_element *new;
788 char *tmp = make_printable_str (equiv_class_str, len);
790 error (0, 0, "%s: equivalence class operand must be a single character",
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 (p, first_idx, last_idx)
811 const unsigned char *p;
815 int len = last_idx - first_idx + 1;
816 unsigned char *tmp = (unsigned char *) xmalloc (len);
818 assert (first_idx <= last_idx);
819 /* Use memcpy rather than strncpy because `p' may contain zero-bytes. */
820 memcpy (tmp, p + first_idx, len);
824 /* Search forward starting at START_IDX for the 2-char sequence
825 (PRE_BRACKET_CHAR,']') in the string P of length P_LEN. If such
826 a sequence is found, return the index of the first character,
827 otherwise return -1. P may contain zero bytes. */
830 find_closing_delim (p, start_idx, p_len, pre_bracket_char)
831 const unsigned char *p;
834 unsigned int pre_bracket_char;
838 for (i = start_idx; i < p_len - 1; i++)
839 if (p[i] == pre_bracket_char && p[i + 1] == ']')
844 /* Convert a string S with explicit length LEN, possibly
845 containing embedded zero bytes, to a long integer value.
846 If the string represents a negative value, a value larger
847 than LONG_MAX, or if all LEN characters do not represent a
848 valid integer, return non-zero and do not modify *VAL.
849 Otherwise, return zero and set *VAL to the converted value. */
852 non_neg_strtol (s, len, val)
853 const unsigned char *s;
865 else if (ISDIGIT (s[0]))
870 for (i = 0; i < len; i++)
874 if (c >= base || c < 0)
876 if (i > 8 && sum > (LONG_MAX - c) / base)
878 sum = sum * base + c;
884 /* Parse the bracketed repeat-char syntax. If the P_LEN characters
885 beginning with P[ START_IDX ] comprise a valid [c*n] construct,
886 return the character and the repeat count through the arg pointers,
887 CHAR_TO_REPEAT and N, and then return the index of the closing
888 bracket as the function value. If the second character following
889 the opening bracket is not `*' or if no closing bracket can be
890 found, return -1. If a closing bracket is found and the
891 second char is `*', but the string between the `*' and `]' isn't
892 empty, an octal number, or a decimal number, print an error message
896 find_bracketed_repeat (p, start_idx, p_len, char_to_repeat, n)
897 const unsigned char *p;
900 unsigned int *char_to_repeat;
905 assert (start_idx + 1 < p_len);
906 if (p[start_idx + 1] != '*')
909 for (i = start_idx + 2; i < p_len; i++)
913 const unsigned char *digit_str;
914 int digit_str_len = i - start_idx - 2;
916 *char_to_repeat = p[start_idx];
917 if (digit_str_len == 0)
919 /* We've matched [c*] -- no explicit repeat count. */
924 /* Here, we have found [c*s] where s should be a string
925 of octal or decimal digits. */
926 digit_str = &p[start_idx + 2];
927 if (non_neg_strtol (digit_str, digit_str_len, n))
929 char *tmp = make_printable_str (digit_str, digit_str_len);
930 error (0, 0, "invalid repeat count `%s' in [c*n] construct", tmp);
937 return -1; /* No bracket found. */
940 /* Convert string UNESACPED_STRING (which has been preprocessed to
941 convert backslash-escape sequences) of length LEN characters into
942 a linked list of the following 5 types of constructs:
943 - [:str:] Character class where `str' is one of the 12 valid strings.
944 - [=c=] Equivalence class where `c' is any single character.
945 - [c*n] Repeat the single character `c' `n' times. n may be omitted.
946 However, if `n' is present, it must be a non-negative octal or
948 - r-s Range of characters from `r' to `s'. The second endpoint must
949 not precede the first in the current collating sequence.
950 - c Any other character is interpreted as itself. */
953 build_spec_list (unescaped_string, len, result)
954 const unsigned char *unescaped_string;
956 struct Spec_list *result;
958 const unsigned char *p;
961 p = unescaped_string;
963 /* The main for-loop below recognizes the 4 multi-character constructs.
964 A character that matches (in its context) none of the multi-character
965 constructs is classified as `normal'. Since all multi-character
966 constructs have at least 3 characters, any strings of length 2 or
967 less are composed solely of normal characters. Hence, the index of
968 the outer for-loop runs only as far as LEN-2. */
970 for (i = 0; i < len - 2;)
979 int closing_delim_idx;
980 int closing_bracket_idx;
981 unsigned int char_to_repeat;
985 closing_delim_idx = find_closing_delim (p, i + 2, len, p[i + 1]);
986 if (closing_delim_idx >= 0)
989 unsigned char *opnd_str = substr (p, i + 2,
990 closing_delim_idx - 1);
992 parse_failed = append_char_class (result, opnd_str,
993 (closing_delim_idx - 1) - (i + 2) + 1);
995 parse_failed = append_equiv_class (result, opnd_str,
996 (closing_delim_idx - 1) - (i + 2) + 1);
999 /* Return non-zero if append_*_class reports a problem. */
1003 i = closing_delim_idx + 2;
1006 /* Else fall through. This could be [:*] or [=*]. */
1008 /* Determine whether this is a bracketed repeat range
1009 matching the RE \[.\*(dec_or_oct_number)?\]. */
1010 closing_bracket_idx = find_bracketed_repeat (p, i + 1,
1011 len, &char_to_repeat, &repeat_count);
1012 if (closing_bracket_idx >= 0)
1014 append_repeated_char (result, char_to_repeat, repeat_count);
1015 i = closing_bracket_idx + 1;
1018 else if (closing_bracket_idx == -1)
1023 /* Found a string that looked like [c*n] but the
1024 numeric part was invalid. */
1031 /* Here if we've tried to match [c*n], [:str:], and [=c=]
1032 and none of them fit. So we still have to consider the
1033 range `[-c' (from `[' to `c'). */
1035 /* Look ahead one char for ranges like a-z. */
1036 if (p[i + 1] == '-')
1038 if (append_range (result, p[i], p[i + 2]))
1044 append_normal_char (result, p[i]);
1051 /* Now handle the (2 or fewer) remaining characters p[i]..p[len - 1]. */
1052 for (; i < len; i++)
1053 append_normal_char (result, p[i]);
1058 /* Given a Spec_list S (with its saved state implicit in the values
1059 of its members `tail' and `state'), return the next single character
1060 in the expansion of S's constructs. If the last character of S was
1061 returned on the previous call or if S was empty, this function
1062 returns -1. For example, successive calls to get_next where S
1063 represents the spec-string 'a-d[y*3]' will return the sequence
1064 of values a, b, c, d, y, y, y, -1. Finally, if the construct from
1065 which the returned character comes is [:upper:] or [:lower:], the
1066 parameter CLASS is given a value to indicate which it was. Otherwise
1067 CLASS is set to UL_NONE. This value is used only when constructing
1068 the translation table to verify that any occurrences of upper and
1069 lower class constructs in the spec-strings appear in the same relative
1074 struct Spec_list *s;
1075 enum Upper_Lower_class *class;
1077 struct List_element *p;
1084 if (s->state == BEGIN_STATE)
1086 s->tail = s->head->next;
1087 s->state = NEW_ELEMENT;
1096 case RE_NORMAL_CHAR:
1097 return_val = p->u.normal_char;
1098 s->state = NEW_ELEMENT;
1103 if (s->state == NEW_ELEMENT)
1104 s->state = ORD (p->u.range.first_char);
1107 return_val = CHR (s->state);
1108 if (s->state == ORD (p->u.range.last_char))
1111 s->state = NEW_ELEMENT;
1116 if (s->state == NEW_ELEMENT)
1118 for (i = 0; i < N_CHARS; i++)
1119 if (is_char_class_member (p->u.char_class, i))
1121 assert (i < N_CHARS);
1124 assert (is_char_class_member (p->u.char_class, s->state));
1125 return_val = CHR (s->state);
1126 for (i = s->state + 1; i < N_CHARS; i++)
1127 if (is_char_class_member (p->u.char_class, i))
1134 s->state = NEW_ELEMENT;
1138 switch (p->u.char_class)
1153 case RE_EQUIV_CLASS:
1154 /* FIXME: this assumes that each character is alone in its own
1155 equivalence class (which appears to be correct for my
1156 LC_COLLATE. But I don't know of any function that allows
1157 one to determine a character's equivalence class. */
1159 return_val = p->u.equiv_code;
1160 s->state = NEW_ELEMENT;
1164 case RE_REPEATED_CHAR:
1165 /* Here, a repeat count of n == 0 means don't repeat at all. */
1166 assert (p->u.repeated_char.repeat_count >= 0);
1167 if (p->u.repeated_char.repeat_count == 0)
1170 s->state = NEW_ELEMENT;
1171 return_val = get_next (s, class);
1175 if (s->state == NEW_ELEMENT)
1180 return_val = p->u.repeated_char.the_repeated_char;
1181 if (p->u.repeated_char.repeat_count > 0
1182 && s->state == p->u.repeated_char.repeat_count)
1185 s->state = NEW_ELEMENT;
1202 /* This is a minor kludge. This function is called from
1203 get_spec_stats to determine the cardinality of a set derived
1204 from a complemented string. It's a kludge in that some of the
1205 same operations are (duplicated) performed in set_initialize. */
1208 card_of_complement (s)
1209 struct Spec_list *s;
1212 int cardinality = N_CHARS;
1213 SET_TYPE in_set[N_CHARS];
1215 memset (in_set, 0, N_CHARS * sizeof (in_set[0]));
1216 s->state = BEGIN_STATE;
1217 while ((c = get_next (s, NULL)) != -1)
1223 /* Gather statistics about the spec-list S in preparation for the tests
1224 in validate that determine the consistency of the specs. This function
1225 is called at most twice; once for string1, and again for any string2.
1226 LEN_S1 < 0 indicates that this is the first call and that S represents
1227 string1. When LEN_S1 >= 0, it is the length of the expansion of the
1228 constructs in string1, and we can use its value to resolve any
1229 indefinite repeat construct in S (which represents string2). Hence,
1230 this function has the side-effect that it converts a valid [c*]
1231 construct in string2 to [c*n] where n is large enough (or 0) to give
1232 string2 the same length as string1. For example, with the command
1233 tr a-z 'A[\n*]Z' on the second call to get_spec_stats, LEN_S1 would
1234 be 26 and S (representing string2) would be converted to 'A[\n*24]Z'. */
1237 get_spec_stats (s, len_s1)
1238 struct Spec_list *s;
1241 struct List_element *p;
1242 struct List_element *indefinite_repeat_element = NULL;
1245 s->n_indefinite_repeats = 0;
1246 s->has_equiv_class = 0;
1247 s->has_restricted_char_class = 0;
1248 s->has_upper_or_lower = 0;
1249 for (p = s->head->next; p; p = p->next)
1254 case RE_NORMAL_CHAR:
1259 assert (p->u.range.last_char >= p->u.range.first_char);
1260 len += p->u.range.last_char - p->u.range.first_char + 1;
1264 for (i = 0; i < N_CHARS; i++)
1265 if (is_char_class_member (p->u.char_class, i))
1267 switch (p->u.char_class)
1271 s->has_upper_or_lower = 1;
1274 s->has_restricted_char_class = 1;
1279 case RE_EQUIV_CLASS:
1280 for (i = 0; i < N_CHARS; i++)
1281 if (is_equiv_class_member (p->u.equiv_code, i))
1283 s->has_equiv_class = 1;
1286 case RE_REPEATED_CHAR:
1287 if (p->u.repeated_char.repeat_count > 0)
1288 len += p->u.repeated_char.repeat_count;
1289 else if (p->u.repeated_char.repeat_count == 0)
1291 indefinite_repeat_element = p;
1292 ++(s->n_indefinite_repeats);
1302 if (len_s1 >= len && s->n_indefinite_repeats == 1)
1304 indefinite_repeat_element->u.repeated_char.repeat_count = len_s1 - len;
1307 if (complement && len_s1 < 0)
1308 s->length = card_of_complement (s);
1315 spec_init (spec_list)
1316 struct Spec_list *spec_list;
1318 spec_list->head = spec_list->tail =
1319 (struct List_element *) xmalloc (sizeof (struct List_element));
1320 spec_list->head->next = NULL;
1323 /* This function makes two passes over the argument string S. The first
1324 one converts all \c and \ddd escapes to their one-byte representations.
1325 The second constructs a linked specification list, SPEC_LIST, of the
1326 characters and constructs that comprise the argument string. If either
1327 of these passes detects an error, this function returns non-zero. */
1330 parse_str (s, spec_list)
1332 struct Spec_list *spec_list;
1336 if (unquote (s, &len))
1338 if (build_spec_list (s, len, spec_list))
1343 /* Given two specification lists, S1 and S2, and assuming that
1344 S1->length > S2->length, append a single [c*n] element to S2 where c
1345 is the last character in the expansion of S2 and n is the difference
1346 between the two lengths.
1347 Upon successful completion, S2->length is set to S1->length. The only
1348 way this function can fail to make S2 as long as S1 is when S2 has
1349 zero-length, since in that case, there is no last character to repeat.
1350 So S2->length is required to be at least 1.
1352 Providing this functionality allows the user to do some pretty
1353 non-BSD (and non-portable) things: For example, the command
1354 tr -cs '[:upper:]0-9' '[:lower:]'
1355 is almost guaranteed to give results that depend on your collating
1359 string2_extend (s1, s2)
1360 const struct Spec_list *s1;
1361 struct Spec_list *s2;
1363 struct List_element *p;
1367 assert (translating);
1368 assert (s1->length > s2->length);
1369 assert (s2->length > 0);
1374 case RE_NORMAL_CHAR:
1375 char_to_repeat = p->u.normal_char;
1378 char_to_repeat = p->u.range.last_char;
1381 for (i = N_CHARS; i >= 0; i--)
1382 if (is_char_class_member (p->u.char_class, i))
1385 char_to_repeat = CHR (i);
1388 case RE_REPEATED_CHAR:
1389 char_to_repeat = p->u.repeated_char.the_repeated_char;
1392 case RE_EQUIV_CLASS:
1393 /* This shouldn't happen, because validate exits with an error
1394 if it finds an equiv class in string2 when translating. */
1407 append_repeated_char (s2, char_to_repeat, s1->length - s2->length);
1408 s2->length = s1->length;
1412 /* Die with an error message if S1 and S2 describe strings that
1413 are not valid with the given command line switches.
1414 A side effect of this function is that if a valid [c*] or
1415 [c*0] construct appears in string2, it is converted to [c*n]
1416 with a value for n that makes s2->length == s1->length. By
1417 the same token, if the --truncate-set1 option is not
1418 given, S2 may be extended. */
1422 const struct Spec_list *s1;
1423 struct Spec_list *s2;
1425 get_spec_stats (s1, -1);
1426 if (s1->n_indefinite_repeats > 0)
1428 error (1, 0, "the [c*] repeat construct may not appear in string1");
1431 /* FIXME: it isn't clear from the POSIX spec that this is invalid,
1432 but in the spirit of the other restrictions put on translation
1433 with character classes, this seems a logical interpretation. */
1434 if (complement && s1->has_upper_or_lower)
1437 "character classes may not be used when translating \
1438 and complementing");
1443 get_spec_stats (s2, s1->length);
1444 if (s2->has_restricted_char_class)
1447 "when translating, the only character classes that may \
1448 appear in\n\tstring2 are `upper' and `lower'");
1451 if (s2->n_indefinite_repeats > 1)
1453 error (1, 0, "only one [c*] repeat construct may appear in string2");
1458 if (s2->has_equiv_class)
1461 "[=c=] expressions may not appear in string2 \
1465 if (s1->length > s2->length)
1469 /* string2 must be non-empty unless --truncate-set1 is
1470 given or string1 is empty. */
1472 if (s2->length == 0)
1474 "when not truncating set1, string2 must be non-empty");
1475 string2_extend (s1, s2);
1479 if (complement && s2->has_upper_or_lower)
1481 "character classes may not be used when translating \
1482 and complementing");
1485 /* Not translating. */
1487 if (s2->n_indefinite_repeats > 0)
1489 "the [c*] construct may appear in string2 only \
1495 /* Read buffers of SIZE bytes via the function READER (if READER is
1496 NULL, read from stdin) until EOF. When non-NULL, READER is either
1497 read_and_delete or read_and_xlate. After each buffer is read, it is
1498 processed and written to stdout. The buffers are processed so that
1499 multiple consecutive occurrences of the same character in the input
1500 stream are replaced by a single occurrence of that character if the
1501 character is in the squeeze set. */
1504 squeeze_filter (buf, size, reader)
1509 unsigned int char_to_squeeze = NOT_A_CHAR;
1520 nr = safe_read (0, (char *) buf, size);
1522 nr = (*reader) (buf, size, NULL);
1525 error (1, errno, "read error");
1533 if (char_to_squeeze == NOT_A_CHAR)
1536 /* Here, by being a little tricky, we can get a significant
1537 performance increase in most cases when the input is
1538 reasonably large. Since tr will modify the input only
1539 if two consecutive (and identical) input characters are
1540 in the squeeze set, we can step by two through the data
1541 when searching for a character in the squeeze set. This
1542 means there may be a little more work in a few cases and
1543 perhaps twice as much work in the worst cases where most
1544 of the input is removed by squeezing repeats. But most
1545 uses of this functionality seem to remove less than 20-30%
1547 for (; i < nr && !in_squeeze_set[buf[i]]; i += 2)
1550 /* There is a special case when i == nr and we've just
1551 skipped a character (the last one in buf) that is in
1553 if (i == nr && in_squeeze_set[buf[i - 1]])
1557 out_len = nr - begin;
1560 char_to_squeeze = buf[i];
1561 /* We're about to output buf[begin..i]. */
1562 out_len = i - begin + 1;
1564 /* But since we stepped by 2 in the loop above,
1565 out_len may be one too large. */
1566 if (i > 0 && buf[i - 1] == char_to_squeeze)
1569 /* Advance i to the index of first character to be
1570 considered when looking for a char different from
1575 && fwrite ((char *) &buf[begin], 1, out_len, stdout) == 0)
1576 error (1, errno, "write error");
1579 if (char_to_squeeze != NOT_A_CHAR)
1581 /* Advance i to index of first char != char_to_squeeze
1582 (or to nr if all the rest of the characters in this
1583 buffer are the same as char_to_squeeze). */
1584 for (; i < nr && buf[i] == char_to_squeeze; i++)
1587 char_to_squeeze = NOT_A_CHAR;
1588 /* If (i >= nr) we've squeezed the last character in this buffer.
1589 So now we have to read a new buffer and continue comparing
1590 characters against char_to_squeeze. */
1595 /* Read buffers of SIZE bytes from stdin until one is found that
1596 contains at least one character not in the delete set. Store
1597 in the array BUF, all characters from that buffer that are not
1598 in the delete set, and return the number of characters saved
1602 read_and_delete (buf, size, not_used)
1608 static int hit_eof = 0;
1610 assert (not_used == NULL);
1616 /* This enclosing do-while loop is to make sure that
1617 we don't return zero (indicating EOF) when we've
1618 just deleted all the characters in a buffer. */
1622 int nr = safe_read (0, (char *) buf, size);
1625 error (1, errno, "read error");
1632 /* This first loop may be a waste of code, but gives much
1633 better performance when no characters are deleted in
1634 the beginning of a buffer. It just avoids the copying
1635 of buf[i] into buf[n_saved] when it would be a NOP. */
1637 for (i = 0; i < nr && !in_delete_set[buf[i]]; i++)
1641 for (++i; i < nr; i++)
1642 if (!in_delete_set[buf[i]])
1643 buf[n_saved++] = buf[i];
1645 while (n_saved == 0);
1650 /* Read at most SIZE bytes from stdin into the array BUF. Then
1651 perform the in-place and one-to-one mapping specified by the global
1652 array `xlate'. Return the number of characters read, or 0 upon EOF. */
1655 read_and_xlate (buf, size, not_used)
1660 long chars_read = 0;
1661 static int hit_eof = 0;
1664 assert (not_used == NULL);
1670 chars_read = safe_read (0, (char *) buf, size);
1672 error (1, errno, "read error");
1673 if (chars_read == 0)
1679 for (i = 0; i < chars_read; i++)
1680 buf[i] = xlate[buf[i]];
1685 /* Initialize a boolean membership set IN_SET with the character
1686 values obtained by traversing the linked list of constructs S
1687 using the function `get_next'. If COMPLEMENT_THIS_SET is
1688 non-zero the resulting set is complemented. */
1691 set_initialize (s, complement_this_set, in_set)
1692 struct Spec_list *s;
1693 int complement_this_set;
1699 memset (in_set, 0, N_CHARS * sizeof (in_set[0]));
1700 s->state = BEGIN_STATE;
1701 while ((c = get_next (s, NULL)) != -1)
1703 if (complement_this_set)
1704 for (i = 0; i < N_CHARS; i++)
1705 in_set[i] = (!in_set[i]);
1714 int non_option_args;
1715 struct Spec_list buf1, buf2;
1716 struct Spec_list *s1 = &buf1;
1717 struct Spec_list *s2 = &buf2;
1719 program_name = argv[0];
1721 while ((c = getopt_long (argc, argv, "cdst", long_options,
1738 squeeze_repeats = 1;
1753 printf ("tr - %s\n", version_string);
1760 posix_pedantic = (getenv ("POSIXLY_CORRECT") != NULL);
1762 non_option_args = argc - optind;
1763 translating = (non_option_args == 2 && !delete);
1765 /* Change this test if it is valid to give tr no options and
1766 no args at all. POSIX doesn't specifically say anything
1767 either way, but it looks like they implied it's invalid
1768 by omission. If you want to make tr do a slow imitation
1769 of `cat' use `tr a a'. */
1770 if (non_option_args > 2)
1772 error (0, 0, "too many arguments");
1776 if (!delete && !squeeze_repeats && non_option_args != 2)
1777 error (1, 0, "two strings must be given when translating");
1779 if (delete && squeeze_repeats && non_option_args != 2)
1780 error (1, 0, "two strings must be given when both \
1781 deleting and squeezing repeats");
1783 /* If --delete is given without --squeeze-repeats, then
1784 only one string argument may be specified. But POSIX
1785 says to ignore any string2 in this case, so if POSIXLY_CORRECT
1786 is set, pretend we never saw string2. But I think
1787 this deserves a fatal error, so that's the default. */
1788 if ((delete && !squeeze_repeats) && non_option_args != 1)
1790 if (posix_pedantic && non_option_args == 2)
1794 "only one string may be given when deleting \
1795 without squeezing repeats");
1798 if (squeeze_repeats && non_option_args == 0)
1799 error (1, 0, "at least one string must be given when squeezing repeats");
1802 if (parse_str ((unsigned char *) argv[optind], s1))
1805 if (non_option_args == 2)
1808 if (parse_str ((unsigned char *) argv[optind + 1], s2))
1816 if (squeeze_repeats && non_option_args == 1)
1818 set_initialize (s1, complement, in_squeeze_set);
1819 squeeze_filter (io_buf, IO_BUF_SIZE, NULL);
1821 else if (delete && non_option_args == 1)
1825 set_initialize (s1, complement, in_delete_set);
1828 nr = read_and_delete (io_buf, IO_BUF_SIZE, NULL);
1829 if (nr > 0 && fwrite ((char *) io_buf, 1, nr, stdout) == 0)
1830 error (1, errno, "write error");
1834 else if (squeeze_repeats && delete && non_option_args == 2)
1836 set_initialize (s1, complement, in_delete_set);
1837 set_initialize (s2, 0, in_squeeze_set);
1838 squeeze_filter (io_buf, IO_BUF_SIZE, (PFI) read_and_delete);
1840 else if (translating)
1845 SET_TYPE *in_s1 = in_delete_set;
1847 set_initialize (s1, 0, in_s1);
1848 s2->state = BEGIN_STATE;
1849 for (i = 0; i < N_CHARS; i++)
1851 for (i = 0; i < N_CHARS; i++)
1855 int ch = get_next (s2, NULL);
1856 assert (ch != -1 || truncate_set1);
1859 /* This will happen when tr is invoked like e.g.
1860 tr -cs A-Za-z0-9 '\012'. */
1866 assert (get_next (s2, NULL) == -1 || truncate_set1);
1872 enum Upper_Lower_class class_s1;
1873 enum Upper_Lower_class class_s2;
1875 for (i = 0; i < N_CHARS; i++)
1877 s1->state = BEGIN_STATE;
1878 s2->state = BEGIN_STATE;
1881 c1 = get_next (s1, &class_s1);
1882 c2 = get_next (s2, &class_s2);
1883 if (!class_ok[(int) class_s1][(int) class_s2])
1885 "misaligned or mismatched upper and/or lower classes");
1886 /* The following should have been checked by validate... */
1891 assert (c1 == -1 || truncate_set1);
1893 if (squeeze_repeats)
1895 set_initialize (s2, 0, in_squeeze_set);
1896 squeeze_filter (io_buf, IO_BUF_SIZE, (PFI) read_and_xlate);
1904 chars_read = read_and_xlate (io_buf, IO_BUF_SIZE, NULL);
1906 && fwrite ((char *) io_buf, 1, chars_read, stdout) == 0)
1907 error (1, errno, "write error");
1909 while (chars_read > 0);
1913 if (fclose (stdout) == EOF)
1914 error (2, errno, "write error");
1917 error (2, errno, "standard input");