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