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/types.h>
35
36 #include <ctype.h>
37 #include <err.h>
38 #include <errno.h>
39 #include <stddef.h>
40 #include <stdio.h>
41 #include <stdlib.h>
42 #include <string.h>
43 #include <strings.h>
44 #include <wchar.h>
45 #include <wctype.h>
46
47 #include "extern.h"
48
49 static int backslash(STR *, int *);
50 static int bracket(STR *);
51 static void genclass(STR *);
52 static void genequiv(STR *);
53 static int genrange(STR *, int);
54 static void genseq(STR *);
55
56 wint_t
next(s)57 next(s)
58 STR *s;
59 {
60 int is_octal;
61 wint_t ch;
62 wchar_t wch;
63 size_t clen;
64
65 switch (s->state) {
66 case EOS:
67 return (0);
68 case INFINITE:
69 return (1);
70 case NORMAL:
71 switch (*s->str) {
72 case '\0':
73 s->state = EOS;
74 return (0);
75 case '\\':
76 s->lastch = backslash(s, &is_octal);
77 break;
78 case '[':
79 if (bracket(s))
80 return (next(s));
81 /* FALLTHROUGH */
82 default:
83 clen = mbrtowc(&wch, s->str, MB_LEN_MAX, NULL);
84 if (clen == (size_t)-1 || clen == (size_t)-2 ||
85 clen == 0)
86 errx(1, "illegal sequence");
87 is_octal = 0;
88 s->lastch = wch;
89 s->str += clen;
90 break;
91 }
92
93 /* We can start a range at any time. */
94 if (s->str[0] == '-' && genrange(s, is_octal))
95 return (next(s));
96 return (1);
97 case RANGE:
98 if (s->cnt-- == 0) {
99 s->state = NORMAL;
100 return (next(s));
101 }
102 ++s->lastch;
103 return (1);
104 case SEQUENCE:
105 if (s->cnt-- == 0) {
106 s->state = NORMAL;
107 return (next(s));
108 }
109 return (1);
110 case CCLASS:
111 case CCLASS_UPPER:
112 case CCLASS_LOWER:
113 s->cnt++;
114 ch = nextwctype(s->lastch, s->cclass);
115 if (ch == -1) {
116 s->state = NORMAL;
117 return (next(s));
118 }
119 s->lastch = ch;
120 return (1);
121 case SET:
122 if ((ch = s->set[s->cnt++]) == OOBCH) {
123 s->state = NORMAL;
124 return (next(s));
125 }
126 s->lastch = ch;
127 return (1);
128 default:
129 return (0);
130 }
131 /* NOTREACHED */
132 }
133
134 static int
bracket(s)135 bracket(s)
136 STR *s;
137 {
138 char *p;
139
140 switch (s->str[1]) {
141 case ':': /* "[:class:]" */
142 if ((p = strchr(s->str + 2, ']')) == NULL)
143 return (0);
144 if (*(p - 1) != ':' || p - s->str < 4)
145 goto repeat;
146 *(p - 1) = '\0';
147 s->str += 2;
148 genclass(s);
149 s->str = p + 1;
150 return (1);
151 case '=': /* "[=equiv=]" */
152 if ((p = strchr(s->str + 3, ']')) == NULL)
153 return (0);
154 if (*(p - 1) != '=' || p - s->str < 4)
155 goto repeat;
156 s->str += 2;
157 genequiv(s);
158 return (1);
159 default: /* "[\###*n]" or "[#*n]" */
160 repeat:
161 if ((p = strpbrk(s->str + 2, "*]")) == NULL)
162 return (0);
163 if (p[0] != '*' || index(p, ']') == NULL)
164 return (0);
165 s->str += 1;
166 genseq(s);
167 return (1);
168 }
169 /* NOTREACHED */
170 }
171
172 static void
genclass(s)173 genclass(s)
174 STR *s;
175 {
176
177 if ((s->cclass = wctype(s->str)) == 0)
178 errx(1, "unknown class %s", s->str);
179 s->cnt = 0;
180 s->lastch = -1; /* incremented before check in next() */
181 if (strcmp(s->str, "upper") == 0)
182 s->state = CCLASS_UPPER;
183 else if (strcmp(s->str, "lower") == 0)
184 s->state = CCLASS_LOWER;
185 else
186 s->state = CCLASS;
187 }
188
189 static void
genequiv(s)190 genequiv(s)
191 STR *s;
192 {
193 int i, p, pri;
194 char src[2], dst[3];
195 size_t clen;
196 wchar_t wc;
197
198 if (*s->str == '\\') {
199 s->equiv[0] = backslash(s, NULL);
200 if (*s->str != '=')
201 errx(1, "misplaced equivalence equals sign");
202 s->str += 2;
203 } else {
204 clen = mbrtowc(&wc, s->str, MB_LEN_MAX, NULL);
205 if (clen == (size_t)-1 || clen == (size_t)-2 || clen == 0) {
206 errno = EILSEQ;
207 err(1, NULL);
208 }
209 s->equiv[0] = wc;
210 if (s->str[clen] != '=')
211 errx(1, "misplaced equivalence equals sign");
212 s->str += clen + 2;
213 }
214
215 /*
216 * Calculate the set of all characters in the same equivalence class
217 * as the specified character (they will have the same primary
218 * collation weights).
219 * XXX Knows too much about how strxfrm() is implemented. Assumes
220 * it fills the string with primary collation weight bytes. Only one-
221 * to-one mappings are supported.
222 * XXX Equivalence classes not supported in multibyte locales.
223 */
224 src[0] = (char)s->equiv[0];
225 src[1] = '\0';
226 if (MB_CUR_MAX == 1 && strxfrm(dst, src, sizeof (dst)) == 1) {
227 pri = (unsigned char)*dst;
228 for (p = 1, i = 1; i < NCHARS_SB; i++) {
229 *src = i;
230 if (strxfrm(dst, src, sizeof (dst)) == 1 && pri &&
231 pri == (unsigned char)*dst)
232 s->equiv[p++] = i;
233 }
234 s->equiv[p] = OOBCH;
235 }
236
237 s->cnt = 0;
238 s->state = SET;
239 s->set = s->equiv;
240 }
241
242 static int
genrange(STR * s,int was_octal)243 genrange(STR *s, int was_octal)
244 {
245 int stopval, octal;
246 char *savestart;
247 int n, cnt, *p;
248 size_t clen;
249 wchar_t wc;
250
251 octal = 0;
252 savestart = s->str;
253 if (*++s->str == '\\')
254 stopval = backslash(s, &octal);
255 else {
256 clen = mbrtowc(&wc, s->str, MB_LEN_MAX, NULL);
257 if (clen == (size_t)-1 || clen == (size_t)-2) {
258 errno = EILSEQ;
259 err(1, NULL);
260 }
261 stopval = wc;
262 s->str += clen;
263 }
264 /*
265 * XXX Characters are not ordered according to collating sequence in
266 * multibyte locales.
267 */
268 if (octal || was_octal || MB_CUR_MAX > 1) {
269 if (stopval < s->lastch) {
270 s->str = savestart;
271 return (0);
272 }
273 s->cnt = stopval - s->lastch + 1;
274 s->state = RANGE;
275 --s->lastch;
276 return (1);
277 }
278 if (charcoll((const void *)&stopval, (const void *)&(s->lastch)) < 0) {
279 s->str = savestart;
280 return (0);
281 }
282 p = malloc((NCHARS_SB + 1) * sizeof (int));
283 if ((s->set = (void *)p) == NULL)
284 err(1, "genrange() malloc");
285 for (cnt = 0; cnt < NCHARS_SB; cnt++)
286 if (charcoll((const void *)&cnt, (const void *)&(s->lastch)) >=
287 0 &&
288 charcoll((const void *)&cnt, (const void *)&stopval) <= 0)
289 *p++ = cnt;
290 *p = OOBCH;
291 n = (int *)p - (int *)s->set;
292
293 s->cnt = 0;
294 s->state = SET;
295 if (n > 1)
296 qsort(s->set, n, sizeof (*(s->set)), charcoll);
297 return (1);
298 }
299
300 static void
genseq(s)301 genseq(s)
302 STR *s;
303 {
304 char *ep;
305 wchar_t wc;
306 size_t clen;
307
308 if (s->which == STRING1)
309 errx(1, "sequences only valid in string2");
310
311 if (*s->str == '\\')
312 s->lastch = backslash(s, NULL);
313 else {
314 clen = mbrtowc(&wc, s->str, MB_LEN_MAX, NULL);
315 if (clen == (size_t)-1 || clen == (size_t)-2) {
316 errno = EILSEQ;
317 err(1, NULL);
318 }
319 s->lastch = wc;
320 s->str += clen;
321 }
322 if (*s->str != '*')
323 errx(1, "misplaced sequence asterisk");
324
325 switch (*++s->str) {
326 case '\\':
327 s->cnt = backslash(s, NULL);
328 break;
329 case ']':
330 s->cnt = 0;
331 ++s->str;
332 break;
333 default:
334 if (isdigit((uchar_t)*s->str)) {
335 s->cnt = strtol(s->str, &ep, 0);
336 if (*ep == ']') {
337 s->str = ep + 1;
338 break;
339 }
340 }
341 errx(1, "illegal sequence count");
342 /* NOTREACHED */
343 }
344
345 s->state = s->cnt ? SEQUENCE : INFINITE;
346 }
347
348 /*
349 * Translate \??? into a character. Up to 3 octal digits, if no digits either
350 * an escape code or a literal character.
351 */
352 static int
backslash(STR * s,int * is_octal)353 backslash(STR *s, int *is_octal)
354 {
355 int ch, cnt, val;
356
357 if (is_octal != NULL)
358 *is_octal = 0;
359 for (cnt = val = 0; ; ) {
360 ch = (uchar_t)*++s->str;
361 if (!isdigit(ch) || ch > '7')
362 break;
363 val = val * 8 + ch - '0';
364 if (++cnt == 3) {
365 ++s->str;
366 break;
367 }
368 }
369 if (cnt) {
370 if (is_octal != NULL)
371 *is_octal = 1;
372 return (val);
373 }
374 if (ch != '\0')
375 ++s->str;
376 switch (ch) {
377 case 'a': /* escape characters */
378 return ('\7');
379 case 'b':
380 return ('\b');
381 case 'f':
382 return ('\f');
383 case 'n':
384 return ('\n');
385 case 'r':
386 return ('\r');
387 case 't':
388 return ('\t');
389 case 'v':
390 return ('\13');
391 case '\0': /* \" -> \ */
392 s->state = EOS;
393 return ('\\');
394 default: /* \x" -> x */
395 return (ch);
396 }
397 }
398