src/common/rexpr.c

#ifndef lint
static const char       RCSid[] = "$Id$";
#endif
/*
 * Regular expression parsing routines.
 *
 * External symbols declared in standard.h
 */

/* ====================================================================
 * The Radiance Software License, Version 1.0
 *
 * Copyright (c) 1990 - 2002 The Regents of the University of California,
 * through Lawrence Berkeley National Laboratory.   All rights reserved.
 *
 * 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. The end-user documentation included with the redistribution,
 *           if any, must include the following acknowledgment:
 *             "This product includes Radiance software
 *                 (http://radsite.lbl.gov/)
 *                 developed by the Lawrence Berkeley National Laboratory
 *               (http://www.lbl.gov/)."
 *       Alternately, this acknowledgment may appear in the software itself,
 *       if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Radiance," "Lawrence Berkeley National Laboratory"
 *       and "The Regents of the University of California" must
 *       not be used to endorse or promote products derived from this
 *       software without prior written permission. For written
 *       permission, please contact [email protected].
 *
 * 5. Products derived from this software may not be called "Radiance",
 *       nor may "Radiance" appear in their name, without prior written
 *       permission of Lawrence Berkeley National Laboratory.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED 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 Lawrence Berkeley National Laboratory OR
 * ITS 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.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of Lawrence Berkeley National Laboratory.   For more
 * information on Lawrence Berkeley National Laboratory, please see
 * <http://www.lbl.gov/>.
 */

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
/*
 * rexpr.c - regular expression parser (ala grep)
 */

#define CCHR    2
#define CDOT    4
#define CCL     6
#define NCCL    8
#define CDOL    10
#define CEOF    11
#define CBRC    14
#define CLET    15
#define STAR    01

#define ESIZE   255

#define same(a,b) (a==b || (iflag && (a^b)==' ' && isalpha(a)))

#ifdef  BSD
#define  memcpy(to,from,len)    bcopy(from,to,len)
#endif

static int     advance(), cclass();

static char    expbuf[ESIZE];
static int     iflag;
static int     circf;

int     explen;                 /* length of the last expression found */

int
ecompile(sp, iflg, wflag)               /* compile the expression */
register char  *sp;
int iflg, wflag;
{
        register c;
        register char *ep;
        char *lastep;
        int cclcnt;
        
        iflag = iflg;
        ep = expbuf;
        explen = 0;
        if (*sp == '^') {
                circf = 1;
                sp++;
        } else
                circf = 0;
        if (wflag)
                *ep++ = CBRC;
        for (;;) {
                if (ep >= &expbuf[ESIZE])
                        return(-1);
                if ((c = *sp++) != '*')
                        lastep = ep;
                switch (c) {

                case '\0':
                        if (wflag)
                                *ep++ = CLET;
                        *ep++ = CEOF;
                        explen = ep - expbuf;
                        return(0);

                case '.':
                        *ep++ = CDOT;
                        continue;

                case '*':
                        if (lastep==0)
                                goto defchar;
                        *lastep |= STAR;
                        continue;

                case '$':
                        if (*sp != '\0')
                                goto defchar;
                        *ep++ = CDOL;
                        continue;

                case '[':
                        *ep++ = CCL;
                        *ep++ = 0;
                        cclcnt = 1;
                        if ((c = *sp++) == '^') {
                                c = *sp++;
                                ep[-2] = NCCL;
                        }
                        do {
                                *ep++ = c;
                                cclcnt++;
                                if (c=='\0' || ep >= &expbuf[ESIZE])
                                        return(-1);
                        } while ((c = *sp++) != ']');
                        lastep[1] = cclcnt;
                        continue;

                case '\\':
                        if ((c = *sp++) == '\0')
                                return(-1);
                        if (c == '<') {
                                if (ep == expbuf || ep[-1] != CBRC)
                                        *ep++ = CBRC;
                                continue;
                        }
                        if (c == '>') {
                                *ep++ = CLET;
                                continue;
                        }
                defchar:
                default:
                        *ep++ = CCHR;
                        *ep++ = c;
                }
        }
}

char *
expsave()                     /* save compiled string */
{
        register char  *ep;

        if (explen == 0)
                return(NULL);
        if ((ep = (char *)malloc(explen+3)) == NULL)
                return(NULL);
        ep[0] = iflag;
        ep[1] = circf;
        ep[2] = explen;
        (void)memcpy(ep+3, expbuf, explen);
        return(ep);
}

void
expset(ep)                      /* install saved string */
register char  *ep;
{
        iflag = ep[0];
        circf = ep[1];
        (void)memcpy(expbuf, ep+3, ep[2]&0xff);
}

char *
eindex(sp)                    /* find the expression in string sp */
register char *sp;
{
        /* check for match at beginning of line, watch CBRC */
        if (advance(sp, expbuf[0]==CBRC ? expbuf+1 : expbuf))
                return(sp);
        if (circf)
                return(NULL);
        /* fast check for first character */
        if (expbuf[0]==CCHR) {
                register c = expbuf[1];
                while (*++sp)
                        if (same(*sp, c) && advance(sp, expbuf))
                                return(sp);
                return(NULL);
        }
        /* regular algorithm */
        while (*++sp)
                if (advance(sp, expbuf))
                        return(sp);
        return(NULL);
}

static int
advance(alp, ep)
        char *alp;
register char *ep;
{
        register char *lp;
        char *curlp;

        lp = alp;
        for (;;) switch (*ep++) {

        case CCHR:
                if (!same(*ep, *lp))
                        return (0);
                ep++, lp++;
                continue;

        case CDOT:
                if (*lp++)
                        continue;
                return(0);

        case CDOL:
                if (*lp==0)
                        continue;
                return(0);

        case CEOF:
                explen = lp - alp;
                return(1);

        case CCL:
                if (cclass(ep, *lp++, 1)) {
                        ep += *ep;
                        continue;
                }
                return(0);

        case NCCL:
                if (cclass(ep, *lp++, 0)) {
                        ep += *ep;
                        continue;
                }
                return(0);

        case CDOT|STAR:
                curlp = lp;
                while (*lp++);
                goto star;

        case CCHR|STAR:
                curlp = lp;
                while (same(*lp, *ep))
                        lp++;
                lp++;
                ep++;
                goto star;

        case CCL|STAR:
        case NCCL|STAR:
                curlp = lp;
                while (cclass(ep, *lp++, ep[-1]==(CCL|STAR)));
                ep += *ep;
        star:
                do {
                        lp--;
                        if (advance(lp, ep)) {
                                explen += lp - alp;
                                return(1);
                        }
                } while (lp > curlp);
                return(0);

        case CBRC:
                if ((isalnum(*lp) || *lp == '_') && !(isalnum(lp[-1]) || lp[-1] == '_'))
                        continue;
                return (0);

        case CLET:
                if (!isalnum(*lp) && *lp != '_')
                        continue;
                return (0);

        default:
                fprintf(stderr, "RE botch\n");
        }
}

static int
cclass(set, c, af)
register char *set;
register c;
int af;
{
        register n;

        if (c == 0)
                return(0);
        n = *set++;
        while (--n)
                if (n > 2 && set[1] == '-') {
                        if (c >= set[0] && c <= set[2])
                                return (af);
                        set += 3;
                        n -= 2;
                } else
                        if (*set++ == c)
                                return(af);
        return(!af);
}
Revision:	2.4
Committed:	Sat Feb 22 02:07:22 2003 UTC (21 years, 2 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 2.3:	+66 -5 lines
Log Message:	Changes and check-in for 3.5 release Includes new source files and modifications not recorded for many years See ray/doc/notes/ReleaseNotes for notes between 3.1 and 3.5 release
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	greg	2.4	static const char RCSid[] = "$Id$";
3	greg	1.1	#endif
4	greg	2.4	/*
5			* Regular expression parsing routines.
6			*
7			* External symbols declared in standard.h
8			*/
9
10			/* ====================================================================
11			* The Radiance Software License, Version 1.0
12			*
13			* Copyright (c) 1990 - 2002 The Regents of the University of California,
14			* through Lawrence Berkeley National Laboratory. All rights reserved.
15			*
16			* Redistribution and use in source and binary forms, with or without
17			* modification, are permitted provided that the following conditions
18			* are met:
19			*
20			* 1. Redistributions of source code must retain the above copyright
21			* notice, this list of conditions and the following disclaimer.
22			*
23			* 2. Redistributions in binary form must reproduce the above copyright
24			* notice, this list of conditions and the following disclaimer in
25			* the documentation and/or other materials provided with the
26			* distribution.
27			*
28			* 3. The end-user documentation included with the redistribution,
29			* if any, must include the following acknowledgment:
30			* "This product includes Radiance software
31			* (http://radsite.lbl.gov/)
32			* developed by the Lawrence Berkeley National Laboratory
33			* (http://www.lbl.gov/)."
34			* Alternately, this acknowledgment may appear in the software itself,
35			* if and wherever such third-party acknowledgments normally appear.
36			*
37			* 4. The names "Radiance," "Lawrence Berkeley National Laboratory"
38			* and "The Regents of the University of California" must
39			* not be used to endorse or promote products derived from this
40			* software without prior written permission. For written
41			* permission, please contact [email protected].
42			*
43			* 5. Products derived from this software may not be called "Radiance",
44			* nor may "Radiance" appear in their name, without prior written
45			* permission of Lawrence Berkeley National Laboratory.
46			*
47			* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
48			* WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
49			* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
50			* DISCLAIMED. IN NO EVENT SHALL Lawrence Berkeley National Laboratory OR
51			* ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
52			* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
53			* LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
54			* USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
55			* ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
56			* OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
57			* OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
58			* SUCH DAMAGE.
59			* ====================================================================
60			*
61			* This software consists of voluntary contributions made by many
62			* individuals on behalf of Lawrence Berkeley National Laboratory. For more
63			* information on Lawrence Berkeley National Laboratory, please see
64			* <http://www.lbl.gov/>.
65			*/
66	greg	1.1
67			#include <stdio.h>
68	greg	2.4	#include <stdlib.h>
69	greg	1.1	#include <ctype.h>
70			/*
71			* rexpr.c - regular expression parser (ala grep)
72			*/
73
74			#define CCHR 2
75			#define CDOT 4
76			#define CCL 6
77			#define NCCL 8
78			#define CDOL 10
79			#define CEOF 11
80			#define CBRC 14
81			#define CLET 15
82			#define STAR 01
83
84			#define ESIZE 255
85
86			#define same(a,b) (a==b \|\| (iflag && (a^b)==' ' && isalpha(a)))
87
88	greg	1.2	#ifdef BSD
89			#define memcpy(to,from,len) bcopy(from,to,len)
90			#endif
91
92	greg	1.4	static int advance(), cclass();
93
94	greg	1.1	static char expbuf[ESIZE];
95			static int iflag;
96			static int circf;
97
98			int explen; /* length of the last expression found */
99
100			int
101			ecompile(sp, iflg, wflag) /* compile the expression */
102			register char *sp;
103			int iflg, wflag;
104			{
105			register c;
106			register char *ep;
107			char *lastep;
108			int cclcnt;
109
110			iflag = iflg;
111			ep = expbuf;
112			explen = 0;
113			if (*sp == '^') {
114			circf = 1;
115			sp++;
116			} else
117			circf = 0;
118			if (wflag)
119			*ep++ = CBRC;
120			for (;;) {
121			if (ep >= &expbuf[ESIZE])
122			return(-1);
123			if ((c = sp++) != '')
124			lastep = ep;
125			switch (c) {
126
127			case '\0':
128			if (wflag)
129			*ep++ = CLET;
130			*ep++ = CEOF;
131			explen = ep - expbuf;
132			return(0);
133
134			case '.':
135			*ep++ = CDOT;
136			continue;
137
138			case '*':
139			if (lastep==0)
140			goto defchar;
141			*lastep \|= STAR;
142			continue;
143
144			case '$':
145			if (*sp != '\0')
146			goto defchar;
147			*ep++ = CDOL;
148			continue;
149
150			case '[':
151			*ep++ = CCL;
152			*ep++ = 0;
153			cclcnt = 1;
154			if ((c = *sp++) == '^') {
155			c = *sp++;
156			ep[-2] = NCCL;
157			}
158			do {
159			*ep++ = c;
160			cclcnt++;
161			if (c=='\0' \|\| ep >= &expbuf[ESIZE])
162			return(-1);
163			} while ((c = *sp++) != ']');
164			lastep[1] = cclcnt;
165			continue;
166
167			case '\\':
168			if ((c = *sp++) == '\0')
169			return(-1);
170			if (c == '<') {
171	greg	2.2	if (ep == expbuf \|\| ep[-1] != CBRC)
172			*ep++ = CBRC;
173	greg	1.1	continue;
174			}
175			if (c == '>') {
176			*ep++ = CLET;
177			continue;
178			}
179			defchar:
180			default:
181			*ep++ = CCHR;
182			*ep++ = c;
183			}
184			}
185			}
186
187			char *
188			expsave() /* save compiled string */
189			{
190			register char *ep;
191
192			if (explen == 0)
193			return(NULL);
194	greg	2.4	if ((ep = (char *)malloc(explen+3)) == NULL)
195	greg	1.1	return(NULL);
196			ep[0] = iflag;
197			ep[1] = circf;
198			ep[2] = explen;
199			(void)memcpy(ep+3, expbuf, explen);
200			return(ep);
201			}
202
203	greg	2.4	void
204	greg	1.1	expset(ep) /* install saved string */
205			register char *ep;
206			{
207			iflag = ep[0];
208			circf = ep[1];
209			(void)memcpy(expbuf, ep+3, ep[2]&0xff);
210			}
211
212			char *
213	greg	2.2	eindex(sp) /* find the expression in string sp */
214	greg	1.1	register char *sp;
215			{
216	greg	2.2	/* check for match at beginning of line, watch CBRC */
217			if (advance(sp, expbuf[0]==CBRC ? expbuf+1 : expbuf))
218			return(sp);
219			if (circf)
220	greg	1.1	return(NULL);
221			/* fast check for first character */
222			if (expbuf[0]==CCHR) {
223			register c = expbuf[1];
224	greg	2.2	while (*++sp)
225	greg	1.1	if (same(*sp, c) && advance(sp, expbuf))
226			return(sp);
227			return(NULL);
228			}
229			/* regular algorithm */
230	greg	2.2	while (*++sp)
231	greg	1.1	if (advance(sp, expbuf))
232			return(sp);
233			return(NULL);
234			}
235
236			static int
237			advance(alp, ep)
238			char *alp;
239			register char *ep;
240			{
241			register char *lp;
242			char *curlp;
243
244			lp = alp;
245			for (;;) switch (*ep++) {
246
247			case CCHR:
248			if (!same(ep, lp))
249			return (0);
250			ep++, lp++;
251			continue;
252
253			case CDOT:
254			if (*lp++)
255			continue;
256			return(0);
257
258			case CDOL:
259			if (*lp==0)
260			continue;
261			return(0);
262
263			case CEOF:
264			explen = lp - alp;
265			return(1);
266
267			case CCL:
268			if (cclass(ep, *lp++, 1)) {
269			ep += *ep;
270			continue;
271			}
272			return(0);
273
274			case NCCL:
275			if (cclass(ep, *lp++, 0)) {
276			ep += *ep;
277			continue;
278			}
279			return(0);
280
281			case CDOT\|STAR:
282			curlp = lp;
283			while (*lp++);
284			goto star;
285
286			case CCHR\|STAR:
287			curlp = lp;
288			while (same(lp, ep))
289			lp++;
290			lp++;
291			ep++;
292			goto star;
293
294			case CCL\|STAR:
295			case NCCL\|STAR:
296			curlp = lp;
297			while (cclass(ep, *lp++, ep[-1]==(CCL\|STAR)));
298			ep += *ep;
299			star:
300			do {
301			lp--;
302			if (advance(lp, ep)) {
303			explen += lp - alp;
304			return(1);
305			}
306			} while (lp > curlp);
307			return(0);
308
309			case CBRC:
310			if ((isalnum(lp) \|\| lp == '_') && !(isalnum(lp[-1]) \|\| lp[-1] == '_'))
311			continue;
312			return (0);
313
314			case CLET:
315			if (!isalnum(lp) && lp != '_')
316			continue;
317			return (0);
318
319			default:
320			fprintf(stderr, "RE botch\n");
321			}
322			}
323
324			static int
325			cclass(set, c, af)
326			register char *set;
327			register c;
328	greg	2.3	int af;
329	greg	1.1	{
330			register n;
331
332			if (c == 0)
333			return(0);
334			n = *set++;
335			while (--n)
336			if (n > 2 && set[1] == '-') {
337			if (c >= set[0] && c <= set[2])
338			return (af);
339			set += 3;
340			n -= 2;
341			} else
342			if (*set++ == c)
343			return(af);
344			return(!af);
345			}