Blob
1 #include "grep.h"3 /*4 * incremental compiler.5 * add the branch c to the6 * state s.7 */8 void9 increment(State *s, int c)10 {11 int i;12 State *t, **tt;13 Re *re1, *re2;15 nfollow = 0;16 gen++;17 matched = 0;18 for(i=0; i<s->count; i++)19 fol1(s->re[i], c);20 qsort(follow, nfollow, sizeof(*follow), fcmp);21 for(tt=&state0; t = *tt;) {22 if(t->count > nfollow) {23 tt = &t->linkleft;24 goto cont;25 }26 if(t->count < nfollow) {27 tt = &t->linkright;28 goto cont;29 }30 for(i=0; i<nfollow; i++) {31 re1 = t->re[i];32 re2 = follow[i];33 if(re1 > re2) {34 tt = &t->linkleft;35 goto cont;36 }37 if(re1 < re2) {38 tt = &t->linkright;39 goto cont;40 }41 }42 if(!!matched && !t->match) {43 tt = &t->linkleft;44 goto cont;45 }46 if(!matched && !!t->match) {47 tt = &t->linkright;48 goto cont;49 }50 s->next[c] = t;51 return;52 cont:;53 }55 t = sal(nfollow);56 *tt = t;57 for(i=0; i<nfollow; i++) {58 re1 = follow[i];59 t->re[i] = re1;60 }61 s->next[c] = t;62 t->match = matched;63 }65 int66 fcmp(const void *va, const void *vb)67 {68 Re **aa, **bb;69 Re *a, *b;71 aa = (Re**)va;72 bb = (Re**)vb;73 a = *aa;74 b = *bb;75 if(a > b)76 return 1;77 if(a < b)78 return -1;79 return 0;80 }82 void83 fol1(Re *r, int c)84 {85 Re *r1;87 loop:88 if(r->gen == gen)89 return;90 if(nfollow >= maxfollow)91 error("nfollow");92 r->gen = gen;93 switch(r->type) {94 default:95 error("fol1");97 case Tcase:98 if(c >= 0 && c < 256)99 if(r1 = r->u.cases[c])100 follow[nfollow++] = r1;101 if(r = r->next)102 goto loop;103 break;105 case Talt:106 case Tor:107 fol1(r->u.alt, c);108 r = r->next;109 goto loop;111 case Tbegin:112 if(c == '\n' || c == Cbegin)113 follow[nfollow++] = r->next;114 break;116 case Tend:117 if(c == '\n') {118 if(r->next == 0) {119 matched = 1;120 break;121 }122 r = r->next;123 goto loop;124 }125 break;127 case Tclass:128 if(c >= r->u.x.lo && c <= r->u.x.hi)129 follow[nfollow++] = r->next;130 break;131 }132 }134 Rune tab1[] =135 {136 0x007f,137 0x07ff138 };139 Rune tab2[] =140 {141 0x003f,142 0x0fff143 };145 Re2146 rclass(Rune p0, Rune p1)147 {148 char xc0[6], xc1[6];149 int i, n, m;150 Re2 x;152 if(p0 > p1)153 return re2char(0xff, 0xff); /* no match */155 /*156 * bust range into same length157 * character sequences158 */159 for(i=0; i<nelem(tab1); i++) {160 m = tab1[i];161 if(p0 <= m && p1 > m)162 return re2or(rclass(p0, m), rclass(m+1, p1));163 }165 /*166 * bust range into part of a single page167 * or into full pages168 */169 for(i=0; i<nelem(tab2); i++) {170 m = tab2[i];171 if((p0 & ~m) != (p1 & ~m)) {172 if((p0 & m) != 0)173 return re2or(rclass(p0, p0|m), rclass((p0|m)+1, p1));174 if((p1 & m) != m)175 return re2or(rclass(p0, (p1&~m)-1), rclass(p1&~m, p1));176 }177 }179 n = runetochar(xc0, &p0);180 i = runetochar(xc1, &p1);181 if(i != n)182 error("length");184 x = re2char(xc0[0], xc1[0]);185 for(i=1; i<n; i++)186 x = re2cat(x, re2char(xc0[i], xc1[i]));187 return x;188 }190 int191 pcmp(const void *va, const void *vb)192 {193 int n;194 Rune *a, *b;196 a = (Rune*)va;197 b = (Rune*)vb;199 n = a[0] - b[0];200 if(n)201 return n;202 return a[1] - b[1];203 }205 /*206 * convert character chass into207 * run-pair ranges of matches.208 * this is 10646/utf specific and209 * needs to be changed for some210 * other input character set.211 * this is the key to a fast212 * regular search of characters213 * by looking at sequential bytes.214 */215 Re2216 re2class(char *s)217 {218 Rune pairs[200], *p, *q, ov;219 int nc;220 Re2 x;222 nc = 0;223 if(*s == '^') {224 nc = 1;225 s++;226 }228 p = pairs;229 s += chartorune(p, s);230 for(;;) {231 if(*p == '\\')232 s += chartorune(p, s);233 if(*p == 0)234 break;235 p[1] = *p;236 p += 2;237 s += chartorune(p, s);238 if(*p != '-')239 continue;240 s += chartorune(p, s);241 if(*p == '\\')242 s += chartorune(p, s);243 if(*p == 0)244 break;245 p[-1] = *p;246 s += chartorune(p, s);247 }248 *p = 0;249 qsort(pairs, (p-pairs)/2, 2*sizeof(*pairs), pcmp);251 q = pairs;252 for(p=pairs+2; *p; p+=2) {253 if(p[0] > p[1])254 continue;255 if(p[0] > q[1] || p[1] < q[0]) {256 q[2] = p[0];257 q[3] = p[1];258 q += 2;259 continue;260 }261 if(p[0] < q[0])262 q[0] = p[0];263 if(p[1] > q[1])264 q[1] = p[1];265 }266 q[2] = 0;268 p = pairs;269 if(nc) {270 x = rclass(0, p[0]-1);271 ov = p[1]+1;272 for(p+=2; *p; p+=2) {273 x = re2or(x, rclass(ov, p[0]-1));274 ov = p[1]+1;275 }276 x = re2or(x, rclass(ov, 0xffff));277 } else {278 x = rclass(p[0], p[1]);279 for(p+=2; *p; p+=2)280 x = re2or(x, rclass(p[0], p[1]));281 }282 return x;283 }