![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to regex.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Apple XNU] / GNUtools / emacs / src|
Return to regex.c CVS log | Up to [Apple XNU] / GNUtools / emacs / src |
1.1 root 1: /* Extended regular expression matching and search.
2: Copyright (C) 1985 Free Software Foundation, Inc.
3:
4: This program is free software; you can redistribute it and/or modify
5: it under the terms of the GNU General Public License as published by
6: the Free Software Foundation; either version 1, or (at your option)
7: any later version.
8:
9: This program is distributed in the hope that it will be useful,
10: but WITHOUT ANY WARRANTY; without even the implied warranty of
11: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12: GNU General Public License for more details.
13:
14: You should have received a copy of the GNU General Public License
15: along with this program; if not, write to the Free Software
16: Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
17:
18: In other words, you are welcome to use, share and improve this program.
19: You are forbidden to forbid anyone else to use, share and improve
20: what you give them. Help stamp out software-hoarding! */
21:
22:
23: /* To test, compile with -Dtest.
24: This Dtestable feature turns this into a self-contained program
25: which reads a pattern, describes how it compiles,
26: then reads a string and searches for it. */
27:
28:
29: #ifdef emacs
30:
31: /* The `emacs' switch turns on certain special matching commands
32: that make sense only in emacs. */
33:
34: #include "config.h"
35: #include "lisp.h"
36: #include "buffer.h"
37: #include "syntax.h"
38:
39: #else /* not emacs */
40:
41: /*
42: * Define the syntax stuff, so we can do the \<...\> things.
43: */
44:
45: #ifndef Sword /* must be non-zero in some of the tests below... */
46: #define Sword 1
47: #endif
48:
49: #define SYNTAX(c) re_syntax_table[c]
50:
51: #ifdef SYNTAX_TABLE
52:
53: char *re_syntax_table;
54:
55: #else
56:
57: static char re_syntax_table[256];
58:
59: static void
60: init_syntax_once ()
61: {
62: register int c;
63: static int done = 0;
64:
65: if (done)
66: return;
67:
68: bzero (re_syntax_table, sizeof re_syntax_table);
69:
70: for (c = 'a'; c <= 'z'; c++)
71: re_syntax_table[c] = Sword;
72:
73: for (c = 'A'; c <= 'Z'; c++)
74: re_syntax_table[c] = Sword;
75:
76: for (c = '0'; c <= '9'; c++)
77: re_syntax_table[c] = Sword;
78:
79: done = 1;
80: }
81:
82: #endif /* SYNTAX_TABLE */
83: #endif /* not emacs */
84:
85: #include "regex.h"
86:
87: /* Number of failure points to allocate space for initially,
88: when matching. If this number is exceeded, more space is allocated,
89: so it is not a hard limit. */
90:
91: #ifndef NFAILURES
92: #define NFAILURES 80
93: #endif NFAILURES
94:
95: /* width of a byte in bits */
96:
97: #define BYTEWIDTH 8
98:
99: #ifndef SIGN_EXTEND_CHAR
100: #define SIGN_EXTEND_CHAR(x) (x)
101: #endif
102:
103: static int obscure_syntax = 0;
104:
105: /* Specify the precise syntax of regexp for compilation.
106: This provides for compatibility for various utilities
107: which historically have different, incompatible syntaxes.
108:
109: The argument SYNTAX is a bit-mask containing the two bits
110: RE_NO_BK_PARENS and RE_NO_BK_VBAR. */
111:
112: int
113: re_set_syntax (syntax)
114: {
115: int ret;
116:
117: ret = obscure_syntax;
118: obscure_syntax = syntax;
119: return ret;
120: }
121:
122: /* re_compile_pattern takes a regular-expression string
123: and converts it into a buffer full of byte commands for matching.
124:
125: PATTERN is the address of the pattern string
126: SIZE is the length of it.
127: BUFP is a struct re_pattern_buffer * which points to the info
128: on where to store the byte commands.
129: This structure contains a char * which points to the
130: actual space, which should have been obtained with malloc.
131: re_compile_pattern may use realloc to grow the buffer space.
132:
133: The number of bytes of commands can be found out by looking in
134: the struct re_pattern_buffer that bufp pointed to,
135: after re_compile_pattern returns.
136: */
137:
138: #define PATPUSH(ch) (*b++ = (char) (ch))
139:
140: #define PATFETCH(c) \
141: {if (p == pend) goto end_of_pattern; \
142: c = * (unsigned char *) p++; \
143: if (translate) c = translate[c]; }
144:
145: #define PATFETCH_RAW(c) \
146: {if (p == pend) goto end_of_pattern; \
147: c = * (unsigned char *) p++; }
148:
149: #define PATUNFETCH p--
150:
151: #define EXTEND_BUFFER \
152: { char *old_buffer = bufp->buffer; \
153: if (bufp->allocated == (1<<16)) goto too_big; \
154: bufp->allocated *= 2; \
155: if (bufp->allocated > (1<<16)) bufp->allocated = (1<<16); \
156: if (!(bufp->buffer = (char *) realloc (bufp->buffer, bufp->allocated))) \
157: goto memory_exhausted; \
158: c = bufp->buffer - old_buffer; \
159: b += c; \
160: if (fixup_jump) \
161: fixup_jump += c; \
162: if (laststart) \
163: laststart += c; \
164: begalt += c; \
165: if (pending_exact) \
166: pending_exact += c; \
167: }
168:
169: static int store_jump (), insert_jump ();
170:
171: char *
172: re_compile_pattern (pattern, size, bufp)
173: char *pattern;
174: int size;
175: struct re_pattern_buffer *bufp;
176: {
177: register char *b = bufp->buffer;
178: register char *p = pattern;
179: char *pend = pattern + size;
180: register unsigned c, c1;
181: char *p1;
182: unsigned char *translate = (unsigned char *) bufp->translate;
183:
184: /* address of the count-byte of the most recently inserted "exactn" command.
185: This makes it possible to tell whether a new exact-match character
186: can be added to that command or requires a new "exactn" command. */
187:
188: char *pending_exact = 0;
189:
190: /* address of the place where a forward-jump should go
191: to the end of the containing expression.
192: Each alternative of an "or", except the last, ends with a forward-jump
193: of this sort. */
194:
195: char *fixup_jump = 0;
196:
197: /* address of start of the most recently finished expression.
198: This tells postfix * where to find the start of its operand. */
199:
200: char *laststart = 0;
201:
202: /* In processing a repeat, 1 means zero matches is allowed */
203:
204: char zero_times_ok;
205:
206: /* In processing a repeat, 1 means many matches is allowed */
207:
208: char many_times_ok;
209:
210: /* address of beginning of regexp, or inside of last \( */
211:
212: char *begalt = b;
213:
214: /* Stack of information saved by \( and restored by \).
215: Four stack elements are pushed by each \(:
216: First, the value of b.
217: Second, the value of fixup_jump.
218: Third, the value of regnum.
219: Fourth, the value of begalt. */
220:
221: int stackb[40];
222: int *stackp = stackb;
223: int *stacke = stackb + 40;
224: int *stackt;
225:
226: /* Counts \('s as they are encountered. Remembered for the matching \),
227: where it becomes the "register number" to put in the stop_memory command */
228:
229: int regnum = 1;
230:
231: bufp->fastmap_accurate = 0;
232:
233: #ifndef emacs
234: #ifndef SYNTAX_TABLE
235: /*
236: * Initialize the syntax table.
237: */
238: init_syntax_once();
239: #endif
240: #endif
241:
242: if (bufp->allocated == 0)
243: {
244: bufp->allocated = 28;
245: if (bufp->buffer)
246: /* EXTEND_BUFFER loses when bufp->allocated is 0 */
247: bufp->buffer = (char *) realloc (bufp->buffer, 28);
248: else
249: /* Caller did not allocate a buffer. Do it for him */
250: bufp->buffer = (char *) malloc (28);
251: if (!bufp->buffer) goto memory_exhausted;
252: begalt = b = bufp->buffer;
253: }
254:
255: while (p != pend)
256: {
257: if (b - bufp->buffer > bufp->allocated - 10)
258: /* Note that EXTEND_BUFFER clobbers c */
259: EXTEND_BUFFER;
260:
261: PATFETCH (c);
262:
263: switch (c)
264: {
265: case '$':
266: if (obscure_syntax & RE_TIGHT_VBAR)
267: {
268: if (! (obscure_syntax & RE_CONTEXT_INDEP_OPS) && p != pend)
269: goto normal_char;
270: /* Make operand of last vbar end before this `$'. */
271: if (fixup_jump)
272: store_jump (fixup_jump, jump, b);
273: fixup_jump = 0;
274: PATPUSH (endline);
275: break;
276: }
277:
278: /* $ means succeed if at end of line, but only in special contexts.
279: If randomly in the middle of a pattern, it is a normal character. */
280: if (p == pend || *p == '\n'
281: || (obscure_syntax & RE_CONTEXT_INDEP_OPS)
282: || (obscure_syntax & RE_NO_BK_PARENS
283: ? *p == ')'
284: : *p == '\\' && p[1] == ')')
285: || (obscure_syntax & RE_NO_BK_VBAR
286: ? *p == '|'
287: : *p == '\\' && p[1] == '|'))
288: {
289: PATPUSH (endline);
290: break;
291: }
292: goto normal_char;
293:
294: case '^':
295: /* ^ means succeed if at beg of line, but only if no preceding pattern. */
296:
297: if (laststart && p[-2] != '\n'
298: && ! (obscure_syntax & RE_CONTEXT_INDEP_OPS))
299: goto normal_char;
300: if (obscure_syntax & RE_TIGHT_VBAR)
301: {
302: if (p != pattern + 1
303: && ! (obscure_syntax & RE_CONTEXT_INDEP_OPS))
304: goto normal_char;
305: PATPUSH (begline);
306: begalt = b;
307: }
308: else
309: PATPUSH (begline);
310: break;
311:
312: case '+':
313: case '?':
314: if (obscure_syntax & RE_BK_PLUS_QM)
315: goto normal_char;
316: handle_plus:
317: case '*':
318: /* If there is no previous pattern, char not special. */
319: if (!laststart && ! (obscure_syntax & RE_CONTEXT_INDEP_OPS))
320: goto normal_char;
321: /* If there is a sequence of repetition chars,
322: collapse it down to equivalent to just one. */
323: zero_times_ok = 0;
324: many_times_ok = 0;
325: while (1)
326: {
327: zero_times_ok |= c != '+';
328: many_times_ok |= c != '?';
329: if (p == pend)
330: break;
331: PATFETCH (c);
332: if (c == '*')
333: ;
334: else if (!(obscure_syntax & RE_BK_PLUS_QM)
335: && (c == '+' || c == '?'))
336: ;
337: else if ((obscure_syntax & RE_BK_PLUS_QM)
338: && c == '\\')
339: {
340: int c1;
341: PATFETCH (c1);
342: if (!(c1 == '+' || c1 == '?'))
343: {
344: PATUNFETCH;
345: PATUNFETCH;
346: break;
347: }
348: c = c1;
349: }
350: else
351: {
352: PATUNFETCH;
353: break;
354: }
355: }
356:
357: /* Star, etc. applied to an empty pattern is equivalent
358: to an empty pattern. */
359: if (!laststart)
360: break;
361:
362: /* Now we know whether 0 matches is allowed,
363: and whether 2 or more matches is allowed. */
364: if (many_times_ok)
365: {
366: /* If more than one repetition is allowed,
367: put in a backward jump at the end. */
368: store_jump (b, maybe_finalize_jump, laststart - 3);
369: b += 3;
370: }
371: insert_jump (on_failure_jump, laststart, b + 3, b);
372: pending_exact = 0;
373: b += 3;
374: if (!zero_times_ok)
375: {
376: /* At least one repetition required: insert before the loop
377: a skip over the initial on-failure-jump instruction */
378: insert_jump (dummy_failure_jump, laststart, laststart + 6, b);
379: b += 3;
380: }
381: break;
382:
383: case '.':
384: laststart = b;
385: PATPUSH (anychar);
386: break;
387:
388: case '[':
389: while (b - bufp->buffer
390: > bufp->allocated - 3 - (1 << BYTEWIDTH) / BYTEWIDTH)
391: /* Note that EXTEND_BUFFER clobbers c */
392: EXTEND_BUFFER;
393:
394: laststart = b;
395: if (*p == '^')
396: PATPUSH (charset_not), p++;
397: else
398: PATPUSH (charset);
399: p1 = p;
400:
401: PATPUSH ((1 << BYTEWIDTH) / BYTEWIDTH);
402: /* Clear the whole map */
403: bzero (b, (1 << BYTEWIDTH) / BYTEWIDTH);
404: /* Read in characters and ranges, setting map bits */
405: while (1)
406: {
407: PATFETCH (c);
408: if (c == ']' && p != p1 + 1) break;
409: if (*p == '-' && p[1] != ']')
410: {
411: PATFETCH (c1);
412: PATFETCH (c1);
413: if (translate)
414: while (c <= c1)
415: {
416: register unsigned char mapped_c = translate[c];
417: b[mapped_c / BYTEWIDTH] |= 1 << (mapped_c % BYTEWIDTH);
418: c++;
419: }
420: else
421: while (c <= c1)
422: b[c / BYTEWIDTH] |= 1 << (c % BYTEWIDTH), c++;
423: }
424: else
425: {
426: if (translate)
427: c = translate[c];
428: b[c / BYTEWIDTH] |= 1 << (c % BYTEWIDTH);
429: }
430: }
431: /* Discard any bitmap bytes that are all 0 at the end of the map.
432: Decrement the map-length byte too. */
433: while ((int) b[-1] > 0 && b[b[-1] - 1] == 0)
434: b[-1]--;
435: b += b[-1];
436: break;
437:
438: case '(':
439: if (! (obscure_syntax & RE_NO_BK_PARENS))
440: goto normal_char;
441: else
442: goto handle_open;
443:
444: case ')':
445: if (! (obscure_syntax & RE_NO_BK_PARENS))
446: goto normal_char;
447: else
448: goto handle_close;
449:
450: case '\n':
451: if (! (obscure_syntax & RE_NEWLINE_OR))
452: goto normal_char;
453: else
454: goto handle_bar;
455:
456: case '|':
457: if (! (obscure_syntax & RE_NO_BK_VBAR))
458: goto normal_char;
459: else
460: goto handle_bar;
461:
462: case '\\':
463: if (p == pend) goto invalid_pattern;
464: PATFETCH_RAW (c);
465: switch (c)
466: {
467: case '(':
468: if (obscure_syntax & RE_NO_BK_PARENS)
469: goto normal_backsl;
470: handle_open:
471: if (stackp == stacke) goto nesting_too_deep;
472: if (regnum < RE_NREGS)
473: {
474: PATPUSH (start_memory);
475: PATPUSH (regnum);
476: }
477: *stackp++ = b - bufp->buffer;
478: *stackp++ = fixup_jump ? fixup_jump - bufp->buffer + 1 : 0;
479: *stackp++ = regnum++;
480: *stackp++ = begalt - bufp->buffer;
481: fixup_jump = 0;
482: laststart = 0;
483: begalt = b;
484: break;
485:
486: case ')':
487: if (obscure_syntax & RE_NO_BK_PARENS)
488: goto normal_backsl;
489: handle_close:
490: if (stackp == stackb) goto unmatched_close;
491: begalt = *--stackp + bufp->buffer;
492: if (fixup_jump)
493: store_jump (fixup_jump, jump, b);
494: if (stackp[-1] < RE_NREGS)
495: {
496: PATPUSH (stop_memory);
497: PATPUSH (stackp[-1]);
498: }
499: stackp -= 2;
500: fixup_jump = 0;
501: if (*stackp)
502: fixup_jump = *stackp + bufp->buffer - 1;
503: laststart = *--stackp + bufp->buffer;
504: break;
505:
506: case '|':
507: if (obscure_syntax & RE_NO_BK_VBAR)
508: goto normal_backsl;
509: handle_bar:
510: insert_jump (on_failure_jump, begalt, b + 6, b);
511: pending_exact = 0;
512: b += 3;
513: if (fixup_jump)
514: store_jump (fixup_jump, jump, b);
515: fixup_jump = b;
516: b += 3;
517: laststart = 0;
518: begalt = b;
519: break;
520:
521: #ifdef emacs
522: case '=':
523: PATPUSH (at_dot);
524: break;
525:
526: case 's':
527: laststart = b;
528: PATPUSH (syntaxspec);
529: PATFETCH (c);
530: PATPUSH (syntax_spec_code[c]);
531: break;
532:
533: case 'S':
534: laststart = b;
535: PATPUSH (notsyntaxspec);
536: PATFETCH (c);
537: PATPUSH (syntax_spec_code[c]);
538: break;
539: #endif emacs
540:
541: case 'w':
542: laststart = b;
543: PATPUSH (wordchar);
544: break;
545:
546: case 'W':
547: laststart = b;
548: PATPUSH (notwordchar);
549: break;
550:
551: case '<':
552: PATPUSH (wordbeg);
553: break;
554:
555: case '>':
556: PATPUSH (wordend);
557: break;
558:
559: case 'b':
560: PATPUSH (wordbound);
561: break;
562:
563: case 'B':
564: PATPUSH (notwordbound);
565: break;
566:
567: case '`':
568: PATPUSH (begbuf);
569: break;
570:
571: case '\'':
572: PATPUSH (endbuf);
573: break;
574:
575: case '1':
576: case '2':
577: case '3':
578: case '4':
579: case '5':
580: case '6':
581: case '7':
582: case '8':
583: case '9':
584: c1 = c - '0';
585: if (c1 >= regnum)
586: goto normal_char;
587: for (stackt = stackp - 2; stackt > stackb; stackt -= 4)
588: if (*stackt == c1)
589: goto normal_char;
590: laststart = b;
591: PATPUSH (duplicate);
592: PATPUSH (c1);
593: break;
594:
595: case '+':
596: case '?':
597: if (obscure_syntax & RE_BK_PLUS_QM)
598: goto handle_plus;
599:
600: default:
601: normal_backsl:
602: /* You might think it would be useful for \ to mean
603: not to translate; but if we don't translate it
604: it will never match anything. */
605: if (translate) c = translate[c];
606: goto normal_char;
607: }
608: break;
609:
610: default:
611: normal_char:
612: if (!pending_exact || pending_exact + *pending_exact + 1 != b
613: || *pending_exact == 0177 || *p == '*' || *p == '^'
614: || ((obscure_syntax & RE_BK_PLUS_QM)
615: ? *p == '\\' && (p[1] == '+' || p[1] == '?')
616: : (*p == '+' || *p == '?')))
617: {
618: laststart = b;
619: PATPUSH (exactn);
620: pending_exact = b;
621: PATPUSH (0);
622: }
623: PATPUSH (c);
624: (*pending_exact)++;
625: }
626: }
627:
628: if (fixup_jump)
629: store_jump (fixup_jump, jump, b);
630:
631: if (stackp != stackb) goto unmatched_open;
632:
633: bufp->used = b - bufp->buffer;
634: return 0;
635:
636: invalid_pattern:
637: return "Invalid regular expression";
638:
639: unmatched_open:
640: return "Unmatched \\(";
641:
642: unmatched_close:
643: return "Unmatched \\)";
644:
645: end_of_pattern:
646: return "Premature end of regular expression";
647:
648: nesting_too_deep:
649: return "Nesting too deep";
650:
651: too_big:
652: return "Regular expression too big";
653:
654: memory_exhausted:
655: return "Memory exhausted";
656: }
657:
658: /* Store where `from' points a jump operation to jump to where `to' points.
659: `opcode' is the opcode to store. */
660:
661: static int
662: store_jump (from, opcode, to)
663: char *from, *to;
664: char opcode;
665: {
666: from[0] = opcode;
667: from[1] = (to - (from + 3)) & 0377;
668: from[2] = (to - (from + 3)) >> 8;
669: }
670:
671: /* Open up space at char FROM, and insert there a jump to TO.
672: CURRENT_END gives te end of the storage no in use,
673: so we know how much data to copy up.
674: OP is the opcode of the jump to insert.
675:
676: If you call this function, you must zero out pending_exact. */
677:
678: static int
679: insert_jump (op, from, to, current_end)
680: char op;
681: char *from, *to, *current_end;
682: {
683: register char *pto = current_end + 3;
684: register char *pfrom = current_end;
685: while (pfrom != from)
686: *--pto = *--pfrom;
687: store_jump (from, op, to);
688: }
689:
690: /* Given a pattern, compute a fastmap from it.
691: The fastmap records which of the (1 << BYTEWIDTH) possible characters
692: can start a string that matches the pattern.
693: This fastmap is used by re_search to skip quickly over totally implausible text.
694:
695: The caller must supply the address of a (1 << BYTEWIDTH)-byte data area
696: as bufp->fastmap.
697: The other components of bufp describe the pattern to be used. */
698:
699: void
700: re_compile_fastmap (bufp)
701: struct re_pattern_buffer *bufp;
702: {
703: unsigned char *pattern = (unsigned char *) bufp->buffer;
704: int size = bufp->used;
705: register char *fastmap = bufp->fastmap;
706: register unsigned char *p = pattern;
707: register unsigned char *pend = pattern + size;
708: register int j, k;
709: unsigned char *translate = (unsigned char *) bufp->translate;
710:
711: unsigned char *stackb[NFAILURES];
712: unsigned char **stackp = stackb;
713:
714: bzero (fastmap, (1 << BYTEWIDTH));
715: bufp->fastmap_accurate = 1;
716: bufp->can_be_null = 0;
717:
718: while (p)
719: {
720: if (p == pend)
721: {
722: bufp->can_be_null = 1;
723: break;
724: }
725: #ifdef SWITCH_ENUM_BUG
726: switch ((int) ((enum regexpcode) *p++))
727: #else
728: switch ((enum regexpcode) *p++)
729: #endif
730: {
731: case exactn:
732: if (translate)
733: fastmap[translate[p[1]]] = 1;
734: else
735: fastmap[p[1]] = 1;
736: break;
737:
738: case begline:
739: case before_dot:
740: case at_dot:
741: case after_dot:
742: case begbuf:
743: case endbuf:
744: case wordbound:
745: case notwordbound:
746: case wordbeg:
747: case wordend:
748: continue;
749:
750: case endline:
751: if (translate)
752: fastmap[translate['\n']] = 1;
753: else
754: fastmap['\n'] = 1;
755: if (bufp->can_be_null != 1)
756: bufp->can_be_null = 2;
757: break;
758:
759: case finalize_jump:
760: case maybe_finalize_jump:
761: case jump:
762: case dummy_failure_jump:
763: bufp->can_be_null = 1;
764: j = *p++ & 0377;
765: j += SIGN_EXTEND_CHAR (*(char *)p) << 8;
766: p += j + 1; /* The 1 compensates for missing ++ above */
767: if (j > 0)
768: continue;
769: /* Jump backward reached implies we just went through
770: the body of a loop and matched nothing.
771: Opcode jumped to should be an on_failure_jump.
772: Just treat it like an ordinary jump.
773: For a * loop, it has pushed its failure point already;
774: if so, discard that as redundant. */
775: if ((enum regexpcode) *p != on_failure_jump)
776: continue;
777: p++;
778: j = *p++ & 0377;
779: j += SIGN_EXTEND_CHAR (*(char *)p) << 8;
780: p += j + 1; /* The 1 compensates for missing ++ above */
781: if (stackp != stackb && *stackp == p)
782: stackp--;
783: continue;
784:
785: case on_failure_jump:
786: j = *p++ & 0377;
787: j += SIGN_EXTEND_CHAR (*(char *)p) << 8;
788: p++;
789: *++stackp = p + j;
790: continue;
791:
792: case start_memory:
793: case stop_memory:
794: p++;
795: continue;
796:
797: case duplicate:
798: bufp->can_be_null = 1;
799: fastmap['\n'] = 1;
800: case anychar:
801: for (j = 0; j < (1 << BYTEWIDTH); j++)
802: if (j != '\n')
803: fastmap[j] = 1;
804: if (bufp->can_be_null)
805: return;
806: /* Don't return; check the alternative paths
807: so we can set can_be_null if appropriate. */
808: break;
809:
810: case wordchar:
811: for (j = 0; j < (1 << BYTEWIDTH); j++)
812: if (SYNTAX (j) == Sword)
813: fastmap[j] = 1;
814: break;
815:
816: case notwordchar:
817: for (j = 0; j < (1 << BYTEWIDTH); j++)
818: if (SYNTAX (j) != Sword)
819: fastmap[j] = 1;
820: break;
821:
822: #ifdef emacs
823: case syntaxspec:
824: k = *p++;
825: for (j = 0; j < (1 << BYTEWIDTH); j++)
826: if (SYNTAX (j) == (enum syntaxcode) k)
827: fastmap[j] = 1;
828: break;
829:
830: case notsyntaxspec:
831: k = *p++;
832: for (j = 0; j < (1 << BYTEWIDTH); j++)
833: if (SYNTAX (j) != (enum syntaxcode) k)
834: fastmap[j] = 1;
835: break;
836: #endif emacs
837:
838: case charset:
839: for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
840: if (p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH)))
841: {
842: if (translate)
843: fastmap[translate[j]] = 1;
844: else
845: fastmap[j] = 1;
846: }
847: break;
848:
849: case charset_not:
850: /* Chars beyond end of map must be allowed */
851: for (j = *p * BYTEWIDTH; j < (1 << BYTEWIDTH); j++)
852: if (translate)
853: fastmap[translate[j]] = 1;
854: else
855: fastmap[j] = 1;
856:
857: for (j = *p++ * BYTEWIDTH - 1; j >= 0; j--)
858: if (!(p[j / BYTEWIDTH] & (1 << (j % BYTEWIDTH))))
859: {
860: if (translate)
861: fastmap[translate[j]] = 1;
862: else
863: fastmap[j] = 1;
864: }
865: break;
866: }
867:
868: /* Get here means we have successfully found the possible starting characters
869: of one path of the pattern. We need not follow this path any farther.
870: Instead, look at the next alternative remembered in the stack. */
871: if (stackp != stackb)
872: p = *stackp--;
873: else
874: break;
875: }
876: }
877:
878: /* Like re_search_2, below, but only one string is specified. */
879:
880: int
881: re_search (pbufp, string, size, startpos, range, regs)
882: struct re_pattern_buffer *pbufp;
883: char *string;
884: int size, startpos, range;
885: struct re_registers *regs;
886: {
887: return re_search_2 (pbufp, 0, 0, string, size, startpos, range, regs, size);
888: }
889:
890: /* Like re_match_2 but tries first a match starting at index STARTPOS,
891: then at STARTPOS + 1, and so on.
892: RANGE is the number of places to try before giving up.
893: If RANGE is negative, the starting positions tried are
894: STARTPOS, STARTPOS - 1, etc.
895: It is up to the caller to make sure that range is not so large
896: as to take the starting position outside of the input strings.
897:
898: The value returned is the position at which the match was found,
899: or -1 if no match was found,
900: or -2 if error (such as failure stack overflow). */
901:
902: int
903: re_search_2 (pbufp, string1, size1, string2, size2, startpos, range, regs, mstop)
904: struct re_pattern_buffer *pbufp;
905: char *string1, *string2;
906: int size1, size2;
907: int startpos;
908: register int range;
909: struct re_registers *regs;
910: int mstop;
911: {
912: register char *fastmap = pbufp->fastmap;
913: register unsigned char *translate = (unsigned char *) pbufp->translate;
914: int total = size1 + size2;
915: int val;
916:
917: /* Update the fastmap now if not correct already */
918: if (fastmap && !pbufp->fastmap_accurate)
919: re_compile_fastmap (pbufp);
920:
921: /* Don't waste time in a long search for a pattern
922: that says it is anchored. */
923: if (pbufp->used > 0 && (enum regexpcode) pbufp->buffer[0] == begbuf
924: && range > 0)
925: {
926: if (startpos > 0)
927: return -1;
928: else
929: range = 1;
930: }
931:
932: while (1)
933: {
934: /* If a fastmap is supplied, skip quickly over characters
935: that cannot possibly be the start of a match.
936: Note, however, that if the pattern can possibly match
937: the null string, we must test it at each starting point
938: so that we take the first null string we get. */
939:
940: if (fastmap && startpos < total && pbufp->can_be_null != 1)
941: {
942: if (range > 0)
943: {
944: register int lim = 0;
945: register unsigned char *p;
946: int irange = range;
947: if (startpos < size1 && startpos + range >= size1)
948: lim = range - (size1 - startpos);
949:
950: p = ((unsigned char *)
951: &(startpos >= size1 ? string2 - size1 : string1)[startpos]);
952:
953: if (translate)
954: {
955: while (range > lim && !fastmap[translate[*p++]])
956: range--;
957: }
958: else
959: {
960: while (range > lim && !fastmap[*p++])
961: range--;
962: }
963: startpos += irange - range;
964: }
965: else
966: {
967: register unsigned char c;
968: if (startpos >= size1)
969: c = string2[startpos - size1];
970: else
971: c = string1[startpos];
972: c &= 0xff;
973: if (translate ? !fastmap[translate[c]] : !fastmap[c])
974: goto advance;
975: }
976: }
977:
978: if (range >= 0 && startpos == total
979: && fastmap && pbufp->can_be_null == 0)
980: return -1;
981:
982: val = re_match_2 (pbufp, string1, size1, string2, size2, startpos, regs,
983: mstop);
984: /* Propagate error indication if worse than mere failure. */
985: if (val == -2)
986: return -2;
987: /* Return position on success. */
988: if (0 <= val)
989: return startpos;
990:
991: #ifdef C_ALLOCA
992: alloca (0);
993: #endif /* C_ALLOCA */
994:
995: advance:
996: if (!range) break;
997: if (range > 0) range--, startpos++; else range++, startpos--;
998: }
999: return -1;
1000: }
1001:
1002: #ifndef emacs /* emacs never uses this */
1003: int
1004: re_match (pbufp, string, size, pos, regs)
1005: struct re_pattern_buffer *pbufp;
1006: char *string;
1007: int size, pos;
1008: struct re_registers *regs;
1009: {
1010: return re_match_2 (pbufp, 0, 0, string, size, pos, regs, size);
1011: }
1012: #endif /* emacs */
1013:
1014: /* Maximum size of failure stack. Beyond this, overflow is an error. */
1015:
1016: int re_max_failures = 2000;
1017:
1018: static int bcmp_translate();
1019: /* Match the pattern described by PBUFP
1020: against data which is the virtual concatenation of STRING1 and STRING2.
1021: SIZE1 and SIZE2 are the sizes of the two data strings.
1022: Start the match at position POS.
1023: Do not consider matching past the position MSTOP.
1024:
1025: If pbufp->fastmap is nonzero, then it had better be up to date.
1026:
1027: The reason that the data to match are specified as two components
1028: which are to be regarded as concatenated
1029: is so this function can be used directly on the contents of an Emacs buffer.
1030:
1031: -1 is returned if there is no match. -2 is returned if there is
1032: an error (such as match stack overflow). Otherwise the value is the length
1033: of the substring which was matched. */
1034:
1035: int
1036: re_match_2 (pbufp, string1, size1, string2, size2, pos, regs, mstop)
1037: struct re_pattern_buffer *pbufp;
1038: unsigned char *string1, *string2;
1039: int size1, size2;
1040: int pos;
1041: struct re_registers *regs;
1042: int mstop;
1043: {
1044: register unsigned char *p = (unsigned char *) pbufp->buffer;
1045: register unsigned char *pend = p + pbufp->used;
1046: /* End of first string */
1047: unsigned char *end1;
1048: /* End of second string */
1049: unsigned char *end2;
1050: /* Pointer just past last char to consider matching */
1051: unsigned char *end_match_1, *end_match_2;
1052: register unsigned char *d, *dend;
1053: register int mcnt;
1054: unsigned char *translate = (unsigned char *) pbufp->translate;
1055:
1056: /* Failure point stack. Each place that can handle a failure further down the line
1057: pushes a failure point on this stack. It consists of two char *'s.
1058: The first one pushed is where to resume scanning the pattern;
1059: the second pushed is where to resume scanning the strings.
1060: If the latter is zero, the failure point is a "dummy".
1061: If a failure happens and the innermost failure point is dormant,
1062: it discards that failure point and tries the next one. */
1063:
1064: unsigned char *initial_stack[2 * NFAILURES];
1065: unsigned char **stackb = initial_stack;
1066: unsigned char **stackp = stackb, **stacke = &stackb[2 * NFAILURES];
1067:
1068: /* Information on the "contents" of registers.
1069: These are pointers into the input strings; they record
1070: just what was matched (on this attempt) by some part of the pattern.
1071: The start_memory command stores the start of a register's contents
1072: and the stop_memory command stores the end.
1073:
1074: At that point, regstart[regnum] points to the first character in the register,
1075: regend[regnum] points to the first character beyond the end of the register,
1076: regstart_seg1[regnum] is true iff regstart[regnum] points into string1,
1077: and regend_seg1[regnum] is true iff regend[regnum] points into string1. */
1078:
1079: unsigned char *regstart[RE_NREGS];
1080: unsigned char *regend[RE_NREGS];
1081: unsigned char regstart_seg1[RE_NREGS], regend_seg1[RE_NREGS];
1082:
1083: /* Set up pointers to ends of strings.
1084: Don't allow the second string to be empty unless both are empty. */
1085: if (!size2)
1086: {
1087: string2 = string1;
1088: size2 = size1;
1089: string1 = 0;
1090: size1 = 0;
1091: }
1092: end1 = string1 + size1;
1093: end2 = string2 + size2;
1094:
1095: /* Compute where to stop matching, within the two strings */
1096: if (mstop <= size1)
1097: {
1098: end_match_1 = string1 + mstop;
1099: end_match_2 = string2;
1100: }
1101: else
1102: {
1103: end_match_1 = end1;
1104: end_match_2 = string2 + mstop - size1;
1105: }
1106:
1107: /* Initialize \) text positions to -1
1108: to mark ones that no \( or \) has been seen for. */
1109:
1110: for (mcnt = 0; mcnt < sizeof (regend) / sizeof (*regend); mcnt++)
1111: regend[mcnt] = (unsigned char *) -1;
1112:
1113: /* `p' scans through the pattern as `d' scans through the data.
1114: `dend' is the end of the input string that `d' points within.
1115: `d' is advanced into the following input string whenever necessary,
1116: but this happens before fetching;
1117: therefore, at the beginning of the loop,
1118: `d' can be pointing at the end of a string,
1119: but it cannot equal string2. */
1120:
1121: if (pos <= size1)
1122: d = string1 + pos, dend = end_match_1;
1123: else
1124: d = string2 + pos - size1, dend = end_match_2;
1125:
1126: /* Write PREFETCH; just before fetching a character with *d. */
1127: #define PREFETCH \
1128: while (d == dend) \
1129: { if (dend == end_match_2) goto fail; /* end of string2 => failure */ \
1130: d = string2; /* end of string1 => advance to string2. */ \
1131: dend = end_match_2; }
1132:
1133: /* This loop loops over pattern commands.
1134: It exits by returning from the function if match is complete,
1135: or it drops through if match fails at this starting point in the input data. */
1136:
1137: while (1)
1138: {
1139: if (p == pend)
1140: /* End of pattern means we have succeeded! */
1141: {
1142: /* If caller wants register contents data back, convert it to indices */
1143: if (regs)
1144: {
1145: regs->start[0] = pos;
1146: if (dend == end_match_1)
1147: regs->end[0] = d - string1;
1148: else
1149: regs->end[0] = d - string2 + size1;
1150: for (mcnt = 1; mcnt < RE_NREGS; mcnt++)
1151: {
1152: if (regend[mcnt] == (unsigned char *) -1)
1153: {
1154: regs->start[mcnt] = -1;
1155: regs->end[mcnt] = -1;
1156: continue;
1157: }
1158: if (regstart_seg1[mcnt])
1159: regs->start[mcnt] = regstart[mcnt] - string1;
1160: else
1161: regs->start[mcnt] = regstart[mcnt] - string2 + size1;
1162: if (regend_seg1[mcnt])
1163: regs->end[mcnt] = regend[mcnt] - string1;
1164: else
1165: regs->end[mcnt] = regend[mcnt] - string2 + size1;
1166: }
1167: }
1168: if (dend == end_match_1)
1169: return (d - string1 - pos);
1170: else
1171: return d - string2 + size1 - pos;
1172: }
1173:
1174: /* Otherwise match next pattern command */
1175: #ifdef SWITCH_ENUM_BUG
1176: switch ((int) ((enum regexpcode) *p++))
1177: #else
1178: switch ((enum regexpcode) *p++)
1179: #endif
1180: {
1181:
1182: /* \( is represented by a start_memory, \) by a stop_memory.
1183: Both of those commands contain a "register number" argument.
1184: The text matched within the \( and \) is recorded under that number.
1185: Then, \<digit> turns into a `duplicate' command which
1186: is followed by the numeric value of <digit> as the register number. */
1187:
1188: case start_memory:
1189: regstart[*p] = d;
1190: regstart_seg1[*p++] = (dend == end_match_1);
1191: break;
1192:
1193: case stop_memory:
1194: regend[*p] = d;
1195: regend_seg1[*p++] = (dend == end_match_1);
1196: break;
1197:
1198: case duplicate:
1199: {
1200: int regno = *p++; /* Get which register to match against */
1201: register unsigned char *d2, *dend2;
1202:
1203: /* Don't allow matching a register that hasn't been used.
1204: This isn't fully reliable in the current version,
1205: but it is better than crashing. */
1206: if ((int) regend[regno] == -1)
1207: goto fail;
1208:
1209: d2 = regstart[regno];
1210: dend2 = ((regstart_seg1[regno] == regend_seg1[regno])
1211: ? regend[regno] : end_match_1);
1212: while (1)
1213: {
1214: /* Advance to next segment in register contents, if necessary */
1215: while (d2 == dend2)
1216: {
1217: if (dend2 == end_match_2) break;
1218: if (dend2 == regend[regno]) break;
1219: d2 = string2, dend2 = regend[regno]; /* end of string1 => advance to string2. */
1220: }
1221: /* At end of register contents => success */
1222: if (d2 == dend2) break;
1223:
1224: /* Advance to next segment in data being matched, if necessary */
1225: PREFETCH;
1226:
1227: /* mcnt gets # consecutive chars to compare */
1228: mcnt = dend - d;
1229: if (mcnt > dend2 - d2)
1230: mcnt = dend2 - d2;
1231: /* Compare that many; failure if mismatch, else skip them. */
1232: if (translate ? bcmp_translate (d, d2, mcnt, translate) : bcmp (d, d2, mcnt))
1233: goto fail;
1234: d += mcnt, d2 += mcnt;
1235: }
1236: }
1237: break;
1238:
1239: case anychar:
1240: /* fetch a data character */
1241: PREFETCH;
1242: /* Match anything but a newline. */
1243: if ((translate ? translate[*d++] : *d++) == '\n')
1244: goto fail;
1245: break;
1246:
1247: case charset:
1248: case charset_not:
1249: {
1250: /* Nonzero for charset_not */
1251: int not = 0;
1252: register int c;
1253: if (*(p - 1) == (unsigned char) charset_not)
1254: not = 1;
1255:
1256: /* fetch a data character */
1257: PREFETCH;
1258:
1259: if (translate)
1260: c = translate [*d];
1261: else
1262: c = *d;
1263:
1264: if (c < *p * BYTEWIDTH
1265: && p[1 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
1266: not = !not;
1267:
1268: p += 1 + *p;
1269:
1270: if (!not) goto fail;
1271: d++;
1272: break;
1273: }
1274:
1275: case begline:
1276: if (d == string1 || d[-1] == '\n')
1277: break;
1278: goto fail;
1279:
1280: case endline:
1281: if (d == end2
1282: || (d == end1 ? (size2 == 0 || *string2 == '\n') : *d == '\n'))
1283: break;
1284: goto fail;
1285:
1286: /* "or" constructs ("|") are handled by starting each alternative
1287: with an on_failure_jump that points to the start of the next alternative.
1288: Each alternative except the last ends with a jump to the joining point.
1289: (Actually, each jump except for the last one really jumps
1290: to the following jump, because tensioning the jumps is a hassle.) */
1291:
1292: /* The start of a stupid repeat has an on_failure_jump that points
1293: past the end of the repeat text.
1294: This makes a failure point so that, on failure to match a repetition,
1295: matching restarts past as many repetitions have been found
1296: with no way to fail and look for another one. */
1297:
1298: /* A smart repeat is similar but loops back to the on_failure_jump
1299: so that each repetition makes another failure point. */
1300:
1301: case on_failure_jump:
1302: if (stackp == stacke)
1303: {
1304: unsigned char **stackx;
1305: if (stacke - stackb > re_max_failures)
1306: return -2;
1307: stackx = (unsigned char **) alloca (2 * (stacke - stackb)
1308: * sizeof (char *));
1309: bcopy (stackb, stackx, (stacke - stackb) * sizeof (char *));
1310: stackp = stackx + (stackp - stackb);
1311: stacke = stackx + 2 * (stacke - stackb);
1312: stackb = stackx;
1313: }
1314: mcnt = *p++ & 0377;
1315: mcnt += SIGN_EXTEND_CHAR (*(char *)p) << 8;
1316: p++;
1317: *stackp++ = mcnt + p;
1318: *stackp++ = d;
1319: break;
1320:
1321: /* The end of a smart repeat has an maybe_finalize_jump back.
1322: Change it either to a finalize_jump or an ordinary jump. */
1323:
1324: case maybe_finalize_jump:
1325: mcnt = *p++ & 0377;
1326: mcnt += SIGN_EXTEND_CHAR (*(char *)p) << 8;
1327: p++;
1328: /* Compare what follows with the begining of the repeat.
1329: If we can establish that there is nothing that they would
1330: both match, we can change to finalize_jump */
1331: if (p == pend)
1332: p[-3] = (unsigned char) finalize_jump;
1333: else if (*p == (unsigned char) exactn
1334: || *p == (unsigned char) endline)
1335: {
1336: register int c = *p == (unsigned char) endline ? '\n' : p[2];
1337: register unsigned char *p1 = p + mcnt;
1338: /* p1[0] ... p1[2] are an on_failure_jump.
1339: Examine what follows that */
1340: if (p1[3] == (unsigned char) exactn && p1[5] != c)
1341: p[-3] = (unsigned char) finalize_jump;
1342: else if (p1[3] == (unsigned char) charset
1343: || p1[3] == (unsigned char) charset_not)
1344: {
1345: int not = p1[3] == (unsigned char) charset_not;
1346: if (c < p1[4] * BYTEWIDTH
1347: && p1[5 + c / BYTEWIDTH] & (1 << (c % BYTEWIDTH)))
1348: not = !not;
1349: /* not is 1 if c would match */
1350: /* That means it is not safe to finalize */
1351: if (!not)
1352: p[-3] = (unsigned char) finalize_jump;
1353: }
1354: }
1355: p -= 2;
1356: if (p[-1] != (unsigned char) finalize_jump)
1357: {
1358: p[-1] = (unsigned char) jump;
1359: goto nofinalize;
1360: }
1361:
1362: /* The end of a stupid repeat has a finalize-jump
1363: back to the start, where another failure point will be made
1364: which will point after all the repetitions found so far. */
1365:
1366: case finalize_jump:
1367: stackp -= 2;
1368:
1369: case jump:
1370: nofinalize:
1371: mcnt = *p++ & 0377;
1372: mcnt += SIGN_EXTEND_CHAR (*(char *)p) << 8;
1373: p += mcnt + 1; /* The 1 compensates for missing ++ above */
1374: break;
1375:
1376: case dummy_failure_jump:
1377: if (stackp == stacke)
1378: {
1379: unsigned char **stackx
1380: = (unsigned char **) alloca (2 * (stacke - stackb)
1381: * sizeof (char *));
1382: bcopy (stackb, stackx, (stacke - stackb) * sizeof (char *));
1383: stackp = stackx + (stackp - stackb);
1384: stacke = stackx + 2 * (stacke - stackb);
1385: stackb = stackx;
1386: }
1387: *stackp++ = 0;
1388: *stackp++ = 0;
1389: goto nofinalize;
1390:
1391: case wordbound:
1392: if (d == string1 /* Points to first char */
1393: || d == end2 /* Points to end */
1394: || (d == end1 && size2 == 0)) /* Points to end */
1395: break;
1396: if ((SYNTAX (d[-1]) == Sword)
1397: != (SYNTAX (d == end1 ? *string2 : *d) == Sword))
1398: break;
1399: goto fail;
1400:
1401: case notwordbound:
1402: if (d == string1 /* Points to first char */
1403: || d == end2 /* Points to end */
1404: || (d == end1 && size2 == 0)) /* Points to end */
1405: goto fail;
1406: if ((SYNTAX (d[-1]) == Sword)
1407: != (SYNTAX (d == end1 ? *string2 : *d) == Sword))
1408: goto fail;
1409: break;
1410:
1411: case wordbeg:
1412: if (d == end2 /* Points to end */
1413: || (d == end1 && size2 == 0) /* Points to end */
1414: || SYNTAX (* (d == end1 ? string2 : d)) != Sword) /* Next char not a letter */
1415: goto fail;
1416: if (d == string1 /* Points to first char */
1417: || SYNTAX (d[-1]) != Sword) /* prev char not letter */
1418: break;
1419: goto fail;
1420:
1421: case wordend:
1422: if (d == string1 /* Points to first char */
1423: || SYNTAX (d[-1]) != Sword) /* prev char not letter */
1424: goto fail;
1425: if (d == end2 /* Points to end */
1426: || (d == end1 && size2 == 0) /* Points to end */
1427: || SYNTAX (d == end1 ? *string2 : *d) != Sword) /* Next char not a letter */
1428: break;
1429: goto fail;
1430:
1431: #ifdef emacs
1432: case before_dot:
1433: if (PTR_CHAR_POS (d) + 1 >= point)
1434: goto fail;
1435: break;
1436:
1437: case at_dot:
1438: if (PTR_CHAR_POS (d) + 1 != point)
1439: goto fail;
1440: break;
1441:
1442: case after_dot:
1443: if (PTR_CHAR_POS (d) + 1 <= point)
1444: goto fail;
1445: break;
1446:
1447: case wordchar:
1448: mcnt = (int) Sword;
1449: goto matchsyntax;
1450:
1451: case syntaxspec:
1452: mcnt = *p++;
1453: matchsyntax:
1454: PREFETCH;
1455: if (SYNTAX (*d++) != (enum syntaxcode) mcnt) goto fail;
1456: break;
1457:
1458: case notwordchar:
1459: mcnt = (int) Sword;
1460: goto matchnotsyntax;
1461:
1462: case notsyntaxspec:
1463: mcnt = *p++;
1464: matchnotsyntax:
1465: PREFETCH;
1466: if (SYNTAX (*d++) == (enum syntaxcode) mcnt) goto fail;
1467: break;
1468: #else
1469: case wordchar:
1470: PREFETCH;
1471: if (SYNTAX (*d++) == 0) goto fail;
1472: break;
1473:
1474: case notwordchar:
1475: PREFETCH;
1476: if (SYNTAX (*d++) != 0) goto fail;
1477: break;
1478: #endif not emacs
1479:
1480: case begbuf:
1481: if (d == string1) /* Note, d cannot equal string2 */
1482: break; /* unless string1 == string2. */
1483: goto fail;
1484:
1485: case endbuf:
1486: if (d == end2 || (d == end1 && size2 == 0))
1487: break;
1488: goto fail;
1489:
1490: case exactn:
1491: /* Match the next few pattern characters exactly.
1492: mcnt is how many characters to match. */
1493: mcnt = *p++;
1494: if (translate)
1495: {
1496: do
1497: {
1498: PREFETCH;
1499: if (translate[*d++] != *p++) goto fail;
1500: }
1501: while (--mcnt);
1502: }
1503: else
1504: {
1505: do
1506: {
1507: PREFETCH;
1508: if (*d++ != *p++) goto fail;
1509: }
1510: while (--mcnt);
1511: }
1512: break;
1513: }
1514: continue; /* Successfully matched one pattern command; keep matching */
1515:
1516: /* Jump here if any matching operation fails. */
1517: fail:
1518: if (stackp != stackb)
1519: /* A restart point is known. Restart there and pop it. */
1520: {
1521: if (!stackp[-2])
1522: { /* If innermost failure point is dormant, flush it and keep looking */
1523: stackp -= 2;
1524: goto fail;
1525: }
1526: d = *--stackp;
1527: p = *--stackp;
1528: if (d >= string1 && d <= end1)
1529: dend = end_match_1;
1530: }
1531: else break; /* Matching at this starting point really fails! */
1532: }
1533: return -1; /* Failure to match */
1534: }
1535:
1536: static int
1537: bcmp_translate (s1, s2, len, translate)
1538: unsigned char *s1, *s2;
1539: register int len;
1540: unsigned char *translate;
1541: {
1542: register unsigned char *p1 = s1, *p2 = s2;
1543: while (len)
1544: {
1545: if (translate [*p1++] != translate [*p2++]) return 1;
1546: len--;
1547: }
1548: return 0;
1549: }
1550:
1551: /* Entry points compatible with bsd4.2 regex library */
1552:
1553: #ifndef emacs
1554:
1555: static struct re_pattern_buffer re_comp_buf;
1556:
1557: char *
1558: re_comp (s)
1559: char *s;
1560: {
1561: if (!s)
1562: {
1563: if (!re_comp_buf.buffer)
1564: return "No previous regular expression";
1565: return 0;
1566: }
1567:
1568: if (!re_comp_buf.buffer)
1569: {
1570: if (!(re_comp_buf.buffer = (char *) malloc (200)))
1571: return "Memory exhausted";
1572: re_comp_buf.allocated = 200;
1573: if (!(re_comp_buf.fastmap = (char *) malloc (1 << BYTEWIDTH)))
1574: return "Memory exhausted";
1575: }
1576: return re_compile_pattern (s, strlen (s), &re_comp_buf);
1577: }
1578:
1579: int
1580: re_exec (s)
1581: char *s;
1582: {
1583: int len = strlen (s);
1584: return 0 <= re_search (&re_comp_buf, s, len, 0, len, 0);
1585: }
1586:
1587: #endif /* emacs */
1588:
1589: #ifdef test
1590:
1591: #include <stdio.h>
1592:
1593: /* Indexed by a character, gives the upper case equivalent of the character */
1594:
1595: static char upcase[0400] =
1596: { 000, 001, 002, 003, 004, 005, 006, 007,
1597: 010, 011, 012, 013, 014, 015, 016, 017,
1598: 020, 021, 022, 023, 024, 025, 026, 027,
1599: 030, 031, 032, 033, 034, 035, 036, 037,
1600: 040, 041, 042, 043, 044, 045, 046, 047,
1601: 050, 051, 052, 053, 054, 055, 056, 057,
1602: 060, 061, 062, 063, 064, 065, 066, 067,
1603: 070, 071, 072, 073, 074, 075, 076, 077,
1604: 0100, 0101, 0102, 0103, 0104, 0105, 0106, 0107,
1605: 0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117,
1606: 0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127,
1607: 0130, 0131, 0132, 0133, 0134, 0135, 0136, 0137,
1608: 0140, 0101, 0102, 0103, 0104, 0105, 0106, 0107,
1609: 0110, 0111, 0112, 0113, 0114, 0115, 0116, 0117,
1610: 0120, 0121, 0122, 0123, 0124, 0125, 0126, 0127,
1611: 0130, 0131, 0132, 0173, 0174, 0175, 0176, 0177,
1612: 0200, 0201, 0202, 0203, 0204, 0205, 0206, 0207,
1613: 0210, 0211, 0212, 0213, 0214, 0215, 0216, 0217,
1614: 0220, 0221, 0222, 0223, 0224, 0225, 0226, 0227,
1615: 0230, 0231, 0232, 0233, 0234, 0235, 0236, 0237,
1616: 0240, 0241, 0242, 0243, 0244, 0245, 0246, 0247,
1617: 0250, 0251, 0252, 0253, 0254, 0255, 0256, 0257,
1618: 0260, 0261, 0262, 0263, 0264, 0265, 0266, 0267,
1619: 0270, 0271, 0272, 0273, 0274, 0275, 0276, 0277,
1620: 0300, 0301, 0302, 0303, 0304, 0305, 0306, 0307,
1621: 0310, 0311, 0312, 0313, 0314, 0315, 0316, 0317,
1622: 0320, 0321, 0322, 0323, 0324, 0325, 0326, 0327,
1623: 0330, 0331, 0332, 0333, 0334, 0335, 0336, 0337,
1624: 0340, 0341, 0342, 0343, 0344, 0345, 0346, 0347,
1625: 0350, 0351, 0352, 0353, 0354, 0355, 0356, 0357,
1626: 0360, 0361, 0362, 0363, 0364, 0365, 0366, 0367,
1627: 0370, 0371, 0372, 0373, 0374, 0375, 0376, 0377
1628: };
1629:
1630: main (argc, argv)
1631: int argc;
1632: char **argv;
1633: {
1634: char pat[80];
1635: struct re_pattern_buffer buf;
1636: int i;
1637: char c;
1638: char fastmap[(1 << BYTEWIDTH)];
1639:
1640: /* Allow a command argument to specify the style of syntax. */
1641: if (argc > 1)
1642: obscure_syntax = atoi (argv[1]);
1643:
1644: buf.allocated = 40;
1645: buf.buffer = (char *) malloc (buf.allocated);
1646: buf.fastmap = fastmap;
1647: buf.translate = upcase;
1648:
1649: while (1)
1650: {
1651: gets (pat);
1652:
1653: if (*pat)
1654: {
1655: re_compile_pattern (pat, strlen(pat), &buf);
1656:
1657: for (i = 0; i < buf.used; i++)
1658: printchar (buf.buffer[i]);
1659:
1660: putchar ('\n');
1661:
1662: printf ("%d allocated, %d used.\n", buf.allocated, buf.used);
1663:
1664: re_compile_fastmap (&buf);
1665: printf ("Allowed by fastmap: ");
1666: for (i = 0; i < (1 << BYTEWIDTH); i++)
1667: if (fastmap[i]) printchar (i);
1668: putchar ('\n');
1669: }
1670:
1671: gets (pat); /* Now read the string to match against */
1672:
1673: i = re_match (&buf, pat, strlen (pat), 0, 0);
1674: printf ("Match value %d.\n", i);
1675: }
1676: }
1677:
1678: #ifdef NOTDEF
1679: print_buf (bufp)
1680: struct re_pattern_buffer *bufp;
1681: {
1682: int i;
1683:
1684: printf ("buf is :\n----------------\n");
1685: for (i = 0; i < bufp->used; i++)
1686: printchar (bufp->buffer[i]);
1687:
1688: printf ("\n%d allocated, %d used.\n", bufp->allocated, bufp->used);
1689:
1690: printf ("Allowed by fastmap: ");
1691: for (i = 0; i < (1 << BYTEWIDTH); i++)
1692: if (bufp->fastmap[i])
1693: printchar (i);
1694: printf ("\nAllowed by translate: ");
1695: if (bufp->translate)
1696: for (i = 0; i < (1 << BYTEWIDTH); i++)
1697: if (bufp->translate[i])
1698: printchar (i);
1699: printf ("\nfastmap is%s accurate\n", bufp->fastmap_accurate ? "" : "n't");
1700: printf ("can %s be null\n----------", bufp->can_be_null ? "" : "not");
1701: }
1702: #endif
1703:
1704: printchar (c)
1705: char c;
1706: {
1707: if (c < 041 || c >= 0177)
1708: {
1709: putchar ('\\');
1710: putchar (((c >> 6) & 3) + '0');
1711: putchar (((c >> 3) & 7) + '0');
1712: putchar ((c & 7) + '0');
1713: }
1714: else
1715: putchar (c);
1716: }
1717:
1718: error (string)
1719: char *string;
1720: {
1721: puts (string);
1722: exit (1);
1723: }
1724:
1725: #endif test
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.