14fa7b105644222d9b35347c9d226ca8e011072ebColin Cross/*	$OpenBSD: regexec.c,v 1.11 2005/08/05 13:03:00 espie Exp $ */
24fa7b105644222d9b35347c9d226ca8e011072ebColin Cross/*-
34fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * Copyright (c) 1992, 1993, 1994 Henry Spencer.
44fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * Copyright (c) 1992, 1993, 1994
54fa7b105644222d9b35347c9d226ca8e011072ebColin Cross *	The Regents of the University of California.  All rights reserved.
64fa7b105644222d9b35347c9d226ca8e011072ebColin Cross *
74fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * This code is derived from software contributed to Berkeley by
84fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * Henry Spencer.
94fa7b105644222d9b35347c9d226ca8e011072ebColin Cross *
104fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * Redistribution and use in source and binary forms, with or without
114fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * modification, are permitted provided that the following conditions
124fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * are met:
134fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * 1. Redistributions of source code must retain the above copyright
144fa7b105644222d9b35347c9d226ca8e011072ebColin Cross *    notice, this list of conditions and the following disclaimer.
154fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * 2. Redistributions in binary form must reproduce the above copyright
164fa7b105644222d9b35347c9d226ca8e011072ebColin Cross *    notice, this list of conditions and the following disclaimer in the
174fa7b105644222d9b35347c9d226ca8e011072ebColin Cross *    documentation and/or other materials provided with the distribution.
184fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * 3. Neither the name of the University nor the names of its contributors
194fa7b105644222d9b35347c9d226ca8e011072ebColin Cross *    may be used to endorse or promote products derived from this software
204fa7b105644222d9b35347c9d226ca8e011072ebColin Cross *    without specific prior written permission.
214fa7b105644222d9b35347c9d226ca8e011072ebColin Cross *
224fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
234fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
244fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
254fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
264fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
274fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
284fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
294fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
304fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
314fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
324fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * SUCH DAMAGE.
334fa7b105644222d9b35347c9d226ca8e011072ebColin Cross *
344fa7b105644222d9b35347c9d226ca8e011072ebColin Cross *	@(#)regexec.c	8.3 (Berkeley) 3/20/94
354fa7b105644222d9b35347c9d226ca8e011072ebColin Cross */
364fa7b105644222d9b35347c9d226ca8e011072ebColin Cross
374fa7b105644222d9b35347c9d226ca8e011072ebColin Cross/*
384fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * the outer shell of regexec()
394fa7b105644222d9b35347c9d226ca8e011072ebColin Cross *
404fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * This file includes engine.c *twice*, after muchos fiddling with the
414fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * macros that code uses.  This lets the same code operate on two different
424fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * representations for state sets.
434fa7b105644222d9b35347c9d226ca8e011072ebColin Cross */
444fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#include <sys/types.h>
454fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#include <stdio.h>
464fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#include <stdlib.h>
474fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#include <string.h>
484fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#include <limits.h>
494fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#include <ctype.h>
504fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#include <regex.h>
514fa7b105644222d9b35347c9d226ca8e011072ebColin Cross
524fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#include "utils.h"
534fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#include "regex2.h"
544fa7b105644222d9b35347c9d226ca8e011072ebColin Cross
554fa7b105644222d9b35347c9d226ca8e011072ebColin Cross/* macros for manipulating states, small version */
564fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	states	long
574fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	states1	states		/* for later use in regexec() decision */
584fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	CLEAR(v)	((v) = 0)
594fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	SET0(v, n)	((v) &= ~((unsigned long)1 << (n)))
604fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	SET1(v, n)	((v) |= (unsigned long)1 << (n))
614fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	ISSET(v, n)	(((v) & ((unsigned long)1 << (n))) != 0)
624fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	ASSIGN(d, s)	((d) = (s))
634fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	EQ(a, b)	((a) == (b))
644fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	STATEVARS	long dummy	/* dummy version */
654fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	STATESETUP(m, n)	/* nothing */
664fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	STATETEARDOWN(m)	/* nothing */
674fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	SETUP(v)	((v) = 0)
684fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	onestate	long
694fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	INIT(o, n)	((o) = (unsigned long)1 << (n))
704fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	INC(o)		((o) <<= 1)
714fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	ISSTATEIN(v, o)	(((v) & (o)) != 0)
724fa7b105644222d9b35347c9d226ca8e011072ebColin Cross/* some abbreviations; note that some of these know variable names! */
734fa7b105644222d9b35347c9d226ca8e011072ebColin Cross/* do "if I'm here, I can also be there" etc without branches */
744fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	FWD(dst, src, n)	((dst) |= ((unsigned long)(src)&(here)) << (n))
754fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	BACK(dst, src, n)	((dst) |= ((unsigned long)(src)&(here)) >> (n))
764fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	ISSETBACK(v, n)		(((v) & ((unsigned long)here >> (n))) != 0)
774fa7b105644222d9b35347c9d226ca8e011072ebColin Cross/* function names */
784fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define SNAMES			/* engine.c looks after details */
794fa7b105644222d9b35347c9d226ca8e011072ebColin Cross
804fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#include "engine.c"
814fa7b105644222d9b35347c9d226ca8e011072ebColin Cross
824fa7b105644222d9b35347c9d226ca8e011072ebColin Cross/* now undo things */
834fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	states
844fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	CLEAR
854fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	SET0
864fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	SET1
874fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	ISSET
884fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	ASSIGN
894fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	EQ
904fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	STATEVARS
914fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	STATESETUP
924fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	STATETEARDOWN
934fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	SETUP
944fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	onestate
954fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	INIT
964fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	INC
974fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	ISSTATEIN
984fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	FWD
994fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	BACK
1004fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	ISSETBACK
1014fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#undef	SNAMES
1024fa7b105644222d9b35347c9d226ca8e011072ebColin Cross
1034fa7b105644222d9b35347c9d226ca8e011072ebColin Cross/* macros for manipulating states, large version */
1044fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	states	char *
1054fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	CLEAR(v)	memset(v, 0, m->g->nstates)
1064fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	SET0(v, n)	((v)[n] = 0)
1074fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	SET1(v, n)	((v)[n] = 1)
1084fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	ISSET(v, n)	((v)[n])
1094fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	ASSIGN(d, s)	memcpy(d, s, m->g->nstates)
1104fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	EQ(a, b)	(memcmp(a, b, m->g->nstates) == 0)
1114fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	STATEVARS	long vn; char *space
1124fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	STATESETUP(m, nv)	{ (m)->space = malloc((nv)*(m)->g->nstates); \
1134fa7b105644222d9b35347c9d226ca8e011072ebColin Cross				if ((m)->space == NULL) return(REG_ESPACE); \
1144fa7b105644222d9b35347c9d226ca8e011072ebColin Cross				(m)->vn = 0; }
1154fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	STATETEARDOWN(m)	{ free((m)->space); }
1164fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	SETUP(v)	((v) = &m->space[m->vn++ * m->g->nstates])
1174fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	onestate	long
1184fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	INIT(o, n)	((o) = (n))
1194fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	INC(o)	((o)++)
1204fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	ISSTATEIN(v, o)	((v)[o])
1214fa7b105644222d9b35347c9d226ca8e011072ebColin Cross/* some abbreviations; note that some of these know variable names! */
1224fa7b105644222d9b35347c9d226ca8e011072ebColin Cross/* do "if I'm here, I can also be there" etc without branches */
1234fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	FWD(dst, src, n)	((dst)[here+(n)] |= (src)[here])
1244fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	BACK(dst, src, n)	((dst)[here-(n)] |= (src)[here])
1254fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	ISSETBACK(v, n)	((v)[here - (n)])
1264fa7b105644222d9b35347c9d226ca8e011072ebColin Cross/* function names */
1274fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#define	LNAMES			/* flag */
1284fa7b105644222d9b35347c9d226ca8e011072ebColin Cross
1294fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#include "engine.c"
1304fa7b105644222d9b35347c9d226ca8e011072ebColin Cross
1314fa7b105644222d9b35347c9d226ca8e011072ebColin Cross/*
1324fa7b105644222d9b35347c9d226ca8e011072ebColin Cross - regexec - interface for matching
1334fa7b105644222d9b35347c9d226ca8e011072ebColin Cross *
1344fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * We put this here so we can exploit knowledge of the state representation
1354fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * when choosing which matcher to call.  Also, by this point the matchers
1364fa7b105644222d9b35347c9d226ca8e011072ebColin Cross * have been prototyped.
1374fa7b105644222d9b35347c9d226ca8e011072ebColin Cross */
1384fa7b105644222d9b35347c9d226ca8e011072ebColin Crossint				/* 0 success, REG_NOMATCH failure */
1394fa7b105644222d9b35347c9d226ca8e011072ebColin Crossregexec(const regex_t *preg, const char *string, size_t nmatch,
1404fa7b105644222d9b35347c9d226ca8e011072ebColin Cross    regmatch_t pmatch[], int eflags)
1414fa7b105644222d9b35347c9d226ca8e011072ebColin Cross{
1424fa7b105644222d9b35347c9d226ca8e011072ebColin Cross	struct re_guts *g = preg->re_g;
1434fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#ifdef REDEBUG
1444fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#	define	GOODFLAGS(f)	(f)
1454fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#else
1464fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#	define	GOODFLAGS(f)	((f)&(REG_NOTBOL|REG_NOTEOL|REG_STARTEND))
1474fa7b105644222d9b35347c9d226ca8e011072ebColin Cross#endif
1484fa7b105644222d9b35347c9d226ca8e011072ebColin Cross
1494fa7b105644222d9b35347c9d226ca8e011072ebColin Cross	if (preg->re_magic != MAGIC1 || g->magic != MAGIC2)
1504fa7b105644222d9b35347c9d226ca8e011072ebColin Cross		return(REG_BADPAT);
1514fa7b105644222d9b35347c9d226ca8e011072ebColin Cross	assert(!(g->iflags&BAD));
1524fa7b105644222d9b35347c9d226ca8e011072ebColin Cross	if (g->iflags&BAD)		/* backstop for no-debug case */
1534fa7b105644222d9b35347c9d226ca8e011072ebColin Cross		return(REG_BADPAT);
1544fa7b105644222d9b35347c9d226ca8e011072ebColin Cross	eflags = GOODFLAGS(eflags);
1554fa7b105644222d9b35347c9d226ca8e011072ebColin Cross
15650ace4fec5e8cb5afcbc656a4556fa528adfd760David 'Digit' Turner	if (g->nstates <= (int)(CHAR_BIT*sizeof(states1)) && !(eflags&REG_LARGE))
1574fa7b105644222d9b35347c9d226ca8e011072ebColin Cross		return(smatcher(g, (char *)string, nmatch, pmatch, eflags));
1584fa7b105644222d9b35347c9d226ca8e011072ebColin Cross	else
1594fa7b105644222d9b35347c9d226ca8e011072ebColin Cross		return(lmatcher(g, (char *)string, nmatch, pmatch, eflags));
1604fa7b105644222d9b35347c9d226ca8e011072ebColin Cross}
161