1 /* tr -- a filter to translate characters
2 Copyright (C) 91, 1995-2009 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 3 of the License, or
7 (at your option) any later version.
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, see <http://www.gnu.org/licenses/>. */
17 /* Written by Jim Meyering */
23 #include <sys/types.h>
29 #include "safe-read.h"
33 /* The official name of this program (e.g., no `g' prefix). */
34 #define PROGRAM_NAME "tr"
36 #define AUTHORS proper_name ("Jim Meyering")
38 enum { N_CHARS
= UCHAR_MAX
+ 1 };
40 /* An unsigned integer type big enough to hold a repeat count or an
41 unsigned character. POSIX requires support for repeat counts as
42 high as 2**31 - 1. Since repeat counts might need to expand to
43 match the length of an argument string, we need at least size_t to
44 avoid arbitrary internal limits. It doesn't cost much to use
46 typedef uintmax_t count
;
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 (UINTMAX_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 /* The maximum possible repeat count. Due to how the states are
63 implemented, it can be as much as BEGIN_STATE. */
64 #define REPEAT_COUNT_MAXIMUM BEGIN_STATE
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 /* The type of a List_element. See build_spec_list for more details. */
90 enum Range_element_type
99 /* One construct in one of tr's argument strings.
100 For example, consider the POSIX version of the classic tr command:
101 tr -cs 'a-zA-Z_' '[\n*]'
102 String1 has 3 constructs, two of which are ranges (a-z and A-Z),
103 and a single normal character, `_'. String2 has one construct. */
106 enum Range_element_type type
;
107 struct List_element
*next
;
110 unsigned char normal_char
;
113 unsigned char first_char
;
114 unsigned char last_char
;
117 enum Char_class char_class
;
118 unsigned char equiv_code
;
121 unsigned char the_repeated_char
;
129 /* Each of tr's argument strings is parsed into a form that is easier
130 to work with: a linked list of constructs (struct List_element).
131 Each Spec_list structure also encapsulates various attributes of
132 the corresponding argument string. The attributes are used mainly
133 to verify that the strings are valid in the context of any options
134 specified (like -s, -d, or -c). The main exception is the member
135 `tail', which is first used to construct the list. After construction,
136 it is used by get_next to save its state when traversing the list.
137 The member `state' serves a similar function. */
140 /* Points to the head of the list of range elements.
141 The first struct is a dummy; its members are never used. */
142 struct List_element
*head
;
144 /* When appending, points to the last element. When traversing via
145 get_next(), points to the element to process next. Setting
146 Spec_list.state to the value BEGIN_STATE before calling get_next
147 signals get_next to initialize tail to point to head->next. */
148 struct List_element
*tail
;
150 /* Used to save state between calls to get_next. */
153 /* Length, in the sense that length ('a-z[:digit:]123abc')
154 is 42 ( = 26 + 10 + 6). */
157 /* The number of [c*] and [c*0] constructs that appear in this spec. */
158 size_t n_indefinite_repeats
;
160 /* If n_indefinite_repeats is nonzero, this points to the List_element
161 corresponding to the last [c*] or [c*0] construct encountered in
162 this spec. Otherwise it is undefined. */
163 struct List_element
*indefinite_repeat_element
;
165 /* True if this spec contains at least one equivalence
166 class construct e.g. [=c=]. */
167 bool has_equiv_class
;
169 /* True if this spec contains at least one character class
170 construct. E.g. [:digit:]. */
173 /* True if this spec contains at least one of the character class
174 constructs (all but upper and lower) that aren't allowed in s2. */
175 bool has_restricted_char_class
;
178 /* A representation for escaped string1 or string2. As a string is parsed,
179 any backslash-escaped characters (other than octal or \a, \b, \f, \n,
180 etc.) are marked as such in this structure by setting the corresponding
181 entry in the ESCAPED vector. */
189 /* Return nonzero if the Ith character of escaped string ES matches C
190 and is not escaped itself. */
192 es_match (struct E_string
const *es
, size_t i
, char c
)
194 return es
->s
[i
] == c
&& !es
->escaped
[i
];
197 /* When true, each sequence in the input of a repeated character
198 (call it c) is replaced (in the output) by a single occurrence of c
199 for every c in the squeeze set. */
200 static bool squeeze_repeats
= false;
202 /* When true, removes characters in the delete set from input. */
203 static bool delete = false;
205 /* Use the complement of set1 in place of set1. */
206 static bool complement
= false;
208 /* When tr is performing translation and string1 is longer than string2,
209 POSIX says that the result is unspecified. That gives the implementor
210 of a POSIX conforming version of tr two reasonable choices for the
211 semantics of this case.
213 * The BSD tr pads string2 to the length of string1 by
214 repeating the last character in string2.
216 * System V tr ignores characters in string1 that have no
217 corresponding character in string2. That is, string1 is effectively
218 truncated to the length of string2.
220 When nonzero, this flag causes GNU tr to imitate the behavior
221 of System V tr when translating with string1 longer than string2.
222 The default is to emulate BSD tr. This flag is ignored in modes where
223 no translation is performed. Emulating the System V tr
224 in this exceptional case causes the relatively common BSD idiom:
226 tr -cs A-Za-z0-9 '\012'
228 to break (it would convert only zero bytes, rather than all
229 non-alphanumerics, to newlines).
231 WARNING: This switch does not provide general BSD or System V
232 compatibility. For example, it doesn't disable the interpretation
233 of the POSIX constructs [:alpha:], [=c=], and [c*10], so if by
234 some unfortunate coincidence you use such constructs in scripts
235 expecting to use some other version of tr, the scripts will break. */
236 static bool truncate_set1
= false;
238 /* An alias for (!delete && non_option_args == 2).
239 It is set in main and used there and in validate(). */
240 static bool translating
;
242 static char io_buf
[BUFSIZ
];
244 static char const *const char_class_name
[] =
246 "alnum", "alpha", "blank", "cntrl", "digit", "graph",
247 "lower", "print", "punct", "space", "upper", "xdigit"
250 /* Array of boolean values. A character `c' is a member of the
251 squeeze set if and only if in_squeeze_set[c] is true. The squeeze
252 set is defined by the last (possibly, the only) string argument
253 on the command line when the squeeze option is given. */
254 static bool in_squeeze_set
[N_CHARS
];
256 /* Array of boolean values. A character `c' is a member of the
257 delete set if and only if in_delete_set[c] is true. The delete
258 set is defined by the first (or only) string argument on the
259 command line when the delete option is given. */
260 static bool in_delete_set
[N_CHARS
];
262 /* Array of character values defining the translation (if any) that
263 tr is to perform. Translation is performed only when there are
264 two specification strings and the delete switch is not given. */
265 static char xlate
[N_CHARS
];
267 static struct option
const long_options
[] =
269 {"complement", no_argument
, NULL
, 'c'},
270 {"delete", no_argument
, NULL
, 'd'},
271 {"squeeze-repeats", no_argument
, NULL
, 's'},
272 {"truncate-set1", no_argument
, NULL
, 't'},
273 {GETOPT_HELP_OPTION_DECL
},
274 {GETOPT_VERSION_OPTION_DECL
},
281 if (status
!= EXIT_SUCCESS
)
282 fprintf (stderr
, _("Try `%s --help' for more information.\n"),
287 Usage: %s [OPTION]... SET1 [SET2]\n\
291 Translate, squeeze, and/or delete characters from standard input,\n\
292 writing to standard output.\n\
294 -c, -C, --complement use the complement of SET1\n\
295 -d, --delete delete characters in SET1, do not translate\n\
296 -s, --squeeze-repeats replace each input sequence of a repeated character\n\
297 that is listed in SET1 with a single occurrence\n\
299 -t, --truncate-set1 first truncate SET1 to length of SET2\n\
301 fputs (HELP_OPTION_DESCRIPTION
, stdout
);
302 fputs (VERSION_OPTION_DESCRIPTION
, stdout
);
305 SETs are specified as strings of characters. Most represent themselves.\n\
306 Interpreted sequences are:\n\
308 \\NNN character with octal value NNN (1 to 3 octal digits)\n\
315 \\t horizontal tab\n\
319 CHAR1-CHAR2 all characters from CHAR1 to CHAR2 in ascending order\n\
320 [CHAR*] in SET2, copies of CHAR until length of SET1\n\
321 [CHAR*REPEAT] REPEAT copies of CHAR, REPEAT octal if starting with 0\n\
322 [:alnum:] all letters and digits\n\
323 [:alpha:] all letters\n\
324 [:blank:] all horizontal whitespace\n\
325 [:cntrl:] all control characters\n\
326 [:digit:] all digits\n\
329 [:graph:] all printable characters, not including space\n\
330 [:lower:] all lower case letters\n\
331 [:print:] all printable characters, including space\n\
332 [:punct:] all punctuation characters\n\
333 [:space:] all horizontal or vertical whitespace\n\
334 [:upper:] all upper case letters\n\
335 [:xdigit:] all hexadecimal digits\n\
336 [=CHAR=] all characters which are equivalent to CHAR\n\
340 Translation occurs if -d is not given and both SET1 and SET2 appear.\n\
341 -t may be used only when translating. SET2 is extended to length of\n\
342 SET1 by repeating its last character as necessary. Excess characters\n\
343 of SET2 are ignored. Only [:lower:] and [:upper:] are guaranteed to\n\
344 expand in ascending order; used in SET2 while translating, they may\n\
345 only be used in pairs to specify case conversion. -s uses SET1 if not\n\
346 translating nor deleting; else squeezing uses SET2 and occurs after\n\
347 translation or deletion.\n\
349 emit_bug_reporting_address ();
354 /* Return nonzero if the character C is a member of the
355 equivalence class containing the character EQUIV_CLASS. */
358 is_equiv_class_member (unsigned char equiv_class
, unsigned char c
)
360 return (equiv_class
== c
);
363 /* Return true if the character C is a member of the
364 character class CHAR_CLASS. */
367 is_char_class_member (enum Char_class char_class
, unsigned char c
)
374 result
= isalnum (c
);
377 result
= isalpha (c
);
380 result
= isblank (c
);
383 result
= iscntrl (c
);
386 result
= isdigit (c
);
389 result
= isgraph (c
);
392 result
= islower (c
);
395 result
= isprint (c
);
398 result
= ispunct (c
);
401 result
= isspace (c
);
404 result
= isupper (c
);
407 result
= isxdigit (c
);
418 es_free (struct E_string
*es
)
424 /* Perform the first pass over each range-spec argument S, converting all
425 \c and \ddd escapes to their one-byte representations. If an invalid
426 quote sequence is found print an error message and return false;
427 Otherwise set *ES to the resulting string and return true.
428 The resulting array of characters may contain zero-bytes;
429 however, on input, S is assumed to be null-terminated, and hence
430 cannot contain actual (non-escaped) zero bytes. */
433 unquote (char const *s
, struct E_string
*es
)
436 size_t len
= strlen (s
);
438 es
->s
= xmalloc (len
);
439 es
->escaped
= xcalloc (len
, sizeof es
->escaped
[0]);
442 for (i
= 0; s
[i
]; i
++)
450 es
->escaped
[j
] = true;
486 oct_digit
= s
[i
+ 2] - '0';
487 if (0 <= oct_digit
&& oct_digit
<= 7)
489 c
= 8 * c
+ oct_digit
;
491 oct_digit
= s
[i
+ 2] - '0';
492 if (0 <= oct_digit
&& oct_digit
<= 7)
494 if (8 * c
+ oct_digit
< N_CHARS
)
496 c
= 8 * c
+ oct_digit
;
501 /* A 3-digit octal number larger than \377 won't
502 fit in 8 bits. So we stop when adding the
503 next digit would put us over the limit and
504 give a warning about the ambiguity. POSIX
505 isn't clear on this, and we interpret this
506 lack of clarity as meaning the resulting behavior
507 is undefined, which means we're allowed to issue
509 error (0, 0, _("warning: the ambiguous octal escape \
510 \\%c%c%c is being\n\tinterpreted as the 2-byte sequence \\0%c%c, %c"),
511 s
[i
], s
[i
+ 1], s
[i
+ 2],
512 s
[i
], s
[i
+ 1], s
[i
+ 2]);
518 error (0, 0, _("warning: an unescaped backslash "
519 "at end of string is not portable"));
520 /* POSIX is not clear about this. */
521 es
->escaped
[j
] = false;
541 /* If CLASS_STR is a valid character class string, return its index
542 in the global char_class_name array. Otherwise, return CC_NO_CLASS. */
544 static enum Char_class
545 look_up_char_class (char const *class_str
, size_t len
)
549 for (i
= 0; i
< ARRAY_CARDINALITY (char_class_name
); i
++)
550 if (strncmp (class_str
, char_class_name
[i
], len
) == 0
551 && strlen (char_class_name
[i
]) == len
)
556 /* Return a newly allocated string with a printable version of C.
557 This function is used solely for formatting error messages. */
560 make_printable_char (unsigned char c
)
562 char *buf
= xmalloc (5);
571 sprintf (buf
, "\\%03o", c
);
576 /* Return a newly allocated copy of S which is suitable for printing.
577 LEN is the number of characters in S. Most non-printing
578 (isprint) characters are represented by a backslash followed by
579 3 octal digits. However, the characters represented by \c escapes
580 where c is one of [abfnrtv] are represented by their 2-character \c
581 sequences. This function is used solely for printing error messages. */
584 make_printable_str (char const *s
, size_t len
)
586 /* Worst case is that every character expands to a backslash
587 followed by a 3-character octal escape sequence. */
588 char *printable_buf
= xnmalloc (len
+ 1, 4);
589 char *p
= printable_buf
;
592 for (i
= 0; i
< len
; i
++)
595 char const *tmp
= NULL
;
596 unsigned char c
= s
[i
];
631 sprintf (buf
, "\\%03o", c
);
637 return printable_buf
;
640 /* Append a newly allocated structure representing a
641 character C to the specification list LIST. */
644 append_normal_char (struct Spec_list
*list
, unsigned char c
)
646 struct List_element
*new;
648 new = xmalloc (sizeof *new);
650 new->type
= RE_NORMAL_CHAR
;
651 new->u
.normal_char
= c
;
653 list
->tail
->next
= new;
657 /* Append a newly allocated structure representing the range
658 of characters from FIRST to LAST to the specification list LIST.
659 Return false if LAST precedes FIRST in the collating sequence,
660 true otherwise. This means that '[c-c]' is acceptable. */
663 append_range (struct Spec_list
*list
, unsigned char first
, unsigned char last
)
665 struct List_element
*new;
669 char *tmp1
= make_printable_char (first
);
670 char *tmp2
= make_printable_char (last
);
673 _("range-endpoints of `%s-%s' are in reverse collating sequence order"),
679 new = xmalloc (sizeof *new);
681 new->type
= RE_RANGE
;
682 new->u
.range
.first_char
= first
;
683 new->u
.range
.last_char
= last
;
685 list
->tail
->next
= new;
690 /* If CHAR_CLASS_STR is a valid character class string, append a
691 newly allocated structure representing that character class to the end
692 of the specification list LIST and return true. If CHAR_CLASS_STR is not
693 a valid string return false. */
696 append_char_class (struct Spec_list
*list
,
697 char const *char_class_str
, size_t len
)
699 enum Char_class char_class
;
700 struct List_element
*new;
702 char_class
= look_up_char_class (char_class_str
, len
);
703 if (char_class
== CC_NO_CLASS
)
705 new = xmalloc (sizeof *new);
707 new->type
= RE_CHAR_CLASS
;
708 new->u
.char_class
= char_class
;
710 list
->tail
->next
= new;
715 /* Append a newly allocated structure representing a [c*n]
716 repeated character construct to the specification list LIST.
717 THE_CHAR is the single character to be repeated, and REPEAT_COUNT
718 is a non-negative repeat count. */
721 append_repeated_char (struct Spec_list
*list
, unsigned char the_char
,
724 struct List_element
*new;
726 new = xmalloc (sizeof *new);
728 new->type
= RE_REPEATED_CHAR
;
729 new->u
.repeated_char
.the_repeated_char
= the_char
;
730 new->u
.repeated_char
.repeat_count
= repeat_count
;
732 list
->tail
->next
= new;
736 /* Given a string, EQUIV_CLASS_STR, from a [=str=] context and
737 the length of that string, LEN, if LEN is exactly one, append
738 a newly allocated structure representing the specified
739 equivalence class to the specification list, LIST and return true.
740 If LEN is not 1, return false. */
743 append_equiv_class (struct Spec_list
*list
,
744 char const *equiv_class_str
, size_t len
)
746 struct List_element
*new;
750 new = xmalloc (sizeof *new);
752 new->type
= RE_EQUIV_CLASS
;
753 new->u
.equiv_code
= *equiv_class_str
;
755 list
->tail
->next
= new;
760 /* Search forward starting at START_IDX for the 2-char sequence
761 (PRE_BRACKET_CHAR,']') in the string P of length P_LEN. If such
762 a sequence is found, set *RESULT_IDX to the index of the first
763 character and return true. Otherwise return false. P may contain
767 find_closing_delim (const struct E_string
*es
, size_t start_idx
,
768 char pre_bracket_char
, size_t *result_idx
)
772 for (i
= start_idx
; i
< es
->len
- 1; i
++)
773 if (es
->s
[i
] == pre_bracket_char
&& es
->s
[i
+ 1] == ']'
774 && !es
->escaped
[i
] && !es
->escaped
[i
+ 1])
782 /* Parse the bracketed repeat-char syntax. If the P_LEN characters
783 beginning with P[ START_IDX ] comprise a valid [c*n] construct,
784 then set *CHAR_TO_REPEAT, *REPEAT_COUNT, and *CLOSING_BRACKET_IDX
785 and return zero. If the second character following
786 the opening bracket is not `*' or if no closing bracket can be
787 found, return -1. If a closing bracket is found and the
788 second char is `*', but the string between the `*' and `]' isn't
789 empty, an octal number, or a decimal number, print an error message
793 find_bracketed_repeat (const struct E_string
*es
, size_t start_idx
,
794 unsigned char *char_to_repeat
, count
*repeat_count
,
795 size_t *closing_bracket_idx
)
799 assert (start_idx
+ 1 < es
->len
);
800 if (!es_match (es
, start_idx
+ 1, '*'))
803 for (i
= start_idx
+ 2; i
< es
->len
&& !es
->escaped
[i
]; i
++)
807 size_t digit_str_len
= i
- start_idx
- 2;
809 *char_to_repeat
= es
->s
[start_idx
];
810 if (digit_str_len
== 0)
812 /* We've matched [c*] -- no explicit repeat count. */
817 /* Here, we have found [c*s] where s should be a string
818 of octal (if it starts with `0') or decimal digits. */
819 char const *digit_str
= &es
->s
[start_idx
+ 2];
821 if ((xstrtoumax (digit_str
, &d_end
, *digit_str
== '0' ? 8 : 10,
824 || REPEAT_COUNT_MAXIMUM
< *repeat_count
825 || digit_str
+ digit_str_len
!= d_end
)
827 char *tmp
= make_printable_str (digit_str
, digit_str_len
);
829 _("invalid repeat count %s in [c*n] construct"),
835 *closing_bracket_idx
= i
;
839 return -1; /* No bracket found. */
842 /* Return true if the string at ES->s[IDX] matches the regular
843 expression `\*[0-9]*\]', false otherwise. The string does not
844 match if any of its characters are escaped. */
847 star_digits_closebracket (const struct E_string
*es
, size_t idx
)
851 if (!es_match (es
, idx
, '*'))
854 for (i
= idx
+ 1; i
< es
->len
; i
++)
855 if (!ISDIGIT (to_uchar (es
->s
[i
])) || es
->escaped
[i
])
856 return es_match (es
, i
, ']');
860 /* Convert string UNESCAPED_STRING (which has been preprocessed to
861 convert backslash-escape sequences) of length LEN characters into
862 a linked list of the following 5 types of constructs:
863 - [:str:] Character class where `str' is one of the 12 valid strings.
864 - [=c=] Equivalence class where `c' is any single character.
865 - [c*n] Repeat the single character `c' `n' times. n may be omitted.
866 However, if `n' is present, it must be a non-negative octal or
868 - r-s Range of characters from `r' to `s'. The second endpoint must
869 not precede the first in the current collating sequence.
870 - c Any other character is interpreted as itself. */
873 build_spec_list (const struct E_string
*es
, struct Spec_list
*result
)
880 /* The main for-loop below recognizes the 4 multi-character constructs.
881 A character that matches (in its context) none of the multi-character
882 constructs is classified as `normal'. Since all multi-character
883 constructs have at least 3 characters, any strings of length 2 or
884 less are composed solely of normal characters. Hence, the index of
885 the outer for-loop runs only as far as LEN-2. */
887 for (i
= 0; i
+ 2 < es
->len
; /* empty */)
889 if (es_match (es
, i
, '['))
891 bool matched_multi_char_construct
;
892 size_t closing_bracket_idx
;
893 unsigned char char_to_repeat
;
897 matched_multi_char_construct
= true;
898 if (es_match (es
, i
+ 1, ':') || es_match (es
, i
+ 1, '='))
900 size_t closing_delim_idx
;
902 if (find_closing_delim (es
, i
+ 2, p
[i
+ 1], &closing_delim_idx
))
904 size_t opnd_str_len
= closing_delim_idx
- 1 - (i
+ 2) + 1;
905 char const *opnd_str
= p
+ i
+ 2;
907 if (opnd_str_len
== 0)
910 error (0, 0, _("missing character class name `[::]'"));
913 _("missing equivalence class character `[==]'"));
919 /* FIXME: big comment. */
920 if (!append_char_class (result
, opnd_str
, opnd_str_len
))
922 if (star_digits_closebracket (es
, i
+ 2))
923 goto try_bracketed_repeat
;
926 char *tmp
= make_printable_str (opnd_str
,
928 error (0, 0, _("invalid character class %s"),
937 /* FIXME: big comment. */
938 if (!append_equiv_class (result
, opnd_str
, opnd_str_len
))
940 if (star_digits_closebracket (es
, i
+ 2))
941 goto try_bracketed_repeat
;
944 char *tmp
= make_printable_str (opnd_str
,
947 _("%s: equivalence class operand must be a single character"),
955 i
= closing_delim_idx
+ 2;
958 /* Else fall through. This could be [:*] or [=*]. */
961 try_bracketed_repeat
:
963 /* Determine whether this is a bracketed repeat range
964 matching the RE \[.\*(dec_or_oct_number)?\]. */
965 err
= find_bracketed_repeat (es
, i
+ 1, &char_to_repeat
,
967 &closing_bracket_idx
);
970 append_repeated_char (result
, char_to_repeat
, repeat_count
);
971 i
= closing_bracket_idx
+ 1;
975 matched_multi_char_construct
= false;
979 /* Found a string that looked like [c*n] but the
980 numeric part was invalid. */
984 if (matched_multi_char_construct
)
987 /* We reach this point if P does not match [:str:], [=c=],
988 [c*n], or [c*]. Now, see if P looks like a range `[-c'
989 (from `[' to `c'). */
992 /* Look ahead one char for ranges like a-z. */
993 if (es_match (es
, i
+ 1, '-'))
995 if (!append_range (result
, p
[i
], p
[i
+ 2]))
1001 append_normal_char (result
, p
[i
]);
1006 /* Now handle the (2 or fewer) remaining characters p[i]..p[es->len - 1]. */
1007 for (; i
< es
->len
; i
++)
1008 append_normal_char (result
, p
[i
]);
1013 /* Advance past the current construct.
1014 S->tail must be non-NULL. */
1016 skip_construct (struct Spec_list
*s
)
1018 s
->tail
= s
->tail
->next
;
1019 s
->state
= NEW_ELEMENT
;
1022 /* Given a Spec_list S (with its saved state implicit in the values
1023 of its members `tail' and `state'), return the next single character
1024 in the expansion of S's constructs. If the last character of S was
1025 returned on the previous call or if S was empty, this function
1026 returns -1. For example, successive calls to get_next where S
1027 represents the spec-string 'a-d[y*3]' will return the sequence
1028 of values a, b, c, d, y, y, y, -1. Finally, if the construct from
1029 which the returned character comes is [:upper:] or [:lower:], the
1030 parameter CLASS is given a value to indicate which it was. Otherwise
1031 CLASS is set to UL_NONE. This value is used only when constructing
1032 the translation table to verify that any occurrences of upper and
1033 lower class constructs in the spec-strings appear in the same relative
1037 get_next (struct Spec_list
*s
, enum Upper_Lower_class
*class)
1039 struct List_element
*p
;
1046 if (s
->state
== BEGIN_STATE
)
1048 s
->tail
= s
->head
->next
;
1049 s
->state
= NEW_ELEMENT
;
1058 case RE_NORMAL_CHAR
:
1059 return_val
= p
->u
.normal_char
;
1060 s
->state
= NEW_ELEMENT
;
1065 if (s
->state
== NEW_ELEMENT
)
1066 s
->state
= p
->u
.range
.first_char
;
1069 return_val
= s
->state
;
1070 if (s
->state
== p
->u
.range
.last_char
)
1073 s
->state
= NEW_ELEMENT
;
1080 switch (p
->u
.char_class
)
1093 if (s
->state
== NEW_ELEMENT
)
1095 for (i
= 0; i
< N_CHARS
; i
++)
1096 if (is_char_class_member (p
->u
.char_class
, i
))
1098 assert (i
< N_CHARS
);
1101 assert (is_char_class_member (p
->u
.char_class
, s
->state
));
1102 return_val
= s
->state
;
1103 for (i
= s
->state
+ 1; i
< N_CHARS
; i
++)
1104 if (is_char_class_member (p
->u
.char_class
, i
))
1111 s
->state
= NEW_ELEMENT
;
1115 case RE_EQUIV_CLASS
:
1116 /* FIXME: this assumes that each character is alone in its own
1117 equivalence class (which appears to be correct for my
1118 LC_COLLATE. But I don't know of any function that allows
1119 one to determine a character's equivalence class. */
1121 return_val
= p
->u
.equiv_code
;
1122 s
->state
= NEW_ELEMENT
;
1126 case RE_REPEATED_CHAR
:
1127 /* Here, a repeat count of n == 0 means don't repeat at all. */
1128 if (p
->u
.repeated_char
.repeat_count
== 0)
1131 s
->state
= NEW_ELEMENT
;
1132 return_val
= get_next (s
, class);
1136 if (s
->state
== NEW_ELEMENT
)
1141 return_val
= p
->u
.repeated_char
.the_repeated_char
;
1142 if (s
->state
== p
->u
.repeated_char
.repeat_count
)
1145 s
->state
= NEW_ELEMENT
;
1158 /* This is a minor kludge. This function is called from
1159 get_spec_stats to determine the cardinality of a set derived
1160 from a complemented string. It's a kludge in that some of the
1161 same operations are (duplicated) performed in set_initialize. */
1164 card_of_complement (struct Spec_list
*s
)
1167 int cardinality
= N_CHARS
;
1168 bool in_set
[N_CHARS
] = { 0, };
1170 s
->state
= BEGIN_STATE
;
1171 while ((c
= get_next (s
, NULL
)) != -1)
1173 cardinality
-= (!in_set
[c
]);
1179 /* Gather statistics about the spec-list S in preparation for the tests
1180 in validate that determine the consistency of the specs. This function
1181 is called at most twice; once for string1, and again for any string2.
1182 LEN_S1 < 0 indicates that this is the first call and that S represents
1183 string1. When LEN_S1 >= 0, it is the length of the expansion of the
1184 constructs in string1, and we can use its value to resolve any
1185 indefinite repeat construct in S (which represents string2). Hence,
1186 this function has the side-effect that it converts a valid [c*]
1187 construct in string2 to [c*n] where n is large enough (or 0) to give
1188 string2 the same length as string1. For example, with the command
1189 tr a-z 'A[\n*]Z' on the second call to get_spec_stats, LEN_S1 would
1190 be 26 and S (representing string2) would be converted to 'A[\n*24]Z'. */
1193 get_spec_stats (struct Spec_list
*s
)
1195 struct List_element
*p
;
1198 s
->n_indefinite_repeats
= 0;
1199 s
->has_equiv_class
= false;
1200 s
->has_restricted_char_class
= false;
1201 s
->has_char_class
= false;
1202 for (p
= s
->head
->next
; p
; p
= p
->next
)
1210 case RE_NORMAL_CHAR
:
1215 assert (p
->u
.range
.last_char
>= p
->u
.range
.first_char
);
1216 len
= p
->u
.range
.last_char
- p
->u
.range
.first_char
+ 1;
1220 s
->has_char_class
= true;
1221 for (i
= 0; i
< N_CHARS
; i
++)
1222 if (is_char_class_member (p
->u
.char_class
, i
))
1224 switch (p
->u
.char_class
)
1230 s
->has_restricted_char_class
= true;
1235 case RE_EQUIV_CLASS
:
1236 for (i
= 0; i
< N_CHARS
; i
++)
1237 if (is_equiv_class_member (p
->u
.equiv_code
, i
))
1239 s
->has_equiv_class
= true;
1242 case RE_REPEATED_CHAR
:
1243 if (p
->u
.repeated_char
.repeat_count
> 0)
1244 len
= p
->u
.repeated_char
.repeat_count
;
1247 s
->indefinite_repeat_element
= p
;
1248 ++(s
->n_indefinite_repeats
);
1257 /* Check for arithmetic overflow in computing length. Also, reject
1258 any length greater than the maximum repeat count, in case the
1259 length is later used to compute the repeat count for an
1260 indefinite element. */
1261 new_length
= length
+ len
;
1262 if (! (length
<= new_length
&& new_length
<= REPEAT_COUNT_MAXIMUM
))
1263 error (EXIT_FAILURE
, 0, _("too many characters in set"));
1264 length
= new_length
;
1271 get_s1_spec_stats (struct Spec_list
*s1
)
1273 get_spec_stats (s1
);
1275 s1
->length
= card_of_complement (s1
);
1279 get_s2_spec_stats (struct Spec_list
*s2
, count len_s1
)
1281 get_spec_stats (s2
);
1282 if (len_s1
>= s2
->length
&& s2
->n_indefinite_repeats
== 1)
1284 s2
->indefinite_repeat_element
->u
.repeated_char
.repeat_count
=
1285 len_s1
- s2
->length
;
1286 s2
->length
= len_s1
;
1291 spec_init (struct Spec_list
*spec_list
)
1293 struct List_element
*new = xmalloc (sizeof *new);
1294 spec_list
->head
= spec_list
->tail
= new;
1295 spec_list
->head
->next
= NULL
;
1298 /* This function makes two passes over the argument string S. The first
1299 one converts all \c and \ddd escapes to their one-byte representations.
1300 The second constructs a linked specification list, SPEC_LIST, of the
1301 characters and constructs that comprise the argument string. If either
1302 of these passes detects an error, this function returns false. */
1305 parse_str (char const *s
, struct Spec_list
*spec_list
)
1308 bool ok
= unquote (s
, &es
) && build_spec_list (&es
, spec_list
);
1313 /* Given two specification lists, S1 and S2, and assuming that
1314 S1->length > S2->length, append a single [c*n] element to S2 where c
1315 is the last character in the expansion of S2 and n is the difference
1316 between the two lengths.
1317 Upon successful completion, S2->length is set to S1->length. The only
1318 way this function can fail to make S2 as long as S1 is when S2 has
1319 zero-length, since in that case, there is no last character to repeat.
1320 So S2->length is required to be at least 1.
1322 Providing this functionality allows the user to do some pretty
1323 non-BSD (and non-portable) things: For example, the command
1324 tr -cs '[:upper:]0-9' '[:lower:]'
1325 is almost guaranteed to give results that depend on your collating
1329 string2_extend (const struct Spec_list
*s1
, struct Spec_list
*s2
)
1331 struct List_element
*p
;
1332 unsigned char char_to_repeat
;
1335 assert (translating
);
1336 assert (s1
->length
> s2
->length
);
1337 assert (s2
->length
> 0);
1342 case RE_NORMAL_CHAR
:
1343 char_to_repeat
= p
->u
.normal_char
;
1346 char_to_repeat
= p
->u
.range
.last_char
;
1349 for (i
= N_CHARS
- 1; i
>= 0; i
--)
1350 if (is_char_class_member (p
->u
.char_class
, i
))
1356 case RE_REPEATED_CHAR
:
1357 char_to_repeat
= p
->u
.repeated_char
.the_repeated_char
;
1360 case RE_EQUIV_CLASS
:
1361 /* This shouldn't happen, because validate exits with an error
1362 if it finds an equiv class in string2 when translating. */
1371 append_repeated_char (s2
, char_to_repeat
, s1
->length
- s2
->length
);
1372 s2
->length
= s1
->length
;
1375 /* Return true if S is a non-empty list in which exactly one
1376 character (but potentially, many instances of it) appears.
1377 E.g., [X*] or xxxxxxxx. */
1380 homogeneous_spec_list (struct Spec_list
*s
)
1384 s
->state
= BEGIN_STATE
;
1386 if ((b
= get_next (s
, NULL
)) == -1)
1389 while ((c
= get_next (s
, NULL
)) != -1)
1396 /* Die with an error message if S1 and S2 describe strings that
1397 are not valid with the given command line switches.
1398 A side effect of this function is that if a valid [c*] or
1399 [c*0] construct appears in string2, it is converted to [c*n]
1400 with a value for n that makes s2->length == s1->length. By
1401 the same token, if the --truncate-set1 option is not
1402 given, S2 may be extended. */
1405 validate (struct Spec_list
*s1
, struct Spec_list
*s2
)
1407 get_s1_spec_stats (s1
);
1408 if (s1
->n_indefinite_repeats
> 0)
1410 error (EXIT_FAILURE
, 0,
1411 _("the [c*] repeat construct may not appear in string1"));
1416 get_s2_spec_stats (s2
, s1
->length
);
1418 if (s2
->n_indefinite_repeats
> 1)
1420 error (EXIT_FAILURE
, 0,
1421 _("only one [c*] repeat construct may appear in string2"));
1426 if (s2
->has_equiv_class
)
1428 error (EXIT_FAILURE
, 0,
1429 _("[=c=] expressions may not appear in string2 \
1430 when translating"));
1433 if (s1
->length
> s2
->length
)
1437 /* string2 must be non-empty unless --truncate-set1 is
1438 given or string1 is empty. */
1440 if (s2
->length
== 0)
1441 error (EXIT_FAILURE
, 0,
1442 _("when not truncating set1, string2 must be non-empty"));
1443 string2_extend (s1
, s2
);
1447 if (complement
&& s1
->has_char_class
1448 && ! (s2
->length
== s1
->length
&& homogeneous_spec_list (s2
)))
1450 error (EXIT_FAILURE
, 0,
1451 _("when translating with complemented character classes,\
1452 \nstring2 must map all characters in the domain to one"));
1455 if (s2
->has_restricted_char_class
)
1457 error (EXIT_FAILURE
, 0,
1458 _("when translating, the only character classes that may \
1459 appear in\nstring2 are `upper' and `lower'"));
1463 /* Not translating. */
1465 if (s2
->n_indefinite_repeats
> 0)
1466 error (EXIT_FAILURE
, 0,
1467 _("the [c*] construct may appear in string2 only \
1468 when translating"));
1473 /* Read buffers of SIZE bytes via the function READER (if READER is
1474 NULL, read from stdin) until EOF. When non-NULL, READER is either
1475 read_and_delete or read_and_xlate. After each buffer is read, it is
1476 processed and written to stdout. The buffers are processed so that
1477 multiple consecutive occurrences of the same character in the input
1478 stream are replaced by a single occurrence of that character if the
1479 character is in the squeeze set. */
1482 squeeze_filter (char *buf
, size_t size
, size_t (*reader
) (char *, size_t))
1484 /* A value distinct from any character that may have been stored in a
1485 buffer as the result of a block-read in the function squeeze_filter. */
1486 enum { NOT_A_CHAR
= CHAR_MAX
+ 1 };
1488 int char_to_squeeze
= NOT_A_CHAR
;
1498 nr
= reader (buf
, size
);
1506 if (char_to_squeeze
== NOT_A_CHAR
)
1509 /* Here, by being a little tricky, we can get a significant
1510 performance increase in most cases when the input is
1511 reasonably large. Since tr will modify the input only
1512 if two consecutive (and identical) input characters are
1513 in the squeeze set, we can step by two through the data
1514 when searching for a character in the squeeze set. This
1515 means there may be a little more work in a few cases and
1516 perhaps twice as much work in the worst cases where most
1517 of the input is removed by squeezing repeats. But most
1518 uses of this functionality seem to remove less than 20-30%
1520 for (; i
< nr
&& !in_squeeze_set
[to_uchar (buf
[i
])]; i
+= 2)
1523 /* There is a special case when i == nr and we've just
1524 skipped a character (the last one in buf) that is in
1526 if (i
== nr
&& in_squeeze_set
[to_uchar (buf
[i
- 1])])
1530 out_len
= nr
- begin
;
1533 char_to_squeeze
= buf
[i
];
1534 /* We're about to output buf[begin..i]. */
1535 out_len
= i
- begin
+ 1;
1537 /* But since we stepped by 2 in the loop above,
1538 out_len may be one too large. */
1539 if (i
> 0 && buf
[i
- 1] == char_to_squeeze
)
1542 /* Advance i to the index of first character to be
1543 considered when looking for a char different from
1548 && fwrite (&buf
[begin
], 1, out_len
, stdout
) != out_len
)
1549 error (EXIT_FAILURE
, errno
, _("write error"));
1552 if (char_to_squeeze
!= NOT_A_CHAR
)
1554 /* Advance i to index of first char != char_to_squeeze
1555 (or to nr if all the rest of the characters in this
1556 buffer are the same as char_to_squeeze). */
1557 for (; i
< nr
&& buf
[i
] == char_to_squeeze
; i
++)
1560 char_to_squeeze
= NOT_A_CHAR
;
1561 /* If (i >= nr) we've squeezed the last character in this buffer.
1562 So now we have to read a new buffer and continue comparing
1563 characters against char_to_squeeze. */
1569 plain_read (char *buf
, size_t size
)
1571 size_t nr
= safe_read (STDIN_FILENO
, buf
, size
);
1572 if (nr
== SAFE_READ_ERROR
)
1573 error (EXIT_FAILURE
, errno
, _("read error"));
1577 /* Read buffers of SIZE bytes from stdin until one is found that
1578 contains at least one character not in the delete set. Store
1579 in the array BUF, all characters from that buffer that are not
1580 in the delete set, and return the number of characters saved
1584 read_and_delete (char *buf
, size_t size
)
1588 /* This enclosing do-while loop is to make sure that
1589 we don't return zero (indicating EOF) when we've
1590 just deleted all the characters in a buffer. */
1594 size_t nr
= plain_read (buf
, size
);
1599 /* This first loop may be a waste of code, but gives much
1600 better performance when no characters are deleted in
1601 the beginning of a buffer. It just avoids the copying
1602 of buf[i] into buf[n_saved] when it would be a NOP. */
1604 for (i
= 0; i
< nr
&& !in_delete_set
[to_uchar (buf
[i
])]; i
++)
1608 for (++i
; i
< nr
; i
++)
1609 if (!in_delete_set
[to_uchar (buf
[i
])])
1610 buf
[n_saved
++] = buf
[i
];
1612 while (n_saved
== 0);
1617 /* Read at most SIZE bytes from stdin into the array BUF. Then
1618 perform the in-place and one-to-one mapping specified by the global
1619 array `xlate'. Return the number of characters read, or 0 upon EOF. */
1622 read_and_xlate (char *buf
, size_t size
)
1624 size_t bytes_read
= plain_read (buf
, size
);
1627 for (i
= 0; i
< bytes_read
; i
++)
1628 buf
[i
] = xlate
[to_uchar (buf
[i
])];
1633 /* Initialize a boolean membership set, IN_SET, with the character
1634 values obtained by traversing the linked list of constructs S
1635 using the function `get_next'. IN_SET is expected to have been
1636 initialized to all zeros by the caller. If COMPLEMENT_THIS_SET
1637 is true the resulting set is complemented. */
1640 set_initialize (struct Spec_list
*s
, bool complement_this_set
, bool *in_set
)
1645 s
->state
= BEGIN_STATE
;
1646 while ((c
= get_next (s
, NULL
)) != -1)
1648 if (complement_this_set
)
1649 for (i
= 0; i
< N_CHARS
; i
++)
1650 in_set
[i
] = (!in_set
[i
]);
1654 main (int argc
, char **argv
)
1657 int non_option_args
;
1660 struct Spec_list buf1
, buf2
;
1661 struct Spec_list
*s1
= &buf1
;
1662 struct Spec_list
*s2
= &buf2
;
1664 initialize_main (&argc
, &argv
);
1665 set_program_name (argv
[0]);
1666 setlocale (LC_ALL
, "");
1667 bindtextdomain (PACKAGE
, LOCALEDIR
);
1668 textdomain (PACKAGE
);
1670 atexit (close_stdout
);
1672 while ((c
= getopt_long (argc
, argv
, "+cCdst", long_options
, NULL
)) != -1)
1686 squeeze_repeats
= true;
1690 truncate_set1
= true;
1693 case_GETOPT_HELP_CHAR
;
1695 case_GETOPT_VERSION_CHAR (PROGRAM_NAME
, AUTHORS
);
1698 usage (EXIT_FAILURE
);
1703 non_option_args
= argc
- optind
;
1704 translating
= (non_option_args
== 2 && !delete);
1705 min_operands
= 1 + (delete == squeeze_repeats
);
1706 max_operands
= 1 + (delete <= squeeze_repeats
);
1708 if (non_option_args
< min_operands
)
1710 if (non_option_args
== 0)
1711 error (0, 0, _("missing operand"));
1714 error (0, 0, _("missing operand after %s"), quote (argv
[argc
- 1]));
1715 fprintf (stderr
, "%s\n",
1717 ? N_("Two strings must be given when "
1718 "both deleting and squeezing repeats.")
1719 : N_("Two strings must be given when translating.")));
1721 usage (EXIT_FAILURE
);
1724 if (max_operands
< non_option_args
)
1726 error (0, 0, _("extra operand %s"), quote (argv
[optind
+ max_operands
]));
1727 if (non_option_args
== 2)
1728 fprintf (stderr
, "%s\n",
1729 _("Only one string may be given when "
1730 "deleting without squeezing repeats."));
1731 usage (EXIT_FAILURE
);
1735 if (!parse_str (argv
[optind
], s1
))
1736 exit (EXIT_FAILURE
);
1738 if (non_option_args
== 2)
1741 if (!parse_str (argv
[optind
+ 1], s2
))
1742 exit (EXIT_FAILURE
);
1749 /* Use binary I/O, since `tr' is sometimes used to transliterate
1750 non-printable characters, or characters which are stripped away
1751 by text-mode reads (like CR and ^Z). */
1752 if (O_BINARY
&& ! isatty (STDIN_FILENO
))
1753 xfreopen (NULL
, "rb", stdin
);
1754 if (O_BINARY
&& ! isatty (STDOUT_FILENO
))
1755 xfreopen (NULL
, "wb", stdout
);
1757 if (squeeze_repeats
&& non_option_args
== 1)
1759 set_initialize (s1
, complement
, in_squeeze_set
);
1760 squeeze_filter (io_buf
, sizeof io_buf
, plain_read
);
1762 else if (delete && non_option_args
== 1)
1764 set_initialize (s1
, complement
, in_delete_set
);
1768 size_t nr
= read_and_delete (io_buf
, sizeof io_buf
);
1771 if (fwrite (io_buf
, 1, nr
, stdout
) != nr
)
1772 error (EXIT_FAILURE
, errno
, _("write error"));
1775 else if (squeeze_repeats
&& delete && non_option_args
== 2)
1777 set_initialize (s1
, complement
, in_delete_set
);
1778 set_initialize (s2
, false, in_squeeze_set
);
1779 squeeze_filter (io_buf
, sizeof io_buf
, read_and_delete
);
1781 else if (translating
)
1786 bool *in_s1
= in_delete_set
;
1788 set_initialize (s1
, false, in_s1
);
1789 s2
->state
= BEGIN_STATE
;
1790 for (i
= 0; i
< N_CHARS
; i
++)
1792 for (i
= 0; i
< N_CHARS
; i
++)
1796 int ch
= get_next (s2
, NULL
);
1797 assert (ch
!= -1 || truncate_set1
);
1800 /* This will happen when tr is invoked like e.g.
1801 tr -cs A-Za-z0-9 '\012'. */
1812 bool case_convert
= false;
1813 enum Upper_Lower_class class_s1
;
1814 enum Upper_Lower_class class_s2
;
1816 for (i
= 0; i
< N_CHARS
; i
++)
1818 s1
->state
= BEGIN_STATE
;
1819 s2
->state
= BEGIN_STATE
;
1822 /* When the previous pair identified case-converting classes,
1823 advance S1 and S2 so that each points to the following
1827 skip_construct (s1
);
1828 skip_construct (s2
);
1829 case_convert
= false;
1832 c1
= get_next (s1
, &class_s1
);
1833 c2
= get_next (s2
, &class_s2
);
1835 /* When translating and there is an [:upper:] or [:lower:]
1836 class in SET2, then there must be a corresponding [:lower:]
1837 or [:upper:] class in SET1. */
1838 if (class_s1
== UL_NONE
1839 && (class_s2
== UL_LOWER
|| class_s2
== UL_UPPER
))
1840 error (EXIT_FAILURE
, 0,
1841 _("misaligned [:upper:] and/or [:lower:] construct"));
1843 if (class_s1
== UL_LOWER
&& class_s2
== UL_UPPER
)
1845 case_convert
= true;
1846 for (i
= 0; i
< N_CHARS
; i
++)
1848 xlate
[i
] = toupper (i
);
1850 else if (class_s1
== UL_UPPER
&& class_s2
== UL_LOWER
)
1852 case_convert
= true;
1853 for (i
= 0; i
< N_CHARS
; i
++)
1855 xlate
[i
] = tolower (i
);
1857 else if ((class_s1
== UL_LOWER
&& class_s2
== UL_LOWER
)
1858 || (class_s1
== UL_UPPER
&& class_s2
== UL_UPPER
))
1860 /* POSIX says the behavior of `tr "[:upper:]" "[:upper:]"'
1861 is undefined. Treat it as a no-op. */
1865 /* The following should have been checked by validate... */
1866 if (c1
== -1 || c2
== -1)
1871 assert (c1
== -1 || truncate_set1
);
1873 if (squeeze_repeats
)
1875 set_initialize (s2
, false, in_squeeze_set
);
1876 squeeze_filter (io_buf
, sizeof io_buf
, read_and_xlate
);
1882 size_t bytes_read
= read_and_xlate (io_buf
, sizeof io_buf
);
1883 if (bytes_read
== 0)
1885 if (fwrite (io_buf
, 1, bytes_read
, stdout
) != bytes_read
)
1886 error (EXIT_FAILURE
, errno
, _("write error"));
1891 if (close (STDIN_FILENO
) != 0)
1892 error (EXIT_FAILURE
, errno
, _("standard input"));
1894 exit (EXIT_SUCCESS
);