src/common/rexpr.c

#ifndef lint
static const char       RCSid[] = "$Id: rexpr.c,v 2.8 2003/06/30 14:59:11 schorsch Exp $";
#endif
/*
 * Regular expression parsing routines.
 *
 * External symbols declared in standard.h
 */

#include "copyright.h"

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

#include "rtio.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)))


static int     advance(char *, char *);
static int     cclass(char *, int c, int af);

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 int c;
        register char *ep;
        char *lastep = NULL;
        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 int 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 int c;
int af;
{
        register int 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.9
Committed:	Thu Jul 17 09:21:29 2003 UTC (20 years, 9 months ago) by schorsch
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad5R2, rad4R2P2, rad5R0, rad5R1, rad3R7P2, rad3R7P1, rad4R2, rad4R1, rad4R0, rad3R6, rad3R6P1, rad3R8, rad3R9, rad4R2P1
Changes since 2.8:	+10 -7 lines
Log Message:	Added prototypes and includes from patch by Randolph Fritz. Added more required includes and reduced other compile warnings.
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	schorsch	2.9	static const char RCSid[] = "$Id: rexpr.c,v 2.8 2003/06/30 14:59:11 schorsch Exp $";
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	greg	2.5	#include "copyright.h"
11	greg	1.1
12			#include <stdio.h>
13	greg	2.4	#include <stdlib.h>
14	greg	1.1	#include <ctype.h>
15	schorsch	2.7	#include <string.h>
16
17	schorsch	2.9	#include "rtio.h"
18
19	greg	1.1	/*
20			* rexpr.c - regular expression parser (ala grep)
21			*/
22
23			#define CCHR 2
24			#define CDOT 4
25			#define CCL 6
26			#define NCCL 8
27			#define CDOL 10
28			#define CEOF 11
29			#define CBRC 14
30			#define CLET 15
31			#define STAR 01
32
33			#define ESIZE 255
34
35			#define same(a,b) (a==b \|\| (iflag && (a^b)==' ' && isalpha(a)))
36
37	greg	1.2
38	schorsch	2.9	static int advance(char , char );
39			static int cclass(char *, int c, int af);
40	greg	1.4
41	greg	1.1	static char expbuf[ESIZE];
42			static int iflag;
43			static int circf;
44
45			int explen; /* length of the last expression found */
46
47			int
48			ecompile(sp, iflg, wflag) /* compile the expression */
49			register char *sp;
50			int iflg, wflag;
51			{
52	schorsch	2.9	register int c;
53	greg	1.1	register char *ep;
54	schorsch	2.9	char *lastep = NULL;
55	greg	1.1	int cclcnt;
56
57			iflag = iflg;
58			ep = expbuf;
59			explen = 0;
60			if (*sp == '^') {
61			circf = 1;
62			sp++;
63			} else
64			circf = 0;
65			if (wflag)
66			*ep++ = CBRC;
67			for (;;) {
68			if (ep >= &expbuf[ESIZE])
69			return(-1);
70			if ((c = sp++) != '')
71			lastep = ep;
72			switch (c) {
73
74			case '\0':
75			if (wflag)
76			*ep++ = CLET;
77			*ep++ = CEOF;
78			explen = ep - expbuf;
79			return(0);
80
81			case '.':
82			*ep++ = CDOT;
83			continue;
84
85			case '*':
86			if (lastep==0)
87			goto defchar;
88			*lastep \|= STAR;
89			continue;
90
91			case '$':
92			if (*sp != '\0')
93			goto defchar;
94			*ep++ = CDOL;
95			continue;
96
97			case '[':
98			*ep++ = CCL;
99			*ep++ = 0;
100			cclcnt = 1;
101			if ((c = *sp++) == '^') {
102			c = *sp++;
103			ep[-2] = NCCL;
104			}
105			do {
106			*ep++ = c;
107			cclcnt++;
108			if (c=='\0' \|\| ep >= &expbuf[ESIZE])
109			return(-1);
110			} while ((c = *sp++) != ']');
111			lastep[1] = cclcnt;
112			continue;
113
114			case '\\':
115			if ((c = *sp++) == '\0')
116			return(-1);
117			if (c == '<') {
118	greg	2.2	if (ep == expbuf \|\| ep[-1] != CBRC)
119			*ep++ = CBRC;
120	greg	1.1	continue;
121			}
122			if (c == '>') {
123			*ep++ = CLET;
124			continue;
125			}
126			defchar:
127			default:
128			*ep++ = CCHR;
129			*ep++ = c;
130			}
131			}
132			}
133
134			char *
135			expsave() /* save compiled string */
136			{
137			register char *ep;
138
139			if (explen == 0)
140			return(NULL);
141	greg	2.4	if ((ep = (char *)malloc(explen+3)) == NULL)
142	greg	1.1	return(NULL);
143			ep[0] = iflag;
144			ep[1] = circf;
145			ep[2] = explen;
146			(void)memcpy(ep+3, expbuf, explen);
147			return(ep);
148			}
149
150	greg	2.4	void
151	greg	1.1	expset(ep) /* install saved string */
152			register char *ep;
153			{
154			iflag = ep[0];
155			circf = ep[1];
156			(void)memcpy(expbuf, ep+3, ep[2]&0xff);
157			}
158
159			char *
160	greg	2.2	eindex(sp) /* find the expression in string sp */
161	greg	1.1	register char *sp;
162			{
163	greg	2.2	/* check for match at beginning of line, watch CBRC */
164			if (advance(sp, expbuf[0]==CBRC ? expbuf+1 : expbuf))
165			return(sp);
166			if (circf)
167	greg	1.1	return(NULL);
168			/* fast check for first character */
169			if (expbuf[0]==CCHR) {
170	schorsch	2.9	register int c = expbuf[1];
171	greg	2.2	while (*++sp)
172	greg	1.1	if (same(*sp, c) && advance(sp, expbuf))
173			return(sp);
174			return(NULL);
175			}
176			/* regular algorithm */
177	greg	2.2	while (*++sp)
178	greg	1.1	if (advance(sp, expbuf))
179			return(sp);
180			return(NULL);
181			}
182
183			static int
184			advance(alp, ep)
185			char *alp;
186			register char *ep;
187			{
188			register char *lp;
189			char *curlp;
190
191			lp = alp;
192			for (;;) switch (*ep++) {
193
194			case CCHR:
195			if (!same(ep, lp))
196			return (0);
197			ep++, lp++;
198			continue;
199
200			case CDOT:
201			if (*lp++)
202			continue;
203			return(0);
204
205			case CDOL:
206			if (*lp==0)
207			continue;
208			return(0);
209
210			case CEOF:
211			explen = lp - alp;
212			return(1);
213
214			case CCL:
215			if (cclass(ep, *lp++, 1)) {
216			ep += *ep;
217			continue;
218			}
219			return(0);
220
221			case NCCL:
222			if (cclass(ep, *lp++, 0)) {
223			ep += *ep;
224			continue;
225			}
226			return(0);
227
228			case CDOT\|STAR:
229			curlp = lp;
230			while (*lp++);
231			goto star;
232
233			case CCHR\|STAR:
234			curlp = lp;
235			while (same(lp, ep))
236			lp++;
237			lp++;
238			ep++;
239			goto star;
240
241			case CCL\|STAR:
242			case NCCL\|STAR:
243			curlp = lp;
244			while (cclass(ep, *lp++, ep[-1]==(CCL\|STAR)));
245			ep += *ep;
246			star:
247			do {
248			lp--;
249			if (advance(lp, ep)) {
250			explen += lp - alp;
251			return(1);
252			}
253			} while (lp > curlp);
254			return(0);
255
256			case CBRC:
257			if ((isalnum(lp) \|\| lp == '_') && !(isalnum(lp[-1]) \|\| lp[-1] == '_'))
258			continue;
259			return (0);
260
261			case CLET:
262			if (!isalnum(lp) && lp != '_')
263			continue;
264			return (0);
265
266			default:
267			fprintf(stderr, "RE botch\n");
268			}
269			}
270
271			static int
272			cclass(set, c, af)
273			register char *set;
274	schorsch	2.9	register int c;
275	greg	2.3	int af;
276	greg	1.1	{
277	schorsch	2.9	register int n;
278	greg	1.1
279			if (c == 0)
280			return(0);
281			n = *set++;
282			while (--n)
283			if (n > 2 && set[1] == '-') {
284			if (c >= set[0] && c <= set[2])
285			return (af);
286			set += 3;
287			n -= 2;
288			} else
289			if (*set++ == c)
290			return(af);
291			return(!af);
292			}