1 /***********************************************************************
2 *                                                                      *
3 *               This software is part of the ast package               *
4 *          Copyright (c) 1985-2011 AT&T Intellectual Property          *
5 *                      and is licensed under the                       *
6 *                 Eclipse Public License, Version 1.0                  *
7 *                    by AT&T Intellectual Property                     *
8 *                                                                      *
9 *                A copy of the License is available at                 *
10 *          http://www.eclipse.org/org/documents/epl-v10.html           *
11 *         (with md5 checksum b35adb5213ca9657e911e9befb180842)         *
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*
fmtmatch(const char * as)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