source: trunk/sys/dietlibc/rx.c @ 291

Last change on this file since 291 was 1, checked in by alain, 8 years ago

First import

File size: 16.6 KB
Line 
1#define NDEBUG
2#include <regex.h>
3#include <stdlib.h>
4#include <string.h>
5#include <ctype.h>
6#include <string.h>
7#include <assert.h>
8
9#if !defined(__x86_64__)
10#undef WANT_REGEX_JIT
11#endif
12
13/* this is ugly.
14 * the idea is to build a parse tree, then do some poor man's OOP with a
15 * generic matcher function call that is always that the start of each
16 * record, and a next pointer.  When the parse tree is done, we need to
17 * recursively set the next pointers to point to the part of the parse
18 * tree that needs to match next.
19 * This is the prototype of the generic match function call pointer.
20 * The first argument is the "this" pointer, the second is the text to
21 * be matched against, ofs is the offset from the start of the matched
22 * text (so we can match "^") and matches is an array where match
23 * positions are stored. */
24/* now declared in regex.h: */
25/* typedef int (*matcher)(void*,const char*,int ofs,regmatch_t* matches,int plus,int eflags); */
26
27/* one would think that this is approach is an order of magnitude slower
28 * than the standard NFA approach, but it isn't.  The busybox grep took
29 * 0.26 seconds for a fixed string compared to 0.19 seconds for the
30 * glibc regex. */
31
32/* first part: parse a regex into a parse tree */
33struct bracketed {
34  unsigned int cc[32];
35};
36
37/* now declared in regex.h:
38struct regex {
39  matcher m;
40  void* next;
41  int pieces;
42  int num;
43  struct branch *b;
44}; */
45
46struct string {
47  char* s;
48  size_t len;
49};
50
51struct atom {
52  matcher m;
53  void* next;
54  enum { ILLEGAL, EMPTY, REGEX, BRACKET, ANY, LINESTART, LINEEND, WORDSTART, WORDEND, CHAR, STRING, BACKREF, } type;
55  int bnum;
56  union {
57    struct regex r;
58    struct bracketed b;
59    char c;
60    struct string s;
61  } u;
62};
63
64struct piece {
65  matcher m;
66  void* next;
67  struct atom a;
68  unsigned int min,max;
69};
70
71struct branch {
72  matcher m;
73  void* next;
74  int num;
75  struct piece *p;
76};
77
78static void clearcc(unsigned int* x) {
79  memset(x,0,sizeof(struct bracketed));
80}
81
82static void setcc(unsigned int* x,unsigned int bit) {
83  x[bit/32]|=(1<<((bit%32)-1));
84}
85
86static int issetcc(unsigned int* x,unsigned int bit) {
87  return x[bit/32] & (1<<((bit%32)-1));
88}
89
90static const char* parsebracketed(struct bracketed*__restrict__ b,const char*__restrict__ s,regex_t*__restrict__ rx) {
91  const char* t;
92  int i,negflag=0;
93  if (*s!='[') return s;
94  t=s+1;
95  clearcc(b->cc);
96  if (*t=='^') { negflag=1; ++t; }
97  do {
98    if (*t==0) return s;
99    setcc(b->cc,rx->cflags&REG_ICASE?tolower(*t):*t);
100    if (t[1]=='-' && t[2]!=']') {
101      for (i=*t+1; i<=t[2]; ++i) setcc(b->cc,rx->cflags&REG_ICASE?tolower(i):i);
102      t+=2;
103    }
104    ++t;
105  } while (*t!=']');
106  if (negflag) for (i=0; i<32; ++i) b->cc[i]=~b->cc[i];
107  return t+1;
108}
109
110static const char* parseregex(struct regex* r,const char* s,regex_t* rx);
111
112static int matchatom_CHAR(void*__restrict__ x,const unsigned char*__restrict__ s,int ofs,struct __regex_t*__restrict__ preg,int plus,int eflags) {
113  register struct atom* a=(struct atom*)x;
114#ifdef DEBUG
115    printf("matching atom CHAR %c against \"%.20s\"\n",a->u.c,s);
116#endif
117  if (*s!=a->u.c) return -1;
118  if (a->next)
119    return ((struct atom*)(a->next))->m(a->next,(const char*)s+1,ofs+1,preg,plus+1,eflags);
120  else
121    return plus+1;
122}
123
124static int matchatom_CHAR_ICASE(void*__restrict__ x,const unsigned char*__restrict__ s,int ofs,struct __regex_t*__restrict__ preg,int plus,int eflags) {
125  register struct atom* a=(struct atom*)x;
126#ifdef DEBUG
127    printf("matching atom CHAR_ICASE %c against \"%.20s\"\n",a->u.c,s);
128#endif
129  if (tolower(*s)!=a->u.c) return -1;
130  if (a->next)
131    return ((struct atom*)(a->next))->m(a->next,(const char*)s+1,ofs+1,preg,plus+1,eflags);
132  else
133    return plus+1;
134}
135
136static int matchatom(void*__restrict__ x,const unsigned char*__restrict__ s,int ofs,struct __regex_t*__restrict__ preg,int plus,int eflags) {
137  register struct atom* a=(struct atom*)x;
138  int matchlen=0;
139  assert(a->type!=ILLEGAL);
140  switch (a->type) {
141  case EMPTY:
142#ifdef DEBUG
143    printf("matching atom EMPTY against \"%.20s\"\n",s);
144    printf("a->bnum is %d\n",a->bnum);
145#endif
146    if (a->bnum>=0) preg->l[a->bnum].rm_so=preg->l[a->bnum].rm_eo=ofs;
147    goto match;
148  case REGEX:
149#ifdef DEBUG
150    printf("matching atom REGEX against \"%.20s\"\n",s);
151    printf("a->bnum is %d\n",a->bnum);
152#endif
153    if ((matchlen=a->u.r.m(&a->u.r,(const char*)s,ofs,preg,0,eflags))>=0) {
154      assert(a->bnum>=0);
155      preg->l[a->bnum].rm_so=ofs;
156      preg->l[a->bnum].rm_eo=ofs+matchlen;
157      goto match;
158    }
159    break;
160  case BRACKET:
161#ifdef DEBUG
162    printf("matching atom BRACKET against \"%.20s\"\n",s);
163#endif
164    matchlen=1;
165    if (*s=='\n' && (preg->cflags&REG_NEWLINE)) break;
166    if (*s && issetcc(a->u.b.cc,(preg->cflags&REG_ICASE?tolower(*s):*s)))
167      goto match;
168    break;
169  case ANY:
170#ifdef DEBUG
171    printf("matching atom ANY against \"%.20s\"\n",s);
172#endif
173    if (*s=='\n' && (preg->cflags&REG_NEWLINE)) break;
174    matchlen=1;
175    if (*s) goto match;
176    break;
177  case LINESTART:
178#ifdef DEBUG
179    printf("matching atom LINESTART against \"%.20s\"\n",s);
180#endif
181    if (ofs==0 && (eflags&REG_NOTBOL)==0) {
182      goto match;
183    }
184    break;
185  case LINEEND:
186#ifdef DEBUG
187    printf("matching atom LINEEND against \"%.20s\"\n",s);
188#endif
189    if ((*s && *s!='\n') || (eflags&REG_NOTEOL)) break;
190    goto match;
191  case WORDSTART:
192#ifdef DEBUG
193    printf("matching atom WORDSTART against \"%.20s\"\n",s);
194#endif
195    if ((ofs==0 || !isalnum(s[-1])) && isalnum(*s))
196      goto match;
197    break;
198  case WORDEND:
199#ifdef DEBUG
200    printf("matching atom WORDEND against \"%.20s\"\n",s);
201#endif
202    if (ofs>0 && isalnum(s[-1]) && !isalnum(*s))
203      goto match;
204    break;
205  case CHAR:
206#ifdef DEBUG
207    printf("matching atom CHAR %c against \"%.20s\"\n",a->u.c,s);
208#endif
209    matchlen=1;
210    if (((preg->cflags&REG_ICASE)?tolower(*s):*s)==a->u.c) goto match;
211    break;
212  case STRING:
213    matchlen=a->u.s.len;
214#ifdef DEBUG
215    printf("matching atom STRING \"%.*s\" against \"%.20s\"\n",a->u.s.len,a->u.s.s,s);
216#endif
217    {
218      int i;
219      if (preg->cflags&REG_ICASE) {
220        for (i=0; i<matchlen; ++i)
221          if (tolower(s[i]) != a->u.s.s[i]) return -1;
222      } else {
223        for (i=0; i<matchlen; ++i)
224          if (s[i] != a->u.s.s[i]) return -1;
225      }
226    }
227    goto match;
228    break;
229  case BACKREF:
230    matchlen=preg->l[(unsigned char)(a->u.c)].rm_eo-preg->l[(unsigned char)(a->u.c)].rm_so;
231#ifdef DEBUG
232    printf("matching atom BACKREF %d (\"%.*s\") against \"%.20s\"\n",a->u.c,matchlen,s-ofs+preg->l[a->u.c].rm_so,s);
233#endif
234    if (memcmp(s-ofs+preg->l[(unsigned char)(a->u.c)].rm_so,s,matchlen)==0) goto match;
235    break;
236  }
237  return -1;
238match:
239  if (a->next)
240    return ((struct atom*)(a->next))->m(a->next,(const char*)s+matchlen,ofs+matchlen,preg,plus+matchlen,eflags);
241  else
242    return plus+matchlen;
243}
244
245static const char* parseatom(struct atom*__restrict__ a,const char*__restrict__ s,regex_t*__restrict__ rx) {
246  const char *tmp;
247  a->m=(matcher)matchatom;
248  a->bnum=-1;
249  switch (*s) {
250  case '(':
251    a->bnum=++rx->brackets;
252    if (s[1]==')') {
253      a->type=EMPTY;
254      return s+2;
255    }
256    a->type=REGEX;
257    tmp=parseregex(&a->u.r,s+1,rx);
258    if (*tmp==')')
259      return tmp+1;
260  case 0:
261  case '|':
262  case ')':
263    return s;
264  case '[':
265    a->type=BRACKET;
266    if ((tmp=parsebracketed(&a->u.b,s,rx))!=s)
267      return tmp;
268    return s;
269  case '.':
270    a->type=ANY;
271    break;
272  case '^':
273    a->type=LINESTART;
274    break;
275  case '$':
276    a->type=LINEEND;
277    break;
278  case '\\':
279    if (!*++s) return s;
280    if (*s=='<') {
281      a->type=WORDSTART;
282      break;
283    } else if (*s=='>') {
284      a->type=WORDEND;
285      break;
286    } else if (*s>='1' && *s<=(rx->brackets+'1') && ((rx->cflags&REG_EXTENDED)==0)) {
287      a->type=BACKREF;
288      a->u.c=*s-'0';
289      break;
290    }
291    /* fall through */
292  default:
293    a->type=CHAR;
294    if (rx->cflags&REG_ICASE) {
295      a->u.c=tolower(*s);
296      a->m=(matcher)matchatom_CHAR_ICASE;
297    } else {
298      a->u.c=*s;
299      a->m=(matcher)matchatom_CHAR;
300    }
301    /* optimization: if we have a run of CHAR, make it into a STRING */
302    {
303      size_t i;
304      for (i=1; s[i] && !strchr("(|)[.^$\\*+?{",s[i]); ++i) ;
305      if (!strchr("*+?{",s[i])) --i;
306      if (i>2) {
307        a->m=(matcher)matchatom;
308        a->type=STRING;
309        a->u.s.len=i;
310        if (!(a->u.s.s=malloc(i+1))) return s;
311        memcpy(a->u.s.s,s,i);
312        a->u.s.s[i]=0;
313        return s+i;
314      }
315    }
316    break;
317  }
318  return s+1;
319}
320
321/* needs to do "greedy" matching, i.e. match as often as possible */
322static int matchpiece(void*__restrict__ x,const char*__restrict__ s,int ofs,struct __regex_t*__restrict__ preg,int plus,int eflags) {
323  register struct piece* a=(struct piece*)x;
324  int matchlen=0;
325  int tmp=0,num=0;
326  unsigned int *offsets;
327  assert(a->max>0 && a->max<1000);
328#ifdef DEBUG
329  printf("alloca(%d)\n",sizeof(int)*a->max);
330#endif
331  offsets=alloca(sizeof(int)*a->max);
332  offsets[0]=0;
333//  printf("allocating %d offsets...\n",a->max);
334//  printf("matchpiece \"%s\"...\n",s);
335  /* first, try to match the atom as often as possible, up to a->max times */
336  if (a->max == 1 && a->min == 1)
337    return a->a.m(&a->a,s+matchlen,ofs+matchlen,preg,0,eflags);
338  while ((unsigned int)num<a->max) {
339    void* save=a->a.next;
340    a->a.next=0;
341    if ((tmp=a->a.m(&a->a,s+matchlen,ofs+matchlen,preg,0,eflags))>=0) {
342      a->a.next=save;
343      ++num;
344      matchlen+=tmp;
345//      printf("setting offsets[%d] to %d\n",num,tmp);
346      offsets[num]=tmp;
347    } else {
348      a->a.next=save;
349      break;
350    }
351  }
352  if ((unsigned int)num<a->min) return -1;              /* already at minimum matches; signal mismatch */
353  /* then, while the rest does not match, back off */
354  for (;num>=0;) {
355    if (a->next)
356      tmp=((struct atom*)(a->next))->m(a->next,s+matchlen,ofs+matchlen,preg,plus+matchlen,eflags);
357    else
358      tmp=plus+matchlen;
359    if (tmp>=0) break;  /* it did match; don't back off any further */
360//    printf("using offsets[%d] (%d)\n",num,offsets[num]);
361    matchlen-=offsets[num];
362    --num;
363  }
364  return tmp;
365}
366
367static const char* parsepiece(struct piece*__restrict__ p,const char*__restrict__ s,regex_t*__restrict__ rx) {
368  const char* tmp=parseatom(&p->a,s,rx);
369  if (tmp==s) return s;
370  p->m=matchpiece;
371  p->min=p->max=1;
372  switch (*tmp) {
373  case '*': p->min=0; p->max=RE_DUP_MAX; break;
374  case '+': p->min=1; p->max=RE_DUP_MAX; break;
375  case '?': p->min=0; p->max=1; break;
376  case '{':
377    if (isdigit(*++tmp)) {
378      p->min=*tmp-'0'; p->max=RE_DUP_MAX;
379      while (isdigit(*++tmp)) p->min=p->min*10+*tmp-'0';
380      if (*tmp==',') {
381        if (isdigit(*++tmp)) {
382          p->max=*tmp-'0';
383          while (isdigit(*++tmp)) p->max=p->max*10+*tmp-'0';
384        }
385      } else
386        p->max=p->min;
387      if (*tmp!='}') return s;
388      ++tmp;
389    }
390  default:
391    return tmp;
392  }
393  return tmp+1;
394}
395
396/* trivial, just pass through */
397static int matchbranch(void*__restrict__ x,const char*__restrict__ s,int ofs,struct __regex_t*__restrict__ preg,int plus,int eflags) {
398  register struct branch* a=(struct branch*)x;
399  int tmp;
400#ifdef DEBUG
401  printf("%08p matching branch against \"%.20s\"\n",a,s);
402  printf("%p %p\n",&a->p->m,a->p->m);
403#endif
404  assert(a->p->m==matchpiece);
405  tmp=a->p->m(a->p,s,ofs,preg,plus,eflags);
406  if (tmp>=0) {
407    if (a->next)
408      return ((struct atom*)(a->next))->m(a->next,s+tmp,ofs+tmp,preg,plus+tmp,eflags);
409    else
410      return plus+tmp;
411  }
412  return -1;
413}
414
415static int matchempty(void*__restrict__ x,const char*__restrict__ s,int ofs,struct __regex_t*__restrict__ preg,int plus,int eflags) {
416  return 0;
417}
418
419static const char* parsebranch(struct branch*__restrict__ b,const char*__restrict__ s,regex_t*__restrict__ rx,int*__restrict__ pieces) {
420  struct piece p;
421  const char *tmp = NULL;
422  b->m=matchbranch;
423  b->num=0; b->p=0;
424  for (;;) {
425    if (*s=='|' && b->num==0) {
426      tmp=s+1;
427      p.a.type=EMPTY;
428      p.a.m=matchempty;
429      p.min=p.max=1;
430      p.m=matchpiece;
431    } else {
432      tmp=parsepiece(&p,s,rx);
433      if (tmp==s) return s;
434    }
435//    printf("b->p from %p to ",b->p);
436    {
437      struct piece* tmp;
438      if (!(tmp=realloc(b->p,++b->num*sizeof(p)))) return s;
439//      printf("piece realloc: %p -> %p (%d*%d)\n",b->p,tmp,b->num,sizeof(p));
440      b->p=tmp;
441    }
442//    printf("%p (size %d)\n",b->p,b->num*sizeof(p));
443    b->p[b->num-1]=p;
444//    printf("assigned piece %d in branch %p\n",b->num-1,b->p);
445    if (*tmp=='|') break;
446    s=tmp;
447  }
448  *pieces+=b->num;
449  return tmp;
450}
451
452/* try the branches one by one */
453static int matchregex(void*__restrict__ x,const char*__restrict__ s,int ofs,struct __regex_t*__restrict__ preg,int plus,int eflags) {
454  register struct regex* a=(struct regex*)x;
455  int i,tmp;
456#ifdef DEBUG
457  printf("%08p matching regex against \"%.20s\"\n",a,s);
458#endif
459  for (i=0; i<a->num; ++i) {
460    assert(a->b[i].m==matchbranch);
461    tmp=a->b[i].m(&a->b[i],s,ofs,preg,plus,eflags);
462    if (tmp>=0) {
463      if (a->next)
464        return ((struct atom*)(a->next))->m(a->next,s+tmp,ofs+tmp,preg,plus+tmp,eflags);
465      else
466        return plus+tmp;
467    }
468  }
469  return -1;
470}
471
472static const char* parseregex(struct regex*__restrict__ r,const char*__restrict__ s,regex_t*__restrict__ p) {
473  struct branch b;
474  const char *tmp;
475  r->m=matchregex;
476  r->num=0; r->b=0; r->pieces=0;
477  p->brackets=0;
478  b.next=0;
479  if (*s==')' || !*s) {
480    r->m=matchempty;
481    return s;
482  }
483  for (;;) {
484    tmp=parsebranch(&b,s,p,&r->pieces);
485    if (tmp==s && *s!=')') return s;
486//    printf("r->b from %p to ",r->b);
487    {
488      struct branch* tmp;
489      if (!(tmp=realloc(r->b,++r->num*sizeof(b)))) return s;
490//      printf("branch realloc: %p -> %p (%d*%d)\n",r->b,tmp,r->num,sizeof(b));
491      r->b=tmp;
492    }
493//    printf("%p (size %d)\n",r->b,r->num*sizeof(b));
494    r->b[r->num-1]=b;
495    if (*s==')') {
496      r->b[r->num-1].m=matchempty;
497      return s;
498    }
499//    printf("assigned branch %d at %p\n",r->num-1,r->b);
500    s=tmp;
501    if (*s==')') return s;
502    if (*s=='|') ++s;
503  }
504  return tmp;
505}
506
507
508/* The matcher relies on the presence of next pointers, of which the
509 * parser does not know the correct destination.  So we need an
510 * additional pass through the data structure that sets the next
511 * pointers correctly. */
512static void regex_putnext(struct regex* r,void* next);
513
514static void atom_putnext(struct atom*__restrict__ a,void*__restrict__ next) {
515  a->next=next;
516  if (a->type==REGEX)
517    regex_putnext(&a->u.r,0);
518}
519
520static void piece_putnext(struct piece*__restrict__ p,void*__restrict__ next) {
521  p->next=next;
522  atom_putnext(&p->a,next);
523}
524
525static void branch_putnext(struct branch*__restrict__ b,void*__restrict__ next) {
526  int i;
527  if (b->m!=matchempty) {
528    for (i=0; i<b->num-1; ++i) {
529      if (b->p[i+1].min==1 && b->p[i+1].max==1)
530/* shortcut: link directly to next atom if it's a piece with min=max=1 */
531        piece_putnext(&b->p[i],&b->p[i+1].a);
532      else
533        piece_putnext(&b->p[i],&b->p[i+1]);
534    }
535    piece_putnext(&b->p[i],0);
536  }
537  b->next=next;
538}
539
540static void regex_putnext(struct regex*__restrict__ r,void*__restrict__ next) {
541  int i;
542  for (i=0; i<r->num; ++i)
543    branch_putnext(&r->b[i],next);
544  r->next=next;
545}
546
547
548
549int regcomp(regex_t*__restrict__ preg, const char*__restrict__ regex, int cflags) {
550  const char* t;
551  preg->cflags=cflags;
552  t=parseregex(&preg->r,regex,preg);
553  if (t==regex && *regex!=0) return -1;
554  regex_putnext(&preg->r,0);
555  return 0;
556}
557
558int regexec(const regex_t*__restrict__ preg, const char*__restrict__ string, size_t nmatch, regmatch_t pmatch[], int eflags) {
559  int matched;
560  const char *orig=string;
561  assert(preg->brackets+1>0 && preg->brackets<1000);
562  for (matched=0; (unsigned int)matched<nmatch; ++matched)
563    pmatch[matched].rm_so=-1;
564#ifdef DEBUG
565  printf("alloca(%d)\n",sizeof(regmatch_t)*(preg->brackets+3));
566#endif
567  ((regex_t*)preg)->l=alloca(sizeof(regmatch_t)*(preg->brackets+3));
568  while (1) {
569    matched=preg->r.m((void*)&preg->r,string,string-orig,(regex_t*)preg,0,eflags);
570//    printf("ebp on stack = %x\n",stack[1]);
571    if (matched>=0) {
572      preg->l[0].rm_so=string-orig;
573      preg->l[0].rm_eo=string-orig+matched;
574      if ((preg->cflags&REG_NOSUB)==0) memcpy(pmatch,preg->l,nmatch*sizeof(regmatch_t));
575      return 0;
576    }
577    if (!*string) break;
578    ++string; eflags|=REG_NOTBOL;
579  }
580  return REG_NOMATCH;
581}
582
583static void __regfree(struct regex* r) {
584  int i;
585  for (i=0; i<r->num; ++i) {
586    int j,k;
587    k=r->b[i].num;
588    for (j=0; j<k; ++j)
589      if (r->b[i].p[j].a.type==REGEX)
590        __regfree(&r->b[i].p[j].a.u.r);
591      else if (r->b[i].p[j].a.type==STRING)
592        free(r->b[i].p[j].a.u.s.s);
593    free(r->b[i].p);
594  }
595  free(r->b);
596}
597
598void regfree(regex_t* preg) {
599  __regfree(&preg->r);
600  memset(preg,0,sizeof(regex_t));
601}
602
603size_t regerror(int errcode, const regex_t*__restrict__ preg, char*__restrict__ errbuf, size_t errbuf_size) {
604  strncpy(errbuf,"invalid regular expression (sorry)",errbuf_size);
605  return strlen(errbuf);
606}
607
608
609
610
611#if 0
612int main() {
613  struct regex r;
614  int bnum=-1;
615  const char* t=parseregex(&r,"^a*ab$",&bnum);
616  regex_putnext(&r,0);
617  printf("%d pieces, %s\n",r.pieces,t);
618  printf("%d\n",r.m(&r,"aaab",0,0,0));
619  return 0;
620}
621#endif
Note: See TracBrowser for help on using the repository browser.