codekingpro/portable-devtools

1/*2 * Internal interface definitions, etc., for the reg package3 *4 * Copyright (c) 1998, 1999 Henry Spencer.  All rights reserved.5 *6 * Development of this software was funded, in part, by Cray Research Inc.,7 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics8 * Corporation, none of whom are responsible for the results.  The author9 * thanks all of them.10 *11 * Redistribution and use in source and binary forms -- with or without12 * modification -- are permitted for any purpose, provided that13 * redistributions in source form retain this entire copyright notice and14 * indicate the origin and nature of any modifications.15 *16 * I'd appreciate being given credit for this package in the documentation17 * of software which uses it, but that is not a requirement.18 *19 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,20 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY21 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL22 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;25 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,26 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR27 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF28 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.29 *30 * src/include/regex/regguts.h31 */32 33 34 35/*36 * Environmental customization.  It should not (I hope) be necessary to37 * alter the file you are now reading -- regcustom.h should handle it all,38 * given care here and elsewhere.39 */40#include "regcustom.h"41 42 43 44/*45 * Things that regcustom.h might override.46 */47 48/* assertions */49#ifndef assert50#ifndef REG_DEBUG51#define  NDEBUG					/* no assertions */52#endif53#include <assert.h>54#endif55 56/* voids */57#ifndef DISCARD58#define DISCARD void			/* for throwing values away */59#endif60#ifndef VS61#define VS(x)	((void *)(x))	/* cast something to generic ptr */62#endif63 64/* function-pointer declarator */65#ifndef FUNCPTR66#define FUNCPTR(name, args) (*(name)) args67#endif68 69/* memory allocation */70#ifndef MALLOC71#define MALLOC(n)	malloc(n)72#endif73#ifndef REALLOC74#define REALLOC(p, n)	realloc(VS(p), n)75#endif76#ifndef FREE77#define FREE(p)		free(VS(p))78#endif79 80/* interruption */81#ifndef INTERRUPT82#define INTERRUPT(re)83#endif84 85/* want size of a char in bits, and max value in bounded quantifiers */86#ifndef _POSIX2_RE_DUP_MAX87#define _POSIX2_RE_DUP_MAX	255 /* normally from <limits.h> */88#endif89 90 91 92/*93 * misc94 */95 96#define NOTREACHED	097 98#define DUPMAX	_POSIX2_RE_DUP_MAX99#define DUPINF	(DUPMAX+1)100 101#define REMAGIC 0xfed7			/* magic number for main struct */102 103/* Type codes for lookaround constraints */104#define LATYPE_AHEAD_POS	03	/* positive lookahead */105#define LATYPE_AHEAD_NEG	02	/* negative lookahead */106#define LATYPE_BEHIND_POS	01	/* positive lookbehind */107#define LATYPE_BEHIND_NEG	00	/* negative lookbehind */108#define LATYPE_IS_POS(la)	((la) & 01)109#define LATYPE_IS_AHEAD(la) ((la) & 02)110 111 112/*113 * debugging facilities114 */115#ifdef REG_DEBUG116/* FDEBUG does finite-state tracing */117#define FDEBUG(arglist) { if (v->eflags&REG_FTRACE) printf arglist; }118/* MDEBUG does higher-level tracing */119#define MDEBUG(arglist) { if (v->eflags&REG_MTRACE) printf arglist; }120#else121#define FDEBUG(arglist) {}122#define MDEBUG(arglist) {}123#endif124 125 126 127/*128 * bitmap manipulation129 */130#define UBITS	(CHAR_BIT * sizeof(unsigned))131#define BSET(uv, sn)	((uv)[(sn)/UBITS] |= (unsigned)1 << ((sn)%UBITS))132#define ISBSET(uv, sn)	((uv)[(sn)/UBITS] & ((unsigned)1 << ((sn)%UBITS)))133 134 135/*136 * known character classes137 */138enum char_classes139{140	CC_ALNUM, CC_ALPHA, CC_ASCII, CC_BLANK, CC_CNTRL, CC_DIGIT, CC_GRAPH,141	CC_LOWER, CC_PRINT, CC_PUNCT, CC_SPACE, CC_UPPER, CC_XDIGIT, CC_WORD142};143 144#define NUM_CCLASSES 14145 146 147/*148 * As soon as possible, we map chrs into equivalence classes -- "colors" --149 * which are of much more manageable number.150 *151 * To further reduce the number of arcs in NFAs and DFAs, we also have a152 * special RAINBOW "color" that can be assigned to an arc.  This is not a153 * real color, in that it has no entry in color maps.154 */155typedef short color;			/* colors of characters */156 157#define MAX_COLOR	32767		/* max color (must fit in 'color' datatype) */158#define COLORLESS	(-1)		/* impossible color */159#define RAINBOW		(-2)		/* represents all colors except pseudocolors */160#define WHITE		0			/* default color, parent of all others */161/* Note: various places in the code know that WHITE is zero */162 163 164/*165 * Per-color data structure for the compile-time color machinery166 *167 * If "sub" is not NOSUB then it is the number of the color's current168 * subcolor, i.e. we are in process of dividing this color (character169 * equivalence class) into two colors.  See src/backend/regex/README for170 * discussion of subcolors.171 *172 * Currently-unused colors have the FREECOL bit set and are linked into a173 * freelist using their "sub" fields, but only if their color numbers are174 * less than colormap.max.  Any array entries beyond "max" are just garbage.175 */176struct colordesc177{178	int			nschrs;			/* number of simple chars of this color */179	int			nuchrs;			/* number of upper map entries of this color */180	color		sub;			/* open subcolor, if any; or free-chain ptr */181#define  NOSUB	 COLORLESS		/* value of "sub" when no open subcolor */182	struct arc *arcs;			/* chain of all arcs of this color */183	chr			firstchr;		/* simple char first assigned to this color */184	int			flags;			/* bitmask of the following flags: */185#define  FREECOL 01				/* currently free */186#define  PSEUDO  02				/* pseudocolor, no real chars */187#define  COLMARK 04				/* temporary marker used in some functions */188};189 190#define  UNUSEDCOLOR(cd) ((cd)->flags & FREECOL)191 192/*193 * The color map itself194 *195 * This struct holds both data used only at compile time, and the chr to196 * color mapping information, used at both compile and run time.  The latter197 * is the bulk of the space, so it's not really worth separating out the198 * compile-only portion.199 *200 * Ideally, the mapping data would just be an array of colors indexed by201 * chr codes; but for large character sets that's impractical.  Fortunately,202 * common characters have smaller codes, so we can use a simple array for chr203 * codes up to MAX_SIMPLE_CHR, and do something more complex for codes above204 * that, without much loss of performance.  The "something more complex" is a205 * 2-D array of color entries, where row indexes correspond to individual chrs206 * or chr ranges that have been mentioned in the regex (with row zero207 * representing all other chrs), and column indexes correspond to different208 * sets of locale-dependent character classes such as "isalpha".  The209 * classbits[k] entry is zero if we do not care about the k'th character class210 * in this regex, and otherwise it is the bit to be OR'd into the column index211 * if the character in question is a member of that class.  We find the color212 * of a high-valued chr by identifying which colormaprange it is in to get213 * the row index (use row zero if it's in none of them), identifying which of214 * the interesting cclasses it's in to get the column index, and then indexing215 * into the 2-D hicolormap array.216 *217 * The colormapranges are required to be nonempty, nonoverlapping, and to218 * appear in increasing chr-value order.219 */220 221typedef struct colormaprange222{223	chr			cmin;			/* range represents cmin..cmax inclusive */224	chr			cmax;225	int			rownum;			/* row index in hicolormap array (>= 1) */226} colormaprange;227 228struct colormap229{230	int			magic;231#define  CMMAGIC 0x876232	struct vars *v;				/* for compile error reporting */233	size_t		ncds;			/* allocated length of colordescs array */234	size_t		max;			/* highest color number currently in use */235	color		free;			/* beginning of free chain (if non-0) */236	struct colordesc *cd;		/* pointer to array of colordescs */237#define  CDEND(cm)	 (&(cm)->cd[(cm)->max + 1])238 239	/* mapping data for chrs <= MAX_SIMPLE_CHR: */240	color	   *locolormap;		/* simple array indexed by chr code */241 242	/* mapping data for chrs > MAX_SIMPLE_CHR: */243	int			classbits[NUM_CCLASSES];	/* see comment above */244	int			numcmranges;	/* number of colormapranges */245	colormaprange *cmranges;	/* ranges of high chrs */246	color	   *hicolormap;		/* 2-D array of color entries */247	int			maxarrayrows;	/* number of array rows allocated */248	int			hiarrayrows;	/* number of array rows in use */249	int			hiarraycols;	/* number of array columns (2^N) */250 251	/* If we need up to NINLINECDS, we store them here to save a malloc */252#define  NINLINECDS  ((size_t) 10)253	struct colordesc cdspace[NINLINECDS];254};255 256/* fetch color for chr; beware of multiple evaluation of c argument */257#define GETCOLOR(cm, c) \258	((c) <= MAX_SIMPLE_CHR ? (cm)->locolormap[(c) - CHR_MIN] : pg_reg_getcolor(cm, c))259 260 261/*262 * Interface definitions for locale-interface functions in regc_locale.c.263 */264 265/*266 * Representation of a set of characters.  chrs[] represents individual267 * code points, ranges[] represents ranges in the form min..max inclusive.268 *269 * If the cvec represents a locale-specific character class, eg [[:alpha:]],270 * then the chrs[] and ranges[] arrays contain only members of that class271 * up to MAX_SIMPLE_CHR (inclusive).  cclasscode is set to regc_locale.c's272 * code for the class, rather than being -1 as it is in an ordinary cvec.273 *274 * Note that in cvecs gotten from newcvec() and intended to be freed by275 * freecvec(), both arrays of chrs are after the end of the struct, not276 * separately malloc'd; so chrspace and rangespace are effectively immutable.277 */278struct cvec279{280	int			nchrs;			/* number of chrs */281	int			chrspace;		/* number of chrs allocated in chrs[] */282	chr		   *chrs;			/* pointer to vector of chrs */283	int			nranges;		/* number of ranges (chr pairs) */284	int			rangespace;		/* number of ranges allocated in ranges[] */285	chr		   *ranges;			/* pointer to vector of chr pairs */286	int			cclasscode;		/* value of "enum classes", or -1 */287};288 289 290/*291 * definitions for NFA internal representation292 */293struct state;294 295struct arc296{297	int			type;			/* 0 if free, else an NFA arc type code */298	color		co;				/* color the arc matches (possibly RAINBOW) */299	struct state *from;			/* where it's from */300	struct state *to;			/* where it's to */301	struct arc *outchain;		/* link in *from's outs chain or free chain */302	struct arc *outchainRev;	/* back-link in *from's outs chain */303#define  freechain	outchain	/* we do not maintain "freechainRev" */304	struct arc *inchain;		/* link in *to's ins chain */305	struct arc *inchainRev;		/* back-link in *to's ins chain */306	/* these fields are not used when co == RAINBOW: */307	struct arc *colorchain;		/* link in color's arc chain */308	struct arc *colorchainRev;	/* back-link in color's arc chain */309};310 311struct arcbatch312{								/* for bulk allocation of arcs */313	struct arcbatch *next;		/* chain link */314	size_t		narcs;			/* number of arcs allocated in this arcbatch */315	struct arc	a[FLEXIBLE_ARRAY_MEMBER];316};317#define  ARCBATCHSIZE(n)  ((n) * sizeof(struct arc) + offsetof(struct arcbatch, a))318/* first batch will have FIRSTABSIZE arcs; then double it until MAXABSIZE */319#define  FIRSTABSIZE	64320#define  MAXABSIZE		1024321 322struct state323{324	int			no;				/* state number, zero and up; or FREESTATE */325#define  FREESTATE	 (-1)326	char		flag;			/* marks special states */327	int			nins;			/* number of inarcs */328	int			nouts;			/* number of outarcs */329	struct arc *ins;			/* chain of inarcs */330	struct arc *outs;			/* chain of outarcs */331	struct state *tmp;			/* temporary for traversal algorithms */332	struct state *next;			/* chain for traversing all live states */333	/* the "next" field is also used to chain free states together */334	struct state *prev;			/* back-link in chain of all live states */335};336 337struct statebatch338{								/* for bulk allocation of states */339	struct statebatch *next;	/* chain link */340	size_t		nstates;		/* number of states allocated in this batch */341	struct state s[FLEXIBLE_ARRAY_MEMBER];342};343#define  STATEBATCHSIZE(n)  ((n) * sizeof(struct state) + offsetof(struct statebatch, s))344/* first batch will have FIRSTSBSIZE states; then double it until MAXSBSIZE */345#define  FIRSTSBSIZE	32346#define  MAXSBSIZE		1024347 348struct nfa349{350	struct state *pre;			/* pre-initial state */351	struct state *init;			/* initial state */352	struct state *final;		/* final state */353	struct state *post;			/* post-final state */354	int			nstates;		/* for numbering states */355	struct state *states;		/* chain of live states */356	struct state *slast;		/* tail of the chain */357	struct state *freestates;	/* chain of free states */358	struct arc *freearcs;		/* chain of free arcs */359	struct statebatch *lastsb;	/* chain of statebatches */360	struct arcbatch *lastab;	/* chain of arcbatches */361	size_t		lastsbused;		/* number of states consumed from *lastsb */362	size_t		lastabused;		/* number of arcs consumed from *lastab */363	struct colormap *cm;		/* the color map */364	color		bos[2];			/* colors, if any, assigned to BOS and BOL */365	color		eos[2];			/* colors, if any, assigned to EOS and EOL */366	int			flags;			/* flags to pass forward to cNFA */367	int			minmatchall;	/* min number of chrs to match, if matchall */368	int			maxmatchall;	/* max number of chrs to match, or DUPINF */369	struct vars *v;				/* simplifies compile error reporting */370	struct nfa *parent;			/* parent NFA, if any */371};372 373 374 375/*376 * definitions for compacted NFA377 *378 * The main space savings in a compacted NFA is from making the arcs as small379 * as possible.  We store only the transition color and next-state number for380 * each arc.  The list of out arcs for each state is an array beginning at381 * cnfa.states[statenumber], and terminated by a dummy carc struct with382 * co == COLORLESS.383 *384 * The non-dummy carc structs are of two types: plain arcs and LACON arcs.385 * Plain arcs just store the transition color number as "co".  LACON arcs386 * store the lookaround constraint number plus cnfa.ncolors as "co".  LACON387 * arcs can be distinguished from plain by testing for co >= cnfa.ncolors.388 *389 * Note that in a plain arc, "co" can be RAINBOW; since that's negative,390 * it doesn't break the rule about how to recognize LACON arcs.391 *392 * We have special markings for "trivial" NFAs that can match any string393 * (possibly with limits on the number of characters therein).  In such a394 * case, flags & MATCHALL is set (and HASLACONS can't be set).  Then the395 * fields minmatchall and maxmatchall give the minimum and maximum numbers396 * of characters to match.  For example, ".*" produces minmatchall = 0397 * and maxmatchall = DUPINF, while ".+" produces minmatchall = 1 and398 * maxmatchall = DUPINF.399 */400struct carc401{402	color		co;				/* COLORLESS is list terminator */403	int			to;				/* next-state number */404};405 406struct cnfa407{408	int			nstates;		/* number of states */409	int			ncolors;		/* number of colors (max color in use + 1) */410	int			flags;			/* bitmask of the following flags: */411#define  HASLACONS	01			/* uses lookaround constraints */412#define  MATCHALL	02			/* matches all strings of a range of lengths */413	int			pre;			/* setup state number */414	int			post;			/* teardown state number */415	color		bos[2];			/* colors, if any, assigned to BOS and BOL */416	color		eos[2];			/* colors, if any, assigned to EOS and EOL */417	char	   *stflags;		/* vector of per-state flags bytes */418#define  CNFA_NOPROGRESS	01	/* flag bit for a no-progress state */419	struct carc **states;		/* vector of pointers to outarc lists */420	/* states[n] are pointers into a single malloc'd array of arcs */421	struct carc *arcs;			/* the area for the lists */422	/* these fields are used only in a MATCHALL NFA (else they're -1): */423	int			minmatchall;	/* min number of chrs to match */424	int			maxmatchall;	/* max number of chrs to match, or DUPINF */425};426 427/*428 * When debugging, it's helpful if an un-filled CNFA is all-zeroes.429 * In production, though, we only require nstates to be zero.430 */431#ifdef REG_DEBUG432#define ZAPCNFA(cnfa)	memset(&(cnfa), 0, sizeof(cnfa))433#else434#define ZAPCNFA(cnfa)	((cnfa).nstates = 0)435#endif436#define NULLCNFA(cnfa)	((cnfa).nstates == 0)437 438/*439 * This symbol limits the transient heap space used by the regex compiler,440 * and thereby also the maximum complexity of NFAs that we'll deal with.441 * Currently we only count NFA states and arcs against this; the other442 * transient data is generally not large enough to notice compared to those.443 * Note that we do not charge anything for the final output data structures444 * (the compacted NFA and the colormap).445 * The scaling here is based on an empirical measurement that very large446 * NFAs tend to have about 4 arcs/state.447 */448#ifndef REG_MAX_COMPILE_SPACE449#define REG_MAX_COMPILE_SPACE  \450	(500000 * (sizeof(struct state) + 4 * sizeof(struct arc)))451#endif452 453/*454 * subexpression tree455 *456 * "op" is one of:457 *		'='  plain regex without interesting substructure (implemented as DFA)458 *		'b'  back-reference (has no substructure either)459 *		'('  no-op capture node: captures the match of its single child460 *		'.'  concatenation: matches a match for first child, then second child461 *		'|'  alternation: matches a match for any of its children462 *		'*'  iteration: matches some number of matches of its single child463 *464 * An alternation node can have any number of children (but at least two),465 * linked through their sibling fields.466 *467 * A concatenation node must have exactly two children.  It might be useful468 * to support more, but that would complicate the executor.  Note that it is469 * the first child's greediness that determines the node's preference for470 * where to split a match.471 *472 * Note: when a backref is directly quantified, we stick the min/max counts473 * into the backref rather than plastering an iteration node on top.  This is474 * for efficiency: there is no need to search for possible division points.475 */476struct subre477{478	char		op;				/* see type codes above */479	char		flags;480#define  LONGER  01				/* prefers longer match */481#define  SHORTER 02				/* prefers shorter match */482#define  MIXED	 04				/* mixed preference below */483#define  CAP	 010			/* capturing parens here or below */484#define  BACKR	 020			/* back reference here or below */485#define  BRUSE	 040			/* is referenced by a back reference */486#define  INUSE	 0100			/* in use in final tree */487#define  UPPROP  (MIXED|CAP|BACKR)	/* flags which should propagate up */488#define  LMIX(f) ((f)<<2)		/* LONGER -> MIXED */489#define  SMIX(f) ((f)<<1)		/* SHORTER -> MIXED */490#define  UP(f)	 (((f)&UPPROP) | (LMIX(f) & SMIX(f) & MIXED))491#define  MESSY(f)	 ((f)&(MIXED|CAP|BACKR))492#define  PREF(f)	 ((f)&(LONGER|SHORTER))493#define  PREF2(f1, f2)	 ((PREF(f1) != 0) ? PREF(f1) : PREF(f2))494#define  COMBINE(f1, f2) (UP((f1)|(f2)) | PREF2(f1, f2))495	char		latype;			/* LATYPE code, if lookaround constraint */496	int			id;				/* ID of subre (1..ntree-1) */497	int			capno;			/* if capture node, subno to capture into */498	int			backno;			/* if backref node, subno it refers to */499	short		min;			/* min repetitions for iteration or backref */500	short		max;			/* max repetitions for iteration or backref */501	struct subre *child;		/* first child, if any (also freelist chain) */502	struct subre *sibling;		/* next child of same parent, if any */503	struct state *begin;		/* outarcs from here... */504	struct state *end;			/* ...ending in inarcs here */505	struct cnfa cnfa;			/* compacted NFA, if any */506	struct subre *chain;		/* for bookkeeping and error cleanup */507};508 509 510 511/*512 * table of function pointers for generic manipulation functions513 * A regex_t's re_fns points to one of these.514 */515struct fns516{517	void		FUNCPTR(free, (regex_t *));518	int			FUNCPTR(stack_too_deep, (void));519};520 521#define STACK_TOO_DEEP(re)	\522	((*((struct fns *) (re)->re_fns)->stack_too_deep) ())523 524 525/*526 * the insides of a regex_t, hidden behind a void *527 */528struct guts529{530	int			magic;531#define  GUTSMAGIC	 0xfed9532	int			cflags;			/* copy of compile flags */533	long		info;			/* copy of re_info */534	size_t		nsub;			/* copy of re_nsub */535	struct subre *tree;536	struct cnfa search;			/* for fast preliminary search */537	int			ntree;			/* number of subre's, plus one */538	struct colormap cmap;539	int			FUNCPTR(compare, (const chr *, const chr *, size_t));540	struct subre *lacons;		/* lookaround-constraint vector */541	int			nlacons;		/* size of lacons[]; note that only slots542								 * numbered 1 .. nlacons-1 are used */543};544 545 546/* prototypes for functions that are exported from regcomp.c to regexec.c */547extern void pg_set_regex_collation(Oid collation);548extern color pg_reg_getcolor(struct colormap *cm, chr c);549