str.c revision 166134
1/*- 2 * Copyright (c) 1991, 1993 3 * The Regents of the University of California. All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. All advertising materials mentioning features or use of this software 14 * must display the following acknowledgement: 15 * This product includes software developed by the University of 16 * California, Berkeley and its contributors. 17 * 4. Neither the name of the University nor the names of its contributors 18 * may be used to endorse or promote products derived from this software 19 * without specific prior written permission. 20 * 21 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 24 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 31 * SUCH DAMAGE. 32 */ 33 34#include <sys/cdefs.h> 35 36__FBSDID("$FreeBSD: head/usr.bin/tr/str.c 166134 2007-01-20 08:24:02Z maxim $"); 37 38#ifndef lint 39static const char sccsid[] = "@(#)str.c 8.2 (Berkeley) 4/28/95"; 40#endif 41 42#include <sys/types.h> 43 44#include <ctype.h> 45#include <err.h> 46#include <errno.h> 47#include <stddef.h> 48#include <stdio.h> 49#include <stdlib.h> 50#include <string.h> 51#include <wchar.h> 52#include <wctype.h> 53 54#include "extern.h" 55 56static int backslash(STR *, int *); 57static int bracket(STR *); 58static void genclass(STR *); 59static void genequiv(STR *); 60static int genrange(STR *, int); 61static void genseq(STR *); 62 63wint_t 64next(s) 65 STR *s; 66{ 67 int is_octal; 68 wint_t ch; 69 wchar_t wch; 70 size_t clen; 71 72 switch (s->state) { 73 case EOS: 74 return (0); 75 case INFINITE: 76 return (1); 77 case NORMAL: 78 switch (*s->str) { 79 case '\0': 80 s->state = EOS; 81 return (0); 82 case '\\': 83 s->lastch = backslash(s, &is_octal); 84 break; 85 case '[': 86 if (bracket(s)) 87 return (next(s)); 88 /* FALLTHROUGH */ 89 default: 90 clen = mbrtowc(&wch, s->str, MB_LEN_MAX, NULL); 91 if (clen == (size_t)-1 || clen == (size_t)-2 || 92 clen == 0) 93 errc(1, EILSEQ, NULL); 94 is_octal = 0; 95 s->lastch = wch; 96 s->str += clen; 97 break; 98 } 99 100 /* We can start a range at any time. */ 101 if (s->str[0] == '-' && genrange(s, is_octal)) 102 return (next(s)); 103 return (1); 104 case RANGE: 105 if (s->cnt-- == 0) { 106 s->state = NORMAL; 107 return (next(s)); 108 } 109 ++s->lastch; 110 return (1); 111 case SEQUENCE: 112 if (s->cnt-- == 0) { 113 s->state = NORMAL; 114 return (next(s)); 115 } 116 return (1); 117 case CCLASS: 118 case CCLASS_UPPER: 119 case CCLASS_LOWER: 120 s->cnt++; 121 ch = nextwctype(s->lastch, s->cclass); 122 if (ch == -1) { 123 s->state = NORMAL; 124 return (next(s)); 125 } 126 s->lastch = ch; 127 return (1); 128 case SET: 129 if ((ch = s->set[s->cnt++]) == OOBCH) { 130 s->state = NORMAL; 131 return (next(s)); 132 } 133 s->lastch = ch; 134 return (1); 135 default: 136 return (0); 137 } 138 /* NOTREACHED */ 139} 140 141static int 142bracket(s) 143 STR *s; 144{ 145 char *p; 146 147 switch (s->str[1]) { 148 case ':': /* "[:class:]" */ 149 if ((p = strchr(s->str + 2, ']')) == NULL) 150 return (0); 151 if (*(p - 1) != ':' || p - s->str < 4) 152 goto repeat; 153 *(p - 1) = '\0'; 154 s->str += 2; 155 genclass(s); 156 s->str = p + 1; 157 return (1); 158 case '=': /* "[=equiv=]" */ 159 if ((p = strchr(s->str + 2, ']')) == NULL) 160 return (0); 161 if (*(p - 1) != '=' || p - s->str < 4) 162 goto repeat; 163 s->str += 2; 164 genequiv(s); 165 return (1); 166 default: /* "[\###*n]" or "[#*n]" */ 167 repeat: 168 if ((p = strpbrk(s->str + 2, "*]")) == NULL) 169 return (0); 170 if (p[0] != '*' || index(p, ']') == NULL) 171 return (0); 172 s->str += 1; 173 genseq(s); 174 return (1); 175 } 176 /* NOTREACHED */ 177} 178 179static void 180genclass(s) 181 STR *s; 182{ 183 184 if ((s->cclass = wctype(s->str)) == 0) 185 errx(1, "unknown class %s", s->str); 186 s->cnt = 0; 187 s->lastch = -1; /* incremented before check in next() */ 188 if (strcmp(s->str, "upper") == 0) 189 s->state = CCLASS_UPPER; 190 else if (strcmp(s->str, "lower") == 0) 191 s->state = CCLASS_LOWER; 192 else 193 s->state = CCLASS; 194} 195 196static void 197genequiv(s) 198 STR *s; 199{ 200 int i, p, pri; 201 char src[2], dst[3]; 202 size_t clen; 203 wchar_t wc; 204 205 if (*s->str == '\\') { 206 s->equiv[0] = backslash(s, NULL); 207 if (*s->str != '=') 208 errx(1, "misplaced equivalence equals sign"); 209 s->str += 2; 210 } else { 211 clen = mbrtowc(&wc, s->str, MB_LEN_MAX, NULL); 212 if (clen == (size_t)-1 || clen == (size_t)-2 || clen == 0) 213 errc(1, EILSEQ, NULL); 214 s->equiv[0] = wc; 215 if (s->str[clen] != '=') 216 errx(1, "misplaced equivalence equals sign"); 217 s->str += clen + 2; 218 } 219 220 /* 221 * Calculate the set of all characters in the same equivalence class 222 * as the specified character (they will have the same primary 223 * collation weights). 224 * XXX Knows too much about how strxfrm() is implemented. Assumes 225 * it fills the string with primary collation weight bytes. Only one- 226 * to-one mappings are supported. 227 * XXX Equivalence classes not supported in multibyte locales. 228 */ 229 src[0] = (char)s->equiv[0]; 230 src[1] = '\0'; 231 if (MB_CUR_MAX == 1 && strxfrm(dst, src, sizeof(dst)) == 1) { 232 pri = (unsigned char)*dst; 233 for (p = 1, i = 1; i < NCHARS_SB; i++) { 234 *src = i; 235 if (strxfrm(dst, src, sizeof(dst)) == 1 && pri && 236 pri == (unsigned char)*dst) 237 s->equiv[p++] = i; 238 } 239 s->equiv[p] = OOBCH; 240 } 241 242 s->cnt = 0; 243 s->state = SET; 244 s->set = s->equiv; 245} 246 247static int 248genrange(STR *s, int was_octal) 249{ 250 int stopval, octal; 251 char *savestart; 252 int n, cnt, *p; 253 size_t clen; 254 wchar_t wc; 255 256 octal = 0; 257 savestart = s->str; 258 if (*++s->str == '\\') 259 stopval = backslash(s, &octal); 260 else { 261 clen = mbrtowc(&wc, s->str, MB_LEN_MAX, NULL); 262 if (clen == (size_t)-1 || clen == (size_t)-2) 263 errc(1, EILSEQ, NULL); 264 stopval = wc; 265 s->str += clen; 266 } 267 /* 268 * XXX Characters are not ordered according to collating sequence in 269 * multibyte locales. 270 */ 271 if (octal || was_octal || MB_CUR_MAX > 1) { 272 if (stopval < s->lastch) { 273 s->str = savestart; 274 return (0); 275 } 276 s->cnt = stopval - s->lastch + 1; 277 s->state = RANGE; 278 --s->lastch; 279 return (1); 280 } 281 if (charcoll((const void *)&stopval, (const void *)&(s->lastch)) < 0) { 282 s->str = savestart; 283 return (0); 284 } 285 if ((s->set = p = malloc((NCHARS_SB + 1) * sizeof(int))) == NULL) 286 err(1, "genrange() malloc"); 287 for (cnt = 0; cnt < NCHARS_SB; cnt++) 288 if (charcoll((const void *)&cnt, (const void *)&(s->lastch)) >= 0 && 289 charcoll((const void *)&cnt, (const void *)&stopval) <= 0) 290 *p++ = cnt; 291 *p = OOBCH; 292 n = p - s->set; 293 294 s->cnt = 0; 295 s->state = SET; 296 if (n > 1) 297 mergesort(s->set, n, sizeof(*(s->set)), charcoll); 298 return (1); 299} 300 301static void 302genseq(s) 303 STR *s; 304{ 305 char *ep; 306 wchar_t wc; 307 size_t clen; 308 309 if (s->which == STRING1) 310 errx(1, "sequences only valid in string2"); 311 312 if (*s->str == '\\') 313 s->lastch = backslash(s, NULL); 314 else { 315 clen = mbrtowc(&wc, s->str, MB_LEN_MAX, NULL); 316 if (clen == (size_t)-1 || clen == (size_t)-2) 317 errc(1, EILSEQ, NULL); 318 s->lastch = wc; 319 s->str += clen; 320 } 321 if (*s->str != '*') 322 errx(1, "misplaced sequence asterisk"); 323 324 switch (*++s->str) { 325 case '\\': 326 s->cnt = backslash(s, NULL); 327 break; 328 case ']': 329 s->cnt = 0; 330 ++s->str; 331 break; 332 default: 333 if (isdigit((u_char)*s->str)) { 334 s->cnt = strtol(s->str, &ep, 0); 335 if (*ep == ']') { 336 s->str = ep + 1; 337 break; 338 } 339 } 340 errx(1, "illegal sequence count"); 341 /* NOTREACHED */ 342 } 343 344 s->state = s->cnt ? SEQUENCE : INFINITE; 345} 346 347/* 348 * Translate \??? into a character. Up to 3 octal digits, if no digits either 349 * an escape code or a literal character. 350 */ 351static int 352backslash(STR *s, int *is_octal) 353{ 354 int ch, cnt, val; 355 356 if (is_octal != NULL) 357 *is_octal = 0; 358 for (cnt = val = 0;;) { 359 ch = (u_char)*++s->str; 360 if (!isdigit(ch) || ch > '7') 361 break; 362 val = val * 8 + ch - '0'; 363 if (++cnt == 3) { 364 ++s->str; 365 break; 366 } 367 } 368 if (cnt) { 369 if (is_octal != NULL) 370 *is_octal = 1; 371 return (val); 372 } 373 if (ch != '\0') 374 ++s->str; 375 switch (ch) { 376 case 'a': /* escape characters */ 377 return ('\7'); 378 case 'b': 379 return ('\b'); 380 case 'f': 381 return ('\f'); 382 case 'n': 383 return ('\n'); 384 case 'r': 385 return ('\r'); 386 case 't': 387 return ('\t'); 388 case 'v': 389 return ('\13'); 390 case '\0': /* \" -> \ */ 391 s->state = EOS; 392 return ('\\'); 393 default: /* \x" -> x */ 394 return (ch); 395 } 396} 397