/*
* Changes by Gunnar Ritter, Freiburg i. Br., Germany, November 2002.
*
* Sccsid @(#)bracket.c 1.14 (gritter) 10/18/03
*/
/* UNIX(R) Regular Expresssion Library
*
* Note: Code is released under the GNU LGPL
*
* Copyright (C) 2001 Caldera International, Inc.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Lesser General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library 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. See the GNU
* Lesser General Public License for more details.
*
* You should have received a copy of the GNU Lesser General Public
* License along with this library; if not, write to:
* Free Software Foundation, Inc.
* 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*/
/* #include "synonyms.h" */
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
#include "re.h"
/*
* Build and match the [...] part of REs.
*
* In general, each compiled bracket construct holds a set of mapped
* wide character values and a set of character classifications.
* The mapping applied (when the current LC_COLLATE is not CHF_ENCODED)
* is the "basic" weight (cep->weight[0]); otherwise the actual wide
* character is used.
*
* To support simplified range handling, this code assumes that a w_type,
* a signed integer type, can hold all valid basic weight values (as well
* as all wide character values for CHF_ENCODED locales) and that these
* are all positive. Negative values indicate error conditions (BKT_*);
* zero (which must be the same as WGHT_IGNORE) indicates success, but
* that the item installed is not a range endpoint.
*/
static int
addwide(Bracket *bp, wchar_t ord)
{
unsigned int nw;
if ((nw = bp->nwide) < NWIDE)
bp->wide[nw] = ord;
else
{
if (nw % NWIDE == 0 && (bp->exwide =
realloc(bp->exwide, nw * sizeof(wchar_t))) == 0)
{
return BKT_ESPACE;
}
nw -= NWIDE;
bp->exwide[nw] = ord;
}
bp->nwide++;
return 0;
}
#if USHRT_MAX == 65535 /* have 16 bits */
#define PLIND(n) ((n) >> 4)
#define PLBIT(n) (1 << ((n) & 0xf))
#else
#define PLIND(n) ((n) / CHAR_BIT)
#define PLBIT(n) (1 << ((n) % CHAR_BIT))
#endif
#define RANGE ((wchar_t)'-') /* separates wide chars in ranges */
static int
addrange(Bracket *bp, wchar_t ord, w_type prev)
{
int ret;
if (prev > 0 && prev != ord) /* try for range */
{
if (prev > ord)
{
if (bp->flags & BKT_ODDRANGE) /* prev only - done */
return 0;
else if ((bp->flags & BKT_BADRANGE) == 0)
return BKT_ERANGE;
}
else
{
if (++prev <= UCHAR_MAX) /* "prev" already there */
{
do
{
bp->byte[PLIND(prev)] |= PLBIT(prev);
if (prev == ord)
return 0;
} while (++prev <= UCHAR_MAX);
}
if ((ret = addwide(bp, prev)) != 0)
return ret;
if (++prev > ord)
return 0;
if (prev < ord && (ret = addwide(bp, RANGE)) != 0)
return ret;
return addwide(bp, ord);
}
}
if (ord <= UCHAR_MAX)
{
bp->byte[PLIND(ord)] |= PLBIT(ord);
return 0;
}
if (prev == ord) /* don't bother */
return 0;
return addwide(bp, ord);
}
static w_type
place(Bracket *bp, wchar_t wc, w_type prev, int mb_cur_max)
{
const CollElem *cep;
CollElem spare;
int ret;
if ((cep = libuxre_collelem(bp->col, &spare, wc)) != ELEM_ENCODED)
{
if (cep == ELEM_BADCHAR)
return BKT_BADCHAR;
wc = cep->weight[0];
}
if ((ret = addrange(bp, wc, prev)) != 0)
return ret;
return wc;
}
#ifndef CHARCLASS_NAME_MAX
# define CHARCLASS_NAME_MAX 127
#endif
static w_type
chcls(Bracket *bp, const unsigned char *s, int n)
{
char clsstr[CHARCLASS_NAME_MAX + 1];
unsigned int nt;
wctype_t wct;
if (n > CHARCLASS_NAME_MAX)
return BKT_ECTYPE;
(void)memcpy(clsstr, s, n);
clsstr[n] = '\0';
if ((wct = wctype(clsstr)) == 0)
return BKT_ECTYPE;
if ((nt = bp->ntype) < NTYPE)
bp->type[nt] = wct;
else
{
if (nt % NTYPE == 0 && (bp->extype =
realloc(bp->extype, nt * sizeof(wctype_t))) == 0)
{
return BKT_ESPACE;
}
nt -= NTYPE;
bp->extype[nt] = wct;
}
bp->ntype++;
return 0; /* cannot be end point of a range */
}
/*
* The purpose of mcce() and its Mcce structure is to locate
* the next full collation element from "wc" and "s". It is
* called both at compile and execute time. These two differ
* primarily in that at compile time there is an exact number
* of bytes to be consumed, while at execute time the longest
* valid collation element is to be found.
*
* When BKT_ONECASE is set, MCCEs become particularly messy.
* There is no guarantee that all possible combinations of
* upper/lower case are defined as MCCEs. Thus, this code
* tries both lower- and uppercase (in that order) for each
* character than might be part of an MCCE.
*/
typedef struct
{
const unsigned char *max; /* restriction by caller */
const unsigned char *aft; /* longest successful */
Bracket *bp; /* readonly */
struct lc_collate *col; /* readonly */
const CollElem *cep; /* entry matching longest */
wchar_t ch; /* initial character (if any) */
w_type wc; /* character matching "aft" */
} Mcce;
static int
mcce(Mcce *mcp, const CollElem *cep, const unsigned char *s, int mb_cur_max,
int compile_time)
{
const CollElem *nxt;
CollElem spare;
w_type ch, wc;
int i;
/*
* Get next character.
*/
if ((wc = mcp->ch) != '\0')
{
mcp->ch = '\0';
}
else if (ISONEBYTE(wc = *s++))
{
if (wc == '\0')
return 0;
}
else if ((i = libuxre_mb2wc(&wc, s)) > 0)
{
s += i;
if (mcp->max != 0 && s > mcp->max)
return 0;
}
else if (i < 0)
return BKT_ILLSEQ;
/*
* Try out the this character as part of an MCCE.
* If BKT_ONECASE is set, this code tries both the lower- and
* uppercase version, continuing if it matches so far.
*/
ch = wc;
if (mcp->bp->flags & BKT_ONECASE)
{
if ((wc = to_lower(wc)) == ch)
ch = to_upper(wc);
}
for (;;) /* at most twice */
{
if (cep == ELEM_BADCHAR) /* first character */
{
if ((nxt = libuxre_collelem(mcp->col, &spare, wc))
== ELEM_ENCODED
|| (mcp->col->flags & CHF_MULTICH) == 0
|| s == mcp->max)
{
mcp->aft = s;
mcp->cep = nxt;
mcp->wc = wc;
break;
}
}
else
{
nxt = libuxre_collmult(mcp->col, cep, wc);
}
if (nxt != ELEM_BADCHAR)
{
/*
* Okay so far. Record this collating element
* if it's really one (not WGHT_IGNORE) and
* we've reached a new high point or it's the
* first match.
*
* If there's a possibility for more, call mcce()
* recursively for the subsequent characters.
*/
if (nxt->weight[0] != WGHT_IGNORE
&& (mcp->aft < s || mcp->cep == ELEM_BADCHAR))
{
mcp->aft = s;
mcp->cep = nxt;
mcp->wc = wc;
}
if (nxt->multbeg != 0
&& (mcp->max == 0 || s < mcp->max))
{
if ((i = mcce(mcp, nxt, s, mb_cur_max,
compile_time)) != 0)
return i;
}
}
if (wc == ch)
break;
wc = ch;
}
return 0;
}
static w_type
eqcls(Bracket *bp, const unsigned char *s, int n, w_type prev, int mb_cur_max)
{
w_type last;
Mcce mcbuf;
int err;
mcbuf.max = &s[n];
mcbuf.aft = &s[0];
mcbuf.bp = bp;
mcbuf.col = bp->col;
mcbuf.cep = ELEM_BADCHAR;
mcbuf.ch = '\0';
if ((err = mcce(&mcbuf, ELEM_BADCHAR, s, mb_cur_max, 1)) != 0)
return err;
if (mcbuf.cep == ELEM_BADCHAR || mcbuf.aft != mcbuf.max)
return BKT_EEQUIV;
last = mcbuf.wc;
if (mcbuf.cep != ELEM_ENCODED && mcbuf.col->nweight > 1)
{
const CollElem *cep;
/*
* The first and last weight[0] values for equivalence
* classes are stuffed into the terminator for the
* multiple character lists. If these values are
* scattered (elements that are not part of this
* equivalence class have weight[0] values between the
* two end points), then SUBN_SPECIAL is placed in
* this terminator. Note that weight[1] of the
* terminator must be other than WGHT_IGNORE, too.
*/
last = mcbuf.cep->weight[0];
if ((cep = libuxre_collmult(bp->col, mcbuf.cep, 0))
!= ELEM_BADCHAR
&& cep->weight[1] != WGHT_IGNORE)
{
last = cep->weight[1];
if (cep->subnbeg == SUBN_SPECIAL)
{
unsigned int nq;
/*
* Permit ranges up to the first and
* after the last.
*/
if (prev > 0 && prev != cep->weight[0]
&& (prev = addrange(bp,
cep->weight[0], prev)) != 0)
{
return prev;
}
/*
* Record the equivalence class by storing
* the primary weight.
*/
if ((nq = bp->nquiv) < NQUIV)
bp->quiv[nq] = mcbuf.cep->weight[1];
else
{
if (nq % NQUIV == 0 && (bp->exquiv =
realloc(bp->exquiv,
nq * sizeof(wuchar_type)))
== 0)
{
return REG_ESPACE;
}
nq -= NQUIV;
bp->exquiv[nq] = mcbuf.cep->weight[1];
}
bp->nquiv++;
return last;
}
mcbuf.cep = cep;
}
mcbuf.wc = mcbuf.cep->weight[0];
}
/*
* Determine range, if any, to install.
*
* If there's a pending low (prev > 0), then try to use it.
*
* Otherwise, try to use mcbuf.wc as the low end of the range.
* Since addrange() assumes that the low point has already been
* placed, we try to fool it by using a prev of one less than
* mcbuf.wc. But, if that value would not look like a valid
* low point of a range, we have to explicitly place mcbuf.wc.
*/
if (prev <= 0 && (prev = mcbuf.wc - 1) <= 0)
{
if ((prev = addrange(bp, mcbuf.wc, 0)) != 0)
return prev;
}
if ((mcbuf.wc = addrange(bp, last, prev)) != 0)
return mcbuf.wc;
return last;
}
static w_type
clsym(Bracket *bp, const unsigned char *s, int n, w_type prev, int mb_cur_max)
{
Mcce mcbuf;
int err;
mcbuf.max = &s[n];
mcbuf.aft = &s[0];
mcbuf.bp = bp;
mcbuf.col = bp->col;
mcbuf.cep = ELEM_BADCHAR;
mcbuf.ch = '\0';
if ((err = mcce(&mcbuf, ELEM_BADCHAR, s, mb_cur_max, 1)) != 0)
return err;
if (mcbuf.cep == ELEM_BADCHAR || mcbuf.aft != mcbuf.max)
return BKT_ECOLLATE;
if (mcbuf.cep != ELEM_ENCODED)
mcbuf.wc = mcbuf.cep->weight[0];
if ((err = addrange(bp, mcbuf.wc, prev)) != 0)
return err;
return mcbuf.wc;
}
/*
* Scans the rest of a bracket construction within a regular
* expression and fills in a description for it.
* The leading [ and the optional set complement indicator
* were handled already by the caller.
* Returns:
* <0 error (a BKT_* value)
* >0 success; equals how many bytes were scanned.
*/
LIBUXRE_STATIC int
libuxre_bktmbcomp(Bracket *bp, const unsigned char *pat0,
int flags, int mb_cur_max)
{
static const Bracket zero = {0};
const unsigned char *pat = pat0;
struct lc_collate *savecol;
w_type n, wc, prev = 0;
/*
* Set represented set to empty. Easiest to copy an empty
* version over the caller's, (re)setting col and flags.
*/
savecol = bp->col;
*bp = zero;
bp->col = savecol;
bp->flags = flags
& (BKT_NEGATED | BKT_ONECASE | BKT_NOTNL | BKT_BADRANGE |
BKT_ODDRANGE);
/*
* Handle optional "empty" brackets; typically only used
* in combination with BKT_QUOTE or BKT_ESCAPE.
*/
if ((wc = *pat) == ']' && (flags & BKT_EMPTY) != 0)
return 1;
/*
* Populate *bp.
*/
for (;; prev = n)
{
switch (wc)
{
case '\0':
ebrack:;
n = BKT_EBRACK;
goto err;
case '\n':
if (flags & BKT_NLBAD)
goto ebrack;
goto regular;
case '/':
if (flags & BKT_SLASHBAD)
goto ebrack;
goto regular;
case '\\':
if ((flags & (BKT_ESCAPE | BKT_QUOTE
| BKT_ESCNL | BKT_ESCSEQ)) == 0)
{
goto regular;
}
switch (wc = *++pat)
{
default:
noesc:;
if ((flags & BKT_ESCAPE) == 0)
{
wc = '\\';
pat--;
}
break;
case '\\':
case ']':
case '-':
case '^':
if ((flags & BKT_QUOTE) == 0)
goto noesc;
break;
case 'a':
if ((flags & BKT_ESCSEQ) == 0 ||
(flags & BKT_OLDESC))
goto noesc;
wc = '\a';
break;
case 'b':
if ((flags & BKT_ESCSEQ) == 0)
goto noesc;
wc = '\b';
break;
case 'f':
if ((flags & BKT_ESCSEQ) == 0)
goto noesc;
wc = '\f';
break;
case 'n':
if ((flags & (BKT_ESCSEQ | BKT_ESCNL)) == 0)
goto noesc;
wc = '\n';
break;
case 'r':
if ((flags & BKT_ESCSEQ) == 0)
goto noesc;
wc = '\r';
break;
case 't':
if ((flags & BKT_ESCSEQ) == 0)
goto noesc;
wc = '\t';
break;
case 'v':
if ((flags & BKT_ESCSEQ) == 0 ||
(flags & BKT_OLDESC))
goto noesc;
wc = '\v';
break;
case 'x':
if ((flags & BKT_ESCSEQ) == 0 ||
(flags & BKT_OLDESC))
goto noesc;
if (!isxdigit(wc = *++pat))
{
pat--;
goto noesc;
}
/*
* Take as many hex digits as possible,
* ignoring overflows.
* Any positive result is okay.
*/
n = 0;
do
{
if (isdigit(wc))
wc -= '0';
else if (isupper(wc))
wc -= 'A' + 10;
else
wc -= 'a' + 10;
n <<= 4;
n |= wc;
} while (isxdigit(wc = *++pat));
pat--;
if ((wc = n) <= 0)
{
n = BKT_BADESC;
goto err;
}
break;
case '0':
case '1':
case '2':
case '3':
case '4':
case '5':
case '6':
case '7':
case '8':
case '9':
if ((flags & BKT_ESCSEQ) == 0 ||
(flags & BKT_OLDESC))
goto noesc;
/*
* For compatibility (w/awk),
* permit "octal" 8 and 9.
*/
n = wc - '0';
if ((wc = *++pat) >= '0' && wc <= '9')
{
n <<= 3;
n += wc - '0';
if ((wc = *++pat) >= '0' && wc <= '9')
{
n <<= 3;
n += wc - '0';
}
}
pat--;
if ((wc = n) <= 0)
{
n = BKT_BADESC;
goto err;
}
break;
}
goto regular;
case '[':
if (((wc = *++pat) == ':' || wc == '=' || wc == '.') &&
(flags & BKT_NOI18N) == 0)
{
n = 0;
while (*++pat != wc || pat[1] != ']')
{
if (*pat == '\0')
{
badpat:;
n = BKT_BADPAT;
goto err;
}
else if (*pat == '/')
{
if (flags & BKT_SLASHBAD)
goto badpat;
}
else if (*pat == '\n')
{
if (flags & BKT_NLBAD)
goto badpat;
}
n++;
}
if (n == 0)
{
n = BKT_EMPTYSUBBKT;
goto err;
}
if (wc == ':')
n = chcls(bp, &pat[-n], n);
else if (wc == '=')
n = eqcls(bp, &pat[-n], n, prev,
mb_cur_max);
else /* wc == '.' */
n = clsym(bp, &pat[-n], n, prev,
mb_cur_max);
pat++;
break;
}
wc = '[';
pat--;
goto regular;
default:
if (!ISONEBYTE(wc) &&
(n = libuxre_mb2wc(&wc, pat + 1)) > 0)
pat += n;
regular:;
n = place(bp, wc, prev, mb_cur_max);
break;
}
if (n < 0) {
n = BKT_ILLSEQ;
goto err;
}
if ((wc = *++pat) == ']')
break;
if (wc == '-' && n != 0)
{
if (prev == 0 || (flags & BKT_SEPRANGE) == 0)
{
if ((wc = *++pat) != ']')
continue; /* valid range */
wc = '-';
pat--;
}
}
n = 0; /* no range this time */
}
return pat - pat0 + 1;
err:;
libuxre_bktfree(bp);
return n;
}
LIBUXRE_STATIC void
libuxre_bktfree(Bracket *bp)
{
if (bp->extype != 0)
free(bp->extype);
if (bp->exquiv != 0)
free(bp->exquiv);
if (bp->exwide != 0)
free(bp->exwide);
}
LIBUXRE_STATIC int
libuxre_bktmbexec(Bracket *bp, wchar_t wc,
const unsigned char *str, int mb_cur_max)
{
unsigned int i;
wchar_t lc, uc;
Mcce mcbuf;
mcbuf.aft = str; /* in case of match in character classes */
mcbuf.ch = wc;
/*
* First: check the single wc against any character classes.
* Since multiple character collating elements are not part
* of this world, they don't apply here.
*/
if ((i = bp->ntype) != 0)
{
wctype_t *wctp = &bp->type[0];
if (bp->flags & BKT_ONECASE)
{
if ((wc = to_lower(wc)) == mcbuf.ch)
mcbuf.ch = to_upper(wc);
}
for (;;)
{
if (iswctype(mb_cur_max==1?btowc(wc):wc, *wctp))
goto match;
if (wc != mcbuf.ch &&
iswctype(mb_cur_max==1?btowc(mcbuf.ch):mcbuf.ch,
*wctp))
goto match;
if (--i == 0)
break;
if (++wctp == &bp->type[NTYPE])
wctp = &bp->extype[0];
}
}
/*
* The main match is determined by the weight[0] value
* of the character (or characters, if the input can be
* taken as a multiple character collating element).
*/
mcbuf.max = 0;
mcbuf.bp = bp;
mcbuf.col = bp->col;
mcbuf.cep = ELEM_BADCHAR;
mcce(&mcbuf, ELEM_BADCHAR, str, mb_cur_max, 0);
if (mcbuf.cep == ELEM_BADCHAR)
return -1; /* never matches */
if (mcbuf.cep != ELEM_ENCODED)
mcbuf.wc = mcbuf.cep->weight[0];
/*
* POSIX.2 demands that both a character and its case counterpart
* can match if REG_ICASE is set. This means that [B-z] matches
* 'A', 'a', and '['.
*/
if (bp->flags & BKT_ONECASE)
{
lc = to_lower(mcbuf.wc);
uc = to_upper(mcbuf.wc);
}
else
lc = uc = mcbuf.wc;
/*
* See if it's in the set. Note that the list of true wide
* character values has explicit ranges.
*/
if (mcbuf.wc <= UCHAR_MAX)
{
if (bp->byte[PLIND(lc)] & PLBIT(lc))
goto match;
if (lc != uc && (bp->byte[PLIND(uc)] & PLBIT(uc)))
goto match;
}
else if ((i = bp->nwide) != 0)
{
wchar_t *wcp = &bp->wide[0];
long lcmp, ucmp;
for (;;)
{
if ((lcmp = lc - *wcp) == 0)
goto match;
ucmp = uc - *wcp;
if (lc != uc && ucmp == 0)
goto match;
if (--i == 0)
break;
if (++wcp == &bp->wide[NWIDE])
wcp = &bp->exwide[0];
if (*wcp == RANGE)
{
if (++wcp == &bp->wide[NWIDE])
wcp = &bp->exwide[0];
if (lcmp > 0 && lc <= *wcp)
goto match;
if (lc != uc && ucmp > 0 && uc < *wcp)
goto match;
if ((i -= 2) == 0)
break;
if (++wcp == &bp->wide[NWIDE])
wcp = &bp->exwide[0];
}
}
}
/*
* The last chance for a match is if an equivalence class
* was specified for which the primary weights are scattered
* through the weight[0]s.
*/
if ((i = bp->nquiv) != 0 && mcbuf.cep != ELEM_ENCODED)
{
wuchar_type *wucp = &bp->quiv[0];
mcbuf.wc = mcbuf.cep->weight[1];
for (;;)
{
if (mcbuf.wc == *wucp)
goto match;
if (--i == 0)
break;
if (++wucp == &bp->quiv[NQUIV])
wucp = &bp->exquiv[0];
}
}
/*
* Only here when no match against the set was found.
* One final special case w/r/t newline.
*/
if (bp->flags & BKT_NEGATED)
{
if (wc != '\n' || (bp->flags & BKT_NOTNL) == 0)
return mcbuf.aft - str;
}
return -1;
match:;
/*
* Only here when a match against the described set is found.
*/
if (bp->flags & BKT_NEGATED)
return -1;
return mcbuf.aft - str;
}
syntax highlighted by Code2HTML, v. 0.9.1