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®_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