rregexec.c (4730B)
1 #include "plan9.h" 2 #include "regexp9.h" 3 #include "regcomp.h" 4 5 /* 6 * return 0 if no match 7 * >0 if a match 8 * <0 if we ran out of _relist space 9 */ 10 static int 11 rregexec1(Reprog *progp, /* program to run */ 12 Rune *bol, /* string to run machine on */ 13 Resub *mp, /* subexpression elements */ 14 int ms, /* number of elements at mp */ 15 Reljunk *j) 16 { 17 int flag=0; 18 Reinst *inst; 19 Relist *tlp; 20 Rune *s; 21 int i, checkstart; 22 Rune r, *rp, *ep; 23 Relist* tl; /* This list, next list */ 24 Relist* nl; 25 Relist* tle; /* ends of this and next list */ 26 Relist* nle; 27 int match; 28 Rune *p; 29 30 match = 0; 31 checkstart = j->startchar; 32 if(mp) 33 for(i=0; i<ms; i++) { 34 mp[i].s.rsp = 0; 35 mp[i].e.rep = 0; 36 } 37 j->relist[0][0].inst = 0; 38 j->relist[1][0].inst = 0; 39 40 /* Execute machine once for each character, including terminal NUL */ 41 s = j->rstarts; 42 do{ 43 44 /* fast check for first char */ 45 if(checkstart) { 46 switch(j->starttype) { 47 case RUNE: 48 p = runestrchr(s, j->startchar); 49 if(p == 0 || p == j->reol) 50 return match; 51 s = p; 52 break; 53 case BOL: 54 if(s == bol) 55 break; 56 p = runestrchr(s, '\n'); 57 if(p == 0 || s == j->reol) 58 return match; 59 s = p+1; 60 break; 61 } 62 } 63 64 r = *s; 65 66 /* switch run lists */ 67 tl = j->relist[flag]; 68 tle = j->reliste[flag]; 69 nl = j->relist[flag^=1]; 70 nle = j->reliste[flag]; 71 nl->inst = 0; 72 73 /* Add first instruction to current list */ 74 _rrenewemptythread(tl, progp->startinst, ms, s); 75 76 /* Execute machine until current list is empty */ 77 for(tlp=tl; tlp->inst; tlp++){ 78 for(inst=tlp->inst; ; inst = inst->u2.next){ 79 switch(inst->type){ 80 case RUNE: /* regular character */ 81 if(inst->u1.r == r) 82 if(_renewthread(nl, inst->u2.next, ms, &tlp->se)==nle) 83 return -1; 84 break; 85 case LBRA: 86 tlp->se.m[inst->u1.subid].s.rsp = s; 87 continue; 88 case RBRA: 89 tlp->se.m[inst->u1.subid].e.rep = s; 90 continue; 91 case ANY: 92 if(r != '\n') 93 if(_renewthread(nl, inst->u2.next, ms, &tlp->se)==nle) 94 return -1; 95 break; 96 case ANYNL: 97 if(_renewthread(nl, inst->u2.next, ms, &tlp->se)==nle) 98 return -1; 99 break; 100 case BOL: 101 if(s == bol || *(s-1) == '\n') 102 continue; 103 break; 104 case EOL: 105 if(s == j->reol || r == 0 || r == '\n') 106 continue; 107 break; 108 case CCLASS: 109 ep = inst->u1.cp->end; 110 for(rp = inst->u1.cp->spans; rp < ep; rp += 2) 111 if(r >= rp[0] && r <= rp[1]){ 112 if(_renewthread(nl, inst->u2.next, ms, &tlp->se)==nle) 113 return -1; 114 break; 115 } 116 break; 117 case NCCLASS: 118 ep = inst->u1.cp->end; 119 for(rp = inst->u1.cp->spans; rp < ep; rp += 2) 120 if(r >= rp[0] && r <= rp[1]) 121 break; 122 if(rp == ep) 123 if(_renewthread(nl, inst->u2.next, ms, &tlp->se)==nle) 124 return -1; 125 break; 126 case OR: 127 /* evaluate right choice later */ 128 if(_renewthread(tlp, inst->u1.right, ms, &tlp->se) == tle) 129 return -1; 130 /* efficiency: advance and re-evaluate */ 131 continue; 132 case END: /* Match! */ 133 match = 1; 134 tlp->se.m[0].e.rep = s; 135 if(mp != 0) 136 _renewmatch(mp, ms, &tlp->se); 137 break; 138 } 139 break; 140 } 141 } 142 if(s == j->reol) 143 break; 144 checkstart = j->startchar && nl->inst==0; 145 s++; 146 }while(r); 147 return match; 148 } 149 150 static int 151 rregexec2(Reprog *progp, /* program to run */ 152 Rune *bol, /* string to run machine on */ 153 Resub *mp, /* subexpression elements */ 154 int ms, /* number of elements at mp */ 155 Reljunk *j 156 ) 157 { 158 Relist relist0[5*LISTSIZE], relist1[5*LISTSIZE]; 159 160 /* mark space */ 161 j->relist[0] = relist0; 162 j->relist[1] = relist1; 163 j->reliste[0] = relist0 + nelem(relist0) - 2; 164 j->reliste[1] = relist1 + nelem(relist1) - 2; 165 166 return rregexec1(progp, bol, mp, ms, j); 167 } 168 169 extern int 170 rregexec(Reprog *progp, /* program to run */ 171 Rune *bol, /* string to run machine on */ 172 Resub *mp, /* subexpression elements */ 173 int ms) /* number of elements at mp */ 174 { 175 Reljunk j; 176 Relist relist0[LISTSIZE], relist1[LISTSIZE]; 177 int rv; 178 179 /* 180 * use user-specified starting/ending location if specified 181 */ 182 j.rstarts = bol; 183 j.reol = 0; 184 if(mp && ms>0){ 185 if(mp->s.sp) 186 j.rstarts = mp->s.rsp; 187 if(mp->e.ep) 188 j.reol = mp->e.rep; 189 } 190 j.starttype = 0; 191 j.startchar = 0; 192 if(progp->startinst->type == RUNE && progp->startinst->u1.r < Runeself) { 193 j.starttype = RUNE; 194 j.startchar = progp->startinst->u1.r; 195 } 196 if(progp->startinst->type == BOL) 197 j.starttype = BOL; 198 199 /* mark space */ 200 j.relist[0] = relist0; 201 j.relist[1] = relist1; 202 j.reliste[0] = relist0 + nelem(relist0) - 2; 203 j.reliste[1] = relist1 + nelem(relist1) - 2; 204 205 rv = rregexec1(progp, bol, mp, ms, &j); 206 if(rv >= 0) 207 return rv; 208 rv = rregexec2(progp, bol, mp, ms, &j); 209 if(rv >= 0) 210 return rv; 211 return -1; 212 }