regengine.inc | Explore in Territory

/*-
 * This code is derived from OpenBSD's libc/regex, original license follows:
 *
 * Copyright (c) 1992, 1993, 1994 Henry Spencer.
 * Copyright (c) 1992, 1993, 1994
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Henry Spencer.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	@(#)engine.c	8.5 (Berkeley) 3/20/94
 */

/*
 * The matching engine and friends.  This file is #included by regexec.c
 * after suitable #defines of a variety of macros used herein, so that
 * different state representations can be used without duplicating masses
 * of code.
 */

#ifdef SNAMES
#define matcher …
#define fast …
#define slow …
#define dissect …
#define backref …
#define step …
#define print …
#define at …
#define match …
#define nope …
#define step_back …
#endif
#ifdef LNAMES
#define matcher …
#define fast …
#define slow …
#define dissect …
#define backref …
#define step …
#define print …
#define at …
#define match …
#define nope …
#define step_back …
#endif

/* another structure passed up and down to avoid zillions of parameters */
struct match { … };

static int matcher(struct re_guts *, const char *, size_t,
                   llvm_regmatch_t[], int);
static const char *dissect(struct match *, const char *, const char *, sopno,
                           sopno);
static const char *backref(struct match *, const char *, const char *, sopno,
                           sopno, sopno, int);
static const char *fast(struct match *, const char *, const char *, sopno, sopno);
static const char *slow(struct match *, const char *, const char *, sopno, sopno);
static states step(struct re_guts *, sopno, sopno, states, int, states);
#define MAX_RECURSION …
#define BOL …
#define EOL …
#define BOLEOL …
#define NOTHING …
#define BOW …
#define EOW …
#define CODEMAX …
#define NONCHAR(c) …
#define NNONCHAR …
#ifdef REDEBUG
static void print(struct match *, const char *, states, int, FILE *);
#endif
#ifdef REDEBUG
static void at(
	struct match *, const char *, const char *, const char *, sopno, sopno);
#endif
#ifdef REDEBUG
static char *pchar(int);
#endif

#ifdef REDEBUG
#define SP …
#define AT …
#define NOTE …
static int nope = 0;
#else
#define SP(t, s, c) …
#define AT(t, p1, p2, s1, s2) …
#define NOTE(s) …
#endif

/*
 - matcher - the actual matching engine
 */
static int			/* 0 success, REG_NOMATCH failure */
matcher(struct re_guts *g, const char *string, size_t nmatch,
        llvm_regmatch_t pmatch[],
    int eflags)
{ … }

/* Step back from "stop" to a position where the strip startst..stopst might
 * match. This can always conservatively return "stop - 1", but may return an
 * earlier position if matches at later positions are impossible. */
static const char *
step_back(struct re_guts *g, const char *start, const char *stop, sopno startst,
          sopno stopst)
{ … }

/*
 - dissect - figure out what matched what, no back references
 */
static const char *			/* == stop (success) always */
dissect(struct match *m, const char *start, const char *stop, sopno startst,
        sopno stopst)
{ … }

/*
 - backref - figure out what matched what, figuring in back references
 */
static const char *			/* == stop (success) or NULL (failure) */
backref(struct match *m, const char *start, const char *stop, sopno startst,
        sopno stopst, sopno lev, int rec)			/* PLUS nesting level */
{ … }

/*
 - fast - step through the string at top speed
 */
static const char *			/* where tentative match ended, or NULL */
fast(struct match *m, const char *start, const char *stop, sopno startst,
     sopno stopst)
{ … }

/*
 - slow - step through the string more deliberately
 */
static const char *			/* where it ended */
slow(struct match *m, const char *start, const char *stop, sopno startst,
     sopno stopst)
{ … }


/*
 - step - map set of states reachable before char to set reachable after
 */
static states
step(struct re_guts *g,
    sopno start,		/* start state within strip */
    sopno stop,			/* state after stop state within strip */
    states bef,			/* states reachable before */
    int ch,			/* character or NONCHAR code */
    states aft)			/* states already known reachable after */
{ … }

#ifdef REDEBUG
/*
 - print - print a set of states
 */
static void
print(struct match *m, const char *caption, states st, int ch, FILE *d)
{
	struct re_guts *g = m->g;
	int i;
	int first = 1;

	if (!(m->eflags&REG_TRACE))
		return;

	(void)fprintf(d, "%s", caption);
	if (ch != '\0')
		(void)fprintf(d, " %s", pchar(ch));
	for (i = 0; i < g->nstates; i++)
		if (ISSET(st, i)) {
			(void)fprintf(d, "%s%d", (first) ? "\t" : ", ", i);
			first = 0;
		}
	(void)fprintf(d, "\n");
}

/* 
 - at - print current situation
 */
static void
at(struct match *m, const char *title, const char *start, const char *stop,
	sopno startst, sopno stopst)
{
	if (!(m->eflags&REG_TRACE))
		return;

	(void)printf("%s %s-", title, pchar(*start));
	(void)printf("%s ", pchar(*stop));
	(void)printf("%ld-%ld\n", (long)startst, (long)stopst);
}

#ifndef PCHARDONE
#define PCHARDONE …
/*
 - pchar - make a character printable
 *
 * Is this identical to regchar() over in debug.c?  Well, yes.  But a
 * duplicate here avoids having a debugging-capable regexec.o tied to
 * a matching debug.o, and this is convenient.  It all disappears in
 * the non-debug compilation anyway, so it doesn't matter much.
 */
static char *			/* -> representation */
pchar(int ch)
{
	static char pbuf[10];

	if (isprint(ch) || ch == ' ')
		(void)snprintf(pbuf, sizeof pbuf, "%c", ch);
	else
		(void)snprintf(pbuf, sizeof pbuf, "\\%o", ch);
	return(pbuf);
}
#endif
#endif

#undef	matcher
#undef	fast
#undef	slow
#undef	dissect
#undef	backref
#undef	step
#undef	print
#undef	at
#undef	match
#undef	nope
#undef	step_back
llvm/llvm/lib/Support/regengine.inc
