/* vi:ts=4:sw=4 * NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE * * This is NOT the original regular expression code as written by * Henry Spencer. This code has been modified specifically for use * with the VIM editor, and should not be used apart from compiling * VIM. If you want a good regular expression library, get the * original code. The copyright notice that follows is from the * original. * * Furthermore, this code is modified to work on Japanese letters * for use with the JVim editor. * * NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE * * * regcomp and regexec -- regsub and regerror are elsewhere * * Copyright (c) 1986 by University of Toronto. * Written by Henry Spencer. Not derived from licensed software. * * Permission is granted to anyone to use this software for any * purpose on any computer system, and to redistribute it freely, * subject to the following restrictions: * * 1. The author is not responsible for the consequences of use of * this software, no matter how awful, even if they arise * from defects in it. * * 2. The origin of this software must not be misrepresented, either * by explicit claim or by omission. * * 3. Altered versions must be plainly marked as such, and must not * be misrepresented as being the original software. * * Beware that some of this code is subtly aware of the way operator * precedence is structured in regular expressions. Serious changes in * regular-expression syntax might require a total rethink. * * $Log: regexp.c,v $ * Revision 1.2 88/04/28 08:09:45 tony * First modification of the regexp library. Added an external variable * 'reg_ic' which can be set to indicate that case should be ignored. * Added a new parameter to regexec() to indicate that the given string * comes from the beginning of a line and is thus eligible to match * 'beginning-of-line'. * * Revisions by Olaf 'Rhialto' Seibert, rhialto@cs.kun.nl: * Changes for vi: (the semantics of several things were rather different) * - Added lexical analyzer, because in vi magicness of characters * is rather difficult, and may change over time. * - Added support for \< \> \1-\9 and ~ * - Left some magic stuff in, but only backslashed: \| \+ * - * and \+ still work after \) even though they shouldn't. */ #include "vim.h" #include "globals.h" #include "proto.h" #include "jp.h" #undef DEBUG #include #include "regexp.h" #include "regmagic.h" /* * The "internal use only" fields in regexp.h are present to pass info from * compile to execute that permits the execute phase to run lots faster on * simple cases. They are: * * regstart char that must begin a match; '\0' if none obvious * reganch is the match anchored (at beginning-of-line only)? * regmust string (pointer into program) that match must include, or NULL * regmlen length of regmust string * * Regstart and reganch permit very fast decisions on suitable starting points * for a match, cutting down the work a lot. Regmust permits fast rejection * of lines that cannot possibly match. The regmust tests are costly enough * that regcomp() supplies a regmust only if the r.e. contains something * potentially expensive (at present, the only such thing detected is * or + * at the start of the r.e., which can involve a lot of backup). Regmlen is * supplied because the test in regexec() needs it and regcomp() is computing * it anyway. */ /* * Structure for regexp "program". This is essentially a linear encoding * of a nondeterministic finite-state machine (aka syntax charts or * "railroad normal form" in parsing technology). Each node is an opcode * plus a "next" pointer, possibly plus an operand. "Next" pointers of * all nodes except BRANCH implement concatenation; a "next" pointer with * a BRANCH on both ends of it is connecting two alternatives. (Here we * have one of the subtle syntax dependencies: an individual BRANCH (as * opposed to a collection of them) is never concatenated with anything * because of operator precedence.) The operand of some types of node is * a literal string; for others, it is a node leading into a sub-FSM. In * particular, the operand of a BRANCH node is the first node of the branch. * (NB this is *not* a tree structure: the tail of the branch connects * to the thing following the set of BRANCHes.) The opcodes are: */ /* definition number opnd? meaning */ #define END 0 /* no End of program. */ #define BOL 1 /* no Match "" at beginning of line. */ #define EOL 2 /* no Match "" at end of line. */ #define ANY 3 /* no Match any one character. */ #define ANYOF 4 /* str Match any character in this string. */ #define ANYBUT 5 /* str Match any character not in this * string. */ #define BRANCH 6 /* node Match this alternative, or the * next... */ #define BACK 7 /* no Match "", "next" ptr points backward. */ #define EXACTLY 8 /* str Match this string. */ #define NOTHING 9 /* no Match empty string. */ #define STAR 10 /* node Match this (simple) thing 0 or more * times. */ #define PLUS 11 /* node Match this (simple) thing 1 or more * times. */ #define BOW 12 /* no Match "" after [^a-zA-Z0-9_] */ #define EOW 13 /* no Match "" at [^a-zA-Z0-9_] */ #define MOPEN 20 /* no Mark this point in input as start of * #n. */ /* MOPEN+1 is number 1, etc. */ #define MCLOSE 30 /* no Analogous to MOPEN. */ #define BACKREF 40 /* node Match same string again \1-\9 */ #define Magic(x) ((x)|('\\'<<8)) /* * Opcode notes: * * BRANCH The set of branches constituting a single choice are hooked * together with their "next" pointers, since precedence prevents * anything being concatenated to any individual branch. The * "next" pointer of the last BRANCH in a choice points to the * thing following the whole choice. This is also where the * final "next" pointer of each individual branch points; each * branch starts with the operand node of a BRANCH node. * * BACK Normal "next" pointers all implicitly point forward; BACK * exists to make loop structures possible. * * STAR,PLUS '?', and complex '*' and '+', are implemented as circular * BRANCH structures using BACK. Simple cases (one character * per match) are implemented with STAR and PLUS for speed * and to minimize recursive plunges. * * MOPEN,MCLOSE ...are numbered at compile time. */ /* * A node is one char of opcode followed by two chars of "next" pointer. * "Next" pointers are stored as two 8-bit pieces, high order first. The * value is a positive offset from the opcode of the node containing it. * An operand, if any, simply follows the node. (Note that much of the * code generation knows about this implicit relationship.) * * Using two bytes for the "next" pointer is vast overkill for most things, * but allows patterns to get big without disasters. */ #define OP(p) (*(p)) #define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377)) #define OPERAND(p) ((p) + 3) /* * See regmagic.h for one further detail of program structure. */ /* * Utility definitions. */ #ifndef CHARBITS #define UCHARAT(p) ((int)*(unsigned char *)(p)) #else #define UCHARAT(p) ((int)*(p)&CHARBITS) #endif #define FAIL(m) { emsg(m); return NULL; } static int ismult __ARGS((int)); #ifdef DEBUG void regdump __ARGS((regexp *)); #endif static int ismult(c) int c; { return (c == Magic('*') || c == Magic('+') || c == Magic('?')); } /* * Flags to be passed up and down. */ #define HASWIDTH 01 /* Known never to match null string. */ #define SIMPLE 02 /* Simple enough to be STAR/PLUS operand. */ #define SPSTART 04 /* Starts with * or +. */ #define WORST 0 /* Worst case. */ /* * The following supports the ability to ignore case in searches. */ int reg_ic = 0; /* set by callers to ignore case */ /* * mkup - convert to upper case IF we're doing caseless compares */ #define mkup(c) (reg_ic ? TO_UPPER(c) : (c)) /* * The following allows empty REs, meaning "the same as the previous RE". * per the ed(1) manual. */ /* #define EMPTY_RE */ /* this is done outside of regexp */ #ifdef EMPTY_RE char *reg_prev_re; #endif #define TILDE #ifdef TILDE char *reg_prev_sub; #endif /* * This if for vi's "magic" mode. If magic is false, only ^$\ are magic. */ int reg_magic = 1; /* * Global work variables for regcomp(). */ static unsigned char *regparse; /* Input-scan pointer. */ static int regnpar; /* () count. */ static char regdummy; static char *regcode; /* Code-emit pointer; ®dummy = don't. */ static long regsize; /* Code size. */ static char **regendp; /* Ditto for endp. */ /* * META contains all characters that may be magic, except '^' and '$'. * This depends on the configuration options TILDE, BACKREF. * (could be done simpler for compilers that know string concatenation) */ #ifdef TILDE # ifdef BACKREF static char META[] = ".[()|?+*<>~123456789"; # else static char META[] = ".[()|?+*<>~"; # endif #else # ifdef BACKREF static char META[] = ".[()|?+*<>123456789"; # else static char META[] = ".[()|?+*<>"; # endif #endif /* * Forward declarations for regcomp()'s friends. */ static void initchr __ARGS((unsigned char *)); static int getchr __ARGS((void)); static int peekchr __ARGS((void)); #define PeekChr() curchr /* shortcut only when last action was peekchr() */ static int curchr; static void skipchr __ARGS((void)); static void ungetchr __ARGS((void)); static char *reg __ARGS((int, int *)); static char *regbranch __ARGS((int *)); static char *regpiece __ARGS((int *)); static char *regatom __ARGS((int *)); static char *regnode __ARGS((int)); static char *regnext __ARGS((char *)); static void regc __ARGS((int)); static void unregc __ARGS((void)); static void reginsert __ARGS((int, char *)); static void regtail __ARGS((char *, char *)); static void regoptail __ARGS((char *, char *)); #ifdef JP static void regjp(); static char *strjpchr(); #endif #undef STRCSPN #ifdef STRCSPN static int strcspn __ARGS((const char *, const char *)); #endif static int cstrncmp __ARGS((char *, char *, int)); #ifdef GENERAL # define alloc(x) malloc(x) # undef free #endif /* - regcomp - compile a regular expression into internal code * * We can't allocate space until we know how big the compiled form will be, * but we can't compile it (and thus know how big it is) until we've got a * place to put the code. So we cheat: we compile it twice, once with code * generation turned off and size counting turned on, and once "for real". * This also means that we don't allocate space until we are sure that the * thing really will compile successfully, and we never have to move the * code and thus invalidate pointers into it. (Note that it has to be in * one piece because free() must be able to free it all.) * * Beware that the optimization-preparation code in here knows about some * of the structure of the compiled regexp. */ regexp * regcomp(exp) char *exp; { register regexp *r; register char *scan; register char *longest; register int len; int flags; /* extern char *malloc(); */ if (exp == NULL) { FAIL(e_null); } #ifdef EMPTY_RE /* this is done outside of regexp */ if (*exp == '\0') { if (reg_prev_re) { exp = reg_prev_re; } else { FAIL(e_noprevre); } } #endif /* First pass: determine size, legality. */ initchr((unsigned char *)exp); regnpar = 1; regsize = 0L; regcode = ®dummy; regendp = NULL; regc(MAGIC); if (reg(0, &flags) == NULL) return NULL; /* Small enough for pointer-storage convention? */ if (regsize >= 32767L) /* Probably could be 65535L. */ FAIL(e_toolong); /* Allocate space. */ r = (regexp *) alloc((unsigned) (sizeof(regexp) + regsize)); if (r == NULL) FAIL(e_outofmem); #ifdef EMPTY_RE /* this is done outside of regexp */ if (exp != reg_prev_re) { free(reg_prev_re); if ((reg_prev_re = alloc(strlen(exp) + 1))) strcpy(reg_prev_re, exp); } #endif /* Second pass: emit code. */ initchr((unsigned char *)exp); regnpar = 1; regcode = r->program; regendp = r->endp; regc(MAGIC); if (reg(0, &flags) == NULL) { free(r); return NULL; } /* Dig out information for optimizations. */ r->regstart = '\0'; /* Worst-case defaults. */ r->reganch = 0; r->regmust = NULL; r->regmlen = 0; scan = r->program + 1; /* First BRANCH. */ if (OP(regnext(scan)) == END) { /* Only one top-level choice. */ scan = OPERAND(scan); /* Starting-point info. */ if (OP(scan) == EXACTLY) r->regstart = *OPERAND(scan); else if (OP(scan) == BOL) r->reganch++; /* * If there's something expensive in the r.e., find the longest * literal string that must appear and make it the regmust. Resolve * ties in favor of later strings, since the regstart check works * with the beginning of the r.e. and avoiding duplication * strengthens checking. Not a strong reason, but sufficient in the * absence of others. */ if (flags & SPSTART) { longest = NULL; len = 0; for (; scan != NULL; scan = regnext(scan)) if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= (size_t)len) { longest = OPERAND(scan); len = strlen(OPERAND(scan)); } r->regmust = longest; r->regmlen = len; } } #ifdef DEBUG regdump(r); #endif return r; } /* - reg - regular expression, i.e. main body or parenthesized thing * * Caller must absorb opening parenthesis. * * Combining parenthesis handling with the base level of regular expression * is a trifle forced, but the need to tie the tails of the branches to what * follows makes it hard to avoid. */ static char * reg(paren, flagp) int paren; /* Parenthesized? */ int *flagp; { register char *ret; register char *br; register char *ender; register int parno = 0; int flags; *flagp = HASWIDTH; /* Tentatively. */ /* Make an MOPEN node, if parenthesized. */ if (paren) { if (regnpar >= NSUBEXP) FAIL(e_toombra); parno = regnpar; regnpar++; ret = regnode((char)(MOPEN + parno)); if (regendp) regendp[parno] = NULL; /* haven't seen the close paren yet */ } else ret = NULL; /* Pick up the branches, linking them together. */ br = regbranch(&flags); if (br == NULL) return NULL; if (ret != NULL) regtail(ret, br); /* MOPEN -> first. */ else ret = br; if (!(flags & HASWIDTH)) *flagp &= ~HASWIDTH; *flagp |= flags & SPSTART; while (peekchr() == Magic('|')) { skipchr(); br = regbranch(&flags); if (br == NULL) return NULL; regtail(ret, br); /* BRANCH -> BRANCH. */ if (!(flags & HASWIDTH)) *flagp &= ~HASWIDTH; *flagp |= flags & SPSTART; } /* Make a closing node, and hook it on the end. */ ender = regnode((char)((paren) ? MCLOSE + parno : END)); regtail(ret, ender); /* Hook the tails of the branches to the closing node. */ for (br = ret; br != NULL; br = regnext(br)) regoptail(br, ender); /* Check for proper termination. */ if (paren && getchr() != Magic(')')) { FAIL(e_toombra); } else if (!paren && peekchr() != '\0') { if (PeekChr() == Magic(')')) { FAIL(e_toomket); } else FAIL(e_trailing);/* "Can't happen". */ /* NOTREACHED */ } /* * Here we set the flag allowing back references to this set of * parentheses. */ if (paren && regendp) regendp[parno] = ender; /* have seen the close paren */ return ret; } /* - regbranch - one alternative of an | operator * * Implements the concatenation operator. */ static char * regbranch(flagp) int *flagp; { register char *ret; register char *chain; register char *latest; int flags; *flagp = WORST; /* Tentatively. */ ret = regnode(BRANCH); chain = NULL; while (peekchr() != '\0' && PeekChr() != Magic('|') && PeekChr() != Magic(')')) { latest = regpiece(&flags); if (latest == NULL) return NULL; *flagp |= flags & HASWIDTH; if (chain == NULL) /* First piece. */ *flagp |= flags & SPSTART; else regtail(chain, latest); chain = latest; } if (chain == NULL) /* Loop ran zero times. */ (void) regnode(NOTHING); return ret; } /* - regpiece - something followed by possible [*+?] * * Note that the branching code sequences used for ? and the general cases * of * and + are somewhat optimized: they use the same NOTHING node as * both the endmarker for their branch list and the body of the last branch. * It might seem that this node could be dispensed with entirely, but the * endmarker role is not redundant. */ static char * regpiece(flagp) int *flagp; { register char *ret; register int op; register char *next; int flags; ret = regatom(&flags); if (ret == NULL) return NULL; op = peekchr(); if (!ismult(op)) { *flagp = flags; return ret; } if (!(flags & HASWIDTH) && op != Magic('?')) FAIL("*+ operand could be empty"); *flagp = (op != Magic('+')) ? (WORST | SPSTART) : (WORST | HASWIDTH); if (op == Magic('*') && (flags & SIMPLE)) reginsert(STAR, ret); else if (op == Magic('*')) { /* Emit x* as (x&|), where & means "self". */ reginsert(BRANCH, ret); /* Either x */ regoptail(ret, regnode(BACK)); /* and loop */ regoptail(ret, ret); /* back */ regtail(ret, regnode(BRANCH)); /* or */ regtail(ret, regnode(NOTHING)); /* null. */ } else if (op == Magic('+') && (flags & SIMPLE)) reginsert(PLUS, ret); else if (op == Magic('+')) { /* Emit x+ as x(&|), where & means "self". */ next = regnode(BRANCH); /* Either */ regtail(ret, next); regtail(regnode(BACK), ret); /* loop back */ regtail(next, regnode(BRANCH)); /* or */ regtail(ret, regnode(NOTHING)); /* null. */ } else if (op == Magic('?')) { /* Emit x? as (x|) */ reginsert(BRANCH, ret); /* Either x */ regtail(ret, regnode(BRANCH)); /* or */ next = regnode(NOTHING);/* null. */ regtail(ret, next); regoptail(ret, next); } skipchr(); if (ismult(peekchr())) FAIL("Nested *?+"); return ret; } /* - regatom - the lowest level * * Optimization: gobbles an entire sequence of ordinary characters so that * it can turn them into a single node, which is smaller to store and * faster to run. */ static char * regatom(flagp) int *flagp; { register char *ret; int flags; *flagp = WORST; /* Tentatively. */ switch (getchr()) { case Magic('^'): ret = regnode(BOL); break; case Magic('$'): ret = regnode(EOL); break; case Magic('<'): ret = regnode(BOW); break; case Magic('>'): ret = regnode(EOW); break; case Magic('.'): ret = regnode(ANY); *flagp |= HASWIDTH | SIMPLE; break; case Magic('['):{ /* * In a character class, different parsing rules apply. * Not even \ is special anymore, nothing is. */ if (*regparse == '^') { /* Complement of range. */ ret = regnode(ANYBUT); regparse++; } else ret = regnode(ANYOF); if (*regparse == ']' || *regparse == '-') regc(*regparse++); while (*regparse != '\0' && *regparse != ']') { if (*regparse == '-') { regparse++; if (*regparse == ']' || *regparse == '\0') regc('-'); else { register int class; register int classend; #ifdef JP if (IsKanji(*(regparse - 2))) class = ((*(regparse - 3) & 0x7f) << 8 ) | (*(regparse - 2) & 0x7f); else #endif class = UCHARAT(regparse - 2) + 1; #ifdef JP if (IsKanji(*regparse)) { classend = ((*regparse & 0x7f) << 8 ) | (*(regparse + 1) & 0x7f); regparse ++; } else #endif classend = UCHARAT(regparse); #ifdef JP if (classend - class > 256) FAIL(e_invrange); #endif if (class > classend + 1) FAIL(e_invrange); #ifdef JP if (class & 0xff00) for (; class <= classend; class++) regjp(((char)(class >> 8)) | 0x80, (class & 0xff) | 0x80); else #endif for (; class <= classend; class++) regc((char)class); regparse++; } } else { if (*regparse == '\\' && regparse[1]) regparse++; #ifdef JP if (IsKanji(*regparse)) { u_char c; c = *regparse++; regjp(c, *regparse++); } else #endif regc(*regparse++); } } regc('\0'); if (*regparse != ']') FAIL(e_toomsbra); skipchr(); /* let's be friends with the lexer again */ *flagp |= HASWIDTH | SIMPLE; } break; case Magic('('): ret = reg(1, &flags); if (ret == NULL) return NULL; *flagp |= flags & (HASWIDTH | SPSTART); break; case '\0': case Magic('|'): case Magic(')'): FAIL(e_internal); /* Supposed to be caught earlier. */ /* break; Not Reached */ case Magic('?'): case Magic('+'): case Magic('*'): FAIL("?+* follows nothing"); /* break; Not Reached */ #ifdef TILDE case Magic('~'): /* previous substitute pattern */ if (reg_prev_sub) { register char *p; ret = regnode(EXACTLY); p = reg_prev_sub; while (*p) { regc(*p++); } regc('\0'); if (p - reg_prev_sub) { *flagp |= HASWIDTH; if ((p - reg_prev_sub) == 1) *flagp |= SIMPLE; } } else FAIL(e_nopresub); break; #endif #ifdef BACKREF case Magic('1'): case Magic('2'): case Magic('3'): case Magic('4'): case Magic('5'): case Magic('6'): case Magic('7'): case Magic('8'): case Magic('9'): { int refnum; ungetchr(); refnum = getchr() - Magic('0'); /* * Check if the back reference is legal. We use the parentheses * pointers to mark encountered close parentheses, but this * is only available in the second pass. Checking opens is * always possible. * Should also check that we don't refer to something that * is repeated (+*?): what instance of the repetition should * we match? TODO. */ if (refnum < regnpar && (regendp == NULL || regendp[refnum] != NULL)) ret = regnode(BACKREF + refnum); else FAIL("Illegal back reference"); } break; #endif default:{ register int len; int chr; ungetchr(); len = 0; ret = regnode(EXACTLY); while ((chr = peekchr()) != '\0' && (chr < Magic(0))) { #ifdef JP if (IsKanji(chr)) regjp(chr, regparse[1]); else #endif regc(chr); skipchr(); len++; } #ifdef DEBUG if (len == 0) FAIL("Unexpected magic character; check META."); #endif /* * If there is a following *, \+ or \? we need the character * in front of it as a single character operand */ if (len > 1 && ismult(chr)) { unregc(); /* Back off of *+? operand */ ungetchr(); /* and put it back for next time */ --len; } regc('\0'); *flagp |= HASWIDTH; if (len == 1) *flagp |= SIMPLE; } break; } return ret; } /* - regnode - emit a node */ static char * /* Location. */ regnode(op) int op; { register char *ret; register char *ptr; ret = regcode; if (ret == ®dummy) { regsize += 3; return ret; } ptr = ret; *ptr++ = op; *ptr++ = '\0'; /* Null "next" pointer. */ *ptr++ = '\0'; regcode = ptr; return ret; } /* - regc - emit (if appropriate) a byte of code */ static void regc(b) int b; { if (regcode != ®dummy) *(u_char *)regcode++ = b; else regsize++; } #ifdef JP static void regjp(b, k) int b; u_char k; { if (regcode != ®dummy) { *(u_char *)regcode++ = b; *(u_char *)regcode++ = k; } else regsize++; } #endif /* - unregc - take back (if appropriate) a byte of code */ static void unregc() { if (regcode != ®dummy) #ifdef JP { if (IsKanji(* --regcode)) regcode--; } #else regcode--; #endif else regsize--; } /* - reginsert - insert an operator in front of already-emitted operand * * Means relocating the operand. */ static void reginsert(op, opnd) int op; char *opnd; { register char *src; register char *dst; register char *place; if (regcode == ®dummy) { regsize += 3; return; } src = regcode; regcode += 3; dst = regcode; while (src > opnd) *--dst = *--src; place = opnd; /* Op node, where operand used to be. */ *place++ = op; *place++ = '\0'; *place = '\0'; } /* - regtail - set the next-pointer at the end of a node chain */ static void regtail(p, val) char *p; char *val; { register char *scan; register char *temp; register int offset; if (p == ®dummy) return; /* Find last node. */ scan = p; for (;;) { temp = regnext(scan); if (temp == NULL) break; scan = temp; } if (OP(scan) == BACK) offset = (int)(scan - val); else offset = (int)(val - scan); *(scan + 1) = (char) ((offset >> 8) & 0377); *(scan + 2) = (char) (offset & 0377); } /* - regoptail - regtail on operand of first argument; nop if operandless */ static void regoptail(p, val) char *p; char *val; { /* "Operandless" and "op != BRANCH" are synonymous in practice. */ if (p == NULL || p == ®dummy || OP(p) != BRANCH) return; regtail(OPERAND(p), val); } /* - getchr() - get the next character from the pattern. We know about * magic and such, so therefore we need a lexical analyzer. */ /* static int curchr; */ static int prevchr; static int nextchr; /* used for ungetchr() */ static void initchr(str) unsigned char *str; { regparse = str; curchr = prevchr = nextchr = -1; } static int peekchr() { if (curchr < 0) { switch (curchr = regparse[0]) { case '.': case '*': /* case '+':*/ /* case '?':*/ case '[': case '~': if (reg_magic) curchr = Magic(curchr); break; case '^': /* ^ is only magic as the very first character */ if (prevchr < 0) curchr = Magic('^'); break; case '$': /* $ is only magic as the very last character */ if (!regparse[1]) curchr = Magic('$'); break; case '\\': regparse++; if (regparse[0] == NUL) curchr = '\\'; /* trailing '\' */ else if (strchr(META, regparse[0])) { /* * META contains everything that may be magic sometimes, except * ^ and $ ("\^" and "\$" are never magic). * We now fetch the next character and toggle its magicness. * Therefore, \ is so meta-magic that it is not in META. */ curchr = -1; peekchr(); curchr ^= Magic(0); } else { /* * Next character can never be (made) magic? * Then backslashing it won't do anything. */ curchr = regparse[0]; } break; } } return curchr; } static void skipchr() { #ifdef JP if (IsKanji(*regparse)) regparse += 2; else #endif regparse++; prevchr = curchr; curchr = nextchr; /* use previously unget char, or -1 */ nextchr = -1; } static int getchr() { int chr; chr = peekchr(); skipchr(); return chr; } /* * put character back. Works only once! */ static void ungetchr() { nextchr = curchr; curchr = prevchr; /* * Backup regparse as well; not because we will use what it points at, * but because skipchr() will bump it again. */ #ifdef JP if (IsKanji(curchr)) { nextchr = -1; regparse-= 2; } else #endif regparse--; } /* * regexec and friends */ /* * Global work variables for regexec(). */ static char *reginput; /* String-input pointer. */ static char *regbol; /* Beginning of input, for ^ check. */ static char **regstartp; /* Pointer to startp array. */ /* static char **regendp; */ /* Ditto for endp. */ /* * Forwards. */ static int regtry __ARGS((regexp *, char *)); static int regmatch __ARGS((char *)); static int regrepeat __ARGS((char *)); #ifdef DEBUG int regnarrate = 1; /* void regdump __ARGS((regexp *)); */ static char *regprop __ARGS((char *)); #endif /* - regexec - match a regexp against a string */ int regexec(prog, string, at_bol) register regexp *prog; register char *string; int at_bol; { register char *s; /* Be paranoid... */ if (prog == NULL || string == NULL) { emsg(e_null); return 0; } /* Check validity of program. */ if (UCHARAT(prog->program) != MAGIC) { emsg(e_re_corr); return 0; } /* If there is a "must appear" string, look for it. */ if (prog->regmust != NULL) { s = string; while ((s = cstrchr(s, prog->regmust[0])) != NULL) { if (cstrncmp(s, prog->regmust, prog->regmlen) == 0) break; /* Found it. */ #ifdef JP if (IsKanji(*s)) s += 2; else #endif s++; } if (s == NULL) /* Not present. */ return 0; } /* Mark beginning of line for ^ . */ if (at_bol) regbol = string; /* is possible to match bol */ else regbol = NULL; /* we aren't there, so don't match it */ /* Simplest case: anchored match need be tried only once. */ if (prog->reganch) return regtry(prog, string); /* Messy cases: unanchored match. */ s = string; if (prog->regstart != '\0') /* We know what char it must start with. */ while ((s = cstrchr(s, prog->regstart)) != NULL) { if (regtry(prog, s)) return 1; #ifdef JP if (IsKanji(*s)) s += 2; else #endif s++; } else /* We don't -- general case. */ do { if (regtry(prog, s)) return 1; if (*s == '\0') break; #ifdef JP if (IsKanji(*s)) s += 2; else #endif s ++; } while (1); /* Failure. */ return 0; } /* - regtry - try match at specific point */ static int /* 0 failure, 1 success */ regtry(prog, string) regexp *prog; char *string; { register int i; register char **sp; register char **ep; reginput = string; regstartp = prog->startp; regendp = prog->endp; sp = prog->startp; ep = prog->endp; for (i = NSUBEXP; i > 0; i--) { *sp++ = NULL; *ep++ = NULL; } if (regmatch(prog->program + 1)) { prog->startp[0] = string; prog->endp[0] = reginput; return 1; } else return 0; } /* - regmatch - main matching routine * * Conceptually the strategy is simple: check to see whether the current * node matches, call self recursively to see whether the rest matches, * and then act accordingly. In practice we make some effort to avoid * recursion, in particular by going through "ordinary" nodes (that don't * need to know whether the rest of the match failed) by a loop instead of * by recursion. */ static int /* 0 failure, 1 success */ regmatch(prog) char *prog; { register char *scan; /* Current node. */ char *next; /* Next node. */ scan = prog; #ifdef DEBUG if (scan != NULL && regnarrate) fprintf(stderr, "%s(\n", regprop(scan)); #endif while (scan != NULL) { #ifdef DEBUG if (regnarrate) { fprintf(stderr, "%s...\n", regprop(scan)); } #endif next = regnext(scan); switch (OP(scan)) { case BOL: if (reginput != regbol) return 0; break; case EOL: if (*reginput != '\0') return 0; break; case BOW: /* \; reginput points after d */ if (reginput == regbol) return 0; #ifdef JP if (IsKanji(reginput[-1])) { int sclass; if (! (sclass = jpcls(reginput[-2], reginput[-1])) || sclass == JPC_KIGOU) return 0; if (IsKanji(reginput[0]) && sclass == jpcls(reginput[0], reginput[1])) return 0; break; } #endif if (!isidchar(reginput[-1])) return 0; if (reginput[0] && isidchar(reginput[0])) return 0; break; case ANY: if (*reginput == '\0') return 0; #ifdef JP if (IsKanji(*reginput)) reginput += 2; else #endif reginput++; break; case EXACTLY:{ register int len; register char *opnd; opnd = OPERAND(scan); /* Inline the first character, for speed. */ if (mkup(*opnd) != mkup(*reginput)) return 0; len = strlen(opnd); if (len > 1 && cstrncmp(opnd, reginput, len) != 0) return 0; reginput += len; } break; case ANYOF: #ifdef JP if (*reginput == '\0' || strjpchr(OPERAND(scan), *reginput, *(reginput + 1)) == NULL) #else if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL) #endif return 0; #ifdef JP if (IsKanji(*reginput)) reginput += 2; else #endif reginput++; break; case ANYBUT: #ifdef JP if (*reginput == '\0' || strjpchr(OPERAND(scan), *reginput, *(reginput + 1)) != NULL) #else if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL) #endif return 0; #ifdef JP if (IsKanji(*reginput)) reginput += 2; else #endif reginput++; break; case NOTHING: break; case BACK: break; case MOPEN + 1: case MOPEN + 2: case MOPEN + 3: case MOPEN + 4: case MOPEN + 5: case MOPEN + 6: case MOPEN + 7: case MOPEN + 8: case MOPEN + 9:{ register int no; register char *save; no = OP(scan) - MOPEN; save = regstartp[no]; regstartp[no] = reginput; /* Tentatively */ #ifdef DEBUG printf("MOPEN %d pre @'%s' ('%s' )'%s'\n", no, save, regstartp[no]? regstartp[no] : "NULL", regendp[no]? regendp[no] : "NULL"); #endif if (regmatch(next)) { #ifdef DEBUG printf("MOPEN %d post @'%s' ('%s' )'%s'\n", no, save, regstartp[no]? regstartp[no] : "NULL", regendp[no]? regendp[no] : "NULL"); #endif return 1; } regstartp[no] = save; /* We were wrong... */ return 0; } /* break; Not Reached */ case MCLOSE + 1: case MCLOSE + 2: case MCLOSE + 3: case MCLOSE + 4: case MCLOSE + 5: case MCLOSE + 6: case MCLOSE + 7: case MCLOSE + 8: case MCLOSE + 9:{ register int no; register char *save; no = OP(scan) - MCLOSE; save = regendp[no]; regendp[no] = reginput; /* Tentatively */ #ifdef DEBUG printf("MCLOSE %d pre @'%s' ('%s' )'%s'\n", no, save, regstartp[no]? regstartp[no] : "NULL", regendp[no]? regendp[no] : "NULL"); #endif if (regmatch(next)) { #ifdef DEBUG printf("MCLOSE %d post @'%s' ('%s' )'%s'\n", no, save, regstartp[no]? regstartp[no] : "NULL", regendp[no]? regendp[no] : "NULL"); #endif return 1; } regendp[no] = save; /* We were wrong... */ return 0; } /* break; Not Reached */ #ifdef BACKREF case BACKREF + 1: case BACKREF + 2: case BACKREF + 3: case BACKREF + 4: case BACKREF + 5: case BACKREF + 6: case BACKREF + 7: case BACKREF + 8: case BACKREF + 9:{ register int no; int len; no = OP(scan) - BACKREF; if (regendp[no] != NULL) { len = (int)(regendp[no] - regstartp[no]); if (cstrncmp(regstartp[no], reginput, len) != 0) return 0; reginput += len; } else { /*emsg("backref to 0-repeat");*/ /*return 0;*/ } } break; #endif case BRANCH:{ register char *save; if (OP(next) != BRANCH) /* No choice. */ next = OPERAND(scan); /* Avoid recursion. */ else { do { save = reginput; if (regmatch(OPERAND(scan))) return 1; reginput = save; scan = regnext(scan); } while (scan != NULL && OP(scan) == BRANCH); return 0; /* NOTREACHED */ } } break; case STAR: case PLUS:{ register char nextch; register int no; register char *save; register int min; /* * Lookahead to avoid useless match attempts when we know * what character comes next. */ nextch = '\0'; if (OP(next) == EXACTLY) nextch = mkup(*OPERAND(next)); min = (OP(scan) == STAR) ? 0 : 1; save = reginput; no = regrepeat(OPERAND(scan)); while (no >= min) { /* If it could work, try it. */ if (nextch == '\0' || mkup(*reginput) == nextch) if (regmatch(next)) return 1; /* Couldn't or didn't -- back up. */ no--; reginput = save + no; #ifdef JP if (IsKanji(*reginput)) { no --; reginput --; } #endif } return 0; } /* break; Not Reached */ case END: return 1; /* Success! */ /* break; Not Reached */ default: emsg(e_re_corr); return 0; /* break; Not Reached */ } scan = next; } /* * We get here only if there's trouble -- normally "case END" is the * terminating point. */ emsg(e_re_corr); return 0; } /* - regrepeat - repeatedly match something simple, report how many */ static int regrepeat(p) char *p; { register int count = 0; register char *scan; register char *opnd; scan = reginput; opnd = OPERAND(p); switch (OP(p)) { case ANY: count = strlen(scan); scan += count; break; case EXACTLY: #ifdef JP if (IsKanji(*opnd)) while (*opnd == *scan && *(opnd + 1) == *(scan + 1)) { count+=2; scan +=2; } else #endif while (mkup(*opnd) == mkup(*scan)) { count++; scan++; } break; case ANYOF: #ifdef JP while (*scan != '\0' && strjpchr(opnd, *scan, *(scan + 1)) != NULL) if (IsKanji(*scan)) { count += 2; scan += 2; } else { count ++; scan ++; } #else while (*scan != '\0' && strchr(opnd, *scan) != NULL) { count++; scan++; } #endif break; case ANYBUT: #ifdef JP while (*scan != '\0' && strjpchr(opnd, *scan, *(scan + 1)) == NULL) if (IsKanji(*scan)) { count += 2; scan += 2; } else { count ++; scan ++; } #else while (*scan != '\0' && strchr(opnd, *scan) == NULL) { count++; scan++; } #endif break; default: /* Oh dear. Called inappropriately. */ emsg(e_re_corr); count = 0; /* Best compromise. */ break; } reginput = scan; return count; } /* - regnext - dig the "next" pointer out of a node */ static char * regnext(p) register char *p; { register int offset; if (p == ®dummy) return NULL; offset = NEXT(p); if (offset == 0) return NULL; if (OP(p) == BACK) return p - offset; else return p + offset; } #ifdef DEBUG /* - regdump - dump a regexp onto stdout in vaguely comprehensible form */ void regdump(r) regexp *r; { register char *s; register char op = EXACTLY; /* Arbitrary non-END op. */ register char *next; /*extern char *strchr();*/ s = r->program + 1; while (op != END) { /* While that wasn't END last time... */ op = OP(s); printf("%2d%s", s - r->program, regprop(s)); /* Where, what. */ next = regnext(s); if (next == NULL) /* Next ptr. */ printf("(0)"); else printf("(%d)", (s - r->program) + (next - s)); s += 3; if (op == ANYOF || op == ANYBUT || op == EXACTLY) { /* Literal string, where present. */ while (*s != '\0') { putchar(*s); s++; } s++; } putchar('\n'); } /* Header fields of interest. */ if (r->regstart != '\0') printf("start `%c' ", r->regstart); if (r->reganch) printf("anchored "); if (r->regmust != NULL) printf("must have \"%s\"", r->regmust); printf("\n"); } /* - regprop - printable representation of opcode */ static char * regprop(op) char *op; { register char *p; static char buf[50]; (void) strcpy(buf, ":"); switch (OP(op)) { case BOL: p = "BOL"; break; case EOL: p = "EOL"; break; case ANY: p = "ANY"; break; case ANYOF: p = "ANYOF"; break; case ANYBUT: p = "ANYBUT"; break; case BRANCH: p = "BRANCH"; break; case EXACTLY: p = "EXACTLY"; break; case NOTHING: p = "NOTHING"; break; case BACK: p = "BACK"; break; case END: p = "END"; break; case MOPEN + 1: case MOPEN + 2: case MOPEN + 3: case MOPEN + 4: case MOPEN + 5: case MOPEN + 6: case MOPEN + 7: case MOPEN + 8: case MOPEN + 9: sprintf(buf + strlen(buf), "MOPEN%d", OP(op) - MOPEN); p = NULL; break; case MCLOSE + 1: case MCLOSE + 2: case MCLOSE + 3: case MCLOSE + 4: case MCLOSE + 5: case MCLOSE + 6: case MCLOSE + 7: case MCLOSE + 8: case MCLOSE + 9: sprintf(buf + strlen(buf), "MCLOSE%d", OP(op) - MCLOSE); p = NULL; break; case BACKREF + 1: case BACKREF + 2: case BACKREF + 3: case BACKREF + 4: case BACKREF + 5: case BACKREF + 6: case BACKREF + 7: case BACKREF + 8: case BACKREF + 9: sprintf(buf + strlen(buf), "BACKREF%d", OP(op) - BACKREF); p = NULL; break; case STAR: p = "STAR"; break; case PLUS: p = "PLUS"; break; default: sprintf(buf + strlen(buf), "corrupt %d", OP(op)); p = NULL; break; } if (p != NULL) (void) strcat(buf, p); return buf; } #endif /* * The following is provided for those people who do not have strcspn() in * their C libraries. They should get off their butts and do something * about it; at least one public-domain implementation of those (highly * useful) string routines has been published on Usenet. */ #ifdef STRCSPN /* * strcspn - find length of initial segment of s1 consisting entirely * of characters not from s2 */ static int strcspn(s1, s2) const char *s1; const char *s2; { register char *scan1; register char *scan2; register int count; count = 0; for (scan1 = s1; *scan1 != '\0'; scan1++) { for (scan2 = s2; *scan2 != '\0';) /* ++ moved down. */ if (*scan1 == *scan2++) return count; count++; } return count; } #endif /* * Compare two strings, ignore case if reg_ic set. * Return 0 if strings match, non-zero otherwise. */ static int cstrncmp(s1, s2, n) char *s1, *s2; int n; { if (!reg_ic) return strncmp(s1, s2, (size_t)n); #ifndef UNIX return strnicmp(s1, s2, (size_t)n); #else # ifdef STRNCASECMP return strncasecmp(s1, s2, (size_t)n); # else while (n && *s1 && *s2) { if (mkup(*s1) != mkup(*s2)) return 1; s1++; s2++; n--; } if (n) return 1; return 0; # endif /* STRNCASECMP */ #endif /* UNIX */ } char * cstrchr(s, c) char *s; int c; { char *p; c = mkup(c); for (p = s; *p; p++) { if (mkup(*p) == c) return p; #ifdef JP if (IsKanji(*p)) p++; #endif } return NULL; } #ifdef JP static char * strjpchr(s, c, k) char *s; char c, k; { while(*s) if (IsKanji(*s)) { if (*s == c && *(s + 1) == k) return s; s += 2; } else { if (*s == c) return s; s ++; } return NULL; } #endif