1*3e12c5d1SDavid du Colombier #include <stdlib.h>
2*3e12c5d1SDavid du Colombier #include <stdio.h>
3*3e12c5d1SDavid du Colombier #include "regexp.h"
4*3e12c5d1SDavid du Colombier #include "regcomp.h"
5*3e12c5d1SDavid du Colombier
6*3e12c5d1SDavid du Colombier static Resublist sempty; /* empty set of matches */
7*3e12c5d1SDavid du Colombier
8*3e12c5d1SDavid du Colombier /*
9*3e12c5d1SDavid du Colombier * return 0 if no match
10*3e12c5d1SDavid du Colombier * >0 if a match
11*3e12c5d1SDavid du Colombier * <0 if we ran out of _relist space
12*3e12c5d1SDavid du Colombier */
13*3e12c5d1SDavid du Colombier static int
rregexec1(Reprog * progp,wchar_t * bol,Resub * mp,int ms,wchar_t * starts,wchar_t * eol,wchar_t startchar)14*3e12c5d1SDavid du Colombier rregexec1(Reprog *progp, /* program to run */
15*3e12c5d1SDavid du Colombier wchar_t *bol, /* string to run machine on */
16*3e12c5d1SDavid du Colombier Resub *mp, /* subexpression elements */
17*3e12c5d1SDavid du Colombier int ms, /* number of elements at mp */
18*3e12c5d1SDavid du Colombier wchar_t *starts,
19*3e12c5d1SDavid du Colombier wchar_t *eol,
20*3e12c5d1SDavid du Colombier wchar_t startchar)
21*3e12c5d1SDavid du Colombier {
22*3e12c5d1SDavid du Colombier int flag=0;
23*3e12c5d1SDavid du Colombier Reinst *inst;
24*3e12c5d1SDavid du Colombier Relist *tlp;
25*3e12c5d1SDavid du Colombier wchar_t *s;
26*3e12c5d1SDavid du Colombier int i, checkstart;
27*3e12c5d1SDavid du Colombier wchar_t r, *rp, *ep;
28*3e12c5d1SDavid du Colombier Relist* tl; /* This list, next list */
29*3e12c5d1SDavid du Colombier Relist* nl;
30*3e12c5d1SDavid du Colombier Relist* tle; /* ends of this and next list */
31*3e12c5d1SDavid du Colombier Relist* nle;
32*3e12c5d1SDavid du Colombier int match;
33*3e12c5d1SDavid du Colombier
34*3e12c5d1SDavid du Colombier match = 0;
35*3e12c5d1SDavid du Colombier checkstart = startchar;
36*3e12c5d1SDavid du Colombier sempty.m[0].s.rsp = 0;
37*3e12c5d1SDavid du Colombier if(mp!=0)
38*3e12c5d1SDavid du Colombier for(i=0; i<ms; i++)
39*3e12c5d1SDavid du Colombier mp[i].s.rsp = mp[i].e.rep = 0;
40*3e12c5d1SDavid du Colombier _relist[0][0].inst = _relist[1][0].inst = 0;
41*3e12c5d1SDavid du Colombier
42*3e12c5d1SDavid du Colombier /* Execute machine once for each character, including terminal NUL */
43*3e12c5d1SDavid du Colombier s = starts;
44*3e12c5d1SDavid du Colombier do{
45*3e12c5d1SDavid du Colombier r = *s;
46*3e12c5d1SDavid du Colombier
47*3e12c5d1SDavid du Colombier /* fast check for first char */
48*3e12c5d1SDavid du Colombier if(checkstart && r!=startchar){
49*3e12c5d1SDavid du Colombier s++;
50*3e12c5d1SDavid du Colombier continue;
51*3e12c5d1SDavid du Colombier }
52*3e12c5d1SDavid du Colombier
53*3e12c5d1SDavid du Colombier /* switch run lists */
54*3e12c5d1SDavid du Colombier tl = _relist[flag];
55*3e12c5d1SDavid du Colombier tle = _reliste[flag];
56*3e12c5d1SDavid du Colombier nl = _relist[flag^=1];
57*3e12c5d1SDavid du Colombier nle = _reliste[flag];
58*3e12c5d1SDavid du Colombier nl->inst = 0;
59*3e12c5d1SDavid du Colombier
60*3e12c5d1SDavid du Colombier /* Add first instruction to current list */
61*3e12c5d1SDavid du Colombier sempty.m[0].s.rsp = s;
62*3e12c5d1SDavid du Colombier _renewthread(tl, progp->startinst, &sempty);
63*3e12c5d1SDavid du Colombier
64*3e12c5d1SDavid du Colombier /* Execute machine until current list is empty */
65*3e12c5d1SDavid du Colombier for(tlp=tl; tlp->inst; tlp++){ /* assignment = */
66*3e12c5d1SDavid du Colombier if(s == eol)
67*3e12c5d1SDavid du Colombier break;
68*3e12c5d1SDavid du Colombier
69*3e12c5d1SDavid du Colombier for(inst=tlp->inst; ; inst = inst->l.next){
70*3e12c5d1SDavid du Colombier switch(inst->type){
71*3e12c5d1SDavid du Colombier case RUNE: /* regular character */
72*3e12c5d1SDavid du Colombier if(inst->r.r == r)
73*3e12c5d1SDavid du Colombier if(_renewthread(nl, inst->l.next, &tlp->se)==nle)
74*3e12c5d1SDavid du Colombier return -1;
75*3e12c5d1SDavid du Colombier break;
76*3e12c5d1SDavid du Colombier case LBRA:
77*3e12c5d1SDavid du Colombier tlp->se.m[inst->r.subid].s.rsp = s;
78*3e12c5d1SDavid du Colombier continue;
79*3e12c5d1SDavid du Colombier case RBRA:
80*3e12c5d1SDavid du Colombier tlp->se.m[inst->r.subid].e.rep = s;
81*3e12c5d1SDavid du Colombier continue;
82*3e12c5d1SDavid du Colombier case ANY:
83*3e12c5d1SDavid du Colombier if(r != '\n')
84*3e12c5d1SDavid du Colombier if(_renewthread(nl, inst->l.next, &tlp->se)==nle)
85*3e12c5d1SDavid du Colombier return -1;
86*3e12c5d1SDavid du Colombier break;
87*3e12c5d1SDavid du Colombier case ANYNL:
88*3e12c5d1SDavid du Colombier if(_renewthread(nl, inst->l.next, &tlp->se)==nle)
89*3e12c5d1SDavid du Colombier return -1;
90*3e12c5d1SDavid du Colombier break;
91*3e12c5d1SDavid du Colombier case BOL:
92*3e12c5d1SDavid du Colombier if(s == bol || *(s-1) == '\n')
93*3e12c5d1SDavid du Colombier continue;
94*3e12c5d1SDavid du Colombier break;
95*3e12c5d1SDavid du Colombier case EOL:
96*3e12c5d1SDavid du Colombier if(r == 0 || r == '\n')
97*3e12c5d1SDavid du Colombier continue;
98*3e12c5d1SDavid du Colombier break;
99*3e12c5d1SDavid du Colombier case CCLASS:
100*3e12c5d1SDavid du Colombier ep = inst->r.cp->end;
101*3e12c5d1SDavid du Colombier for(rp = inst->r.cp->spans; rp < ep; rp += 2)
102*3e12c5d1SDavid du Colombier if(r >= rp[0] && r <= rp[1]){
103*3e12c5d1SDavid du Colombier if(_renewthread(nl, inst->l.next, &tlp->se)==nle)
104*3e12c5d1SDavid du Colombier return -1;
105*3e12c5d1SDavid du Colombier break;
106*3e12c5d1SDavid du Colombier }
107*3e12c5d1SDavid du Colombier break;
108*3e12c5d1SDavid du Colombier case NCCLASS:
109*3e12c5d1SDavid du Colombier ep = inst->r.cp->end;
110*3e12c5d1SDavid du Colombier for(rp = inst->r.cp->spans; rp < ep; rp += 2)
111*3e12c5d1SDavid du Colombier if(r >= rp[0] && r <= rp[1])
112*3e12c5d1SDavid du Colombier break;
113*3e12c5d1SDavid du Colombier if(rp == ep)
114*3e12c5d1SDavid du Colombier if(_renewthread(nl, inst->l.next, &tlp->se)==nle)
115*3e12c5d1SDavid du Colombier return -1;
116*3e12c5d1SDavid du Colombier break;
117*3e12c5d1SDavid du Colombier case OR:
118*3e12c5d1SDavid du Colombier /* evaluate right choice later */
119*3e12c5d1SDavid du Colombier if(_renewthread(tlp, inst->r.right, &tlp->se) == tle)
120*3e12c5d1SDavid du Colombier return -1;
121*3e12c5d1SDavid du Colombier /* efficiency: advance and re-evaluate */
122*3e12c5d1SDavid du Colombier continue;
123*3e12c5d1SDavid du Colombier case END: /* Match! */
124*3e12c5d1SDavid du Colombier match = 1;
125*3e12c5d1SDavid du Colombier tlp->se.m[0].e.rep = s;
126*3e12c5d1SDavid du Colombier if(mp != 0)
127*3e12c5d1SDavid du Colombier _renewmatch(mp, ms, &tlp->se);
128*3e12c5d1SDavid du Colombier break;
129*3e12c5d1SDavid du Colombier }
130*3e12c5d1SDavid du Colombier break;
131*3e12c5d1SDavid du Colombier }
132*3e12c5d1SDavid du Colombier }
133*3e12c5d1SDavid du Colombier checkstart = startchar && nl->inst==0;
134*3e12c5d1SDavid du Colombier s++;
135*3e12c5d1SDavid du Colombier }while(r);
136*3e12c5d1SDavid du Colombier return match;
137*3e12c5d1SDavid du Colombier }
138*3e12c5d1SDavid du Colombier
139*3e12c5d1SDavid du Colombier extern int
rregexec(Reprog * progp,wchar_t * bol,Resub * mp,int ms)140*3e12c5d1SDavid du Colombier rregexec(Reprog *progp, /* program to run */
141*3e12c5d1SDavid du Colombier wchar_t *bol, /* string to run machine on */
142*3e12c5d1SDavid du Colombier Resub *mp, /* subexpression elements */
143*3e12c5d1SDavid du Colombier int ms) /* number of elements at mp */
144*3e12c5d1SDavid du Colombier {
145*3e12c5d1SDavid du Colombier wchar_t *starts; /* where to start match */
146*3e12c5d1SDavid du Colombier wchar_t *eol; /* where to end match */
147*3e12c5d1SDavid du Colombier wchar_t startchar;
148*3e12c5d1SDavid du Colombier int rv;
149*3e12c5d1SDavid du Colombier
150*3e12c5d1SDavid du Colombier /*
151*3e12c5d1SDavid du Colombier * use user-specified starting/ending location if specified
152*3e12c5d1SDavid du Colombier */
153*3e12c5d1SDavid du Colombier starts = bol;
154*3e12c5d1SDavid du Colombier eol = 0;
155*3e12c5d1SDavid du Colombier if(mp && ms>0){
156*3e12c5d1SDavid du Colombier if(mp->s.rsp)
157*3e12c5d1SDavid du Colombier starts = mp->s.rsp;
158*3e12c5d1SDavid du Colombier if(mp->e.rep)
159*3e12c5d1SDavid du Colombier eol = mp->e.rep;
160*3e12c5d1SDavid du Colombier }
161*3e12c5d1SDavid du Colombier startchar = progp->startinst->type == RUNE ? progp->startinst->r.r : 0;
162*3e12c5d1SDavid du Colombier
163*3e12c5d1SDavid du Colombier /* keep trying till we have enough list space to terminate */
164*3e12c5d1SDavid du Colombier for(;;){
165*3e12c5d1SDavid du Colombier if(_relist[0] == 0){
166*3e12c5d1SDavid du Colombier _relist[0] = malloc(2*_relistsize*sizeof(Relist));
167*3e12c5d1SDavid du Colombier _relist[1] = _relist[0] + _relistsize;
168*3e12c5d1SDavid du Colombier _reliste[0] = _relist[0] + _relistsize - 1;
169*3e12c5d1SDavid du Colombier _reliste[1] = _relist[1] + _relistsize - 1;
170*3e12c5d1SDavid du Colombier if(_relist[0] == 0)
171*3e12c5d1SDavid du Colombier regerror("_relist overflow");
172*3e12c5d1SDavid du Colombier }
173*3e12c5d1SDavid du Colombier rv = rregexec1(progp, bol, mp, ms, starts, eol, startchar);
174*3e12c5d1SDavid du Colombier if(rv >= 0)
175*3e12c5d1SDavid du Colombier return rv;
176*3e12c5d1SDavid du Colombier free(_relist[0]);
177*3e12c5d1SDavid du Colombier _relist[0] = 0;
178*3e12c5d1SDavid du Colombier _relistsize += LISTINCREMENT;
179*3e12c5d1SDavid du Colombier }
180*3e12c5d1SDavid du Colombier }
181