[p5sagit/p5-mst-13.2.git] / regcomp.h

/* $RCSfile: regcomp.h,v $$Revision: 4.1 $$Date: 92/08/07 18:26:31 $
 *
 * $Log:	regcomp.h,v $
 * Revision 4.1  92/08/07  18:26:31  lwall
 * 
 * Revision 4.0.1.1  91/06/07  11:49:40  lwall
 * patch4: no change
 * 
 * Revision 4.0  91/03/20  01:39:09  lwall
 * 4.0 baseline.
 * 
 */

/*
 * 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	sv that must begin a match; Nullch if none obvious
 * reganch	is the match anchored (at beginning-of-line only)?
 * regmust	string (pointer into program) that match must include, or NULL
 *  [regmust changed to SV* for bminstr()--law]
 * regmlen	length of regmust string
 *  [regmlen not used currently]
 *
 * 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.
 * [regmust is now supplied always.  The tests that use regmust have a
 * heuristic that disables the test if it usually matches.]
 *
 * [In fact, we now use regmust in many cases to locate where the search
 * starts in the string, so if regback is >= 0, the regmust search is never
 * wasted effort.  The regback variable says how many characters back from
 * where regmust matched is the earliest possible start of the match.
 * For instance, /[a-z].foo/ has a regmust of 'foo' and a regback of 2.]
 */

/*
 * 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 "next" pointer, possibly plus an operand.  "Next" pointers of
 * all nodes except BRANCH implement concatenation; a "next" 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	/* sv	Match character in (or not in) this class. */
#define	CURLY	5	/* sv	Match this simple thing {n,m} times. */
#define	BRANCH	6	/* node	Match this alternative, or the next... */
#define	BACK	7	/* no	Match "", "next" ptr points backward. */
#define	EXACTLY	8	/* sv	Match this string (preceded by length). */
#define	NOTHING	9	/* no	Match empty string. */
#define	STAR	10	/* node	Match this (simple) thing 0 or more times. */
#define	PLUS	11	/* node	Match this (simple) thing 1 or more times. */
#define ALNUM	12	/* no	Match any alphanumeric character */
#define NALNUM	13	/* no	Match any non-alphanumeric character */
#define BOUND	14	/* no	Match "" at any word boundary */
#define NBOUND	15	/* no	Match "" at any word non-boundary */
#define SPACE	16	/* no	Match any whitespace character */
#define NSPACE	17	/* no	Match any non-whitespace character */
#define DIGIT	18	/* no	Match any numeric character */
#define NDIGIT	19	/* no	Match any non-numeric character */
#define REF	20	/* num	Match some already matched string */
#define	OPEN	21	/* num	Mark this point in input as start of #n. */
#define	CLOSE	22	/* num	Analogous to OPEN. */

/*
 * Opcode notes:
 *
 * BRANCH	The set of branches constituting a single choice are hooked
 *		together with their "next" pointers, since precedence prevents
 *		anything being concatenated to any individual branch.  The
 *		"next" pointer of the last BRANCH in a choice points to the
 *		thing following the whole choice.  This is also where the
 *		final "next" pointer of each individual branch points; each
 *		branch starts with the operand node of a BRANCH node.
 *
 * BACK		Normal "next" pointers all implicitly point forward; BACK
 *		exists to make loop structures possible.
 *
 * STAR,PLUS	'?', and complex '*' and '+', are implemented as circular
 *		BRANCH structures using BACK.  Simple cases (one character
 *		per match) are implemented with STAR and PLUS for speed
 *		and to minimize recursive plunges.
 *
 * OPEN,CLOSE	...are numbered at compile time.
 */

#ifndef DOINIT
extern char regarglen[];
#else
char regarglen[] = {0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2};
#endif

/* The following have no fixed length. */
#ifndef DOINIT
extern char varies[];
#else
char varies[] = {BRANCH,BACK,STAR,PLUS,CURLY,REF,0};
#endif

/* The following always have a length of 1. */
#ifndef DOINIT
extern char simple[];
#else
char simple[] = {ANY,ANYOF,ALNUM,NALNUM,SPACE,NSPACE,DIGIT,NDIGIT,0};
#endif

EXT char regdummy;

/*
 * A node is one char of opcode followed by two chars of "next" pointer.
 * "Next" 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 "next" pointer is vast overkill for most things,
 * but allows patterns to get big without disasters.
 *
 * [If REGALIGN is defined, the "next" pointer is always aligned on an even
 * boundary, and reads the offset directly as a short.  Also, there is no
 * special test to reverse the sign of BACK pointers since the offset is
 * stored negative.]
 */

#ifndef gould
#ifndef cray
#ifndef eta10
#define REGALIGN
#endif
#endif
#endif

#define	OP(p)	(*(p))

#ifndef lint
#ifdef REGALIGN
#define NEXT(p) (*(short*)(p+1))
#define ARG1(p) (*(unsigned short*)(p+3))
#define ARG2(p) (*(unsigned short*)(p+5))
#else
#define	NEXT(p)	(((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
#define	ARG1(p)	(((*((p)+3)&0377)<<8) + (*((p)+4)&0377))
#define	ARG2(p)	(((*((p)+5)&0377)<<8) + (*((p)+6)&0377))
#endif
#else /* lint */
#define NEXT(p) 0
#endif /* lint */

#define	OPERAND(p)	((p) + 3)

#ifdef REGALIGN
#define	NEXTOPER(p)	((p) + 4)
#else
#define	NEXTOPER(p)	((p) + 3)
#endif

#define MAGIC 0234

/*
 * Utility definitions.
 */
#ifndef lint
#ifndef CHARMASK
#define	UCHARAT(p)	((int)*(unsigned char *)(p))
#else
#define	UCHARAT(p)	((int)*(p)&CHARMASK)
#endif
#else /* lint */
#define UCHARAT(p)	regdummy
#endif /* lint */

#define	FAIL(m)	croak("/%s/: %s",regprecomp,m)
Commit	Line	Data
79072805	1	/* $RCSfile: regcomp.h,v $$Revision: 4.1 $$Date: 92/08/07 18:26:31 $
a687059c	2	*
a687059c	3	* $Log: regcomp.h,v $
79072805	4	* Revision 4.1 92/08/07 18:26:31 lwall
79072805	5	*
9ef589d8	6	* Revision 4.0.1.1 91/06/07 11:49:40 lwall
	7	* patch4: no change
	8	*
fe14fcc3	9	* Revision 4.0 91/03/20 01:39:09 lwall
fe14fcc3	10	* 4.0 baseline.
a687059c	11	*
	12	*/
	13
	14	/*
	15	* The "internal use only" fields in regexp.h are present to pass info from
	16	* compile to execute that permits the execute phase to run lots faster on
	17	* simple cases. They are:
	18	*
79072805	19	* regstart sv that must begin a match; Nullch if none obvious
a687059c	20	* reganch is the match anchored (at beginning-of-line only)?
a687059c	21	* regmust string (pointer into program) that match must include, or NULL
79072805	22	* [regmust changed to SV* for bminstr()--law]
a687059c	23	* regmlen length of regmust string
	24	* [regmlen not used currently]
	25	*
	26	* Regstart and reganch permit very fast decisions on suitable starting points
	27	* for a match, cutting down the work a lot. Regmust permits fast rejection
	28	* of lines that cannot possibly match. The regmust tests are costly enough
	29	* that regcomp() supplies a regmust only if the r.e. contains something
	30	* potentially expensive (at present, the only such thing detected is * or +
	31	* at the start of the r.e., which can involve a lot of backup). Regmlen is
	32	* supplied because the test in regexec() needs it and regcomp() is computing
	33	* it anyway.
	34	* [regmust is now supplied always. The tests that use regmust have a
	35	* heuristic that disables the test if it usually matches.]
	36	*
	37	* [In fact, we now use regmust in many cases to locate where the search
	38	* starts in the string, so if regback is >= 0, the regmust search is never
	39	* wasted effort. The regback variable says how many characters back from
	40	* where regmust matched is the earliest possible start of the match.
	41	* For instance, /[a-z].foo/ has a regmust of 'foo' and a regback of 2.]
	42	*/
	43
	44	/*
	45	* Structure for regexp "program". This is essentially a linear encoding
	46	* of a nondeterministic finite-state machine (aka syntax charts or
	47	* "railroad normal form" in parsing technology). Each node is an opcode
	48	* plus a "next" pointer, possibly plus an operand. "Next" pointers of
	49	* all nodes except BRANCH implement concatenation; a "next" pointer with
	50	* a BRANCH on both ends of it is connecting two alternatives. (Here we
	51	* have one of the subtle syntax dependencies: an individual BRANCH (as
	52	* opposed to a collection of them) is never concatenated with anything
	53	* because of operator precedence.) The operand of some types of node is
	54	* a literal string; for others, it is a node leading into a sub-FSM. In
	55	* particular, the operand of a BRANCH node is the first node of the branch.
	56	* (NB this is not a tree structure: the tail of the branch connects
	57	* to the thing following the set of BRANCHes.) The opcodes are:
	58	*/
	59
	60	/* definition number opnd? meaning */
	61	#define END 0 /* no End of program. */
	62	#define BOL 1 /* no Match "" at beginning of line. */
	63	#define EOL 2 /* no Match "" at end of line. */
	64	#define ANY 3 /* no Match any one character. */
79072805	65	#define ANYOF 4 /* sv Match character in (or not in) this class. */
79072805	66	#define CURLY 5 /* sv Match this simple thing {n,m} times. */
a687059c	67	#define BRANCH 6 /* node Match this alternative, or the next... */
a687059c	68	#define BACK 7 /* no Match "", "next" ptr points backward. */
79072805	69	#define EXACTLY 8 /* sv Match this string (preceded by length). */
a687059c	70	#define NOTHING 9 /* no Match empty string. */
	71	#define STAR 10 /* node Match this (simple) thing 0 or more times. */
	72	#define PLUS 11 /* node Match this (simple) thing 1 or more times. */
	73	#define ALNUM 12 /* no Match any alphanumeric character */
	74	#define NALNUM 13 /* no Match any non-alphanumeric character */
	75	#define BOUND 14 /* no Match "" at any word boundary */
	76	#define NBOUND 15 /* no Match "" at any word non-boundary */
	77	#define SPACE 16 /* no Match any whitespace character */
	78	#define NSPACE 17 /* no Match any non-whitespace character */
	79	#define DIGIT 18 /* no Match any numeric character */
	80	#define NDIGIT 19 /* no Match any non-numeric character */
fe14fcc3	81	#define REF 20 /* num Match some already matched string */
	82	#define OPEN 21 /* num Mark this point in input as start of #n. */
	83	#define CLOSE 22 /* num Analogous to OPEN. */
a687059c	84
	85	/*
	86	* Opcode notes:
	87	*
	88	* BRANCH The set of branches constituting a single choice are hooked
	89	* together with their "next" pointers, since precedence prevents
	90	* anything being concatenated to any individual branch. The
	91	* "next" pointer of the last BRANCH in a choice points to the
	92	* thing following the whole choice. This is also where the
	93	* final "next" pointer of each individual branch points; each
	94	* branch starts with the operand node of a BRANCH node.
	95	*
	96	* BACK Normal "next" pointers all implicitly point forward; BACK
	97	* exists to make loop structures possible.
	98	*
	99	* STAR,PLUS '?', and complex '*' and '+', are implemented as circular
	100	* BRANCH structures using BACK. Simple cases (one character
	101	* per match) are implemented with STAR and PLUS for speed
	102	* and to minimize recursive plunges.
	103	*
	104	* OPEN,CLOSE ...are numbered at compile time.
	105	*/
	106
fe14fcc3	107	#ifndef DOINIT
	108	extern char regarglen[];
	109	#else
	110	char regarglen[] = {0,0,0,0,0,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2};
	111	#endif
	112
a687059c	113	/* The following have no fixed length. */
	114	#ifndef DOINIT
	115	extern char varies[];
	116	#else
fe14fcc3	117	char varies[] = {BRANCH,BACK,STAR,PLUS,CURLY,REF,0};
a687059c	118	#endif
	119
	120	/* The following always have a length of 1. */
	121	#ifndef DOINIT
	122	extern char simple[];
	123	#else
00bf170e	124	char simple[] = {ANY,ANYOF,ALNUM,NALNUM,SPACE,NSPACE,DIGIT,NDIGIT,0};
a687059c	125	#endif
	126
	127	EXT char regdummy;
	128
	129	/*
	130	* A node is one char of opcode followed by two chars of "next" pointer.
	131	* "Next" pointers are stored as two 8-bit pieces, high order first. The
	132	* value is a positive offset from the opcode of the node containing it.
	133	* An operand, if any, simply follows the node. (Note that much of the
	134	* code generation knows about this implicit relationship.)
	135	*
	136	* Using two bytes for the "next" pointer is vast overkill for most things,
	137	* but allows patterns to get big without disasters.
	138	*
	139	* [If REGALIGN is defined, the "next" pointer is always aligned on an even
	140	* boundary, and reads the offset directly as a short. Also, there is no
	141	* special test to reverse the sign of BACK pointers since the offset is
	142	* stored negative.]
	143	*/
	144
	145	#ifndef gould
	146	#ifndef cray
34de22dd	147	#ifndef eta10
a687059c	148	#define REGALIGN
	149	#endif
	150	#endif
34de22dd	151	#endif
a687059c	152
	153	#define OP(p) (*(p))
	154
	155	#ifndef lint
	156	#ifdef REGALIGN
	157	#define NEXT(p) ((short)(p+1))
00bf170e	158	#define ARG1(p) ((unsigned short)(p+3))
00bf170e	159	#define ARG2(p) ((unsigned short)(p+5))
a687059c	160	#else
a687059c	161	#define NEXT(p) (((((p)+1)&0377)<<8) + (((p)+2)&0377))
00bf170e	162	#define ARG1(p) (((((p)+3)&0377)<<8) + (((p)+4)&0377))
00bf170e	163	#define ARG2(p) (((((p)+5)&0377)<<8) + (((p)+6)&0377))
a687059c	164	#endif
	165	#else /* lint */
	166	#define NEXT(p) 0
	167	#endif /* lint */
	168
	169	#define OPERAND(p) ((p) + 3)
	170
	171	#ifdef REGALIGN
	172	#define NEXTOPER(p) ((p) + 4)
	173	#else
	174	#define NEXTOPER(p) ((p) + 3)
	175	#endif
	176
	177	#define MAGIC 0234
	178
	179	/*
	180	* Utility definitions.
	181	*/
	182	#ifndef lint
2304df62	183	#ifndef CHARMASK
a687059c	184	#define UCHARAT(p) ((int)(unsigned char )(p))
a687059c	185	#else
2304df62	186	#define UCHARAT(p) ((int)*(p)&CHARMASK)
a687059c	187	#endif
	188	#else /* lint */
	189	#define UCHARAT(p) regdummy
	190	#endif /* lint */
	191
463ee0b2	192	#define FAIL(m) croak("/%s/: %s",regprecomp,m)