sys/src/libregexp/rregexec.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <regexp.h>
   4 #include "regimpl.h"
   5
   6 typedef struct RethreadQ RethreadQ;
   7 struct RethreadQ {
   8         Rethread *head;
   9         Rethread **tail;
  10 };
  11
  12 int
  13 rregexec(Reprog *p, Rune *str, Resub *sem, int msize)
  14 {
  15         RethreadQ lists[2], *clist, *nlist, *tmp;
  16         Rethread *t, *next, *pool, *avail;
  17         Reinst *ci;
  18         Rune *rsp, *rep, endr, r;
  19         int matchgen, gen;
  20
  21         memset(p->threads, 0, sizeof(Rethread)*p->nthr);
  22         if(msize > NSUBEXPM)
  23                 msize = NSUBEXPM;
  24         if(p->startinst->gen != 0) {
  25                 for(ci = p->startinst; ci < p->startinst + p->len; ci++)
  26                         ci->gen = 0;
  27         }
  28
  29         clist = lists;
  30         clist->head = nil;
  31         clist->tail = &clist->head;
  32         nlist = lists + 1;
  33         nlist->head = nil;
  34         nlist->tail = &nlist->head;
  35
  36         pool = p->threads;
  37         avail = nil;
  38         gen = matchgen = 0;
  39
  40         rsp = str;
  41         rep = nil;
  42         endr = L'\0';
  43         if(sem != nil && msize > 0) {
  44                 if(sem->rsp != nil)
  45                         rsp = sem->rsp;
  46                 if(sem->rep != nil && *sem->rep != L'\0') {
  47                         rep = sem->rep;
  48                         endr = *sem->rep;
  49                         *sem->rep = '\0';
  50                 }
  51         }
  52
  53         for(r = L'☺'; r != L'\0'; rsp++) {
  54                 r = *rsp;
  55                 gen++;
  56                 if(matchgen == 0) {
  57                         if(avail == nil) {
  58                                 assert(pool < p->threads + p->nthr);
  59                                 t = pool++;
  60                         } else {
  61                                 t = avail;
  62                                 avail = avail->next;
  63                         }
  64                         t->i = p->startinst;
  65                         if(msize > 0)
  66                                 memset(t->sem, 0, sizeof(Resub)*msize);
  67                         t->next = nil;
  68                         t->gen = gen;
  69                         *clist->tail = t;
  70                         clist->tail = &t->next;
  71                 }
  72                 t = clist->head;
  73                 if(t == nil)
  74                         break;
  75                 ci = t->i;
  76 Again:
  77                 if(ci->gen == gen)
  78                         goto Done;
  79                 ci->gen = gen;
  80                 switch(ci->op) {
  81                 case ORUNE:
  82                         if(r != ci->r)
  83                                 goto Done;
  84                 case OANY: /* fallthrough */
  85                         next = t->next;
  86                         t->i = ci + 1;
  87                         t->next = nil;
  88                         *nlist->tail = t;
  89                         nlist->tail = &t->next;
  90                         goto Next;
  91                 case OCLASS:
  92                 Class:
  93                         if(r < ci->r)
  94                                 goto Done;
  95                         if(r > ci->r1) {
  96                                 ci++;
  97                                 goto Class;
  98                         }
  99                         next = t->next;
 100                         t->i = ci->a;
 101                         t->next = nil;
 102                         *nlist->tail = t;
 103                         nlist->tail = &t->next;
 104                         goto Next;
 105                 case ONOTNL:
 106                         if(r != L'\n') {
 107                                 ci++;
 108                                 goto Again;
 109                         }
 110                         goto Done;
 111                 case OBOL:
 112                         if(rsp == str || rsp[-1] == L'\n') {
 113                                 ci++;
 114                                 goto Again;
 115                         }
 116                         goto Done;
 117                 case OEOL:
 118                         if(r == L'\n' || r == L'\0' && rep == nil) {
 119                                 ci++;
 120                                 goto Again;
 121                         }
 122                         goto Done;
 123                 case OJMP:
 124                         ci = ci->a;
 125                         goto Again;
 126                 case OSPLIT:
 127                         if(avail == nil) {
 128                                 assert(pool < p->threads + p->nthr);
 129                                 next = pool++;
 130                         } else {
 131                                 next = avail;
 132                                 avail = avail->next;
 133                         }
 134                         next->i = ci->b;
 135                         if(msize > 0)
 136                                 memcpy(next->sem, t->sem, sizeof(Resub)*msize);
 137                         next->next = t->next;
 138                         next->gen = t->gen;
 139                         t->next = next;
 140                         ci = ci->a;
 141                         goto Again;
 142                 case OSAVE:
 143                         if(ci->sub < msize)
 144                                 t->sem[ci->sub].rsp = rsp;
 145                         ci++;
 146                         goto Again;
 147                 case OUNSAVE:
 148                         if(ci->sub == 0) {
 149                                 matchgen = t->gen;
 150                                 if(sem != nil && msize > 0) {
 151                                         memcpy(sem, t->sem, sizeof(Resub)*msize);
 152                                         sem->rep = rsp;
 153                                 }
 154                                 goto Done;
 155                         }
 156                         if(ci->sub < msize)
 157                                 t->sem[ci->sub].rep = rsp;
 158                         ci++;
 159                         goto Again;
 160                 Done:
 161                         next = t->next;
 162                         t->next = avail;
 163                         avail = t;
 164                 Next:
 165                         if(next == nil)
 166                                 break;
 167                         if(matchgen && next->gen > matchgen) {
 168                                 *clist->tail = avail;
 169                                 avail = next;
 170                                 break;
 171                         }
 172                         t = next;
 173                         ci = t->i;
 174                         goto Again;
 175                 }
 176                 tmp = clist;
 177                 clist = nlist;
 178                 nlist = tmp;
 179                 nlist->head = nil;
 180                 nlist->tail = &nlist->head;
 181         }
 182         if(rep != nil)
 183                 *rep = endr;
 184         return matchgen > 0 ? 1 : 0;
 185 }