Annotation of src/usr.bin/vim/regexp.c, Revision 1.1
1.1 ! downsj 1: /* $OpenBSD$ */
! 2: /* vi:set ts=4 sw=4:
! 3: * NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE
! 4: *
! 5: * This is NOT the original regular expression code as written by
! 6: * Henry Spencer. This code has been modified specifically for use
! 7: * with the VIM editor, and should not be used apart from compiling
! 8: * VIM. If you want a good regular expression library, get the
! 9: * original code. The copyright notice that follows is from the
! 10: * original.
! 11: *
! 12: * NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE NOTICE
! 13: *
! 14: *
! 15: * vim_regcomp and vim_regexec -- vim_regsub and regerror are elsewhere
! 16: *
! 17: * Copyright (c) 1986 by University of Toronto.
! 18: * Written by Henry Spencer. Not derived from licensed software.
! 19: *
! 20: * Permission is granted to anyone to use this software for any
! 21: * purpose on any computer system, and to redistribute it freely,
! 22: * subject to the following restrictions:
! 23: *
! 24: * 1. The author is not responsible for the consequences of use of
! 25: * this software, no matter how awful, even if they arise
! 26: * from defects in it.
! 27: *
! 28: * 2. The origin of this software must not be misrepresented, either
! 29: * by explicit claim or by omission.
! 30: *
! 31: * 3. Altered versions must be plainly marked as such, and must not
! 32: * be misrepresented as being the original software.
! 33: *
! 34: * Beware that some of this code is subtly aware of the way operator
! 35: * precedence is structured in regular expressions. Serious changes in
! 36: * regular-expression syntax might require a total rethink.
! 37: *
! 38: * $Log: regexp.c,v $
! 39: * Revision 1.2 88/04/28 08:09:45 tony
! 40: * First modification of the regexp library. Added an external variable
! 41: * 'reg_ic' which can be set to indicate that case should be ignored.
! 42: * Added a new parameter to vim_regexec() to indicate that the given string
! 43: * comes from the beginning of a line and is thus eligible to match
! 44: * 'beginning-of-line'.
! 45: *
! 46: * Revisions by Olaf 'Rhialto' Seibert, rhialto@mbfys.kun.nl:
! 47: * Changes for vi: (the semantics of several things were rather different)
! 48: * - Added lexical analyzer, because in vi magicness of characters
! 49: * is rather difficult, and may change over time.
! 50: * - Added support for \< \> \1-\9 and ~
! 51: * - Left some magic stuff in, but only backslashed: \| \+
! 52: * - * and \+ still work after \) even though they shouldn't.
! 53: */
! 54: #include "vim.h"
! 55: #include "globals.h"
! 56: #include "proto.h"
! 57: #undef DEBUG
! 58:
! 59: #include <stdio.h>
! 60: #include "regexp.h"
! 61: #include "option.h"
! 62:
! 63: /*
! 64: * The "internal use only" fields in regexp.h are present to pass info from
! 65: * compile to execute that permits the execute phase to run lots faster on
! 66: * simple cases. They are:
! 67: *
! 68: * regstart char that must begin a match; '\0' if none obvious
! 69: * reganch is the match anchored (at beginning-of-line only)?
! 70: * regmust string (pointer into program) that match must include, or NULL
! 71: * regmlen length of regmust string
! 72: *
! 73: * Regstart and reganch permit very fast decisions on suitable starting points
! 74: * for a match, cutting down the work a lot. Regmust permits fast rejection
! 75: * of lines that cannot possibly match. The regmust tests are costly enough
! 76: * that vim_regcomp() supplies a regmust only if the r.e. contains something
! 77: * potentially expensive (at present, the only such thing detected is * or +
! 78: * at the start of the r.e., which can involve a lot of backup). Regmlen is
! 79: * supplied because the test in vim_regexec() needs it and vim_regcomp() is
! 80: * computing it anyway.
! 81: */
! 82:
! 83: /*
! 84: * Structure for regexp "program". This is essentially a linear encoding
! 85: * of a nondeterministic finite-state machine (aka syntax charts or
! 86: * "railroad normal form" in parsing technology). Each node is an opcode
! 87: * plus a "next" pointer, possibly plus an operand. "Next" pointers of
! 88: * all nodes except BRANCH implement concatenation; a "next" pointer with
! 89: * a BRANCH on both ends of it is connecting two alternatives. (Here we
! 90: * have one of the subtle syntax dependencies: an individual BRANCH (as
! 91: * opposed to a collection of them) is never concatenated with anything
! 92: * because of operator precedence.) The operand of some types of node is
! 93: * a literal string; for others, it is a node leading into a sub-FSM. In
! 94: * particular, the operand of a BRANCH node is the first node of the branch.
! 95: * (NB this is *not* a tree structure: the tail of the branch connects
! 96: * to the thing following the set of BRANCHes.) The opcodes are:
! 97: */
! 98:
! 99: /* definition number opnd? meaning */
! 100: #define END 0 /* no End of program. */
! 101: #define BOL 1 /* no Match "" at beginning of line. */
! 102: #define EOL 2 /* no Match "" at end of line. */
! 103: #define ANY 3 /* no Match any one character. */
! 104: #define ANYOF 4 /* str Match any character in this string. */
! 105: #define ANYBUT 5 /* str Match any character not in this
! 106: * string. */
! 107: #define BRANCH 6 /* node Match this alternative, or the
! 108: * next... */
! 109: #define BACK 7 /* no Match "", "next" ptr points backward. */
! 110: #define EXACTLY 8 /* str Match this string. */
! 111: #define NOTHING 9 /* no Match empty string. */
! 112: #define STAR 10 /* node Match this (simple) thing 0 or more
! 113: * times. */
! 114: #define PLUS 11 /* node Match this (simple) thing 1 or more
! 115: * times. */
! 116: #define BOW 12 /* no Match "" after [^a-zA-Z0-9_] */
! 117: #define EOW 13 /* no Match "" at [^a-zA-Z0-9_] */
! 118: #define IDENT 14 /* no Match identifier char */
! 119: #define WORD 15 /* no Match keyword char */
! 120: #define FNAME 16 /* no Match file name char */
! 121: #define PRINT 17 /* no Match printable char */
! 122: #define SIDENT 18 /* no Match identifier char but no digit */
! 123: #define SWORD 19 /* no Match word char but no digit */
! 124: #define SFNAME 20 /* no Match file name char but no digit */
! 125: #define SPRINT 21 /* no Match printable char but no digit */
! 126: #define MOPEN 30 /* no Mark this point in input as start of
! 127: * #n. */
! 128: /* MOPEN+1 is number 1, etc. */
! 129: #define MCLOSE 40 /* no Analogous to MOPEN. */
! 130: #define BACKREF 50 /* node Match same string again \1-\9 */
! 131:
! 132: #define Magic(x) ((x)|('\\'<<8))
! 133:
! 134: /*
! 135: * Opcode notes:
! 136: *
! 137: * BRANCH The set of branches constituting a single choice are hooked
! 138: * together with their "next" pointers, since precedence prevents
! 139: * anything being concatenated to any individual branch. The
! 140: * "next" pointer of the last BRANCH in a choice points to the
! 141: * thing following the whole choice. This is also where the
! 142: * final "next" pointer of each individual branch points; each
! 143: * branch starts with the operand node of a BRANCH node.
! 144: *
! 145: * BACK Normal "next" pointers all implicitly point forward; BACK
! 146: * exists to make loop structures possible.
! 147: *
! 148: * STAR,PLUS '=', and complex '*' and '+', are implemented as circular
! 149: * BRANCH structures using BACK. Simple cases (one character
! 150: * per match) are implemented with STAR and PLUS for speed
! 151: * and to minimize recursive plunges.
! 152: * Note: We would like to use "\?" instead of "\=", but a "\?"
! 153: * can be part of a pattern to escape the special meaning of '?'
! 154: * at the end of the pattern in "?pattern?e".
! 155: *
! 156: * MOPEN,MCLOSE ...are numbered at compile time.
! 157: */
! 158:
! 159: /*
! 160: * A node is one char of opcode followed by two chars of "next" pointer.
! 161: * "Next" pointers are stored as two 8-bit pieces, high order first. The
! 162: * value is a positive offset from the opcode of the node containing it.
! 163: * An operand, if any, simply follows the node. (Note that much of the
! 164: * code generation knows about this implicit relationship.)
! 165: *
! 166: * Using two bytes for the "next" pointer is vast overkill for most things,
! 167: * but allows patterns to get big without disasters.
! 168: */
! 169: #define OP(p) (*(p))
! 170: #define NEXT(p) (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
! 171: #define OPERAND(p) ((p) + 3)
! 172:
! 173: /*
! 174: * Utility definitions.
! 175: */
! 176: #ifndef CHARBITS
! 177: #define UCHARAT(p) ((int)*(unsigned char *)(p))
! 178: #else
! 179: #define UCHARAT(p) ((int)*(p)&CHARBITS)
! 180: #endif
! 181:
! 182: #define EMSG_RETURN(m) { emsg(m); rc_did_emsg = TRUE; return NULL; }
! 183:
! 184: static int ismult __ARGS((int));
! 185: static char_u *cstrchr __ARGS((char_u *, int));
! 186:
! 187: static int
! 188: ismult(c)
! 189: int c;
! 190: {
! 191: return (c == Magic('*') || c == Magic('+') || c == Magic('='));
! 192: }
! 193:
! 194: /*
! 195: * Flags to be passed up and down.
! 196: */
! 197: #define HASWIDTH 01 /* Known never to match null string. */
! 198: #define SIMPLE 02 /* Simple enough to be STAR/PLUS operand. */
! 199: #define SPSTART 04 /* Starts with * or +. */
! 200: #define WORST 0 /* Worst case. */
! 201:
! 202: /*
! 203: * The following allows empty REs, meaning "the same as the previous RE".
! 204: * per the ed(1) manual.
! 205: */
! 206: /* #define EMPTY_RE */ /* this is done outside of regexp */
! 207: #ifdef EMPTY_RE
! 208: char_u *reg_prev_re;
! 209: #endif
! 210:
! 211: #define TILDE
! 212: #ifdef TILDE
! 213: char_u *reg_prev_sub;
! 214: #endif
! 215:
! 216: /*
! 217: * Global work variables for vim_regcomp().
! 218: */
! 219:
! 220: static char_u *regparse; /* Input-scan pointer. */
! 221: static int regnpar; /* () count. */
! 222: static char_u regdummy;
! 223: static char_u *regcode; /* Code-emit pointer; ®dummy = don't. */
! 224: static long regsize; /* Code size. */
! 225: static char_u **regendp; /* Ditto for endp. */
! 226:
! 227: /*
! 228: * META contains all characters that may be magic, except '^' and '$'.
! 229: * This depends on the configuration options TILDE, BACKREF.
! 230: * (could be done simpler for compilers that know string concatenation)
! 231: */
! 232:
! 233: #ifdef TILDE
! 234: # ifdef BACKREF
! 235: static char_u META[] = ".[()|=+*<>iIkKfFpP~123456789";
! 236: # else
! 237: static char_u META[] = ".[()|=+*<>iIkKfFpP~";
! 238: # endif
! 239: #else
! 240: # ifdef BACKREF
! 241: static char_u META[] = ".[()|=+*<>iIkKfFpP123456789";
! 242: # else
! 243: static char_u META[] = ".[()|=+*<>iIkKfFpP";
! 244: # endif
! 245: #endif
! 246:
! 247: /*
! 248: * REGEXP_ABBR contains all characters which act as abbreviations after '\'.
! 249: * These are:
! 250: * \r - New line (CR).
! 251: * \t - Tab (TAB).
! 252: * \e - Escape (ESC).
! 253: * \b - Backspace (Ctrl('H')).
! 254: */
! 255: static char_u REGEXP_ABBR[] = "rteb";
! 256:
! 257: /*
! 258: * Forward declarations for vim_regcomp()'s friends.
! 259: */
! 260: static void initchr __ARGS((char_u *));
! 261: static int getchr __ARGS((void));
! 262: static int peekchr __ARGS((void));
! 263: #define PeekChr() curchr /* shortcut only when last action was peekchr() */
! 264: static int curchr;
! 265: static void skipchr __ARGS((void));
! 266: static void ungetchr __ARGS((void));
! 267: static char_u *reg __ARGS((int, int *));
! 268: static char_u *regbranch __ARGS((int *));
! 269: static char_u *regpiece __ARGS((int *));
! 270: static char_u *regatom __ARGS((int *));
! 271: static char_u *regnode __ARGS((int));
! 272: static char_u *regnext __ARGS((char_u *));
! 273: static void regc __ARGS((int));
! 274: static void unregc __ARGS((void));
! 275: static void reginsert __ARGS((int, char_u *));
! 276: static void regtail __ARGS((char_u *, char_u *));
! 277: static void regoptail __ARGS((char_u *, char_u *));
! 278:
! 279: #ifndef HAVE_STRCSPN
! 280: static size_t strcspn __ARGS((const char_u *, const char_u *));
! 281: #endif
! 282:
! 283: /*
! 284: * skip past regular expression
! 285: * stop at end of 'p' of where 'dirc' is found ('/', '?', etc)
! 286: * take care of characters with a backslash in front of it
! 287: * skip strings inside [ and ].
! 288: */
! 289: char_u *
! 290: skip_regexp(p, dirc)
! 291: char_u *p;
! 292: int dirc;
! 293: {
! 294: int in_range = FALSE;
! 295:
! 296: for (; p[0] != NUL; ++p)
! 297: {
! 298: if (p[0] == dirc && !in_range) /* found end of regexp */
! 299: break;
! 300: if ((p[0] == '[' && p_magic) || (p[0] == '\\' && p[1] == '[' && !p_magic))
! 301: {
! 302: in_range = TRUE;
! 303: if (p[0] == '\\')
! 304: ++p;
! 305: /* "[^]" and "[]" are not the end of a range */
! 306: if (p[1] == '^')
! 307: ++p;
! 308: if (p[1] == ']')
! 309: ++p;
! 310: }
! 311: else if (p[0] == '\\' && p[1] != NUL)
! 312: ++p; /* skip next character */
! 313: else if (p[0] == ']')
! 314: in_range = FALSE;
! 315: }
! 316: return p;
! 317: }
! 318:
! 319: /*
! 320: - vim_regcomp - compile a regular expression into internal code
! 321: *
! 322: * We can't allocate space until we know how big the compiled form will be,
! 323: * but we can't compile it (and thus know how big it is) until we've got a
! 324: * place to put the code. So we cheat: we compile it twice, once with code
! 325: * generation turned off and size counting turned on, and once "for real".
! 326: * This also means that we don't allocate space until we are sure that the
! 327: * thing really will compile successfully, and we never have to move the
! 328: * code and thus invalidate pointers into it. (Note that it has to be in
! 329: * one piece because vim_free() must be able to free it all.)
! 330: *
! 331: * Beware that the optimization-preparation code in here knows about some
! 332: * of the structure of the compiled regexp.
! 333: */
! 334: regexp *
! 335: vim_regcomp(exp)
! 336: char_u *exp;
! 337: {
! 338: register regexp *r;
! 339: register char_u *scan;
! 340: register char_u *longest;
! 341: register int len;
! 342: int flags;
! 343: /* extern char *malloc();*/
! 344:
! 345: if (exp == NULL)
! 346: EMSG_RETURN(e_null);
! 347:
! 348: #ifdef EMPTY_RE /* this is done outside of regexp */
! 349: if (*exp == '\0')
! 350: {
! 351: if (reg_prev_re)
! 352: exp = reg_prev_re;
! 353: else
! 354: EMSG_RETURN(e_noprevre);
! 355: }
! 356: #endif
! 357:
! 358: /* First pass: determine size, legality. */
! 359: initchr((char_u *)exp);
! 360: regnpar = 1;
! 361: regsize = 0L;
! 362: regcode = ®dummy;
! 363: regendp = NULL;
! 364: regc(MAGIC);
! 365: if (reg(0, &flags) == NULL)
! 366: return NULL;
! 367:
! 368: /* Small enough for pointer-storage convention? */
! 369: if (regsize >= 32767L) /* Probably could be 65535L. */
! 370: EMSG_RETURN(e_toolong);
! 371:
! 372: /* Allocate space. */
! 373: /* r = (regexp *) malloc((unsigned) (sizeof(regexp) + regsize));*/
! 374: r = (regexp *) alloc((unsigned) (sizeof(regexp) + regsize));
! 375: if (r == NULL)
! 376: return NULL;
! 377:
! 378: #ifdef EMPTY_RE /* this is done outside of regexp */
! 379: if (exp != reg_prev_re) {
! 380: vim_free(reg_prev_re);
! 381: if (reg_prev_re = alloc(STRLEN(exp) + 1))
! 382: STRCPY(reg_prev_re, exp);
! 383: }
! 384: #endif
! 385:
! 386: /* Second pass: emit code. */
! 387: initchr((char_u *)exp);
! 388: regnpar = 1;
! 389: regcode = r->program;
! 390: regendp = r->endp;
! 391: regc(MAGIC);
! 392: if (reg(0, &flags) == NULL) {
! 393: vim_free(r);
! 394: return NULL;
! 395: }
! 396:
! 397: /* Dig out information for optimizations. */
! 398: r->regstart = '\0'; /* Worst-case defaults. */
! 399: r->reganch = 0;
! 400: r->regmust = NULL;
! 401: r->regmlen = 0;
! 402: scan = r->program + 1; /* First BRANCH. */
! 403: if (OP(regnext(scan)) == END) { /* Only one top-level choice. */
! 404: scan = OPERAND(scan);
! 405:
! 406: /* Starting-point info. */
! 407: if (OP(scan) == EXACTLY)
! 408: r->regstart = *OPERAND(scan);
! 409: else if (OP(scan) == BOL)
! 410: r->reganch++;
! 411:
! 412: /*
! 413: * If there's something expensive in the r.e., find the longest
! 414: * literal string that must appear and make it the regmust. Resolve
! 415: * ties in favor of later strings, since the regstart check works
! 416: * with the beginning of the r.e. and avoiding duplication
! 417: * strengthens checking. Not a strong reason, but sufficient in the
! 418: * absence of others.
! 419: */
! 420: /*
! 421: * When the r.e. starts with BOW, it is faster to look for a regmust
! 422: * first. Used a lot for "#" and "*" commands. (Added by mool).
! 423: */
! 424: if (flags & SPSTART || OP(scan) == BOW) {
! 425: longest = NULL;
! 426: len = 0;
! 427: for (; scan != NULL; scan = regnext(scan))
! 428: if (OP(scan) == EXACTLY && STRLEN(OPERAND(scan)) >= (size_t)len) {
! 429: longest = OPERAND(scan);
! 430: len = STRLEN(OPERAND(scan));
! 431: }
! 432: r->regmust = longest;
! 433: r->regmlen = len;
! 434: }
! 435: }
! 436: #ifdef DEBUG
! 437: regdump(r);
! 438: #endif
! 439: return r;
! 440: }
! 441:
! 442: /*
! 443: - reg - regular expression, i.e. main body or parenthesized thing
! 444: *
! 445: * Caller must absorb opening parenthesis.
! 446: *
! 447: * Combining parenthesis handling with the base level of regular expression
! 448: * is a trifle forced, but the need to tie the tails of the branches to what
! 449: * follows makes it hard to avoid.
! 450: */
! 451: static char_u *
! 452: reg(paren, flagp)
! 453: int paren; /* Parenthesized? */
! 454: int *flagp;
! 455: {
! 456: register char_u *ret;
! 457: register char_u *br;
! 458: register char_u *ender;
! 459: register int parno = 0;
! 460: int flags;
! 461:
! 462: *flagp = HASWIDTH; /* Tentatively. */
! 463:
! 464: /* Make an MOPEN node, if parenthesized. */
! 465: if (paren) {
! 466: if (regnpar >= NSUBEXP)
! 467: EMSG_RETURN(e_toombra);
! 468: parno = regnpar;
! 469: regnpar++;
! 470: ret = regnode(MOPEN + parno);
! 471: if (regendp)
! 472: regendp[parno] = NULL; /* haven't seen the close paren yet */
! 473: } else
! 474: ret = NULL;
! 475:
! 476: /* Pick up the branches, linking them together. */
! 477: br = regbranch(&flags);
! 478: if (br == NULL)
! 479: return NULL;
! 480: if (ret != NULL)
! 481: regtail(ret, br); /* MOPEN -> first. */
! 482: else
! 483: ret = br;
! 484: if (!(flags & HASWIDTH))
! 485: *flagp &= ~HASWIDTH;
! 486: *flagp |= flags & SPSTART;
! 487: while (peekchr() == Magic('|')) {
! 488: skipchr();
! 489: br = regbranch(&flags);
! 490: if (br == NULL)
! 491: return NULL;
! 492: regtail(ret, br); /* BRANCH -> BRANCH. */
! 493: if (!(flags & HASWIDTH))
! 494: *flagp &= ~HASWIDTH;
! 495: *flagp |= flags & SPSTART;
! 496: }
! 497:
! 498: /* Make a closing node, and hook it on the end. */
! 499: ender = regnode((paren) ? MCLOSE + parno : END);
! 500: regtail(ret, ender);
! 501:
! 502: /* Hook the tails of the branches to the closing node. */
! 503: for (br = ret; br != NULL; br = regnext(br))
! 504: regoptail(br, ender);
! 505:
! 506: /* Check for proper termination. */
! 507: if (paren && getchr() != Magic(')'))
! 508: EMSG_RETURN(e_toombra)
! 509: else if (!paren && peekchr() != '\0')
! 510: {
! 511: if (PeekChr() == Magic(')'))
! 512: EMSG_RETURN(e_toomket)
! 513: else
! 514: EMSG_RETURN(e_trailing) /* "Can't happen". */
! 515: /* NOTREACHED */
! 516: }
! 517: /*
! 518: * Here we set the flag allowing back references to this set of
! 519: * parentheses.
! 520: */
! 521: if (paren && regendp)
! 522: regendp[parno] = ender; /* have seen the close paren */
! 523: return ret;
! 524: }
! 525:
! 526: /*
! 527: - regbranch - one alternative of an | operator
! 528: *
! 529: * Implements the concatenation operator.
! 530: */
! 531: static char_u *
! 532: regbranch(flagp)
! 533: int *flagp;
! 534: {
! 535: register char_u *ret;
! 536: register char_u *chain;
! 537: register char_u *latest;
! 538: int flags;
! 539:
! 540: *flagp = WORST; /* Tentatively. */
! 541:
! 542: ret = regnode(BRANCH);
! 543: chain = NULL;
! 544: while (peekchr() != '\0' && PeekChr() != Magic('|') && PeekChr() != Magic(')')) {
! 545: latest = regpiece(&flags);
! 546: if (latest == NULL)
! 547: return NULL;
! 548: *flagp |= flags & HASWIDTH;
! 549: if (chain == NULL) /* First piece. */
! 550: *flagp |= flags & SPSTART;
! 551: else
! 552: regtail(chain, latest);
! 553: chain = latest;
! 554: }
! 555: if (chain == NULL) /* Loop ran zero times. */
! 556: (void) regnode(NOTHING);
! 557:
! 558: return ret;
! 559: }
! 560:
! 561: /*
! 562: - regpiece - something followed by possible [*+=]
! 563: *
! 564: * Note that the branching code sequences used for = and the general cases
! 565: * of * and + are somewhat optimized: they use the same NOTHING node as
! 566: * both the endmarker for their branch list and the body of the last branch.
! 567: * It might seem that this node could be dispensed with entirely, but the
! 568: * endmarker role is not redundant.
! 569: */
! 570: static char_u *
! 571: regpiece(flagp)
! 572: int *flagp;
! 573: {
! 574: register char_u *ret;
! 575: register int op;
! 576: register char_u *next;
! 577: int flags;
! 578:
! 579: ret = regatom(&flags);
! 580: if (ret == NULL)
! 581: return NULL;
! 582:
! 583: op = peekchr();
! 584: if (!ismult(op)) {
! 585: *flagp = flags;
! 586: return ret;
! 587: }
! 588: if (!(flags & HASWIDTH) && op != Magic('='))
! 589: EMSG_RETURN((char_u *)"*+ operand could be empty");
! 590: *flagp = (op != Magic('+')) ? (WORST | SPSTART) : (WORST | HASWIDTH);
! 591:
! 592: if (op == Magic('*') && (flags & SIMPLE))
! 593: reginsert(STAR, ret);
! 594: else if (op == Magic('*')) {
! 595: /* Emit x* as (x&|), where & means "self". */
! 596: reginsert(BRANCH, ret); /* Either x */
! 597: regoptail(ret, regnode(BACK)); /* and loop */
! 598: regoptail(ret, ret); /* back */
! 599: regtail(ret, regnode(BRANCH)); /* or */
! 600: regtail(ret, regnode(NOTHING)); /* null. */
! 601: } else if (op == Magic('+') && (flags & SIMPLE))
! 602: reginsert(PLUS, ret);
! 603: else if (op == Magic('+')) {
! 604: /* Emit x+ as x(&|), where & means "self". */
! 605: next = regnode(BRANCH); /* Either */
! 606: regtail(ret, next);
! 607: regtail(regnode(BACK), ret); /* loop back */
! 608: regtail(next, regnode(BRANCH)); /* or */
! 609: regtail(ret, regnode(NOTHING)); /* null. */
! 610: } else if (op == Magic('=')) {
! 611: /* Emit x= as (x|) */
! 612: reginsert(BRANCH, ret); /* Either x */
! 613: regtail(ret, regnode(BRANCH)); /* or */
! 614: next = regnode(NOTHING);/* null. */
! 615: regtail(ret, next);
! 616: regoptail(ret, next);
! 617: }
! 618: skipchr();
! 619: if (ismult(peekchr()))
! 620: EMSG_RETURN((char_u *)"Nested *=+");
! 621:
! 622: return ret;
! 623: }
! 624:
! 625: /*
! 626: - regatom - the lowest level
! 627: *
! 628: * Optimization: gobbles an entire sequence of ordinary characters so that
! 629: * it can turn them into a single node, which is smaller to store and
! 630: * faster to run.
! 631: */
! 632: static char_u *
! 633: regatom(flagp)
! 634: int *flagp;
! 635: {
! 636: register char_u *ret;
! 637: int flags;
! 638:
! 639: *flagp = WORST; /* Tentatively. */
! 640:
! 641: switch (getchr()) {
! 642: case Magic('^'):
! 643: ret = regnode(BOL);
! 644: break;
! 645: case Magic('$'):
! 646: ret = regnode(EOL);
! 647: break;
! 648: case Magic('<'):
! 649: ret = regnode(BOW);
! 650: break;
! 651: case Magic('>'):
! 652: ret = regnode(EOW);
! 653: break;
! 654: case Magic('.'):
! 655: ret = regnode(ANY);
! 656: *flagp |= HASWIDTH | SIMPLE;
! 657: break;
! 658: case Magic('i'):
! 659: ret = regnode(IDENT);
! 660: *flagp |= HASWIDTH | SIMPLE;
! 661: break;
! 662: case Magic('k'):
! 663: ret = regnode(WORD);
! 664: *flagp |= HASWIDTH | SIMPLE;
! 665: break;
! 666: case Magic('I'):
! 667: ret = regnode(SIDENT);
! 668: *flagp |= HASWIDTH | SIMPLE;
! 669: break;
! 670: case Magic('K'):
! 671: ret = regnode(SWORD);
! 672: *flagp |= HASWIDTH | SIMPLE;
! 673: break;
! 674: case Magic('f'):
! 675: ret = regnode(FNAME);
! 676: *flagp |= HASWIDTH | SIMPLE;
! 677: break;
! 678: case Magic('F'):
! 679: ret = regnode(SFNAME);
! 680: *flagp |= HASWIDTH | SIMPLE;
! 681: break;
! 682: case Magic('p'):
! 683: ret = regnode(PRINT);
! 684: *flagp |= HASWIDTH | SIMPLE;
! 685: break;
! 686: case Magic('P'):
! 687: ret = regnode(SPRINT);
! 688: *flagp |= HASWIDTH | SIMPLE;
! 689: break;
! 690: case Magic('('):
! 691: ret = reg(1, &flags);
! 692: if (ret == NULL)
! 693: return NULL;
! 694: *flagp |= flags & (HASWIDTH | SPSTART);
! 695: break;
! 696: case '\0':
! 697: case Magic('|'):
! 698: case Magic(')'):
! 699: EMSG_RETURN(e_internal) /* Supposed to be caught earlier. */
! 700: /* NOTREACHED */
! 701: case Magic('='):
! 702: EMSG_RETURN((char_u *)"\\= follows nothing")
! 703: /* NOTREACHED */
! 704: case Magic('+'):
! 705: EMSG_RETURN((char_u *)"\\+ follows nothing")
! 706: /* NOTREACHED */
! 707: case Magic('*'):
! 708: if (reg_magic)
! 709: EMSG_RETURN((char_u *)"* follows nothing")
! 710: else
! 711: EMSG_RETURN((char_u *)"\\* follows nothing")
! 712: /* break; Not Reached */
! 713: #ifdef TILDE
! 714: case Magic('~'): /* previous substitute pattern */
! 715: if (reg_prev_sub) {
! 716: register char_u *p;
! 717:
! 718: ret = regnode(EXACTLY);
! 719: p = reg_prev_sub;
! 720: while (*p) {
! 721: regc(*p++);
! 722: }
! 723: regc('\0');
! 724: if (p - reg_prev_sub) {
! 725: *flagp |= HASWIDTH;
! 726: if ((p - reg_prev_sub) == 1)
! 727: *flagp |= SIMPLE;
! 728: }
! 729: } else
! 730: EMSG_RETURN(e_nopresub);
! 731: break;
! 732: #endif
! 733: #ifdef BACKREF
! 734: case Magic('1'):
! 735: case Magic('2'):
! 736: case Magic('3'):
! 737: case Magic('4'):
! 738: case Magic('5'):
! 739: case Magic('6'):
! 740: case Magic('7'):
! 741: case Magic('8'):
! 742: case Magic('9'): {
! 743: int refnum;
! 744:
! 745: ungetchr();
! 746: refnum = getchr() - Magic('0');
! 747: /*
! 748: * Check if the back reference is legal. We use the parentheses
! 749: * pointers to mark encountered close parentheses, but this
! 750: * is only available in the second pass. Checking opens is
! 751: * always possible.
! 752: * Should also check that we don't refer to something that
! 753: * is repeated (+*=): what instance of the repetition should
! 754: * we match? TODO.
! 755: */
! 756: if (refnum < regnpar &&
! 757: (regendp == NULL || regendp[refnum] != NULL))
! 758: ret = regnode(BACKREF + refnum);
! 759: else
! 760: EMSG_RETURN((char_u *)"Illegal back reference");
! 761: }
! 762: break;
! 763: #endif
! 764: case Magic('['):
! 765: {
! 766: char_u *p;
! 767:
! 768: /*
! 769: * If there is no matching ']', we assume the '[' is a normal
! 770: * character. This makes ":help [" work.
! 771: */
! 772: p = regparse;
! 773: if (*p == '^') /* Complement of range. */
! 774: ++p;
! 775: if (*p == ']' || *p == '-')
! 776: ++p;
! 777: while (*p != '\0' && *p != ']')
! 778: {
! 779: if (*p == '-')
! 780: {
! 781: ++p;
! 782: if (*p != ']' && *p != '\0')
! 783: ++p;
! 784: }
! 785: else if (*p == '\\' && p[1] != '\0')
! 786: p += 2;
! 787: else
! 788: ++p;
! 789: }
! 790: if (*p == ']') /* there is a matching ']' */
! 791: {
! 792: /*
! 793: * In a character class, different parsing rules apply.
! 794: * Not even \ is special anymore, nothing is.
! 795: */
! 796: if (*regparse == '^') { /* Complement of range. */
! 797: ret = regnode(ANYBUT);
! 798: regparse++;
! 799: } else
! 800: ret = regnode(ANYOF);
! 801: if (*regparse == ']' || *regparse == '-')
! 802: regc(*regparse++);
! 803: while (*regparse != '\0' && *regparse != ']') {
! 804: if (*regparse == '-') {
! 805: regparse++;
! 806: if (*regparse == ']' || *regparse == '\0')
! 807: regc('-');
! 808: else {
! 809: register int cclass;
! 810: register int cclassend;
! 811:
! 812: cclass = UCHARAT(regparse - 2) + 1;
! 813: cclassend = UCHARAT(regparse);
! 814: if (cclass > cclassend + 1)
! 815: EMSG_RETURN(e_invrange);
! 816: for (; cclass <= cclassend; cclass++)
! 817: regc(cclass);
! 818: regparse++;
! 819: }
! 820: } else if (*regparse == '\\' && regparse[1]) {
! 821: regparse++;
! 822: regc(*regparse++);
! 823: } else
! 824: regc(*regparse++);
! 825: }
! 826: regc('\0');
! 827: if (*regparse != ']')
! 828: EMSG_RETURN(e_toomsbra);
! 829: skipchr(); /* let's be friends with the lexer again */
! 830: *flagp |= HASWIDTH | SIMPLE;
! 831: break;
! 832: }
! 833: }
! 834: /* FALLTHROUGH */
! 835:
! 836: default:
! 837: {
! 838: register int len;
! 839: int chr;
! 840:
! 841: ungetchr();
! 842: len = 0;
! 843: ret = regnode(EXACTLY);
! 844: /*
! 845: * Always take at least one character, for '[' without matching
! 846: * ']'.
! 847: */
! 848: while ((chr = peekchr()) != '\0' && (chr < Magic(0) || len == 0))
! 849: {
! 850: regc(chr);
! 851: skipchr();
! 852: len++;
! 853: }
! 854: #ifdef DEBUG
! 855: if (len == 0)
! 856: EMSG_RETURN((char_u *)"Unexpected magic character; check META.");
! 857: #endif
! 858: /*
! 859: * If there is a following *, \+ or \= we need the character
! 860: * in front of it as a single character operand
! 861: */
! 862: if (len > 1 && ismult(chr))
! 863: {
! 864: unregc(); /* Back off of *+= operand */
! 865: ungetchr(); /* and put it back for next time */
! 866: --len;
! 867: }
! 868: regc('\0');
! 869: *flagp |= HASWIDTH;
! 870: if (len == 1)
! 871: *flagp |= SIMPLE;
! 872: }
! 873: break;
! 874: }
! 875:
! 876: return ret;
! 877: }
! 878:
! 879: /*
! 880: - regnode - emit a node
! 881: */
! 882: static char_u * /* Location. */
! 883: regnode(op)
! 884: int op;
! 885: {
! 886: register char_u *ret;
! 887: register char_u *ptr;
! 888:
! 889: ret = regcode;
! 890: if (ret == ®dummy) {
! 891: regsize += 3;
! 892: return ret;
! 893: }
! 894: ptr = ret;
! 895: *ptr++ = op;
! 896: *ptr++ = '\0'; /* Null "next" pointer. */
! 897: *ptr++ = '\0';
! 898: regcode = ptr;
! 899:
! 900: return ret;
! 901: }
! 902:
! 903: /*
! 904: - regc - emit (if appropriate) a byte of code
! 905: */
! 906: static void
! 907: regc(b)
! 908: int b;
! 909: {
! 910: if (regcode != ®dummy)
! 911: *regcode++ = b;
! 912: else
! 913: regsize++;
! 914: }
! 915:
! 916: /*
! 917: - unregc - take back (if appropriate) a byte of code
! 918: */
! 919: static void
! 920: unregc()
! 921: {
! 922: if (regcode != ®dummy)
! 923: regcode--;
! 924: else
! 925: regsize--;
! 926: }
! 927:
! 928: /*
! 929: - reginsert - insert an operator in front of already-emitted operand
! 930: *
! 931: * Means relocating the operand.
! 932: */
! 933: static void
! 934: reginsert(op, opnd)
! 935: int op;
! 936: char_u *opnd;
! 937: {
! 938: register char_u *src;
! 939: register char_u *dst;
! 940: register char_u *place;
! 941:
! 942: if (regcode == ®dummy) {
! 943: regsize += 3;
! 944: return;
! 945: }
! 946: src = regcode;
! 947: regcode += 3;
! 948: dst = regcode;
! 949: while (src > opnd)
! 950: *--dst = *--src;
! 951:
! 952: place = opnd; /* Op node, where operand used to be. */
! 953: *place++ = op;
! 954: *place++ = '\0';
! 955: *place = '\0';
! 956: }
! 957:
! 958: /*
! 959: - regtail - set the next-pointer at the end of a node chain
! 960: */
! 961: static void
! 962: regtail(p, val)
! 963: char_u *p;
! 964: char_u *val;
! 965: {
! 966: register char_u *scan;
! 967: register char_u *temp;
! 968: register int offset;
! 969:
! 970: if (p == ®dummy)
! 971: return;
! 972:
! 973: /* Find last node. */
! 974: scan = p;
! 975: for (;;) {
! 976: temp = regnext(scan);
! 977: if (temp == NULL)
! 978: break;
! 979: scan = temp;
! 980: }
! 981:
! 982: if (OP(scan) == BACK)
! 983: offset = (int)(scan - val);
! 984: else
! 985: offset = (int)(val - scan);
! 986: *(scan + 1) = (char_u) ((offset >> 8) & 0377);
! 987: *(scan + 2) = (char_u) (offset & 0377);
! 988: }
! 989:
! 990: /*
! 991: - regoptail - regtail on operand of first argument; nop if operandless
! 992: */
! 993: static void
! 994: regoptail(p, val)
! 995: char_u *p;
! 996: char_u *val;
! 997: {
! 998: /* "Operandless" and "op != BRANCH" are synonymous in practice. */
! 999: if (p == NULL || p == ®dummy || OP(p) != BRANCH)
! 1000: return;
! 1001: regtail(OPERAND(p), val);
! 1002: }
! 1003:
! 1004: /*
! 1005: - getchr() - get the next character from the pattern. We know about
! 1006: * magic and such, so therefore we need a lexical analyzer.
! 1007: */
! 1008:
! 1009: /* static int curchr; */
! 1010: static int prevchr;
! 1011: static int nextchr; /* used for ungetchr() */
! 1012: /*
! 1013: * Note: prevchr is sometimes -1 when we are not at the start,
! 1014: * eg in /[ ^I]^ the pattern was never found even if it existed, because ^ was
! 1015: * taken to be magic -- webb
! 1016: */
! 1017: static int at_start; /* True when we are on the first character */
! 1018:
! 1019: static void
! 1020: initchr(str)
! 1021: char_u *str;
! 1022: {
! 1023: regparse = str;
! 1024: curchr = prevchr = nextchr = -1;
! 1025: at_start = TRUE;
! 1026: }
! 1027:
! 1028: static int
! 1029: peekchr()
! 1030: {
! 1031: if (curchr < 0) {
! 1032: switch (curchr = regparse[0]) {
! 1033: case '.':
! 1034: /* case '+':*/
! 1035: /* case '=':*/
! 1036: case '[':
! 1037: case '~':
! 1038: if (reg_magic)
! 1039: curchr = Magic(curchr);
! 1040: break;
! 1041: case '*':
! 1042: /* * is not magic as the very first character, eg "?*ptr" */
! 1043: if (reg_magic && !at_start)
! 1044: curchr = Magic('*');
! 1045: break;
! 1046: case '^':
! 1047: /* ^ is only magic as the very first character */
! 1048: if (at_start)
! 1049: curchr = Magic('^');
! 1050: break;
! 1051: case '$':
! 1052: /* $ is only magic as the very last character and in front of '\|' */
! 1053: if (regparse[1] == NUL || (regparse[1] == '\\' && regparse[2] == '|'))
! 1054: curchr = Magic('$');
! 1055: break;
! 1056: case '\\':
! 1057: regparse++;
! 1058: if (regparse[0] == NUL)
! 1059: curchr = '\\'; /* trailing '\' */
! 1060: else if (vim_strchr(META, regparse[0]))
! 1061: {
! 1062: /*
! 1063: * META contains everything that may be magic sometimes, except
! 1064: * ^ and $ ("\^" and "\$" are never magic).
! 1065: * We now fetch the next character and toggle its magicness.
! 1066: * Therefore, \ is so meta-magic that it is not in META.
! 1067: */
! 1068: curchr = -1;
! 1069: at_start = FALSE; /* We still want to be able to say "/\*ptr" */
! 1070: peekchr();
! 1071: curchr ^= Magic(0);
! 1072: }
! 1073: else if (vim_strchr(REGEXP_ABBR, regparse[0]))
! 1074: {
! 1075: /*
! 1076: * Handle abbreviations, like "\t" for TAB -- webb
! 1077: */
! 1078: switch (regparse[0])
! 1079: {
! 1080: case 'r': curchr = CR; break;
! 1081: case 't': curchr = TAB; break;
! 1082: case 'e': curchr = ESC; break;
! 1083: case 'b': curchr = Ctrl('H'); break;
! 1084: }
! 1085: }
! 1086: else
! 1087: {
! 1088: /*
! 1089: * Next character can never be (made) magic?
! 1090: * Then backslashing it won't do anything.
! 1091: */
! 1092: curchr = regparse[0];
! 1093: }
! 1094: break;
! 1095: }
! 1096: }
! 1097:
! 1098: return curchr;
! 1099: }
! 1100:
! 1101: static void
! 1102: skipchr()
! 1103: {
! 1104: regparse++;
! 1105: at_start = FALSE;
! 1106: prevchr = curchr;
! 1107: curchr = nextchr; /* use previously unget char, or -1 */
! 1108: nextchr = -1;
! 1109: }
! 1110:
! 1111: static int
! 1112: getchr()
! 1113: {
! 1114: int chr;
! 1115:
! 1116: chr = peekchr();
! 1117: skipchr();
! 1118:
! 1119: return chr;
! 1120: }
! 1121:
! 1122: /*
! 1123: * put character back. Works only once!
! 1124: */
! 1125: static void
! 1126: ungetchr()
! 1127: {
! 1128: nextchr = curchr;
! 1129: curchr = prevchr;
! 1130: /*
! 1131: * Backup regparse as well; not because we will use what it points at,
! 1132: * but because skipchr() will bump it again.
! 1133: */
! 1134: regparse--;
! 1135: }
! 1136:
! 1137: /*
! 1138: * vim_regexec and friends
! 1139: */
! 1140:
! 1141: /*
! 1142: * Global work variables for vim_regexec().
! 1143: */
! 1144: static char_u *reginput; /* String-input pointer. */
! 1145: static char_u *regbol; /* Beginning of input, for ^ check. */
! 1146: static char_u **regstartp; /* Pointer to startp array. */
! 1147: /* static char_u **regendp; */ /* Ditto for endp. */
! 1148:
! 1149: /*
! 1150: * Forwards.
! 1151: */
! 1152: static int regtry __ARGS((regexp *, char_u *));
! 1153: static int regmatch __ARGS((char_u *));
! 1154: static int regrepeat __ARGS((char_u *));
! 1155:
! 1156: #ifdef DEBUG
! 1157: int regnarrate = 1;
! 1158: void regdump __ARGS((regexp *));
! 1159: static char_u *regprop __ARGS((char_u *));
! 1160: #endif
! 1161:
! 1162: /*
! 1163: * vim_regexec - match a regexp against a string
! 1164: * Return non-zero if there is a match.
! 1165: */
! 1166: int
! 1167: vim_regexec(prog, string, at_bol)
! 1168: register regexp *prog;
! 1169: register char_u *string;
! 1170: int at_bol;
! 1171: {
! 1172: register char_u *s;
! 1173:
! 1174: /* Be paranoid... */
! 1175: if (prog == NULL || string == NULL) {
! 1176: emsg(e_null);
! 1177: rc_did_emsg = TRUE;
! 1178: return 0;
! 1179: }
! 1180: /* Check validity of program. */
! 1181: if (UCHARAT(prog->program) != MAGIC) {
! 1182: emsg(e_re_corr);
! 1183: rc_did_emsg = TRUE;
! 1184: return 0;
! 1185: }
! 1186: /* If there is a "must appear" string, look for it. */
! 1187: if (prog->regmust != NULL) {
! 1188: s = string;
! 1189: while ((s = cstrchr(s, prog->regmust[0])) != NULL) {
! 1190: if (cstrncmp(s, prog->regmust, prog->regmlen) == 0)
! 1191: break; /* Found it. */
! 1192: s++;
! 1193: }
! 1194: if (s == NULL) /* Not present. */
! 1195: return 0;
! 1196: }
! 1197: /* Mark beginning of line for ^ . */
! 1198: if (at_bol)
! 1199: regbol = string; /* is possible to match bol */
! 1200: else
! 1201: regbol = NULL; /* we aren't there, so don't match it */
! 1202:
! 1203: /* Simplest case: anchored match need be tried only once. */
! 1204: if (prog->reganch)
! 1205: return regtry(prog, string);
! 1206:
! 1207: /* Messy cases: unanchored match. */
! 1208: s = string;
! 1209: if (prog->regstart != '\0')
! 1210: /* We know what char it must start with. */
! 1211: while ((s = cstrchr(s, prog->regstart)) != NULL) {
! 1212: if (regtry(prog, s))
! 1213: return 1;
! 1214: s++;
! 1215: }
! 1216: else
! 1217: /* We don't -- general case. */
! 1218: do {
! 1219: if (regtry(prog, s))
! 1220: return 1;
! 1221: } while (*s++ != '\0');
! 1222:
! 1223: /* Failure. */
! 1224: return 0;
! 1225: }
! 1226:
! 1227: /*
! 1228: - regtry - try match at specific point
! 1229: */
! 1230: static int /* 0 failure, 1 success */
! 1231: regtry(prog, string)
! 1232: regexp *prog;
! 1233: char_u *string;
! 1234: {
! 1235: register int i;
! 1236: register char_u **sp;
! 1237: register char_u **ep;
! 1238:
! 1239: reginput = string;
! 1240: regstartp = prog->startp;
! 1241: regendp = prog->endp;
! 1242:
! 1243: sp = prog->startp;
! 1244: ep = prog->endp;
! 1245: for (i = NSUBEXP; i > 0; i--) {
! 1246: *sp++ = NULL;
! 1247: *ep++ = NULL;
! 1248: }
! 1249: if (regmatch(prog->program + 1)) {
! 1250: prog->startp[0] = string;
! 1251: prog->endp[0] = reginput;
! 1252: return 1;
! 1253: } else
! 1254: return 0;
! 1255: }
! 1256:
! 1257: /*
! 1258: - regmatch - main matching routine
! 1259: *
! 1260: * Conceptually the strategy is simple: check to see whether the current
! 1261: * node matches, call self recursively to see whether the rest matches,
! 1262: * and then act accordingly. In practice we make some effort to avoid
! 1263: * recursion, in particular by going through "ordinary" nodes (that don't
! 1264: * need to know whether the rest of the match failed) by a loop instead of
! 1265: * by recursion.
! 1266: */
! 1267: static int /* 0 failure, 1 success */
! 1268: regmatch(prog)
! 1269: char_u *prog;
! 1270: {
! 1271: register char_u *scan; /* Current node. */
! 1272: char_u *next; /* Next node. */
! 1273:
! 1274: scan = prog;
! 1275: #ifdef DEBUG
! 1276: if (scan != NULL && regnarrate)
! 1277: fprintf(stderr, "%s(\n", regprop(scan));
! 1278: #endif
! 1279: while (scan != NULL) {
! 1280: #ifdef DEBUG
! 1281: if (regnarrate) {
! 1282: fprintf(stderr, "%s...\n", regprop(scan));
! 1283: }
! 1284: #endif
! 1285: next = regnext(scan);
! 1286: switch (OP(scan)) {
! 1287: case BOL:
! 1288: if (reginput != regbol)
! 1289: return 0;
! 1290: break;
! 1291: case EOL:
! 1292: if (*reginput != '\0')
! 1293: return 0;
! 1294: break;
! 1295: case BOW: /* \<word; reginput points to w */
! 1296: if (reginput != regbol && iswordchar(reginput[-1]))
! 1297: return 0;
! 1298: if (!reginput[0] || !iswordchar(reginput[0]))
! 1299: return 0;
! 1300: break;
! 1301: case EOW: /* word\>; reginput points after d */
! 1302: if (reginput == regbol || !iswordchar(reginput[-1]))
! 1303: return 0;
! 1304: if (reginput[0] && iswordchar(reginput[0]))
! 1305: return 0;
! 1306: break;
! 1307: case ANY:
! 1308: if (*reginput == '\0')
! 1309: return 0;
! 1310: reginput++;
! 1311: break;
! 1312: case IDENT:
! 1313: if (!isidchar(*reginput))
! 1314: return 0;
! 1315: reginput++;
! 1316: break;
! 1317: case WORD:
! 1318: if (!iswordchar(*reginput))
! 1319: return 0;
! 1320: reginput++;
! 1321: break;
! 1322: case FNAME:
! 1323: if (!isfilechar(*reginput))
! 1324: return 0;
! 1325: reginput++;
! 1326: break;
! 1327: case PRINT:
! 1328: if (charsize(*reginput) != 1)
! 1329: return 0;
! 1330: reginput++;
! 1331: break;
! 1332: case SIDENT:
! 1333: if (isdigit(*reginput) || !isidchar(*reginput))
! 1334: return 0;
! 1335: reginput++;
! 1336: break;
! 1337: case SWORD:
! 1338: if (isdigit(*reginput) || !iswordchar(*reginput))
! 1339: return 0;
! 1340: reginput++;
! 1341: break;
! 1342: case SFNAME:
! 1343: if (isdigit(*reginput) || !isfilechar(*reginput))
! 1344: return 0;
! 1345: reginput++;
! 1346: break;
! 1347: case SPRINT:
! 1348: if (isdigit(*reginput) || charsize(*reginput) != 1)
! 1349: return 0;
! 1350: reginput++;
! 1351: break;
! 1352: case EXACTLY:{
! 1353: register int len;
! 1354: register char_u *opnd;
! 1355:
! 1356: opnd = OPERAND(scan);
! 1357: /* Inline the first character, for speed. */
! 1358: if (*opnd != *reginput && (!reg_ic || TO_UPPER(*opnd) != TO_UPPER(*reginput)))
! 1359: return 0;
! 1360: len = STRLEN(opnd);
! 1361: if (len > 1 && cstrncmp(opnd, reginput, len) != 0)
! 1362: return 0;
! 1363: reginput += len;
! 1364: }
! 1365: break;
! 1366: case ANYOF:
! 1367: if (*reginput == '\0' || cstrchr(OPERAND(scan), *reginput) == NULL)
! 1368: return 0;
! 1369: reginput++;
! 1370: break;
! 1371: case ANYBUT:
! 1372: if (*reginput == '\0' || cstrchr(OPERAND(scan), *reginput) != NULL)
! 1373: return 0;
! 1374: reginput++;
! 1375: break;
! 1376: case NOTHING:
! 1377: break;
! 1378: case BACK:
! 1379: break;
! 1380: case MOPEN + 1:
! 1381: case MOPEN + 2:
! 1382: case MOPEN + 3:
! 1383: case MOPEN + 4:
! 1384: case MOPEN + 5:
! 1385: case MOPEN + 6:
! 1386: case MOPEN + 7:
! 1387: case MOPEN + 8:
! 1388: case MOPEN + 9:{
! 1389: register int no;
! 1390: register char_u *save;
! 1391:
! 1392: no = OP(scan) - MOPEN;
! 1393: save = regstartp[no];
! 1394: regstartp[no] = reginput; /* Tentatively */
! 1395: #ifdef DEBUG
! 1396: printf("MOPEN %d pre @'%s' ('%s' )'%s'\n",
! 1397: no, save,
! 1398: regstartp[no] ? regstartp[no] : "NULL",
! 1399: regendp[no] ? regendp[no] : "NULL");
! 1400: #endif
! 1401:
! 1402: if (regmatch(next)) {
! 1403: #ifdef DEBUG
! 1404: printf("MOPEN %d post @'%s' ('%s' )'%s'\n",
! 1405: no, save,
! 1406: regstartp[no] ? regstartp[no] : "NULL",
! 1407: regendp[no] ? regendp[no] : "NULL");
! 1408: #endif
! 1409: return 1;
! 1410: }
! 1411: regstartp[no] = save; /* We were wrong... */
! 1412: return 0;
! 1413: }
! 1414: /* break; Not Reached */
! 1415: case MCLOSE + 1:
! 1416: case MCLOSE + 2:
! 1417: case MCLOSE + 3:
! 1418: case MCLOSE + 4:
! 1419: case MCLOSE + 5:
! 1420: case MCLOSE + 6:
! 1421: case MCLOSE + 7:
! 1422: case MCLOSE + 8:
! 1423: case MCLOSE + 9:{
! 1424: register int no;
! 1425: register char_u *save;
! 1426:
! 1427: no = OP(scan) - MCLOSE;
! 1428: save = regendp[no];
! 1429: regendp[no] = reginput; /* Tentatively */
! 1430: #ifdef DEBUG
! 1431: printf("MCLOSE %d pre @'%s' ('%s' )'%s'\n",
! 1432: no, save,
! 1433: regstartp[no] ? regstartp[no] : "NULL",
! 1434: regendp[no] ? regendp[no] : "NULL");
! 1435: #endif
! 1436:
! 1437: if (regmatch(next)) {
! 1438: #ifdef DEBUG
! 1439: printf("MCLOSE %d post @'%s' ('%s' )'%s'\n",
! 1440: no, save,
! 1441: regstartp[no] ? regstartp[no] : "NULL",
! 1442: regendp[no] ? regendp[no] : "NULL");
! 1443: #endif
! 1444: return 1;
! 1445: }
! 1446: regendp[no] = save; /* We were wrong... */
! 1447: return 0;
! 1448: }
! 1449: /* break; Not Reached */
! 1450: #ifdef BACKREF
! 1451: case BACKREF + 1:
! 1452: case BACKREF + 2:
! 1453: case BACKREF + 3:
! 1454: case BACKREF + 4:
! 1455: case BACKREF + 5:
! 1456: case BACKREF + 6:
! 1457: case BACKREF + 7:
! 1458: case BACKREF + 8:
! 1459: case BACKREF + 9:{
! 1460: register int no;
! 1461: int len;
! 1462:
! 1463: no = OP(scan) - BACKREF;
! 1464: if (regendp[no] != NULL) {
! 1465: len = (int)(regendp[no] - regstartp[no]);
! 1466: if (cstrncmp(regstartp[no], reginput, len) != 0)
! 1467: return 0;
! 1468: reginput += len;
! 1469: } else {
! 1470: /*emsg("backref to 0-repeat");*/
! 1471: /*return 0;*/
! 1472: }
! 1473: }
! 1474: break;
! 1475: #endif
! 1476: case BRANCH:{
! 1477: register char_u *save;
! 1478:
! 1479: if (OP(next) != BRANCH) /* No choice. */
! 1480: next = OPERAND(scan); /* Avoid recursion. */
! 1481: else {
! 1482: do {
! 1483: save = reginput;
! 1484: if (regmatch(OPERAND(scan)))
! 1485: return 1;
! 1486: reginput = save;
! 1487: scan = regnext(scan);
! 1488: } while (scan != NULL && OP(scan) == BRANCH);
! 1489: return 0;
! 1490: /* NOTREACHED */
! 1491: }
! 1492: }
! 1493: break;
! 1494: case STAR:
! 1495: case PLUS:{
! 1496: register int nextch;
! 1497: register int no;
! 1498: register char_u *save;
! 1499: register int min;
! 1500:
! 1501: /*
! 1502: * Lookahead to avoid useless match attempts when we know
! 1503: * what character comes next.
! 1504: */
! 1505: nextch = '\0';
! 1506: if (OP(next) == EXACTLY)
! 1507: {
! 1508: nextch = *OPERAND(next);
! 1509: if (reg_ic)
! 1510: nextch = TO_UPPER(nextch);
! 1511: }
! 1512: min = (OP(scan) == STAR) ? 0 : 1;
! 1513: save = reginput;
! 1514: no = regrepeat(OPERAND(scan));
! 1515: while (no >= min)
! 1516: {
! 1517: /* If it could work, try it. */
! 1518: if (nextch == '\0' || (*reginput == nextch ||
! 1519: (reg_ic && TO_UPPER(*reginput) == nextch)))
! 1520: if (regmatch(next))
! 1521: return 1;
! 1522: /* Couldn't or didn't -- back up. */
! 1523: no--;
! 1524: reginput = save + no;
! 1525: }
! 1526: return 0;
! 1527: }
! 1528: /* break; Not Reached */
! 1529: case END:
! 1530: return 1; /* Success! */
! 1531: /* break; Not Reached */
! 1532: default:
! 1533: emsg(e_re_corr);
! 1534: return 0;
! 1535: /* break; Not Reached */
! 1536: }
! 1537:
! 1538: scan = next;
! 1539: }
! 1540:
! 1541: /*
! 1542: * We get here only if there's trouble -- normally "case END" is the
! 1543: * terminating point.
! 1544: */
! 1545: emsg(e_re_corr);
! 1546: return 0;
! 1547: }
! 1548:
! 1549: /*
! 1550: - regrepeat - repeatedly match something simple, report how many
! 1551: */
! 1552: static int
! 1553: regrepeat(p)
! 1554: char_u *p;
! 1555: {
! 1556: register int count = 0;
! 1557: register char_u *scan;
! 1558: register char_u *opnd;
! 1559:
! 1560: scan = reginput;
! 1561: opnd = OPERAND(p);
! 1562: switch (OP(p)) {
! 1563: case ANY:
! 1564: count = STRLEN(scan);
! 1565: scan += count;
! 1566: break;
! 1567: case IDENT:
! 1568: for (count = 0; isidchar(*scan); ++count)
! 1569: ++scan;
! 1570: break;
! 1571: case WORD:
! 1572: for (count = 0; iswordchar(*scan); ++count)
! 1573: ++scan;
! 1574: break;
! 1575: case FNAME:
! 1576: for (count = 0; isfilechar(*scan); ++count)
! 1577: ++scan;
! 1578: break;
! 1579: case PRINT:
! 1580: for (count = 0; charsize(*scan) == 1; ++count)
! 1581: ++scan;
! 1582: break;
! 1583: case SIDENT:
! 1584: for (count = 0; !isdigit(*scan) && isidchar(*scan); ++count)
! 1585: ++scan;
! 1586: break;
! 1587: case SWORD:
! 1588: for (count = 0; !isdigit(*scan) && iswordchar(*scan); ++count)
! 1589: ++scan;
! 1590: break;
! 1591: case SFNAME:
! 1592: for (count = 0; !isdigit(*scan) && isfilechar(*scan); ++count)
! 1593: ++scan;
! 1594: break;
! 1595: case SPRINT:
! 1596: for (count = 0; !isdigit(*scan) && charsize(*scan) == 1; ++count)
! 1597: ++scan;
! 1598: break;
! 1599: case EXACTLY:
! 1600: while (*opnd == *scan || (reg_ic && TO_UPPER(*opnd) == TO_UPPER(*scan)))
! 1601: {
! 1602: count++;
! 1603: scan++;
! 1604: }
! 1605: break;
! 1606: case ANYOF:
! 1607: while (*scan != '\0' && cstrchr(opnd, *scan) != NULL)
! 1608: {
! 1609: count++;
! 1610: scan++;
! 1611: }
! 1612: break;
! 1613: case ANYBUT:
! 1614: while (*scan != '\0' && cstrchr(opnd, *scan) == NULL) {
! 1615: count++;
! 1616: scan++;
! 1617: }
! 1618: break;
! 1619: default: /* Oh dear. Called inappropriately. */
! 1620: emsg(e_re_corr);
! 1621: count = 0; /* Best compromise. */
! 1622: break;
! 1623: }
! 1624: reginput = scan;
! 1625:
! 1626: return count;
! 1627: }
! 1628:
! 1629: /*
! 1630: - regnext - dig the "next" pointer out of a node
! 1631: */
! 1632: static char_u *
! 1633: regnext(p)
! 1634: register char_u *p;
! 1635: {
! 1636: register int offset;
! 1637:
! 1638: if (p == ®dummy)
! 1639: return NULL;
! 1640:
! 1641: offset = NEXT(p);
! 1642: if (offset == 0)
! 1643: return NULL;
! 1644:
! 1645: if (OP(p) == BACK)
! 1646: return p - offset;
! 1647: else
! 1648: return p + offset;
! 1649: }
! 1650:
! 1651: #ifdef DEBUG
! 1652:
! 1653: /*
! 1654: - regdump - dump a regexp onto stdout in vaguely comprehensible form
! 1655: */
! 1656: void
! 1657: regdump(r)
! 1658: regexp *r;
! 1659: {
! 1660: register char_u *s;
! 1661: register int op = EXACTLY; /* Arbitrary non-END op. */
! 1662: register char_u *next;
! 1663:
! 1664:
! 1665: s = r->program + 1;
! 1666: while (op != END) { /* While that wasn't END last time... */
! 1667: op = OP(s);
! 1668: printf("%2d%s", s - r->program, regprop(s)); /* Where, what. */
! 1669: next = regnext(s);
! 1670: if (next == NULL) /* Next ptr. */
! 1671: printf("(0)");
! 1672: else
! 1673: printf("(%d)", (s - r->program) + (next - s));
! 1674: s += 3;
! 1675: if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
! 1676: /* Literal string, where present. */
! 1677: while (*s != '\0') {
! 1678: putchar(*s);
! 1679: s++;
! 1680: }
! 1681: s++;
! 1682: }
! 1683: putchar('\n');
! 1684: }
! 1685:
! 1686: /* Header fields of interest. */
! 1687: if (r->regstart != '\0')
! 1688: printf("start `%c' ", r->regstart);
! 1689: if (r->reganch)
! 1690: printf("anchored ");
! 1691: if (r->regmust != NULL)
! 1692: printf("must have \"%s\"", r->regmust);
! 1693: printf("\n");
! 1694: }
! 1695:
! 1696: /*
! 1697: - regprop - printable representation of opcode
! 1698: */
! 1699: static char_u *
! 1700: regprop(op)
! 1701: char_u *op;
! 1702: {
! 1703: register char_u *p;
! 1704: static char_u buf[50];
! 1705:
! 1706: (void) strcpy(buf, ":");
! 1707:
! 1708: switch (OP(op)) {
! 1709: case BOL:
! 1710: p = "BOL";
! 1711: break;
! 1712: case EOL:
! 1713: p = "EOL";
! 1714: break;
! 1715: case ANY:
! 1716: p = "ANY";
! 1717: break;
! 1718: case IDENT:
! 1719: p = "IDENT";
! 1720: break;
! 1721: case WORD:
! 1722: p = "WORD";
! 1723: break;
! 1724: case FNAME:
! 1725: p = "FNAME";
! 1726: break;
! 1727: case PRINT:
! 1728: p = "PRINT";
! 1729: break;
! 1730: case SIDENT:
! 1731: p = "SIDENT";
! 1732: break;
! 1733: case SWORD:
! 1734: p = "SWORD";
! 1735: break;
! 1736: case SFNAME:
! 1737: p = "SFNAME";
! 1738: break;
! 1739: case SPRINT:
! 1740: p = "SPRINT";
! 1741: break;
! 1742: case ANYOF:
! 1743: p = "ANYOF";
! 1744: break;
! 1745: case ANYBUT:
! 1746: p = "ANYBUT";
! 1747: break;
! 1748: case BRANCH:
! 1749: p = "BRANCH";
! 1750: break;
! 1751: case EXACTLY:
! 1752: p = "EXACTLY";
! 1753: break;
! 1754: case NOTHING:
! 1755: p = "NOTHING";
! 1756: break;
! 1757: case BACK:
! 1758: p = "BACK";
! 1759: break;
! 1760: case END:
! 1761: p = "END";
! 1762: break;
! 1763: case MOPEN + 1:
! 1764: case MOPEN + 2:
! 1765: case MOPEN + 3:
! 1766: case MOPEN + 4:
! 1767: case MOPEN + 5:
! 1768: case MOPEN + 6:
! 1769: case MOPEN + 7:
! 1770: case MOPEN + 8:
! 1771: case MOPEN + 9:
! 1772: sprintf(buf + STRLEN(buf), "MOPEN%d", OP(op) - MOPEN);
! 1773: p = NULL;
! 1774: break;
! 1775: case MCLOSE + 1:
! 1776: case MCLOSE + 2:
! 1777: case MCLOSE + 3:
! 1778: case MCLOSE + 4:
! 1779: case MCLOSE + 5:
! 1780: case MCLOSE + 6:
! 1781: case MCLOSE + 7:
! 1782: case MCLOSE + 8:
! 1783: case MCLOSE + 9:
! 1784: sprintf(buf + STRLEN(buf), "MCLOSE%d", OP(op) - MCLOSE);
! 1785: p = NULL;
! 1786: break;
! 1787: case BACKREF + 1:
! 1788: case BACKREF + 2:
! 1789: case BACKREF + 3:
! 1790: case BACKREF + 4:
! 1791: case BACKREF + 5:
! 1792: case BACKREF + 6:
! 1793: case BACKREF + 7:
! 1794: case BACKREF + 8:
! 1795: case BACKREF + 9:
! 1796: sprintf(buf + STRLEN(buf), "BACKREF%d", OP(op) - BACKREF);
! 1797: p = NULL;
! 1798: break;
! 1799: case STAR:
! 1800: p = "STAR";
! 1801: break;
! 1802: case PLUS:
! 1803: p = "PLUS";
! 1804: break;
! 1805: default:
! 1806: sprintf(buf + STRLEN(buf), "corrupt %d", OP(op));
! 1807: p = NULL;
! 1808: break;
! 1809: }
! 1810: if (p != NULL)
! 1811: (void) strcat(buf, p);
! 1812: return buf;
! 1813: }
! 1814: #endif
! 1815:
! 1816: /*
! 1817: * The following is provided for those people who do not have strcspn() in
! 1818: * their C libraries. They should get off their butts and do something
! 1819: * about it; at least one public-domain implementation of those (highly
! 1820: * useful) string routines has been published on Usenet.
! 1821: */
! 1822: #ifndef HAVE_STRCSPN
! 1823: /*
! 1824: * strcspn - find length of initial segment of s1 consisting entirely
! 1825: * of characters not from s2
! 1826: */
! 1827:
! 1828: static size_t
! 1829: strcspn(s1, s2)
! 1830: const char_u *s1;
! 1831: const char_u *s2;
! 1832: {
! 1833: register char_u *scan1;
! 1834: register char_u *scan2;
! 1835: register int count;
! 1836:
! 1837: count = 0;
! 1838: for (scan1 = s1; *scan1 != '\0'; scan1++) {
! 1839: for (scan2 = s2; *scan2 != '\0';) /* ++ moved down. */
! 1840: if (*scan1 == *scan2++)
! 1841: return count;
! 1842: count++;
! 1843: }
! 1844: return count;
! 1845: }
! 1846: #endif
! 1847:
! 1848: /*
! 1849: * Compare two strings, ignore case if reg_ic set.
! 1850: * Return 0 if strings match, non-zero otherwise.
! 1851: */
! 1852: int
! 1853: cstrncmp(s1, s2, n)
! 1854: char_u *s1, *s2;
! 1855: int n;
! 1856: {
! 1857: if (!reg_ic)
! 1858: return STRNCMP(s1, s2, (size_t)n);
! 1859:
! 1860: return vim_strnicmp(s1, s2, (size_t)n);
! 1861: }
! 1862:
! 1863: /*
! 1864: * cstrchr: This function is used a lot for simple searches, keep it fast!
! 1865: */
! 1866: static char_u *
! 1867: cstrchr(s, c)
! 1868: char_u *s;
! 1869: register int c;
! 1870: {
! 1871: register char_u *p;
! 1872:
! 1873: if (!reg_ic)
! 1874: return vim_strchr(s, c);
! 1875:
! 1876: c = TO_UPPER(c);
! 1877:
! 1878: for (p = s; *p; p++)
! 1879: {
! 1880: if (TO_UPPER(*p) == c)
! 1881: return p;
! 1882: }
! 1883: return NULL;
! 1884: }
![[BACK]](/icons/back.gif){kind=icon}
Return to regexp.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / vim