1 /* tr -- a filter to translate characters
2 Copyright (C) 91, 1995-2008 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"
249 enum { N_CHAR_CLASSES
= sizeof char_class_name
/ sizeof char_class_name
[0] };
251 /* Array of boolean values. A character `c' is a member of the
252 squeeze set if and only if in_squeeze_set[c] is true. The squeeze
253 set is defined by the last (possibly, the only) string argument
254 on the command line when the squeeze option is given. */
255 static bool in_squeeze_set
[N_CHARS
];
257 /* Array of boolean values. A character `c' is a member of the
258 delete set if and only if in_delete_set[c] is true. The delete
259 set is defined by the first (or only) string argument on the
260 command line when the delete option is given. */
261 static bool in_delete_set
[N_CHARS
];
263 /* Array of character values defining the translation (if any) that
264 tr is to perform. Translation is performed only when there are
265 two specification strings and the delete switch is not given. */
266 static char xlate
[N_CHARS
];
268 static struct option
const long_options
[] =
270 {"complement", no_argument
, NULL
, 'c'},
271 {"delete", no_argument
, NULL
, 'd'},
272 {"squeeze-repeats", no_argument
, NULL
, 's'},
273 {"truncate-set1", no_argument
, NULL
, 't'},
274 {GETOPT_HELP_OPTION_DECL
},
275 {GETOPT_VERSION_OPTION_DECL
},
282 if (status
!= EXIT_SUCCESS
)
283 fprintf (stderr
, _("Try `%s --help' for more information.\n"),
288 Usage: %s [OPTION]... SET1 [SET2]\n\
292 Translate, squeeze, and/or delete characters from standard input,\n\
293 writing to standard output.\n\
295 -c, -C, --complement first complement SET1\n\
296 -d, --delete delete characters in SET1, do not translate\n\
297 -s, --squeeze-repeats replace each input sequence of a repeated character\n\
298 that is listed in SET1 with a single occurrence\n\
300 -t, --truncate-set1 first truncate SET1 to length of SET2\n\
302 fputs (HELP_OPTION_DESCRIPTION
, stdout
);
303 fputs (VERSION_OPTION_DESCRIPTION
, stdout
);
306 SETs are specified as strings of characters. Most represent themselves.\n\
307 Interpreted sequences are:\n\
309 \\NNN character with octal value NNN (1 to 3 octal digits)\n\
316 \\t horizontal tab\n\
320 CHAR1-CHAR2 all characters from CHAR1 to CHAR2 in ascending order\n\
321 [CHAR*] in SET2, copies of CHAR until length of SET1\n\
322 [CHAR*REPEAT] REPEAT copies of CHAR, REPEAT octal if starting with 0\n\
323 [:alnum:] all letters and digits\n\
324 [:alpha:] all letters\n\
325 [:blank:] all horizontal whitespace\n\
326 [:cntrl:] all control characters\n\
327 [:digit:] all digits\n\
330 [:graph:] all printable characters, not including space\n\
331 [:lower:] all lower case letters\n\
332 [:print:] all printable characters, including space\n\
333 [:punct:] all punctuation characters\n\
334 [:space:] all horizontal or vertical whitespace\n\
335 [:upper:] all upper case letters\n\
336 [:xdigit:] all hexadecimal digits\n\
337 [=CHAR=] all characters which are equivalent to CHAR\n\
341 Translation occurs if -d is not given and both SET1 and SET2 appear.\n\
342 -t may be used only when translating. SET2 is extended to length of\n\
343 SET1 by repeating its last character as necessary. Excess characters\n\
344 of SET2 are ignored. Only [:lower:] and [:upper:] are guaranteed to\n\
345 expand in ascending order; used in SET2 while translating, they may\n\
346 only be used in pairs to specify case conversion. -s uses SET1 if not\n\
347 translating nor deleting; else squeezing uses SET2 and occurs after\n\
348 translation or deletion.\n\
350 emit_bug_reporting_address ();
355 /* Return nonzero if the character C is a member of the
356 equivalence class containing the character EQUIV_CLASS. */
359 is_equiv_class_member (unsigned char equiv_class
, unsigned char c
)
361 return (equiv_class
== c
);
364 /* Return true if the character C is a member of the
365 character class CHAR_CLASS. */
368 is_char_class_member (enum Char_class char_class
, unsigned char c
)
375 result
= isalnum (c
);
378 result
= isalpha (c
);
381 result
= isblank (c
);
384 result
= iscntrl (c
);
387 result
= isdigit (c
);
390 result
= isgraph (c
);
393 result
= islower (c
);
396 result
= isprint (c
);
399 result
= ispunct (c
);
402 result
= isspace (c
);
405 result
= isupper (c
);
408 result
= isxdigit (c
);
419 es_free (struct E_string
*es
)
425 /* Perform the first pass over each range-spec argument S, converting all
426 \c and \ddd escapes to their one-byte representations. If an invalid
427 quote sequence is found print an error message and return false;
428 Otherwise set *ES to the resulting string and return true.
429 The resulting array of characters may contain zero-bytes;
430 however, on input, S is assumed to be null-terminated, and hence
431 cannot contain actual (non-escaped) zero bytes. */
434 unquote (char const *s
, struct E_string
*es
)
437 size_t len
= strlen (s
);
439 es
->s
= xmalloc (len
);
440 es
->escaped
= xcalloc (len
, sizeof es
->escaped
[0]);
443 for (i
= 0; s
[i
]; i
++)
451 es
->escaped
[j
] = true;
487 oct_digit
= s
[i
+ 2] - '0';
488 if (0 <= oct_digit
&& oct_digit
<= 7)
490 c
= 8 * c
+ oct_digit
;
492 oct_digit
= s
[i
+ 2] - '0';
493 if (0 <= oct_digit
&& oct_digit
<= 7)
495 if (8 * c
+ oct_digit
< N_CHARS
)
497 c
= 8 * c
+ oct_digit
;
502 /* A 3-digit octal number larger than \377 won't
503 fit in 8 bits. So we stop when adding the
504 next digit would put us over the limit and
505 give a warning about the ambiguity. POSIX
506 isn't clear on this, and we interpret this
507 lack of clarity as meaning the resulting behavior
508 is undefined, which means we're allowed to issue
510 error (0, 0, _("warning: the ambiguous octal escape \
511 \\%c%c%c is being\n\tinterpreted as the 2-byte sequence \\0%c%c, %c"),
512 s
[i
], s
[i
+ 1], s
[i
+ 2],
513 s
[i
], s
[i
+ 1], s
[i
+ 2]);
519 error (0, 0, _("warning: an unescaped backslash "
520 "at end of string is not portable"));
521 /* POSIX is not clear about this. */
522 es
->escaped
[j
] = false;
542 /* If CLASS_STR is a valid character class string, return its index
543 in the global char_class_name array. Otherwise, return CC_NO_CLASS. */
545 static enum Char_class
546 look_up_char_class (char const *class_str
, size_t len
)
550 for (i
= 0; i
< N_CHAR_CLASSES
; i
++)
551 if (strncmp (class_str
, char_class_name
[i
], len
) == 0
552 && strlen (char_class_name
[i
]) == len
)
557 /* Return a newly allocated string with a printable version of C.
558 This function is used solely for formatting error messages. */
561 make_printable_char (unsigned char c
)
563 char *buf
= xmalloc (5);
572 sprintf (buf
, "\\%03o", c
);
577 /* Return a newly allocated copy of S which is suitable for printing.
578 LEN is the number of characters in S. Most non-printing
579 (isprint) characters are represented by a backslash followed by
580 3 octal digits. However, the characters represented by \c escapes
581 where c is one of [abfnrtv] are represented by their 2-character \c
582 sequences. This function is used solely for printing error messages. */
585 make_printable_str (char const *s
, size_t len
)
587 /* Worst case is that every character expands to a backslash
588 followed by a 3-character octal escape sequence. */
589 char *printable_buf
= xnmalloc (len
+ 1, 4);
590 char *p
= printable_buf
;
593 for (i
= 0; i
< len
; i
++)
596 char const *tmp
= NULL
;
597 unsigned char c
= s
[i
];
632 sprintf (buf
, "\\%03o", c
);
638 return printable_buf
;
641 /* Append a newly allocated structure representing a
642 character C to the specification list LIST. */
645 append_normal_char (struct Spec_list
*list
, unsigned char c
)
647 struct List_element
*new;
649 new = xmalloc (sizeof *new);
651 new->type
= RE_NORMAL_CHAR
;
652 new->u
.normal_char
= c
;
654 list
->tail
->next
= new;
658 /* Append a newly allocated structure representing the range
659 of characters from FIRST to LAST to the specification list LIST.
660 Return false if LAST precedes FIRST in the collating sequence,
661 true otherwise. This means that '[c-c]' is acceptable. */
664 append_range (struct Spec_list
*list
, unsigned char first
, unsigned char last
)
666 struct List_element
*new;
670 char *tmp1
= make_printable_char (first
);
671 char *tmp2
= make_printable_char (last
);
674 _("range-endpoints of `%s-%s' are in reverse collating sequence order"),
680 new = xmalloc (sizeof *new);
682 new->type
= RE_RANGE
;
683 new->u
.range
.first_char
= first
;
684 new->u
.range
.last_char
= last
;
686 list
->tail
->next
= new;
691 /* If CHAR_CLASS_STR is a valid character class string, append a
692 newly allocated structure representing that character class to the end
693 of the specification list LIST and return true. If CHAR_CLASS_STR is not
694 a valid string return false. */
697 append_char_class (struct Spec_list
*list
,
698 char const *char_class_str
, size_t len
)
700 enum Char_class char_class
;
701 struct List_element
*new;
703 char_class
= look_up_char_class (char_class_str
, len
);
704 if (char_class
== CC_NO_CLASS
)
706 new = xmalloc (sizeof *new);
708 new->type
= RE_CHAR_CLASS
;
709 new->u
.char_class
= char_class
;
711 list
->tail
->next
= new;
716 /* Append a newly allocated structure representing a [c*n]
717 repeated character construct to the specification list LIST.
718 THE_CHAR is the single character to be repeated, and REPEAT_COUNT
719 is a non-negative repeat count. */
722 append_repeated_char (struct Spec_list
*list
, unsigned char the_char
,
725 struct List_element
*new;
727 new = xmalloc (sizeof *new);
729 new->type
= RE_REPEATED_CHAR
;
730 new->u
.repeated_char
.the_repeated_char
= the_char
;
731 new->u
.repeated_char
.repeat_count
= repeat_count
;
733 list
->tail
->next
= new;
737 /* Given a string, EQUIV_CLASS_STR, from a [=str=] context and
738 the length of that string, LEN, if LEN is exactly one, append
739 a newly allocated structure representing the specified
740 equivalence class to the specification list, LIST and return true.
741 If LEN is not 1, return false. */
744 append_equiv_class (struct Spec_list
*list
,
745 char const *equiv_class_str
, size_t len
)
747 struct List_element
*new;
751 new = xmalloc (sizeof *new);
753 new->type
= RE_EQUIV_CLASS
;
754 new->u
.equiv_code
= *equiv_class_str
;
756 list
->tail
->next
= new;
761 /* Search forward starting at START_IDX for the 2-char sequence
762 (PRE_BRACKET_CHAR,']') in the string P of length P_LEN. If such
763 a sequence is found, set *RESULT_IDX to the index of the first
764 character and return true. Otherwise return false. P may contain
768 find_closing_delim (const struct E_string
*es
, size_t start_idx
,
769 char pre_bracket_char
, size_t *result_idx
)
773 for (i
= start_idx
; i
< es
->len
- 1; i
++)
774 if (es
->s
[i
] == pre_bracket_char
&& es
->s
[i
+ 1] == ']'
775 && !es
->escaped
[i
] && !es
->escaped
[i
+ 1])
783 /* Parse the bracketed repeat-char syntax. If the P_LEN characters
784 beginning with P[ START_IDX ] comprise a valid [c*n] construct,
785 then set *CHAR_TO_REPEAT, *REPEAT_COUNT, and *CLOSING_BRACKET_IDX
786 and return zero. If the second character following
787 the opening bracket is not `*' or if no closing bracket can be
788 found, return -1. If a closing bracket is found and the
789 second char is `*', but the string between the `*' and `]' isn't
790 empty, an octal number, or a decimal number, print an error message
794 find_bracketed_repeat (const struct E_string
*es
, size_t start_idx
,
795 unsigned char *char_to_repeat
, count
*repeat_count
,
796 size_t *closing_bracket_idx
)
800 assert (start_idx
+ 1 < es
->len
);
801 if (!es_match (es
, start_idx
+ 1, '*'))
804 for (i
= start_idx
+ 2; i
< es
->len
&& !es
->escaped
[i
]; i
++)
808 size_t digit_str_len
= i
- start_idx
- 2;
810 *char_to_repeat
= es
->s
[start_idx
];
811 if (digit_str_len
== 0)
813 /* We've matched [c*] -- no explicit repeat count. */
818 /* Here, we have found [c*s] where s should be a string
819 of octal (if it starts with `0') or decimal digits. */
820 char const *digit_str
= &es
->s
[start_idx
+ 2];
822 if ((xstrtoumax (digit_str
, &d_end
, *digit_str
== '0' ? 8 : 10,
825 || REPEAT_COUNT_MAXIMUM
< *repeat_count
826 || digit_str
+ digit_str_len
!= d_end
)
828 char *tmp
= make_printable_str (digit_str
, digit_str_len
);
830 _("invalid repeat count %s in [c*n] construct"),
836 *closing_bracket_idx
= i
;
840 return -1; /* No bracket found. */
843 /* Return true if the string at ES->s[IDX] matches the regular
844 expression `\*[0-9]*\]', false otherwise. The string does not
845 match if any of its characters are escaped. */
848 star_digits_closebracket (const struct E_string
*es
, size_t idx
)
852 if (!es_match (es
, idx
, '*'))
855 for (i
= idx
+ 1; i
< es
->len
; i
++)
856 if (!ISDIGIT (to_uchar (es
->s
[i
])) || es
->escaped
[i
])
857 return es_match (es
, i
, ']');
861 /* Convert string UNESCAPED_STRING (which has been preprocessed to
862 convert backslash-escape sequences) of length LEN characters into
863 a linked list of the following 5 types of constructs:
864 - [:str:] Character class where `str' is one of the 12 valid strings.
865 - [=c=] Equivalence class where `c' is any single character.
866 - [c*n] Repeat the single character `c' `n' times. n may be omitted.
867 However, if `n' is present, it must be a non-negative octal or
869 - r-s Range of characters from `r' to `s'. The second endpoint must
870 not precede the first in the current collating sequence.
871 - c Any other character is interpreted as itself. */
874 build_spec_list (const struct E_string
*es
, struct Spec_list
*result
)
881 /* The main for-loop below recognizes the 4 multi-character constructs.
882 A character that matches (in its context) none of the multi-character
883 constructs is classified as `normal'. Since all multi-character
884 constructs have at least 3 characters, any strings of length 2 or
885 less are composed solely of normal characters. Hence, the index of
886 the outer for-loop runs only as far as LEN-2. */
888 for (i
= 0; i
+ 2 < es
->len
; /* empty */)
890 if (es_match (es
, i
, '['))
892 bool matched_multi_char_construct
;
893 size_t closing_bracket_idx
;
894 unsigned char char_to_repeat
;
898 matched_multi_char_construct
= true;
899 if (es_match (es
, i
+ 1, ':') || es_match (es
, i
+ 1, '='))
901 size_t closing_delim_idx
;
903 if (find_closing_delim (es
, i
+ 2, p
[i
+ 1], &closing_delim_idx
))
905 size_t opnd_str_len
= closing_delim_idx
- 1 - (i
+ 2) + 1;
906 char const *opnd_str
= p
+ i
+ 2;
908 if (opnd_str_len
== 0)
911 error (0, 0, _("missing character class name `[::]'"));
914 _("missing equivalence class character `[==]'"));
920 /* FIXME: big comment. */
921 if (!append_char_class (result
, opnd_str
, opnd_str_len
))
923 if (star_digits_closebracket (es
, i
+ 2))
924 goto try_bracketed_repeat
;
927 char *tmp
= make_printable_str (opnd_str
,
929 error (0, 0, _("invalid character class %s"),
938 /* FIXME: big comment. */
939 if (!append_equiv_class (result
, opnd_str
, opnd_str_len
))
941 if (star_digits_closebracket (es
, i
+ 2))
942 goto try_bracketed_repeat
;
945 char *tmp
= make_printable_str (opnd_str
,
948 _("%s: equivalence class operand must be a single character"),
956 i
= closing_delim_idx
+ 2;
959 /* Else fall through. This could be [:*] or [=*]. */
962 try_bracketed_repeat
:
964 /* Determine whether this is a bracketed repeat range
965 matching the RE \[.\*(dec_or_oct_number)?\]. */
966 err
= find_bracketed_repeat (es
, i
+ 1, &char_to_repeat
,
968 &closing_bracket_idx
);
971 append_repeated_char (result
, char_to_repeat
, repeat_count
);
972 i
= closing_bracket_idx
+ 1;
976 matched_multi_char_construct
= false;
980 /* Found a string that looked like [c*n] but the
981 numeric part was invalid. */
985 if (matched_multi_char_construct
)
988 /* We reach this point if P does not match [:str:], [=c=],
989 [c*n], or [c*]. Now, see if P looks like a range `[-c'
990 (from `[' to `c'). */
993 /* Look ahead one char for ranges like a-z. */
994 if (es_match (es
, i
+ 1, '-'))
996 if (!append_range (result
, p
[i
], p
[i
+ 2]))
1002 append_normal_char (result
, p
[i
]);
1007 /* Now handle the (2 or fewer) remaining characters p[i]..p[es->len - 1]. */
1008 for (; i
< es
->len
; i
++)
1009 append_normal_char (result
, p
[i
]);
1014 /* Advance past the current construct.
1015 S->tail must be non-NULL. */
1017 skip_construct (struct Spec_list
*s
)
1019 s
->tail
= s
->tail
->next
;
1020 s
->state
= NEW_ELEMENT
;
1023 /* Given a Spec_list S (with its saved state implicit in the values
1024 of its members `tail' and `state'), return the next single character
1025 in the expansion of S's constructs. If the last character of S was
1026 returned on the previous call or if S was empty, this function
1027 returns -1. For example, successive calls to get_next where S
1028 represents the spec-string 'a-d[y*3]' will return the sequence
1029 of values a, b, c, d, y, y, y, -1. Finally, if the construct from
1030 which the returned character comes is [:upper:] or [:lower:], the
1031 parameter CLASS is given a value to indicate which it was. Otherwise
1032 CLASS is set to UL_NONE. This value is used only when constructing
1033 the translation table to verify that any occurrences of upper and
1034 lower class constructs in the spec-strings appear in the same relative
1038 get_next (struct Spec_list
*s
, enum Upper_Lower_class
*class)
1040 struct List_element
*p
;
1047 if (s
->state
== BEGIN_STATE
)
1049 s
->tail
= s
->head
->next
;
1050 s
->state
= NEW_ELEMENT
;
1059 case RE_NORMAL_CHAR
:
1060 return_val
= p
->u
.normal_char
;
1061 s
->state
= NEW_ELEMENT
;
1066 if (s
->state
== NEW_ELEMENT
)
1067 s
->state
= p
->u
.range
.first_char
;
1070 return_val
= s
->state
;
1071 if (s
->state
== p
->u
.range
.last_char
)
1074 s
->state
= NEW_ELEMENT
;
1081 switch (p
->u
.char_class
)
1094 if (s
->state
== NEW_ELEMENT
)
1096 for (i
= 0; i
< N_CHARS
; i
++)
1097 if (is_char_class_member (p
->u
.char_class
, i
))
1099 assert (i
< N_CHARS
);
1102 assert (is_char_class_member (p
->u
.char_class
, s
->state
));
1103 return_val
= s
->state
;
1104 for (i
= s
->state
+ 1; i
< N_CHARS
; i
++)
1105 if (is_char_class_member (p
->u
.char_class
, i
))
1112 s
->state
= NEW_ELEMENT
;
1116 case RE_EQUIV_CLASS
:
1117 /* FIXME: this assumes that each character is alone in its own
1118 equivalence class (which appears to be correct for my
1119 LC_COLLATE. But I don't know of any function that allows
1120 one to determine a character's equivalence class. */
1122 return_val
= p
->u
.equiv_code
;
1123 s
->state
= NEW_ELEMENT
;
1127 case RE_REPEATED_CHAR
:
1128 /* Here, a repeat count of n == 0 means don't repeat at all. */
1129 if (p
->u
.repeated_char
.repeat_count
== 0)
1132 s
->state
= NEW_ELEMENT
;
1133 return_val
= get_next (s
, class);
1137 if (s
->state
== NEW_ELEMENT
)
1142 return_val
= p
->u
.repeated_char
.the_repeated_char
;
1143 if (s
->state
== p
->u
.repeated_char
.repeat_count
)
1146 s
->state
= NEW_ELEMENT
;
1159 /* This is a minor kludge. This function is called from
1160 get_spec_stats to determine the cardinality of a set derived
1161 from a complemented string. It's a kludge in that some of the
1162 same operations are (duplicated) performed in set_initialize. */
1165 card_of_complement (struct Spec_list
*s
)
1168 int cardinality
= N_CHARS
;
1169 bool in_set
[N_CHARS
] = { 0, };
1171 s
->state
= BEGIN_STATE
;
1172 while ((c
= get_next (s
, NULL
)) != -1)
1174 cardinality
-= (!in_set
[c
]);
1180 /* Gather statistics about the spec-list S in preparation for the tests
1181 in validate that determine the consistency of the specs. This function
1182 is called at most twice; once for string1, and again for any string2.
1183 LEN_S1 < 0 indicates that this is the first call and that S represents
1184 string1. When LEN_S1 >= 0, it is the length of the expansion of the
1185 constructs in string1, and we can use its value to resolve any
1186 indefinite repeat construct in S (which represents string2). Hence,
1187 this function has the side-effect that it converts a valid [c*]
1188 construct in string2 to [c*n] where n is large enough (or 0) to give
1189 string2 the same length as string1. For example, with the command
1190 tr a-z 'A[\n*]Z' on the second call to get_spec_stats, LEN_S1 would
1191 be 26 and S (representing string2) would be converted to 'A[\n*24]Z'. */
1194 get_spec_stats (struct Spec_list
*s
)
1196 struct List_element
*p
;
1199 s
->n_indefinite_repeats
= 0;
1200 s
->has_equiv_class
= false;
1201 s
->has_restricted_char_class
= false;
1202 s
->has_char_class
= false;
1203 for (p
= s
->head
->next
; p
; p
= p
->next
)
1211 case RE_NORMAL_CHAR
:
1216 assert (p
->u
.range
.last_char
>= p
->u
.range
.first_char
);
1217 len
= p
->u
.range
.last_char
- p
->u
.range
.first_char
+ 1;
1221 s
->has_char_class
= true;
1222 for (i
= 0; i
< N_CHARS
; i
++)
1223 if (is_char_class_member (p
->u
.char_class
, i
))
1225 switch (p
->u
.char_class
)
1231 s
->has_restricted_char_class
= true;
1236 case RE_EQUIV_CLASS
:
1237 for (i
= 0; i
< N_CHARS
; i
++)
1238 if (is_equiv_class_member (p
->u
.equiv_code
, i
))
1240 s
->has_equiv_class
= true;
1243 case RE_REPEATED_CHAR
:
1244 if (p
->u
.repeated_char
.repeat_count
> 0)
1245 len
= p
->u
.repeated_char
.repeat_count
;
1248 s
->indefinite_repeat_element
= p
;
1249 ++(s
->n_indefinite_repeats
);
1258 /* Check for arithmetic overflow in computing length. Also, reject
1259 any length greater than the maximum repeat count, in case the
1260 length is later used to compute the repeat count for an
1261 indefinite element. */
1262 new_length
= length
+ len
;
1263 if (! (length
<= new_length
&& new_length
<= REPEAT_COUNT_MAXIMUM
))
1264 error (EXIT_FAILURE
, 0, _("too many characters in set"));
1265 length
= new_length
;
1272 get_s1_spec_stats (struct Spec_list
*s1
)
1274 get_spec_stats (s1
);
1276 s1
->length
= card_of_complement (s1
);
1280 get_s2_spec_stats (struct Spec_list
*s2
, count len_s1
)
1282 get_spec_stats (s2
);
1283 if (len_s1
>= s2
->length
&& s2
->n_indefinite_repeats
== 1)
1285 s2
->indefinite_repeat_element
->u
.repeated_char
.repeat_count
=
1286 len_s1
- s2
->length
;
1287 s2
->length
= len_s1
;
1292 spec_init (struct Spec_list
*spec_list
)
1294 struct List_element
*new = xmalloc (sizeof *new);
1295 spec_list
->head
= spec_list
->tail
= new;
1296 spec_list
->head
->next
= NULL
;
1299 /* This function makes two passes over the argument string S. The first
1300 one converts all \c and \ddd escapes to their one-byte representations.
1301 The second constructs a linked specification list, SPEC_LIST, of the
1302 characters and constructs that comprise the argument string. If either
1303 of these passes detects an error, this function returns false. */
1306 parse_str (char const *s
, struct Spec_list
*spec_list
)
1309 bool ok
= unquote (s
, &es
) && build_spec_list (&es
, spec_list
);
1314 /* Given two specification lists, S1 and S2, and assuming that
1315 S1->length > S2->length, append a single [c*n] element to S2 where c
1316 is the last character in the expansion of S2 and n is the difference
1317 between the two lengths.
1318 Upon successful completion, S2->length is set to S1->length. The only
1319 way this function can fail to make S2 as long as S1 is when S2 has
1320 zero-length, since in that case, there is no last character to repeat.
1321 So S2->length is required to be at least 1.
1323 Providing this functionality allows the user to do some pretty
1324 non-BSD (and non-portable) things: For example, the command
1325 tr -cs '[:upper:]0-9' '[:lower:]'
1326 is almost guaranteed to give results that depend on your collating
1330 string2_extend (const struct Spec_list
*s1
, struct Spec_list
*s2
)
1332 struct List_element
*p
;
1333 unsigned char char_to_repeat
;
1336 assert (translating
);
1337 assert (s1
->length
> s2
->length
);
1338 assert (s2
->length
> 0);
1343 case RE_NORMAL_CHAR
:
1344 char_to_repeat
= p
->u
.normal_char
;
1347 char_to_repeat
= p
->u
.range
.last_char
;
1350 for (i
= N_CHARS
- 1; i
>= 0; i
--)
1351 if (is_char_class_member (p
->u
.char_class
, i
))
1357 case RE_REPEATED_CHAR
:
1358 char_to_repeat
= p
->u
.repeated_char
.the_repeated_char
;
1361 case RE_EQUIV_CLASS
:
1362 /* This shouldn't happen, because validate exits with an error
1363 if it finds an equiv class in string2 when translating. */
1372 append_repeated_char (s2
, char_to_repeat
, s1
->length
- s2
->length
);
1373 s2
->length
= s1
->length
;
1376 /* Return true if S is a non-empty list in which exactly one
1377 character (but potentially, many instances of it) appears.
1378 E.g., [X*] or xxxxxxxx. */
1381 homogeneous_spec_list (struct Spec_list
*s
)
1385 s
->state
= BEGIN_STATE
;
1387 if ((b
= get_next (s
, NULL
)) == -1)
1390 while ((c
= get_next (s
, NULL
)) != -1)
1397 /* Die with an error message if S1 and S2 describe strings that
1398 are not valid with the given command line switches.
1399 A side effect of this function is that if a valid [c*] or
1400 [c*0] construct appears in string2, it is converted to [c*n]
1401 with a value for n that makes s2->length == s1->length. By
1402 the same token, if the --truncate-set1 option is not
1403 given, S2 may be extended. */
1406 validate (struct Spec_list
*s1
, struct Spec_list
*s2
)
1408 get_s1_spec_stats (s1
);
1409 if (s1
->n_indefinite_repeats
> 0)
1411 error (EXIT_FAILURE
, 0,
1412 _("the [c*] repeat construct may not appear in string1"));
1417 get_s2_spec_stats (s2
, s1
->length
);
1419 if (s2
->n_indefinite_repeats
> 1)
1421 error (EXIT_FAILURE
, 0,
1422 _("only one [c*] repeat construct may appear in string2"));
1427 if (s2
->has_equiv_class
)
1429 error (EXIT_FAILURE
, 0,
1430 _("[=c=] expressions may not appear in string2 \
1431 when translating"));
1434 if (s1
->length
> s2
->length
)
1438 /* string2 must be non-empty unless --truncate-set1 is
1439 given or string1 is empty. */
1441 if (s2
->length
== 0)
1442 error (EXIT_FAILURE
, 0,
1443 _("when not truncating set1, string2 must be non-empty"));
1444 string2_extend (s1
, s2
);
1448 if (complement
&& s1
->has_char_class
1449 && ! (s2
->length
== s1
->length
&& homogeneous_spec_list (s2
)))
1451 error (EXIT_FAILURE
, 0,
1452 _("when translating with complemented character classes,\
1453 \nstring2 must map all characters in the domain to one"));
1456 if (s2
->has_restricted_char_class
)
1458 error (EXIT_FAILURE
, 0,
1459 _("when translating, the only character classes that may \
1460 appear in\nstring2 are `upper' and `lower'"));
1464 /* Not translating. */
1466 if (s2
->n_indefinite_repeats
> 0)
1467 error (EXIT_FAILURE
, 0,
1468 _("the [c*] construct may appear in string2 only \
1469 when translating"));
1474 /* Read buffers of SIZE bytes via the function READER (if READER is
1475 NULL, read from stdin) until EOF. When non-NULL, READER is either
1476 read_and_delete or read_and_xlate. After each buffer is read, it is
1477 processed and written to stdout. The buffers are processed so that
1478 multiple consecutive occurrences of the same character in the input
1479 stream are replaced by a single occurrence of that character if the
1480 character is in the squeeze set. */
1483 squeeze_filter (char *buf
, size_t size
, size_t (*reader
) (char *, size_t))
1485 /* A value distinct from any character that may have been stored in a
1486 buffer as the result of a block-read in the function squeeze_filter. */
1487 enum { NOT_A_CHAR
= CHAR_MAX
+ 1 };
1489 int char_to_squeeze
= NOT_A_CHAR
;
1499 nr
= reader (buf
, size
);
1507 if (char_to_squeeze
== NOT_A_CHAR
)
1510 /* Here, by being a little tricky, we can get a significant
1511 performance increase in most cases when the input is
1512 reasonably large. Since tr will modify the input only
1513 if two consecutive (and identical) input characters are
1514 in the squeeze set, we can step by two through the data
1515 when searching for a character in the squeeze set. This
1516 means there may be a little more work in a few cases and
1517 perhaps twice as much work in the worst cases where most
1518 of the input is removed by squeezing repeats. But most
1519 uses of this functionality seem to remove less than 20-30%
1521 for (; i
< nr
&& !in_squeeze_set
[to_uchar (buf
[i
])]; i
+= 2)
1524 /* There is a special case when i == nr and we've just
1525 skipped a character (the last one in buf) that is in
1527 if (i
== nr
&& in_squeeze_set
[to_uchar (buf
[i
- 1])])
1531 out_len
= nr
- begin
;
1534 char_to_squeeze
= buf
[i
];
1535 /* We're about to output buf[begin..i]. */
1536 out_len
= i
- begin
+ 1;
1538 /* But since we stepped by 2 in the loop above,
1539 out_len may be one too large. */
1540 if (i
> 0 && buf
[i
- 1] == char_to_squeeze
)
1543 /* Advance i to the index of first character to be
1544 considered when looking for a char different from
1549 && fwrite (&buf
[begin
], 1, out_len
, stdout
) != out_len
)
1550 error (EXIT_FAILURE
, errno
, _("write error"));
1553 if (char_to_squeeze
!= NOT_A_CHAR
)
1555 /* Advance i to index of first char != char_to_squeeze
1556 (or to nr if all the rest of the characters in this
1557 buffer are the same as char_to_squeeze). */
1558 for (; i
< nr
&& buf
[i
] == char_to_squeeze
; i
++)
1561 char_to_squeeze
= NOT_A_CHAR
;
1562 /* If (i >= nr) we've squeezed the last character in this buffer.
1563 So now we have to read a new buffer and continue comparing
1564 characters against char_to_squeeze. */
1570 plain_read (char *buf
, size_t size
)
1572 size_t nr
= safe_read (STDIN_FILENO
, buf
, size
);
1573 if (nr
== SAFE_READ_ERROR
)
1574 error (EXIT_FAILURE
, errno
, _("read error"));
1578 /* Read buffers of SIZE bytes from stdin until one is found that
1579 contains at least one character not in the delete set. Store
1580 in the array BUF, all characters from that buffer that are not
1581 in the delete set, and return the number of characters saved
1585 read_and_delete (char *buf
, size_t size
)
1589 /* This enclosing do-while loop is to make sure that
1590 we don't return zero (indicating EOF) when we've
1591 just deleted all the characters in a buffer. */
1595 size_t nr
= plain_read (buf
, size
);
1600 /* This first loop may be a waste of code, but gives much
1601 better performance when no characters are deleted in
1602 the beginning of a buffer. It just avoids the copying
1603 of buf[i] into buf[n_saved] when it would be a NOP. */
1605 for (i
= 0; i
< nr
&& !in_delete_set
[to_uchar (buf
[i
])]; i
++)
1609 for (++i
; i
< nr
; i
++)
1610 if (!in_delete_set
[to_uchar (buf
[i
])])
1611 buf
[n_saved
++] = buf
[i
];
1613 while (n_saved
== 0);
1618 /* Read at most SIZE bytes from stdin into the array BUF. Then
1619 perform the in-place and one-to-one mapping specified by the global
1620 array `xlate'. Return the number of characters read, or 0 upon EOF. */
1623 read_and_xlate (char *buf
, size_t size
)
1625 size_t bytes_read
= plain_read (buf
, size
);
1628 for (i
= 0; i
< bytes_read
; i
++)
1629 buf
[i
] = xlate
[to_uchar (buf
[i
])];
1634 /* Initialize a boolean membership set, IN_SET, with the character
1635 values obtained by traversing the linked list of constructs S
1636 using the function `get_next'. IN_SET is expected to have been
1637 initialized to all zeros by the caller. If COMPLEMENT_THIS_SET
1638 is true the resulting set is complemented. */
1641 set_initialize (struct Spec_list
*s
, bool complement_this_set
, bool *in_set
)
1646 s
->state
= BEGIN_STATE
;
1647 while ((c
= get_next (s
, NULL
)) != -1)
1649 if (complement_this_set
)
1650 for (i
= 0; i
< N_CHARS
; i
++)
1651 in_set
[i
] = (!in_set
[i
]);
1655 main (int argc
, char **argv
)
1658 int non_option_args
;
1661 struct Spec_list buf1
, buf2
;
1662 struct Spec_list
*s1
= &buf1
;
1663 struct Spec_list
*s2
= &buf2
;
1665 initialize_main (&argc
, &argv
);
1666 set_program_name (argv
[0]);
1667 setlocale (LC_ALL
, "");
1668 bindtextdomain (PACKAGE
, LOCALEDIR
);
1669 textdomain (PACKAGE
);
1671 atexit (close_stdout
);
1673 while ((c
= getopt_long (argc
, argv
, "+cCdst", long_options
, NULL
)) != -1)
1687 squeeze_repeats
= true;
1691 truncate_set1
= true;
1694 case_GETOPT_HELP_CHAR
;
1696 case_GETOPT_VERSION_CHAR (PROGRAM_NAME
, AUTHORS
);
1699 usage (EXIT_FAILURE
);
1704 non_option_args
= argc
- optind
;
1705 translating
= (non_option_args
== 2 && !delete);
1706 min_operands
= 1 + (delete == squeeze_repeats
);
1707 max_operands
= 1 + (delete <= squeeze_repeats
);
1709 if (non_option_args
< min_operands
)
1711 if (non_option_args
== 0)
1712 error (0, 0, _("missing operand"));
1715 error (0, 0, _("missing operand after %s"), quote (argv
[argc
- 1]));
1716 fprintf (stderr
, "%s\n",
1718 ? N_("Two strings must be given when "
1719 "both deleting and squeezing repeats.")
1720 : N_("Two strings must be given when translating.")));
1722 usage (EXIT_FAILURE
);
1725 if (max_operands
< non_option_args
)
1727 error (0, 0, _("extra operand %s"), quote (argv
[optind
+ max_operands
]));
1728 if (non_option_args
== 2)
1729 fprintf (stderr
, "%s\n",
1730 _("Only one string may be given when "
1731 "deleting without squeezing repeats."));
1732 usage (EXIT_FAILURE
);
1736 if (!parse_str (argv
[optind
], s1
))
1737 exit (EXIT_FAILURE
);
1739 if (non_option_args
== 2)
1742 if (!parse_str (argv
[optind
+ 1], s2
))
1743 exit (EXIT_FAILURE
);
1750 /* Use binary I/O, since `tr' is sometimes used to transliterate
1751 non-printable characters, or characters which are stripped away
1752 by text-mode reads (like CR and ^Z). */
1753 if (O_BINARY
&& ! isatty (STDIN_FILENO
))
1754 xfreopen (NULL
, "rb", stdin
);
1755 if (O_BINARY
&& ! isatty (STDOUT_FILENO
))
1756 xfreopen (NULL
, "wb", stdout
);
1758 if (squeeze_repeats
&& non_option_args
== 1)
1760 set_initialize (s1
, complement
, in_squeeze_set
);
1761 squeeze_filter (io_buf
, sizeof io_buf
, plain_read
);
1763 else if (delete && non_option_args
== 1)
1765 set_initialize (s1
, complement
, in_delete_set
);
1769 size_t nr
= read_and_delete (io_buf
, sizeof io_buf
);
1772 if (fwrite (io_buf
, 1, nr
, stdout
) != nr
)
1773 error (EXIT_FAILURE
, errno
, _("write error"));
1776 else if (squeeze_repeats
&& delete && non_option_args
== 2)
1778 set_initialize (s1
, complement
, in_delete_set
);
1779 set_initialize (s2
, false, in_squeeze_set
);
1780 squeeze_filter (io_buf
, sizeof io_buf
, read_and_delete
);
1782 else if (translating
)
1787 bool *in_s1
= in_delete_set
;
1789 set_initialize (s1
, false, in_s1
);
1790 s2
->state
= BEGIN_STATE
;
1791 for (i
= 0; i
< N_CHARS
; i
++)
1793 for (i
= 0; i
< N_CHARS
; i
++)
1797 int ch
= get_next (s2
, NULL
);
1798 assert (ch
!= -1 || truncate_set1
);
1801 /* This will happen when tr is invoked like e.g.
1802 tr -cs A-Za-z0-9 '\012'. */
1813 bool case_convert
= false;
1814 enum Upper_Lower_class class_s1
;
1815 enum Upper_Lower_class class_s2
;
1817 for (i
= 0; i
< N_CHARS
; i
++)
1819 s1
->state
= BEGIN_STATE
;
1820 s2
->state
= BEGIN_STATE
;
1823 /* When the previous pair identified case-converting classes,
1824 advance S1 and S2 so that each points to the following
1828 skip_construct (s1
);
1829 skip_construct (s2
);
1830 case_convert
= false;
1833 c1
= get_next (s1
, &class_s1
);
1834 c2
= get_next (s2
, &class_s2
);
1836 /* When translating and there is an [:upper:] or [:lower:]
1837 class in SET2, then there must be a corresponding [:lower:]
1838 or [:upper:] class in SET1. */
1839 if (class_s1
== UL_NONE
1840 && (class_s2
== UL_LOWER
|| class_s2
== UL_UPPER
))
1841 error (EXIT_FAILURE
, 0,
1842 _("misaligned [:upper:] and/or [:lower:] construct"));
1844 if (class_s1
== UL_LOWER
&& class_s2
== UL_UPPER
)
1846 case_convert
= true;
1847 for (i
= 0; i
< N_CHARS
; i
++)
1849 xlate
[i
] = toupper (i
);
1851 else if (class_s1
== UL_UPPER
&& class_s2
== UL_LOWER
)
1853 case_convert
= true;
1854 for (i
= 0; i
< N_CHARS
; i
++)
1856 xlate
[i
] = tolower (i
);
1858 else if ((class_s1
== UL_LOWER
&& class_s2
== UL_LOWER
)
1859 || (class_s1
== UL_UPPER
&& class_s2
== UL_UPPER
))
1861 /* POSIX says the behavior of `tr "[:upper:]" "[:upper:]"'
1862 is undefined. Treat it as a no-op. */
1866 /* The following should have been checked by validate... */
1867 if (c1
== -1 || c2
== -1)
1872 assert (c1
== -1 || truncate_set1
);
1874 if (squeeze_repeats
)
1876 set_initialize (s2
, false, in_squeeze_set
);
1877 squeeze_filter (io_buf
, sizeof io_buf
, read_and_xlate
);
1883 size_t bytes_read
= read_and_xlate (io_buf
, sizeof io_buf
);
1884 if (bytes_read
== 0)
1886 if (fwrite (io_buf
, 1, bytes_read
, stdout
) != bytes_read
)
1887 error (EXIT_FAILURE
, errno
, _("write error"));
1892 if (close (STDIN_FILENO
) != 0)
1893 error (EXIT_FAILURE
, errno
, _("standard input"));
1895 exit (EXIT_SUCCESS
);