lib/libc/regex/regexec.c

   1 /*      $NetBSD: regexec.c,v 1.21 2009/02/12 05:06:54 lukem 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 #include <sys/cdefs.h>
  75 #if defined(LIBC_SCCS) && !defined(lint)
  76 #if 0
  77 static char sccsid[] = "@(#)regexec.c   8.3 (Berkeley) 3/20/94";
  78 #else
  79 __RCSID("$NetBSD: regexec.c,v 1.21 2009/02/12 05:06:54 lukem Exp $");
  80 #endif
  81 #endif /* LIBC_SCCS and not lint */
  82
  83 /*
  84  * the outer shell of regexec()
  85  *
  86  * This file includes engine.c *twice*, after muchos fiddling with the
  87  * macros that code uses.  This lets the same code operate on two different
  88  * representations for state sets.
  89  */
  90 #include "namespace.h"
  91 #include <sys/types.h>
  92
  93 #include <assert.h>
  94 #include <ctype.h>
  95 #include <limits.h>
  96 #include <stdio.h>
  97 #include <stdlib.h>
  98 #include <string.h>
  99 #include <regex.h>
 100
 101 #ifdef __weak_alias
 102 __weak_alias(regexec,_regexec)
 103 #endif
 104
 105 #include "utils.h"
 106 #include "regex2.h"
 107
 108 /* macros for manipulating states, small version */
 109 #define states  unsigned long
 110 #define states1 unsigned long   /* for later use in regexec() decision */
 111 #define CLEAR(v)        ((v) = 0)
 112 #define SET0(v, n)      ((v) &= ~((unsigned long)1 << (n)))
 113 #define SET1(v, n)      ((v) |= (unsigned long)1 << (n))
 114 #define ISSET(v, n)     (((v) & ((unsigned long)1 << (n))) != 0)
 115 #define ASSIGN(d, s)    ((d) = (s))
 116 #define EQ(a, b)        ((a) == (b))
 117 #define STATEVARS       int dummy       /* dummy version */
 118 #define STATESETUP(m, n)        /* nothing */
 119 #define STATETEARDOWN(m)        /* nothing */
 120 #define SETUP(v)        ((v) = 0)
 121 #define onestate        unsigned long
 122 #define INIT(o, n)      ((o) = (unsigned long)1 << (n))
 123 #define INC(o)  ((o) <<= 1)
 124 #define ISSTATEIN(v, o) (((v) & (o)) != 0)
 125 /* some abbreviations; note that some of these know variable names! */
 126 /* do "if I'm here, I can also be there" etc without branches */
 127 #define FWD(dst, src, n)        ((dst) |= ((unsigned long)(src)&(here)) << (n))
 128 #define BACK(dst, src, n)       ((dst) |= ((unsigned long)(src)&(here)) >> (n))
 129 #define ISSETBACK(v, n) (((v) & ((unsigned long)here >> (n))) != 0)
 130 /* function names */
 131 #define SNAMES                  /* engine.c looks after details */
 132
 133 #include "engine.c"
 134
 135 /* now undo things */
 136 #undef  states
 137 #undef  CLEAR
 138 #undef  SET0
 139 #undef  SET1
 140 #undef  ISSET
 141 #undef  ASSIGN
 142 #undef  EQ
 143 #undef  STATEVARS
 144 #undef  STATESETUP
 145 #undef  STATETEARDOWN
 146 #undef  SETUP
 147 #undef  onestate
 148 #undef  INIT
 149 #undef  INC
 150 #undef  ISSTATEIN
 151 #undef  FWD
 152 #undef  BACK
 153 #undef  ISSETBACK
 154 #undef  SNAMES
 155
 156 /* macros for manipulating states, large version */
 157 #define states  char *
 158 #define CLEAR(v)        memset(v, 0, (size_t)m->g->nstates)
 159 #define SET0(v, n)      ((v)[n] = 0)
 160 #define SET1(v, n)      ((v)[n] = 1)
 161 #define ISSET(v, n)     ((v)[n])
 162 #define ASSIGN(d, s)    memcpy(d, s, (size_t)m->g->nstates)
 163 #define EQ(a, b)        (memcmp(a, b, (size_t)m->g->nstates) == 0)
 164 #define STATEVARS       int vn; char *space
 165 #define STATESETUP(m, nv) \
 166     if (((m)->space = malloc((size_t)((nv)*(m)->g->nstates))) == NULL) \
 167         return(REG_ESPACE); \
 168     else \
 169         (m)->vn = 0
 170
 171 #define STATETEARDOWN(m)        { free((m)->space); m->space = NULL; }
 172 #define SETUP(v)        ((v) = &m->space[(size_t)(m->vn++ * m->g->nstates)])
 173 #define onestate        int
 174 #define INIT(o, n)      ((o) = (n))
 175 #define INC(o)  ((o)++)
 176 #define ISSTATEIN(v, o) ((v)[o])
 177 /* some abbreviations; note that some of these know variable names! */
 178 /* do "if I'm here, I can also be there" etc without branches */
 179 #define FWD(dst, src, n)        ((dst)[here+(n)] |= (src)[here])
 180 #define BACK(dst, src, n)       ((dst)[here-(n)] |= (src)[here])
 181 #define ISSETBACK(v, n) ((v)[here - (n)])
 182 /* function names */
 183 #define LNAMES                  /* flag */
 184
 185 #include "engine.c"
 186
 187 /*
 188  - regexec - interface for matching
 189  = extern int regexec(const regex_t *, const char *, size_t, \
 190  =                                      regmatch_t [], int);
 191  = #define      REG_NOTBOL      00001
 192  = #define      REG_NOTEOL      00002
 193  = #define      REG_STARTEND    00004
 194  = #define      REG_TRACE       00400   // tracing of execution
 195  = #define      REG_LARGE       01000   // force large representation
 196  = #define      REG_BACKR       02000   // force use of backref code
 197  *
 198  * We put this here so we can exploit knowledge of the state representation
 199  * when choosing which matcher to call.  Also, by this point the matchers
 200  * have been prototyped.
 201  */
 202 int                             /* 0 success, REG_NOMATCH failure */
 203 regexec(
 204     const regex_t *preg,
 205     const char *string,
 206     size_t nmatch,
 207     regmatch_t pmatch[],
 208     int eflags)
 209 {
 210         struct re_guts *g = preg->re_g;
 211         char *s;
 212 #ifdef REDEBUG
 213 #       define  GOODFLAGS(f)    (f)
 214 #else
 215 #       define  GOODFLAGS(f)    ((f)&(REG_NOTBOL|REG_NOTEOL|REG_STARTEND))
 216 #endif
 217
 218         _DIAGASSERT(preg != NULL);
 219         _DIAGASSERT(string != NULL);
 220
 221         if (preg->re_magic != MAGIC1 || g->magic != MAGIC2)
 222                 return(REG_BADPAT);
 223         assert(!(g->iflags&BAD));
 224         if (g->iflags&BAD)              /* backstop for no-debug case */
 225                 return(REG_BADPAT);
 226         eflags = GOODFLAGS(eflags);
 227
 228         s = __UNCONST(string);
 229
 230         if (g->nstates <= (sopno)(CHAR_BIT*sizeof(states1)) && !(eflags&REG_LARGE))
 231                 return(smatcher(g, s, nmatch, pmatch, eflags));
 232         else
 233                 return(lmatcher(g, s, nmatch, pmatch, eflags));
 234 }