games/quiz/rxp.c

   1 /*-
   2  * Copyright (c) 1991, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Jim R. Oldroyd at The Instruction Set and Keith Gabryelski at
   7  * Commodore Business Machines.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  * 3. 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  * @(#)rxp.c    8.1 (Berkeley) 5/31/93
  34  * $FreeBSD: src/games/quiz/rxp.c,v 1.5 1999/12/12 02:29:54 billf Exp $
  35  * $DragonFly: src/games/quiz/rxp.c,v 1.4 2005/04/25 16:10:24 liamfoy Exp $
  36  */
  37
  38 /*
  39  * regular expression parser
  40  *
  41  * external functions and return values are:
  42  * rxp_compile(s)
  43  *      TRUE    success
  44  *      FALSE   parse failure; error message will be in char rxperr[]
  45  * metas are:
  46  *      {...}   optional pattern, equialent to [...|]
  47  *      |       alternate pattern
  48  *      [...]   pattern delimiters
  49  *
  50  * rxp_match(s)
  51  *      TRUE    string s matches compiled pattern
  52  *      FALSE   match failure or regexp error
  53  *
  54  * rxp_expand()
  55  *      char *  reverse-engineered regular expression string
  56  *      NULL    regexp error
  57  */
  58
  59 #include <stdio.h>
  60 #include <ctype.h>
  61 #include "quiz.h"
  62                                         /* regexp tokens,       arg */
  63 #define LIT     (-1)                    /* literal character,   char */
  64 #define SOT     (-2)                    /* start text anchor,   - */
  65 #define EOT     (-3)                    /* end text anchor,     - */
  66 #define GRP_S   (-4)                    /* start alternate grp, ptr_to_end */
  67 #define GRP_E   (-5)                    /* end group,           - */
  68 #define ALT_S   (-6)                    /* alternate starts,    ptr_to_next */
  69 #define ALT_E   (-7)                    /* alternate ends,      - */
  70 #define END     (-8)                    /* end of regexp,       - */
  71
  72 typedef short Rxp_t;                    /* type for regexp tokens */
  73
  74 static Rxp_t rxpbuf[RXP_LINE_SZ];       /* compiled regular expression buffer */
  75 char rxperr[128];                       /* parser error message */
  76
  77 static int       rxp__compile (char *, int);
  78 static char     *rxp__expand (int);
  79 static int       rxp__match (char *, int, Rxp_t *, Rxp_t *, char *);
  80
  81 int
  82 rxp_compile(char *s)
  83 {
  84         return (rxp__compile(s, TRUE));
  85 }
  86
  87 static int
  88 rxp__compile(char *s, int first)
  89 {
  90         static Rxp_t *rp;
  91         static char *sp;
  92         Rxp_t *grp_ptr;
  93         Rxp_t *alt_ptr;
  94         int esc, err;
  95
  96         esc = 0;
  97         if (first) {
  98                 rp = rxpbuf;
  99                 sp = s;
 100                 *rp++ = SOT;    /* auto-anchor: pat is really ^pat$ */
 101                 *rp++ = GRP_S;  /* auto-group: ^pat$ is really ^[pat]$ */
 102                 *rp++ = 0;
 103         }
 104         *rp++ = ALT_S;
 105         alt_ptr = rp;
 106         *rp++ = 0;
 107         for (; *sp; ++sp) {
 108                 if (rp - rxpbuf >= RXP_LINE_SZ - 4) {
 109                         (void)snprintf(rxperr, sizeof(rxperr),
 110                             "regular expression too long %s", s);
 111                         return (FALSE);
 112                 }
 113                 if (*sp == ':' && !esc)
 114                         break;
 115                 if (esc) {
 116                         *rp++ = LIT;
 117                         *rp++ = *sp;
 118                         esc = 0;
 119                 }
 120                 else switch (*sp) {
 121                 case '\\':
 122                         esc = 1;
 123                         break;
 124                 case '{':
 125                 case '[':
 126                         *rp++ = GRP_S;
 127                         grp_ptr = rp;
 128                         *rp++ = 0;
 129                         sp++;
 130                         if ((err = rxp__compile(s, FALSE)) != TRUE)
 131                                 return (err);
 132                         *rp++ = GRP_E;
 133                         *grp_ptr = rp - rxpbuf;
 134                         break;
 135                 case '}':
 136                 case ']':
 137                 case '|':
 138                         *rp++ = ALT_E;
 139                         *alt_ptr = rp - rxpbuf;
 140                         if (*sp != ']') {
 141                                 *rp++ = ALT_S;
 142                                 alt_ptr = rp;
 143                                 *rp++ = 0;
 144                         }
 145                         if (*sp != '|') {
 146                                 if (*sp != ']') {
 147                                         *rp++ = ALT_E;
 148                                         *alt_ptr = rp - rxpbuf;
 149                                 }
 150                                 if (first) {
 151                                         (void)snprintf(rxperr, sizeof(rxperr),
 152                                             "unmatched alternator in regexp %s",
 153                                              s);
 154                                         return (FALSE);
 155                                 }
 156                                 return (TRUE);
 157                         }
 158                         break;
 159                 default:
 160                         *rp++ = LIT;
 161                         *rp++ = *sp;
 162                         esc = 0;
 163                         break;
 164                 }
 165         }
 166         if (!first) {
 167                 (void)snprintf(rxperr, sizeof(rxperr),
 168                     "unmatched alternator in regexp %s", s);
 169                 return (FALSE);
 170         }
 171         *rp++ = ALT_E;
 172         *alt_ptr = rp - rxpbuf;
 173         *rp++ = GRP_E;
 174         *(rxpbuf + 2) = rp - rxpbuf;
 175         *rp++ = EOT;
 176         *rp = END;
 177         return (TRUE);
 178 }
 179
 180 /*
 181  * match string against compiled regular expression
 182  */
 183 int
 184 rxp_match(char *s)
 185 {
 186         return (rxp__match(s, TRUE, NULL, NULL, NULL));
 187 }
 188
 189 /*
 190  * jump to j_succ on successful alt match
 191  * jump to j_fail on failed match
 192  * reset sp to sp_fail on failed match
 193  */
 194 static int
 195 rxp__match(char *s, int first, Rxp_t *j_succ, Rxp_t *j_fail, char *sp_fail)
 196 {
 197         static Rxp_t *rp;
 198         static char *sp;
 199         int ch;
 200         Rxp_t *grp_end;
 201         int err;
 202
 203         grp_end = NULL;
 204         if (first) {
 205                 rp = rxpbuf;
 206                 sp = s;
 207         }
 208         while (rp < rxpbuf + RXP_LINE_SZ && *rp != END)
 209                 switch(*rp) {
 210                 case LIT:
 211                         rp++;
 212                         ch = isascii(*rp) && isupper(*rp) ? tolower(*rp) : *rp;
 213                         if (ch != *sp++) {
 214                                 rp = j_fail;
 215                                 sp = sp_fail;
 216                                 return (TRUE);
 217                         }
 218                         rp++;
 219                         break;
 220                 case SOT:
 221                         if (sp != s)
 222                                 return (FALSE);
 223                         rp++;
 224                         break;
 225                 case EOT:
 226                         if (*sp != 0)
 227                                 return (FALSE);
 228                         rp++;
 229                         break;
 230                 case GRP_S:
 231                         rp++;
 232                         grp_end = rxpbuf + *rp++;
 233                         break;
 234                 case ALT_S:
 235                         rp++;
 236                         if ((err = rxp__match(sp,
 237                             FALSE, grp_end, rxpbuf + *rp++, sp)) != TRUE)
 238                                 return (err);
 239                         break;
 240                 case ALT_E:
 241                         rp = j_succ;
 242                         return (TRUE);
 243                 case GRP_E:
 244                 default:
 245                         return (FALSE);
 246                 }
 247         return (*rp != END ? FALSE : TRUE);
 248 }
 249
 250 /*
 251  * Reverse engineer the regular expression, by picking first of all alternates.
 252  */
 253 char *
 254 rxp_expand(void)
 255 {
 256         return (rxp__expand(TRUE));
 257 }
 258
 259 static char *
 260 rxp__expand(int first)
 261 {
 262         static char buf[RXP_LINE_SZ/2];
 263         static Rxp_t *rp;
 264         static char *bp;
 265         Rxp_t *grp_ptr;
 266         char *err;
 267
 268         if (first) {
 269                 rp = rxpbuf;
 270                 bp = buf;
 271         }
 272         while (rp < rxpbuf + RXP_LINE_SZ && *rp != END)
 273                 switch(*rp) {
 274                 case LIT:
 275                         rp++;
 276                         *bp++ = *rp++;
 277                         break;
 278                 case GRP_S:
 279                         rp++;
 280                         grp_ptr = rxpbuf + *rp;
 281                         rp++;
 282                         if ((err = rxp__expand(FALSE)) == NULL)
 283                                 return (err);
 284                         rp = grp_ptr;
 285                         break;
 286                 case ALT_E:
 287                         return (buf);
 288                 case ALT_S:
 289                         rp++;
 290                         /* FALLTHROUGH */
 291                 case SOT:
 292                 case EOT:
 293                 case GRP_E:
 294                         rp++;
 295                         break;
 296                 default:
 297                         return (NULL);
 298                 }
 299         if (first) {
 300                 if (*rp != END)
 301                         return (NULL);
 302                 *bp = '\0';
 303         }
 304         return (buf);
 305 }