9base

revived minimalist port of Plan 9 userland to Unix
git clone git://git.suckless.org/9base
Log | Files | Refs | README | LICENSE

comp.c (4165B)


      1 #include	"grep.h"
      2 
      3 /*
      4  * incremental compiler.
      5  * add the branch c to the
      6  * state s.
      7  */
      8 void
      9 increment(State *s, int c)
     10 {
     11 	int i;
     12 	State *t, **tt;
     13 	Re *re1, *re2;
     14 
     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 	}
     54 
     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 }
     64 
     65 int
     66 fcmp(const void *va, const void *vb)
     67 {
     68 	Re **aa, **bb;
     69 	Re *a, *b;
     70 
     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 }
     81 
     82 void
     83 fol1(Re *r, int c)
     84 {
     85 	Re *r1;
     86 
     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");
     96 
     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;
    104 
    105 	case Talt:
    106 	case Tor:
    107 		fol1(r->u.alt, c);
    108 		r = r->next;
    109 		goto loop;
    110 
    111 	case Tbegin:
    112 		if(c == '\n' || c == Cbegin)
    113 			follow[nfollow++] = r->next;
    114 		break;
    115 
    116 	case Tend:
    117 		if(c == '\n')
    118 			matched = 1;
    119 		break;
    120 
    121 	case Tclass:
    122 		if(c >= r->u.x.lo && c <= r->u.x.hi)
    123 			follow[nfollow++] = r->next;
    124 		break;
    125 	}
    126 }
    127 
    128 Rune	tab1[] =
    129 {
    130 	0x007f,
    131 	0x07ff
    132 };
    133 Rune	tab2[] =
    134 {
    135 	0x003f,
    136 	0x0fff
    137 };
    138 
    139 Re2
    140 rclass(Rune p0, Rune p1)
    141 {
    142 	char xc0[6], xc1[6];
    143 	int i, n, m;
    144 	Re2 x;
    145 
    146 	if(p0 > p1)
    147 		return re2char(0xff, 0xff);	/* no match */
    148 
    149 	/*
    150 	 * bust range into same length
    151 	 * character sequences
    152 	 */
    153 	for(i=0; i<nelem(tab1); i++) {
    154 		m = tab1[i];
    155 		if(p0 <= m && p1 > m)
    156 			return re2or(rclass(p0, m), rclass(m+1, p1));
    157 	}
    158 
    159 	/*
    160 	 * bust range into part of a single page
    161 	 * or into full pages
    162 	 */
    163 	for(i=0; i<nelem(tab2); i++) {
    164 		m = tab2[i];
    165 		if((p0 & ~m) != (p1 & ~m)) {
    166 			if((p0 & m) != 0)
    167 				return re2or(rclass(p0, p0|m), rclass((p0|m)+1, p1));
    168 			if((p1 & m) != m)
    169 				return re2or(rclass(p0, (p1&~m)-1), rclass(p1&~m, p1));
    170 		}
    171 	}
    172 
    173 	n = runetochar(xc0, &p0);
    174 	i = runetochar(xc1, &p1);
    175 	if(i != n)
    176 		error("length");
    177 
    178 	x = re2char(xc0[0], xc1[0]);
    179 	for(i=1; i<n; i++)
    180 		x = re2cat(x, re2char(xc0[i], xc1[i]));
    181 	return x;
    182 }
    183 
    184 int
    185 pcmp(const void *va, const void *vb)
    186 {
    187 	int n;
    188 	Rune *a, *b;
    189 
    190 	a = (Rune*)va;
    191 	b = (Rune*)vb;
    192 
    193 	n = a[0] - b[0];
    194 	if(n)
    195 		return n;
    196 	return a[1] - b[1];
    197 }
    198 
    199 /*
    200  * convert character chass into
    201  * run-pair ranges of matches.
    202  * this is 10646/utf specific and
    203  * needs to be changed for some
    204  * other input character set.
    205  * this is the key to a fast
    206  * regular search of characters
    207  * by looking at sequential bytes.
    208  */
    209 Re2
    210 re2class(char *s)
    211 {
    212 	Rune pairs[200], *p, *q, ov;
    213 	int nc;
    214 	Re2 x;
    215 
    216 	nc = 0;
    217 	if(*s == '^') {
    218 		nc = 1;
    219 		s++;
    220 	}
    221 
    222 	p = pairs;
    223 	s += chartorune(p, s);
    224 	for(;;) {
    225 		if(*p == '\\')
    226 			s += chartorune(p, s);
    227 		if(*p == 0)
    228 			break;
    229 		p[1] = *p;
    230 		p += 2;
    231 		s += chartorune(p, s);
    232 		if(*p != '-')
    233 			continue;
    234 		s += chartorune(p, s);
    235 		if(*p == '\\')
    236 			s += chartorune(p, s);
    237 		if(*p == 0)
    238 			break;
    239 		p[-1] = *p;
    240 		s += chartorune(p, s);
    241 	}
    242 	*p = 0;
    243 	qsort(pairs, (p-pairs)/2, 2*sizeof(*pairs), pcmp);
    244 
    245 	q = pairs;
    246 	for(p=pairs+2; *p; p+=2) {
    247 		if(p[0] > p[1])
    248 			continue;
    249 		if(p[0] > q[1] || p[1] < q[0]) {
    250 			q[2] = p[0];
    251 			q[3] = p[1];
    252 			q += 2;
    253 			continue;
    254 		}
    255 		if(p[0] < q[0])
    256 			q[0] = p[0];
    257 		if(p[1] > q[1])
    258 			q[1] = p[1];
    259 	}
    260 	q[2] = 0;
    261 
    262 	p = pairs;
    263 	if(nc) {
    264 		x = rclass(0, p[0]-1);
    265 		ov = p[1]+1;
    266 		for(p+=2; *p; p+=2) {
    267 			x = re2or(x, rclass(ov, p[0]-1));
    268 			ov = p[1]+1;
    269 		}
    270 		x = re2or(x, rclass(ov, 0xffff));
    271 	} else {
    272 		x = rclass(p[0], p[1]);
    273 		for(p+=2; *p; p+=2)
    274 			x = re2or(x, rclass(p[0], p[1]));
    275 	}
    276 	return x;
    277 }