git.cworth.org Git - vogl/blob - src/voglcore/regex/regexec.c

   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 #ifndef D_FILE_OFFSET_BITS
  28 #define _FILE_OFFSET_BITS 64
  29 #endif
  30 #ifndef _LARGEFILE64_SOURCE
  31 #define _LARGEFILE64_SOURCE 1
  32 #endif
  33
  34 /*
  35  * the outer shell of vogl_regexec()
  36  *
  37  * This file includes engine.c *twice*, after muchos fiddling with the
  38  * macros that code uses.  This lets the same code operate on two different
  39  * representations for state sets.
  40  */
  41 #include <sys/types.h>
  42 #include <stdio.h>
  43 #include <stdlib.h>
  44 #include <string.h>
  45 #include <limits.h>
  46 #include <ctype.h>
  47
  48 #include "regex.h"
  49
  50 #include "utils.h"
  51 #include "regex2.h"
  52
  53 // static int vogl_nope = 0;            /* for use in asserts; shuts lint up */
  54
  55 /* macros for manipulating states, small version */
  56 #define states unsigned
  57 #define states1 unsigned /* for later use in vogl_regexec() decision */
  58 #define CLEAR(v) ((v) = 0)
  59 #define SET0(v, n) ((v) &= ~((unsigned)1 << (n)))
  60 #define SET1(v, n) ((v) |= (unsigned)1 << (n))
  61 #define ISSET(v, n) ((v) & ((unsigned)1 << (n)))
  62 #define ASSIGN(d, s) ((d) = (s))
  63 #define EQ(a, b) ((a) == (b))
  64 #define STATEVARS int dummy /* dummy version */
  65 #define STATESETUP(m, n)    /* nothing */
  66 #define STATETEARDOWN(m)    /* nothing */
  67 #define SETUP(v) ((v) = 0)
  68 #define onestate unsigned
  69 #define INIT(o, n) ((o) = (unsigned)1 << (n))
  70 #define INC(o) ((o) <<= 1)
  71 #define ISSTATEIN(v, o) ((v) & (o))
  72 /* some abbreviations; note that some of these know variable names! */
  73 /* do "if I'm here, I can also be there" etc without branches */
  74 #define FWD(dst, src, n) ((dst) |= ((unsigned)(src) & (here)) << (n))
  75 #define BACK(dst, src, n) ((dst) |= ((unsigned)(src) & (here)) >> (n))
  76 #define ISSETBACK(v, n) ((v) & ((unsigned)here >> (n)))
  77 /* function names */
  78 #define SNAMES /* engine.c looks after details */
  79
  80 #include "engine.c"
  81
  82 /* now undo things */
  83 #undef states
  84 #undef CLEAR
  85 #undef SET0
  86 #undef SET1
  87 #undef ISSET
  88 #undef ASSIGN
  89 #undef EQ
  90 #undef STATEVARS
  91 #undef STATESETUP
  92 #undef STATETEARDOWN
  93 #undef SETUP
  94 #undef onestate
  95 #undef INIT
  96 #undef INC
  97 #undef ISSTATEIN
  98 #undef FWD
  99 #undef BACK
 100 #undef ISSETBACK
 101 #undef SNAMES
 102
 103 /* macros for manipulating states, large version */
 104 #define states char *
 105 #define CLEAR(v) memset(v, 0, m->g->nstates)
 106 #define SET0(v, n) ((v)[n] = 0)
 107 #define SET1(v, n) ((v)[n] = 1)
 108 #define ISSET(v, n) ((v)[n])
 109 #define ASSIGN(d, s) memcpy(d, s, m->g->nstates)
 110 #define EQ(a, b) (memcmp(a, b, m->g->nstates) == 0)
 111 #define STATEVARS \
 112     int vn;       \
 113     char *space
 114 #define STATESETUP(m, nv)                                  \
 115     {                                                      \
 116         (m)->space = regex_malloc((nv) * (m)->g->nstates); \
 117         if ((m)->space == NULL)                            \
 118             return (REG_ESPACE);                           \
 119         (m)->vn = 0;                                       \
 120     }
 121 #define STATETEARDOWN(m)        \
 122     {                           \
 123         regex_free((m)->space); \
 124     }
 125 #define SETUP(v) ((v) = &m->space[m->vn++ * m->g->nstates])
 126 #define onestate int
 127 #define INIT(o, n) ((o) = (n))
 128 #define INC(o) ((o)++)
 129 #define ISSTATEIN(v, o) ((v)[o])
 130 /* some abbreviations; note that some of these know variable names! */
 131 /* do "if I'm here, I can also be there" etc without branches */
 132 #define FWD(dst, src, n) ((dst)[here + (n)] |= (src)[here])
 133 #define BACK(dst, src, n) ((dst)[here - (n)] |= (src)[here])
 134 #define ISSETBACK(v, n) ((v)[here - (n)])
 135 /* function names */
 136 #define LNAMES /* flag */
 137
 138 #include "engine.c"
 139
 140 #define CASSERT(predicate, file) _impl_CASSERT_LINE(predicate, __LINE__, file)
 141
 142 #define _impl_PASTE(a, b) a##b
 143 #define _impl_CASSERT_LINE(predicate, line, file) \
 144     typedef char _impl_PASTE(assertion_failed_##file##_, line)[2 * !!(predicate) - 1];
 145
 146 /*
 147  - vogl_regexec - interface for matching
 148  = extern int vogl_regexec(const regex_t *, const char *, size_t, \
 149  =                                      regmatch_t [], int);
 150  = #define      REG_NOTBOL      00001
 151  = #define      REG_NOTEOL      00002
 152  = #define      REG_STARTEND    00004
 153  = #define      REG_TRACE       00400   // tracing of execution
 154  = #define      REG_LARGE       01000   // force large representation
 155  = #define      REG_BACKR       02000   // force use of backref code
 156  *
 157  * We put this here so we can exploit knowledge of the state representation
 158  * when choosing which matcher to call.  Also, by this point the matchers
 159  * have been prototyped.
 160  */
 161 int /* 0 success, REG_NOMATCH failure */
 162     vogl_regexec(preg, string, nmatch, pmatch, eflags)
 163     const regex_t *preg;
 164 const char *string;
 165 size_t nmatch;
 166 regmatch_t pmatch[];
 167 int eflags;
 168 {
 169     register struct re_guts *g = preg->re_g;
 170 #ifdef REDEBUG
 171 #define GOODFLAGS(f) (f)
 172 #else
 173 #define GOODFLAGS(f) ((f) & (REG_NOTBOL | REG_NOTEOL | REG_STARTEND))
 174 #endif
 175
 176     // Make sure off_t is ALWAYS 64-bits, because that's how the C++ code that calls this gets compiled.
 177     CASSERT(sizeof(off_t) == sizeof(unsigned long long), regexec_c);
 178
 179     if (preg->re_magic != MAGIC1 || g->magic != MAGIC2)
 180         return (REG_BADPAT);
 181     assert(!(g->iflags & BAD));
 182     if (g->iflags & BAD) /* backstop for no-debug case */
 183         return (REG_BADPAT);
 184     eflags = GOODFLAGS(eflags);
 185
 186     if (g->nstates <= (long)(CHAR_BIT * sizeof(states1)) && !(eflags & REG_LARGE))
 187         return (smatcher(g, (char *)string, nmatch, pmatch, eflags));
 188     else
 189         return (lmatcher(g, (char *)string, nmatch, pmatch, eflags));
 190 }