usr.bin/tr/str.c

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