/* vi:set ts=8 sts=4 sw=4: * * Handling of regular expressions: vim_regcomp(), vim_regexec(), vim_regsub() * * 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 separately from Vim.  If you want a good * regular expression library, get the original code.  The copyright notice * that follows is from the original. * * END NOTICE * *	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. * * Changes have been made by Tony Andrews, Olaf 'Rhialto' Seibert, Robert * Webb, Ciaran McCreesh and Bram Moolenaar. * Named character class support added by Walter Briscoe (1998 Jul 01) */ #include "vim.h" #undef DEBUG /* * 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; NUL if none obvious; Can be a *		multi-byte character. * 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 * regflags	RF_ values or'ed together * * 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 vim_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 vim_regexec() needs it and vim_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 and BRACES_COMPLEX 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 "next" pointer of a BRACES_COMPLEX * node points to the node after the stuff to be repeated. * 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.) * * pattern	is coded like: * *			  +-----------------+ *			  |		    V * <aa>\|<bb>	BRANCH <aa> BRANCH <bb> --> END *		     |	    ^	 |	    ^ *		     +------+	 +----------+ * * *		       +------------------+ *		       V		  | * <aa>*	BRANCH BRANCH <aa> --> BACK BRANCH --> NOTHING --> END *		     |	    |		    ^			   ^ *		     |	    +---------------+			   | *		     +---------------------------------------------+ * * *		       +----------------------+ *		       V		      | * <aa>\+	BRANCH <aa> --> BRANCH --> BACK  BRANCH --> NOTHING --> END *		     |		     |		 ^			^ *		     |		     +-----------+			| *		     +--------------------------------------------------+ * * *					+-------------------------+ *					V			  | * <aa>\{}	BRANCH BRACE_LIMITS --> BRACE_COMPLEX <aa> --> BACK  END *		     |				    |		     ^ *		     |				    +----------------+ *		     +-----------------------------------------------+ * * * <aa>\@!<bb>	BRANCH NOMATCH <aa> --> END  <bb> --> END *		     |	     |		      ^       ^ *		     |	     +----------------+       | *		     +--------------------------------+ * *						      +---------+ *						      |		V * \z[abc]	BRANCH BRANCH  a  BRANCH  b  BRANCH  c	BRANCH	NOTHING --> END *		     |	    |	       |	  |	^		    ^ *		     |	    |	       |	  +-----+		    | *		     |	    |	       +----------------+		    | *		     |	    +---------------------------+		    | *		     +------------------------------------------------------+ * * They all start with a BRANCH for "\|" alternatives, even when there is only * one alternative. */ /* * The opcodes are: */ /* definition	number		   opnd?    meaning */#define END		0	/*	End of program or NOMATCH operand. */#define BOL		1	/*	Match "" at beginning of line. */#define EOL		2	/*	Match "" at end of line. */#define BRANCH		3	/* node Match this alternative, or the				 *	next... */#define BACK		4	/*	Match "", "next" ptr points backward. */#define EXACTLY		5	/* str	Match this string. */#define NOTHING		6	/*	Match empty string. */#define STAR		7	/* node Match this (simple) thing 0 or more				 *	times. */#define PLUS		8	/* node Match this (simple) thing 1 or more				 *	times. */#define MATCH		9	/* node match the operand zero-width */#define NOMATCH		10	/* node check for no match with operand */#define BEHIND		11	/* node look behind for a match with operand */#define NOBEHIND	12	/* node look behind for no match with operand */#define SUBPAT		13	/* node match the operand here */#define BRACE_SIMPLE	14	/* node Match this (simple) thing between m and				 *	n times (\{m,n\}). */#define BOW		15	/*	Match "" after [^a-zA-Z0-9_] */#define EOW		16	/*	Match "" at    [^a-zA-Z0-9_] */#define BRACE_LIMITS	17	/* nr nr  define the min & max for BRACE_SIMPLE				 *	and BRACE_COMPLEX. */#define NEWL		18	/*	Match line-break */#define BHPOS		19	/*	End position for BEHIND or NOBEHIND */  /* character classes: 20-48 normal, 50-78 include a line-break */#define ADD_NL		30#define FIRST_NL	ANY + ADD_NL#define ANY		20	/*	Match any one character. */#define ANYOF		21	/* str	Match any character in this string. */#define ANYBUT		22	/* str	Match any character not in this				 *	string. */#define IDENT		23	/*	Match identifier char */#define SIDENT		24	/*	Match identifier char but no digit */#define KWORD		25	/*	Match keyword char */#define SKWORD		26	/*	Match word char but no digit */#define FNAME		27	/*	Match file name char */#define SFNAME		28	/*	Match file name char but no digit */#define PRINT		29	/*	Match printable char */#define SPRINT		30	/*	Match printable char but no digit */#define WHITE		31	/*	Match whitespace char */#define NWHITE		32	/*	Match non-whitespace char */#define DIGIT		33	/*	Match digit char */#define NDIGIT		34	/*	Match non-digit char */#define HEX		35	/*	Match hex char */#define NHEX		36	/*	Match non-hex char */#define OCTAL		37	/*	Match octal char */#define NOCTAL		38	/*	Match non-octal char */#define WORD		39	/*	Match word char */#define NWORD		40	/*	Match non-word char */#define HEAD		41	/*	Match head char */#define NHEAD		42	/*	Match non-head char */#define ALPHA		43	/*	Match alpha char */#define NALPHA		44	/*	Match non-alpha char */#define LOWER		45	/*	Match lowercase char */#define NLOWER		46	/*	Match non-lowercase char */#define UPPER		47	/*	Match uppercase char */#define NUPPER		48	/*	Match non-uppercase char */#define LAST_NL		NUPPER + ADD_NL#define WITH_NL(op)	((op) >= FIRST_NL && (op) <= LAST_NL) #define MOPEN		80  /* -89	 Mark this point in input as start of				 *	 \( subexpr.  MOPEN + 0 marks start of				 *	 match. */#define MCLOSE		90  /* -99	 Analogous to MOPEN.  MCLOSE + 0 marks				 *	 end of match. */#define BACKREF		100 /* -109 node Match same string again \1-\9 */ #ifdef FEAT_SYN_HL# define ZOPEN		110 /* -119	 Mark this point in input as start of				 *	 \z( subexpr. */# define ZCLOSE		120 /* -129	 Analogous to ZOPEN. */# define ZREF		130 /* -139 node Match external submatch \z1-\z9 */#endif #define BRACE_COMPLEX	140 /* -149 node Match nodes between m & n times */ #define NOPEN		150	/*	Mark this point in input as start of					\%( subexpr. */#define NCLOSE		151	/*	Analogous to NOPEN. */ #define MULTIBYTECODE	200	/* mbc	Match one multi-byte character */#define RE_BOF		201	/*	Match "" at beginning of file. */#define RE_EOF		202	/*	Match "" at end of file. */#define CURSOR		203	/*	Match location of cursor. */ #define RE_LNUM		204	/* nr cmp  Match line number */#define RE_COL		205	/* nr cmp  Match column number */#define RE_VCOL		206	/* nr cmp  Match virtual column number */ #define RE_MARK		207	/* mark cmp  Match mark position */#define RE_VISUAL	208	/*	Match Visual area */ /* * Magic characters have a special meaning, they don't match literally. * Magic characters are negative.  This separates them from literal characters * (possibly multi-byte).  Only ASCII characters can be Magic. */#define Magic(x)	((int)(x) - 256)#define un_Magic(x)	((x) + 256)#define is_Magic(x)	((x) < 0) static int no_Magic __ARGS((int x));static int toggle_Magic __ARGS((int x));     static intno_Magic(x)    int		x;{    if (is_Magic(x))	return un_Magic(x);    return x;}     static inttoggle_Magic(x)    int		x;{    if (is_Magic(x))	return un_Magic(x);    return Magic(x);} /* * The first byte of the regexp internal "program" is actually this magic * number; the start node begins in the second byte.  It's used to catch the * most severe mutilation of the program by the caller. */ #define REGMAGIC	0234 /* * 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. * * BRACE_LIMITS	This is always followed by a BRACE_SIMPLE or BRACE_COMPLEX *		node, and defines the min and max limits to be used for that *		node. * * MOPEN,MCLOSE	...are numbered at compile time. * ZOPEN,ZCLOSE	...ditto */ /* * A node is one char of opcode followed by two chars of "next" pointer. * "Next" pointers are stored as two 8-bit bytes, 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)		((int)*(p))#define NEXT(p)		(((*((p) + 1) & 0377) << 8) + (*((p) + 2) & 0377))#define OPERAND(p)	((p) + 3)/* Obtain an operand that was stored as four bytes, MSB first. */#define OPERAND_MIN(p)	(((long)(p)[3] << 24) + ((long)(p)[4] << 16) \			+ ((long)(p)[5] << 8) + (long)(p)[6])/* Obtain a second operand stored as four bytes. */#define OPERAND_MAX(p)	OPERAND_MIN((p) + 4)/* Obtain a second single-byte operand stored after a four bytes operand. */#define OPERAND_CMP(p)	(p)[7] /* * Utility definitions. */#define UCHARAT(p)	((int)*(char_u *)(p)) /* Used for an error (down from) vim_regcomp(): give the error message, set * rc_did_emsg and return NULL */#define EMSG_RET_NULL(m) return (EMSG(m), rc_did_emsg = TRUE, (void *)NULL)#define EMSG_M_RET_NULL(m, c) return (EMSG2((m), (c) ? "" : "\\"), rc_did_emsg = TRUE, (void *)NULL)#define EMSG_RET_FAIL(m) return (EMSG(m), rc_did_emsg = TRUE, FAIL)#define EMSG_ONE_RET_NULL EMSG_M_RET_NULL(_("E369: invalid item in %s%%[]"), reg_magic == MAGIC_ALL) #define MAX_LIMIT	(32767L << 16L) static int re_multi_type __ARGS((int));static int cstrncmp __ARGS((char_u *s1, char_u *s2, int *n));static char_u *cstrchr __ARGS((char_u *, int)); #ifdef DEBUGstatic void	regdump __ARGS((char_u *, regprog_T *));static char_u	*regprop __ARGS((char_u *));#endif #define NOT_MULTI	0#define MULTI_ONE	1#define MULTI_MULT	2/* * Return NOT_MULTI if c is not a "multi" operator. * Return MULTI_ONE if c is a single "multi" operator. * Return MULTI_MULT if c is a multi "multi" operator. */    static intre_multi_type(c)    int c;{    if (c == Magic('@') || c == Magic('=') || c == Magic('?'))	return MULTI_ONE;    if (c == Magic('*') || c == Magic('+') || c == Magic('{'))	return MULTI_MULT;    return NOT_MULTI;} /* * Flags to be passed up and down. */#define HASWIDTH	0x1	/* Known never to match null string. */#define SIMPLE		0x2	/* Simple enough to be STAR/PLUS operand. */#define SPSTART		0x4	/* Starts with * or +. */#define HASNL		0x8	/* Contains some \n. */#define HASLOOKBH	0x10	/* Contains "\@<=" or "\@<!". */#define WORST		0	/* Worst case. */ /* * When regcode is set to this value, code is not emitted and size is computed * instead. */#define JUST_CALC_SIZE	((char_u *) -1) static char_u		*reg_prev_sub = NULL; #if defined(EXITFREE) || defined(PROTO)    voidfree_regexp_stuff(){    vim_free(reg_prev_sub);}#endif /* * REGEXP_INRANGE contains all characters which are always special in a [] * range after '\'. * REGEXP_ABBR contains all characters which act as abbreviations after '\'. * These are: *  \n	- New line (NL). *  \r	- Carriage Return (CR). *  \t	- Tab (TAB). *  \e	- Escape (ESC). *  \b	- Backspace (Ctrl_H). *  \d  - Character code in decimal, eg \d123 *  \o	- Character code in octal, eg \o80 *  \x	- Character code in hex, eg \x4a *  \u	- Multibyte character code, eg \u20ac *  \U	- Long multibyte character code, eg \U12345678 */static char_u REGEXP_INRANGE[] = "]^-n\\";static char_u REGEXP_ABBR[] = "nrtebdoxuU"; static int	backslash_trans __ARGS((int c));static int	get_char_class __ARGS((char_u **pp));static int	get_equi_class __ARGS((char_u **pp));static void	reg_equi_class __ARGS((int c));static int	get_coll_element __ARGS((char_u **pp));static char_u	*skip_anyof __ARGS((char_u *p));static void	init_class_tab __ARGS((void)); /* * Translate '\x' to its control character, except "\n", which is Magic. */    static intbackslash_trans(c)    int		c;{    switch (c)    {	case 'r':   return CAR;	case 't':   return TAB;	case 'e':   return ESC;	case 'b':   return BS;    }    return c;} /* * Check for a character class name "[:name:]".  "pp" points to the '['. * Returns one of the CLASS_ items. CLASS_NONE means that no item was * recognized.  Otherwise "pp" is advanced to after the item. */    static intget_char_class(pp)    char_u	**pp;{    static const char *(class_names[]) =    {	"alnum:]",#define CLASS_ALNUM 0	"alpha:]",#define CLASS_ALPHA 1	"blank:]",#define CLASS_BLANK 2	"cntrl:]",#define CLASS_CNTRL 3	"digit:]",#define CLASS_DIGIT 4	"graph:]",#define CLASS_GRAPH 5	"lower:]",#define CLASS_LOWER 6	"print:]",#define CLASS_PRINT 7	"punct:]",#define CLASS_PUNCT 8	"space:]",#define CLASS_SPACE 9	"upper:]",#define CLASS_UPPER 10	"xdigit:]",#define CLASS_XDIGIT 11	"tab:]",#define CLASS_TAB 12	"return:]",#define CLASS_RETURN 13	"backspace:]",#define CLASS_BACKSPACE 14	"escape:]",#define CLASS_ESCAPE 15    };#define CLASS_NONE 99    int i;     if ((*pp)[1] == ':')    {	for (i = 0; i < sizeof(class_names) / sizeof(*class_names); ++i)	    if (STRNCMP(*pp + 2, class_names[i], STRLEN(class_names[i])) == 0)	    {		*pp += STRLEN(class_names[i]) + 2;		return i;	    }    }    return CLASS_NONE;} /* * Specific version of character class functions. * Using a table to keep this fast. */static short	class_tab[256]; #define	    RI_DIGIT	0x01#define	    RI_HEX	0x02#define	    RI_OCTAL	0x04

Lines 1–500 of 7142. Load more