![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to egmatch.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv10no / cmd / gre|
Return to egmatch.c CVS log | Up to [Research Unix] / researchv10no / cmd / gre |
1.1 root 1: #include "re.h"
2: #include "lre.h"
3: #include "hdr.h"
4:
5: #define DEBUG
6:
7: static unsigned char *eg_slowmatch(Br *, unsigned char *, unsigned char *, int);
8: static unsigned char *wholeb, *wholee;
9: static unsigned char *start[10];
10: static int len[10];
11: static void undobr(Br *); /* undo group assignements */
12:
13: eg_match(register re_re *r, register unsigned char *b, register unsigned char *e, unsigned char **rb, unsigned char **re)
14: {
15: int i, ret;
16:
17: #ifdef DEBUG
18: if(TRACE(2)){
19: PR "eg_match(%d->%d, %d, %d)\n", (int)r, (int)r->br, (int)b, (int)e);
20: if(r->br)
21: eg_brpr(r->br);
22: }
23: #endif
24: if((rb == 0) != (re == 0)){
25: re_error("must supply both or none of group pointers");
26: return(0);
27: }
28: if(r->backref || r->parens || rb){
29: wholeb = e;
30: for(i = 1; i < 10; i++)
31: start[i] = 0;
32: if(r->br == 0)
33: egbr(r);
34: ret = (wholee = eg_slowmatch(r->br, b, e, RE_BEG|RE_END)) != 0;
35: if(rb && ret){
36: rb[0] = wholeb;
37: re[0] = wholee;
38: for(i = 1; i < 10; i++){
39: rb[i] = start[i];
40: re[i] = rb[i]+len[i];
41: }
42: #ifdef DEBUG
43: if(TRACE(1)){
44: PR "eg_match groups:");
45: for(i = 0; i < 10; i++)
46: if(rb[i])PR " %d: %d@%d", i, rb[i], re[i]-rb[i]);
47: PR "\n");
48: }
49: #endif
50: }
51: #ifdef DEBUG
52: else {
53: if(TRACE(1)){
54: PR "eg_match groups: [%d - %d]\n", wholeb, wholee);
55: for(i = 1; i < 10; i++)
56: if(start[i])PR " %d: %d@%d", i, start[i], len[i]);
57: PR "\n");
58: }
59: }
60: #endif
61: } else
62: ret = eg_quickmatch(r, b, e, RE_BEG|RE_END) != 0;
63: return(ret);
64: }
65:
66: static unsigned char *
67: eg_slowmatch(Br *br, unsigned char *b, unsigned char *e, int endpts)
68: {
69: int i;
70: unsigned char *me, *end;
71: unsigned char *beg, *lbeg, *llbeg, *rbeg, *rend, *lm, *rm;
72: #ifdef DEBUG
73: char buf[EPRINTSIZE];
74: static id = 1;
75: int myid = id++;
76: #endif
77:
78: #define BOFF(x) ((x)? (endpts&~RE_BEG):endpts)
79: #define EOFF(x) ((x)? (endpts&~RE_END):endpts)
80:
81: if(br == 0) /* nothing to match - we won! */
82: return(b);
83: #ifdef DEBUG
84: if(TRACE(3))
85: PR "slowmatch(br=%d, [b,e]=%d,%d id=%d, endpt=%d)\n", br, b, e, myid, endpts);
86: #endif
87: switch(br->type)
88: {
89: case br_br:
90: i = br->group;
91: #ifdef DEBUG
92: if(TRACE(3))
93: PR "br[%d]: %d,%d b=%d,e=%d\n", i, (int)start[i], len[i], b, e);
94: #endif
95: if(start[i] == 0)
96: return(0);
97: if((len[i] > e-b) || memcmp((char *)b, (char *)start[i], len[i]))
98: return(0);
99: if(wholeb > b) wholeb = b;
100: #ifdef DEBUG
101: if(TRACE(3))
102: PR "br[%d]: matched\n", i);
103: #endif
104: return(b+len[i]);
105:
106: case br_re:
107: #ifdef DEBUG
108: if(TRACE(3)){
109: eg_epr(br->e, buf, 0);
110: PR "matching RE(%s)@%d against '", buf, br->r);
111: WR((char *)b, e-b);
112: PR "' id=%d\n", myid);
113: }
114: #endif
115: if((me = eg_lquickmatch(br->r, b, e, endpts)) == 0)
116: return(0);
117: #ifdef DEBUG
118: if(TRACE(3)){
119: PR "--%s matched '", buf);
120: WR((char *)b, me-b);
121: PR "'[%d %d] id=%d\n", (int)b, (int)me, myid);
122: }
123: #endif
124: if(wholeb > b)
125: wholeb = b;
126: return(me);
127:
128: case br_group:
129: #ifdef DEBUG
130: if(TRACE(3)){
131: PR "matching GROUP%d against '", br->group);
132: WR((char *)b, e-b);
133: PR "' id=%d\n", myid);
134: }
135: #endif
136: if((me = eg_slowmatch(br->lb, b, e, endpts)) == 0){
137: undobr(br->lb);
138: return(0);
139: }
140: #ifdef DEBUG
141: if(TRACE(3)){
142: PR "--G%d matched '", br->group);
143: WR((char *)b, me-b);
144: PR "'[%d %d]\n", (int)b, (int)me);
145: }
146: #endif
147: if(wholeb > b)
148: wholeb = b;
149: start[br->group] = b;
150: len[br->group] = me-b;
151: return(me);
152:
153: case br_quest:
154: #ifdef DEBUG
155: if(TRACE(3)){
156: PR "matching BR? against '", buf);
157: WR((char *)b, e-b);
158: PR "'\n");
159: }
160: #endif
161: if(lbeg = eg_slowmatch(br->lb, b, e, endpts)){
162: return(lbeg);
163: }
164: undobr(br->lb);
165: return(b);
166:
167: case br_plus:
168: #ifdef DEBUG
169: if(TRACE(3)){
170: PR "matching BR+ against '", buf);
171: WR((char *)b, e-b);
172: PR "' id=%d\n", myid);
173: }
174: #endif
175: if((lbeg = eg_slowmatch(br->lb, b, e, endpts)) == 0){
176: undobr(br->lb);
177: return(0);
178: }
179: llbeg = b;
180: while(beg = eg_slowmatch(br->lb, lbeg, e, BOFF(lbeg != b))){
181: llbeg = lbeg, lbeg = beg;
182: }
183: #ifdef DEBUG
184: if(TRACE(3)){
185: PR "--+ matched [%d %d]'", (int)llbeg, (int)lbeg);
186: WR((char *)llbeg, lbeg-llbeg);
187: PR "' id=%d\n", myid);
188: }
189: #endif
190: return(eg_slowmatch(br->lb, llbeg, e, BOFF(llbeg != b)));
191:
192: case br_star:
193: #ifdef DEBUG
194: if(TRACE(3)){
195: PR "matching BR* against '", buf);
196: WR((char *)b, e-b);
197: PR "'\n");
198: }
199: #endif
200: llbeg = lbeg = b;
201: while(beg = eg_slowmatch(br->lb, lbeg, e, BOFF(lbeg != b)))
202: llbeg = lbeg, lbeg = beg;
203: #ifdef DEBUG
204: if(TRACE(3)){
205: PR "--* matched '");
206: WR((char *)lbeg, lbeg-llbeg);
207: PR "'[%d %d]\n", (int)llbeg, (int)lbeg);
208: }
209: #endif
210: if(beg = eg_slowmatch(br->lb, llbeg, e, BOFF(llbeg != b)))
211: return(beg);
212: undobr(br->lb);
213: return(b);
214:
215: case br_cat:
216: #ifdef DEBUG
217: if(TRACE(3)){
218: PR "matching BRcat against '", buf);
219: WR((char *)b, e-b);
220: PR "' id=%d\n", myid);
221: }
222: #endif
223: /*
224: this is not so hard.
225: we try all possible matches of the left half,
226: and record the match that gave the longest
227: valid match on the right half
228: */
229: rend = 0;
230: for(end = e; b <= e; e = beg-1){
231: if((beg = eg_slowmatch(br->lb, b, e, EOFF(e != end))) == 0){
232: break;
233: }
234: #ifdef DEBUG
235: if(TRACE(3)){
236: PR "--cat matched '");
237: WR((char *)b, beg-b);
238: PR "'[%d %d] id=%d\n", (int)b, (int)beg, myid);
239: }
240: #endif
241: if((me = eg_slowmatch(br->rb, beg, end, BOFF(beg != b))) == 0){
242: continue; /* no match of right half */
243: }
244: #ifdef DEBUG
245: if(TRACE(3)){
246: PR "----cat matched '");
247: WR((char *)b, beg-b);
248: PR "'[%d %d] id=%d\n", (int)b, (int)beg, myid);
249: }
250: #endif
251: if(me > rend){
252: rend = me;
253: rbeg = beg;
254: #ifdef DEBUG
255: if(TRACE(3)){
256: PR "--++-- cat new max rb=%d re=%d\n", (int)rbeg, (int)rend);
257: }
258: #endif
259: }
260: }
261: if(rend == 0){
262: undobr(br->lb);
263: undobr(br->rb);
264: return(0);
265: }
266: (void)eg_slowmatch(br->lb, b, rbeg, EOFF(rbeg != end));
267: return(eg_slowmatch(br->rb, rbeg, end, BOFF(rbeg != b)));
268:
269: case br_alt:
270: #ifdef DEBUG
271: if(TRACE(3)){
272: PR "matching BR| against '", buf);
273: WR((char *)b, e-b);
274: PR "'\n");
275: }
276: #endif
277: if(lm = eg_slowmatch(br->lb, b, e, endpts)){
278: #ifdef DEBUG
279: if(TRACE(3)){
280: PR "--|L matched '");
281: WR((char *)b, lm-b);
282: PR "'[%d %d]\n", (int)b, (int)lm);
283: }
284: #endif
285: }
286: if(rm = eg_slowmatch(br->rb, b, e, endpts)){
287: #ifdef DEBUG
288: if(TRACE(3)){
289: PR "--|R matched '");
290: WR((char *)b, rm-b);
291: PR "'[%d %d]\n", (int)b, (int)rm);
292: }
293: #endif
294: }
295: if(lm > rm){
296: undobr(br->rb);
297: return(eg_slowmatch(br->lb, b, e, endpts));
298: } else {
299: if(rm == 0){
300: undobr(br->lb);
301: undobr(br->rb);
302: return(0);
303: } else {
304: undobr(br->lb);
305: return(beg);
306: }
307: }
308: }
309: abort();
310: return(0);
311: }
312:
313: static void
314: undobr(register Br *br)
315: {
316: switch(br->type)
317: {
318: case br_group:
319: start[br->group] = 0;
320: undobr(br->lb);
321: break;
322: case br_star:
323: case br_plus:
324: case br_quest:
325: undobr(br->lb);
326: break;
327: case br_cat:
328: case br_alt:
329: undobr(br->lb);
330: undobr(br->rb);
331: break;
332: }
333: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.