1254225Speter/* $NetBSD: regexec.c,v 1.4 2009/10/31 20:11:53 dsl Exp $ */ 2254225Speter 3254225Speter/*- 4254225Speter * Copyright (c) 1992, 1993, 1994 Henry Spencer. 5254225Speter * Copyright (c) 1992, 1993, 1994 6254225Speter * The Regents of the University of California. All rights reserved. 7254225Speter * 8254225Speter * This code is derived from software contributed to Berkeley by 9254225Speter * Henry Spencer of the University of Toronto. 10254225Speter * 11254225Speter * Redistribution and use in source and binary forms, with or without 12254225Speter * modification, are permitted provided that the following conditions 13254225Speter * are met: 14254225Speter * 1. Redistributions of source code must retain the above copyright 15254225Speter * notice, this list of conditions and the following disclaimer. 16254225Speter * 2. Redistributions in binary form must reproduce the above copyright 17254225Speter * notice, this list of conditions and the following disclaimer in the 18254225Speter * documentation and/or other materials provided with the distribution. 19254225Speter * 3. All advertising materials mentioning features or use of this software 20254225Speter * must display the following acknowledgement: 21254225Speter * This product includes software developed by the University of 22254225Speter * California, Berkeley and its contributors. 23254225Speter * 4. Neither the name of the University nor the names of its contributors 24254225Speter * may be used to endorse or promote products derived from this software 25254225Speter * without specific prior written permission. 26254225Speter * 27254225Speter * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 28254225Speter * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 29254225Speter * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 30254225Speter * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 31254225Speter * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 32254225Speter * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 33254225Speter * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 34254225Speter * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 35254225Speter * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 36254225Speter * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 37254225Speter * SUCH DAMAGE. 38254225Speter * 39254225Speter * @(#)regexec.c 8.2 (Berkeley) 3/16/94 40254225Speter */ 41254225Speter 42254225Speter#if defined(LIBC_SCCS) && !defined(lint) 43254225Speterstatic char sccsid[] = "@(#)regexec.c 8.2 (Berkeley) 3/16/94"; 44254225Speter#endif /* LIBC_SCCS and not lint */ 45254225Speter 46254225Speter/* 47254225Speter * the outer shell of regexec() 48254225Speter * 49254225Speter * This file includes engine.c *twice*, after muchos fiddling with the 50254225Speter * macros that code uses. This lets the same code operate on two different 51254225Speter * representations for state sets. 52254225Speter */ 53254225Speter#include <sys/types.h> 54254225Speter#include <stdio.h> 55254225Speter#include <stdlib.h> 56254225Speter#include <string.h> 57254225Speter#include <limits.h> 58254225Speter#include <ctype.h> 59254225Speter#include <regex.h> 60254225Speter 61254225Speter#include "utils.h" 62254225Speter#include "regex2.h" 63254225Speter 64254225Speter#ifdef notdef 65254225Speterstatic int nope = 0; /* for use in asserts; shuts lint up */ 66254225Speter#endif 67254225Speter 68254225Speter/* macros for manipulating states, small version */ 69254225Speter#define states int 70254225Speter#define states1 int /* for later use in regexec() decision */ 71254225Speter#define CLEAR(v) ((v) = 0) 72254225Speter#define SET0(v, n) ((v) &= ~(1 << (n))) 73254225Speter#define SET1(v, n) ((v) |= 1 << (n)) 74254225Speter#define ISSET(v, n) ((v) & (1 << (n))) 75254225Speter#define ASSIGN(d, s) ((d) = (s)) 76254225Speter#define EQ(a, b) ((a) == (b)) 77254225Speter#define STATEVARS int dummy /* dummy version */ 78254225Speter#define STATESETUP(m, n) /* nothing */ 79254225Speter#define STATETEARDOWN(m) /* nothing */ 80254225Speter#define SETUP(v) ((v) = 0) 81254225Speter#define onestate int 82254225Speter#define INIT(o, n) ((o) = (unsigned)1 << (n)) 83254225Speter#define INC(o) ((o) <<= 1) 84254225Speter#define ISSTATEIN(v, o) ((v) & (o)) 85254225Speter/* some abbreviations; note that some of these know variable names! */ 86254225Speter/* do "if I'm here, I can also be there" etc without branches */ 87254225Speter#define FWD(dst, src, n) ((dst) |= ((unsigned)(src)&(here)) << (n)) 88254225Speter#define BACK(dst, src, n) ((dst) |= ((unsigned)(src)&(here)) >> (n)) 89254225Speter#define ISSETBACK(v, n) ((v) & ((unsigned)here >> (n))) 90254225Speter/* function names */ 91254225Speter#define SNAMES /* engine.c looks after details */ 92254225Speter 93254225Speter#include "engine.c" 94254225Speter 95254225Speter/* now undo things */ 96254225Speter#undef states 97254225Speter#undef CLEAR 98254225Speter#undef SET0 99254225Speter#undef SET1 100254225Speter#undef ISSET 101254225Speter#undef ASSIGN 102254225Speter#undef EQ 103254225Speter#undef STATEVARS 104254225Speter#undef STATESETUP 105254225Speter#undef STATETEARDOWN 106254225Speter#undef SETUP 107254225Speter#undef onestate 108254225Speter#undef INIT 109254225Speter#undef INC 110254225Speter#undef ISSTATEIN 111254225Speter#undef FWD 112254225Speter#undef BACK 113254225Speter#undef ISSETBACK 114254225Speter#undef SNAMES 115254225Speter 116254225Speter/* macros for manipulating states, large version */ 117254225Speter#define states char * 118254225Speter#define CLEAR(v) memset(v, 0, m->g->nstates) 119254225Speter#define SET0(v, n) ((v)[n] = 0) 120254225Speter#define SET1(v, n) ((v)[n] = 1) 121254225Speter#define ISSET(v, n) ((v)[n]) 122254225Speter#define ASSIGN(d, s) memcpy(d, s, m->g->nstates) 123254225Speter#define EQ(a, b) (memcmp(a, b, m->g->nstates) == 0) 124254225Speter#define STATEVARS int vn; char *space 125254225Speter#define STATESETUP(m, nv) { (m)->space = malloc((nv)*(m)->g->nstates); \ 126254225Speter if ((m)->space == NULL) return(REG_ESPACE); \ 127254225Speter (m)->vn = 0; } 128254225Speter#define STATETEARDOWN(m) { free((m)->space); } 129254225Speter#define SETUP(v) ((v) = &m->space[m->vn++ * m->g->nstates]) 130254225Speter#define onestate int 131254225Speter#define INIT(o, n) ((o) = (n)) 132254225Speter#define INC(o) ((o)++) 133254225Speter#define ISSTATEIN(v, o) ((v)[o]) 134254225Speter/* some abbreviations; note that some of these know variable names! */ 135254225Speter/* do "if I'm here, I can also be there" etc without branches */ 136254225Speter#define FWD(dst, src, n) ((dst)[here+(n)] |= (src)[here]) 137254225Speter#define BACK(dst, src, n) ((dst)[here-(n)] |= (src)[here]) 138254225Speter#define ISSETBACK(v, n) ((v)[here - (n)]) 139254225Speter/* function names */ 140254225Speter#define LNAMES /* flag */ 141254225Speter 142254225Speter#include "engine.c" 143254225Speter 144254225Speter/* 145254225Speter - regexec - interface for matching 146254225Speter = extern int regexec(const regex_t *, const char *, size_t, \ 147254225Speter = regmatch_t [], int); 148254225Speter = #define REG_NOTBOL 00001 149254225Speter = #define REG_NOTEOL 00002 150254225Speter = #define REG_STARTEND 00004 151254225Speter = #define REG_TRACE 00400 // tracing of execution 152254225Speter = #define REG_LARGE 01000 // force large representation 153254225Speter = #define REG_BACKR 02000 // force use of backref code 154254225Speter * 155254225Speter * We put this here so we can exploit knowledge of the state representation 156254225Speter * when choosing which matcher to call. Also, by this point the matchers 157254225Speter * have been prototyped. 158254225Speter */ 159254225Speterint /* 0 success, REG_NOMATCH failure */ 160254225Speterregexec(const regex_t *preg, const RCHAR_T *string, size_t nmatch, regmatch_t *pmatch, int eflags) 161254225Speter{ 162254225Speter register struct re_guts *g = preg->re_g; 163254225Speter#ifdef REDEBUG 164254225Speter# define GOODFLAGS(f) (f) 165254225Speter#else 166254225Speter# define GOODFLAGS(f) ((f)&(REG_NOTBOL|REG_NOTEOL|REG_STARTEND)) 167254225Speter#endif 168254225Speter 169254225Speter if (preg->re_magic != MAGIC1 || g->magic != MAGIC2) 170254225Speter return(REG_BADPAT); 171254225Speter assert(!(g->iflags&BAD)); 172254225Speter if (g->iflags&BAD) /* backstop for no-debug case */ 173254225Speter return(REG_BADPAT); 174254225Speter eflags = GOODFLAGS(eflags); 175254225Speter 176254225Speter if (g->nstates <= (int)(CHAR_BIT*sizeof(states1)) && !(eflags®_LARGE)) 177254225Speter return(smatcher(g, string, nmatch, pmatch, eflags)); 178254225Speter else 179254225Speter return(lmatcher(g, string, nmatch, pmatch, eflags)); 180254225Speter} 181