regexp.c

从一个开源软件中摘取的正则表达式模块

/*-------------------------------------------------------------------------
 *
 * regexp.c
 *	  Postgres' interface to the regular expression package.
 *
 * Portions Copyright (c) 1996-2008, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  $PostgreSQL: pgsql/src/backend/utils/adt/regexp.c,v 1.78.2.1 2008/03/19 02:40:43 tgl Exp $
 *
 *		Alistair Crooks added the code for the regex caching
 *		agc - cached the regular expressions used - there's a good chance
 *		that we'll get a hit, so this saves a compile step for every
 *		attempted match. I haven't actually measured the speed improvement,
 *		but it `looks' a lot quicker visually when watching regression
 *		test output.
 *
 *		agc - incorporated Keith Bostic's Berkeley regex code into
 *		the tree for all ports. To distinguish this regex code from any that
 *		is existent on a platform, I've prepended the string "pg_" to
 *		the functions regcomp, regerror, regexec and regfree.
 *		Fixed a bug that was originally a typo by me, where `i' was used
 *		instead of `oldest' when compiling regular expressions - benign
 *		results mostly, although occasionally it bit you...
 *
 *-------------------------------------------------------------------------
 */
#include <stdlib.h>

#include "postgres.h"
#include "regex.h"
#include "pg_wchar.h"

/* GUC  默认的正则表达式选项*/
static int      regex_flavor = REG_ADVANCED; 
/*
 * We cache precompiled regular expressions using a "self organizing list"
 * structure, in which recently-used items tend to be near the front.
 * Whenever we use an entry, it's moved up to the front of the list.
 * Over time, an item's average position corresponds to its frequency of use.
 * 使用 “自己组织的列表”结构 来缓冲编译后的正则表达式。在结构里面最近使用的条目放在最前面。
 * 当我们使用一个条目后，他都会移到列表的前面。这样，一个条目的位置就和它出现的频率相关。
 *
 * When we first create an entry, it's inserted at the front of
 * the array, dropping the entry at the end of the array if necessary to
 * make room.  (This might seem to be weighting the new entry too heavily,
 * but if we insert new entries further back, we'll be unable to adjust to
 * a sudden shift in the query mix where we are presented with MAX_CACHED_RES
 * never-before-seen items used circularly.  We ought to be able to handle
 * that case, so we have to insert at the front.)
 * 当最初创建一个条目的时候，把它插入到数组的前面，如果空间不足，就把最后面的那个条目删除。
 *
 *
 * Knuth mentions a variant strategy in which a used item is moved up just
 * one place in the list.  Although he says this uses fewer comparisons on
 * average, it seems not to adapt very well to the situation where you have
 * both some reusable patterns and a steady stream of non-reusable patterns.
 * A reusable pattern that isn't used at least as often as non-reusable
 * patterns are seen will "fail to keep up" and will drop off the end of the
 * cache.  With move-to-front, a reusable pattern is guaranteed to stay in
 * the cache as long as it's used at least once in every MAX_CACHED_RES uses.
 * Knuth用到一个 ‘变量策略’ ，当一个条目被使用的时候，只向前移到一个位置。
 *
 */

/* this is the maximum number of cached regular expressions */
#ifndef MAX_CACHED_RES
#define MAX_CACHED_RES	32
#endif

/* this structure describes one cached regular expression ,用来缓冲正则表达式字符串 和 编译后的结构的结构体*/
typedef struct cached_re_str                       
{
	char   *cre_pat;		/*原始的正则表达式  original RE (not null terminated!) */
	int	cre_pat_len;		/*原始的正则表达式的字节长度。length of original RE, in bytes */
	int	cre_flags;		/*正则表达式选项，扩展。compile flags: extended,icase etc */
	 regex_t	cre_re;			/*保存编译后的正则表达式 the compiled regular expression */
} cached_re_str;

static int	num_res = 0;		/* # of cached re's 缓冲长度*/
static cached_re_str re_array[MAX_CACHED_RES];	/* 正则表达式的缓冲数组 */
static bool check_replace_text_has_escape_char(const char  *replace_text);
static char * replace_text_regexp(const char * src_text, regex_t *re, const char *replace_text, bool glob);
static char * appendStringInfoRegexpSubstr(char * str, const char *replace_text,
                                          regmatch_t *pmatch,
                                         const   char *start_ptr, int data_pos);




static size_t null_strlen(const char * x)
{
	return (x==NULL?0:strlen(x));
}

/*
 * RE_compile_and_cache - compile a RE, caching if possible
 * 正则表达式的编译和缓存。这个函数是对编译函数的一个包装，他把正则表达式转换成pg_wchar格式，并且缓冲了编译结果。
 *
 * Returns regex_t *
 *
 *	text_re --- the pattern, expressed as a TEXT object， 正则表达式的模式
 *	cflags --- compile options for the pattern            模式的编译选项
 *
 * 模式用数据库编码给出，我们在内部转化成pg_wchar
 * pg_mb2wchar_with_len(const char *from, pg_wchar *to, int len)
 * {
 *         return (*pg_wchar_table[DatabaseEncoding->encoding].mb2wchar_with_len) ((const unsigned char *) from, to, len);
 * }
 */
regex_t * RE_compile_and_cache(const char *re_val, int cflags)
{
	int			re_len = null_strlen(re_val); //获取正则表达式字符串的长度
	pg_wchar   		*pattern;				  //转化成pg_wchar类型的正则表达式
	int			pattern_len;				  //转化后的长度
	int			i;
	int			regcomp_result;				  //判断编译是否成功的结果
	cached_re_str		re_temp; 				  //临时的缓冲结果的结构,内含的cre_re是regex_t
	char			errMsg[100];

	/*	 * 从缓冲列表里面查找是否有匹配的。	 */
	for (i = 0; i < num_res; i++)
	{
		/*如果长度、编译标记和字符串都一样，则不用编译直接返回。*/
		if (re_array[i].cre_pat_len == re_len &&
			re_array[i].cre_flags == cflags &&
			memcmp(re_array[i].cre_pat, re_val, re_len) == 0)
		{
			/*
			 * Found a match; move it to front if not there already.
			 */
			if (i > 0)
			{
				re_temp = re_array[i];
				memmove(&re_array[1], &re_array[0], i * sizeof(cached_re_str));
				re_array[0] = re_temp;
			}

			return &re_array[0].cre_re;
		}
	}

	/*
	 * Couldn't find it, so try to compile the new RE.  To avoid leaking
	 * resources on failure, we build into the re_temp local.
	 */

	/* Convert pattern string to wide characters */
	//pattern = (pg_wchar *) palloc((re_len + 1) * sizeof(pg_wchar));       //把正则表达式转换成pg_wchar格式
	pattern = (pg_wchar *) malloc((re_len + 1) * sizeof(pg_wchar));       //用其他的内存处理函数来处理上面的内存分配
	if( pattern == NULL)
	{
		fprintf(stderr,"Memory alloc error!");
		return NULL;
	}

	/*pattern_len = pg_mb2wchar_with_len(re_val, pattern, re_len);函数删除*/
        pattern_len = pg_encoding_mb2wchar_with_len(GetDatabaseEncoding(), re_val,pattern,re_len);  /*杜英杰添加*/
	regcomp_result = pg_regcomp(&re_temp.cre_re, pattern, pattern_len, cflags); //编译正则表达式，结果存入te_temp.cre_re

	//pfree(pattern);   /*释放转化后的宽位模式字符串*/
	free(pattern);   /*替换分配的字符串*/
	pattern = NULL;

	if (regcomp_result != REG_OKAY)  //如果编译不成功
	{
		/* re didn't compile */
		pg_regerror(regcomp_result, &re_temp.cre_re, errMsg, sizeof(errMsg));
		fprintf(stderr,"invalid regular expression: %s", errMsg);
		return NULL ;
		/* duyingjie delete
		ereport(ERROR,
				(errcode(ERRCODE_INVALID_REGULAR_EXPRESSION),
				 errmsg("invalid regular expression: %s", errMsg)));
		*/
	}

	/*
	 * We use malloc/free for the cre_pat field because the storage has to
	 * persist across transactions, and because we want to get control back on
	 * out-of-memory.  The Max() is because some malloc implementations return
	 * NULL for malloc(0).
	 */
	re_temp.cre_pat = (char *)malloc(Max(re_len, 1));
	if (re_temp.cre_pat == NULL)
	{
		pg_regfree(&re_temp.cre_re);
		fprintf(stderr,"out of memory");
		return NULL;
		/*
		ereport(ERROR,
				(errcode(ERRCODE_OUT_OF_MEMORY),
				 errmsg("out of memory")));
		*/
	}
	/*把原始的正则表达式存入临时结果中的相应位置。并设置临时结果的其他值。*/
	memcpy(re_temp.cre_pat, re_val, re_len);
	re_temp.cre_pat_len = re_len;
	re_temp.cre_flags = cflags;

	/*
	 * Okay, we have a valid new item in re_temp; insert it into the storage
	 * array.  Discard last entry if needed.
	 */
	if (num_res >= MAX_CACHED_RES) /*如果长度大于最大缓冲长度*/
	{
		--num_res;
		Assert(num_res < MAX_CACHED_RES);
		pg_regfree(&re_array[num_res].cre_re); /*释放最后的那个编译后的结构体*/
		free(re_array[num_res].cre_pat);       /*释放保存的原始正则表达式*/
	}

	if (num_res > 0)  /**/
		memmove(&re_array[1], &re_array[0], num_res * sizeof(cached_re_str));

	re_array[0] = re_temp;
	num_res++;

	return &re_array[0].cre_re;  /*返回编译后的，放在缓冲区的结构体*/
}

/*
 * RE_wchar_execute - execute a RE on pg_wchar data
 * 执行正则表达式的匹配，被匹配的数据必须是pg_wchar 类型的字符串。如果匹配成功返回TRUE,否则返回FALSE
 *
 *	re --- 编译过的正则表达式结构体
 *	data --- 被匹配的数据the data to match against (need not be null-terminated)
 *	data_len --- 数据字符串的长度the length of the data string
 *	start_search -- the offset in the data to start searching
 *	nmatch, pmatch	--- 匹配函数使用的可选项 optional return area for match details
 *
 * Data is given as array of pg_wchar which is what Spencer's regex package
 * wants.
 */
bool RE_wchar_execute(regex_t *re, pg_wchar *data, int data_len, int start_search, int nmatch, regmatch_t *pmatch)
{
	int 		regexec_result; //保存原始匹配函数返回的结果
	char		errMsg[100];

	/* Perform RE match and return result */
	regexec_result = pg_regexec(re,
								data,
								data_len,
								start_search,
								NULL,	/* no details */
								nmatch,
								pmatch,
								0);

	if (regexec_result != REG_OKAY && regexec_result != REG_NOMATCH)
	{
		/* re failed??? */
		pg_regerror(regexec_result, re, errMsg, sizeof(errMsg));
		fprintf(stderr,"regular expression failed: %s\n", errMsg);
		/*duyingjie delete
		ereport(ERROR,
				(errcode(ERRCODE_INVALID_REGULAR_EXPRESSION),
				 errmsg("regular expression failed: %s", errMsg)));
		*/
	}

	return (regexec_result == REG_OKAY);
}

/*
 * RE_execute - execute a RE
 * 对上面匹配函数的进一步宝装，被匹配字符串不要求是pg_wchar格式不需要是一个
 *
 * Returns TRUE on match, FALSE on no match
 *
 *	re --- the compiled pattern as returned by RE_compile_and_cache
 *	dat --- the data to match against (need not be null-terminated)
 *	dat_len --- the length of the data string
 *	nmatch, pmatch	--- optional return area for match details
 *
 * Data is given in the database encoding.	We internally
 * convert to array of pg_wchar which is what Spencer's regex package wants.
 */
bool RE_execute(regex_t *re, const char *dat, int nmatch, regmatch_t *pmatch)
{
	pg_wchar  *data;
	int     dat_len = null_strlen(dat);
	int	data_len = 0;
	bool	match;

	/* Convert data string to wide characters */
	//data = (pg_wchar *) palloc((dat_len + 1) * sizeof(pg_wchar));
	data = (pg_wchar *) malloc((dat_len + 1) * sizeof(pg_wchar));
        if( data == NULL)
        {
                fprintf(stderr,"Memory alloc error!");
                return FALSE;
        }

	/*data_len = pg_mb2wchar_with_len(dat, data, dat_len);  这个函数废除*/
        data_len = pg_encoding_mb2wchar_with_len(GetDatabaseEncoding(), dat,data,dat_len);  /*杜英杰添加*/

	/* Perform RE match and return result */
	match = RE_wchar_execute(re, data, data_len, 0, nmatch, pmatch);

	//pfree(data);
	free(data);
	data = NULL;
	return match;
}

/*
 * RE_compile_and_execute - compile and execute a RE
 *
 * Returns TRUE on match, FALSE on no match
 *
 *	text_re --- the pattern, expressed as a TEXT object
 *	dat --- the data to match against (need not be null-terminated)
 *	dat_len --- the length of the data string
 *	cflags --- compile options for the pattern
 *	nmatch, pmatch	--- optional return area for match details
 *
 * Both pattern and data are given in the database encoding.  We internally
 * convert to array of pg_wchar which is what Spencer's regex package wants.
 */
/*bool RE_compile_and_execute(text *text_re, char *dat, int dat_len, int cflags, int nmatch, regmatch_t *pmatch)*/