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