[apple/libc.git] / regex / regex2.h

/*-
 * Copyright (c) 1992, 1993, 1994 Henry Spencer.
 * Copyright (c) 1992, 1993, 1994
 *	The Regents of the University of California.  All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Henry Spencer.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	@(#)regex2.h	8.4 (Berkeley) 3/20/94
 * $FreeBSD: src/lib/libc/regex/regex2.h,v 1.8 2004/07/12 07:35:59 tjr Exp $
 */

/*
 * First, the stuff that ends up in the outside-world include file
 = typedef off_t regoff_t;
 = typedef struct {
 = 	int re_magic;
 = 	size_t re_nsub;		// number of parenthesized subexpressions
 = 	const char *re_endp;	// end pointer for REG_PEND
 = 	struct re_guts *re_g;	// none of your business :-)
 = } regex_t;
 = typedef struct {
 = 	regoff_t rm_so;		// start of match
 = 	regoff_t rm_eo;		// end of match
 = } regmatch_t;
 */
/*
 * internals of regex_t
 */
#define	MAGIC1	((('r'^0200)<<8) | 'e')

/*
 * The internal representation is a *strip*, a sequence of
 * operators ending with an endmarker.  (Some terminology etc. is a
 * historical relic of earlier versions which used multiple strips.)
 * Certain oddities in the representation are there to permit running
 * the machinery backwards; in particular, any deviation from sequential
 * flow must be marked at both its source and its destination.  Some
 * fine points:
 *
 * - OPLUS_ and O_PLUS are *inside* the loop they create.
 * - OQUEST_ and O_QUEST are *outside* the bypass they create.
 * - OCH_ and O_CH are *outside* the multi-way branch they create, while
 *   OOR1 and OOR2 are respectively the end and the beginning of one of
 *   the branches.  Note that there is an implicit OOR2 following OCH_
 *   and an implicit OOR1 preceding O_CH.
 *
 * In state representations, an operator's bit is on to signify a state
 * immediately *preceding* "execution" of that operator.
 */
typedef unsigned long sop;	/* strip operator */
typedef long sopno;
#define	OPRMASK	0xf8000000L
#define	OPDMASK	0x07ffffffL
#define	OPSHIFT	((unsigned)27)
#define	OP(n)	((n)&OPRMASK)
#define	OPND(n)	((n)&OPDMASK)
#define	SOP(op, opnd)	((op)|(opnd))
/* operators			   meaning	operand			*/
/*						(back, fwd are offsets)	*/
#define	OEND	(1L<<OPSHIFT)	/* endmarker	-			*/
#define	OCHAR	(2L<<OPSHIFT)	/* character	wide character		*/
#define	OBOL	(3L<<OPSHIFT)	/* left anchor	-			*/
#define	OEOL	(4L<<OPSHIFT)	/* right anchor	-			*/
#define	OANY	(5L<<OPSHIFT)	/* .		-			*/
#define	OANYOF	(6L<<OPSHIFT)	/* [...]	set number		*/
#define	OBACK_	(7L<<OPSHIFT)	/* begin \d	paren number		*/
#define	O_BACK	(8L<<OPSHIFT)	/* end \d	paren number		*/
#define	OPLUS_	(9L<<OPSHIFT)	/* + prefix	fwd to suffix		*/
#define	O_PLUS	(10L<<OPSHIFT)	/* + suffix	back to prefix		*/
#define	OQUEST_	(11L<<OPSHIFT)	/* ? prefix	fwd to suffix		*/
#define	O_QUEST	(12L<<OPSHIFT)	/* ? suffix	back to prefix		*/
#define	OLPAREN	(13L<<OPSHIFT)	/* (		fwd to )		*/
#define	ORPAREN	(14L<<OPSHIFT)	/* )		back to (		*/
#define	OCH_	(15L<<OPSHIFT)	/* begin choice	fwd to OOR2		*/
#define	OOR1	(16L<<OPSHIFT)	/* | pt. 1	back to OOR1 or OCH_	*/
#define	OOR2	(17L<<OPSHIFT)	/* | pt. 2	fwd to OOR2 or O_CH	*/
#define	O_CH	(18L<<OPSHIFT)	/* end choice	back to OOR1		*/
#define	OBOW	(19L<<OPSHIFT)	/* begin word	-			*/
#define	OEOW	(20L<<OPSHIFT)	/* end word	-			*/

/*
 * Structures for [] character-set representation.
 */
typedef struct {
	wint_t		min;
	wint_t		max;
} crange;
typedef struct {
	unsigned char	bmp[NC / 8];
	wctype_t	*types;
	int		ntypes;
	wint_t		*wides;
	int		nwides;
	crange		*ranges;
	int		nranges;
	int		invert;
	int		icase;
	int		*equiv_classes;
	int		nequiv_classes;
} cset;

#include "collate.h"

static int
CHIN1(cs, ch, loc)
cset *cs;
wint_t ch;
locale_t loc;
{
	int i;

	assert(ch >= 0);
	for (i = 0; i < cs->nequiv_classes; i++)
		/* sadly, we can only deal with single characters from an
		 * equivalence class */
		if (__collate_equiv_match(cs->equiv_classes[i], NULL, 0, ch, NULL, 0, NULL, NULL, loc) > 0)
			return (!cs->invert);
	if (ch < NC)
		return (((cs->bmp[ch >> 3] & (1 << (ch & 7))) != 0) ^
		    cs->invert);
	for (i = 0; i < cs->nwides; i++)
		if (ch == cs->wides[i])
			return (!cs->invert);
	for (i = 0; i < cs->nranges; i++)
		if (cs->ranges[i].min <= ch && ch <= cs->ranges[i].max)
			return (!cs->invert);
	for (i = 0; i < cs->ntypes; i++)
		if (iswctype_l(ch, cs->types[i], loc))
			return (!cs->invert);
	return (cs->invert);
}

static __inline int
CHIN(cs, ch, loc)
cset *cs;
wint_t ch;
locale_t loc;
{

	assert(ch >= 0);
	if (ch < NC && cs->nequiv_classes == 0)
		return (((cs->bmp[ch >> 3] & (1 << (ch & 7))) != 0) ^
		    cs->invert);
	else if (cs->icase)
		return (CHIN1(cs, ch, loc) || CHIN1(cs, towlower_l(ch, loc), loc) ||
		    CHIN1(cs, towupper_l(ch, loc), loc));
	else
		return (CHIN1(cs, ch, loc));
}

/*
 * main compiled-expression structure
 */
struct re_guts {
	int magic;
#		define	MAGIC2	((('R'^0200)<<8)|'E')
	sop *strip;		/* malloced area for strip */
	int ncsets;		/* number of csets in use */
	cset *sets;		/* -> cset [ncsets] */
	int cflags;		/* copy of regcomp() cflags argument */
	sopno nstates;		/* = number of sops */
	sopno firststate;	/* the initial OEND (normally 0) */
	sopno laststate;	/* the final OEND */
	int iflags;		/* internal flags */
#		define	USEBOL	01	/* used ^ */
#		define	USEEOL	02	/* used $ */
#		define	BAD	04	/* something wrong */
	int nbol;		/* number of ^ used */
	int neol;		/* number of $ used */
	char *must;		/* match must contain this string */
	int moffset;		/* latest point at which must may be located */
	int *charjump;		/* Boyer-Moore char jump table */
	int *matchjump;		/* Boyer-Moore match jump table */
	int mlen;		/* length of must */
	size_t nsub;		/* copy of re_nsub */
	int backrefs;		/* does it use back references? */
	sopno nplus;		/* how deep does it nest +s? */
	locale_t loc;		/* current locale */
};

/* misc utilities */
#define	OUT	(-130)	/* a non-character value */
#define ISWORD(c,l)     (iswalnum_l((uch)(c), l) || (c) == '_')
Commit	Line	Data
224c7076 A	1	/*-
	2	* Copyright (c) 1992, 1993, 1994 Henry Spencer.
	3	* Copyright (c) 1992, 1993, 1994
	4	* The Regents of the University of California. All rights reserved.
	5	*
	6	* This code is derived from software contributed to Berkeley by
	7	* Henry Spencer.
	8	*
	9	* Redistribution and use in source and binary forms, with or without
	10	* modification, are permitted provided that the following conditions
	11	* are met:
	12	* 1. Redistributions of source code must retain the above copyright
	13	* notice, this list of conditions and the following disclaimer.
	14	* 2. Redistributions in binary form must reproduce the above copyright
	15	* notice, this list of conditions and the following disclaimer in the
	16	* documentation and/or other materials provided with the distribution.
	17	* 3. All advertising materials mentioning features or use of this software
	18	* must display the following acknowledgement:
	19	* This product includes software developed by the University of
	20	* California, Berkeley and its contributors.
	21	* 4. Neither the name of the University nor the names of its contributors
	22	* may be used to endorse or promote products derived from this software
	23	* without specific prior written permission.
	24	*
	25	* THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
	26	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	27	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	28	* ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
	29	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	30	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	31	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	32	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	33	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	34	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	35	* SUCH DAMAGE.
	36	*
	37	* @(#)regex2.h 8.4 (Berkeley) 3/20/94
	38	* $FreeBSD: src/lib/libc/regex/regex2.h,v 1.8 2004/07/12 07:35:59 tjr Exp $
	39	*/
	40
	41	/*
	42	* First, the stuff that ends up in the outside-world include file
	43	= typedef off_t regoff_t;
	44	= typedef struct {
	45	= int re_magic;
	46	= size_t re_nsub; // number of parenthesized subexpressions
	47	= const char *re_endp; // end pointer for REG_PEND
	48	= struct re_guts *re_g; // none of your business :-)
	49	= } regex_t;
	50	= typedef struct {
	51	= regoff_t rm_so; // start of match
	52	= regoff_t rm_eo; // end of match
	53	= } regmatch_t;
	54	*/
	55	/*
	56	* internals of regex_t
	57	*/
	58	#define MAGIC1 ((('r'^0200)<<8) \| 'e')
	59
	60	/*
	61	* The internal representation is a strip, a sequence of
	62	* operators ending with an endmarker. (Some terminology etc. is a
	63	* historical relic of earlier versions which used multiple strips.)
	64	* Certain oddities in the representation are there to permit running
65	* the machinery backwards; in particular, any deviation from sequential
66	* flow must be marked at both its source and its destination. Some
67	* fine points:
68	*
69	* - OPLUS_ and O_PLUS are inside the loop they create.
70	* - OQUEST_ and O_QUEST are outside the bypass they create.
71	* - OCH_ and O_CH are outside the multi-way branch they create, while
72	* OOR1 and OOR2 are respectively the end and the beginning of one of
73	* the branches. Note that there is an implicit OOR2 following OCH_
74	* and an implicit OOR1 preceding O_CH.
75	*
76	* In state representations, an operator's bit is on to signify a state
77	* immediately preceding "execution" of that operator.
78	*/
79	typedef unsigned long sop; /* strip operator */
80	typedef long sopno;
81	#define OPRMASK 0xf8000000L
82	#define OPDMASK 0x07ffffffL
83	#define OPSHIFT ((unsigned)27)
84	#define OP(n) ((n)&OPRMASK)
85	#define OPND(n) ((n)&OPDMASK)
86	#define SOP(op, opnd) ((op)\|(opnd))
87	/* operators meaning operand */
88	/* (back, fwd are offsets) */
89	#define OEND (1L<<OPSHIFT) /* endmarker - */
90	#define OCHAR (2L<<OPSHIFT) /* character wide character */
91	#define OBOL (3L<<OPSHIFT) /* left anchor - */
92	#define OEOL (4L<<OPSHIFT) /* right anchor - */
93	#define OANY (5L<<OPSHIFT) /* . - */
94	#define OANYOF (6L<<OPSHIFT) /* [...] set number */
95	#define OBACK_ (7L<<OPSHIFT) /* begin \d paren number */
96	#define O_BACK (8L<<OPSHIFT) /* end \d paren number */
97	#define OPLUS_ (9L<<OPSHIFT) /* + prefix fwd to suffix */
98	#define O_PLUS (10L<<OPSHIFT) /* + suffix back to prefix */
99	#define OQUEST_ (11L<<OPSHIFT) /* ? prefix fwd to suffix */
100	#define O_QUEST (12L<<OPSHIFT) /* ? suffix back to prefix */
101	#define OLPAREN (13L<<OPSHIFT) /* ( fwd to ) */
102	#define ORPAREN (14L<<OPSHIFT) /* ) back to ( */
103	#define OCH_ (15L<<OPSHIFT) /* begin choice fwd to OOR2 */
104	#define OOR1 (16L<<OPSHIFT) /* \| pt. 1 back to OOR1 or OCH_ */
105	#define OOR2 (17L<<OPSHIFT) /* \| pt. 2 fwd to OOR2 or O_CH */
106	#define O_CH (18L<<OPSHIFT) /* end choice back to OOR1 */
107	#define OBOW (19L<<OPSHIFT) /* begin word - */
108	#define OEOW (20L<<OPSHIFT) /* end word - */
109
110	/*
111	* Structures for [] character-set representation.
112	*/
113	typedef struct {
114	wint_t min;
115	wint_t max;
116	} crange;
117	typedef struct {
118	unsigned char bmp[NC / 8];
119	wctype_t *types;
120	int ntypes;
121	wint_t *wides;
122	int nwides;
123	crange *ranges;
124	int nranges;
125	int invert;
126	int icase;
127	int *equiv_classes;
128	int nequiv_classes;
129	} cset;
130
131	#include "collate.h"
132
133	static int
134	CHIN1(cs, ch, loc)
135	cset *cs;
136	wint_t ch;
137	locale_t loc;
138	{
139	int i;
140
141	assert(ch >= 0);
142	for (i = 0; i < cs->nequiv_classes; i++)
143	/* sadly, we can only deal with single characters from an
144	* equivalence class */
145	if (__collate_equiv_match(cs->equiv_classes[i], NULL, 0, ch, NULL, 0, NULL, NULL, loc) > 0)
146	return (!cs->invert);
147	if (ch < NC)
148	return (((cs->bmp[ch >> 3] & (1 << (ch & 7))) != 0) ^
149	cs->invert);
150	for (i = 0; i < cs->nwides; i++)
151	if (ch == cs->wides[i])
152	return (!cs->invert);
153	for (i = 0; i < cs->nranges; i++)
154	if (cs->ranges[i].min <= ch && ch <= cs->ranges[i].max)
155	return (!cs->invert);
156	for (i = 0; i < cs->ntypes; i++)
157	if (iswctype_l(ch, cs->types[i], loc))
158	return (!cs->invert);
159	return (cs->invert);
160	}
161
162	static __inline int
163	CHIN(cs, ch, loc)
164	cset *cs;
165	wint_t ch;
166	locale_t loc;
167	{
168
169	assert(ch >= 0);
170	if (ch < NC && cs->nequiv_classes == 0)
171	return (((cs->bmp[ch >> 3] & (1 << (ch & 7))) != 0) ^
172	cs->invert);
173	else if (cs->icase)
174	return (CHIN1(cs, ch, loc) \|\| CHIN1(cs, towlower_l(ch, loc), loc) \|\|
175	CHIN1(cs, towupper_l(ch, loc), loc));
176	else
177	return (CHIN1(cs, ch, loc));
178	}
179
180	/*
181	* main compiled-expression structure
182	*/
183	struct re_guts {
184	int magic;
185	# define MAGIC2 ((('R'^0200)<<8)\|'E')
186	sop strip; / malloced area for strip */
187	int ncsets; /* number of csets in use */
188	cset sets; / -> cset [ncsets] */
189	int cflags; /* copy of regcomp() cflags argument */
190	sopno nstates; /* = number of sops */
191	sopno firststate; /* the initial OEND (normally 0) */
192	sopno laststate; /* the final OEND */
193	int iflags; /* internal flags */
194	# define USEBOL 01 /* used ^ */
195	# define USEEOL 02 /* used $ */
196	# define BAD 04 /* something wrong */
197	int nbol; /* number of ^ used */
198	int neol; /* number of $ used */
199	char must; / match must contain this string */
200	int moffset; /* latest point at which must may be located */
201	int charjump; / Boyer-Moore char jump table */
202	int matchjump; / Boyer-Moore match jump table */
203	int mlen; /* length of must */
204	size_t nsub; /* copy of re_nsub */
205	int backrefs; /* does it use back references? */
206	sopno nplus; /* how deep does it nest +s? */
207	locale_t loc; /* current locale */
208	};
209
210	/* misc utilities */
211	#define OUT (-130) /* a non-character value */
212	#define ISWORD(c,l) (iswalnum_l((uch)(c), l) \|\| (c) == '_')