Files
Paolo Bonzini 7446bac7a8 support (?<=[^C])
2007-11-08  Paolo Bonzini  <bonzini@gnu.org>

	* regcomp.c (find_fixedlength): Support some more opcodes.

git-archimport-id: bonzini@gnu.org--2004b/sed--ssed--3.61--patch-41
2008-01-09 16:18:58 +01:00

1043 lines
24 KiB
C

/*************************************************
* Perl-Compatible Regular Expressions *
*************************************************/
/*
This is a library of functions to support regular expressions whose syntax
and semantics are as close as possible to those of the Perl 5 language. See
the file Tech.Notes for some information on the internals.
Written by: Philip Hazel <ph10@cam.ac.uk>
Copyright (c) 1997-2000 University of Cambridge
-----------------------------------------------------------------------------
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. This software is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
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.
4. If PCRE is embedded in any software that is released under the GNU
General Purpose Licence (GPL), then the terms of that licence shall
supersede any condition above with which it is incompatible.
-----------------------------------------------------------------------------
*/
/* Include the internals header, which itself includes Standard C headers plus
the external pcre header. */
#include "internal.h"
/* Use a macro for debugging printing, 'cause that eliminates the use of #ifdef
inline, and there are *still* stupid compilers about that don't like indented
pre-processor statements. I suppose it's only been 10 years... */
#ifdef DEBUG
#define DPRINTF(p) printf p
#define DFWRITE(p) fwrite p
#else
#define DPRINTF(p) /*nothing */
#define DFWRITE(p) /*nothing */
#endif
/* Allow compilation as C++ source code, should anybody want to do that. */
#ifdef __cplusplus
#define class pcre_class
#endif
/* Tables of names of POSIX character classes and their lengths. The list is
terminated by a zero length entry. The first three must be alpha, upper, lower,
as this is assumed for handling case independence. */
static const char *posix_names[] =
{
"alpha", "lower", "upper",
"alnum", "ascii", "cntrl", "digit", "graph",
"print", "punct", "space", "word", "xdigit",
"blank"
};
static const uschar posix_name_lengths[] =
{
5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 4, 6, 5, 0
};
static const int posix_class_maps[] =
{
cbit_lower, cbit_upper, -1, /* alpha */
cbit_lower, -1, -1, /* lower */
cbit_upper, -1, -1, /* upper */
cbit_digit, cbit_lower, cbit_upper, /* alnum */
cbit_print, cbit_cntrl, -1, /* ascii */
cbit_cntrl, -1, -1, /* cntrl */
cbit_digit, -1, -1, /* digit */
cbit_graph, -1, -1, /* graph */
cbit_print, -1, -1, /* print */
cbit_punct, -1, -1, /* punct */
cbit_space, -1, -1, /* space */
cbit_word, -1, -1, /* word */
cbit_xdigit, -1, -1, /* xdigit */
cbit_blank, -1, -1 /* blank */
};
/*************************************************
* Check for counted repeat *
*************************************************/
/* This function is called when a '{' is encountered in a place where it might
start a quantifier. It looks ahead to see if it really is a quantifier or not.
It is only a quantifier if it is one of the forms {ddd} {ddd,} or {ddd,ddd}
where the ddds are digits.
Arguments:
p pointer to the first char after '{'
cd pointer to char tables block
Returns: TRUE or FALSE
*/
static BOOL
is_counted_repeat (p, cd)
const uschar *p;
compile_data *cd;
{
if (p > cd->end)
return FALSE;
if ((cd->ctypes[*p++] & ctype_digit) == 0)
return FALSE;
while (p <= cd->end && (cd->ctypes[*p] & ctype_digit) != 0)
p++;
/* Check end of regexp */
if (p > cd->end)
return FALSE;
if (p == cd->end)
return (*p == '}');
/* Not at end of regexp */
if (*p == '}')
return TRUE;
if (*p++ != ',')
return FALSE;
/* Check again for end of regexp */
if (p == cd->end)
return (*p == '}');
if (*p == '}')
return TRUE;
if (p > cd->end)
return FALSE;
if ((cd->ctypes[*p++] & ctype_digit) == 0)
return FALSE;
while (p <= cd->end && (cd->ctypes[*p] & ctype_digit) != 0)
p++;
return (p <= cd->end && *p == '}');
}
/*************************************************
* Read repeat counts *
*************************************************/
/* Read an item of the form {n,m} and return the values. This is called only
after is_counted_repeat() has confirmed that a repeat-count quantifier exists,
so the syntax is guaranteed to be correct, but we need to check the values.
Arguments:
p pointer to first char after '{'
minp pointer to int for min
maxp pointer to int for max
returned as -1 if no max
errorptr points to pointer to error message
cd pointer to character tables clock
Returns: pointer to '}' on success;
current ptr on error, with errorptr set
*/
static const uschar *
read_repeat_counts (p, minp, maxp, errorptr, cd)
const uschar *p;
int *minp;
int *maxp;
const char **errorptr;
compile_data *cd;
{
int min = 0;
int max = -1;
while ((cd->ctypes[*p] & ctype_digit) != 0)
min = min * 10 + *p++ - '0';
if (*p == '}')
max = min;
else
{
if (*(++p) != '}')
{
max = 0;
while ((cd->ctypes[*p] & ctype_digit) != 0)
max = max * 10 + *p++ - '0';
if (max < min)
{
*errorptr = pcre_estrings[4];
return p;
}
}
}
min *= *minp;
if (max > 0)
max *= *maxp;
/* Do paranoid checks, then fill in the required variables, and pass back the
pointer to the terminating '}'. */
if (min > 65535 || max > 65535)
*errorptr = pcre_estrings[5];
else
{
*minp = min;
*maxp = max;
}
return p;
}
/*************************************************
* Find the fixed length of a pattern *
*************************************************/
/* Scan a pattern and compute the fixed length of subject that will match it,
if the length is fixed. This is needed for dealing with backward assertions.
Arguments:
code points to the start of the pattern (the bracket)
options the compiling options
Returns: the fixed length, or -1 if there is no fixed length
*/
static int
find_fixedlength (code, options)
uschar *code;
int options;
{
int length = -1;
int branchlength = 0;
uschar *cc = code + 3;
/* Scan along the opcodes for this branch. If we get to the end of the
branch, check the length against that of the other branches. */
for (;;)
{
int d;
int op = *cc;
if (op >= OP_BRA)
op = OP_BRA;
switch (op)
{
case OP_BRA:
case OP_ONCE:
case OP_COND:
d = find_fixedlength (cc, options);
if (d < 0)
return -1;
branchlength += d;
do
cc += (cc[1] << 8) + cc[2];
while (*cc == OP_ALT);
cc += 3;
break;
/* Reached end of a branch; if it's a ket it is the end of a nested
call. If it's ALT it is an alternation in a nested call. If it is
END it's the end of the outer call. All can be handled by the same code. */
case OP_ALT:
case OP_KET:
case OP_KET_MAXSTAR:
case OP_KET_MINSTAR:
case OP_END:
if (length < 0)
length = branchlength;
else if (length != branchlength)
return -1;
if (*cc != OP_ALT)
return length;
cc += 3;
branchlength = 0;
break;
/* Skip over assertive subpatterns */
case OP_ASSERT:
case OP_ASSERT_NOT:
case OP_ASSERTBACK:
case OP_ASSERTBACK_NOT:
do
cc += (cc[1] << 8) + cc[2];
while (*cc == OP_ALT);
cc += 3;
break;
/* Skip over things that don't match chars */
case OP_REVERSE:
case OP_BRANUMBER:
case OP_CREF:
cc++;
/* Fall through */
case OP_OPT:
cc++;
/* Fall through */
case OP_SOD:
case OP_EOD:
case OP_EODN:
case OP_CIRC:
case OP_DOLL:
case OP_NOT_WORD_BOUNDARY:
case OP_WORD_BOUNDARY:
case OP_ANCHOR_MATCH:
cc++;
break;
/* Handle char strings. */
case OP_CHARS:
branchlength += *(++cc);
cc += *cc + 1;
break;
/* Handle exact repetitions */
case OP_EXACT:
case OP_TYPEEXACT:
case OP_TYPENOTEXACT:
branchlength += (cc[1] << 8) + cc[2];
cc += 4;
break;
/* Handle single-char matchers */
case OP_TYPE:
case OP_TYPENOT:
case OP_NOT:
branchlength++;
cc += 2;
break;
case OP_ANY:
branchlength++;
cc++;
break;
/* Check a class for variable quantification */
case OP_CLASS:
branchlength++;
cc += 33;
break;
case OP_CL_MAXSTAR:
case OP_CL_MINSTAR:
case OP_CL_MAXQUERY:
case OP_CL_MINQUERY:
return -1;
case OP_CL_MAXRANGE:
case OP_CL_MINRANGE:
cc += 33;
if ((cc[1] << 8) + cc[2] != (cc[3] << 8) + cc[4])
return -1;
branchlength += (cc[1] << 8) + cc[2];
cc += 4;
break;
/* Anything else is variable length */
default:
return -1;
}
}
/* Control never gets here */
}
/*************************************************
* Check for POSIX class syntax *
*************************************************/
/* This function is called when the sequence "[:" or "[." or "[=" is
encountered in a character class. It checks whether this is followed by an
optional ^ and then a sequence of letters, terminated by a matching ":]" or
".]" or "=]".
Argument:
ptr pointer to the initial [
endptr where to return the end pointer
cd pointer to compile data
Returns: TRUE or FALSE
*/
static BOOL
check_posix_syntax (ptr, endptr, cd)
const uschar *ptr;
const uschar **endptr;
compile_data *cd;
{
int terminator; /* Don't combine these lines; the Solaris cc */
terminator = *(++ptr); /* compiler warns about "non-constant" initializer. */
if (*(++ptr) == '^')
ptr++;
/* Use < because we have to look one character ahead */
while (ptr < cd->end && (cd->ctypes[*ptr] & ctype_letter) != 0)
ptr++;
if (ptr < cd->end && *ptr == terminator && ptr[1] == ']')
{
*endptr = ptr;
return TRUE;
}
return FALSE;
}
/*************************************************
* Check POSIX class name *
*************************************************/
/* This function is called to check the name given in a POSIX-style class entry
such as [:alnum:].
Arguments:
ptr points to the first letter
len the length of the name
Returns: a value representing the name, or -1 if unknown
*/
static int
check_posix_name (ptr, len)
const uschar *ptr;
int len;
{
int yield = 0;
while (posix_name_lengths[yield] != 0)
{
if (len == posix_name_lengths[yield] &&
strncmp ((const char *) ptr, posix_names[yield], len) == 0)
return yield;
yield++;
}
return -1;
}
/*************************************************
* Compile sequence of alternatives *
*************************************************/
/* On entry, ptr is pointing past the bracket character, but on return
it points to the closing bracket, or vertical bar, or end of string.
The code variable is pointing at the byte into which the BRA operator has been
stored. If the ims options are changed at the start (for a (?ims: group) or
during any branch, we need to insert an OP_OPT item at the start of every
following branch to ensure they get set correctly at run time, and also pass
the new options into every subsequent branch compile.
Argument:
options the option bits
optchanged new ims options to set as if (?ims) were at the start, or -1
for no change
brackets -> int containing the number of capturing brackets used
codeptr -> the address of the current code pointer
ptrptr -> the address of the current pattern pointer
errorptr -> pointer to error message
lookbehind TRUE if this is a lookbehind assertion
skipbytes skip this many bytes at start (for OP_COND, OP_BRANUMBER)
reqchar -> place to put the last required character, or a negative number
countlits -> place to put the shortest literal count of any branch
cd points to the data block with tables pointers
Returns: TRUE on success
*/
static BOOL
compile_regex (options, optchanged, brackets, codeptr, ptrptr, errorptr, lookbehind, skipbytes, reqchar, countlits, cd,
compile_branch_func)
int options;
int optchanged;
int *brackets;
uschar **codeptr;
const uschar **ptrptr;
const char **errorptr;
BOOL lookbehind;
int skipbytes;
int *reqchar;
int *countlits;
compile_data *cd;
BOOL (*compile_branch_func) (int, int *, uschar **, const uschar **, const char **, int *, int *, int *, compile_data *);
{
const uschar *ptr = *ptrptr;
uschar *code = *codeptr;
uschar *last_branch = code;
uschar *start_bracket = code;
uschar *reverse_count = NULL;
int oldoptions = options & PCRE_IMS;
int branchreqchar, branchcountlits;
*reqchar = -1;
*countlits = INT_MAX;
code += 3 + skipbytes;
/* Loop for each alternative branch */
for (;;)
{
int length;
/* Handle change of options */
if (optchanged >= 0)
{
*code++ = OP_OPT;
*code++ = optchanged;
options = (options & ~PCRE_IMS) | optchanged;
}
/* Set up dummy OP_REVERSE if lookbehind assertion */
if (lookbehind)
{
*code++ = OP_REVERSE;
reverse_count = code;
*code++ = 0;
*code++ = 0;
}
/* Now compile the branch */
if (!compile_branch_func (options, brackets, &code, &ptr, errorptr, &optchanged,
&branchreqchar, &branchcountlits, cd))
{
*ptrptr = ptr;
return FALSE;
}
/* Fill in the length of the last branch */
length = code - last_branch;
last_branch[1] = length >> 8;
last_branch[2] = length & 255;
/* Save the last required character if all branches have the same; a current
value of -1 means unset, while -2 means "previous branch had no last required
char". */
if (*reqchar != -2)
{
if (branchreqchar >= 0)
{
if (*reqchar == -1)
*reqchar = branchreqchar;
else if (*reqchar != branchreqchar)
*reqchar = -2;
}
else
*reqchar = -2;
}
/* Keep the shortest literal count */
if (branchcountlits < *countlits)
*countlits = branchcountlits;
DPRINTF (("literal count = %d min=%d\n", branchcountlits, *countlits));
/* If lookbehind, check that this branch matches a fixed-length string,
and put the length into the OP_REVERSE item. Temporarily mark the end of
the branch with OP_END. */
if (lookbehind)
{
*code = OP_END;
length = find_fixedlength (last_branch, options);
DPRINTF (("fixed length = %d\n", length));
if (length < 0)
{
*errorptr = pcre_estrings[25];
*ptrptr = ptr;
return FALSE;
}
reverse_count[0] = (length >> 8);
reverse_count[1] = length & 255;
}
/* Reached end of expression, either ')' or end of pattern. Insert a
terminating ket and the length of the whole bracketed item, and return,
leaving the pointer at the terminating char. If any of the ims options
were changed inside the group, compile a resetting op-code following. */
if (ptr > cd->end || *ptr != '|')
{
length = code - start_bracket;
*code++ = OP_KET;
*code++ = length >> 8;
*code++ = length & 255;
if (optchanged >= 0)
{
*code++ = OP_OPT;
*code++ = oldoptions;
}
*codeptr = code;
*ptrptr = ptr;
return TRUE;
}
/* Another branch follows; insert an "or" node and advance the pointer. */
*code = OP_ALT;
last_branch = code;
code += 3;
ptr++;
}
/* Control never reaches here */
}
/*************************************************
* Find first significant op code *
*************************************************/
/* This is called by several functions that scan a compiled expression looking
for a fixed first character, or an anchoring op code etc. It skips over things
that do not influence this. For one application, a change of caseless option is
important.
Arguments:
code pointer to the start of the group
options pointer to external options
optbit the option bit whose changing is significant, or
zero if none are
optstop TRUE to return on option change, otherwise change the options
value and continue
Returns: pointer to the first significant opcode
*/
static const uschar *
first_significant_code (code, options, optbit, optstop)
const uschar *code;
int *options;
int optbit;
BOOL optstop;
{
for (;;)
{
switch ((int) *code)
{
case OP_OPT:
if (optbit > 0 && ((int) code[1] & optbit) != (*options & optbit))
{
if (optstop)
return code;
*options = (int) code[1];
}
code += 2;
break;
case OP_CREF:
case OP_BRANUMBER:
code += 3;
break;
case OP_WORD_BOUNDARY:
case OP_NOT_WORD_BOUNDARY:
code++;
break;
case OP_ASSERT_NOT:
case OP_ASSERTBACK:
case OP_ASSERTBACK_NOT:
do
code += (code[1] << 8) + code[2];
while (*code == OP_ALT);
code += 3;
break;
default:
return code;
}
}
/* Control never reaches here */
}
/*************************************************
* Check for anchored expression *
*************************************************/
/* Try to find out if this is an anchored regular expression. Consider each
alternative branch. If they all start with OP_SOD or OP_CIRC, or with a bracket
all of whose alternatives start with OP_SOD or OP_CIRC (recurse ad lib), then
it's anchored. However, if this is a multiline pattern, then only OP_SOD
counts, since OP_CIRC can match in the middle.
A branch is also implicitly anchored if it starts with .* and DOTALL is set,
because that will try the rest of the pattern at all possible matching points,
so there is no point trying them again.
Arguments:
code points to start of expression (the bracket)
options points to the options setting
Returns: TRUE or FALSE
*/
static BOOL
is_anchored (code, options)
const uschar *code;
int *options;
{
do
{
const uschar *scode = first_significant_code (code + 3, options,
PCRE_MULTILINE, FALSE);
int op = *scode;
if (op >= OP_BRA || op == OP_ASSERT || op == OP_ONCE || op == OP_COND)
{
if (!is_anchored (scode, options))
return FALSE;
}
else if ((op == OP_TYPE_MAXSTAR || op == OP_TYPE_MINSTAR) &&
(*options & PCRE_DOTALL) != 0)
{
if (scode[1] != OP_ANY)
return FALSE;
}
else if (op != OP_SOD && op != OP_ANCHOR_MATCH
&& ((*options & PCRE_MULTILINE) != 0 || op != OP_CIRC))
return FALSE;
code += (code[1] << 8) + code[2];
}
while (*code == OP_ALT);
return TRUE;
}
/*************************************************
* Check for starting with ^ or .* *
*************************************************/
/* This is called to find out if every branch starts with ^ or .* so that
"first char" processing can be done to speed things up in multiline
matching and for non-DOTALL patterns that start with .* (which must start at
the beginning or after \n).
Argument: points to start of expression (the bracket)
Returns: TRUE or FALSE
*/
static BOOL
is_startline (code)
const uschar *code;
{
do
{
const uschar *scode = first_significant_code (code + 3, NULL, 0, FALSE);
int op = *scode;
if (op >= OP_BRA || op == OP_ASSERT || op == OP_ONCE || op == OP_COND)
{
if (!is_startline (scode))
return FALSE;
}
else if (op == OP_TYPE_MAXSTAR || op == OP_TYPE_MINSTAR)
{
if (scode[1] != OP_ANY)
return FALSE;
}
else if (op != OP_CIRC)
return FALSE;
code += (code[1] << 8) + code[2];
}
while (*code == OP_ALT);
return TRUE;
}
/*************************************************
* Check for ending with $ *
*************************************************/
/* This is called to find out if every branch ends with $ so that if the
match can only have a limited length we can start the match directly
at the end of the line.
Argument: points to start of expression (the bracket)
Returns: TRUE or FALSE
*/
static BOOL
is_endline (code)
const uschar *code;
{
BOOL was_dollar = FALSE, is_dollar = FALSE, found_dollar = FALSE;
for (;;)
{
int op;
was_dollar = is_dollar;
is_dollar = FALSE;
op = *code;
if (op >= OP_BRA)
op = OP_BRA;
switch (op)
{
case OP_EODN:
case OP_EOD:
found_dollar = is_dollar = TRUE;
/* Fall through */
case OP_END:
return found_dollar;
case OP_OPT:
code++;
break;
case OP_COND:
code += 2;
break;
case OP_CREF:
code++;
break;
case OP_CHARS:
code += code[1] + 2;
break;
case OP_KET_MAXSTAR:
case OP_KET_MINSTAR:
case OP_ALT:
case OP_KET:
if (!was_dollar)
return FALSE;
case OP_ASSERT:
case OP_ASSERT_NOT:
case OP_ASSERTBACK:
case OP_ASSERTBACK_NOT:
case OP_ONCE:
code += 2;
break;
case OP_REVERSE:
code += 2;
break;
case OP_MAXSTAR:
case OP_MINSTAR:
case OP_MAXPLUS:
case OP_MINPLUS:
case OP_MAXQUERY:
case OP_MINQUERY:
case OP_TYPE_MAXSTAR:
case OP_TYPE_MINSTAR:
case OP_TYPE_MAXPLUS:
case OP_TYPE_MINPLUS:
case OP_TYPE_MAXQUERY:
case OP_TYPE_MINQUERY:
code++;
break;
case OP_EXACT:
case OP_MAXUPTO:
case OP_MINUPTO:
code += 3;
break;
case OP_TYPEEXACT:
case OP_TYPE_MAXUPTO:
case OP_TYPE_MINUPTO:
code += 3;
break;
case OP_NOT:
code++;
break;
case OP_NOT_MAXSTAR:
case OP_NOT_MINSTAR:
case OP_NOT_MAXPLUS:
case OP_NOT_MINPLUS:
case OP_NOT_MAXQUERY:
case OP_NOT_MINQUERY:
code++;
break;
case OP_NOTEXACT:
case OP_NOT_MAXUPTO:
case OP_NOT_MINUPTO:
code += 3;
break;
case OP_CL_MAXSTAR:
case OP_CL_MINSTAR:
case OP_CL_MAXPLUS:
case OP_CL_MINPLUS:
case OP_CL_MAXQUERY:
case OP_CL_MINQUERY:
case OP_CLASS:
code += 32;
break;
case OP_CL_MAXRANGE:
case OP_CL_MINRANGE:
code += 36;
break;
case OP_REF:
case OP_REF_MAXSTAR:
case OP_REF_MINSTAR:
case OP_REF_MAXPLUS:
case OP_REF_MINPLUS:
case OP_REF_MAXQUERY:
case OP_REF_MINQUERY:
code++;
break;
case OP_REF_MAXRANGE:
case OP_REF_MINRANGE:
code += 5;
break;
case OP_BRA:
code += 3;
break;
/* Anything else is just a one-node item */
default:
code++;
break;
}
}
}
/*************************************************
* Check for fixed first char *
*************************************************/
/* Try to find out if there is a fixed first character. This is called for
unanchored expressions, as it speeds up their processing quite considerably.
Consider each alternative branch. If they all start with the same char, or with
a bracket all of whose alternatives start with the same char (recurse ad lib),
then we return that char, otherwise -1.
Arguments:
code points to start of expression (the bracket)
options pointer to the options (used to check casing changes)
Returns: -1 or the fixed first char
*/
static int
find_firstchar (code, options)
const uschar *code;
int *options;
{
int c = -1;
do
{
int d;
const uschar *scode = first_significant_code (code + 3, options,
PCRE_CASELESS, TRUE);
int op = *scode;
if (op >= OP_BRA)
op = OP_BRA;
switch (op)
{
default:
return -1;
case OP_BRA:
case OP_ASSERT:
case OP_ONCE:
case OP_COND:
if ((d = find_firstchar (scode, options)) < 0)
return -1;
if (c < 0)
c = d;
else if (c != d)
return -1;
break;
case OP_EXACT: /* Fall through */
scode++;
case OP_CHARS: /* Fall through */
scode++;
case OP_MAXPLUS:
case OP_MINPLUS:
if (c < 0)
c = scode[1];
else if (c != scode[1])
return -1;
break;
}
code += (code[1] << 8) + code[2];
}
while (*code == OP_ALT);
return c;
}