Home | History | Annotate | Download | only in regex
      1 /*	$OpenBSD: regexec.c,v 1.11 2005/08/05 13:03:00 espie Exp $ */
      2 /*-
      3  * Copyright (c) 1992, 1993, 1994 Henry Spencer.
      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  * the outer shell of regexec()
     39  *
     40  * This file includes engine.c *twice*, after muchos fiddling with the
     41  * macros that code uses.  This lets the same code operate on two different
     42  * representations for state sets.
     43  */
     44 #include <sys/types.h>
     45 #include <stdio.h>
     46 #include <stdlib.h>
     47 #include <string.h>
     48 #include <limits.h>
     49 #include <ctype.h>
     50 #include "./regex.h"
     51 
     52 #include "utils.h"
     53 #include "./regex2.h"
     54 
     55 /* macros for manipulating states, small version */
     56 #define	states	long
     57 #define	states1	states		/* for later use in regexec() decision */
     58 #define	CLEAR(v)	((v) = 0)
     59 #define	SET0(v, n)	((v) &= ~((unsigned long)1 << (n)))
     60 #define	SET1(v, n)	((v) |= (unsigned long)1 << (n))
     61 #define	ISSET(v, n)	(((v) & ((unsigned long)1 << (n))) != 0)
     62 #define	ASSIGN(d, s)	((d) = (s))
     63 #define	EQ(a, b)	((a) == (b))
     64 #define	STATEVARS	long dummy	/* dummy version */
     65 #define	STATESETUP(m, n)	/* nothing */
     66 #define	STATETEARDOWN(m)	/* nothing */
     67 #define	SETUP(v)	((v) = 0)
     68 #define	onestate	long
     69 #define	INIT(o, n)	((o) = (unsigned long)1 << (n))
     70 #define	INC(o)		((o) <<= 1)
     71 #define	ISSTATEIN(v, o)	(((v) & (o)) != 0)
     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 long)(src)&(here)) << (n))
     75 #define	BACK(dst, src, n)	((dst) |= ((unsigned long)(src)&(here)) >> (n))
     76 #define	ISSETBACK(v, n)		(((v) & ((unsigned long)here >> (n))) != 0)
     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	long vn; char *space
    112 #define	STATESETUP(m, nv)	{ (m)->space = (char*)malloc((nv)*(m)->g->nstates); \
    113 				if ((m)->space == NULL) return(REG_ESPACE); \
    114 				(m)->vn = 0; }
    115 #define	STATETEARDOWN(m)	{ free((m)->space); }
    116 #define	SETUP(v)	((v) = &m->space[m->vn++ * m->g->nstates])
    117 #define	onestate	long
    118 #define	INIT(o, n)	((o) = (n))
    119 #define	INC(o)	((o)++)
    120 #define	ISSTATEIN(v, o)	((v)[o])
    121 /* some abbreviations; note that some of these know variable names! */
    122 /* do "if I'm here, I can also be there" etc without branches */
    123 #define	FWD(dst, src, n)	((dst)[here+(n)] |= (src)[here])
    124 #define	BACK(dst, src, n)	((dst)[here-(n)] |= (src)[here])
    125 #define	ISSETBACK(v, n)	((v)[here - (n)])
    126 /* function names */
    127 #define	LNAMES			/* flag */
    128 
    129 #include "engine.c"
    130 
    131 /*
    132  - regexec - interface for matching
    133  *
    134  * We put this here so we can exploit knowledge of the state representation
    135  * when choosing which matcher to call.  Also, by this point the matchers
    136  * have been prototyped.
    137  */
    138 int				/* 0 success, REG_NOMATCH failure */
    139 regexec(const regex_t *preg, const char *string, size_t nmatch,
    140     regmatch_t pmatch[], int eflags)
    141 {
    142 	struct re_guts *g = preg->re_g;
    143 #ifdef REDEBUG
    144 #	define	GOODFLAGS(f)	(f)
    145 #else
    146 #	define	GOODFLAGS(f)	((f)&(REG_NOTBOL|REG_NOTEOL|REG_STARTEND))
    147 #endif
    148 
    149 	if (preg->re_magic != MAGIC1 || g->magic != MAGIC2)
    150 		return(REG_BADPAT);
    151 	assert(!(g->iflags&BAD));
    152 	if (g->iflags&BAD)		/* backstop for no-debug case */
    153 		return(REG_BADPAT);
    154 	eflags = GOODFLAGS(eflags);
    155 
    156 	if (g->nstates <= (int)(CHAR_BIT*sizeof(states1)) && !(eflags&REG_LARGE))
    157 		return(smatcher(g, (char *)string, nmatch, pmatch, eflags));
    158 	else
    159 		return(lmatcher(g, (char *)string, nmatch, pmatch, eflags));
    160 }
    161