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  * @(#)str.c    8.2 (Berkeley) 4/28/95
  34  * $FreeBSD: src/usr.bin/tr/str.c,v 1.10.2.2 2002/07/29 12:59:33 tjr Exp $
  35  * $DragonFly: src/usr.bin/tr/str.c,v 1.3 2003/10/04 20:36:53 hmp Exp $
  36  */
  37
  38 #include <sys/cdefs.h>
  39 #include <sys/types.h>
  40
  41 #include <ctype.h>
  42 #include <err.h>
  43 #include <stddef.h>
  44 #include <stdio.h>
  45 #include <stdlib.h>
  46 #include <string.h>
  47
  48 #include "extern.h"
  49
  50 static int      backslash(STR *);
  51 static int      bracket(STR *);
  52 static int      c_class(const void *, const void *);
  53 static void     genclass(STR *);
  54 static void     genequiv(STR *);
  55 static int      genrange(STR *);
  56 static void     genseq(STR *);
  57
  58 int
  59 next(STR *s)
  60 {
  61         int ch;
  62
  63         switch (s->state) {
  64         case EOS:
  65                 return (0);
  66         case INFINITE:
  67                 return (1);
  68         case NORMAL:
  69                 switch (ch = (u_char)*s->str) {
  70                 case '\0':
  71                         s->state = EOS;
  72                         return (0);
  73                 case '\\':
  74                         s->lastch = backslash(s);
  75                         break;
  76                 case '[':
  77                         if (bracket(s))
  78                                 return (next(s));
  79                         /* FALLTHROUGH */
  80                 default:
  81                         ++s->str;
  82                         s->lastch = ch;
  83                         break;
  84                 }
  85
  86                 /* We can start a range at any time. */
  87                 if (s->str[0] == '-' && genrange(s))
  88                         return (next(s));
  89                 return (1);
  90         case RANGE:
  91                 if (s->cnt-- == 0) {
  92                         s->state = NORMAL;
  93                         return (next(s));
  94                 }
  95                 ++s->lastch;
  96                 return (1);
  97         case SEQUENCE:
  98                 if (s->cnt-- == 0) {
  99                         s->state = NORMAL;
 100                         return (next(s));
 101                 }
 102                 return (1);
 103         case SET:
 104                 if ((s->lastch = s->set[s->cnt++]) == OOBCH) {
 105                         s->state = NORMAL;
 106                         return (next(s));
 107                 }
 108                 return (1);
 109         default:
 110                 return (0);
 111         }
 112         /* NOTREACHED */
 113 }
 114
 115 static int
 116 bracket(STR *s)
 117 {
 118         char *p;
 119
 120         switch (s->str[1]) {
 121         case ':':                               /* "[:class:]" */
 122                 if ((p = strchr(s->str + 2, ']')) == NULL)
 123                         return (0);
 124                 if (*(p - 1) != ':' || p - s->str < 4)
 125                         goto repeat;
 126                 *(p - 1) = '\0';
 127                 s->str += 2;
 128                 genclass(s);
 129                 s->str = p + 1;
 130                 return (1);
 131         case '=':                               /* "[=equiv=]" */
 132                 if ((p = strchr(s->str + 2, ']')) == NULL)
 133                         return (0);
 134                 if (*(p - 1) != '=' || p - s->str < 4)
 135                         goto repeat;
 136                 s->str += 2;
 137                 genequiv(s);
 138                 return (1);
 139         default:                                /* "[\###*n]" or "[#*n]" */
 140         repeat:
 141                 if ((p = strpbrk(s->str + 2, "*]")) == NULL)
 142                         return (0);
 143                 if (p[0] != '*' || index(p, ']') == NULL)
 144                         return (0);
 145                 s->str += 1;
 146                 genseq(s);
 147                 return (1);
 148         }
 149         /* NOTREACHED */
 150 }
 151
 152 typedef struct {
 153         const char *name;
 154         int (*func)(int);
 155         int *set;
 156 } CLASS;
 157
 158 static CLASS classes[] = {
 159 #undef isalnum
 160         { "alnum",  isalnum,  NULL },
 161 #undef isalpha
 162         { "alpha",  isalpha,  NULL },
 163 #undef isblank
 164         { "blank",  isblank,  NULL },
 165 #undef iscntrl
 166         { "cntrl",  iscntrl,  NULL },
 167 #undef isdigit
 168         { "digit",  isdigit,  NULL },
 169 #undef isgraph
 170         { "graph",  isgraph,  NULL },
 171 #undef islower
 172         { "lower",  islower,  NULL },
 173 #undef isprint
 174         { "print",  isprint,  NULL },
 175 #undef ispunct
 176         { "punct",  ispunct,  NULL },
 177 #undef isspace
 178         { "space",  isspace,  NULL },
 179 #undef isupper
 180         { "upper",  isupper,  NULL },
 181 #undef isxdigit
 182         { "xdigit", isxdigit, NULL },
 183 };
 184
 185 static void
 186 genclass(STR *s)
 187 {
 188         int cnt, (*func)(int);
 189         CLASS *cp, tmp;
 190         int *p;
 191
 192         tmp.name = s->str;
 193         if ((cp = (CLASS *)bsearch(&tmp, classes, sizeof(classes) /
 194             sizeof(CLASS), sizeof(CLASS), c_class)) == NULL)
 195                 errx(1, "unknown class %s", s->str);
 196
 197         if ((cp->set = p = malloc((NCHARS + 1) * sizeof(int))) == NULL)
 198                 err(1, "malloc");
 199         bzero(p, (NCHARS + 1) * sizeof(int));
 200         for (cnt = 0, func = cp->func; cnt < NCHARS; ++cnt)
 201                 if ((func)(cnt))
 202                         *p++ = cnt;
 203         *p = OOBCH;
 204
 205         s->cnt = 0;
 206         s->state = SET;
 207         s->set = cp->set;
 208 }
 209
 210 static int
 211 c_class(const void *a, const void *b)
 212 {
 213         return (strcmp(((const CLASS *)a)->name, ((const CLASS *)b)->name));
 214 }
 215
 216 static void
 217 genequiv(STR *s)
 218 {
 219         int i, p, pri;
 220         char src[2], dst[3];
 221
 222         if (*s->str == '\\') {
 223                 s->equiv[0] = backslash(s);
 224                 if (*s->str != '=')
 225                         errx(1, "misplaced equivalence equals sign");
 226                 s->str += 2;
 227         } else {
 228                 s->equiv[0] = s->str[0];
 229                 if (s->str[1] != '=')
 230                         errx(1, "misplaced equivalence equals sign");
 231                 s->str += 3;
 232         }
 233
 234         /*
 235          * Calculate the set of all characters in the same equivalence class
 236          * as the specified character (they will have the same primary
 237          * collation weights).
 238          * XXX Knows too much about how strxfrm() is implemented. Assumes
 239          * it fills the string with primary collation weight bytes. Only one-
 240          * to-one mappings are supported.
 241          */
 242         src[0] = s->equiv[0];
 243         src[1] = '\0';
 244         if (strxfrm(dst, src, sizeof(dst)) == 1) {
 245                 pri = (unsigned char)*dst;
 246                 for (p = 1, i = 1; i < NCHARS; i++) {
 247                         *src = i;
 248                         if (strxfrm(dst, src, sizeof(dst)) == 1 && pri &&
 249                             pri == (unsigned char)*dst)
 250                                 s->equiv[p++] = i;
 251                 }
 252                 s->equiv[p] = OOBCH;
 253         }
 254
 255         s->cnt = 0;
 256         s->state = SET;
 257         s->set = s->equiv;
 258 }
 259
 260 static int
 261 genrange(STR *s)
 262 {
 263         int stopval;
 264         char *savestart;
 265
 266         savestart = s->str;
 267         stopval = *++s->str == '\\' ? backslash(s) : (u_char)*s->str++;
 268         if (stopval < (u_char)s->lastch) {
 269                 s->str = savestart;
 270                 return (0);
 271         }
 272         s->cnt = stopval - s->lastch + 1;
 273         s->state = RANGE;
 274         --s->lastch;
 275         return (1);
 276 }
 277
 278 static void
 279 genseq(STR *s)
 280 {
 281         char *ep;
 282
 283         if (s->which == STRING1)
 284                 errx(1, "sequences only valid in string2");
 285
 286         if (*s->str == '\\')
 287                 s->lastch = backslash(s);
 288         else
 289                 s->lastch = *s->str++;
 290         if (*s->str != '*')
 291                 errx(1, "misplaced sequence asterisk");
 292
 293         switch (*++s->str) {
 294         case '\\':
 295                 s->cnt = backslash(s);
 296                 break;
 297         case ']':
 298                 s->cnt = 0;
 299                 ++s->str;
 300                 break;
 301         default:
 302                 if (isdigit((u_char)*s->str)) {
 303                         s->cnt = strtol(s->str, &ep, 0);
 304                         if (*ep == ']') {
 305                                 s->str = ep + 1;
 306                                 break;
 307                         }
 308                 }
 309                 errx(1, "illegal sequence count");
 310                 /* NOTREACHED */
 311         }
 312
 313         s->state = s->cnt ? SEQUENCE : INFINITE;
 314 }
 315
 316 /*
 317  * Translate \??? into a character.  Up to 3 octal digits, if no digits either
 318  * an escape code or a literal character.
 319  */
 320 static int
 321 backslash(STR *s)
 322 {
 323         int ch, cnt, val;
 324
 325         for (cnt = val = 0;;) {
 326                 ch = (u_char)*++s->str;
 327                 if (!isascii(ch) || !isdigit(ch))
 328                         break;
 329                 val = val * 8 + ch - '0';
 330                 if (++cnt == 3) {
 331                         ++s->str;
 332                         break;
 333                 }
 334         }
 335         if (cnt)
 336                 return (val);
 337         if (ch != '\0')
 338                 ++s->str;
 339         switch (ch) {
 340                 case 'a':                       /* escape characters */
 341                         return ('\7');
 342                 case 'b':
 343                         return ('\b');
 344                 case 'f':
 345                         return ('\f');
 346                 case 'n':
 347                         return ('\n');
 348                 case 'r':
 349                         return ('\r');
 350                 case 't':
 351                         return ('\t');
 352                 case 'v':
 353                         return ('\13');
 354                 case '\0':                      /*  \" -> \ */
 355                         s->state = EOS;
 356                         return ('\\');
 357                 default:                        /* \x" -> x */
 358                         return (ch);
 359         }
 360 }