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