compiler/posixc/regex/regexec.c

   1 /*      $NetBSD: regexec.c,v 1.20 2007/02/09 23:44:18 junyoung Exp $    */
   2
   3 /*-
   4  * Copyright (c) 1992, 1993, 1994
   5  *      The Regents of the University of California.  All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Henry Spencer.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  *
  34  *      @(#)regexec.c   8.3 (Berkeley) 3/20/94
  35  */
  36
  37 /*-
  38  * Copyright (c) 1992, 1993, 1994 Henry Spencer.
  39  *
  40  * This code is derived from software contributed to Berkeley by
  41  * Henry Spencer.
  42  *
  43  * Redistribution and use in source and binary forms, with or without
  44  * modification, are permitted provided that the following conditions
  45  * are met:
  46  * 1. Redistributions of source code must retain the above copyright
  47  *    notice, this list of conditions and the following disclaimer.
  48  * 2. Redistributions in binary form must reproduce the above copyright
  49  *    notice, this list of conditions and the following disclaimer in the
  50  *    documentation and/or other materials provided with the distribution.
  51  * 3. All advertising materials mentioning features or use of this software
  52  *    must display the following acknowledgement:
  53  *      This product includes software developed by the University of
  54  *      California, Berkeley and its contributors.
  55  * 4. Neither the name of the University nor the names of its contributors
  56  *    may be used to endorse or promote products derived from this software
  57  *    without specific prior written permission.
  58  *
  59  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  60  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  61  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  62  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  63  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  64  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  65  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  66  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  67  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  68  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  69  * SUCH DAMAGE.
  70  *
  71  *      @(#)regexec.c   8.3 (Berkeley) 3/20/94
  72  */
  73
  74 /*
  75 __RCSID("$NetBSD: regexec.c,v 1.20 2007/02/09 23:44:18 junyoung Exp $");
  76 */
  77
  78 #if defined(__AROS__)
  79 #if !DEBUG
  80 #define NDEBUG
  81 #else
  82 #define REDEBUG
  83 #endif
  84 #endif
  85
  86 /*
  87  * the outer shell of regexec()
  88  *
  89  * This file includes engine.c *twice*, after muchos fiddling with the
  90  * macros that code uses.  This lets the same code operate on two different
  91  * representations for state sets.
  92  */
  93 #include <sys/types.h>
  94 #include <inttypes.h>
  95
  96 #include <assert.h>
  97 #include <ctype.h>
  98 #include <limits.h>
  99 #include <stdio.h>
 100 #include <stdlib.h>
 101 #include <string.h>
 102 #include <regex.h>
 103
 104 #ifdef __weak_alias
 105 __weak_alias(regexec,_regexec)
 106 #endif
 107
 108 #include "utils.h"
 109 #include "regex2.h"
 110
 111 /* macros for manipulating states, small version */
 112 #define states  unsigned long
 113 #define states1 unsigned long   /* for later use in regexec() decision */
 114 #define CLEAR(v)        ((v) = 0)
 115 #define SET0(v, n)      ((v) &= ~((unsigned long)1 << (n)))
 116 #define SET1(v, n)      ((v) |= (unsigned long)1 << (n))
 117 #define ISSET(v, n)     (((v) & ((unsigned long)1 << (n))) != 0)
 118 #define ASSIGN(d, s)    ((d) = (s))
 119 #define EQ(a, b)        ((a) == (b))
 120 #define STATEVARS       int dummy       /* dummy version */
 121 #define STATESETUP(m, n)        /* nothing */
 122 #define STATETEARDOWN(m)        /* nothing */
 123 #define SETUP(v)        ((v) = 0)
 124 #define onestate        unsigned long
 125 #define INIT(o, n)      ((o) = (unsigned long)1 << (n))
 126 #define INC(o)  ((o) <<= 1)
 127 #define ISSTATEIN(v, o) (((v) & (o)) != 0)
 128 /* some abbreviations; note that some of these know variable names! */
 129 /* do "if I'm here, I can also be there" etc without branches */
 130 #define FWD(dst, src, n)        ((dst) |= ((unsigned long)(src)&(here)) << (n))
 131 #define BACK(dst, src, n)       ((dst) |= ((unsigned long)(src)&(here)) >> (n))
 132 #define ISSETBACK(v, n) (((v) & ((unsigned long)here >> (n))) != 0)
 133 /* function names */
 134 #define SNAMES                  /* engine.c looks after details */
 135
 136 #include "engine.c"
 137
 138 /* now undo things */
 139 #undef  states
 140 #undef  CLEAR
 141 #undef  SET0
 142 #undef  SET1
 143 #undef  ISSET
 144 #undef  ASSIGN
 145 #undef  EQ
 146 #undef  STATEVARS
 147 #undef  STATESETUP
 148 #undef  STATETEARDOWN
 149 #undef  SETUP
 150 #undef  onestate
 151 #undef  INIT
 152 #undef  INC
 153 #undef  ISSTATEIN
 154 #undef  FWD
 155 #undef  BACK
 156 #undef  ISSETBACK
 157 #undef  SNAMES
 158
 159 /* macros for manipulating states, large version */
 160 #define states  char *
 161 #define CLEAR(v)        memset(v, 0, (size_t)m->g->nstates)
 162 #define SET0(v, n)      ((v)[n] = 0)
 163 #define SET1(v, n)      ((v)[n] = 1)
 164 #define ISSET(v, n)     ((v)[n])
 165 #define ASSIGN(d, s)    memcpy(d, s, (size_t)m->g->nstates)
 166 #define EQ(a, b)        (memcmp(a, b, (size_t)m->g->nstates) == 0)
 167 #define STATEVARS       int vn; char *space
 168 #define STATESETUP(m, nv) \
 169     if (((m)->space = malloc((size_t)((nv)*(m)->g->nstates))) == NULL) \
 170         return(REG_ESPACE); \
 171     else \
 172         (m)->vn = 0
 173
 174 #define STATETEARDOWN(m)        { free((m)->space); m->space = NULL; }
 175 #define SETUP(v)        ((v) = &m->space[(size_t)(m->vn++ * m->g->nstates)])
 176 #define onestate        int
 177 #define INIT(o, n)      ((o) = (n))
 178 #define INC(o)  ((o)++)
 179 #define ISSTATEIN(v, o) ((v)[o])
 180 /* some abbreviations; note that some of these know variable names! */
 181 /* do "if I'm here, I can also be there" etc without branches */
 182 #define FWD(dst, src, n)        ((dst)[here+(n)] |= (src)[here])
 183 #define BACK(dst, src, n)       ((dst)[here-(n)] |= (src)[here])
 184 #define ISSETBACK(v, n) ((v)[here - (n)])
 185 /* function names */
 186 #define LNAMES                  /* flag */
 187
 188 #include "engine.c"
 189
 190 /*
 191  - regexec - interface for matching
 192  = extern int regexec(const regex_t *, const char *, size_t, \
 193  =                                      regmatch_t [], int);
 194  = #define      REG_NOTBOL      00001
 195  = #define      REG_NOTEOL      00002
 196  = #define      REG_STARTEND    00004
 197  = #define      REG_TRACE       00400   // tracing of execution
 198  = #define      REG_LARGE       01000   // force large representation
 199  = #define      REG_BACKR       02000   // force use of backref code
 200  *
 201  * We put this here so we can exploit knowledge of the state representation
 202  * when choosing which matcher to call.  Also, by this point the matchers
 203  * have been prototyped.
 204  */
 205 int                             /* 0 success, REG_NOMATCH failure */
 206 regexec(
 207     const regex_t *preg,
 208     const char *string,
 209     size_t nmatch,
 210     regmatch_t pmatch[],
 211     int eflags)
 212 {
 213         struct re_guts *g = preg->re_g;
 214         char *s;
 215 #ifdef REDEBUG
 216 #       define  GOODFLAGS(f)    (f)
 217 #else
 218 #       define  GOODFLAGS(f)    ((f)&(REG_NOTBOL|REG_NOTEOL|REG_STARTEND))
 219 #endif
 220
 221         assert(preg != NULL);
 222         assert(string != NULL);
 223
 224         if (preg->re_magic != MAGIC1 || g->magic != MAGIC2)
 225                 return(REG_BADPAT);
 226         assert(!(g->iflags&BAD));
 227         if (g->iflags&BAD)              /* backstop for no-debug case */
 228                 return(REG_BADPAT);
 229         eflags = GOODFLAGS(eflags);
 230
 231         s = (char *)string;
 232
 233         if (g->nstates <= CHAR_BIT*sizeof(states1) && !(eflags&REG_LARGE))
 234                 return(smatcher(g, s, nmatch, pmatch, eflags));
 235         else
 236                 return(lmatcher(g, s, nmatch, pmatch, eflags));
 237 }