usr.bin/tr/str.c

   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$");
  37
  38 #ifndef lint
  39 static 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
  56 static int      backslash(STR *, int *);
  57 static int      bracket(STR *);
  58 static void     genclass(STR *);
  59 static void     genequiv(STR *);
  60 static int      genrange(STR *, int);
  61 static void     genseq(STR *);
  62
  63 wint_t
  64 next(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
 141 static int
 142 bracket(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
 179 static void
 180 genclass(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
 196 static void
 197 genequiv(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
 247 static int
 248 genrange(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
 301 static void
 302 genseq(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  */
 351 static int
 352 backslash(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 }