1 /*********************************************************************** 2 * * 3 * This software is part of the ast package * 4 * Copyright (c) 1985-2007 AT&T Knowledge Ventures * 5 * and is licensed under the * 6 * Common Public License, Version 1.0 * 7 * by AT&T Knowledge Ventures * 8 * * 9 * A copy of the License is available at * 10 * http://www.opensource.org/licenses/cpl1.0.txt * 11 * (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) * 12 * * 13 * Information and Software Systems Research * 14 * AT&T Research * 15 * Florham Park NJ * 16 * * 17 * Glenn Fowler <gsf@research.att.com> * 18 * David Korn <dgk@research.att.com> * 19 * Phong Vo <kpv@research.att.com> * 20 * * 21 ***********************************************************************/ 22 #pragma prototyped 23 /* 24 * Glenn Fowler 25 * AT&T Research 26 * 27 * return strmatch() expression given REG_AUGMENTED RE 28 * 0 returned for invalid RE 29 */ 30 31 #include <ast.h> 32 33 char* 34 fmtmatch(const char* as) 35 { 36 register char* s = (char*)as; 37 register int c; 38 register char* t; 39 register char** p; 40 register char* b; 41 char* x; 42 char* y; 43 char* z; 44 int a; 45 int e; 46 int n; 47 char* buf; 48 char* stack[32]; 49 50 c = 3 * (strlen(s) + 1); 51 buf = fmtbuf(c); 52 t = b = buf + 3; 53 p = stack; 54 if (a = *s == '^') 55 s++; 56 e = 0; 57 for (;;) 58 { 59 switch (c = *s++) 60 { 61 case 0: 62 break; 63 case '\\': 64 if (!(c = *s++)) 65 return 0; 66 switch (*s) 67 { 68 case '*': 69 case '+': 70 case '?': 71 *t++ = *s++; 72 *t++ = '('; 73 *t++ = '\\'; 74 *t++ = c; 75 c = ')'; 76 break; 77 case '|': 78 case '&': 79 if (c == '(') 80 { 81 *t++ = c; 82 c = *s++; 83 goto logical; 84 } 85 break; 86 case '{': 87 case '}': 88 break; 89 default: 90 *t++ = '\\'; 91 break; 92 } 93 *t++ = c; 94 continue; 95 case '[': 96 x = t; 97 *t++ = c; 98 if ((c = *s++) == '^') 99 { 100 *t++ = '!'; 101 c = *s++; 102 } 103 else if (c == '!') 104 { 105 *t++ = '\\'; 106 *t++ = c; 107 c = *s++; 108 } 109 for (;;) 110 { 111 if (!(*t++ = c)) 112 return 0; 113 if (c == '\\') 114 *t++ = c; 115 if ((c = *s++) == ']') 116 { 117 *t++ = c; 118 break; 119 } 120 } 121 switch (*s) 122 { 123 case '*': 124 case '+': 125 case '?': 126 for (y = t + 2, t--; t >= x; t--) 127 *(t + 2) = *t; 128 *++t = *s++; 129 *++t = '('; 130 t = y; 131 *t++ = ')'; 132 break; 133 } 134 continue; 135 case '(': 136 if (p >= &stack[elementsof(stack)]) 137 return 0; 138 *p++ = t; 139 if (*s == '?') 140 { 141 s++; 142 if (*s == 'K' && *(s + 1) == ')') 143 { 144 s += 2; 145 p--; 146 while (*t = *s) 147 t++, s++; 148 continue; 149 } 150 *t++ = '~'; 151 } 152 else 153 *t++ = '@'; 154 *t++ = '('; 155 continue; 156 case ')': 157 if (p == stack) 158 return 0; 159 p--; 160 *t++ = c; 161 switch (*s) 162 { 163 case 0: 164 break; 165 case '*': 166 case '+': 167 case '?': 168 case '!': 169 **p = *s++; 170 if (*s == '?') 171 { 172 s++; 173 x = *p + 1; 174 for (y = ++t; y > x; y--) 175 *y = *(y - 1); 176 *x = '-'; 177 } 178 continue; 179 case '{': 180 for (z = s; *z != '}'; z++) 181 if (!*z) 182 return 0; 183 n = z - s; 184 if (*++z == '?') 185 n++; 186 x = *p + n; 187 for (y = t += n; y > x; y--) 188 *y = *(y - n); 189 for (x = *p; s < z; *x++ = *s++); 190 if (*s == '?') 191 { 192 s++; 193 *x++ = '-'; 194 } 195 continue; 196 default: 197 continue; 198 } 199 break; 200 case '.': 201 switch (*s) 202 { 203 case 0: 204 *t++ = '?'; 205 break; 206 case '*': 207 s++; 208 *t++ = '*'; 209 e = !*s; 210 continue; 211 case '+': 212 s++; 213 *t++ = '?'; 214 *t++ = '*'; 215 continue; 216 case '?': 217 s++; 218 *t++ = '?'; 219 *t++ = '('; 220 *t++ = '?'; 221 *t++ = ')'; 222 continue; 223 default: 224 *t++ = '?'; 225 continue; 226 } 227 break; 228 case '*': 229 case '+': 230 case '?': 231 case '{': 232 n = *(t - 1); 233 if (t == b || n == '(' || n == '|') 234 return 0; 235 *(t - 1) = c; 236 if (c == '{') 237 { 238 for (z = s; *z != '}'; z++) 239 if (!*z) 240 return 0; 241 for (; s <= z; *t++ = *s++); 242 } 243 if (*s == '?') 244 { 245 s++; 246 *t++ = '-'; 247 } 248 *t++ = '('; 249 *t++ = n; 250 *t++ = ')'; 251 continue; 252 case '|': 253 case '&': 254 if (t == b || *(t - 1) == '(') 255 return 0; 256 logical: 257 if (!*s || *s == ')') 258 return 0; 259 if (p == stack && b == buf + 3) 260 { 261 *--b = '('; 262 *--b = '@'; 263 } 264 *t++ = c; 265 continue; 266 case '$': 267 if (e = !*s) 268 break; 269 /*FALLTHROUGH*/ 270 default: 271 *t++ = c; 272 continue; 273 } 274 break; 275 } 276 if (p != stack) 277 return 0; 278 if (b != buf + 3) 279 *t++ = ')'; 280 if (!a && (*b != '*' || *(b + 1) == '(' || (*(b + 1) == '-' || *(b + 1) == '~') && *(b + 2) == '(')) 281 *--b = '*'; 282 if (!e) 283 *t++ = '*'; 284 *t = 0; 285 return b; 286 } 287