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