sys/src/cmd/grep/sub.c

   1 #include        "grep.h"
   2
   3 void*
   4 mal(int n)
   5 {
   6         static char *s;
   7         static int m = 0;
   8         void *v;
   9
  10         n = (n+3) & ~3;
  11         if(m < n) {
  12                 if(n > Nhunk) {
  13                         v = sbrk(n);
  14                         if(v == (void*)-1)
  15                                 error("sbrk");
  16                         memset(v, 0, n);
  17                         return v;
  18                 }
  19                 s = sbrk(Nhunk);
  20                 if(s == (void*)-1)
  21                         error("sbrk");
  22                 m = Nhunk;
  23         }
  24         v = s;
  25         s += n;
  26         m -= n;
  27         memset(v, 0, n);
  28         return v;
  29 }
  30
  31 State*
  32 sal(int n)
  33 {
  34         State *s;
  35
  36         s = mal(sizeof(*s));
  37 //      s->next = mal(256*sizeof(*s->next));
  38         s->count = n;
  39         s->re = mal(n*sizeof(*state0->re));
  40         return s;
  41 }
  42
  43 Re*
  44 ral(int type)
  45 {
  46         Re *r;
  47
  48         r = mal(sizeof(*r));
  49         r->type = type;
  50         maxfollow++;
  51         return r;
  52 }
  53
  54 void
  55 error(char *s)
  56 {
  57         fprint(2, "grep: internal error: %s\n", s);
  58         exits(s);
  59 }
  60
  61 int
  62 countor(Re *r)
  63 {
  64         int n;
  65
  66         n = 0;
  67 loop:
  68         switch(r->type) {
  69         case Tor:
  70                 n += countor(r->alt);
  71                 r = r->next;
  72                 goto loop;
  73         case Tclass:
  74                 return n + r->hi - r->lo + 1;
  75         }
  76         return n;
  77 }
  78
  79 Re*
  80 oralloc(int t, Re *r, Re *b)
  81 {
  82         Re *a;
  83
  84         if(b == 0)
  85                 return r;
  86         a = ral(t);
  87         a->alt = r;
  88         a->next = b;
  89         return a;
  90 }
  91
  92 void
  93 case1(Re *c, Re *r)
  94 {
  95         int n;
  96
  97 loop:
  98         switch(r->type) {
  99         case Tor:
 100                 case1(c, r->alt);
 101                 r = r->next;
 102                 goto loop;
 103
 104         case Tclass:    /* add to character */
 105                 for(n=r->lo; n<=r->hi; n++)
 106                         c->cases[n] = oralloc(Tor, r->next, c->cases[n]);
 107                 break;
 108
 109         default:        /* add everything unknown to next */
 110                 c->next = oralloc(Talt, r, c->next);
 111                 break;
 112         }
 113 }
 114
 115 Re*
 116 addcase(Re *r)
 117 {
 118         int i, n;
 119         Re *a;
 120
 121         if(r->gen == gen)
 122                 return r;
 123         r->gen = gen;
 124         switch(r->type) {
 125         default:
 126                 error("addcase");
 127
 128         case Tor:
 129                 n = countor(r);
 130                 if(n >= Caselim) {
 131                         a = ral(Tcase);
 132                         a->cases = mal(256*sizeof(*a->cases));
 133                         case1(a, r);
 134                         for(i=0; i<256; i++)
 135                                 if(a->cases[i]) {
 136                                         r = a->cases[i];
 137                                         if(countor(r) < n)
 138                                                 a->cases[i] = addcase(r);
 139                                 }
 140                         return a;
 141                 }
 142                 return r;
 143
 144         case Talt:
 145                 r->next = addcase(r->next);
 146                 r->alt = addcase(r->alt);
 147                 return r;
 148
 149         case Tbegin:
 150         case Tend:
 151         case Tclass:
 152                 return r;
 153         }
 154 }
 155
 156 void
 157 str2top(char *p)
 158 {
 159         Re2 oldtop;
 160
 161         oldtop = topre;
 162         input = p;
 163         if (*p == '\0')
 164                 yyerror("empty pattern");       /* can't be a file name here */
 165         if (!flags['f'])
 166                 pattern = p;
 167         topre.beg = 0;
 168         topre.end = 0;
 169         yyparse();
 170         gen++;
 171         if(topre.beg == 0)
 172                 yyerror("syntax");
 173         if(oldtop.beg)
 174                 topre = re2or(oldtop, topre);
 175 }
 176
 177 void
 178 appendnext(Re *a, Re *b)
 179 {
 180         Re *n;
 181
 182         while(n = a->next)
 183                 a = n;
 184         a->next = b;
 185 }
 186
 187 void
 188 patchnext(Re *a, Re *b)
 189 {
 190         Re *n;
 191
 192         while(a) {
 193                 n = a->next;
 194                 a->next = b;
 195                 a = n;
 196         }
 197 }
 198
 199 int
 200 getrec(void)
 201 {
 202         int c;
 203
 204         if(flags['f']) {
 205                 c = Bgetc(rein);
 206                 if(c <= 0)
 207                         return 0;
 208         } else
 209                 c = *input++ & 0xff;
 210         if(flags['i'] && c >= 'A' && c <= 'Z')
 211                 c += 'a'-'A';
 212         if(c == '\n')
 213                 lineno++;
 214         return c;
 215 }
 216
 217 Re2
 218 re2cat(Re2 a, Re2 b)
 219 {
 220         Re2 c;
 221
 222         c.beg = a.beg;
 223         c.end = b.end;
 224         patchnext(a.end, b.beg);
 225         return c;
 226 }
 227
 228 Re2
 229 re2star(Re2 a)
 230 {
 231         Re2 c;
 232
 233         c.beg = ral(Talt);
 234         c.beg->alt = a.beg;
 235         patchnext(a.end, c.beg);
 236         c.end = c.beg;
 237         return c;
 238 }
 239
 240 Re2
 241 re2or(Re2 a, Re2 b)
 242 {
 243         Re2 c;
 244
 245         c.beg = ral(Tor);
 246         c.beg->alt = b.beg;
 247         c.beg->next = a.beg;
 248         c.end = b.end;
 249         appendnext(c.end,  a.end);
 250         return c;
 251 }
 252
 253 Re2
 254 re2char(int c0, int c1)
 255 {
 256         Re2 c;
 257
 258         c.beg = ral(Tclass);
 259         c.beg->lo = c0 & 0xff;
 260         c.beg->hi = c1 & 0xff;
 261         c.end = c.beg;
 262         return c;
 263 }
 264
 265 void
 266 reprint1(Re *a)
 267 {
 268         int i, j;
 269
 270 loop:
 271         if(a == 0)
 272                 return;
 273         if(a->gen == gen)
 274                 return;
 275         a->gen = gen;
 276         print("%p: ", a);
 277         switch(a->type) {
 278         default:
 279                 print("type %d\n", a->type);
 280                 error("print1 type");
 281
 282         case Tcase:
 283                 print("case ->%p\n", a->next);
 284                 for(i=0; i<256; i++)
 285                         if(a->cases[i]) {
 286                                 for(j=i+1; j<256; j++)
 287                                         if(a->cases[i] != a->cases[j])
 288                                                 break;
 289                                 print(" [%.2x-%.2x] ->%p\n", i, j-1, a->cases[i]);
 290                                 i = j-1;
 291                         }
 292                 for(i=0; i<256; i++)
 293                         reprint1(a->cases[i]);
 294                 break;
 295
 296         case Tbegin:
 297                 print("^ ->%p\n", a->next);
 298                 break;
 299
 300         case Tend:
 301                 print("$ ->%p\n", a->next);
 302                 break;
 303
 304         case Tclass:
 305                 print("[%.2x-%.2x] ->%p\n", a->lo, a->hi, a->next);
 306                 break;
 307
 308         case Tor:
 309         case Talt:
 310                 print("| %p ->%p\n", a->alt, a->next);
 311                 reprint1(a->alt);
 312                 break;
 313         }
 314         a = a->next;
 315         goto loop;
 316 }
 317
 318 void
 319 reprint(char *s, Re *r)
 320 {
 321         print("%s:\n", s);
 322         gen++;
 323         reprint1(r);
 324         print("\n\n");
 325 }