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