git.cworth.org Git - vogl/blob - src/voglcore/regex/regex2.h

   1 /**************************************************************************
   2  *
   3  * Copyright 2013-2014 RAD Game Tools and Valve Software
   4  * Copyright 2010-2014 Rich Geldreich and Tenacious Software LLC
   5  * All Rights Reserved.
   6  *
   7  * Permission is hereby granted, free of charge, to any person obtaining a copy
   8  * of this software and associated documentation files (the "Software"), to deal
   9  * in the Software without restriction, including without limitation the rights
  10  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  11  * copies of the Software, and to permit persons to whom the Software is
  12  * furnished to do so, subject to the following conditions:
  13  *
  14  * The above copyright notice and this permission notice shall be included in
  15  * all copies or substantial portions of the Software.
  16  *
  17  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  18  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  19  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  20  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  21  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  22  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  23  * THE SOFTWARE.
  24  *
  25  **************************************************************************/
  26
  27 /*
  28  * First, the stuff that ends up in the outside-world include file
  29  = typedef off_t regoff_t;
  30  = typedef struct {
  31  =      int re_magic;
  32  =      size_t re_nsub;         // number of parenthesized subexpressions
  33  =      const char *re_endp;    // end pointer for REG_PEND
  34  =      struct re_guts *re_g;   // none of your business :-)
  35  = } regex_t;
  36  = typedef struct {
  37  =      regoff_t rm_so;         // start of match
  38  =      regoff_t rm_eo;         // end of match
  39  = } regmatch_t;
  40  */
  41 /*
  42  * internals of regex_t
  43  */
  44 #define MAGIC1 ((('r' ^ 0200) << 8) | 'e')
  45
  46 /*
  47  * The internal representation is a *strip*, a sequence of
  48  * operators ending with an endmarker.  (Some terminology etc. is a
  49  * historical relic of earlier versions which used multiple strips.)
  50  * Certain oddities in the representation are there to permit running
  51  * the machinery backwards; in particular, any deviation from sequential
  52  * flow must be marked at both its source and its destination.  Some
  53  * fine points:
  54  *
  55  * - OPLUS_ and O_PLUS are *inside* the loop they create.
  56  * - OQUEST_ and O_QUEST are *outside* the bypass they create.
  57  * - OCH_ and O_CH are *outside* the multi-way branch they create, while
  58  *   OOR1 and OOR2 are respectively the end and the beginning of one of
  59  *   the branches.  Note that there is an implicit OOR2 following OCH_
  60  *   and an implicit OOR1 preceding O_CH.
  61  *
  62  * In state representations, an operator's bit is on to signify a state
  63  * immediately *preceding* "execution" of that operator.
  64  */
  65 typedef long sop; /* strip operator */
  66 typedef long sopno;
  67 #define OPRMASK 0x7c000000
  68 #define OPDMASK 0x03ffffff
  69 #define OPSHIFT (26)
  70 #define OP(n) ((n) & OPRMASK)
  71 #define OPND(n) ((n) & OPDMASK)
  72 #define SOP(op, opnd) ((op) | (opnd))
  73 /* operators                       meaning      operand                 */
  74 /*                                              (back, fwd are offsets) */
  75 #define OEND (1 << OPSHIFT)     /* endmarker    -                       */
  76 #define OCHAR (2 << OPSHIFT)    /* character    unsigned char           */
  77 #define OBOL (3 << OPSHIFT)     /* left anchor  -                       */
  78 #define OEOL (4 << OPSHIFT)     /* right anchor -                       */
  79 #define OANY (5 << OPSHIFT)     /* .            -                       */
  80 #define OANYOF (6 << OPSHIFT)   /* [...]        set number              */
  81 #define OBACK_ (7 << OPSHIFT)   /* begin \d     paren number            */
  82 #define O_BACK (8 << OPSHIFT)   /* end \d       paren number            */
  83 #define OPLUS_ (9 << OPSHIFT)   /* + prefix     fwd to suffix           */
  84 #define O_PLUS (10 << OPSHIFT)  /* + suffix     back to prefix          */
  85 #define OQUEST_ (11 << OPSHIFT) /* ? prefix     fwd to suffix           */
  86 #define O_QUEST (12 << OPSHIFT) /* ? suffix     back to prefix          */
  87 #define OLPAREN (13 << OPSHIFT) /* (            fwd to )                */
  88 #define ORPAREN (14 << OPSHIFT) /* )            back to (               */
  89 #define OCH_ (15 << OPSHIFT)    /* begin choice fwd to OOR2             */
  90 #define OOR1 (16 << OPSHIFT)    /* | pt. 1      back to OOR1 or OCH_    */
  91 #define OOR2 (17 << OPSHIFT)    /* | pt. 2      fwd to OOR2 or O_CH     */
  92 #define O_CH (18 << OPSHIFT)    /* end choice   back to OOR1            */
  93 #define OBOW (19 << OPSHIFT)    /* begin word   -                       */
  94 #define OEOW (20 << OPSHIFT)    /* end word     -                       */
  95
  96 /*
  97  * Structure for [] character-set representation.  Character sets are
  98  * done as bit vectors, grouped 8 to a byte vector for compactness.
  99  * The individual set therefore has both a pointer to the byte vector
 100  * and a mask to pick out the relevant bit of each byte.  A hash code
 101  * simplifies testing whether two sets could be identical.
 102  *
 103  * This will get trickier for multicharacter collating elements.  As
 104  * preliminary hooks for dealing with such things, we also carry along
 105  * a string of multi-character elements, and decide the size of the
 106  * vectors at run time.
 107  */
 108 typedef struct
 109 {
 110     uch *ptr; /* -> uch [csetsize] */
 111     uch mask; /* bit within array */
 112     uch hash; /* hash code */
 113     size_t smultis;
 114     char *multis; /* -> char[smulti]  ab\0cd\0ef\0\0 */
 115 } cset;
 116 /* note that CHadd and CHsub are unsafe, and CHIN doesn't yield 0/1 */
 117 #define CHadd(cs, c) ((cs)->ptr[(uch)(c)] |= (cs)->mask, (cs)->hash += (c))
 118 #define CHsub(cs, c) ((cs)->ptr[(uch)(c)] &= ~(cs)->mask, (cs)->hash -= (c))
 119 #define CHIN(cs, c) ((cs)->ptr[(uch)(c)] & (cs)->mask)
 120 #define MCadd(p, cs, cp) vogl_mcadd(p, cs, cp) /* regcomp() internal fns */
 121 #define MCsub(p, cs, cp) vogl_mcsub(p, cs, cp)
 122 #define MCin(p, cs, cp) vogl_mcin(p, cs, cp)
 123
 124 /* stuff for character categories */
 125 typedef unsigned char cat_t;
 126
 127 /*
 128  * main compiled-expression structure
 129  */
 130 struct re_guts
 131 {
 132     int magic;
 133 #define MAGIC2 ((('R' ^ 0200) << 8) | 'E')
 134     sop *strip;        /* malloced area for strip */
 135     int csetsize;      /* number of bits in a cset vector */
 136     int ncsets;        /* number of csets in use */
 137     cset *sets;        /* -> cset [ncsets] */
 138     uch *setbits;      /* -> uch[csetsize][ncsets/CHAR_BIT] */
 139     int cflags;        /* copy of regcomp() cflags argument */
 140     sopno nstates;     /* = number of sops */
 141     sopno firststate;  /* the initial OEND (normally 0) */
 142     sopno laststate;   /* the final OEND */
 143     int iflags;        /* internal flags */
 144 #define USEBOL 01      /* used ^ */
 145 #define USEEOL 02      /* used $ */
 146 #define BAD 04         /* something wrong */
 147     int nbol;          /* number of ^ used */
 148     int neol;          /* number of $ used */
 149     int ncategories;   /* how many character categories */
 150     cat_t *categories; /* ->catspace[-CHAR_MIN] */
 151     char *must;        /* match must contain this string */
 152     int mlen;          /* length of must */
 153     size_t nsub;       /* copy of re_nsub */
 154     int backrefs;      /* does it use back references? */
 155     sopno nplus;       /* how deep does it nest +s? */
 156     /* catspace must be last */
 157     cat_t catspace[1]; /* actually [NC] */
 158 };
 159
 160 /* misc utilities */
 161 #define OUT (CHAR_MAX + 1) /* a non-character value */
 162 #define ISWORD(c) (isalnum(c) || (c) == '_')
 163
 164 #define REGEX_FUNCTIONIZE(a, b) a(b)
 165 #define REGEX_STRINGIZE(a) #a
 166 #define REGEX_INT2STRING(i) REGEX_FUNCTIONIZE(REGEX_STRINGIZE, i)
 167 #define REGEX_FILE_POS_STRING __FILE__ ":" REGEX_INT2STRING(__LINE__)
 168
 169 extern void *vogl_realloc(const char *pFile_line, void *p, size_t new_size);
 170
 171 #define regex_malloc(size) vogl_realloc(REGEX_FILE_POS_STRING, NULL, (size))
 172 #define regex_free(ptr) vogl_realloc(REGEX_FILE_POS_STRING, (ptr), 0)
 173 #define regex_realloc(ptr, newsize) vogl_realloc(REGEX_FILE_POS_STRING, (ptr), (newsize))