sys/src/cmd/grep/comp.c

   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(void *va, void *vb)
  67 {
  68         Re **aa, **bb;
  69         Re *a, *b;
  70
  71         aa = va;
  72         bb = 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->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->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                         if(r->next == 0) {
 119                                 matched = 1;
 120                                 break;
 121                         }
 122                         r = r->next;
 123                         goto loop;
 124                 }
 125                 break;
 126
 127         case Tclass:
 128                 if(c >= r->lo && c <= r->hi)
 129                         follow[nfollow++] = r->next;
 130                 break;
 131         }
 132 }
 133
 134 int     tab1[] =
 135 {
 136         0x007f,
 137         0x07ff,
 138         0xffff,
 139 };
 140 int     tab2[] =
 141 {
 142         0x003f,
 143         0x0fff,
 144         0x3ffff,
 145 };
 146
 147 Re2
 148 rclass(Rune p0, Rune p1)
 149 {
 150         char xc0[6], xc1[6];
 151         int i, n, m;
 152         Re2 x;
 153
 154         if(p0 > p1)
 155                 return re2char(0xff, 0xff);     // no match
 156
 157         /*
 158          * bust range into same length
 159          * character sequences
 160          */
 161         for(i=0; i<nelem(tab1); i++) {
 162                 m = tab1[i];
 163                 if(p0 <= m && p1 > m)
 164                         return re2or(rclass(p0, m), rclass(m+1, p1));
 165         }
 166
 167         /*
 168          * bust range into part of a single page
 169          * or into full pages
 170          */
 171         for(i=0; i<nelem(tab2); i++) {
 172                 m = tab2[i];
 173                 if((p0 & ~m) != (p1 & ~m)) {
 174                         if((p0 & m) != 0)
 175                                 return re2or(rclass(p0, p0|m), rclass((p0|m)+1, p1));
 176                         if((p1 & m) != m)
 177                                 return re2or(rclass(p0, (p1&~m)-1), rclass(p1&~m, p1));
 178                 }
 179         }
 180
 181         n = runetochar(xc0, &p0);
 182         i = runetochar(xc1, &p1);
 183         if(i != n)
 184                 error("length");
 185
 186         x = re2char(xc0[0], xc1[0]);
 187         for(i=1; i<n; i++)
 188                 x = re2cat(x, re2char(xc0[i], xc1[i]));
 189         return x;
 190 }
 191
 192 int
 193 pcmp(void *va, void *vb)
 194 {
 195         int n;
 196         Rune *a, *b;
 197
 198         a = va;
 199         b = vb;
 200
 201         n = a[0] - b[0];
 202         if(n)
 203                 return n;
 204         return a[1] - b[1];
 205 }
 206
 207 /*
 208  * convert character chass into
 209  * run-pair ranges of matches.
 210  * this is 10646/utf specific and
 211  * needs to be changed for some
 212  * other input character set.
 213  * this is the key to a fast
 214  * regular search of characters
 215  * by looking at sequential bytes.
 216  */
 217 Re2
 218 re2class(char *s)
 219 {
 220         Rune pairs[200+2], *p, *q, ov;
 221         int nc;
 222         Re2 x;
 223
 224         nc = 0;
 225         if(*s == '^') {
 226                 nc = 1;
 227                 s++;
 228         }
 229
 230         p = pairs;
 231         s += chartorune(p, s);
 232         for(;;) {
 233                 if(*p == '\\')
 234                         s += chartorune(p, s);
 235                 if(*p == 0)
 236                         break;
 237                 p[1] = *p;
 238                 p += 2;
 239                 if(p >= pairs + nelem(pairs) - 2)
 240                         error("class too big");
 241                 s += chartorune(p, s);
 242                 if(*p != '-')
 243                         continue;
 244                 s += chartorune(p, s);
 245                 if(*p == '\\')
 246                         s += chartorune(p, s);
 247                 if(*p == 0)
 248                         break;
 249                 p[-1] = *p;
 250                 s += chartorune(p, s);
 251         }
 252         *p = 0;
 253         qsort(pairs, (p-pairs)/2, 2*sizeof(*pairs), pcmp);
 254
 255         q = pairs;
 256         for(p=pairs+2; *p; p+=2) {
 257                 if(p[0] > p[1])
 258                         continue;
 259                 if(p[0] > q[1] || p[1] < q[0]) {
 260                         q[2] = p[0];
 261                         q[3] = p[1];
 262                         q += 2;
 263                         continue;
 264                 }
 265                 if(p[0] < q[0])
 266                         q[0] = p[0];
 267                 if(p[1] > q[1])
 268                         q[1] = p[1];
 269         }
 270         q[2] = 0;
 271
 272         p = pairs;
 273         if(nc) {
 274                 x = rclass(0, p[0]-1);
 275                 ov = p[1]+1;
 276                 for(p+=2; *p; p+=2) {
 277                         x = re2or(x, rclass(ov, p[0]-1));
 278                         ov = p[1]+1;
 279                 }
 280                 x = re2or(x, rclass(ov, Runemax));
 281         } else {
 282                 x = rclass(p[0], p[1]);
 283                 for(p+=2; *p; p+=2)
 284                         x = re2or(x, rclass(p[0], p[1]));
 285         }
 286         return x;
 287 }