| /programs/develop/tinypy/std_modules/re/init.c |
|---|
| 0,0 → 1,710 |
| /* |
| * regular expression module |
| * |
| * Important Note: do not support group name index |
| * |
| * $Id$ |
| */ |
| #include <stdio.h> |
| #include <assert.h> |
| #include "regexpr.c" |
| /* tinypy API to be use in this unit */ |
| extern tp_obj tp_data(TP,int magic,void *v); |
| extern tp_obj tp_object_new(TP); |
| extern tp_obj tp_object(TP); |
| extern tp_obj tp_method(TP,tp_obj self,tp_obj v(TP)); |
| extern tp_obj tp_string_copy(TP, const char *s, int n); |
| extern tp_obj tp_list(TP); |
| extern tp_obj tp_copy(TP); |
| /* last error message */ |
| static const char * LastError = NULL; |
| /* lower level regex object */ |
| typedef struct { |
| struct re_pattern_buffer re_patbuf; /* The compiled expression */ |
| struct re_registers re_regs; /* The registers from the last match */ |
| char re_fastmap[256]; /* Storage for fastmap */ |
| unsigned char *re_translate; /* String object for translate table */ |
| unsigned char *re_lastok; /* String object last matched/searched */ |
| /* supplementary */ |
| int re_errno; /* error num */ |
| int re_syntax; /* syntax */ |
| } regexobject; |
| /* local declarations */ |
| static regexobject* getre(TP, tp_obj rmobj); |
| static tp_obj match_obj_group(TP); |
| static tp_obj match_obj_groups(TP); |
| static tp_obj match_obj_start(TP); |
| static tp_obj match_obj_end(TP); |
| static tp_obj match_obj_span(TP); |
| /* |
| * helper function: return lower level regex object |
| * rmobj - regex or match object |
| */ |
| static regexobject * getre(TP, tp_obj rmobj) |
| { |
| tp_obj reobj_data = tp_get(tp, rmobj, tp_string("__data__")); |
| regexobject *re = NULL; |
| /* validate magic */ |
| if (reobj_data.data.magic != sizeof(regexobject)) { |
| LastError = "broken regex object"; |
| return (NULL); |
| } |
| re = (regexobject*)reobj_data.data.val; |
| assert(re); |
| return (re); |
| } |
| /* |
| * derive match object from regex object |
| */ |
| static tp_obj match_object(TP, tp_obj reobj) |
| { |
| tp_obj mo = tp_object(tp); /* match object */ |
| tp_obj redata; /* regex object data */ |
| tp_obj madata; /* match object data */ |
| regexobject *re = NULL; /* lower level regex object */ |
| redata = tp_get(tp, reobj, tp_string("__data__")); |
| re = (regexobject *)redata.data.val; |
| assert(re); |
| madata = tp_data(tp, (int)sizeof(regexobject), re); |
| tp_set(tp, mo, tp_string("group"), tp_method(tp, mo, match_obj_group)); |
| tp_set(tp, mo, tp_string("groups"), tp_method(tp, mo, match_obj_groups)); |
| tp_set(tp, mo, tp_string("start"), tp_method(tp, mo, match_obj_start)); |
| tp_set(tp, mo, tp_string("end"), tp_method(tp, mo, match_obj_end)); |
| tp_set(tp, mo, tp_string("span"), tp_method(tp, mo, match_obj_span)); |
| tp_set(tp, mo, tp_string("__data__"), madata); |
| return (mo); |
| } |
| /* |
| * FUNC: regexobj.search(str[,pos=0]) |
| * self - regex object |
| * str - string to be searched |
| * pos - optional starting offset |
| * |
| * RETURN: |
| * match object - when matched |
| * None - not matched |
| */ |
| static tp_obj regex_obj_search(TP) |
| { |
| tp_obj self = TP_OBJ(); /* regex object */ |
| tp_obj str = TP_STR(); |
| tp_obj pos = TP_DEFAULT(tp_number(0)); |
| tp_obj maobj; /* match object */ |
| regexobject *re = NULL; |
| int r = -2; /* -2 indicate exception */ |
| int range; |
| if (pos.number.val < 0 || pos.number.val > str.string.len) { |
| LastError = "search offset out of range"; |
| goto exception; |
| } |
| range = str.string.len - pos.number.val; |
| re = getre(tp, self); |
| re->re_lastok = NULL; |
| r = re_search(&re->re_patbuf, (unsigned char *)str.string.val, |
| str.string.len, pos.number.val, range, &re->re_regs); |
| /* cannot match pattern */ |
| if (r == -1) |
| goto notfind; |
| /* error occurred */ |
| if (r == -2) |
| goto exception; |
| /* matched */ |
| re->re_lastok = (unsigned char *)str.string.val; |
| /* match obj */ |
| maobj = match_object(tp, self); |
| return (maobj); |
| notfind: |
| re->re_lastok = NULL; |
| return (tp_None); |
| exception: |
| re->re_lastok = NULL; |
| tp_raise(tp_None, tp_string("regex search error")); |
| } |
| /* |
| * FUNC: regexobj.match(str[,pos=0]) |
| * self - regex object |
| * str - string to be matched |
| * pos - optional starting position |
| * |
| * RETURN: |
| * match object - when matched |
| * None - not matched |
| */ |
| static tp_obj regex_obj_match(TP) |
| { |
| tp_obj self = TP_OBJ(); /* regex object */ |
| tp_obj str = TP_STR(); |
| tp_obj pos = TP_DEFAULT(tp_number(0)); |
| tp_obj maobj; /* match object */ |
| regexobject *re = NULL; |
| int r = -2; /* -2 indicate exception */ |
| re = getre(tp, self); |
| re->re_lastok = NULL; |
| r = re_match(&re->re_patbuf, (unsigned char *)str.string.val, |
| str.string.len, pos.number.val, &re->re_regs); |
| /* cannot match pattern */ |
| if (r == -1) |
| goto nomatch; |
| /* error occurred */ |
| if (r == -2) |
| goto exception; |
| /* matched */ |
| re->re_lastok = (unsigned char *)str.string.val; |
| /* match obj */ |
| maobj = match_object(tp, self); |
| return (maobj); |
| nomatch: |
| re->re_lastok = NULL; |
| return (tp_None); |
| exception: |
| re->re_lastok = NULL; |
| tp_raise(tp_None, tp_string("regex match error")); |
| } |
| /* |
| * regex object split() |
| * self - regex object |
| * restr - regex string |
| * maxsplit - max split field, default 0, mean no limit |
| */ |
| static tp_obj regex_obj_split(TP) |
| { |
| tp_obj self = TP_OBJ(); /* regex object */ |
| tp_obj restr = TP_OBJ(); /* string */ |
| tp_obj maxsplit = TP_DEFAULT(tp_number(0)); |
| tp_obj maobj; /* match object */ |
| regexobject *re = NULL; /* lower level regex object */ |
| tp_obj result = tp_list(tp); |
| tp_obj grpstr; /* group string */ |
| int slen; /* string length */ |
| int srchloc; /* search location */ |
| /* maxsplit == 0 means no limit */ |
| if ((int)maxsplit.number.val == 0) |
| maxsplit.number.val = RE_NREGS; |
| assert(maxsplit.number.val > 0); |
| srchloc = 0; |
| slen = strlen((char *)restr.string.val); |
| do { |
| /* generate a temp match object */ |
| tp_params_v(tp, 3, self, restr, tp_number(srchloc)); |
| maobj = regex_obj_search(tp); |
| if (!tp_bool(tp, maobj)) |
| break; |
| re = getre(tp, maobj); |
| if (re->re_lastok == NULL) { |
| tp_raise(tp_None, tp_string("no match for split()")); |
| } |
| /* extract fields */ |
| if ((int)maxsplit.number.val > 0) { |
| int start = re->re_regs.start[0]; |
| int end = re->re_regs.end[0]; |
| /*printf("%s:start(%d),end(%d)\n", __func__, start, end);*/ |
| if (start < 0 || end < 0) |
| break; |
| grpstr = tp_string_copy(tp, |
| (const char *)re->re_lastok + srchloc, start - srchloc); |
| if (tp_bool(tp, grpstr)) { |
| tp_set(tp, result, tp_None, grpstr); |
| maxsplit.number.val--; |
| } |
| srchloc = end; |
| } |
| } while (srchloc < slen && (int)maxsplit.number.val > 0); |
| /* collect remaining string, if necessary */ |
| if (srchloc < slen) { |
| grpstr = tp_string_copy(tp, |
| (const char *)restr.string.val + srchloc, slen - srchloc); |
| if (tp_bool(tp, grpstr)) |
| tp_set(tp, result, tp_None, grpstr); |
| } |
| return (result); |
| } |
| /* |
| * regex object findall() |
| * self - regex object |
| * restr - regex string |
| * pos - starting position, default 0 |
| */ |
| static tp_obj regex_obj_findall(TP) |
| { |
| tp_obj self = TP_OBJ(); /* regex object */ |
| tp_obj restr = TP_OBJ(); /* string */ |
| tp_obj pos = TP_DEFAULT(tp_number(0)); |
| tp_obj maobj; /* match object */ |
| regexobject *re = NULL; /* lower level regex object */ |
| tp_obj result = tp_list(tp); |
| tp_obj grpstr; /* group string */ |
| int slen; /* string length */ |
| int srchloc; /* search location */ |
| srchloc = (int)pos.number.val; |
| slen = strlen((char *)restr.string.val); |
| if (srchloc < 0 || srchloc >= slen) |
| tp_raise(tp_None, tp_string("starting position out of range")); |
| do { |
| /* generate a temp match object */ |
| tp_params_v(tp, 3, self, restr, tp_number(srchloc)); |
| maobj = regex_obj_search(tp); |
| if (!tp_bool(tp, maobj)) |
| break; |
| re = getre(tp, maobj); |
| if (re->re_lastok == NULL) { |
| tp_raise(tp_None, tp_string("no match for findall()")); |
| } |
| /* extract fields */ |
| if (srchloc < slen) { |
| int start = re->re_regs.start[0]; |
| int end = re->re_regs.end[0]; |
| /*printf("%s:start(%d),end(%d)\n", __func__, start, end);*/ |
| if (start < 0 || end < 0) |
| break; |
| grpstr = tp_string_copy(tp, |
| (const char *)re->re_lastok + start, end - start); |
| if (tp_bool(tp, grpstr)) { |
| tp_set(tp, result, tp_None, grpstr); |
| } |
| srchloc = end; |
| } |
| } while (srchloc < slen); |
| return (result); |
| } |
| /* |
| * FUNC: matchobj.group([group1, ...]) |
| * self - match object |
| * args - optional group indices, default 0 |
| * |
| * return specified group. |
| */ |
| static tp_obj match_obj_group(TP) |
| { |
| tp_obj self = TP_OBJ(); /* match object */ |
| tp_obj grpidx; /* a group index */ |
| regexobject *re = NULL; |
| int indices[RE_NREGS]; |
| int start; |
| int end; |
| int i; |
| int single = 0; /* single group index? */ |
| tp_obj result; |
| /* get lower level regex object representation */ |
| re = getre(tp, self); |
| if (re->re_lastok == NULL) |
| tp_raise(tp_None, |
| tp_string("group() only valid after successful match/search")); |
| for (i = 0; i < RE_NREGS; i++) |
| indices[i] = -1; |
| /* |
| * if no group index provided, supply default group index 0; else |
| * fill in indices[] with provided group index list. |
| */ |
| if (tp->params.list.val->len == 0) { |
| indices[0] = 0; |
| single = 1; |
| } else if (tp->params.list.val->len == 1) { |
| indices[0] = (int)TP_NUM(); |
| single = 1; |
| } else { |
| i = 0; |
| TP_LOOP(grpidx) |
| if (grpidx.number.val < 0 || grpidx.number.val > RE_NREGS) |
| tp_raise(tp_None, tp_string("group() grpidx out of range")); |
| indices[i++] = (int)grpidx.number.val; |
| TP_END |
| } |
| /* generate result string list */ |
| result = tp_list(tp); |
| for (i = 0; i < RE_NREGS && indices[i] >= 0; i++) { |
| tp_obj grpstr; |
| start = re->re_regs.start[indices[i]]; |
| end = re->re_regs.end[indices[i]]; |
| if (start < 0 || end < 0) { |
| grpstr = tp_None; |
| } else { |
| grpstr = tp_string_copy(tp, (const char *)re->re_lastok + start, |
| end - start); |
| } |
| tp_set(tp, result, tp_None, grpstr); |
| } |
| return (single ? tp_get(tp, result, tp_number(0)) : result); |
| } |
| /* |
| * FUNC: matchobj.groups() |
| * self - match object. |
| * return all groups. |
| * Note: CPython allow a 'default' argument, but we disallow it. |
| */ |
| static tp_obj match_obj_groups(TP) |
| { |
| tp_obj self = TP_OBJ(); /* match object */ |
| regexobject *re = NULL; |
| int start; |
| int end; |
| int i; |
| tp_obj result = tp_list(tp); |
| re = getre(tp, self); |
| if (re->re_lastok == NULL) { |
| tp_raise(tp_None, |
| tp_string("groups() only valid after successful match/search")); |
| } |
| for (i = 1; i < RE_NREGS; i++) { |
| start = re->re_regs.start[i]; |
| end = re->re_regs.end[i]; |
| if (start < 0 || end < 0) |
| break; |
| tp_obj grpstr = tp_string_copy(tp, |
| (const char *)re->re_lastok + start, end - start); |
| if (tp_bool(tp, grpstr)) |
| tp_set(tp, result, tp_None, grpstr); |
| } |
| return (result); |
| } |
| /* |
| * FUNC: matchobj.start([group]) |
| * self - match object |
| * group - group index |
| * return starting position of matched 'group' substring. |
| */ |
| static tp_obj match_obj_start(TP) |
| { |
| tp_obj self = TP_OBJ(); /* match object */ |
| tp_obj group = TP_DEFAULT(tp_number(0)); /* group */ |
| regexobject *re = NULL; |
| int start; |
| re = getre(tp, self); |
| if (re->re_lastok == NULL) { |
| tp_raise(tp_None, |
| tp_string("start() only valid after successful match/search")); |
| } |
| if (group.number.val < 0 || group.number.val > RE_NREGS) |
| tp_raise(tp_None, tp_string("IndexError: group index out of range")); |
| start = re->re_regs.start[(int)group.number.val]; |
| return (tp_number(start)); |
| } |
| /* |
| * FUNC: matchobj.end([group]) |
| * self - match object |
| * group - group index |
| * return ending position of matched 'group' substring. |
| */ |
| static tp_obj match_obj_end(TP) |
| { |
| tp_obj self = TP_OBJ(); /* match object */ |
| tp_obj group = TP_DEFAULT(tp_number(0)); /* group */ |
| regexobject *re = NULL; |
| int end; |
| re = getre(tp, self); |
| if (re->re_lastok == NULL) { |
| tp_raise(tp_None, |
| tp_string("end() only valid after successful match/search")); |
| } |
| if (group.number.val < 0 || group.number.val > RE_NREGS) |
| tp_raise(tp_None, tp_string("IndexError: group index out of range")); |
| end = re->re_regs.end[(int)group.number.val]; |
| return (tp_number(end)); |
| } |
| /* |
| * FUNC: matchobj.span([group]) |
| * self - match object |
| * group - group index |
| * return [start,end] position pair of matched 'group' substring. |
| */ |
| static tp_obj match_obj_span(TP) |
| { |
| tp_obj self = TP_OBJ(); /* match object */ |
| tp_obj group = TP_DEFAULT(tp_number(0)); /* group */ |
| regexobject *re = NULL; |
| int start; |
| int end; |
| tp_obj result; |
| re = getre(tp, self); |
| if (re->re_lastok == NULL) { |
| tp_raise(tp_None, |
| tp_string("span() only valid after successful match/search")); |
| } |
| if (group.number.val < 0 || group.number.val > RE_NREGS) |
| tp_raise(tp_None, tp_string("IndexError: group index out of range")); |
| start = re->re_regs.start[(int)group.number.val]; |
| end = re->re_regs.end[(int)group.number.val]; |
| result = tp_list(tp); |
| tp_set(tp, result, tp_None, tp_number(start)); |
| tp_set(tp, result, tp_None, tp_number(end)); |
| return (result); |
| } |
| /* |
| * compile out a re object |
| * repat - regex pattern |
| * resyn - regex syntax |
| */ |
| static tp_obj regex_compile(TP) |
| { |
| char *error = NULL; |
| char const *pat = NULL; |
| int size = 0; |
| tp_obj reobj_data; |
| tp_obj repat = TP_TYPE(TP_STRING); /* pattern */ |
| tp_obj resyn = TP_DEFAULT(tp_number(RE_SYNTAX_EMACS)); /* syntax */ |
| tp_obj reobj; /* regex object */ |
| regexobject *re; |
| /* |
| * create regex object, its parent is builtin 'object' |
| */ |
| reobj = tp_object(tp); |
| re = (regexobject *)malloc(sizeof(regexobject)); |
| if (!re) { |
| error = "malloc lower level regex object failed"; |
| goto finally; |
| } |
| re->re_patbuf.buffer = NULL; |
| re->re_patbuf.allocated = 0; |
| re->re_patbuf.fastmap = (unsigned char *)re->re_fastmap; |
| re->re_patbuf.translate = NULL; |
| re->re_translate = NULL; |
| re->re_lastok = NULL; |
| re->re_errno = 0; |
| re->re_syntax = (int)resyn.number.val; |
| pat = repat.string.val; |
| size = repat.string.len; |
| error = re_compile_pattern((unsigned char *)pat, size, &re->re_patbuf); |
| if (error != NULL) { |
| LastError = error; |
| goto finally; |
| } |
| /* regexobject's size as magic */ |
| reobj_data = tp_data(tp, (int)sizeof(regexobject), re); |
| /* |
| * bind to regex object |
| */ |
| tp_set(tp, reobj, tp_string("search"), |
| tp_method(tp, reobj, regex_obj_search)); |
| tp_set(tp, reobj, tp_string("match"), |
| tp_method(tp, reobj, regex_obj_match)); |
| tp_set(tp, reobj, tp_string("split"), |
| tp_method(tp, reobj, regex_obj_split)); |
| tp_set(tp, reobj, tp_string("findall"), |
| tp_method(tp, reobj, regex_obj_findall)); |
| tp_set(tp, reobj, tp_string("__data__"), reobj_data); |
| tp_set(tp, reobj, tp_string("__name__"), |
| tp_string("regular expression object")); |
| tp_set(tp, reobj, tp_string("__doc__"), tp_string( |
| "regular expression object, support methods:\n" |
| "search(str[,pos=0])-search 'str' from 'pos'\n" |
| "match(str[,pos=0]) -match 'str' from 'pos'\n" |
| )); |
| return (reobj); |
| finally: |
| tp_raise(tp_None, tp_string(error)); |
| } |
| /* |
| * module level search() |
| */ |
| static tp_obj regex_search(TP) |
| { |
| tp_obj repat = TP_OBJ(); /* pattern */ |
| tp_obj restr = TP_OBJ(); /* string */ |
| tp_obj resyn = TP_DEFAULT(tp_number(RE_SYNTAX_EMACS)); |
| tp_obj reobj; /* regex object */ |
| tp_obj maobj; /* match object */ |
| /* compile out regex object */ |
| tp_params_v(tp, 2, repat, resyn); |
| reobj = regex_compile(tp); |
| /* call r.search() */ |
| tp_params_v(tp, 3, reobj, restr, tp_number(0)); |
| maobj = regex_obj_search(tp); |
| return (maobj); |
| } |
| /* |
| * module level match() |
| */ |
| static tp_obj regex_match(TP) |
| { |
| tp_obj repat = TP_OBJ(); /* pattern */ |
| tp_obj restr = TP_OBJ(); /* string */ |
| tp_obj resyn = TP_DEFAULT(tp_number(RE_SYNTAX_EMACS)); |
| tp_obj reobj; /* regex object */ |
| tp_obj maobj; /* match object */ |
| /* compile out regex object */ |
| tp_params_v(tp, 2, repat, resyn); |
| reobj = regex_compile(tp); |
| /* call r.search() */ |
| tp_params_v(tp, 3, reobj, restr, tp_number(0)); |
| maobj = regex_obj_match(tp); |
| return (maobj); |
| } |
| /* |
| * module level split() |
| * repat - regex pattern |
| * restr - regex string |
| * maxsplit - max split field, default 0, mean no limit |
| */ |
| static tp_obj regex_split(TP) |
| { |
| tp_obj repat = TP_OBJ(); /* pattern */ |
| tp_obj restr = TP_OBJ(); /* string */ |
| tp_obj maxsplit = TP_DEFAULT(tp_number(0)); |
| tp_obj reobj; /* regex object */ |
| /* generate a temp regex object */ |
| tp_params_v(tp, 2, repat, tp_number(RE_SYNTAX_EMACS)); |
| reobj = regex_compile(tp); |
| tp_params_v(tp, 3, reobj, restr, maxsplit); |
| return regex_obj_split(tp); |
| } |
| /* |
| * module level findall() |
| * repat - regex pattern |
| * restr - regex string |
| * resyn - regex syntax, optional, default RE_SYNTAX_EMAC |
| */ |
| static tp_obj regex_findall(TP) |
| { |
| tp_obj repat = TP_OBJ(); /* pattern */ |
| tp_obj restr = TP_OBJ(); /* string */ |
| tp_obj resyn = TP_DEFAULT(tp_number(RE_SYNTAX_EMACS)); |
| tp_obj reobj; /* regex object */ |
| /* generate a temp regex object */ |
| tp_params_v(tp, 2, repat, resyn); |
| reobj = regex_compile(tp); |
| tp_params_v(tp, 2, reobj, restr); |
| return regex_obj_findall(tp); |
| } |
| /* |
| * re mod can only support 'set_syntax', 'get_syntax', and 'compile' functions, |
| * 'compile' function will return a 'reobj', and this 'reobj' will support |
| * methods 'search', 'match', 'group', 'groupall', el al. |
| */ |
| void re_init(TP) |
| { |
| /* |
| * module dict for re |
| */ |
| tp_obj re_mod = tp_dict(tp); |
| /* |
| * bind to re module |
| */ |
| tp_set(tp, re_mod, tp_string("compile"), tp_fnc(tp, regex_compile)); |
| tp_set(tp, re_mod, tp_string("search"), tp_fnc(tp, regex_search)); |
| tp_set(tp, re_mod, tp_string("match"), tp_fnc(tp, regex_match)); |
| tp_set(tp, re_mod, tp_string("split"), tp_fnc(tp, regex_split)); |
| tp_set(tp, re_mod, tp_string("findall"), tp_fnc(tp, regex_findall)); |
| tp_set(tp, re_mod, tp_string("AWK_SYNTAX"), tp_number(RE_SYNTAX_AWK)); |
| tp_set(tp, re_mod, tp_string("EGREP_SYNTAX"), tp_number(RE_SYNTAX_EGREP)); |
| tp_set(tp, re_mod, tp_string("GREP_SYNTAX"), tp_number(RE_SYNTAX_GREP)); |
| tp_set(tp, re_mod, tp_string("EMACS_SYNTAX"), tp_number(RE_SYNTAX_EMACS)); |
| /* |
| * bind special attibutes to re module |
| */ |
| tp_set(tp, re_mod, tp_string("__name__"), |
| tp_string("regular expression module")); |
| tp_set(tp, re_mod, tp_string("__file__"), tp_string(__FILE__)); |
| tp_set(tp, re_mod, tp_string("__doc__"), |
| tp_string("simple regular express implementation")); |
| /* |
| * bind regex module to tinypy modules[] |
| */ |
| tp_set(tp, tp->modules, tp_string("re"), re_mod); |
| } |
| /programs/develop/tinypy/std_modules/re/regexpr.c |
|---|
| 0,0 → 1,2125 |
| /* |
| * to eliminate dependence on CPython, I stripped out |
| * some CPython error handling function calls. |
| */ |
| /* regexpr.c |
| * |
| * Author: Tatu Ylonen <ylo@ngs.fi> |
| * |
| * Copyright (c) 1991 Tatu Ylonen, Espoo, Finland |
| * |
| * Permission to use, copy, modify, distribute, and sell this software |
| * and its documentation for any purpose is hereby granted without |
| * fee, provided that the above copyright notice appear in all copies. |
| * This software is provided "as is" without express or implied |
| * warranty. |
| * |
| * Created: Thu Sep 26 17:14:05 1991 ylo |
| * Last modified: Mon Nov 4 17:06:48 1991 ylo |
| * Ported to Think C: 19 Jan 1992 guido@cwi.nl |
| * |
| * This code draws many ideas from the regular expression packages by |
| * Henry Spencer of the University of Toronto and Richard Stallman of |
| * the Free Software Foundation. |
| * |
| * Emacs-specific code and syntax table code is almost directly borrowed |
| * from GNU regexp. |
| * |
| * Bugs fixed and lots of reorganization by Jeffrey C. Ollie, April |
| * 1997 Thanks for bug reports and ideas from Andrew Kuchling, Tim |
| * Peters, Guido van Rossum, Ka-Ping Yee, Sjoerd Mullender, and |
| * probably one or two others that I'm forgetting. |
| * |
| * $Id$ */ |
| #include <stdlib.h> |
| #include <string.h> |
| #include "regexpr.h" |
| #include "tinypy.h" |
| /* The original code blithely assumed that sizeof(short) == 2. Not |
| * always true. Original instances of "(short)x" were replaced by |
| * SHORT(x), where SHORT is #defined below. */ |
| #define SHORT(x) ((x) & 0x8000 ? (x) - 0x10000 : (x)) |
| /* The stack implementation is taken from an idea by Andrew Kuchling. |
| * It's a doubly linked list of arrays. The advantages of this over a |
| * simple linked list are that the number of mallocs required are |
| * reduced. It also makes it possible to statically allocate enough |
| * space so that small patterns don't ever need to call malloc. |
| * |
| * The advantages over a single array is that is periodically |
| * realloced when more space is needed is that we avoid ever copying |
| * the stack. */ |
| /* item_t is the basic stack element. Defined as a union of |
| * structures so that both registers, failure points, and counters can |
| * be pushed/popped from the stack. There's nothing built into the |
| * item to keep track of whether a certain stack item is a register, a |
| * failure point, or a counter. */ |
| typedef union item_t |
| { |
| struct |
| { |
| int num; |
| int level; |
| unsigned char *start; |
| unsigned char *end; |
| } reg; |
| struct |
| { |
| int count; |
| int level; |
| int phantom; |
| unsigned char *code; |
| unsigned char *text; |
| } fail; |
| struct |
| { |
| int num; |
| int level; |
| int count; |
| } cntr; |
| } item_t; |
| #define STACK_PAGE_SIZE 256 |
| #define NUM_REGISTERS 256 |
| /* A 'page' of stack items. */ |
| typedef struct item_page_t |
| { |
| item_t items[STACK_PAGE_SIZE]; |
| struct item_page_t *prev; |
| struct item_page_t *next; |
| } item_page_t; |
| typedef struct match_state |
| { |
| /* The number of registers that have been pushed onto the stack |
| * since the last failure point. */ |
| int count; |
| /* Used to control when registers need to be pushed onto the |
| * stack. */ |
| int level; |
| /* The number of failure points on the stack. */ |
| int point; |
| /* Storage for the registers. Each register consists of two |
| * pointers to characters. So register N is represented as |
| * start[N] and end[N]. The pointers must be converted to |
| * offsets from the beginning of the string before returning the |
| * registers to the calling program. */ |
| unsigned char *start[NUM_REGISTERS]; |
| unsigned char *end[NUM_REGISTERS]; |
| /* Keeps track of whether a register has changed recently. */ |
| int changed[NUM_REGISTERS]; |
| /* Structure to encapsulate the stack. */ |
| struct |
| { |
| /* index into the current page. If index == 0 and you need |
| * to pop an item, move to the previous page and set index |
| * = STACK_PAGE_SIZE - 1. Otherwise decrement index to |
| * push a page. If index == STACK_PAGE_SIZE and you need |
| * to push a page move to the next page and set index = |
| * 0. If there is no new next page, allocate a new page |
| * and link it in. Otherwise, increment index to push a |
| * page. */ |
| int index; |
| item_page_t *current; /* Pointer to the current page. */ |
| item_page_t first; /* First page is statically allocated. */ |
| } stack; |
| } match_state; |
| /* Initialize a state object */ |
| /* #define NEW_STATE(state) \ */ |
| /* memset(&state, 0, (void *)(&state.stack) - (void *)(&state)); \ */ |
| /* state.stack.current = &state.stack.first; \ */ |
| /* state.stack.first.prev = NULL; \ */ |
| /* state.stack.first.next = NULL; \ */ |
| /* state.stack.index = 0; \ */ |
| /* state.level = 1 */ |
| #define NEW_STATE(state, nregs) \ |
| { \ |
| int i; \ |
| for (i = 0; i < nregs; i++) \ |
| { \ |
| state.start[i] = NULL; \ |
| state.end[i] = NULL; \ |
| state.changed[i] = 0; \ |
| } \ |
| state.stack.current = &state.stack.first; \ |
| state.stack.first.prev = NULL; \ |
| state.stack.first.next = NULL; \ |
| state.stack.index = 0; \ |
| state.level = 1; \ |
| state.count = 0; \ |
| state.level = 0; \ |
| state.point = 0; \ |
| } |
| /* Free any memory that might have been malloc'd */ |
| #define FREE_STATE(state) \ |
| while(state.stack.first.next != NULL) \ |
| { \ |
| state.stack.current = state.stack.first.next; \ |
| state.stack.first.next = state.stack.current->next; \ |
| free(state.stack.current); \ |
| } |
| /* Discard the top 'count' stack items. */ |
| #define STACK_DISCARD(stack, count, on_error) \ |
| stack.index -= count; \ |
| while (stack.index < 0) \ |
| { \ |
| if (stack.current->prev == NULL) \ |
| on_error; \ |
| stack.current = stack.current->prev; \ |
| stack.index += STACK_PAGE_SIZE; \ |
| } |
| /* Store a pointer to the previous item on the stack. Used to pop an |
| * item off of the stack. */ |
| #define STACK_PREV(stack, top, on_error) \ |
| if (stack.index == 0) \ |
| { \ |
| if (stack.current->prev == NULL) \ |
| on_error; \ |
| stack.current = stack.current->prev; \ |
| stack.index = STACK_PAGE_SIZE - 1; \ |
| } \ |
| else \ |
| { \ |
| stack.index--; \ |
| } \ |
| top = &(stack.current->items[stack.index]) |
| /* Store a pointer to the next item on the stack. Used to push an item |
| * on to the stack. */ |
| #define STACK_NEXT(stack, top, on_error) \ |
| if (stack.index == STACK_PAGE_SIZE) \ |
| { \ |
| if (stack.current->next == NULL) \ |
| { \ |
| stack.current->next = (item_page_t *)malloc(sizeof(item_page_t)); \ |
| if (stack.current->next == NULL) \ |
| on_error; \ |
| stack.current->next->prev = stack.current; \ |
| stack.current->next->next = NULL; \ |
| } \ |
| stack.current = stack.current->next; \ |
| stack.index = 0; \ |
| } \ |
| top = &(stack.current->items[stack.index++]) |
| /* Store a pointer to the item that is 'count' items back in the |
| * stack. STACK_BACK(stack, top, 1, on_error) is equivalent to |
| * STACK_TOP(stack, top, on_error). */ |
| #define STACK_BACK(stack, top, count, on_error) \ |
| { \ |
| int index; \ |
| item_page_t *current; \ |
| current = stack.current; \ |
| index = stack.index - (count); \ |
| while (index < 0) \ |
| { \ |
| if (current->prev == NULL) \ |
| on_error; \ |
| current = current->prev; \ |
| index += STACK_PAGE_SIZE; \ |
| } \ |
| top = &(current->items[index]); \ |
| } |
| /* Store a pointer to the top item on the stack. Execute the |
| * 'on_error' code if there are no items on the stack. */ |
| #define STACK_TOP(stack, top, on_error) \ |
| if (stack.index == 0) \ |
| { \ |
| if (stack.current->prev == NULL) \ |
| on_error; \ |
| top = &(stack.current->prev->items[STACK_PAGE_SIZE - 1]); \ |
| } \ |
| else \ |
| { \ |
| top = &(stack.current->items[stack.index - 1]); \ |
| } |
| /* Test to see if the stack is empty */ |
| #define STACK_EMPTY(stack) ((stack.index == 0) && \ |
| (stack.current->prev == NULL)) |
| /* Return the start of register 'reg' */ |
| #define GET_REG_START(state, reg) (state.start[reg]) |
| /* Return the end of register 'reg' */ |
| #define GET_REG_END(state, reg) (state.end[reg]) |
| /* Set the start of register 'reg'. If the state of the register needs |
| * saving, push it on the stack. */ |
| #define SET_REG_START(state, reg, text, on_error) \ |
| if(state.changed[reg] < state.level) \ |
| { \ |
| item_t *item; \ |
| STACK_NEXT(state.stack, item, on_error); \ |
| item->reg.num = reg; \ |
| item->reg.start = state.start[reg]; \ |
| item->reg.end = state.end[reg]; \ |
| item->reg.level = state.changed[reg]; \ |
| state.changed[reg] = state.level; \ |
| state.count++; \ |
| } \ |
| state.start[reg] = text |
| /* Set the end of register 'reg'. If the state of the register needs |
| * saving, push it on the stack. */ |
| #define SET_REG_END(state, reg, text, on_error) \ |
| if(state.changed[reg] < state.level) \ |
| { \ |
| item_t *item; \ |
| STACK_NEXT(state.stack, item, on_error); \ |
| item->reg.num = reg; \ |
| item->reg.start = state.start[reg]; \ |
| item->reg.end = state.end[reg]; \ |
| item->reg.level = state.changed[reg]; \ |
| state.changed[reg] = state.level; \ |
| state.count++; \ |
| } \ |
| state.end[reg] = text |
| #define PUSH_FAILURE(state, xcode, xtext, on_error) \ |
| { \ |
| item_t *item; \ |
| STACK_NEXT(state.stack, item, on_error); \ |
| item->fail.code = xcode; \ |
| item->fail.text = xtext; \ |
| item->fail.count = state.count; \ |
| item->fail.level = state.level; \ |
| item->fail.phantom = 0; \ |
| state.count = 0; \ |
| state.level++; \ |
| state.point++; \ |
| } |
| /* Update the last failure point with a new position in the text. */ |
| #define UPDATE_FAILURE(state, xtext, on_error) \ |
| { \ |
| item_t *item; \ |
| STACK_BACK(state.stack, item, state.count + 1, on_error); \ |
| if (!item->fail.phantom) \ |
| { \ |
| item_t *item2; \ |
| STACK_NEXT(state.stack, item2, on_error); \ |
| item2->fail.code = item->fail.code; \ |
| item2->fail.text = xtext; \ |
| item2->fail.count = state.count; \ |
| item2->fail.level = state.level; \ |
| item2->fail.phantom = 1; \ |
| state.count = 0; \ |
| state.level++; \ |
| state.point++; \ |
| } \ |
| else \ |
| { \ |
| STACK_DISCARD(state.stack, state.count, on_error); \ |
| STACK_TOP(state.stack, item, on_error); \ |
| item->fail.text = xtext; \ |
| state.count = 0; \ |
| state.level++; \ |
| } \ |
| } |
| #define POP_FAILURE(state, xcode, xtext, on_empty, on_error) \ |
| { \ |
| item_t *item; \ |
| do \ |
| { \ |
| while(state.count > 0) \ |
| { \ |
| STACK_PREV(state.stack, item, on_error); \ |
| state.start[item->reg.num] = item->reg.start; \ |
| state.end[item->reg.num] = item->reg.end; \ |
| state.changed[item->reg.num] = item->reg.level; \ |
| state.count--; \ |
| } \ |
| STACK_PREV(state.stack, item, on_empty); \ |
| xcode = item->fail.code; \ |
| xtext = item->fail.text; \ |
| state.count = item->fail.count; \ |
| state.level = item->fail.level; \ |
| state.point--; \ |
| } \ |
| while (item->fail.text == NULL); \ |
| } |
| enum regexp_compiled_ops /* opcodes for compiled regexp */ |
| { |
| Cend, /* end of pattern reached */ |
| Cbol, /* beginning of line */ |
| Ceol, /* end of line */ |
| Cset, /* character set. Followed by 32 bytes of set. */ |
| Cexact, /* followed by a byte to match */ |
| Canychar, /* matches any character except newline */ |
| Cstart_memory, /* set register start addr (followed by reg number) */ |
| Cend_memory, /* set register end addr (followed by reg number) */ |
| Cmatch_memory, /* match a duplicate of reg contents (regnum follows)*/ |
| Cjump, /* followed by two bytes (lsb,msb) of displacement. */ |
| Cstar_jump, /* will change to jump/update_failure_jump at runtime */ |
| Cfailure_jump, /* jump to addr on failure */ |
| Cupdate_failure_jump, /* update topmost failure point and jump */ |
| Cdummy_failure_jump, /* push a dummy failure point and jump */ |
| Cbegbuf, /* match at beginning of buffer */ |
| Cendbuf, /* match at end of buffer */ |
| Cwordbeg, /* match at beginning of word */ |
| Cwordend, /* match at end of word */ |
| Cwordbound, /* match if at word boundary */ |
| Cnotwordbound, /* match if not at word boundary */ |
| Csyntaxspec, /* matches syntax code (1 byte follows) */ |
| Cnotsyntaxspec, /* matches if syntax code does not match (1 byte follows) */ |
| Crepeat1 |
| }; |
| enum regexp_syntax_op /* syntax codes for plain and quoted characters */ |
| { |
| Rend, /* special code for end of regexp */ |
| Rnormal, /* normal character */ |
| Ranychar, /* any character except newline */ |
| Rquote, /* the quote character */ |
| Rbol, /* match beginning of line */ |
| Reol, /* match end of line */ |
| Roptional, /* match preceding expression optionally */ |
| Rstar, /* match preceding expr zero or more times */ |
| Rplus, /* match preceding expr one or more times */ |
| Ror, /* match either of alternatives */ |
| Ropenpar, /* opening parenthesis */ |
| Rclosepar, /* closing parenthesis */ |
| Rmemory, /* match memory register */ |
| Rextended_memory, /* \vnn to match registers 10-99 */ |
| Ropenset, /* open set. Internal syntax hard-coded below. */ |
| /* the following are gnu extensions to "normal" regexp syntax */ |
| Rbegbuf, /* beginning of buffer */ |
| Rendbuf, /* end of buffer */ |
| Rwordchar, /* word character */ |
| Rnotwordchar, /* not word character */ |
| Rwordbeg, /* beginning of word */ |
| Rwordend, /* end of word */ |
| Rwordbound, /* word bound */ |
| Rnotwordbound, /* not word bound */ |
| Rnum_ops |
| }; |
| /* customized errno */ |
| int re_errno = TP_RE_NOERR; |
| static int re_compile_initialized = 0; |
| static int regexp_syntax = 0; |
| int re_syntax = 0; /* Exported copy of regexp_syntax */ |
| static unsigned char regexp_plain_ops[256]; |
| static unsigned char regexp_quoted_ops[256]; |
| static unsigned char regexp_precedences[Rnum_ops]; |
| static int regexp_context_indep_ops; |
| static int regexp_ansi_sequences; |
| #define NUM_LEVELS 5 /* number of precedence levels in use */ |
| #define MAX_NESTING 100 /* max nesting level of operators */ |
| #define SYNTAX(ch) re_syntax_table[(unsigned char)(ch)] |
| unsigned char re_syntax_table[256]; |
| int re_err_occurred(void) |
| { |
| if (re_errno == TP_RE_NOERR) |
| return (0); |
| return (1); |
| } |
| void re_compile_initialize(void) |
| { |
| int a; |
| static int syntax_table_inited = 0; |
| if (!syntax_table_inited) |
| { |
| syntax_table_inited = 1; |
| memset(re_syntax_table, 0, 256); |
| for (a = 'a'; a <= 'z'; a++) |
| re_syntax_table[a] = Sword; |
| for (a = 'A'; a <= 'Z'; a++) |
| re_syntax_table[a] = Sword; |
| for (a = '0'; a <= '9'; a++) |
| re_syntax_table[a] = Sword | Sdigit | Shexdigit; |
| for (a = '0'; a <= '7'; a++) |
| re_syntax_table[a] |= Soctaldigit; |
| for (a = 'A'; a <= 'F'; a++) |
| re_syntax_table[a] |= Shexdigit; |
| for (a = 'a'; a <= 'f'; a++) |
| re_syntax_table[a] |= Shexdigit; |
| re_syntax_table['_'] = Sword; |
| for (a = 9; a <= 13; a++) |
| re_syntax_table[a] = Swhitespace; |
| re_syntax_table[' '] = Swhitespace; |
| } |
| re_compile_initialized = 1; |
| for (a = 0; a < 256; a++) |
| { |
| regexp_plain_ops[a] = Rnormal; |
| regexp_quoted_ops[a] = Rnormal; |
| } |
| for (a = '0'; a <= '9'; a++) |
| regexp_quoted_ops[a] = Rmemory; |
| regexp_plain_ops['\134'] = Rquote; |
| if (regexp_syntax & RE_NO_BK_PARENS) |
| { |
| regexp_plain_ops['('] = Ropenpar; |
| regexp_plain_ops[')'] = Rclosepar; |
| } |
| else |
| { |
| regexp_quoted_ops['('] = Ropenpar; |
| regexp_quoted_ops[')'] = Rclosepar; |
| } |
| if (regexp_syntax & RE_NO_BK_VBAR) |
| regexp_plain_ops['\174'] = Ror; |
| else |
| regexp_quoted_ops['\174'] = Ror; |
| regexp_plain_ops['*'] = Rstar; |
| if (regexp_syntax & RE_BK_PLUS_QM) |
| { |
| regexp_quoted_ops['+'] = Rplus; |
| regexp_quoted_ops['?'] = Roptional; |
| } |
| else |
| { |
| regexp_plain_ops['+'] = Rplus; |
| regexp_plain_ops['?'] = Roptional; |
| } |
| if (regexp_syntax & RE_NEWLINE_OR) |
| regexp_plain_ops['\n'] = Ror; |
| regexp_plain_ops['\133'] = Ropenset; |
| regexp_plain_ops['\136'] = Rbol; |
| regexp_plain_ops['$'] = Reol; |
| regexp_plain_ops['.'] = Ranychar; |
| if (!(regexp_syntax & RE_NO_GNU_EXTENSIONS)) |
| { |
| regexp_quoted_ops['w'] = Rwordchar; |
| regexp_quoted_ops['W'] = Rnotwordchar; |
| regexp_quoted_ops['<'] = Rwordbeg; |
| regexp_quoted_ops['>'] = Rwordend; |
| regexp_quoted_ops['b'] = Rwordbound; |
| regexp_quoted_ops['B'] = Rnotwordbound; |
| regexp_quoted_ops['`'] = Rbegbuf; |
| regexp_quoted_ops['\''] = Rendbuf; |
| } |
| if (regexp_syntax & RE_ANSI_HEX) |
| regexp_quoted_ops['v'] = Rextended_memory; |
| for (a = 0; a < Rnum_ops; a++) |
| regexp_precedences[a] = 4; |
| if (regexp_syntax & RE_TIGHT_VBAR) |
| { |
| regexp_precedences[Ror] = 3; |
| regexp_precedences[Rbol] = 2; |
| regexp_precedences[Reol] = 2; |
| } |
| else |
| { |
| regexp_precedences[Ror] = 2; |
| regexp_precedences[Rbol] = 3; |
| regexp_precedences[Reol] = 3; |
| } |
| regexp_precedences[Rclosepar] = 1; |
| regexp_precedences[Rend] = 0; |
| regexp_context_indep_ops = (regexp_syntax & RE_CONTEXT_INDEP_OPS) != 0; |
| regexp_ansi_sequences = (regexp_syntax & RE_ANSI_HEX) != 0; |
| } |
| int re_set_syntax(int syntax) |
| { |
| int ret; |
| ret = regexp_syntax; |
| regexp_syntax = syntax; |
| re_syntax = syntax; /* Exported copy */ |
| re_compile_initialize(); |
| return ret; |
| } |
| static int hex_char_to_decimal(int ch) |
| { |
| if (ch >= '0' && ch <= '9') |
| return ch - '0'; |
| if (ch >= 'a' && ch <= 'f') |
| return ch - 'a' + 10; |
| if (ch >= 'A' && ch <= 'F') |
| return ch - 'A' + 10; |
| return 16; |
| } |
| static void re_compile_fastmap_aux(unsigned char *code, int pos, |
| unsigned char *visited, |
| unsigned char *can_be_null, |
| unsigned char *fastmap) |
| { |
| int a; |
| int b; |
| int syntaxcode; |
| if (visited[pos]) |
| return; /* we have already been here */ |
| visited[pos] = 1; |
| for (;;) |
| switch (code[pos++]) { |
| case Cend: |
| { |
| *can_be_null = 1; |
| return; |
| } |
| case Cbol: |
| case Cbegbuf: |
| case Cendbuf: |
| case Cwordbeg: |
| case Cwordend: |
| case Cwordbound: |
| case Cnotwordbound: |
| { |
| for (a = 0; a < 256; a++) |
| fastmap[a] = 1; |
| break; |
| } |
| case Csyntaxspec: |
| { |
| syntaxcode = code[pos++]; |
| for (a = 0; a < 256; a++) |
| if (SYNTAX(a) & syntaxcode) |
| fastmap[a] = 1; |
| return; |
| } |
| case Cnotsyntaxspec: |
| { |
| syntaxcode = code[pos++]; |
| for (a = 0; a < 256; a++) |
| if (!(SYNTAX(a) & syntaxcode) ) |
| fastmap[a] = 1; |
| return; |
| } |
| case Ceol: |
| { |
| fastmap['\n'] = 1; |
| if (*can_be_null == 0) |
| *can_be_null = 2; /* can match null, but only at end of buffer*/ |
| return; |
| } |
| case Cset: |
| { |
| for (a = 0; a < 256/8; a++) |
| if (code[pos + a] != 0) |
| for (b = 0; b < 8; b++) |
| if (code[pos + a] & (1 << b)) |
| fastmap[(a << 3) + b] = 1; |
| pos += 256/8; |
| return; |
| } |
| case Cexact: |
| { |
| fastmap[(unsigned char)code[pos]] = 1; |
| return; |
| } |
| case Canychar: |
| { |
| for (a = 0; a < 256; a++) |
| if (a != '\n') |
| fastmap[a] = 1; |
| return; |
| } |
| case Cstart_memory: |
| case Cend_memory: |
| { |
| pos++; |
| break; |
| } |
| case Cmatch_memory: |
| { |
| for (a = 0; a < 256; a++) |
| fastmap[a] = 1; |
| *can_be_null = 1; |
| return; |
| } |
| case Cjump: |
| case Cdummy_failure_jump: |
| case Cupdate_failure_jump: |
| case Cstar_jump: |
| { |
| a = (unsigned char)code[pos++]; |
| a |= (unsigned char)code[pos++] << 8; |
| pos += (int)SHORT(a); |
| if (visited[pos]) |
| { |
| /* argh... the regexp contains empty loops. This is not |
| good, as this may cause a failure stack overflow when |
| matching. Oh well. */ |
| /* this path leads nowhere; pursue other paths. */ |
| return; |
| } |
| visited[pos] = 1; |
| break; |
| } |
| case Cfailure_jump: |
| { |
| a = (unsigned char)code[pos++]; |
| a |= (unsigned char)code[pos++] << 8; |
| a = pos + (int)SHORT(a); |
| re_compile_fastmap_aux(code, a, visited, can_be_null, fastmap); |
| break; |
| } |
| case Crepeat1: |
| { |
| pos += 2; |
| break; |
| } |
| default: |
| { |
| /*PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");*/ |
| re_errno = TP_RE_UNKNOWN_OPCODE; |
| return; |
| /*NOTREACHED*/ |
| } |
| } |
| } |
| static int re_do_compile_fastmap(unsigned char *buffer, int used, int pos, |
| unsigned char *can_be_null, |
| unsigned char *fastmap) |
| { |
| unsigned char small_visited[512], *visited; |
| if (used <= sizeof(small_visited)) |
| visited = small_visited; |
| else |
| { |
| visited = (unsigned char *)malloc(used); |
| if (!visited) |
| return 0; |
| } |
| *can_be_null = 0; |
| memset(fastmap, 0, 256); |
| memset(visited, 0, used); |
| re_compile_fastmap_aux(buffer, pos, visited, can_be_null, fastmap); |
| if (visited != small_visited) |
| free(visited); |
| return 1; |
| } |
| void re_compile_fastmap(regexp_t bufp) |
| { |
| if (!bufp->fastmap || bufp->fastmap_accurate) |
| return; |
| assert(bufp->used > 0); |
| if (!re_do_compile_fastmap(bufp->buffer, |
| bufp->used, |
| 0, |
| &bufp->can_be_null, |
| bufp->fastmap)) |
| return; |
| /*if (PyErr_Occurred()) return;*/ |
| if (re_err_occurred()) return; |
| if (bufp->buffer[0] == Cbol) |
| bufp->anchor = 1; /* begline */ |
| else |
| if (bufp->buffer[0] == Cbegbuf) |
| bufp->anchor = 2; /* begbuf */ |
| else |
| bufp->anchor = 0; /* none */ |
| bufp->fastmap_accurate = 1; |
| } |
| /* |
| * star is coded as: |
| * 1: failure_jump 2 |
| * ... code for operand of star |
| * star_jump 1 |
| * 2: ... code after star |
| * |
| * We change the star_jump to update_failure_jump if we can determine |
| * that it is safe to do so; otherwise we change it to an ordinary |
| * jump. |
| * |
| * plus is coded as |
| * |
| * jump 2 |
| * 1: failure_jump 3 |
| * 2: ... code for operand of plus |
| * star_jump 1 |
| * 3: ... code after plus |
| * |
| * For star_jump considerations this is processed identically to star. |
| * |
| */ |
| static int re_optimize_star_jump(regexp_t bufp, unsigned char *code) |
| { |
| unsigned char map[256]; |
| unsigned char can_be_null; |
| unsigned char *p1; |
| unsigned char *p2; |
| unsigned char ch; |
| int a; |
| int b; |
| int num_instructions = 0; |
| a = (unsigned char)*code++; |
| a |= (unsigned char)*code++ << 8; |
| a = (int)SHORT(a); |
| p1 = code + a + 3; /* skip the failure_jump */ |
| /* Check that the jump is within the pattern */ |
| if (p1<bufp->buffer || bufp->buffer+bufp->used<p1) |
| { |
| /*PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (failure_jump opt)");*/ |
| re_errno = TP_RE_JUMP_OUT_BOUNDS; |
| return 0; |
| } |
| assert(p1[-3] == Cfailure_jump); |
| p2 = code; |
| /* p1 points inside loop, p2 points to after loop */ |
| if (!re_do_compile_fastmap(bufp->buffer, bufp->used, |
| (int)(p2 - bufp->buffer), |
| &can_be_null, map)) |
| goto make_normal_jump; |
| /* If we might introduce a new update point inside the |
| * loop, we can't optimize because then update_jump would |
| * update a wrong failure point. Thus we have to be |
| * quite careful here. |
| */ |
| /* loop until we find something that consumes a character */ |
| loop_p1: |
| num_instructions++; |
| switch (*p1++) |
| { |
| case Cbol: |
| case Ceol: |
| case Cbegbuf: |
| case Cendbuf: |
| case Cwordbeg: |
| case Cwordend: |
| case Cwordbound: |
| case Cnotwordbound: |
| { |
| goto loop_p1; |
| } |
| case Cstart_memory: |
| case Cend_memory: |
| { |
| p1++; |
| goto loop_p1; |
| } |
| case Cexact: |
| { |
| ch = (unsigned char)*p1++; |
| if (map[(int)ch]) |
| goto make_normal_jump; |
| break; |
| } |
| case Canychar: |
| { |
| for (b = 0; b < 256; b++) |
| if (b != '\n' && map[b]) |
| goto make_normal_jump; |
| break; |
| } |
| case Cset: |
| { |
| for (b = 0; b < 256; b++) |
| if ((p1[b >> 3] & (1 << (b & 7))) && map[b]) |
| goto make_normal_jump; |
| p1 += 256/8; |
| break; |
| } |
| default: |
| { |
| goto make_normal_jump; |
| } |
| } |
| /* now we know that we can't backtrack. */ |
| while (p1 != p2 - 3) |
| { |
| num_instructions++; |
| switch (*p1++) |
| { |
| case Cend: |
| { |
| return 0; |
| } |
| case Cbol: |
| case Ceol: |
| case Canychar: |
| case Cbegbuf: |
| case Cendbuf: |
| case Cwordbeg: |
| case Cwordend: |
| case Cwordbound: |
| case Cnotwordbound: |
| { |
| break; |
| } |
| case Cset: |
| { |
| p1 += 256/8; |
| break; |
| } |
| case Cexact: |
| case Cstart_memory: |
| case Cend_memory: |
| case Cmatch_memory: |
| case Csyntaxspec: |
| case Cnotsyntaxspec: |
| { |
| p1++; |
| break; |
| } |
| case Cjump: |
| case Cstar_jump: |
| case Cfailure_jump: |
| case Cupdate_failure_jump: |
| case Cdummy_failure_jump: |
| { |
| goto make_normal_jump; |
| } |
| default: |
| { |
| return 0; |
| } |
| } |
| } |
| /* make_update_jump: */ |
| code -= 3; |
| a += 3; /* jump to after the Cfailure_jump */ |
| code[0] = Cupdate_failure_jump; |
| code[1] = a & 0xff; |
| code[2] = a >> 8; |
| if (num_instructions > 1) |
| return 1; |
| assert(num_instructions == 1); |
| /* if the only instruction matches a single character, we can do |
| * better */ |
| p1 = code + 3 + a; /* start of sole instruction */ |
| if (*p1 == Cset || *p1 == Cexact || *p1 == Canychar || |
| *p1 == Csyntaxspec || *p1 == Cnotsyntaxspec) |
| code[0] = Crepeat1; |
| return 1; |
| make_normal_jump: |
| code -= 3; |
| *code = Cjump; |
| return 1; |
| } |
| static int re_optimize(regexp_t bufp) |
| { |
| unsigned char *code; |
| code = bufp->buffer; |
| while(1) |
| { |
| switch (*code++) |
| { |
| case Cend: |
| { |
| return 1; |
| } |
| case Canychar: |
| case Cbol: |
| case Ceol: |
| case Cbegbuf: |
| case Cendbuf: |
| case Cwordbeg: |
| case Cwordend: |
| case Cwordbound: |
| case Cnotwordbound: |
| { |
| break; |
| } |
| case Cset: |
| { |
| code += 256/8; |
| break; |
| } |
| case Cexact: |
| case Cstart_memory: |
| case Cend_memory: |
| case Cmatch_memory: |
| case Csyntaxspec: |
| case Cnotsyntaxspec: |
| { |
| code++; |
| break; |
| } |
| case Cstar_jump: |
| { |
| if (!re_optimize_star_jump(bufp, code)) |
| { |
| return 0; |
| } |
| /* fall through */ |
| } |
| case Cupdate_failure_jump: |
| case Cjump: |
| case Cdummy_failure_jump: |
| case Cfailure_jump: |
| case Crepeat1: |
| { |
| code += 2; |
| break; |
| } |
| default: |
| { |
| return 0; |
| } |
| } |
| } |
| } |
| #define NEXTCHAR(var) \ |
| { \ |
| if (pos >= size) \ |
| goto ends_prematurely; \ |
| (var) = regex[pos]; \ |
| pos++; \ |
| } |
| #define ALLOC(amount) \ |
| { \ |
| if (pattern_offset+(amount) > alloc) \ |
| { \ |
| alloc += 256 + (amount); \ |
| pattern = (unsigned char *)realloc(pattern, alloc); \ |
| if (!pattern) \ |
| goto out_of_memory; \ |
| } \ |
| } |
| #define STORE(ch) pattern[pattern_offset++] = (ch) |
| #define CURRENT_LEVEL_START (starts[starts_base + current_level]) |
| #define SET_LEVEL_START starts[starts_base + current_level] = pattern_offset |
| #define PUSH_LEVEL_STARTS \ |
| if (starts_base < (MAX_NESTING-1)*NUM_LEVELS) \ |
| starts_base += NUM_LEVELS; \ |
| else \ |
| goto too_complex \ |
| #define POP_LEVEL_STARTS starts_base -= NUM_LEVELS |
| #define PUT_ADDR(offset,addr) \ |
| { \ |
| int disp = (addr) - (offset) - 2; \ |
| pattern[(offset)] = disp & 0xff; \ |
| pattern[(offset)+1] = (disp>>8) & 0xff; \ |
| } |
| #define INSERT_JUMP(pos,type,addr) \ |
| { \ |
| int a, p = (pos), t = (type), ad = (addr); \ |
| for (a = pattern_offset - 1; a >= p; a--) \ |
| pattern[a + 3] = pattern[a]; \ |
| pattern[p] = t; \ |
| PUT_ADDR(p+1,ad); \ |
| pattern_offset += 3; \ |
| } |
| #define SETBIT(buf,offset,bit) (buf)[(offset)+(bit)/8] |= (1<<((bit) & 7)) |
| #define SET_FIELDS \ |
| { \ |
| bufp->allocated = alloc; \ |
| bufp->buffer = pattern; \ |
| bufp->used = pattern_offset; \ |
| } |
| #define GETHEX(var) \ |
| { \ |
| unsigned char gethex_ch, gethex_value; \ |
| NEXTCHAR(gethex_ch); \ |
| gethex_value = hex_char_to_decimal(gethex_ch); \ |
| if (gethex_value == 16) \ |
| goto hex_error; \ |
| NEXTCHAR(gethex_ch); \ |
| gethex_ch = hex_char_to_decimal(gethex_ch); \ |
| if (gethex_ch == 16) \ |
| goto hex_error; \ |
| (var) = gethex_value * 16 + gethex_ch; \ |
| } |
| #define ANSI_TRANSLATE(ch) \ |
| { \ |
| switch (ch) \ |
| { \ |
| case 'a': \ |
| case 'A': \ |
| { \ |
| ch = 7; /* audible bell */ \ |
| break; \ |
| } \ |
| case 'b': \ |
| case 'B': \ |
| { \ |
| ch = 8; /* backspace */ \ |
| break; \ |
| } \ |
| case 'f': \ |
| case 'F': \ |
| { \ |
| ch = 12; /* form feed */ \ |
| break; \ |
| } \ |
| case 'n': \ |
| case 'N': \ |
| { \ |
| ch = 10; /* line feed */ \ |
| break; \ |
| } \ |
| case 'r': \ |
| case 'R': \ |
| { \ |
| ch = 13; /* carriage return */ \ |
| break; \ |
| } \ |
| case 't': \ |
| case 'T': \ |
| { \ |
| ch = 9; /* tab */ \ |
| break; \ |
| } \ |
| case 'v': \ |
| case 'V': \ |
| { \ |
| ch = 11; /* vertical tab */ \ |
| break; \ |
| } \ |
| case 'x': /* hex code */ \ |
| case 'X': \ |
| { \ |
| GETHEX(ch); \ |
| break; \ |
| } \ |
| default: \ |
| { \ |
| /* other characters passed through */ \ |
| if (translate) \ |
| ch = translate[(unsigned char)ch]; \ |
| break; \ |
| } \ |
| } \ |
| } |
| char *re_compile_pattern(unsigned char *regex, int size, regexp_t bufp) |
| { |
| int a; |
| int pos; |
| int op; |
| int current_level; |
| int level; |
| int opcode; |
| int pattern_offset = 0, alloc; |
| int starts[NUM_LEVELS * MAX_NESTING]; |
| int starts_base; |
| int future_jumps[MAX_NESTING]; |
| int num_jumps; |
| unsigned char ch = '\0'; |
| unsigned char *pattern; |
| unsigned char *translate; |
| int next_register; |
| int paren_depth; |
| int num_open_registers; |
| int open_registers[RE_NREGS]; |
| int beginning_context; |
| if (!re_compile_initialized) |
| re_compile_initialize(); |
| bufp->used = 0; |
| bufp->fastmap_accurate = 0; |
| bufp->uses_registers = 1; |
| bufp->num_registers = 1; |
| translate = bufp->translate; |
| pattern = bufp->buffer; |
| alloc = bufp->allocated; |
| if (alloc == 0 || pattern == NULL) |
| { |
| alloc = 256; |
| pattern = (unsigned char *)malloc(alloc); |
| if (!pattern) |
| goto out_of_memory; |
| } |
| pattern_offset = 0; |
| starts_base = 0; |
| num_jumps = 0; |
| current_level = 0; |
| SET_LEVEL_START; |
| num_open_registers = 0; |
| next_register = 1; |
| paren_depth = 0; |
| beginning_context = 1; |
| op = -1; |
| /* we use Rend dummy to ensure that pending jumps are updated |
| (due to low priority of Rend) before exiting the loop. */ |
| pos = 0; |
| while (op != Rend) |
| { |
| if (pos >= size) |
| op = Rend; |
| else |
| { |
| NEXTCHAR(ch); |
| if (translate) |
| ch = translate[(unsigned char)ch]; |
| op = regexp_plain_ops[(unsigned char)ch]; |
| if (op == Rquote) |
| { |
| NEXTCHAR(ch); |
| op = regexp_quoted_ops[(unsigned char)ch]; |
| if (op == Rnormal && regexp_ansi_sequences) |
| ANSI_TRANSLATE(ch); |
| } |
| } |
| level = regexp_precedences[op]; |
| /* printf("ch='%c' op=%d level=%d current_level=%d |
| curlevstart=%d\n", ch, op, level, current_level, |
| CURRENT_LEVEL_START); */ |
| if (level > current_level) |
| { |
| for (current_level++; current_level < level; current_level++) |
| SET_LEVEL_START; |
| SET_LEVEL_START; |
| } |
| else |
| if (level < current_level) |
| { |
| current_level = level; |
| for (;num_jumps > 0 && |
| future_jumps[num_jumps-1] >= CURRENT_LEVEL_START; |
| num_jumps--) |
| PUT_ADDR(future_jumps[num_jumps-1], pattern_offset); |
| } |
| switch (op) |
| { |
| case Rend: |
| { |
| break; |
| } |
| case Rnormal: |
| { |
| normal_char: |
| opcode = Cexact; |
| store_opcode_and_arg: /* opcode & ch must be set */ |
| SET_LEVEL_START; |
| ALLOC(2); |
| STORE(opcode); |
| STORE(ch); |
| break; |
| } |
| case Ranychar: |
| { |
| opcode = Canychar; |
| store_opcode: |
| SET_LEVEL_START; |
| ALLOC(1); |
| STORE(opcode); |
| break; |
| } |
| case Rquote: |
| { |
| /*Py_FatalError("Rquote");*/ |
| re_errno = TP_RE_QUOTE_ERR; |
| abort(); /* XXX: may need to jump to error handler */ |
| /*NOTREACHED*/ |
| } |
| case Rbol: |
| { |
| if (!beginning_context) { |
| if (regexp_context_indep_ops) |
| goto op_error; |
| else |
| goto normal_char; |
| } |
| opcode = Cbol; |
| goto store_opcode; |
| } |
| case Reol: |
| { |
| if (!((pos >= size) || |
| ((regexp_syntax & RE_NO_BK_VBAR) ? |
| (regex[pos] == '\174') : |
| (pos+1 < size && regex[pos] == '\134' && |
| regex[pos+1] == '\174')) || |
| ((regexp_syntax & RE_NO_BK_PARENS)? |
| (regex[pos] == ')'): |
| (pos+1 < size && regex[pos] == '\134' && |
| regex[pos+1] == ')')))) { |
| if (regexp_context_indep_ops) |
| goto op_error; |
| else |
| goto normal_char; |
| } |
| opcode = Ceol; |
| goto store_opcode; |
| /* NOTREACHED */ |
| break; |
| } |
| case Roptional: |
| { |
| if (beginning_context) { |
| if (regexp_context_indep_ops) |
| goto op_error; |
| else |
| goto normal_char; |
| } |
| if (CURRENT_LEVEL_START == pattern_offset) |
| break; /* ignore empty patterns for ? */ |
| ALLOC(3); |
| INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump, |
| pattern_offset + 3); |
| break; |
| } |
| case Rstar: |
| case Rplus: |
| { |
| if (beginning_context) { |
| if (regexp_context_indep_ops) |
| goto op_error; |
| else |
| goto normal_char; |
| } |
| if (CURRENT_LEVEL_START == pattern_offset) |
| break; /* ignore empty patterns for + and * */ |
| ALLOC(9); |
| INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump, |
| pattern_offset + 6); |
| INSERT_JUMP(pattern_offset, Cstar_jump, CURRENT_LEVEL_START); |
| if (op == Rplus) /* jump over initial failure_jump */ |
| INSERT_JUMP(CURRENT_LEVEL_START, Cdummy_failure_jump, |
| CURRENT_LEVEL_START + 6); |
| break; |
| } |
| case Ror: |
| { |
| ALLOC(6); |
| INSERT_JUMP(CURRENT_LEVEL_START, Cfailure_jump, |
| pattern_offset + 6); |
| if (num_jumps >= MAX_NESTING) |
| goto too_complex; |
| STORE(Cjump); |
| future_jumps[num_jumps++] = pattern_offset; |
| STORE(0); |
| STORE(0); |
| SET_LEVEL_START; |
| break; |
| } |
| case Ropenpar: |
| { |
| SET_LEVEL_START; |
| if (next_register < RE_NREGS) |
| { |
| bufp->uses_registers = 1; |
| ALLOC(2); |
| STORE(Cstart_memory); |
| STORE(next_register); |
| open_registers[num_open_registers++] = next_register; |
| bufp->num_registers++; |
| next_register++; |
| } |
| paren_depth++; |
| PUSH_LEVEL_STARTS; |
| current_level = 0; |
| SET_LEVEL_START; |
| break; |
| } |
| case Rclosepar: |
| { |
| if (paren_depth <= 0) |
| goto parenthesis_error; |
| POP_LEVEL_STARTS; |
| current_level = regexp_precedences[Ropenpar]; |
| paren_depth--; |
| if (paren_depth < num_open_registers) |
| { |
| bufp->uses_registers = 1; |
| ALLOC(2); |
| STORE(Cend_memory); |
| num_open_registers--; |
| STORE(open_registers[num_open_registers]); |
| } |
| break; |
| } |
| case Rmemory: |
| { |
| if (ch == '0') |
| goto bad_match_register; |
| assert(ch >= '0' && ch <= '9'); |
| bufp->uses_registers = 1; |
| opcode = Cmatch_memory; |
| ch -= '0'; |
| goto store_opcode_and_arg; |
| } |
| case Rextended_memory: |
| { |
| NEXTCHAR(ch); |
| if (ch < '0' || ch > '9') |
| goto bad_match_register; |
| NEXTCHAR(a); |
| if (a < '0' || a > '9') |
| goto bad_match_register; |
| ch = 10 * (a - '0') + ch - '0'; |
| if (ch == 0 || ch >= RE_NREGS) |
| goto bad_match_register; |
| bufp->uses_registers = 1; |
| opcode = Cmatch_memory; |
| goto store_opcode_and_arg; |
| } |
| case Ropenset: |
| { |
| int complement; |
| int prev; |
| int offset; |
| int range; |
| int firstchar; |
| SET_LEVEL_START; |
| ALLOC(1+256/8); |
| STORE(Cset); |
| offset = pattern_offset; |
| for (a = 0; a < 256/8; a++) |
| STORE(0); |
| NEXTCHAR(ch); |
| if (translate) |
| ch = translate[(unsigned char)ch]; |
| if (ch == '\136') |
| { |
| complement = 1; |
| NEXTCHAR(ch); |
| if (translate) |
| ch = translate[(unsigned char)ch]; |
| } |
| else |
| complement = 0; |
| prev = -1; |
| range = 0; |
| firstchar = 1; |
| while (ch != '\135' || firstchar) |
| { |
| firstchar = 0; |
| if (regexp_ansi_sequences && ch == '\134') |
| { |
| NEXTCHAR(ch); |
| ANSI_TRANSLATE(ch); |
| } |
| if (range) |
| { |
| for (a = prev; a <= (int)ch; a++) |
| SETBIT(pattern, offset, a); |
| prev = -1; |
| range = 0; |
| } |
| else |
| if (prev != -1 && ch == '-') |
| range = 1; |
| else |
| { |
| SETBIT(pattern, offset, ch); |
| prev = ch; |
| } |
| NEXTCHAR(ch); |
| if (translate) |
| ch = translate[(unsigned char)ch]; |
| } |
| if (range) |
| SETBIT(pattern, offset, '-'); |
| if (complement) |
| { |
| for (a = 0; a < 256/8; a++) |
| pattern[offset+a] ^= 0xff; |
| } |
| break; |
| } |
| case Rbegbuf: |
| { |
| opcode = Cbegbuf; |
| goto store_opcode; |
| } |
| case Rendbuf: |
| { |
| opcode = Cendbuf; |
| goto store_opcode; |
| } |
| case Rwordchar: |
| { |
| opcode = Csyntaxspec; |
| ch = Sword; |
| goto store_opcode_and_arg; |
| } |
| case Rnotwordchar: |
| { |
| opcode = Cnotsyntaxspec; |
| ch = Sword; |
| goto store_opcode_and_arg; |
| } |
| case Rwordbeg: |
| { |
| opcode = Cwordbeg; |
| goto store_opcode; |
| } |
| case Rwordend: |
| { |
| opcode = Cwordend; |
| goto store_opcode; |
| } |
| case Rwordbound: |
| { |
| opcode = Cwordbound; |
| goto store_opcode; |
| } |
| case Rnotwordbound: |
| { |
| opcode = Cnotwordbound; |
| goto store_opcode; |
| } |
| default: |
| { |
| abort(); |
| } |
| } |
| beginning_context = (op == Ropenpar || op == Ror); |
| } |
| if (starts_base != 0) |
| goto parenthesis_error; |
| assert(num_jumps == 0); |
| ALLOC(1); |
| STORE(Cend); |
| SET_FIELDS; |
| if(!re_optimize(bufp)) |
| return "Optimization error"; |
| return NULL; |
| op_error: |
| SET_FIELDS; |
| return "Badly placed special character"; |
| bad_match_register: |
| SET_FIELDS; |
| return "Bad match register number"; |
| hex_error: |
| SET_FIELDS; |
| return "Bad hexadecimal number"; |
| parenthesis_error: |
| SET_FIELDS; |
| return "Badly placed parenthesis"; |
| out_of_memory: |
| SET_FIELDS; |
| return "Out of memory"; |
| ends_prematurely: |
| SET_FIELDS; |
| return "Regular expression ends prematurely"; |
| too_complex: |
| SET_FIELDS; |
| return "Regular expression too complex"; |
| } |
| #undef CHARAT |
| #undef NEXTCHAR |
| #undef GETHEX |
| #undef ALLOC |
| #undef STORE |
| #undef CURRENT_LEVEL_START |
| #undef SET_LEVEL_START |
| #undef PUSH_LEVEL_STARTS |
| #undef POP_LEVEL_STARTS |
| #undef PUT_ADDR |
| #undef INSERT_JUMP |
| #undef SETBIT |
| #undef SET_FIELDS |
| #define PREFETCH if (text == textend) goto fail |
| #define NEXTCHAR(var) \ |
| PREFETCH; \ |
| var = (unsigned char)*text++; \ |
| if (translate) \ |
| var = translate[var] |
| int re_match(regexp_t bufp, unsigned char *string, int size, int pos, |
| regexp_registers_t old_regs) |
| { |
| unsigned char *code; |
| unsigned char *translate; |
| unsigned char *text; |
| unsigned char *textstart; |
| unsigned char *textend; |
| int a; |
| int b; |
| int ch; |
| int reg; |
| int match_end; |
| unsigned char *regstart; |
| unsigned char *regend; |
| int regsize; |
| match_state state; |
| assert(pos >= 0 && size >= 0); |
| assert(pos <= size); |
| text = string + pos; |
| textstart = string; |
| textend = string + size; |
| code = bufp->buffer; |
| translate = bufp->translate; |
| NEW_STATE(state, bufp->num_registers); |
| continue_matching: |
| switch (*code++) |
| { |
| case Cend: |
| { |
| match_end = text - textstart; |
| if (old_regs) |
| { |
| old_regs->start[0] = pos; |
| old_regs->end[0] = match_end; |
| if (!bufp->uses_registers) |
| { |
| for (a = 1; a < RE_NREGS; a++) |
| { |
| old_regs->start[a] = -1; |
| old_regs->end[a] = -1; |
| } |
| } |
| else |
| { |
| for (a = 1; a < bufp->num_registers; a++) |
| { |
| if ((GET_REG_START(state, a) == NULL) || |
| (GET_REG_END(state, a) == NULL)) |
| { |
| old_regs->start[a] = -1; |
| old_regs->end[a] = -1; |
| continue; |
| } |
| old_regs->start[a] = GET_REG_START(state, a) - textstart; |
| old_regs->end[a] = GET_REG_END(state, a) - textstart; |
| } |
| for (; a < RE_NREGS; a++) |
| { |
| old_regs->start[a] = -1; |
| old_regs->end[a] = -1; |
| } |
| } |
| } |
| FREE_STATE(state); |
| return match_end - pos; |
| } |
| case Cbol: |
| { |
| if (text == textstart || text[-1] == '\n') |
| goto continue_matching; |
| goto fail; |
| } |
| case Ceol: |
| { |
| if (text == textend || *text == '\n') |
| goto continue_matching; |
| goto fail; |
| } |
| case Cset: |
| { |
| NEXTCHAR(ch); |
| if (code[ch/8] & (1<<(ch & 7))) |
| { |
| code += 256/8; |
| goto continue_matching; |
| } |
| goto fail; |
| } |
| case Cexact: |
| { |
| NEXTCHAR(ch); |
| if (ch != (unsigned char)*code++) |
| goto fail; |
| goto continue_matching; |
| } |
| case Canychar: |
| { |
| NEXTCHAR(ch); |
| if (ch == '\n') |
| goto fail; |
| goto continue_matching; |
| } |
| case Cstart_memory: |
| { |
| reg = *code++; |
| SET_REG_START(state, reg, text, goto error); |
| goto continue_matching; |
| } |
| case Cend_memory: |
| { |
| reg = *code++; |
| SET_REG_END(state, reg, text, goto error); |
| goto continue_matching; |
| } |
| case Cmatch_memory: |
| { |
| reg = *code++; |
| regstart = GET_REG_START(state, reg); |
| regend = GET_REG_END(state, reg); |
| if ((regstart == NULL) || (regend == NULL)) |
| goto fail; /* or should we just match nothing? */ |
| regsize = regend - regstart; |
| if (regsize > (textend - text)) |
| goto fail; |
| if(translate) |
| { |
| for (; regstart < regend; regstart++, text++) |
| if (translate[*regstart] != translate[*text]) |
| goto fail; |
| } |
| else |
| for (; regstart < regend; regstart++, text++) |
| if (*regstart != *text) |
| goto fail; |
| goto continue_matching; |
| } |
| case Cupdate_failure_jump: |
| { |
| UPDATE_FAILURE(state, text, goto error); |
| /* fall to next case */ |
| } |
| /* treat Cstar_jump just like Cjump if it hasn't been optimized */ |
| case Cstar_jump: |
| case Cjump: |
| { |
| a = (unsigned char)*code++; |
| a |= (unsigned char)*code++ << 8; |
| code += (int)SHORT(a); |
| if (code<bufp->buffer || bufp->buffer+bufp->used<code) { |
| /*PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cjump)");*/ |
| re_errno = TP_RE_JUMP_OUT_BOUNDS; |
| FREE_STATE(state); |
| return -2; |
| } |
| goto continue_matching; |
| } |
| case Cdummy_failure_jump: |
| { |
| unsigned char *failuredest; |
| a = (unsigned char)*code++; |
| a |= (unsigned char)*code++ << 8; |
| a = (int)SHORT(a); |
| assert(*code == Cfailure_jump); |
| b = (unsigned char)code[1]; |
| b |= (unsigned char)code[2] << 8; |
| failuredest = code + (int)SHORT(b) + 3; |
| if (failuredest<bufp->buffer || bufp->buffer+bufp->used < failuredest) { |
| /*PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cdummy_failure_jump failuredest)");*/ |
| re_errno = TP_RE_JUMP_OUT_BOUNDS; |
| FREE_STATE(state); |
| return -2; |
| } |
| PUSH_FAILURE(state, failuredest, NULL, goto error); |
| code += a; |
| if (code<bufp->buffer || bufp->buffer+bufp->used < code) { |
| /*PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cdummy_failure_jump code)");*/ |
| re_errno = TP_RE_JUMP_OUT_BOUNDS; |
| FREE_STATE(state); |
| return -2; |
| } |
| goto continue_matching; |
| } |
| case Cfailure_jump: |
| { |
| a = (unsigned char)*code++; |
| a |= (unsigned char)*code++ << 8; |
| a = (int)SHORT(a); |
| if (code+a<bufp->buffer || bufp->buffer+bufp->used < code+a) { |
| /*PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Cfailure_jump)");*/ |
| re_errno = TP_RE_JUMP_OUT_BOUNDS; |
| FREE_STATE(state); |
| return -2; |
| } |
| PUSH_FAILURE(state, code + a, text, goto error); |
| goto continue_matching; |
| } |
| case Crepeat1: |
| { |
| unsigned char *pinst; |
| a = (unsigned char)*code++; |
| a |= (unsigned char)*code++ << 8; |
| a = (int)SHORT(a); |
| pinst = code + a; |
| if (pinst<bufp->buffer || bufp->buffer+bufp->used<pinst) { |
| /*PyErr_SetString(PyExc_SystemError, "Regex VM jump out of bounds (Crepeat1)");*/ |
| re_errno = TP_RE_JUMP_OUT_BOUNDS; |
| FREE_STATE(state); |
| return -2; |
| } |
| /* pinst is sole instruction in loop, and it matches a |
| * single character. Since Crepeat1 was originally a |
| * Cupdate_failure_jump, we also know that backtracking |
| * is useless: so long as the single-character |
| * expression matches, it must be used. Also, in the |
| * case of +, we've already matched one character, so + |
| * can't fail: nothing here can cause a failure. */ |
| switch (*pinst++) |
| { |
| case Cset: |
| { |
| if (translate) |
| { |
| while (text < textend) |
| { |
| ch = translate[(unsigned char)*text]; |
| if (pinst[ch/8] & (1<<(ch & 7))) |
| text++; |
| else |
| break; |
| } |
| } |
| else |
| { |
| while (text < textend) |
| { |
| ch = (unsigned char)*text; |
| if (pinst[ch/8] & (1<<(ch & 7))) |
| text++; |
| else |
| break; |
| } |
| } |
| break; |
| } |
| case Cexact: |
| { |
| ch = (unsigned char)*pinst; |
| if (translate) |
| { |
| while (text < textend && |
| translate[(unsigned char)*text] == ch) |
| text++; |
| } |
| else |
| { |
| while (text < textend && (unsigned char)*text == ch) |
| text++; |
| } |
| break; |
| } |
| case Canychar: |
| { |
| while (text < textend && (unsigned char)*text != '\n') |
| text++; |
| break; |
| } |
| case Csyntaxspec: |
| { |
| a = (unsigned char)*pinst; |
| if (translate) |
| { |
| while (text < textend && |
| (SYNTAX(translate[*text]) & a) ) |
| text++; |
| } |
| else |
| { |
| while (text < textend && (SYNTAX(*text) & a) ) |
| text++; |
| } |
| break; |
| } |
| case Cnotsyntaxspec: |
| { |
| a = (unsigned char)*pinst; |
| if (translate) |
| { |
| while (text < textend && |
| !(SYNTAX(translate[*text]) & a) ) |
| text++; |
| } |
| else |
| { |
| while (text < textend && !(SYNTAX(*text) & a) ) |
| text++; |
| } |
| break; |
| } |
| default: |
| { |
| FREE_STATE(state); |
| /*PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");*/ |
| re_errno = TP_RE_UNKNOWN_OPCODE; |
| return -2; |
| /*NOTREACHED*/ |
| } |
| } |
| /* due to the funky way + and * are compiled, the top |
| * failure- stack entry at this point is actually a |
| * success entry -- update it & pop it */ |
| UPDATE_FAILURE(state, text, goto error); |
| goto fail; /* i.e., succeed <wink/sigh> */ |
| } |
| case Cbegbuf: |
| { |
| if (text == textstart) |
| goto continue_matching; |
| goto fail; |
| } |
| case Cendbuf: |
| { |
| if (text == textend) |
| goto continue_matching; |
| goto fail; |
| } |
| case Cwordbeg: |
| { |
| if (text == textend) |
| goto fail; |
| if (!(SYNTAX(*text) & Sword)) |
| goto fail; |
| if (text == textstart) |
| goto continue_matching; |
| if (!(SYNTAX(text[-1]) & Sword)) |
| goto continue_matching; |
| goto fail; |
| } |
| case Cwordend: |
| { |
| if (text == textstart) |
| goto fail; |
| if (!(SYNTAX(text[-1]) & Sword)) |
| goto fail; |
| if (text == textend) |
| goto continue_matching; |
| if (!(SYNTAX(*text) & Sword)) |
| goto continue_matching; |
| goto fail; |
| } |
| case Cwordbound: |
| { |
| /* Note: as in gnu regexp, this also matches at the |
| * beginning and end of buffer. */ |
| if (text == textstart || text == textend) |
| goto continue_matching; |
| if ((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword)) |
| goto continue_matching; |
| goto fail; |
| } |
| case Cnotwordbound: |
| { |
| /* Note: as in gnu regexp, this never matches at the |
| * beginning and end of buffer. */ |
| if (text == textstart || text == textend) |
| goto fail; |
| if (!((SYNTAX(text[-1]) & Sword) ^ (SYNTAX(*text) & Sword))) |
| goto continue_matching; |
| goto fail; |
| } |
| case Csyntaxspec: |
| { |
| NEXTCHAR(ch); |
| if (!(SYNTAX(ch) & (unsigned char)*code++)) |
| goto fail; |
| goto continue_matching; |
| } |
| case Cnotsyntaxspec: |
| { |
| NEXTCHAR(ch); |
| if (SYNTAX(ch) & (unsigned char)*code++) |
| goto fail; |
| goto continue_matching; |
| } |
| default: |
| { |
| FREE_STATE(state); |
| /*PyErr_SetString(PyExc_SystemError, "Unknown regex opcode: memory corrupted?");*/ |
| re_errno = TP_RE_UNKNOWN_OPCODE; |
| return -2; |
| /*NOTREACHED*/ |
| } |
| } |
| #if 0 /* This line is never reached --Guido */ |
| abort(); |
| #endif |
| /* |
| *NOTREACHED |
| */ |
| /* Using "break;" in the above switch statement is equivalent to "goto fail;" */ |
| fail: |
| POP_FAILURE(state, code, text, goto done_matching, goto error); |
| goto continue_matching; |
| done_matching: |
| /* if(translated != NULL) */ |
| /* free(translated); */ |
| FREE_STATE(state); |
| return -1; |
| error: |
| /* if (translated != NULL) */ |
| /* free(translated); */ |
| FREE_STATE(state); |
| return -2; |
| } |
| #undef PREFETCH |
| #undef NEXTCHAR |
| int re_search(regexp_t bufp, unsigned char *string, int size, int pos, |
| int range, regexp_registers_t regs) |
| { |
| unsigned char *fastmap; |
| unsigned char *translate; |
| unsigned char *text; |
| unsigned char *partstart; |
| unsigned char *partend; |
| int dir; |
| int ret; |
| unsigned char anchor; |
| assert(size >= 0 && pos >= 0); |
| assert(pos + range >= 0 && pos + range <= size); /* Bugfix by ylo */ |
| fastmap = bufp->fastmap; |
| translate = bufp->translate; |
| if (fastmap && !bufp->fastmap_accurate) { |
| re_compile_fastmap(bufp); |
| if (re_err_occurred()) return -2; |
| } |
| anchor = bufp->anchor; |
| if (bufp->can_be_null == 1) /* can_be_null == 2: can match null at eob */ |
| fastmap = NULL; |
| if (range < 0) |
| { |
| dir = -1; |
| range = -range; |
| } |
| else |
| dir = 1; |
| if (anchor == 2) { |
| if (pos != 0) |
| return -1; |
| else |
| range = 0; |
| } |
| for (; range >= 0; range--, pos += dir) |
| { |
| if (fastmap) |
| { |
| if (dir == 1) |
| { /* searching forwards */ |
| text = string + pos; |
| partend = string + size; |
| partstart = text; |
| if (translate) |
| while (text != partend && |
| !fastmap[(unsigned char) translate[(unsigned char)*text]]) |
| text++; |
| else |
| while (text != partend && !fastmap[(unsigned char)*text]) |
| text++; |
| pos += text - partstart; |
| range -= text - partstart; |
| if (pos == size && bufp->can_be_null == 0) |
| return -1; |
| } |
| else |
| { /* searching backwards */ |
| text = string + pos; |
| partstart = string + pos - range; |
| partend = text; |
| if (translate) |
| while (text != partstart && |
| !fastmap[(unsigned char) |
| translate[(unsigned char)*text]]) |
| text--; |
| else |
| while (text != partstart && |
| !fastmap[(unsigned char)*text]) |
| text--; |
| pos -= partend - text; |
| range -= partend - text; |
| } |
| } |
| if (anchor == 1) |
| { /* anchored to begline */ |
| if (pos > 0 && (string[pos - 1] != '\n')) |
| continue; |
| } |
| assert(pos >= 0 && pos <= size); |
| ret = re_match(bufp, string, size, pos, regs); |
| if (ret >= 0) |
| return pos; |
| if (ret == -2) |
| return -2; |
| } |
| return -1; |
| } |
| /* |
| ** Local Variables: |
| ** mode: c |
| ** c-file-style: "python" |
| ** End: |
| */ |
| /programs/develop/tinypy/std_modules/re/regexpr.h |
|---|
| 0,0 → 1,160 |
| /* |
| * -*- mode: c-mode; c-file-style: python -*- |
| */ |
| #ifndef Py_REGEXPR_H |
| #define Py_REGEXPR_H |
| #ifdef __cplusplus |
| extern "C" { |
| #endif |
| /* |
| * regexpr.h |
| * |
| * Author: Tatu Ylonen <ylo@ngs.fi> |
| * |
| * Copyright (c) 1991 Tatu Ylonen, Espoo, Finland |
| * |
| * Permission to use, copy, modify, distribute, and sell this software |
| * and its documentation for any purpose is hereby granted without fee, |
| * provided that the above copyright notice appear in all copies. This |
| * software is provided "as is" without express or implied warranty. |
| * |
| * Created: Thu Sep 26 17:15:36 1991 ylo |
| * Last modified: Mon Nov 4 15:49:46 1991 ylo |
| */ |
| /* $Id$ */ |
| #ifndef REGEXPR_H |
| #define REGEXPR_H |
| #define RE_NREGS 100 /* number of registers available */ |
| typedef struct re_pattern_buffer |
| { |
| unsigned char *buffer; /* compiled pattern */ |
| int allocated; /* allocated size of compiled pattern */ |
| int used; /* actual length of compiled pattern */ |
| unsigned char *fastmap; /* fastmap[ch] is true if ch can start pattern */ |
| unsigned char *translate; /* translation to apply during compilation/matching */ |
| unsigned char fastmap_accurate; /* true if fastmap is valid */ |
| unsigned char can_be_null; /* true if can match empty string */ |
| unsigned char uses_registers; /* registers are used and need to be initialized */ |
| int num_registers; /* number of registers used */ |
| unsigned char anchor; /* anchor: 0=none 1=begline 2=begbuf */ |
| } *regexp_t; |
| typedef struct re_registers |
| { |
| int start[RE_NREGS]; /* start offset of region */ |
| int end[RE_NREGS]; /* end offset of region */ |
| } *regexp_registers_t; |
| /* bit definitions for syntax */ |
| #define RE_NO_BK_PARENS 1 /* no quoting for parentheses */ |
| #define RE_NO_BK_VBAR 2 /* no quoting for vertical bar */ |
| #define RE_BK_PLUS_QM 4 /* quoting needed for + and ? */ |
| #define RE_TIGHT_VBAR 8 /* | binds tighter than ^ and $ */ |
| #define RE_NEWLINE_OR 16 /* treat newline as or */ |
| #define RE_CONTEXT_INDEP_OPS 32 /* ^$?*+ are special in all contexts */ |
| #define RE_ANSI_HEX 64 /* ansi sequences (\n etc) and \xhh */ |
| #define RE_NO_GNU_EXTENSIONS 128 /* no gnu extensions */ |
| #define TP_RE_NOERR 0 |
| #define TP_RE_UNKNOWN_OPCODE (-1) |
| #define TP_RE_JUMP_OUT_BOUNDS 1 |
| #define TP_RE_QUOTE_ERR 2 |
| /* definitions for some common regexp styles */ |
| #define RE_SYNTAX_AWK (RE_NO_BK_PARENS|RE_NO_BK_VBAR|RE_CONTEXT_INDEP_OPS) |
| #define RE_SYNTAX_EGREP (RE_SYNTAX_AWK|RE_NEWLINE_OR) |
| #define RE_SYNTAX_GREP (RE_BK_PLUS_QM|RE_NEWLINE_OR) |
| #define RE_SYNTAX_EMACS 0 |
| #define Sword 1 |
| #define Swhitespace 2 |
| #define Sdigit 4 |
| #define Soctaldigit 8 |
| #define Shexdigit 16 |
| /* Rename all exported symbols to avoid conflicts with similarly named |
| symbols in some systems' standard C libraries... */ |
| #define re_syntax _Py_re_syntax |
| #define re_syntax_table _Py_re_syntax_table |
| #define re_compile_initialize _Py_re_compile_initialize |
| #define re_set_syntax _Py_re_set_syntax |
| #define re_compile_pattern _Py_re_compile_pattern |
| #define re_match _Py_re_match |
| #define re_search _Py_re_search |
| #define re_compile_fastmap _Py_re_compile_fastmap |
| #define re_comp _Py_re_comp |
| #define re_exec _Py_re_exec |
| #ifdef HAVE_PROTOTYPES |
| extern int re_syntax; |
| /* This is the actual syntax mask. It was added so that Python could do |
| * syntax-dependent munging of patterns before compilation. */ |
| extern unsigned char re_syntax_table[256]; |
| void re_compile_initialize(void); |
| int re_set_syntax(int syntax); |
| /* This sets the syntax to use and returns the previous syntax. The |
| * syntax is specified by a bit mask of the above defined bits. */ |
| char *re_compile_pattern(unsigned char *regex, int regex_size, regexp_t compiled); |
| /* This compiles the regexp (given in regex and length in regex_size). |
| * This returns NULL if the regexp compiled successfully, and an error |
| * message if an error was encountered. The buffer field must be |
| * initialized to a memory area allocated by malloc (or to NULL) before |
| * use, and the allocated field must be set to its length (or 0 if |
| * buffer is NULL). Also, the translate field must be set to point to a |
| * valid translation table, or NULL if it is not used. */ |
| int re_match(regexp_t compiled, unsigned char *string, int size, int pos, |
| regexp_registers_t old_regs); |
| /* This tries to match the regexp against the string. This returns the |
| * length of the matched portion, or -1 if the pattern could not be |
| * matched and -2 if an error (such as failure stack overflow) is |
| * encountered. */ |
| int re_search(regexp_t compiled, unsigned char *string, int size, int startpos, |
| int range, regexp_registers_t regs); |
| /* This searches for a substring matching the regexp. This returns the |
| * first index at which a match is found. range specifies at how many |
| * positions to try matching; positive values indicate searching |
| * forwards, and negative values indicate searching backwards. mstop |
| * specifies the offset beyond which a match must not go. This returns |
| * -1 if no match is found, and -2 if an error (such as failure stack |
| * overflow) is encountered. */ |
| void re_compile_fastmap(regexp_t compiled); |
| /* This computes the fastmap for the regexp. For this to have any effect, |
| * the calling program must have initialized the fastmap field to point |
| * to an array of 256 characters. */ |
| #else /* HAVE_PROTOTYPES */ |
| extern int re_syntax; |
| extern unsigned char re_syntax_table[256]; |
| void re_compile_initialize(); |
| int re_set_syntax(); |
| char *re_compile_pattern(); |
| int re_match(); |
| int re_search(); |
| void re_compile_fastmap(); |
| #endif /* HAVE_PROTOTYPES */ |
| #endif /* REGEXPR_H */ |
| #ifdef __cplusplus |
| } |
| #endif |
| #endif /* !Py_REGEXPR_H */ |
| /programs/develop/tinypy/std_modules/re/tests.py |
|---|
| 0,0 → 1,648 |
| """ |
| test case for re module |
| """ |
| import re |
| import testsuite |
| SUCCEED, FAIL, SYNTAX_ERROR = range(3) |
| def RAISE(): |
| raise("testing failed") |
| def main(): |
| #print("begin re tests") |
| assert(re.__name__ != None) |
| assert(re.__doc__ != None) |
| assert(re.__file__ != None) |
| test_re_obj_search() |
| test_re_obj_match() |
| test_re_mod_search() |
| test_re_mod_match() |
| test_re_obj_split() |
| test_re_mod_split() |
| test_re_obj_findall() |
| test_re_mod_findall() |
| test_mat_obj_groups() |
| test_mat_obj_start() |
| test_mat_obj_end() |
| test_mat_obj_span() |
| print("#OK: re tests passed") |
| def test_re_obj_search(verbose = None): |
| """ |
| some tests borrowed from cpython |
| testing re.compile(), reobj.search(), and matobj.group() |
| """ |
| regex_tests = testsuite.search_regex_tests |
| for t in regex_tests: |
| pattern=s=outcome=repl=expected=None |
| if len(t)==5: |
| pattern, s, outcome, repl, expected = t |
| elif len(t)==3: |
| pattern, s, outcome = t |
| else: |
| raise ('Test tuples should have 3 or 5 fields',t) |
| try: |
| obj=re.compile(pattern) |
| except: |
| if outcome==SYNTAX_ERROR: continue # Expected a syntax error |
| else: |
| # Regex syntax errors aren't yet reported, so for |
| # the official test suite they'll be quietly ignored. |
| pass |
| try: |
| matobj=obj.search(s) |
| except: |
| print('=== Unexpected exception:', obj, matobj, pattern, s) |
| RAISE() |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| pass |
| elif outcome==FAIL: |
| if matobj==None: pass # No match, as expected |
| else: print('=== Succeeded incorrectly', obj, matobj, pattern, s) |
| elif outcome==SUCCEED: |
| if matobj!=None: |
| # Matched, as expected, so now we compute the |
| # result string and compare it to our expected result. |
| found=matobj.group(0) |
| repl = repl.replace("found", str(found)) |
| for i in range(1,11): |
| if "g"+str(i) in repl: |
| gi = str(matobj.group(i)) |
| repl = repl.replace("g"+str(i), gi) |
| if len(t) == 5: |
| repl = repl.replace('+', '') |
| repl = repl.replace('\"', '') |
| if repl!=expected: |
| print( '=== grouping error', t, |
| str(repl)+' should be '+str(expected)) |
| RAISE() |
| else: |
| print ('=== Failed incorrectly', t) |
| def test_re_obj_match(verbose = None): |
| """ |
| some tests borrowed from cpython |
| testing re.compile(), reobj.match() and matobj.group() |
| """ |
| regex_tests = testsuite.match_regex_tests |
| for t in regex_tests: |
| pattern=s=outcome=repl=expected=None |
| if len(t)==5: |
| pattern, s, outcome, repl, expected = t |
| elif len(t)==3: |
| pattern, s, outcome = t |
| else: |
| raise ('Test tuples should have 3 or 5 fields',t) |
| try: |
| obj=re.compile(pattern) |
| except: |
| if outcome==SYNTAX_ERROR: continue # Expected a syntax error |
| else: |
| # Regex syntax errors aren't yet reported, so for |
| # the official test suite they'll be quietly ignored. |
| pass |
| try: |
| matobj=obj.match(s) |
| except: |
| print('=== Unexpected exception:', obj, matobj, pattern, s) |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| pass |
| elif outcome==FAIL: |
| if matobj==None: pass # No match, as expected |
| else: print('=== Succeeded incorrectly', obj, matobj, pattern, s) |
| elif outcome==SUCCEED: |
| if matobj!=None: |
| # Matched, as expected, so now we compute the |
| # result string and compare it to our expected result. |
| found=matobj.group(0) |
| repl = repl.replace("found", str(found)) |
| for i in range(1,11): |
| if "g"+str(i) in repl: |
| gi = str(matobj.group(i)) |
| repl = repl.replace("g"+str(i), gi) |
| if len(t) == 5: |
| repl = repl.replace('+', '') |
| repl = repl.replace('\"', '') |
| if repl!=expected: |
| print( '=== grouping error', t, |
| str(repl)+' should be '+str(expected)) |
| RAISE() |
| else: |
| print ('=== Failed incorrectly', obj, matobj, pattern, s) |
| def test_re_mod_search(verbose = None): |
| """ |
| some tests borrowed from cpython |
| testing re.search(), and matobj.group() |
| """ |
| regex_tests = testsuite.search_regex_tests |
| for t in regex_tests: |
| pattern=s=outcome=repl=expected=None |
| if len(t)==5: |
| pattern, s, outcome, repl, expected = t |
| elif len(t)==3: |
| pattern, s, outcome = t |
| else: |
| raise ('Test tuples should have 3 or 5 fields',t) |
| try: |
| matobj=re.search(pattern, s) |
| except: |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| pass |
| else: |
| print('=== Unexpected exception:', matobj, pattern, s) |
| if outcome==FAIL: |
| if matobj==None: pass # No match, as expected |
| else: print('=== Succeeded incorrectly', obj, matobj, pattern, s) |
| elif outcome==SUCCEED: |
| if matobj!=None: |
| # Matched, as expected, so now we compute the |
| # result string and compare it to our expected result. |
| found=matobj.group(0) |
| repl = repl.replace("found", str(found)) |
| for i in range(1,11): |
| if "g"+str(i) in repl: |
| gi = str(matobj.group(i)) |
| repl = repl.replace("g"+str(i), gi) |
| if len(t) == 5: |
| repl = repl.replace('+', '') |
| repl = repl.replace('\"', '') |
| if repl!=expected: |
| print( '=== grouping error', t, |
| str(repl)+' should be '+str(expected)) |
| RAISE() |
| else: |
| print ('=== Failed incorrectly', t) |
| def test_re_mod_match(verbose = None): |
| """ |
| some tests borrowed from cpython |
| testing re.match(), and matobj.group() |
| """ |
| regex_tests = testsuite.match_regex_tests |
| for t in regex_tests: |
| pattern=s=outcome=repl=expected=None |
| if len(t)==5: |
| pattern, s, outcome, repl, expected = t |
| elif len(t)==3: |
| pattern, s, outcome = t |
| else: |
| raise ('Test tuples should have 3 or 5 fields',t) |
| try: |
| matobj=re.match(pattern, s) |
| except: |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| pass |
| else: |
| print('=== Unexpected exception:', matobj, pattern, s) |
| if outcome==FAIL: |
| if matobj==None: pass # No match, as expected |
| else: print('=== Succeeded incorrectly', matobj, pattern, s) |
| elif outcome==SUCCEED: |
| if matobj!=None: |
| # Matched, as expected, so now we compute the |
| # result string and compare it to our expected result. |
| found=matobj.group(0) |
| repl = repl.replace("found", str(found)) |
| for i in range(1,11): |
| if "g"+str(i) in repl: |
| gi = str(matobj.group(i)) |
| repl = repl.replace("g"+str(i), gi) |
| if len(t) == 5: |
| repl = repl.replace('+', '') |
| repl = repl.replace('\"', '') |
| if repl!=expected: |
| print( '=== grouping error', t, |
| str(repl)+' should be '+str(expected)) |
| RAISE() |
| else: |
| print ('=== Failed incorrectly', t) |
| def test_re_obj_split(verbose = None): |
| """ |
| test re.compile(), and reobj.split() |
| """ |
| regex_tests = testsuite.split_regex_tests |
| for t in regex_tests: |
| pattern, s, outcome, maxsplit, fields = t |
| try: |
| reobj = re.compile(pattern) |
| except: |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| pass |
| else: |
| print('=== Unexpected exception:', pattern, s, |
| outcome, maxsplit, fields) |
| try: |
| fldlst=reobj.split(s, maxsplit) |
| except: |
| if outcome == SYNTAX_ERROR: |
| continue |
| else: |
| print('=== Unexpected exception:', pattern, s, |
| outcome, maxsplit, fields) |
| if outcome==FAIL: |
| pass # No match, as expected |
| elif outcome==SUCCEED: |
| if fldlst: |
| # Matched, as expected, so now we compute the |
| # result string and compare it to our expected result. |
| if verbose: |
| fldstr = fieldstr = "" |
| for item in fldlst: |
| fldstr = fldstr + str(item) + " | " |
| for item in fields: |
| fieldstr = fieldstr + str(item) + " | " |
| print(fldstr, "~~~", fieldstr) |
| if len(fields) != len(fldlst): |
| print('=== Not coherent 1') |
| RAISE() |
| for i in range(len(fields)): |
| if fields[i] != fldlst[i]: |
| if verbose: |
| print('=== Not coherent 2', pattern, s, |
| outcome, maxsplit, fields, i, |
| fields[i],'(',len(fields[i]),')', ' | ', |
| fldlst[i],'(',len(fldlst[i]),')') |
| else: |
| print('=== Not coherent 2') |
| RAISE() |
| else: |
| print ('=== Failed incorrectly', pattern, s, |
| outcome, maxsplit, fields) |
| def test_re_mod_split(verbose = None): |
| """ |
| test re.split() |
| """ |
| regex_tests = testsuite.split_regex_tests |
| for t in regex_tests: |
| pattern, s, outcome, maxsplit, fields = t |
| try: |
| fldlst=re.split(pattern, s, maxsplit) |
| except: |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| continue |
| else: |
| print('=== Unexpected exception:', pattern, s, |
| outcome, maxsplit, fields) |
| if outcome==FAIL: |
| pass # No match, as expected |
| elif outcome==SUCCEED: |
| if fldlst: |
| # Matched, as expected, so now we compute the |
| # result string and compare it to our expected result. |
| if verbose: |
| fldstr = fieldstr = "" |
| for item in fldlst: |
| fldstr = fldstr + str(item) + " | " |
| for item in fields: |
| fieldstr = fieldstr + str(item) + " | " |
| print(fldstr, "~~~", fieldstr) |
| if len(fields) != len(fldlst): |
| print('=== Not coherent 1') |
| RAISE() |
| for i in range(len(fields)): |
| if fields[i] != fldlst[i]: |
| if verbose: |
| print('=== Not coherent 2', pattern, s, |
| outcome, maxsplit, fields, i, |
| fields[i],'(',len(fields[i]),')', ' | ', |
| fldlst[i],'(',len(fldlst[i]),')') |
| else: |
| print('=== Not coherent 2') |
| RAISE() |
| else: |
| print ('=== Failed incorrectly', pattern, s, |
| outcome, maxsplit, fields) |
| def test_re_obj_findall(verbose = None): |
| """ |
| test re.compile(), and reobj.findall() |
| """ |
| regex_tests = testsuite.findall_regex_tests |
| for t in regex_tests: |
| pattern, s, outcome, pos, fields = t |
| try: |
| reobj = re.compile(pattern) |
| except: |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| pass |
| else: |
| print('=== Unexpected exception:', pattern, s, |
| outcome, pos, fields) |
| try: |
| fldlst=reobj.findall(s, pos) |
| except: |
| if outcome == SYNTAX_ERROR: |
| continue |
| else: |
| print('=== Unexpected exception:', pattern, s, |
| outcome, pos, fields) |
| if outcome==FAIL: |
| pass # No match, as expected |
| elif outcome==SUCCEED: |
| if fldlst: |
| # Matched, as expected, so now we compute the |
| # result string and compare it to our expected result. |
| if verbose: |
| fldstr = fieldstr = "" |
| for item in fldlst: |
| fldstr = fldstr + str(item) + " | " |
| for item in fields: |
| fieldstr = fieldstr + str(item) + " | " |
| print(fldstr, "~~~", fieldstr) |
| if len(fields) != len(fldlst): |
| print('=== Not coherent 1') |
| RAISE() |
| for i in range(len(fields)): |
| if fields[i] != fldlst[i]: |
| if verbose: |
| print('=== Not coherent 2', pattern, s, |
| outcome, maxsplit, fields, i, |
| fields[i],'(',len(fields[i]),')', ' | ', |
| fldlst[i],'(',len(fldlst[i]),')') |
| else: |
| print('=== Not coherent 2') |
| RAISE() |
| else: |
| print ('=== Failed incorrectly', pattern, s, |
| outcome, pos, fields) |
| def test_re_mod_findall(verbose = None): |
| """ |
| test re.findall() |
| """ |
| regex_tests = testsuite.mod_findall_regex_tests |
| for t in regex_tests: |
| pattern, s, outcome, pos, fields = t # pos is not used |
| try: |
| fldlst=re.findall(pattern, s) |
| except: |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| continue |
| else: |
| print('=== Unexpected exception:', pattern, s, |
| outcome, pos, fields) |
| if outcome==FAIL: |
| pass # No match, as expected |
| elif outcome==SUCCEED: |
| if fldlst: |
| # Matched, as expected, so now we compute the |
| # result string and compare it to our expected result. |
| if verbose: |
| fldstr = fieldstr = "" |
| for item in fldlst: |
| fldstr = fldstr + str(item) + " | " |
| for item in fields: |
| fieldstr = fieldstr + str(item) + " | " |
| print(fldstr, "~~~", fieldstr) |
| if len(fields) != len(fldlst): |
| print('=== Not coherent 1') |
| RAISE() |
| for i in range(len(fields)): |
| if fields[i] != fldlst[i]: |
| if verbose: |
| print('=== Not coherent 2', pattern, s, |
| outcome, maxsplit, fields, i, |
| fields[i],'(',len(fields[i]),')', ' | ', |
| fldlst[i],'(',len(fldlst[i]),')') |
| else: |
| print('=== Not coherent 2') |
| RAISE() |
| else: |
| print ('=== Failed incorrectly', pattern, s, |
| outcome, pos, fields) |
| def test_mat_obj_groups(verbose = None): |
| """ |
| test re.search(), and matobj.groups() |
| 'verbose' is for debugging, when 'verbose' is true, print extra info |
| """ |
| regex_tests = testsuite.matobj_groups_regex_tests |
| for t in regex_tests: |
| pattern, s, outcome, fields, grpidx, start, end = t |
| try: |
| matobj=re.search(pattern, s) |
| except: |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| continue |
| else: |
| print('=== Unexpected exception 1:', pattern, s, |
| outcome,fields) |
| try: |
| if outcome==SUCCEED: assert(matobj != None) |
| fldlst = matobj.groups() |
| except: |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| continue |
| else: |
| print('=== Unexpected exception 2:', pattern, s, |
| outcome,fields) |
| if outcome==FAIL: |
| pass # No match, as expected |
| elif outcome==SUCCEED: |
| if fldlst and fields: |
| # Matched, as expected, so now we compute the |
| # result string and compare it to our expected result. |
| if verbose: |
| fldstr = fieldstr = "" |
| for item in fldlst: |
| fldstr = fldstr + str(item) + " | " |
| for item in fields: |
| fieldstr = fieldstr + str(item) + " | " |
| print(fldstr, "~~~", fieldstr) |
| if len(fields) != len(fldlst): |
| print('=== Not coherent 2') |
| RAISE() |
| for i in range(len(fields)): |
| if fields[i] != fldlst[i]: |
| if verbose: |
| print('=== Not coherent', pattern, s, |
| outcome,fields, i, |
| fields[i],'(',len(fields[i]),')', ' | ', |
| fldlst[i],'(',len(fldlst[i]),')') |
| else: |
| print('=== Not coherent') |
| RAISE() |
| elif not len(fldlst) and not len(fields): |
| # output is empty, as expected |
| if verbose: |
| print("output is empty, as expected") |
| continue |
| else: |
| if verbose: |
| for item in fldlst: |
| print(item,) |
| print() |
| for item in fields: |
| print(item,) |
| print() |
| print ('=== Failed incorrectly', pattern, s, |
| outcome,fields,fldlst) |
| def test_mat_obj_start(verbose = None): |
| """ |
| test re.search(), and matobj.start() |
| 'verbose' is for debugging, when 'verbose' is true, print extra info |
| """ |
| regex_tests = testsuite.matobj_groups_regex_tests |
| for t in regex_tests: |
| pattern, s, outcome, fields, grpidx, start, end = t |
| try: |
| matobj=re.search(pattern, s) |
| except: |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| continue |
| else: |
| print('=== Unexpected exception 1:', pattern, s, |
| outcome,fields) |
| try: |
| if outcome==SUCCEED: assert(matobj != None) |
| fldlst = matobj.groups() |
| except: |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| continue |
| else: |
| print('=== Unexpected exception 2:', pattern, s, |
| outcome,fields) |
| if outcome==FAIL: |
| pass # No match, as expected |
| elif outcome==SUCCEED: |
| if grpidx > 0: |
| if matobj.start(grpidx) == start: |
| pass |
| else: |
| if verbose: |
| print ('=== Failed incorrectly', pattern, s, |
| outcome,fields,fldlst) |
| raise("testing failed") |
| def test_mat_obj_end(verbose = None): |
| """ |
| test re.search(), and matobj.end() |
| 'verbose' is for debugging, when 'verbose' is true, print extra info |
| """ |
| regex_tests = testsuite.matobj_groups_regex_tests |
| for t in regex_tests: |
| pattern, s, outcome, fields, grpidx, start, end = t |
| try: |
| matobj=re.search(pattern, s) |
| except: |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| continue |
| else: |
| print('=== Unexpected exception 1:', pattern, s, |
| outcome,fields) |
| try: |
| if outcome==SUCCEED: assert(matobj != None) |
| fldlst = matobj.groups() |
| except: |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| continue |
| else: |
| print('=== Unexpected exception 2:', pattern, s, |
| outcome,fields) |
| if outcome==FAIL: |
| pass # No match, as expected |
| elif outcome==SUCCEED: |
| if grpidx > 0: |
| if matobj.end(grpidx) == end: |
| pass |
| else: |
| if verbose: |
| print ('=== Failed incorrectly', pattern, s, |
| outcome,fields,fldlst, matobj.end(grpidx), end) |
| raise("testing failed") |
| def test_mat_obj_span(verbose = None): |
| """ |
| test re.search(), and matobj.span() |
| 'verbose' is for debugging, when 'verbose' is true, print extra info |
| """ |
| regex_tests = testsuite.matobj_groups_regex_tests |
| for t in regex_tests: |
| pattern, s, outcome, fields, grpidx, start, end = t |
| try: |
| matobj=re.search(pattern, s) |
| except: |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| continue |
| else: |
| print('=== Unexpected exception 1:', pattern, s, |
| outcome,fields) |
| try: |
| if outcome==SUCCEED: assert(matobj != None) |
| fldlst = matobj.groups() |
| except: |
| if outcome==SYNTAX_ERROR: |
| # This should have been a syntax error; forget it. |
| continue |
| else: |
| print('=== Unexpected exception 2:', pattern, s, |
| outcome,fields) |
| if outcome==FAIL: |
| pass # No match, as expected |
| elif outcome==SUCCEED: |
| if (grpidx > 0): |
| spstart, spend = matobj.span(grpidx) |
| if spstart == start and spend == end: |
| pass |
| else: |
| if verbose: |
| print ('=== Failed incorrectly', pattern, s, |
| outcome,fields,fldlst) |
| raise("testing failed") |
| if __name__ == "__main__": |
| main() |
| /programs/develop/tinypy/std_modules/re/testsuite.py |
|---|
| 0,0 → 1,367 |
| # Test suite (for verifying correctness) |
| # |
| # The test suite is a list of 5- or 3-tuples. The 5 parts of a |
| # complete tuple are: |
| # element 0: a string containing the pattern |
| # 1: the string to match against the pattern |
| # 2: the expected result (0 - SUCCEED, 1 - FAIL, 2 - SYNTAX_ERROR) |
| # 3: a string that will be eval()'ed to produce a test string. |
| # This is an arbitrary Python expression; the available |
| # variables are "found" (the whole match), and "g1", "g2", ... |
| # up to "g10" contain the contents of each group, or the |
| # string 'None' if the group wasn't given a value. |
| # 4: The expected result of evaluating the expression. |
| # If the two don't match, an error is reported. |
| # |
| # If the regex isn't expected to work, the latter two elements can be omitted. |
| # test suite for search |
| search_regex_tests=[ |
| ['abc', 'abc', 0, 'found', 'abc'], |
| ['abc', 'xbc', 1], |
| ['abc', 'axc', 1], |
| ['abc', 'abx', 1], |
| ['abc', 'xabcy', 0, 'found', 'abc'], |
| ['abc', 'ababc', 0, 'found', 'abc'], |
| ['ab*c', 'abc', 0, 'found', 'abc'], |
| ['ab*bc', 'abc', 0, 'found', 'abc'], |
| ['ab*bc', 'abbc', 0, 'found', 'abbc'], |
| ['ab*bc', 'abbbbc', 0, 'found', 'abbbbc'], |
| ['ab+bc', 'abbc', 0, 'found', 'abbc'], |
| ['ab+bc', 'abc', 1], |
| ['ab+bc', 'abq', 1], |
| ['ab+bc', 'abbbbc', 0, 'found', 'abbbbc'], |
| ['ab?bc', 'abbc', 0, 'found', 'abbc'], |
| ['ab?bc', 'abc', 0, 'found', 'abc'], |
| ['ab?bc', 'abbbbc', 1], |
| ['ab?c', 'abc', 0, 'found', 'abc'], |
| ['^abc$', 'abc', 0, 'found', 'abc'], |
| ['^abc$', 'abcc', 1], |
| ['^abc', 'abcc', 0, 'found', 'abc'], |
| ['^abc$', 'aabc', 1], |
| ['abc$', 'aabc', 0, 'found', 'abc'], |
| ['^', 'abc', 0, 'found+"-"', '-'], |
| ['$', 'abc', 0, 'found+"-"', '-'], |
| ['a.c', 'abc', 0, 'found', 'abc'], |
| ['a.c', 'axc', 0, 'found', 'axc'], |
| ['a.*c', 'axyzc', 0, 'found', 'axyzc'], |
| ['a.*c', 'axyzd', 1], |
| ['a[bc]d', 'abc', 1], |
| ['a[bc]d', 'abd', 0, 'found', 'abd'], |
| ['a[b-d]e', 'abd', 1], |
| ['a[b-d]e', 'ace', 0, 'found', 'ace'], |
| ['a[b-d]', 'aac', 0, 'found', 'ac'], |
| ['a[-b]', 'a-', 0, 'found', 'a-'], |
| ['a[b-]', 'a-', 0, 'found', 'a-'], |
| ['a[]b', '-', 2], |
| ['a[', '-', 2], |
| ['a\\', '-', 2], |
| ['abc\\)', '-', 2], |
| ['\\(abc', '-', 2], |
| ['a]', 'a]', 0, 'found', 'a]'], |
| ['a[]]b', 'a]b', 0, 'found', 'a]b'], |
| ['a[^bc]d', 'aed', 0, 'found', 'aed'], |
| ['a[^bc]d', 'abd', 1], |
| ['a[^-b]c', 'adc', 0, 'found', 'adc'], |
| ['a[^-b]c', 'a-c', 1], |
| ['a[^]b]c', 'a]c', 1], |
| ['a[^]b]c', 'adc', 0, 'found', 'adc'], |
| ['\\ba\\b', 'a-', 0, '"-"', '-'], |
| ['\\ba\\b', '-a', 0, '"-"', '-'], |
| ['\\ba\\b', '-a-', 0, '"-"', '-'], |
| ['\\by\\b', 'xy', 1], |
| ['\\by\\b', 'yz', 1], |
| ['\\by\\b', 'xyz', 1], |
| ['ab\\|cd', 'abc', 0, 'found', 'ab'], |
| ['ab\\|cd', 'abcd', 0, 'found', 'ab'], |
| ['\\(\\)ef', 'def', 0, 'found+"-"+g1', 'ef-'], |
| ['$b', 'b', 1], |
| ['a(b', 'a(b', 0, 'found+"-"+g1', 'a(b-None'], |
| ['a(*b', 'ab', 0, 'found', 'ab'], |
| ['a(*b', 'a((b', 0, 'found', 'a((b'], |
| ['a\\\\b', 'a\\b', 0, 'found', 'a\\b'], |
| ['\\(\\(a\\)\\)', 'abc', 0, 'found+"-"+g1+"-"+g2', 'a-a-a'], |
| ['\\(a\\)b\\(c\\)', 'abc', 0, 'found+"-"+g1+"-"+g2', 'abc-a-c'], |
| ['a+b+c', 'aabbabc', 0, 'found', 'abc'], |
| ['\\(a+\\|b\\)*', 'ab', 0, 'found+"-"+g1', 'ab-b'], |
| ['\\(a+\\|b\\)+', 'ab', 0, 'found+"-"+g1', 'ab-b'], |
| ['\\(a+\\|b\\)?', 'ab', 0, 'found+"-"+g1', 'a-a'], |
| ['\\)\\(', '-', 2], |
| ['[^ab]*', 'cde', 0, 'found', 'cde'], |
| ['abc', '', 1], |
| ['a*', '', 0, 'found', ''], |
| ['a\\|b\\|c\\|d\\|e', 'e', 0, 'found', 'e'], |
| ['\\(a\\|b\\|c\\|d\\|e\\)f', 'ef', 0, 'found+"-"+g1', 'ef-e'], |
| ['abcd*efg', 'abcdefg', 0, 'found', 'abcdefg'], |
| ['ab*', 'xabyabbbz', 0, 'found', 'ab'], |
| ['ab*', 'xayabbbz', 0, 'found', 'a'], |
| ['\\(ab\\|cd\\)e', 'abcde', 0, 'found+"-"+g1', 'cde-cd'], |
| ['[abhgefdc]ij', 'hij', 0, 'found', 'hij'], |
| ['^\\(ab\\|cd\\)e', 'abcde', 1, 'xg1y', 'xy'], |
| ['\\(abc\\|\\)ef', 'abcdef', 0, 'found+"-"+g1', 'ef-'], |
| ['\\(a\\|b\\)c*d', 'abcd', 0, 'found+"-"+g1', 'bcd-b'], |
| ['\\(ab\\|ab*\\)bc', 'abc', 0, 'found+"-"+g1', 'abc-a'], |
| ['a\\([bc]*\\)c*', 'abc', 0, 'found+"-"+g1', 'abc-bc'], |
| ['a\\([bc]*\\)\\(c*d\\)', 'abcd', 0, 'found+"-"+g1+"-"+g2', 'abcd-bc-d'], |
| ['a\\([bc]+\\)\\(c*d\\)', 'abcd', 0, 'found+"-"+g1+"-"+g2', 'abcd-bc-d'], |
| ['a\\([bc]*\\)\\(c+d\\)', 'abcd', 0, 'found+"-"+g1+"-"+g2', 'abcd-b-cd'], |
| ['a[bcd]*dcdcde', 'adcdcde', 0, 'found', 'adcdcde'], |
| ['a[bcd]+dcdcde', 'adcdcde', 1], |
| ['\\(ab\\|a\\)b*c', 'abc', 0, 'found+"-"+g1', 'abc-ab'], |
| ['\\(\\(a\\)\\(b\\)c\\)\\(d\\)', 'abcd', 0, 'g1+"-"+g2+"-"+g3+"-"+g4', 'abc-a-b-d'], |
| ['[a-zA-Z_][a-zA-Z0-9_]*', 'alpha', 0, 'found', 'alpha'], |
| ['^a\\(bc+\\|b[eh]\\)g\\|.h$', 'abh', 0, 'found+"-"+g1', 'bh-None'], |
| ['\\(bc+d$\\|ef*g.\\|h?i\\(j\\|k\\)\\)', 'effgz', 0, 'found+"-"+g1+"-"+g2', 'effgz-effgz-None'], |
| ['\\(bc+d$\\|ef*g.\\|h?i\\(j\\|k\\)\\)', 'ij', 0, 'found+"-"+g1+"-"+g2', 'ij-ij-j'], |
| ['\\(bc+d$\\|ef*g.\\|h?i\\(j\\|k\\)\\)', 'effg', 1], |
| ['\\(bc+d$\\|ef*g.\\|h?i\\(j\\|k\\)\\)', 'bcdd', 1], |
| ['\\(bc+d$\\|ef*g.\\|h?i\\(j\\|k\\)\\)', 'reffgz', 0, 'found+"-"+g1+"-"+g2', 'effgz-effgz-None'], |
| ['\\(\\(\\(\\(\\(\\(\\(\\(\\(a\\)\\)\\)\\)\\)\\)\\)\\)\\)', 'a', 0, 'found', 'a'], |
| ['multiple words of text', 'uh-uh', 1], |
| ['multiple words', 'multiple words, yeah', 0, 'found', 'multiple words'], |
| ['\\(.*\\)c\\(.*\\)', 'abcde', 0, 'found+"-"+g1+"-"+g2', 'abcde-ab-de'], |
| ['(\\(.*\\), \\(.*\\))', '(a, b)', 0, 'g2+"-"+g1', 'b-a'], |
| ['[k]', 'ab', 1], |
| ['a[-]?c', 'ac', 0, 'found', 'ac'], |
| ['\\(abc\\)\\1', 'abcabc', 0, 'g1', 'abc'], |
| ['\\([a-c]*\\)\\1', 'abcabc', 0, 'g1', 'abc'], |
| ['^\\(.+\\)?B', 'AB', 0, 'g1', 'A'], |
| ['\\(a+\\).\\1$', 'aaaaa', 0, 'found+"-"+g1', 'aaaaa-aa'], |
| ['^\\(a+\\).\\1$', 'aaaa', 1], |
| ['\\(abc\\)\\1', 'abcabc', 0, 'found+"-"+g1', 'abcabc-abc'], |
| ['\\([a-c]+\\)\\1', 'abcabc', 0, 'found+"-"+g1', 'abcabc-abc'], |
| ['\\(a\\)\\1', 'aa', 0, 'found+"-"+g1', 'aa-a'], |
| ['\\(a+\\)\\1', 'aa', 0, 'found+"-"+g1', 'aa-a'], |
| ['\\(a+\\)+\\1', 'aa', 0, 'found+"-"+g1', 'aa-a'], |
| ['\\(a\\).+\\1', 'aba', 0, 'found+"-"+g1', 'aba-a'], |
| ['\\(a\\)ba*\\1', 'aba', 0, 'found+"-"+g1', 'aba-a'], |
| ['\\(aa\\|a\\)a\\1$', 'aaa', 0, 'found+"-"+g1', 'aaa-a'], |
| ['\\(a\\|aa\\)a\\1$', 'aaa', 0, 'found+"-"+g1', 'aaa-a'], |
| ['\\(a+\\)a\\1$', 'aaa', 0, 'found+"-"+g1', 'aaa-a'], |
| ['\\([abc]*\\)\\1', 'abcabc', 0, 'found+"-"+g1', 'abcabc-abc'], |
| ['\\(a\\)\\(b\\)c\\|ab', 'ab', 0, 'found+"-"+g1+"-"+g2', 'ab-None-None'], |
| ['\\(a\\)+x', 'aaax', 0, 'found+"-"+g1', 'aaax-a'], |
| ['\\([ac]\\)+x', 'aacx', 0, 'found+"-"+g1', 'aacx-c'], |
| ['\\([^/]*/\\)*sub1/', 'd:msgs/tdir/sub1/trial/away.cpp', 0, 'found+"-"+g1', 'd:msgs/tdir/sub1/-tdir/'], |
| ['\\([^.]*\\)\\.\\([^:]*\\):[T ]+\\(.*\\)', 'track1.title:TBlah blah blah', 0, 'found+"-"+g1+"-"+g2+"-"+g3', 'track1.title:TBlah blah blah-track1-title-Blah blah blah'], |
| ['\\([^N]*N\\)+', 'abNNxyzN', 0, 'found+"-"+g1', 'abNNxyzN-xyzN'], |
| ['\\([^N]*N\\)+', 'abNNxyz', 0, 'found+"-"+g1', 'abNN-N'], |
| ['\\([abc]*\\)x', 'abcx', 0, 'found+"-"+g1', 'abcx-abc'], |
| ['\\([abc]*\\)x', 'abc', 1], |
| ['\\([xyz]*\\)x', 'abcx', 0, 'found+"-"+g1', 'x-'], |
| ['\\(a\\)+b\\|aac', 'aac', 0, 'found+"-"+g1', 'aac-None'], |
| ['\\<a', 'a', 0, 'found', 'a'], |
| ['\\<a', '!', 1], |
| ['a\\<b', 'ab', 1], |
| ['a\\>', 'ab', 1], |
| ['a\\>', 'a!', 0, 'found', 'a'], |
| ['a\\>', 'a', 0, 'found', 'a'], |
| ] |
| # test suite for match |
| match_regex_tests=[ |
| ['abc', 'abc', 0, 'found', 'abc'], |
| ['abc', 'xbc', 1], |
| ['abc', 'axc', 1], |
| ['abc', 'abx', 1], |
| ['abc', 'xabcy', 1], |
| ['abc', 'ababc', 1], |
| ['ab*c', 'abc', 0, 'found', 'abc'], |
| ['ab*bc', 'abc', 0, 'found', 'abc'], |
| ['ab*bc', 'abbc', 0, 'found', 'abbc'], |
| ['ab*bc', 'abbbbc', 0, 'found', 'abbbbc'], |
| ['ab+bc', 'abbc', 0, 'found', 'abbc'], |
| ['ab+bc', 'abc', 1], |
| ['ab+bc', 'abq', 1], |
| ['ab+bc', 'abbbbc', 0, 'found', 'abbbbc'], |
| ['ab?bc', 'abbc', 0, 'found', 'abbc'], |
| ['ab?bc', 'abc', 0, 'found', 'abc'], |
| ['ab?bc', 'abbbbc', 1], |
| ['ab?c', 'abc', 0, 'found', 'abc'], |
| ['^abc$', 'abc', 0, 'found', 'abc'], |
| ['^abc$', 'abcc', 1], |
| ['^abc', 'abcc', 0, 'found', 'abc'], |
| ['^abc$', 'aabc', 1], |
| ['abc$', 'aabc', 1], |
| ['^', 'abc', 0, 'found+"-"', '-'], |
| ['$', 'abc', 1], |
| ['a.c', 'abc', 0, 'found', 'abc'], |
| ['a.c', 'axc', 0, 'found', 'axc'], |
| ['a.*c', 'axyzc', 0, 'found', 'axyzc'], |
| ['a.*c', 'axyzd', 1], |
| ['a[bc]d', 'abc', 1], |
| ['a[bc]d', 'abd', 0, 'found', 'abd'], |
| ['a[b-d]e', 'abd', 1], |
| ['a[b-d]e', 'ace', 0, 'found', 'ace'], |
| ['a[b-d]', 'aac', 1], |
| ['a[-b]', 'a-', 0, 'found', 'a-'], |
| ['a[b-]', 'a-', 0, 'found', 'a-'], |
| ['a[]b', '-', 2], |
| ['a[', '-', 2], |
| ['a\\', '-', 2], |
| ['abc\\)', '-', 2], |
| ['\\(abc', '-', 2], |
| ['a]', 'a]', 0, 'found', 'a]'], |
| ['a[]]b', 'a]b', 0, 'found', 'a]b'], |
| ['a[^bc]d', 'aed', 0, 'found', 'aed'], |
| ['a[^bc]d', 'abd', 1], |
| ['a[^-b]c', 'adc', 0, 'found', 'adc'], |
| ['a[^-b]c', 'a-c', 1], |
| ['a[^]b]c', 'a]c', 1], |
| ['a[^]b]c', 'adc', 0, 'found', 'adc'], |
| ['\\ba\\b', 'a-', 0, '"-"', '-'], |
| ['\\ba\\b', '-a', 1], |
| ['\\ba\\b', '-a-', 1], |
| ['\\by\\b', 'xy', 1], |
| ['\\by\\b', 'yz', 1], |
| ['\\by\\b', 'xyz', 1], |
| ['ab\\|cd', 'abc', 0, 'found', 'ab'], |
| ['ab\\|cd', 'abcd', 0, 'found', 'ab'], |
| ['\\(\\)ef', 'def', 1], |
| ['$b', 'b', 1], |
| ['a(b', 'a(b', 0, 'found+"-"+g1', 'a(b-None'], |
| ['a(*b', 'ab', 0, 'found', 'ab'], |
| ['a(*b', 'a((b', 0, 'found', 'a((b'], |
| ['a\\\\b', 'a\\b', 0, 'found', 'a\\b'], |
| ['\\(\\(a\\)\\)', 'abc', 0, 'found+"-"+g1+"-"+g2', 'a-a-a'], |
| ['\\(a\\)b\\(c\\)', 'abc', 0, 'found+"-"+g1+"-"+g2', 'abc-a-c'], |
| ['a+b+c', 'aabbabc', 1], |
| ['\\(a+\\|b\\)*', 'ab', 0, 'found+"-"+g1', 'ab-b'], |
| ['\\(a+\\|b\\)+', 'ab', 0, 'found+"-"+g1', 'ab-b'], |
| ['\\(a+\\|b\\)?', 'ab', 0, 'found+"-"+g1', 'a-a'], |
| ['\\)\\(', '-', 2], |
| ['[^ab]*', 'cde', 0, 'found', 'cde'], |
| ['abc', '', 1], |
| ['a*', '', 0, 'found', ''], |
| ['a\\|b\\|c\\|d\\|e', 'e', 0, 'found', 'e'], |
| ['\\(a\\|b\\|c\\|d\\|e\\)f', 'ef', 0, 'found+"-"+g1', 'ef-e'], |
| ['abcd*efg', 'abcdefg', 0, 'found', 'abcdefg'], |
| ['ab*', 'xabyabbbz', 1], |
| ['ab*', 'xayabbbz', 1], |
| ['\\(ab\\|cd\\)e', 'abcde', 1], |
| ['[abhgefdc]ij', 'hij', 0, 'found', 'hij'], |
| ['^\\(ab\\|cd\\)e', 'abcde', 1, 'xg1y', 'xy'], |
| ['\\(abc\\|\\)ef', 'abcdef', 1], |
| ['\\(a\\|b\\)c*d', 'abcd', 1], |
| ['\\(ab\\|ab*\\)bc', 'abc', 0, 'found+"-"+g1', 'abc-a'], |
| ['a\\([bc]*\\)c*', 'abc', 0, 'found+"-"+g1', 'abc-bc'], |
| ['a\\([bc]*\\)\\(c*d\\)', 'abcd', 0, 'found+"-"+g1+"-"+g2', 'abcd-bc-d'], |
| ['a\\([bc]+\\)\\(c*d\\)', 'abcd', 0, 'found+"-"+g1+"-"+g2', 'abcd-bc-d'], |
| ['a\\([bc]*\\)\\(c+d\\)', 'abcd', 0, 'found+"-"+g1+"-"+g2', 'abcd-b-cd'], |
| ['a[bcd]*dcdcde', 'adcdcde', 0, 'found', 'adcdcde'], |
| ['a[bcd]+dcdcde', 'adcdcde', 1], |
| ['\\(ab\\|a\\)b*c', 'abc', 0, 'found+"-"+g1', 'abc-ab'], |
| ['\\(\\(a\\)\\(b\\)c\\)\\(d\\)', 'abcd', 0, 'g1+"-"+g2+"-"+g3+"-"+g4', 'abc-a-b-d'], |
| ['[a-zA-Z_][a-zA-Z0-9_]*', 'alpha', 0, 'found', 'alpha'], |
| ['^a\\(bc+\\|b[eh]\\)g\\|.h$', 'abh', 1], |
| ['\\(bc+d$\\|ef*g.\\|h?i\\(j\\|k\\)\\)', 'effgz', 0, 'found+"-"+g1+"-"+g2', 'effgz-effgz-None'], |
| ['\\(bc+d$\\|ef*g.\\|h?i\\(j\\|k\\)\\)', 'ij', 0, 'found+"-"+g1+"-"+g2', 'ij-ij-j'], |
| ['\\(bc+d$\\|ef*g.\\|h?i\\(j\\|k\\)\\)', 'effg', 1], |
| ['\\(bc+d$\\|ef*g.\\|h?i\\(j\\|k\\)\\)', 'bcdd', 1], |
| ['\\(bc+d$\\|ef*g.\\|h?i\\(j\\|k\\)\\)', 'reffgz', 1], |
| ['\\(\\(\\(\\(\\(\\(\\(\\(\\(a\\)\\)\\)\\)\\)\\)\\)\\)\\)', 'a', 0, 'found', 'a'], |
| ['multiple words of text', 'uh-uh', 1], |
| ['multiple words', 'multiple words, yeah', 0, 'found', 'multiple words'], |
| ['\\(.*\\)c\\(.*\\)', 'abcde', 0, 'found+"-"+g1+"-"+g2', 'abcde-ab-de'], |
| ['(\\(.*\\), \\(.*\\))', '(a, b)', 0, 'g2+"-"+g1', 'b-a'], |
| ['[k]', 'ab', 1], |
| ['a[-]?c', 'ac', 0, 'found', 'ac'], |
| ['\\(abc\\)\\1', 'abcabc', 0, 'g1', 'abc'], |
| ['\\([a-c]*\\)\\1', 'abcabc', 0, 'g1', 'abc'], |
| ['^\\(.+\\)?B', 'AB', 0, 'g1', 'A'], |
| ['\\(a+\\).\\1$', 'aaaaa', 0, 'found+"-"+g1', 'aaaaa-aa'], |
| ['^\\(a+\\).\\1$', 'aaaa', 1], |
| ['\\(abc\\)\\1', 'abcabc', 0, 'found+"-"+g1', 'abcabc-abc'], |
| ['\\([a-c]+\\)\\1', 'abcabc', 0, 'found+"-"+g1', 'abcabc-abc'], |
| ['\\(a\\)\\1', 'aa', 0, 'found+"-"+g1', 'aa-a'], |
| ['\\(a+\\)\\1', 'aa', 0, 'found+"-"+g1', 'aa-a'], |
| ['\\(a+\\)+\\1', 'aa', 0, 'found+"-"+g1', 'aa-a'], |
| ['\\(a\\).+\\1', 'aba', 0, 'found+"-"+g1', 'aba-a'], |
| ['\\(a\\)ba*\\1', 'aba', 0, 'found+"-"+g1', 'aba-a'], |
| ['\\(aa\\|a\\)a\\1$', 'aaa', 0, 'found+"-"+g1', 'aaa-a'], |
| ['\\(a\\|aa\\)a\\1$', 'aaa', 0, 'found+"-"+g1', 'aaa-a'], |
| ['\\(a+\\)a\\1$', 'aaa', 0, 'found+"-"+g1', 'aaa-a'], |
| ['\\([abc]*\\)\\1', 'abcabc', 0, 'found+"-"+g1', 'abcabc-abc'], |
| ['\\(a\\)\\(b\\)c\\|ab', 'ab', 0, 'found+"-"+g1+"-"+g2', 'ab-None-None'], |
| ['\\(a\\)+x', 'aaax', 0, 'found+"-"+g1', 'aaax-a'], |
| ['\\([ac]\\)+x', 'aacx', 0, 'found+"-"+g1', 'aacx-c'], |
| ['\\([^/]*/\\)*sub1/', 'd:msgs/tdir/sub1/trial/away.cpp', 0, 'found+"-"+g1', 'd:msgs/tdir/sub1/-tdir/'], |
| ['\\([^.]*\\)\\.\\([^:]*\\):[T ]+\\(.*\\)', 'track1.title:TBlah blah blah', 0, 'found+"-"+g1+"-"+g2+"-"+g3', 'track1.title:TBlah blah blah-track1-title-Blah blah blah'], |
| ['\\([^N]*N\\)+', 'abNNxyzN', 0, 'found+"-"+g1', 'abNNxyzN-xyzN'], |
| ['\\([^N]*N\\)+', 'abNNxyz', 0, 'found+"-"+g1', 'abNN-N'], |
| ['\\([abc]*\\)x', 'abcx', 0, 'found+"-"+g1', 'abcx-abc'], |
| ['\\([abc]*\\)x', 'abc', 1], |
| ['\\([xyz]*\\)x', 'abcx', 1], |
| ['\\(a\\)+b\\|aac', 'aac', 0, 'found+"-"+g1', 'aac-None'], |
| ['\\<a', 'a', 0, 'found', 'a'], |
| ['\\<a', '!', 1], |
| ['a\\<b', 'ab', 1], |
| ['a\\>', 'ab', 1], |
| ['a\\>', 'a!', 0, 'found', 'a'], |
| ['a\\>', 'a', 0, 'found', 'a'], |
| ] |
| # test suite for split() |
| # element 0: pattern |
| # 1: string to split |
| # 3: compile result |
| # 4: maxsplit |
| # 5: splitted fields list |
| split_regex_tests = [ |
| ["[ |,]", "with you, nothing, and me", 0, 0, ["with","you","nothing","and","me"]], |
| ["[ |,]", "with you, nothing, and me", 0, 1, ["with", "you, nothing, and me"]], |
| ["\\ ", "send email to apply", 0, 0, ["send", "email", "to", "apply"]], |
| ["\\ ", "send email to apply", 0, 2, ["send", "email", "to apply"]], |
| ["[+ | -]", "+86-028-83201034", 0, 0, ["86", "028", "83201034"]], |
| ["[+ | -]", "+86-028-83201034", 0, 1, ["86", "028-83201034"]], |
| ["[*|#]", "slide show", 0, 0, ["slide show"]], |
| ["(", "whats ever", 0, 1, ["whats ever"]], |
| ["@#!~$%^&*()<>\n", "who knows", 0, 1, ["who knows"]], |
| ] |
| # test suite for findall() |
| # element 0: pattern |
| # 1: string to match |
| # 3: compile result |
| # 4: starting position |
| # 5: grouped fields list |
| # reobj.find() |
| findall_regex_tests = [ |
| ["\\ ", "send email to apply", 0, 0, [" ", " ", " "]], |
| ["\\ ", "send email to apply", 0, 5, [" ", " "]], |
| ["[+ | -]", "+86-028-83201034", 0, 0, ["+", "-", "-"]], |
| ["[+ | -]", "+86-028-83201034", 0, 1, ["-", "-"]], |
| ["sl.*e\\|#", "slide show at Room #3", 0, 0, ["slide", "#"]], |
| ["w.+s\\|e.*r", "whats ever", 0, 0, ["whats", "ever"]], |
| ["Euler\\|Gauss", "Both Euler and Gauss are great mathematicians", 0, 0, ["Euler", "Gauss"]], |
| ] |
| # module re.findall() |
| mod_findall_regex_tests = [ |
| ["\\ ", "send email to apply", 0, 0, [" ", " ", " "]], |
| ["\\ ", "send email to apply", 0, 0, [" ", " ", " "]], |
| ["[+ | -]", "+86-028-83201034", 0, 0, ["+", "-", "-"]], |
| ["[+ | -]", "+86-028-83201034", 0, 0, ["+", "-", "-"]], |
| ["sl.*e\\|#", "slide show at Room #3", 0, 0, ["slide", "#"]], |
| ["w.+s\\|e.*r", "whats ever", 0, 0, ["whats", "ever"]], |
| ["Euler\\|Gauss", "Both Euler and Gauss are great mathematicians", 0, 0, ["Euler", "Gauss"]], |
| ] |
| # test for match object's groups() method |
| # element 0: pattern |
| # 1: string |
| # 2: compile result |
| # 3: matched fields, for groups() |
| # 4: group index, valid when > 0, for start(), end(), and span() |
| # 5: pattern's starting index in string, for start() and span() |
| # 6: pattern's ending index in string, for end() and span |
| matobj_groups_regex_tests = [ |
| ["\\(abc\\(.*xyz\\)\\(.*31415926\\)\\)", "where is abc and flurry xyz, which is pi 31415926, derived from ms", 0, ["abc and flurry xyz, which is pi 31415926"," and flurry xyz",", which is pi 31415926"], 2, 12, 27], |
| ["[a\\|b]\\(.+\\)shoe\\([t]+\\)d", "bbbshoetttdxrznmlkjp", 0, ["bb", "ttt"], 1, 1, 3], |
| ["abcdef", "xyah2oewoyqe030uabcdefwhalsdewnkhgiohyczb", 0, [], -1, 0, 0], |
| ] |