xref: /illumos-gate/usr/src/head/regexp.h (revision 5328fc53d11d7151861fa272e4fb0248b8f0e145)
1 /*
2  * CDDL HEADER START
3  *
4  * The contents of this file are subject to the terms of the
5  * Common Development and Distribution License (the "License").
6  * You may not use this file except in compliance with the License.
7  *
8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
9  * or http://www.opensolaris.org/os/licensing.
10  * See the License for the specific language governing permissions
11  * and limitations under the License.
12  *
13  * When distributing Covered Code, include this CDDL HEADER in each
14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
15  * If applicable, add the following below this CDDL HEADER, with the
16  * fields enclosed by brackets "[]" replaced with your own identifying
17  * information: Portions Copyright [yyyy] [name of copyright owner]
18  *
19  * CDDL HEADER END
20  */
21 /*	Copyright (c) 1988 AT&T	*/
22 /*	  All Rights Reserved	*/
23 
24 /*
25  * Copyright 2014 Garrett D'Amore <garrett@damore.org>
26  *
27  * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
28  * Use is subject to license terms.
29  */
30 
31 #ifndef _REGEXP_H
32 #define	_REGEXP_H
33 
34 #include <string.h>
35 
36 #ifdef	__cplusplus
37 extern "C" {
38 #endif
39 
40 #define	CBRA	2
41 #define	CCHR	4
42 #define	CDOT	8
43 #define	CCL	12
44 #define	CXCL	16
45 #define	CDOL	20
46 #define	CCEOF	22
47 #define	CKET	24
48 #define	CBACK	36
49 #define	NCCL	40
50 
51 #define	STAR	01
52 #define	RNGE	03
53 
54 #define	NBRA	9
55 
56 #define	PLACE(c)	ep[c >> 3] |= bittab[c & 07]
57 #define	ISTHERE(c)	(ep[c >> 3] & bittab[c & 07])
58 #define	ecmp(s1, s2, n)	(strncmp(s1, s2, n) == 0)
59 
60 static char	*braslist[NBRA];
61 static char	*braelist[NBRA];
62 int	sed, nbra;
63 char	*loc1, *loc2, *locs;
64 static int	nodelim;
65 
66 int	circf;
67 static int	low;
68 static int	size;
69 
70 static unsigned char	bittab[] = { 1, 2, 4, 8, 16, 32, 64, 128 };
71 
72 int advance(const char *lp, const char *ep);
73 static void getrnge(const char *str);
74 
75 char *
76 compile(char *instring, char *ep, const char *endbuf, int seof)
77 {
78 	INIT	/* Dependent declarations and initializations */
79 	register int c;
80 	register int eof = seof;
81 	char *lastep;
82 	int cclcnt;
83 	char bracket[NBRA], *bracketp;
84 	int closed;
85 	int neg;
86 	int lc;
87 	int i, cflg;
88 	int iflag; /* used for non-ascii characters in brackets */
89 
90 #ifdef __lint
91 	/* make lint happy */
92 	c = nodelim;
93 #endif
94 
95 	lastep = NULL;
96 	if ((c = GETC()) == eof || c == '\n') {
97 		if (c == '\n') {
98 			UNGETC(c);
99 			nodelim = 1;
100 		}
101 		if (*ep == 0 && !sed)
102 			ERROR(41);
103 		RETURN(ep);
104 	}
105 	bracketp = bracket;
106 	circf = closed = nbra = 0;
107 	if (c == '^')
108 		circf++;
109 	else
110 		UNGETC(c);
111 	for (;;) {
112 		if (ep >= endbuf)
113 			ERROR(50);
114 		c = GETC();
115 		if (c != '*' && ((c != '\\') || (PEEKC() != '{')))
116 			lastep = ep;
117 		if (c == eof) {
118 			*ep++ = CCEOF;
119 			if (bracketp != bracket)
120 				ERROR(42);
121 			RETURN(ep);
122 		}
123 		switch (c) {
124 
125 		case '.':
126 			*ep++ = CDOT;
127 			continue;
128 
129 		case '\n':
130 			if (!sed) {
131 				UNGETC(c);
132 				*ep++ = CCEOF;
133 				nodelim = 1;
134 				if (bracketp != bracket)
135 					ERROR(42);
136 				RETURN(ep);
137 			} else ERROR(36);
138 		case '*':
139 			if (lastep == NULL || *lastep == CBRA ||
140 			    *lastep == CKET)
141 				goto defchar;
142 			*lastep |= STAR;
143 			continue;
144 
145 		case '$':
146 			if (PEEKC() != eof && PEEKC() != '\n')
147 				goto defchar;
148 			*ep++ = CDOL;
149 			continue;
150 
151 		case '[':
152 			if (&ep[17] >= endbuf)
153 				ERROR(50);
154 
155 			*ep++ = CCL;
156 			lc = 0;
157 			for (i = 0; i < 16; i++)
158 				ep[i] = 0;
159 
160 			neg = 0;
161 			if ((c = GETC()) == '^') {
162 				neg = 1;
163 				c = GETC();
164 			}
165 			iflag = 1;
166 			do {
167 				c &= 0377;
168 				if (c == '\0' || c == '\n')
169 					ERROR(49);
170 				if ((c & 0200) && iflag) {
171 					iflag = 0;
172 					if (&ep[32] >= endbuf)
173 						ERROR(50);
174 					ep[-1] = CXCL;
175 					for (i = 16; i < 32; i++)
176 						ep[i] = 0;
177 				}
178 				if (c == '-' && lc != 0) {
179 					if ((c = GETC()) == ']') {
180 						PLACE('-');
181 						break;
182 					}
183 					if ((c & 0200) && iflag) {
184 						iflag = 0;
185 						if (&ep[32] >= endbuf)
186 							ERROR(50);
187 						ep[-1] = CXCL;
188 						for (i = 16; i < 32; i++)
189 							ep[i] = 0;
190 					}
191 					while (lc < c) {
192 						PLACE(lc);
193 						lc++;
194 					}
195 				}
196 				lc = c;
197 				PLACE(c);
198 			} while ((c = GETC()) != ']');
199 
200 			if (iflag)
201 				iflag = 16;
202 			else
203 				iflag = 32;
204 
205 			if (neg) {
206 				if (iflag == 32) {
207 					for (cclcnt = 0; cclcnt < iflag;
208 					    cclcnt++)
209 						ep[cclcnt] ^= 0377;
210 					ep[0] &= 0376;
211 				} else {
212 					ep[-1] = NCCL;
213 					/* make nulls match so test fails */
214 					ep[0] |= 01;
215 				}
216 			}
217 
218 			ep += iflag;
219 
220 			continue;
221 
222 		case '\\':
223 			switch (c = GETC()) {
224 
225 			case '(':
226 				if (nbra >= NBRA)
227 					ERROR(43);
228 				*bracketp++ = (char)nbra;
229 				*ep++ = CBRA;
230 				*ep++ = (char)nbra++;
231 				continue;
232 
233 			case ')':
234 				if (bracketp <= bracket)
235 					ERROR(42);
236 				*ep++ = CKET;
237 				*ep++ = *--bracketp;
238 				closed++;
239 				continue;
240 
241 			case '{':
242 				if (lastep == NULL)
243 					goto defchar;
244 				*lastep |= RNGE;
245 				cflg = 0;
246 			nlim:
247 				c = GETC();
248 				i = 0;
249 				do {
250 					if ('0' <= c && c <= '9')
251 						i = 10 * i + c - '0';
252 					else
253 						ERROR(16);
254 				} while (((c = GETC()) != '\\') && (c != ','));
255 				if (i >= 255)
256 					ERROR(11);
257 				*ep++ = (char)i;
258 				if (c == ',') {
259 					if (cflg++)
260 						ERROR(44);
261 					if ((c = GETC()) == '\\')
262 						*ep++ = (char)255;
263 					else {
264 						UNGETC(c);
265 						goto nlim;
266 						/* get 2'nd number */
267 					}
268 				}
269 				if (GETC() != '}')
270 					ERROR(45);
271 				if (!cflg)	/* one number */
272 					*ep++ = (char)i;
273 				else if ((ep[-1] & 0377) < (ep[-2] & 0377))
274 					ERROR(46);
275 				continue;
276 
277 			case '\n':
278 				ERROR(36);
279 
280 			case 'n':
281 				c = '\n';
282 				goto defchar;
283 
284 			default:
285 				if (c >= '1' && c <= '9') {
286 					if ((c -= '1') >= closed)
287 						ERROR(25);
288 					*ep++ = CBACK;
289 					*ep++ = (char)c;
290 					continue;
291 				}
292 				/* FALLTHROUGH */
293 			}
294 			/* FALLTHROUGH */
295 	/* Drop through to default to use \ to turn off special chars */
296 
297 		defchar:
298 		default:
299 			lastep = ep;
300 			*ep++ = CCHR;
301 			*ep++ = (char)c;
302 		}
303 	}
304 	/*NOTREACHED*/
305 }
306 
307 int
308 step(const char *p1, const char *p2)
309 {
310 	char c;
311 
312 
313 	if (circf) {
314 		loc1 = (char *)p1;
315 		return (advance(p1, p2));
316 	}
317 	/* fast check for first character */
318 	if (*p2 == CCHR) {
319 		c = p2[1];
320 		do {
321 			if (*p1 != c)
322 				continue;
323 			if (advance(p1, p2)) {
324 				loc1 = (char *)p1;
325 				return (1);
326 			}
327 		} while (*p1++);
328 		return (0);
329 	}
330 		/* regular algorithm */
331 	do {
332 		if (advance(p1, p2)) {
333 			loc1 = (char *)p1;
334 			return (1);
335 		}
336 	} while (*p1++);
337 	return (0);
338 }
339 
340 int
341 advance(const char *lp, const char *ep)
342 {
343 	const char *curlp;
344 	int c;
345 	char *bbeg;
346 	register char neg;
347 	size_t ct;
348 
349 	for (;;) {
350 		neg = 0;
351 		switch (*ep++) {
352 
353 		case CCHR:
354 			if (*ep++ == *lp++)
355 				continue;
356 			return (0);
357 			/*FALLTHRU*/
358 
359 		case CDOT:
360 			if (*lp++)
361 				continue;
362 			return (0);
363 			/*FALLTHRU*/
364 
365 		case CDOL:
366 			if (*lp == 0)
367 				continue;
368 			return (0);
369 			/*FALLTHRU*/
370 
371 		case CCEOF:
372 			loc2 = (char *)lp;
373 			return (1);
374 			/*FALLTHRU*/
375 
376 		case CXCL:
377 			c = (unsigned char)*lp++;
378 			if (ISTHERE(c)) {
379 				ep += 32;
380 				continue;
381 			}
382 			return (0);
383 			/*FALLTHRU*/
384 
385 		case NCCL:
386 			neg = 1;
387 			/*FALLTHRU*/
388 
389 		case CCL:
390 			c = *lp++;
391 			if (((c & 0200) == 0 && ISTHERE(c)) ^ neg) {
392 				ep += 16;
393 				continue;
394 			}
395 			return (0);
396 			/*FALLTHRU*/
397 
398 		case CBRA:
399 			braslist[*ep++] = (char *)lp;
400 			continue;
401 			/*FALLTHRU*/
402 
403 		case CKET:
404 			braelist[*ep++] = (char *)lp;
405 			continue;
406 			/*FALLTHRU*/
407 
408 		case CCHR | RNGE:
409 			c = *ep++;
410 			getrnge(ep);
411 			while (low--)
412 				if (*lp++ != c)
413 					return (0);
414 			curlp = lp;
415 			while (size--)
416 				if (*lp++ != c)
417 					break;
418 			if (size < 0)
419 				lp++;
420 			ep += 2;
421 			goto star;
422 			/*FALLTHRU*/
423 
424 		case CDOT | RNGE:
425 			getrnge(ep);
426 			while (low--)
427 				if (*lp++ == '\0')
428 					return (0);
429 			curlp = lp;
430 			while (size--)
431 				if (*lp++ == '\0')
432 					break;
433 			if (size < 0)
434 				lp++;
435 			ep += 2;
436 			goto star;
437 			/*FALLTHRU*/
438 
439 		case CXCL | RNGE:
440 			getrnge(ep + 32);
441 			while (low--) {
442 				c = (unsigned char)*lp++;
443 				if (!ISTHERE(c))
444 					return (0);
445 			}
446 			curlp = lp;
447 			while (size--) {
448 				c = (unsigned char)*lp++;
449 				if (!ISTHERE(c))
450 					break;
451 			}
452 			if (size < 0)
453 				lp++;
454 			ep += 34;		/* 32 + 2 */
455 			goto star;
456 			/*FALLTHRU*/
457 
458 		case NCCL | RNGE:
459 			neg = 1;
460 			/*FALLTHRU*/
461 
462 		case CCL | RNGE:
463 			getrnge(ep + 16);
464 			while (low--) {
465 				c = *lp++;
466 				if (((c & 0200) || !ISTHERE(c)) ^ neg)
467 					return (0);
468 			}
469 			curlp = lp;
470 			while (size--) {
471 				c = *lp++;
472 				if (((c & 0200) || !ISTHERE(c)) ^ neg)
473 					break;
474 			}
475 			if (size < 0)
476 				lp++;
477 			ep += 18;		/* 16 + 2 */
478 			goto star;
479 			/*FALLTHRU*/
480 
481 		case CBACK:
482 			bbeg = braslist[*ep];
483 			ct = braelist[*ep++] - bbeg;
484 
485 			if (ecmp(bbeg, lp, ct)) {
486 				lp += ct;
487 				continue;
488 			}
489 			return (0);
490 			/*FALLTHRU*/
491 
492 		case CBACK | STAR:
493 			bbeg = braslist[*ep];
494 			ct = braelist[*ep++] - bbeg;
495 			curlp = lp;
496 			while (ecmp(bbeg, lp, ct))
497 				lp += ct;
498 
499 			while (lp >= curlp) {
500 				if (advance(lp, ep))
501 					return (1);
502 				lp -= ct;
503 			}
504 			return (0);
505 			/*FALLTHRU*/
506 
507 		case CDOT | STAR:
508 			curlp = lp;
509 			while (*lp++)
510 				;
511 			goto star;
512 			/*FALLTHRU*/
513 
514 		case CCHR | STAR:
515 			curlp = lp;
516 			while (*lp++ == *ep)
517 				;
518 			ep++;
519 			goto star;
520 			/*FALLTHRU*/
521 
522 		case CXCL | STAR:
523 			curlp = lp;
524 			do {
525 				c = (unsigned char)*lp++;
526 			} while (ISTHERE(c));
527 			ep += 32;
528 			goto star;
529 			/*FALLTHRU*/
530 
531 		case NCCL | STAR:
532 			neg = 1;
533 			/*FALLTHRU*/
534 
535 		case CCL | STAR:
536 			curlp = lp;
537 			do {
538 				c = *lp++;
539 			} while (((c & 0200) == 0 && ISTHERE(c)) ^ neg);
540 			ep += 16;
541 			goto star;
542 			/*FALLTHRU*/
543 
544 		star:
545 			do {
546 				if (--lp == locs)
547 					break;
548 				if (advance(lp, ep))
549 					return (1);
550 			} while (lp > curlp);
551 			return (0);
552 
553 		}
554 	}
555 	/*NOTREACHED*/
556 }
557 
558 static void
559 getrnge(const char *str)
560 {
561 	low = *str++ & 0377;
562 	size = ((*str & 0377) == 255)? 20000: (*str &0377) - low;
563 }
564 
565 #ifdef	__cplusplus
566 }
567 #endif
568 
569 #endif	/* _REGEXP_H */
570