/*
*
* regexp.c - regular expression matching
*
* DESCRIPTION
*
* Underneath the reformatting and comment blocks which were added to
* make it consistent with the rest of the code, you will find a
* modified version of Henry Specer's regular expression library.
* Henry's functions were modified to provide the minimal regular
* expression matching, as required by P1003. Henry's code was
* copyrighted, and copy of the copyright message and restrictions
* are provided, verbatim, below:
*
* Copyright (c) 1986 by University of Toronto.
* Written by Henry Spencer. Not derived from licensed software.
*
* Permission is granted to anyone to use this software for any
* purpose on any computer system, and to redistribute it freely,
* subject to the following restrictions:
*
* 1. The author is not responsible for the consequences of use of
* this software, no matter how awful, even if they arise
* from defects in it.
*
* 2. The origin of this software must not be misrepresented, either
* by explicit claim or by omission.
*
* 3. Altered versions must be plainly marked as such, and must not
* be misrepresented as being the original software.
*
*
* This version modified by Ian Phillipps to return pointer to terminating
* NUL on substitution string. [ Temp mail address ex-igp@camcon.co.uk ]
*
* Altered by amylaar to support excompatible option and the
* operators \< and >\ . ( 7.Sep. 1991 )
*
* regsub altered by amylaar to take an additional parameter specifying
* maximum number of bytes that can be written to the memory region
* pointed to by dest
*
* regcomp changed for DalekenMUD to use the internal memory allocation
* structures, this breaks the file for any other use!
*
* Beware that some of this code is subtly aware of the way operator
* precedence is structured in regular expressions. Serious changes in
* regular-expression syntax might require a total rethink.
*
* AUTHORS
*
* Mark H. Colburn, NAPS International (mark@jhereg.mn.org)
* Henry Spencer, University of Torronto (henry@utzoo.edu)
*
* Sponsored by The USENIX Association for public distribution.
*
*/
/* Headers */
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include "mud.h"
#include "regexp.h"
/*
* The "internal use only" fields in regexp.h are present to pass info from
* compile to execute that permits the execute phase to run lots faster on
* simple cases. They are:
*
* regstart char that must begin a match; '\0' if none obvious
* reganch is the match anchored (at beginning-of-line only)?
* regmust string (pointer into program) that match must include, or NULL
* regmlen length of regmust string
*
* Regstart and reganch permit very fast decisions on suitable starting points
* for a match, cutting down the work a lot. Regmust permits fast rejection
* of lines that cannot possibly match. The regmust tests are costly enough
* that regcomp() supplies a regmust only if the r.e. contains something
* potentially expensive (at present, the only such thing detected is * or +
* at the start of the r.e., which can involve a lot of backup). Regmlen is
* supplied because the test in regexec() needs it and regcomp() is computing
* it anyway.
*/
/*
* Structure for regexp "program". This is essentially a linear encoding
* of a nondeterministic finite-state machine (aka syntax charts or
* "railroad normal form" in parsing technology). Each node is an opcode
* plus a "nxt" pointer, possibly plus an operand. "Nxt" pointers of
* all nodes except BRANCH implement concatenation; a "nxt" pointer with
* a BRANCH on both ends of it is connecting two alternatives. (Here we
* have one of the subtle syntax dependencies: an individual BRANCH (as
* opposed to a collection of them) is never concatenated with anything
* because of operator precedence.) The operand of some types of node is
* a literal string; for others, it is a node leading into a sub-FSM. In
* particular, the operand of a BRANCH node is the first node of the branch.
* (NB this is *not* a tree structure: the tail of the branch connects
* to the thing following the set of BRANCHes.) The opcodes are:
*/
/* definition number opnd? meaning */
#define END 0 /* no End of program. */
#define BOL 1 /* no Match "" at beginning of line. */
#define EOL 2 /* no Match "" at end of line. */
#define ANY 3 /* no Match any one character. */
#define ANYOF 4 /* str Match any character in this string. */
#define ANYBUT 5 /* str Match any character not in this
* string. */
#define BRANCH 6 /* node Match this alternative, or the
* nxt... */
#define BACK 7 /* no Match "", "nxt" ptr points backward. */
#define EXACTLY 8 /* str Match this string. */
#define NOTHING 9 /* no Match empty string. */
#define STAR 10 /* node Match this (simple) thing 0 or more
* times. */
#define WORDSTART 11 /* node matching a start of a word */
#define WORDEND 12 /* node matching an end of a word */
#define OPEN 20 /* no Mark this point in input as start of
* #n. */
/* OPEN+1 is number 1, etc. */
#define CLOSE 30 /* no Analogous to OPEN. */
/*
* Opcode notes:
*
* BRANCH The set of branches constituting a single choice are hooked
* together with their "nxt" pointers, since precedence prevents
* anything being concatenated to any individual branch. The
* "nxt" pointer of the last BRANCH in a choice points to the
* thing following the whole choice. This is also where the
* final "nxt" pointer of each individual branch points; each
* branch starts with the operand node of a BRANCH node.
*
* BACK Normal "nxt" pointers all implicitly point forward; BACK
* exists to make loop structures possible.
*
* STAR complex '*', are implemented as circular BRANCH structures
* using BACK. Simple cases (one character per match) are
* implemented with STAR for speed and to minimize recursive
* plunges.
*
* OPEN,CLOSE ...are numbered at compile time.
*/
/*
* A node is one char of opcode followed by two chars of "nxt" pointer.
* "Nxt" pointers are stored as two 8-bit pieces, high order first. The
* value is a positive offset from the opcode of the node containing it.
* An operand, if any, simply follows the node. (Note that much of the
* code generation knows about this implicit relationship.)
*
* Using two bytes for the "nxt" pointer is vast overkill for most things,
* but allows patterns to get big without disasters.
*/
#define OP(p) (*(p))
#define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
#define OPERAND(p) ((p) + 3)
/*
* Utility definitions.
*/
#define SPECIAL 0x100
#define LBRAC ('('|SPECIAL)
#define RBRAC (')'|SPECIAL)
#define ASTERIX ('*'|SPECIAL)
#define OR_OP ('|'|SPECIAL)
#define DOLLAR ('$'|SPECIAL)
#define DOT ('.'|SPECIAL)
#define CARET ('^'|SPECIAL)
#define LSQBRAC ('['|SPECIAL)
#define RSQBRAC (']'|SPECIAL)
#define LSHBRAC ('<'|SPECIAL)
#define RSHBRAC ('>'|SPECIAL)
#define FAIL(m) { regerror(m); return(NULL); }
#define ISMULT(c) ((c) == ASTERIX)
#define META "^$.[()|*\\"
#ifndef CHARBITS
#define CHARBITS 0xff
#define UCHARAT(p) ((int)*(unsigned char *)(p))
#else
#define UCHARAT(p) ((int)*(p)&CHARBITS)
#endif
#define ISWORDPART(c) ( isalnum(c) || (c) == '_' )
/*
* Flags to be passed up and down.
*/
#define HASWIDTH 01 /* Known never to match null string. */
#define SIMPLE 02 /* Simple enough to be STAR operand. */
#define SPSTART 04 /* Starts with * */
#define WORST 0 /* Worst case. */
/*
* Global work variables for regcomp().
*/
static short *regparse; /* Input-scan pointer. */
static int regnpar; /* () count. */
static char regdummy;
static char *regcode; /* Code-emit pointer; ®dummy = don't. */
static int regsize; /* Code size. */
/*
* Forward declarations for regcomp()'s friends.
*/
#ifndef STATIC
#define STATIC static
#endif
STATIC char *reg args( ( int paren, int *flagp ) );
STATIC char *regbranch args( ( int *flagp ) );
STATIC char *regpiece args( ( int *flagp ) );
STATIC char *regatom args( ( int *flagp ) );
static char *regnode args( ( char op ) );
STATIC char *regnext args( ( register char *p ) );
static void regc args( ( char b ) );
static void reginsert args( ( char op, char *opnd ) );
STATIC void regtail args( ( char *p, char *val ) );
STATIC void regoptail args( ( char *p, char *val ) );
#ifdef STRCSPN
STATIC int strcspn();
#endif
/*
- regcomp - compile a regular expression into internal code
*
* We can't allocate space until we know how big the compiled form will be,
* but we can't compile it (and thus know how big it is) until we've got a
* place to put the code. So we cheat: we compile it twice, once with code
* generation turned off and size counting turned on, and once "for real".
* This also means that we don't allocate space until we are sure that the
* thing really will compile successfully, and we never have to move the
* code and thus invalidate pointers into it. (Note that it has to be in
* one piece because FREE() must be able to free it all.)
*
* Beware that the optimization-preparation code in here knows about some
* of the structure of the compiled regexp.
*/
regexp *regcomp( char *exp, int excompat )
/* excompat -> \( \) operators like in unix ex */
{
register regexp *r;
register char *scan;
register char *longest;
register unsigned int len;
int flags;
short *exp2,*dest,c;
int exp2size;
if( !exp )
FAIL( "NULL argument" );
exp2size = ( strlen( exp ) + 1 ) * ( sizeof( short[8] )
/ sizeof( char[8] ) );
exp2 = (short *)alloc_mem( exp2size );
/* exp2 = (short *)
DXALLOC( (strlen(exp)+1) * (sizeof(short[8])/sizeof(char[8])), 94,
"regcomp: 1" ); */
for( scan = exp, dest = exp2; ( c = *scan++ ); )
{
switch( c )
{
case '(':
case ')':
*dest++ = excompat ? c : c | SPECIAL;
break;
case '.':
case '*':
case '|':
case '$':
case '^':
case '[':
case ']':
*dest++ = c | SPECIAL;
break;
case '\\':
switch( c = *scan++ ) {
case '(':
case ')':
*dest++ = excompat ? c | SPECIAL : c;
break;
case '<':
case '>':
*dest++ = c | SPECIAL;
break;
case '{':
case '}':
FAIL( "sorry, unimplemented operator" );
case 'b': *dest++ = '\b'; break;
case 't': *dest++ = '\t'; break;
case 'r': *dest++ = '\r'; break;
default:
*dest++ = c;
}
break;
default:
*dest++ = c;
}
}
*dest=0;
/* First pass: determine size, legality. */
regparse = exp2;
regnpar = 1;
regsize = 0L;
regcode = ®dummy;
regc(MAGIC);
if( reg( 0, &flags ) == (char *)NULL)
return ( (regexp *)NULL );
/* Small enough for pointer-storage convention? */
if( regsize >= 32767L ) /* Probably could be 65535L. */
FAIL( "regexp too big" );
/* Allocate space. */
r = malloc( sizeof( regexp ) + (unsigned)regsize );
/* r = (regexp *) DXALLOC(sizeof(regexp) + (unsigned) regsize, 95,
"regcomp: 2"); */
if( !r )
FAIL( "out of space" );
/* Second pass: emit code. */
regparse = exp2;
regnpar = 1;
regcode = r->program;
regc(MAGIC);
if( reg( 0, &flags ) == NULL )
{
free( r );
return( (regexp *)NULL );
}
/* Dig out information for optimizations. */
r->regstart = '\0'; /* Worst-case defaults. */
r->reganch = 0;
r->regmust = NULL;
r->regmlen = 0;
scan = r->program + 1; /* First BRANCH. */
if( OP( regnext( scan ) ) == END ) /* Only one top-level choice. */
{
scan = OPERAND(scan);
/* Starting-point info. */
if( OP( scan ) == EXACTLY )
r->regstart = *OPERAND( scan );
else if( OP( scan ) == BOL )
r->reganch++;
/*
* If there's something expensive in the r.e., find the longest
* literal string that must appear and make it the regmust. Resolve
* ties in favor of later strings, since the regstart check works
* with the beginning of the r.e. and avoiding duplication
* strengthens checking. Not a strong reason, but sufficient in the
* absence of others.
*/
if( flags & SPSTART )
{
longest = NULL;
len = 0;
for( ; scan != NULL; scan = regnext( scan ) )
if( OP( scan ) == EXACTLY && strlen( OPERAND( scan ) ) >= len )
{
longest = OPERAND( scan );
len = strlen( OPERAND( scan ) );
}
r->regmust = longest;
r->regmlen = len;
}
}
free_mem( exp2, exp2size );
/* FREE((char*)exp2); */
return (r);
}
/*
- reg - regular expression, i.e. main body or parenthesized thing
*
* Caller must absorb opening parenthesis.
*
* Combining parenthesis handling with the base level of regular expression
* is a trifle forced, but the need to tie the tails of the branches to what
* follows makes it hard to avoid.
*/
static char *reg( int paren, int *flagp )
{
register char *ret;
register char *br;
register char *ender;
register int parno = 0;
int flags;
*flagp = HASWIDTH; /* Tentatively. */
/* Make an OPEN node, if parenthesized. */
if( paren )
{
if( regnpar >= NSUBEXP )
FAIL( "too many ()" );
parno = regnpar;
regnpar++;
ret = regnode( OPEN + parno );
}
else
ret = (char *)NULL;
/* Pick up the branches, linking them together. */
br = regbranch( &flags );
if( br == (char *)NULL )
return ((char *)NULL );
if( ret != (char *)NULL )
regtail( ret, br ); /* OPEN -> first. */
else
ret = br;
if( !( flags & HASWIDTH ) )
*flagp &= ~HASWIDTH;
*flagp |= flags & SPSTART;
while( *regparse == OR_OP )
{
regparse++;
br = regbranch( &flags );
if( br == (char *)NULL )
return NULL;
regtail( ret, br ); /* BRANCH -> BRANCH. */
if( !( flags & HASWIDTH ) )
*flagp &= ~HASWIDTH;
*flagp |= flags & SPSTART;
}
/* Make a closing node, and hook it on the end. */
ender = regnode( ( paren ) ? CLOSE + parno : END );
regtail( ret, ender );
/* Hook the tails of the branches to the closing node. */
for( br = ret; br; br = regnext( br ) )
regoptail( br, ender );
/* Check for proper termination. */
if( paren && *regparse++ != RBRAC )
{
FAIL( "unmatched ()" );
}
else if( !paren && *regparse != '\0' )
{
if( *regparse == RBRAC )
{
FAIL( "unmatched ()" );
}
else
FAIL( "junk on end" );/* "Can't happen". */
/* NOTREACHED */
}
return ret;
}
/*
- regbranch - one alternative of an | operator
*
* Implements the concatenation operator.
*/
static char *regbranch( int *flagp )
{
register char *ret;
register char *chain;
register char *latest;
int flags;
*flagp = WORST; /* Tentatively. */
ret = regnode( BRANCH );
chain = NULL;
while( *regparse != '\0' && *regparse != OR_OP && *regparse != RBRAC )
{
latest = regpiece( &flags );
if( !latest )
return NULL;
*flagp |= flags & HASWIDTH;
if( !chain ) /* First piece. */
*flagp |= flags & SPSTART;
else
regtail( chain, latest );
chain = latest;
}
if( !chain ) /* Loop ran zero times. */
regnode( NOTHING );
return ret;
}
/*
- regpiece - something followed by possible [*]
*
* Note that the branching code sequence used for * is somewhat optimized:
* they use the same NOTHING node as both the endmarker for their branch
* list and the body of the last branch. It might seem that this node could
* be dispensed with entirely, but the endmarker role is not redundant.
*/
static char *regpiece( int *flagp )
{
register char *ret;
register short op;
/* register char *nxt; */
int flags;
ret = regatom( &flags );
if( !ret )
return NULL;
op = *regparse;
if( !ISMULT( op ) )
{
*flagp = flags;
return ret;
}
if( !( flags & HASWIDTH ) )
FAIL( "* operand could be empty" );
*flagp = ( WORST | SPSTART );
if( op == ASTERIX && ( flags & SIMPLE ) )
reginsert( STAR, ret );
else if( op == ASTERIX )
{
/* Emit x* as (x&|), where & means "self". */
reginsert( BRANCH, ret ); /* Either x */
regoptail( ret, regnode( BACK ) ); /* and loop */
regoptail( ret, ret ); /* back */
regtail( ret, regnode( BRANCH ) ); /* or */
regtail( ret, regnode( NOTHING ) ); /* null. */
}
regparse++;
if( ISMULT( *regparse ) )
FAIL( "nested *" );
return ret;
}
/*
- regatom - the lowest level
*
* Optimization: gobbles an entire sequence of ordinary characters so that
* it can turn them into a single node, which is smaller to store and
* faster to run.
*/
static char *regatom( int * flagp )
{
register char *ret;
int flags;
*flagp = WORST; /* Tentatively. */
switch( *regparse++ )
{
case CARET:
ret = regnode( BOL );
break;
case DOLLAR:
ret = regnode( EOL );
break;
case DOT:
ret = regnode( ANY );
*flagp |= HASWIDTH | SIMPLE;
break;
case LSHBRAC:
ret = regnode( WORDSTART );
break;
case RSHBRAC:
ret = regnode( WORDEND );
break;
case LSQBRAC:
{
register int class;
register int classend;
if( *regparse == CARET ) /* Complement of range. */
{
ret = regnode( ANYBUT );
regparse++;
}
else
ret = regnode( ANYOF );
if( *regparse == RSQBRAC || *regparse == '-' )
regc( *regparse++ );
while( *regparse != '\0' && *regparse != RSQBRAC )
{
if( *regparse == '-' )
{
regparse++;
if( *regparse == RSQBRAC || *regparse == '\0' )
regc( '-' );
else
{
class = ( CHARBITS & *( regparse - 2 ) ) + 1;
classend = ( CHARBITS & *( regparse ) );
if( class > classend + 1 )
FAIL( "invalid [] range" );
for( ; class <= classend; class++ )
regc( class );
regparse++;
}
}
else
regc( *regparse++ );
}
regc('\0');
if( *regparse != RSQBRAC )
FAIL( "unmatched []" );
regparse++;
*flagp |= HASWIDTH | SIMPLE;
}
break;
case LBRAC:
ret = reg( 1, &flags );
if( !ret )
return NULL;
*flagp |= flags & ( HASWIDTH | SPSTART );
break;
case '\0':
case OR_OP:
case RBRAC:
FAIL( "internal urp" ); /* Supposed to be caught earlier. */
break;
case ASTERIX:
FAIL( "* follows nothing" );
break;
default:
{
register int len;
register short ender;
regparse--;
for( len=0; regparse[len]
&& !( regparse[len] & SPECIAL )
&& regparse[len] != RSQBRAC; len++ )
;
if( len <= 0 )
{
FAIL( "internal disaster" );
}
ender = *( regparse + len );
if( len > 1 && ISMULT( ender ) )
len--; /* Back off clear of * operand. */
*flagp |= HASWIDTH;
if( len == 1 )
*flagp |= SIMPLE;
ret = regnode( EXACTLY );
while( len > 0 )
{
regc( *regparse++ );
len--;
}
regc( '\0' );
}
break;
}
return ret;
}
/*
- regnode - emit a node
*/
static char *regnode( char op )
{
register char *ret;
register char *ptr;
ret = regcode;
if( ret == ®dummy )
{
regsize += 3;
return ret;
}
ptr = ret;
*ptr++ = op;
*ptr++ = '\0'; /* Null "nxt" pointer. */
*ptr++ = '\0';
regcode = ptr;
return ret;
}
/*
- regc - emit (if appropriate) a byte of code
*/
static void regc( char b )
{
if( regcode != ®dummy )
*regcode++ = b;
else
regsize++;
}
/*
- reginsert - insert an operator in front of already-emitted operand
*
* Means relocating the operand.
*/
static void reginsert( char op, char *opnd )
{
register char *src;
register char *dst;
register char *place;
if( regcode == ®dummy )
{
regsize += 3;
return;
}
src = regcode;
regcode += 3;
dst = regcode;
while( src > opnd )
*--dst = *--src;
place = opnd; /* Op node, where operand used to be. */
*place++ = op;
*place++ = '\0';
*place = '\0';
}
/*
- regtail - set the next-pointer at the end of a node chain
*/
static void regtail( char *p, char *val )
{
register char *scan;
register char *temp;
register int offset;
if( p == ®dummy )
return;
/* Find last node. */
scan = p;
for( ;; )
{
temp = regnext( scan );
if( !temp )
break;
scan = temp;
}
if( OP( scan ) == BACK )
offset = scan - val;
else
offset = val - scan;
*( scan + 1 ) = ( offset >> 8 ) & 0377;
*( scan + 2 ) = offset & 0377;
}
/*
- regoptail - regtail on operand of first argument; nop if operandless
*/
static void regoptail( char *p, char *val )
{
/* "Operandless" and "op != BRANCH" are synonymous in practice. */
if( !p || p == ®dummy || OP( p ) != BRANCH )
return;
regtail( OPERAND( p ), val );
}
/*
* regexec and friends
*/
/*
* Global work variables for regexec().
*/
static char *reginput; /* String-input pointer. */
static char *regbol; /* Beginning of input, for ^ check. */
static char **regstartp; /* Pointer to startp array. */
static char **regendp; /* Ditto for endp. */
/*
* Forwards.
*/
STATIC int regtry args( ( regexp *prog, char *string ) );
STATIC int regmatch args( ( char *prog ) );
STATIC int regrepeat args( ( char *p ) );
#ifdef DEBUG_REGEX
int regnarrate = 0;
void regdump();
STATIC char *regprop();
#endif
/*
- regexec - match a regexp against a string
*/
int regexec( register regexp *prog, register char *string )
{
register char *s;
/* Be paranoid... */
if( !prog || !string ) {
regerror("NULL parameter");
return 0;
}
/* Check validity of program. */
if( UCHARAT( prog->program ) != MAGIC )
{
regerror( "corrupted program" );
return 0;
}
/* If there is a "must appear" string, look for it. */
if( prog->regmust )
{
s = string;
while( ( s = strchr( s, prog->regmust[0] ) ) )
{
if( !strncmp( s, prog->regmust, prog->regmlen ) )
break; /* Found it. */
s++;
}
if( !s ) /* Not present. */
return 0;
}
/* Mark beginning of line for ^ . */
regbol = string;
/* Simplest case: anchored match need be tried only once. */
if( prog->reganch )
return ( regtry( prog, string ) );
/* Messy cases: unanchored match. */
s = string;
if( prog->regstart != '\0' )
/* We know what char it must start with. */
while( ( s = strchr( s, prog->regstart ) ) )
{
if( regtry( prog, s ) )
return 1;
s++;
}
else
/* We don't -- general case. */
do
{
if( regtry( prog, s ) )
return 1;
}
while( *s++ != '\0' );
/* Failure. */
return 0;
}
/*
- regtry - try match at specific point
*/
static int regtry( regexp *prog, char *string )
{
register int i;
register char **sp;
register char **ep;
reginput = string;
regstartp = prog->startp;
regendp = prog->endp;
sp = prog->startp;
ep = prog->endp;
for( i = NSUBEXP; i > 0; i-- )
{
*sp++ = NULL;
*ep++ = NULL;
}
if( regmatch( prog->program + 1 ) )
{
prog->startp[0] = string;
prog->endp[0] = reginput;
return 1;
}
return (0);
}
/*
- regmatch - main matching routine
*
* Conceptually the strategy is simple: check to see whether the current
* node matches, call self recursively to see whether the rest matches,
* and then act accordingly. In practice we make some effort to avoid
* recursion, in particular by going through "ordinary" nodes (that don't
* need to know whether the rest of the match failed) by a loop instead of
* by recursion.
*/
static int regmatch( char *prog )
{
register char *scan; /* Current node. */
char *nxt; /* nxt node. */
scan = prog;
#ifdef DEBUG_REGEX
if( scan && regnarrate )
fprintf( stderr, "%s(\n", regprop( scan ) );
#endif
while( scan )
{
#ifdef DEBUG_REGEX
if( regnarrate )
fprintf( stderr, "%s...\n", regprop( scan ) );
#endif
nxt = regnext( scan );
switch( OP( scan ) )
{
case BOL:
if( reginput != regbol )
return 0;
break;
case EOL:
if( *reginput != '\0' )
return 0;
break;
case ANY:
if( *reginput == '\0' )
return 0;
reginput++;
break;
case WORDSTART:
if( reginput == regbol )
break;
if( *reginput == '\0'
|| ISWORDPART( *( reginput - 1 ) )
|| !ISWORDPART( *reginput ) )
return 0;
break;
case WORDEND:
if( *reginput == '\0' )
break;
if( reginput == regbol
|| !ISWORDPART( *( reginput - 1 ) )
|| ISWORDPART( *reginput ) )
return 0;
break;
case EXACTLY:
{
register int len;
register char *opnd;
opnd = OPERAND( scan );
/* Inline the first character, for speed. */
if( *opnd != *reginput )
return 0;
len = strlen( opnd );
if( len > 1 && strncmp( opnd, reginput, len ) )
return 0;
reginput += len;
}
break;
case ANYOF:
if( *reginput == '\0'
|| !strchr( OPERAND( scan ), *reginput ) )
return 0;
reginput++;
break;
case ANYBUT:
if( *reginput == '\0'
|| strchr(OPERAND(scan), *reginput ) )
return (0);
reginput++;
break;
case NOTHING:
break;
case BACK:
break;
case OPEN + 1:
case OPEN + 2:
case OPEN + 3:
case OPEN + 4:
case OPEN + 5:
case OPEN + 6:
case OPEN + 7:
case OPEN + 8:
case OPEN + 9:
{
register int no;
register char *save;
no = OP( scan ) - OPEN;
save = reginput;
if( regmatch( nxt ) )
{
/*
* Don't set startp if some later invocation of the same
* parentheses already has.
*/
if( !regstartp[no] )
regstartp[no] = save;
return 1;
}
return (0);
}
break;
case CLOSE + 1:
case CLOSE + 2:
case CLOSE + 3:
case CLOSE + 4:
case CLOSE + 5:
case CLOSE + 6:
case CLOSE + 7:
case CLOSE + 8:
case CLOSE + 9:
{
register int no;
register char *save;
no = OP( scan ) - CLOSE;
save = reginput;
if( regmatch( nxt ) )
{
/*
* Don't set endp if some later invocation of the same
* parentheses already has.
*/
if( !regendp[no] )
regendp[no] = save;
return 1;
}
return 0;
}
break;
case BRANCH:
{
register char *save;
if( OP( nxt ) != BRANCH ) /* No choice. */
nxt = OPERAND( scan ); /* Avoid recursion. */
else
{
do
{
save = reginput;
if( regmatch( OPERAND( scan ) ) )
return 1;
reginput = save;
scan = regnext( scan );
}
while( scan && OP( scan ) == BRANCH );
return 0;
/* NOTREACHED */
}
}
break;
case STAR:
{
register char nextch;
register int no;
register char *save;
register int minimum;
/*
* Lookahead to avoid useless match attempts when we know
* what character comes next.
*/
nextch = '\0';
if( OP( nxt ) == EXACTLY )
nextch = *OPERAND( nxt );
minimum = ( OP( scan ) == STAR ) ? 0 : 1;
save = reginput;
no = regrepeat(OPERAND(scan));
while( no >= minimum )
{
/* If it could work, try it. */
if( nextch == '\0' || *reginput == nextch )
if( regmatch( nxt ) )
return 1;
/* Couldn't or didn't -- back up. */
no--;
reginput = save + no;
}
return 0;
}
break;
case END:
return 1; /* Success! */
break;
default:
regerror( "memory corruption" );
return 0;
break;
}
scan = nxt;
}
/*
* We get here only if there's trouble -- normally "case END" is the
* terminating point.
*/
regerror( "corrupted pointers" );
return 0;
}
/*
- regrepeat - repeatedly match something simple, report how many
*/
static int regrepeat( char *p )
{
register int count = 0;
register char *scan;
register char *opnd;
scan = reginput;
opnd = OPERAND( p );
switch( OP( p ) )
{
case ANY:
count = strlen( scan );
scan += count;
break;
case EXACTLY:
while( *opnd == *scan )
{
count++;
scan++;
}
break;
case ANYOF:
while( *scan != '\0' && strchr( opnd, *scan ) )
{
count++;
scan++;
}
break;
case ANYBUT:
while( *scan != '\0' && !strchr(opnd, *scan) )
{
count++;
scan++;
}
break;
default: /* Oh dear. Called inappropriately. */
regerror( "internal foulup" );
count = 0; /* Best compromise. */
break;
}
reginput = scan;
return count;
}
/*
- regnext - dig the "nxt" pointer out of a node
*/
static char *regnext( register char *p )
{
register int offset;
if( p == ®dummy )
return NULL;
offset = NEXT( p );
if( offset == 0 )
return NULL;
if( OP( p ) == BACK )
return ( p - offset );
else
return ( p + offset );
}
#ifdef DEBUG_REGEX
STATIC char *regprop();
/*
- regdump - dump a regexp onto stdout in vaguely comprehensible form
*/
void regdump( regexp *r )
{
register char *s;
register char op = EXACTLY; /* Arbitrary non-END op. */
register char *nxt;
#ifndef _AIX
extern char *strchr();
#endif /* _AIX */
s = r->program + 1;
while (op != END) { /* While that wasn't END last time... */
op = OP(s);
printf("%2d%s", (int)(s - r->program), regprop(s)); /* Where, what. */
nxt = regnext(s);
if (nxt == (char *)NULL) /* nxt ptr. */
printf("(0)");
else
printf("(%d)", (int)((s - r->program) + (nxt - s)));
s += 3;
if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
/* Literal string, where present. */
while (*s != '\0') {
putchar(*s);
s++;
}
s++;
}
putchar('\n');
}
/* Header fields of interest. */
if (r->regstart != '\0')
printf("start `%c' ", r->regstart);
if (r->reganch)
printf("anchored ");
if (r->regmust != (char *)NULL)
printf("must have \"%s\"", r->regmust);
printf("\n");
}
/*
- regprop - printable representation of opcode
*/
static char *regprop( char *op )
{
register char *p;
static char buf[50];
strcpy( buf, ":" );
switch( OP( op ) )
{
case BOL:
p = "BOL";
break;
case EOL:
p = "EOL";
break;
case ANY:
p = "ANY";
break;
case ANYOF:
p = "ANYOF";
break;
case ANYBUT:
p = "ANYBUT";
break;
case BRANCH:
p = "BRANCH";
break;
case EXACTLY:
p = "EXACTLY";
break;
case NOTHING:
p = "NOTHING";
break;
case BACK:
p = "BACK";
break;
case END:
p = "END";
break;
case OPEN + 1:
case OPEN + 2:
case OPEN + 3:
case OPEN + 4:
case OPEN + 5:
case OPEN + 6:
case OPEN + 7:
case OPEN + 8:
case OPEN + 9:
sprintf( buf + strlen( buf ), "OPEN%d", OP( op ) - OPEN );
p = NULL;
break;
case CLOSE + 1:
case CLOSE + 2:
case CLOSE + 3:
case CLOSE + 4:
case CLOSE + 5:
case CLOSE + 6:
case CLOSE + 7:
case CLOSE + 8:
case CLOSE + 9:
sprintf( buf + strlen( buf ), "CLOSE%d", OP( op ) - CLOSE );
p = NULL;
break;
case STAR:
p = "STAR";
break;
default:
regerror( "corrupted opcode" );
break;
}
if( p )
strcat( buf, p );
return buf;
}
#endif
/*
* The following is provided for those people who do not have strcspn() in
* their C libraries. They should get off their butts and do something
* about it; at least one public-domain implementation of those (highly
* useful) string routines has been published on Usenet.
*/
#ifdef STRCSPN
/*
* strcspn - find length of initial segment of s1 consisting entirely
* of characters not from s2
*/
static int strcspn( char *s1, char *s2 )
{
register char *scan1;
register char *scan2;
register int count;
count = 0;
for( scan1 = s1; *scan1 != '\0'; scan1++ )
{
for( scan2 = s2; *scan2 != '\0'; ) /* ++ moved down. */
if( *scan1 == *scan2++ )
return count;
count++;
}
return count;
}
#endif
/*
- regsub - perform substitutions after a regexp match
*/
char *regsub( regexp *prog, char *source, char *dest, int n )
{
register char *src;
register char *dst;
register char c;
register int no;
register int len;
if( !prog || !source || !dest )
{
regerror( "NULL parm to regsub" );
return NULL;
}
if( UCHARAT( prog->program) != MAGIC )
{
regerror( "damaged regexp fed to regsub" );
return NULL;
}
src = source;
dst = dest;
while( ( c = *src++ ) != '\0' )
{
if( c == '&' )
no = 0;
else if( c == '\\' && '0' <= *src && *src <= '9' )
no = *src++ - '0';
else
no = -1;
if( no < 0 ) /* Ordinary character. */
{
if( c == '\\' && ( *src == '\\' || *src == '&' ) )
c = *src++;
if( --n < 0 ) /* amylaar */
{
regerror( "line too long" );
return NULL;
}
*dst++ = c;
}
else if( prog->startp[no] && prog->endp[no] )
{
len = prog->endp[no] - prog->startp[no];
if( ( n -= len ) < 0 ) /* amylaar */
{
regerror( "line too long" );
return NULL;
}
strncpy( dst, prog->startp[no], len );
dst += len;
if( len != 0 && *( dst - 1 ) == '\0') /* strncpy hit NUL. */
{
regerror( "damaged match string" );
return NULL;
}
}
}
if( --n < 0 ) /* amylaar */
{
regerror( "line too long" );
return NULL;
}
*dst = '\0';
return dst;
}
const char *regexp_error;
void regerror( const char *s )
{
regexp_error = s;
}
