1 static char sccsid[] = "@(#)re.c 4.2 08/17/82"; 2 #include "head.h" 3 #define CBRA 1 4 #define CCHR 2 5 #define CDOT 4 6 #define CCL 6 7 #define NCCL 8 8 #define CDOL 10 9 #define CEOF 11 10 #define CKET 12 11 #define CBACK 18 12 13 #define CSTAR 01 14 15 #define LBSIZE 512 16 #define ESIZE 256 17 #define NBRA 9 18 19 char expbuf[ESIZE]; 20 int circf; 21 char *braslist[NBRA]; 22 char *braelist[NBRA]; 23 char bittab[] = { 24 1, 25 2, 26 4, 27 8, 28 16, 29 32, 30 64, 31 128 32 }; 33 34 dore() { 35 register int line; 36 register char *p; 37 38 circf = 0; 39 line = fline; 40 compile(re); 41 do { 42 if (redir) fnext(); 43 else fprev(); 44 p = fbuf; 45 while(*p++ != '\n') 46 ; 47 *--p = '\0'; 48 if (match(fbuf)) goto l1; 49 } while (fline != line); 50 error("No match"); 51 l1: *p = '\n'; 52 fprint(); 53 } 54 55 56 compile(astr) 57 char *astr; 58 { 59 register c; 60 register char *ep, *sp; 61 char *cstart; 62 char *lastep; 63 int cclcnt; 64 char bracket[NBRA], *bracketp; 65 int closed; 66 char numbra; 67 char neg; 68 69 ep = expbuf; 70 sp = astr; 71 lastep = 0; 72 bracketp = bracket; 73 closed = numbra = 0; 74 if (*sp == '^') { 75 circf++; 76 sp++; 77 } 78 for (;;) { 79 if (ep >= &expbuf[ESIZE]) 80 goto cerror; 81 if ((c = *sp++) != '*') 82 lastep = ep; 83 switch (c) { 84 85 case '\0': 86 *ep++ = CEOF; 87 return; 88 89 case '.': 90 *ep++ = CDOT; 91 continue; 92 93 case '*': 94 if (lastep==0 || *lastep==CBRA || *lastep==CKET) 95 goto defchar; 96 *lastep |= CSTAR; 97 continue; 98 99 case '$': 100 if (*sp != '\0') 101 goto defchar; 102 *ep++ = CDOL; 103 continue; 104 105 case '[': 106 if(&ep[17] >= &expbuf[ESIZE]) 107 goto cerror; 108 *ep++ = CCL; 109 neg = 0; 110 if((c = *sp++) == '^') { 111 neg = 1; 112 c = *sp++; 113 } 114 cstart = sp; 115 do { 116 if (c=='\0') 117 goto cerror; 118 if (c=='-' && sp>cstart && *sp!=']') { 119 for (c = sp[-2]; c<*sp; c++) 120 ep[c>>3] |= bittab[c&07]; 121 sp++; 122 } 123 ep[c>>3] |= bittab[c&07]; 124 } while((c = *sp++) != ']'); 125 if(neg) { 126 for(cclcnt = 0; cclcnt < 16; cclcnt++) 127 ep[cclcnt] ^= -1; 128 ep[0] &= 0376; 129 } 130 131 ep += 16; 132 133 continue; 134 135 case '\\': 136 if((c = *sp++) == '(') { 137 if(numbra >= NBRA) { 138 goto cerror; 139 } 140 *bracketp++ = numbra; 141 *ep++ = CBRA; 142 *ep++ = numbra++; 143 continue; 144 } 145 if(c == ')') { 146 if(bracketp <= bracket) { 147 goto cerror; 148 } 149 *ep++ = CKET; 150 *ep++ = *--bracketp; 151 closed++; 152 continue; 153 } 154 155 if(c >= '1' && c <= '9') { 156 if((c -= '1') >= closed) 157 goto cerror; 158 *ep++ = CBACK; 159 *ep++ = c; 160 continue; 161 } 162 163 defchar: 164 default: 165 *ep++ = CCHR; 166 *ep++ = c; 167 } 168 } 169 cerror: 170 errexit("RE error\n", (char *)NULL); 171 } 172 173 match(p1) 174 register char *p1; { 175 register char *p2; 176 register c; 177 p2 = expbuf; 178 if (circf) { 179 if (advance(p1, p2)) 180 goto found; 181 goto nfound; 182 } 183 /* fast check for first character */ 184 if (*p2==CCHR) { 185 c = p2[1]; 186 do { 187 if (*p1!=c) 188 continue; 189 if (advance(p1, p2)) 190 goto found; 191 } while (*p1++); 192 goto nfound; 193 } 194 /* regular algorithm */ 195 do { 196 if (advance(p1, p2)) 197 goto found; 198 } while (*p1++); 199 nfound: 200 return(0); 201 found: 202 return(1); 203 } 204 205 advance(lp, ep) 206 register char *lp, *ep; 207 { 208 register char *curlp; 209 char c; 210 char *bbeg; 211 int ct; 212 213 for (;;) switch (*ep++) { 214 215 case CCHR: 216 if (*ep++ == *lp++) 217 continue; 218 return(0); 219 220 case CDOT: 221 if (*lp++) 222 continue; 223 return(0); 224 225 case CDOL: 226 if (*lp=='\0') 227 continue; 228 return(0); 229 230 case CEOF: 231 return(1); 232 233 case CCL: 234 c = *lp++ & 0177; 235 if(ep[c>>3] & bittab[c & 07]) { 236 ep += 16; 237 continue; 238 } 239 return(0); 240 case CBRA: 241 braslist[*ep++] = lp; 242 continue; 243 244 case CKET: 245 braelist[*ep++] = lp; 246 continue; 247 248 case CBACK: 249 bbeg = braslist[*ep]; 250 if (braelist[*ep]==0) 251 return(0); 252 ct = braelist[*ep++] - bbeg; 253 if(ecmp(bbeg, lp, ct)) { 254 lp += ct; 255 continue; 256 } 257 return(0); 258 259 case CBACK|CSTAR: 260 bbeg = braslist[*ep]; 261 if (braelist[*ep]==0) 262 return(0); 263 ct = braelist[*ep++] - bbeg; 264 curlp = lp; 265 while(ecmp(bbeg, lp, ct)) 266 lp += ct; 267 while(lp >= curlp) { 268 if(advance(lp, ep)) return(1); 269 lp -= ct; 270 } 271 return(0); 272 273 274 case CDOT|CSTAR: 275 curlp = lp; 276 while (*lp++); 277 goto star; 278 279 case CCHR|CSTAR: 280 curlp = lp; 281 while (*lp++ == *ep); 282 ep++; 283 goto star; 284 285 case CCL|CSTAR: 286 curlp = lp; 287 do { 288 c = *lp++ & 0177; 289 } while(ep[c>>3] & bittab[c & 07]); 290 ep += 16; 291 goto star; 292 293 star: 294 if(--lp == curlp) { 295 continue; 296 } 297 298 if(*ep == CCHR) { 299 c = ep[1]; 300 do { 301 if(*lp != c) 302 continue; 303 if(advance(lp, ep)) 304 return(1); 305 } while(lp-- > curlp); 306 return(0); 307 } 308 309 do { 310 if (advance(lp, ep)) 311 return(1); 312 } while (lp-- > curlp); 313 return(0); 314 315 default: 316 errexit("RE botch\n", (char *)NULL); 317 } 318 } 319 ecmp(a, b, count) 320 char *a, *b; 321 { 322 register cc = count; 323 while(cc--) 324 if(*a++ != *b++) return(0); 325 return(1); 326 } 327 328 329 errexit(s) 330 char *s; { 331 error(s); 332 return; 333 } 334