trregexec.c - plan9port - [fork] Plan 9 from user space
HTML git clone git://src.adamsgaard.dk/plan9port
DIR Log
DIR Files
DIR Refs
DIR README
DIR LICENSE
---
trregexec.c (4728B)
---
1 #include "lib9.h"
2 #include "regexp9.h"
3 #include "regcomp.h"
4
5 /*
6 * return 0 if no match
7 * >0 if a match
8 * <0 if we ran out of _relist space
9 */
10 static int
11 rregexec1(Reprog *progp, /* program to run */
12 Rune *bol, /* string to run machine on */
13 Resub *mp, /* subexpression elements */
14 int ms, /* number of elements at mp */
15 Reljunk *j)
16 {
17 int flag=0;
18 Reinst *inst;
19 Relist *tlp;
20 Rune *s;
21 int i, checkstart;
22 Rune r, *rp, *ep;
23 Relist* tl; /* This list, next list */
24 Relist* nl;
25 Relist* tle; /* ends of this and next list */
26 Relist* nle;
27 int match;
28 Rune *p;
29
30 match = 0;
31 checkstart = j->startchar;
32 if(mp)
33 for(i=0; i<ms; i++) {
34 mp[i].s.rsp = 0;
35 mp[i].e.rep = 0;
36 }
37 j->relist[0][0].inst = 0;
38 j->relist[1][0].inst = 0;
39
40 /* Execute machine once for each character, including terminal NUL */
41 s = j->rstarts;
42 do{
43 /* fast check for first char */
44 if(checkstart) {
45 switch(j->starttype) {
46 case RUNE:
47 p = runestrchr(s, j->startchar);
48 if(p == 0 || s == j->reol)
49 return match;
50 s = p;
51 break;
52 case BOL:
53 if(s == bol)
54 break;
55 p = runestrchr(s, '\n');
56 if(p == 0 || s == j->reol)
57 return match;
58 s = p+1;
59 break;
60 }
61 }
62
63 r = *s;
64
65 /* switch run lists */
66 tl = j->relist[flag];
67 tle = j->reliste[flag];
68 nl = j->relist[flag^=1];
69 nle = j->reliste[flag];
70 nl->inst = 0;
71
72 /* Add first instruction to current list */
73 _rrenewemptythread(tl, progp->startinst, ms, s);
74
75 /* Execute machine until current list is empty */
76 for(tlp=tl; tlp->inst; tlp++){
77 for(inst=tlp->inst; ; inst = inst->u2.next){
78 switch(inst->type){
79 case RUNE: /* regular character */
80 if(inst->u1.r == r)
81 if(_renewthread(nl, inst->u2.next, ms, &tlp->se)==nle)
82 return -1;
83 break;
84 case LBRA:
85 tlp->se.m[inst->u1.subid].s.rsp = s;
86 continue;
87 case RBRA:
88 tlp->se.m[inst->u1.subid].e.rep = s;
89 continue;
90 case ANY:
91 if(r != '\n')
92 if(_renewthread(nl, inst->u2.next, ms, &tlp->se)==nle)
93 return -1;
94 break;
95 case ANYNL:
96 if(_renewthread(nl, inst->u2.next, ms, &tlp->se)==nle)
97 return -1;
98 break;
99 case BOL:
100 if(s == bol || *(s-1) == '\n')
101 continue;
102 break;
103 case EOL:
104 if(s == j->reol || r == 0 || r == '\n')
105 continue;
106 break;
107 case CCLASS:
108 ep = inst->u1.cp->end;
109 for(rp = inst->u1.cp->spans; rp < ep; rp += 2)
110 if(r >= rp[0] && r <= rp[1]){
111 if(_renewthread(nl, inst->u2.next, ms, &tlp->se)==nle)
112 return -1;
113 break;
114 }
115 break;
116 case NCCLASS:
117 ep = inst->u1.cp->end;
118 for(rp = inst->u1.cp->spans; rp < ep; rp += 2)
119 if(r >= rp[0] && r <= rp[1])
120 break;
121 if(rp == ep)
122 if(_renewthread(nl, inst->u2.next, ms, &tlp->se)==nle)
123 return -1;
124 break;
125 case OR:
126 /* evaluate right choice later */
127 if(_renewthread(tlp, inst->u1.right, ms, &tlp->se) == tle)
128 return -1;
129 /* efficiency: advance and re-evaluate */
130 continue;
131 case END: /* Match! */
132 match = 1;
133 tlp->se.m[0].e.rep = s;
134 if(mp != 0)
135 _renewmatch(mp, ms, &tlp->se);
136 break;
137 }
138 break;
139 }
140 }
141 if(s == j->reol)
142 break;
143 checkstart = j->startchar && nl->inst==0;
144 s++;
145 }while(r);
146 return match;
147 }
148
149 static int
150 rregexec2(Reprog *progp, /* program to run */
151 Rune *bol, /* string to run machine on */
152 Resub *mp, /* subexpression elements */
153 int ms, /* number of elements at mp */
154 Reljunk *j
155 )
156 {
157 Relist relist0[5*LISTSIZE], relist1[5*LISTSIZE];
158
159 /* mark space */
160 j->relist[0] = relist0;
161 j->relist[1] = relist1;
162 j->reliste[0] = relist0 + nelem(relist0) - 2;
163 j->reliste[1] = relist1 + nelem(relist1) - 2;
164
165 return rregexec1(progp, bol, mp, ms, j);
166 }
167
168 extern int
169 rregexec(Reprog *progp, /* program to run */
170 Rune *bol, /* string to run machine on */
171 Resub *mp, /* subexpression elements */
172 int ms) /* number of elements at mp */
173 {
174 Reljunk j;
175 Relist relist0[LISTSIZE], relist1[LISTSIZE];
176 int rv;
177
178 /*
179 * use user-specified starting/ending location if specified
180 */
181 j.rstarts = bol;
182 j.reol = 0;
183 if(mp && ms>0){
184 if(mp->s.sp)
185 j.rstarts = mp->s.rsp;
186 if(mp->e.ep)
187 j.reol = mp->e.rep;
188 }
189 j.starttype = 0;
190 j.startchar = 0;
191 if(progp->startinst->type == RUNE && progp->startinst->u1.r < Runeself) {
192 j.starttype = RUNE;
193 j.startchar = progp->startinst->u1.r;
194 }
195 if(progp->startinst->type == BOL)
196 j.starttype = BOL;
197
198 /* mark space */
199 j.relist[0] = relist0;
200 j.relist[1] = relist1;
201 j.reliste[0] = relist0 + nelem(relist0) - 2;
202 j.reliste[1] = relist1 + nelem(relist1) - 2;
203
204 rv = rregexec1(progp, bol, mp, ms, &j);
205 if(rv >= 0)
206 return rv;
207 rv = rregexec2(progp, bol, mp, ms, &j);
208 if(rv >= 0)
209 return rv;
210 return -1;
211 }