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

    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 				(void) fprintf(stderr, "Illegal seqeunce.\n");

    87 				exit(1);

    88 			}

    89 			is_octal = 0;

    90 			s->lastch = wch;

    91 			s->str += clen;

    92 			break;

    93 		}

    94 

    95 		/* We can start a range at any time. */

    96 		if (s->str[0] == '-' && genrange(s, is_octal))

    97 			return (next(s));

    98 		return (1);

    99 	case RANGE:

   100 		if (s->cnt-- == 0) {

   101 			s->state = NORMAL;

   102 			return (next(s));

   103 		}

   104 		++s->lastch;

   105 		return (1);

   106 	case SEQUENCE:

   107 		if (s->cnt-- == 0) {

   108 			s->state = NORMAL;

   109 			return (next(s));

   110 		}

   111 		return (1);

   112 	case CCLASS:

   113 	case CCLASS_UPPER:

   114 	case CCLASS_LOWER:

   115 		s->cnt++;

   116 		ch = nextwctype(s->lastch, s->cclass);

   117 		if (ch == -1) {

   118 			s->state = NORMAL;

   119 			return (next(s));

   120 		}

   121 		s->lastch = ch;

   122 		return (1);

   123 	case SET:

   124 		if ((ch = s->set[s->cnt++]) == OOBCH) {

   125 			s->state = NORMAL;

   126 			return (next(s));

   127 		}

   128 		s->lastch = ch;

   129 		return (1);

   130 	default:

   131 		return (0);

   132 	}

   133 	/* NOTREACHED */

   134 }

   135 

   136 static int

   137 bracket(s)

   138 	STR *s;

   139 {

   140 	char *p;

   141 

   142 	switch (s->str[1]) {

   143 	case ':':				/* "[:class:]" */

   144 		if ((p = strchr(s->str + 2, ']')) == NULL)

   145 			return (0);

   146 		if (*(p - 1) != ':' || p - s->str < 4)

   147 			goto repeat;

   148 		*(p - 1) = '\0';

   149 		s->str += 2;

   150 		genclass(s);

   151 		s->str = p + 1;

   152 		return (1);

   153 	case '=':				/* "[=equiv=]" */

   154 		if ((p = strchr(s->str + 2, ']')) == NULL)

   155 			return (0);

   156 		if (*(p - 1) != '=' || p - s->str < 4)

   157 			goto repeat;

   158 		s->str += 2;

   159 		genequiv(s);

   160 		return (1);

   161 	default:				/* "[\###*n]" or "[#*n]" */

   162 	repeat:

   163 		if ((p = strpbrk(s->str + 2, "*]")) == NULL)

   164 			return (0);

   165 		if (p[0] != '*' || index(p, ']') == NULL)

   166 			return (0);

   167 		s->str += 1;

   168 		genseq(s);

   169 		return (1);

   170 	}

   171 	/* NOTREACHED */

   172 }

   173 

   174 static void

   175 genclass(s)

   176 	STR *s;

   177 {

   178 

   179 	if ((s->cclass = wctype(s->str)) == 0)

   180 		errx(1, "unknown class %s", s->str);

   181 	s->cnt = 0;

   182 	s->lastch = -1;		/* incremented before check in next() */

   183 	if (strcmp(s->str, "upper") == 0)

   184 		s->state = CCLASS_UPPER;

   185 	else if (strcmp(s->str, "lower") == 0)

   186 		s->state = CCLASS_LOWER;

   187 	else

   188 		s->state = CCLASS;

   189 }

   190 

   191 static void

   192 genequiv(s)

   193 	STR *s;

   194 {

   195 	int i, p, pri;

   196 	char src[2], dst[3];

   197 	size_t clen;

   198 	wchar_t wc;

   199 

   200 	if (*s->str == '\\') {

   201 		s->equiv[0] = backslash(s, NULL);

   202 		if (*s->str != '=')

   203 			errx(1, "misplaced equivalence equals sign");

   204 		s->str += 2;

   205 	} else {

   206 		clen = mbrtowc(&wc, s->str, MB_LEN_MAX, NULL);

   207 		if (clen == (size_t)-1 || clen == (size_t)-2 || clen == 0) {

   208 			errno = EILSEQ;

   209 			err(1, NULL);

   210 		}

   211 		s->equiv[0] = wc;

   212 		if (s->str[clen] != '=')

   213 			errx(1, "misplaced equivalence equals sign");

   214 		s->str += clen + 2;

   215 	}

   216 

   217 	/*

   218 	 * Calculate the set of all characters in the same equivalence class

   219 	 * as the specified character (they will have the same primary

   220 	 * collation weights).

   221 	 * XXX Knows too much about how strxfrm() is implemented. Assumes

   222 	 * it fills the string with primary collation weight bytes. Only one-

   223 	 * to-one mappings are supported.

   224 	 * XXX Equivalence classes not supported in multibyte locales.

   225 	 */

   226 	src[0] = (char)s->equiv[0];

   227 	src[1] = '\0';

   228 	if (MB_CUR_MAX == 1 && strxfrm(dst, src, sizeof (dst)) == 1) {

   229 		pri = (unsigned char)*dst;

   230 		for (p = 1, i = 1; i < NCHARS_SB; i++) {

   231 			*src = i;

   232 			if (strxfrm(dst, src, sizeof (dst)) == 1 && pri &&

   233 			    pri == (unsigned char)*dst)

   234 				s->equiv[p++] = i;

   235 		}

   236 		s->equiv[p] = OOBCH;

   237 	}

   238 

   239 	s->cnt = 0;

   240 	s->state = SET;

   241 	s->set = s->equiv;

   242 }

   243 

   244 static int

   245 genrange(STR *s, int was_octal)

   246 {

   247 	int stopval, octal;

   248 	char *savestart;

   249 	int n, cnt, *p;

   250 	size_t clen;

   251 	wchar_t wc;

   252 

   253 	octal = 0;

   254 	savestart = s->str;

   255 	if (*++s->str == '\\')

   256 		stopval = backslash(s, &octal);

   257 	else {

   258 		clen = mbrtowc(&wc, s->str, MB_LEN_MAX, NULL);

   259 		if (clen == (size_t)-1 || clen == (size_t)-2) {

   260 			errno = EILSEQ;

   261 			err(1, NULL);

   262 		}

   263 		stopval = wc;

   264 		s->str += clen;

   265 	}

   266 	/*

   267 	 * XXX Characters are not ordered according to collating sequence in

   268 	 * multibyte locales.

   269 	 */

   270 	if (octal || was_octal || MB_CUR_MAX > 1) {

   271 		if (stopval < s->lastch) {

   272 			s->str = savestart;

   273 			return (0);

   274 		}

   275 		s->cnt = stopval - s->lastch + 1;

   276 		s->state = RANGE;

   277 		--s->lastch;

   278 		return (1);

   279 	}

   280 	if (charcoll((const void *)&stopval, (const void *)&(s->lastch)) < 0) {

   281 		s->str = savestart;

   282 		return (0);

   283 	}

   284 	p = malloc((NCHARS_SB + 1) * sizeof (int));

   285 	if ((s = (void *)p) == NULL)

   286 		err(1, "genrange() malloc");

   287 	for (cnt = 0; cnt < NCHARS_SB; cnt++)

   288 		if (charcoll((const void *)&cnt, (const void *)&(s->lastch)) >=

   289 		    0 &&

   290 		    charcoll((const void *)&cnt, (const void *)&stopval) <= 0)

   291 			*p++ = cnt;

   292 	*p = OOBCH;

   293 	n = (int *)p - (int *)s->set;

   294 

   295 	s->cnt = 0;

   296 	s->state = SET;

   297 	if (n > 1)

   298 		qsort(s->set, n, sizeof (*(s->set)), charcoll);

   299 	return (1);

   300 }

   301 

   302 static void

   303 genseq(s)

   304 	STR *s;

   305 {

   306 	char *ep;

   307 	wchar_t wc;

   308 	size_t clen;

   309 

   310 	if (s->which == STRING1)

   311 		errx(1, "sequences only valid in string2");

   312 

   313 	if (*s->str == '\\')

   314 		s->lastch = backslash(s, NULL);

   315 	else {

   316 		clen = mbrtowc(&wc, s->str, MB_LEN_MAX, NULL);

   317 		if (clen == (size_t)-1 || clen == (size_t)-2) {

   318 			errno = EILSEQ;

   319 			err(1, NULL);

   320 		}

   321 		s->lastch = wc;

   322 		s->str += clen;

   323 	}

   324 	if (*s->str != '*')

   325 		errx(1, "misplaced sequence asterisk");

   326 

   327 	switch (*++s->str) {

   328 	case '\\':

   329 		s->cnt = backslash(s, NULL);

   330 		break;

   331 	case ']':

   332 		s->cnt = 0;

   333 		++s->str;

   334 		break;

   335 	default:

   336 		if (isdigit((uchar_t)*s->str)) {

   337 			s->cnt = strtol(s->str, &ep, 0);

   338 			if (*ep == ']') {

   339 				s->str = ep + 1;

   340 				break;

   341 			}

   342 		}

   343 		errx(1, "illegal sequence count");

   344 		/* NOTREACHED */

   345 	}

   346 

   347 	s->state = s->cnt ? SEQUENCE : INFINITE;

   348 }

   349 

   350 /*

   351  * Translate \??? into a character.  Up to 3 octal digits, if no digits either

   352  * an escape code or a literal character.

   353  */

   354 static int

   355 backslash(STR *s, int *is_octal)

   356 {

   357 	int ch, cnt, val;

   358 

   359 	if (is_octal != NULL)

   360 		*is_octal = 0;

   361 	for (cnt = val = 0; ; ) {

   362 		ch = (uchar_t)*++s->str;

   363 		if (!isdigit(ch) || ch > '7')

   364 			break;

   365 		val = val * 8 + ch - '0';

   366 		if (++cnt == 3) {

   367 			++s->str;

   368 			break;

   369 		}

   370 	}

   371 	if (cnt) {

   372 		if (is_octal != NULL)

   373 			*is_octal = 1;

   374 		return (val);

   375 	}

   376 	if (ch != '\0')

   377 		++s->str;

   378 	switch (ch) {

   379 	case 'a':			/* escape characters */

   380 		return ('\7');

   381 	case 'b':

   382 		return ('\b');

   383 	case 'f':

   384 		return ('\f');

   385 	case 'n':

   386 		return ('\n');

   387 	case 'r':

   388 		return ('\r');

   389 	case 't':

   390 		return ('\t');

   391 	case 'v':

   392 		return ('\13');

   393 	case '\0':			/*  \" -> \ */

   394 		s->state = EOS;

   395 		return ('\\');

   396 	default:			/* \x" -> x */

   397 		return (ch);

   398 	}

   399 }