From 95908b0f50e26fe2c90687966b60a0cf195f71de Mon Sep 17 00:00:00 2001 From: Paul Sokolovsky Date: Wed, 15 Oct 2014 04:43:13 +0300 Subject: modure: Update to re1.5 v0.6, support for char sets/classes ([a-c]). --- extmod/modure.c | 3 +- extmod/re1.5/charclass.c | 11 ++++ extmod/re1.5/compilecode.c | 32 +++++++++- extmod/re1.5/dumpcode.c | 12 +++- extmod/re1.5/re1.5.h | 148 +++++++++++++++++++++++++++++++++++++++++++ extmod/re1.5/recursiveloop.c | 8 ++- extmod/re1.5/regexp.h | 143 ----------------------------------------- 7 files changed, 210 insertions(+), 147 deletions(-) create mode 100644 extmod/re1.5/charclass.c create mode 100644 extmod/re1.5/re1.5.h delete mode 100644 extmod/re1.5/regexp.h (limited to 'extmod') diff --git a/extmod/modure.c b/extmod/modure.c index 7acc045e7..ae47a2129 100644 --- a/extmod/modure.c +++ b/extmod/modure.c @@ -38,7 +38,7 @@ #if MICROPY_PY_URE -#include "re1.5/regexp.h" +#include "re1.5/re1.5.h" #define FLAG_DEBUG 0x1000 @@ -245,5 +245,6 @@ const mp_obj_module_t mp_module_ure = { #include "re1.5/compilecode.c" #include "re1.5/dumpcode.c" #include "re1.5/recursiveloop.c" +#include "re1.5/charclass.c" #endif //MICROPY_PY_URE diff --git a/extmod/re1.5/charclass.c b/extmod/re1.5/charclass.c new file mode 100644 index 000000000..c9f617592 --- /dev/null +++ b/extmod/re1.5/charclass.c @@ -0,0 +1,11 @@ +#include "re1.5.h" + +int _re1_5_classmatch(const char *pc, const char *sp) +{ + // pc points to "cnt" byte after opcode + int cnt = *pc++; + while (cnt--) { + if (!(*sp >= *pc && *sp <= pc[1])) return 0; + } + return 1; +} \ No newline at end of file diff --git a/extmod/re1.5/compilecode.c b/extmod/re1.5/compilecode.c index 5b5d28c2a..a7942b121 100644 --- a/extmod/re1.5/compilecode.c +++ b/extmod/re1.5/compilecode.c @@ -2,7 +2,7 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -#include "regexp.h" +#include "re1.5.h" static void insert_code(char *code, int at, int num, int *pc) { @@ -45,6 +45,18 @@ int re1_5_sizecode(const char *re) break; case ')': break; + case '[': { + pc += 2; + re++; + while (*re != ']') { + if (!*re) return -1; + if (re[1] == '-') { + re += 2; + } + pc += 2; + re++; + } + } } } @@ -76,6 +88,24 @@ const char *_compilecode(const char *re, ByteProg *prog) EMIT(pc++, Any); prog->len++; break; + case '[': { + int cnt; + term = pc; + EMIT(pc++, Class); + pc++; // Skip # of pair byte + prog->len++; + re++; + for (cnt = 0; *re != ']'; re++, cnt++) { + if (!*re) return NULL; + EMIT(pc++, *re); + if (re[1] == '-') { + re += 2; + } + EMIT(pc++, *re); + } + EMIT(term + 1, cnt); + break; + } case '(': term = pc; diff --git a/extmod/re1.5/dumpcode.c b/extmod/re1.5/dumpcode.c index b91ded03a..ca41cfeda 100644 --- a/extmod/re1.5/dumpcode.c +++ b/extmod/re1.5/dumpcode.c @@ -2,7 +2,7 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -#include "regexp.h" +#include "re1.5.h" void re1_5_dumpcode(ByteProg *prog) { @@ -32,6 +32,16 @@ void re1_5_dumpcode(ByteProg *prog) case Any: printf("any\n"); break; + case Class: { + int num = code[pc++]; + printf("class %d", num); + while (num--) { + printf(" 0x%02x-0x%02x", code[pc], code[pc + 1]); + pc += 2; + } + printf("\n"); + break; + } case Match: printf("match\n"); break; diff --git a/extmod/re1.5/re1.5.h b/extmod/re1.5/re1.5.h new file mode 100644 index 000000000..ac41bab8f --- /dev/null +++ b/extmod/re1.5/re1.5.h @@ -0,0 +1,148 @@ +// Copyright 2007-2009 Russ Cox. All Rights Reserved. +// Copyright 2014 Paul Sokolovsky. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +#ifndef _RE1_5_REGEXP__H +#define _RE1_5_REGEXP__H + +#include +#include +#include +#include +#include + +#define nil ((void*)0) +#define nelem(x) (sizeof(x)/sizeof((x)[0])) + +typedef struct Regexp Regexp; +typedef struct Prog Prog; +typedef struct ByteProg ByteProg; +typedef struct Inst Inst; +typedef struct Subject Subject; + +struct Regexp +{ + int type; + int n; + int ch; + Regexp *left; + Regexp *right; +}; + +enum /* Regexp.type */ +{ + Alt = 1, + Cat, + Lit, + Dot, + Paren, + Quest, + Star, + Plus, +}; + +Regexp *parse(char*); +Regexp *reg(int type, Regexp *left, Regexp *right); +void printre(Regexp*); +#ifndef re1_5_fatal +void re1_5_fatal(char*); +#endif +void *mal(int); + +struct Prog +{ + Inst *start; + int len; +}; + +struct ByteProg +{ + int bytelen; + int len; + int sub; + char insts[0]; +}; + +struct Inst +{ + int opcode; + int c; + int n; + Inst *x; + Inst *y; + int gen; // global state, oooh! +}; + +enum /* Inst.opcode */ +{ + // Instructions which consume input bytes (and thus fail if none left) + CONSUMERS = 1, + Char = CONSUMERS, + Any, + Class, + + ASSERTS = 0x50, + Bol = ASSERTS, + Eol, + + // Instructions which take relative offset as arg + JUMPS = 0x60, + Jmp = JUMPS, + Split, + RSplit, + + // Other (special) instructions + Save = 0x7e, + Match = 0x7f, +}; + +#define inst_is_consumer(inst) ((inst) < ASSERTS) +#define inst_is_jump(inst) ((inst) & 0x70 == JUMPS) + +Prog *compile(Regexp*); +void printprog(Prog*); + +extern int gen; + +enum { + MAXSUB = 20 +}; + +typedef struct Sub Sub; + +struct Sub +{ + int ref; + int nsub; + const char *sub[MAXSUB]; +}; + +Sub *newsub(int n); +Sub *incref(Sub*); +Sub *copy(Sub*); +Sub *update(Sub*, int, const char*); +void decref(Sub*); + +struct Subject { + const char *begin; + const char *end; +}; + + +#define NON_ANCHORED_PREFIX 5 +#define HANDLE_ANCHORED(bytecode, is_anchored) ((is_anchored) ? (bytecode) + NON_ANCHORED_PREFIX : (bytecode)) + +int re1_5_backtrack(ByteProg*, Subject*, const char**, int, int); +int re1_5_pikevm(ByteProg*, Subject*, const char**, int, int); +int re1_5_recursiveloopprog(ByteProg*, Subject*, const char**, int, int); +int re1_5_recursiveprog(ByteProg*, Subject*, const char**, int, int); +int re1_5_thompsonvm(ByteProg*, Subject*, const char**, int, int); + +int re1_5_sizecode(const char *re); +int re1_5_compilecode(ByteProg *prog, const char *re); +void re1_5_dumpcode(ByteProg *prog); +void cleanmarks(ByteProg *prog); +int _re1_5_classmatch(const char *pc, const char *sp); + +#endif /*_RE1_5_REGEXP__H*/ diff --git a/extmod/re1.5/recursiveloop.c b/extmod/re1.5/recursiveloop.c index 7b95eb4c9..26c6da43d 100644 --- a/extmod/re1.5/recursiveloop.c +++ b/extmod/re1.5/recursiveloop.c @@ -2,7 +2,7 @@ // Use of this source code is governed by a BSD-style // license that can be found in the LICENSE file. -#include "regexp.h" +#include "re1.5.h" static int recursiveloop(char *pc, const char *sp, Subject *input, const char **subp, int nsubp) @@ -23,6 +23,12 @@ recursiveloop(char *pc, const char *sp, Subject *input, const char **subp, int n case Any: sp++; continue; + case Class: + if (!_re1_5_classmatch(pc, sp)) + return 0; + pc += *(unsigned char*)pc * 2 + 1; + sp++; + continue; case Match: return 1; case Jmp: diff --git a/extmod/re1.5/regexp.h b/extmod/re1.5/regexp.h deleted file mode 100644 index 316b27076..000000000 --- a/extmod/re1.5/regexp.h +++ /dev/null @@ -1,143 +0,0 @@ -// Copyright 2007-2009 Russ Cox. All Rights Reserved. -// Copyright 2014 Paul Sokolovsky. -// Use of this source code is governed by a BSD-style -// license that can be found in the LICENSE file. - -#ifndef _RE1_5_REGEXP__H -#define _RE1_5_REGEXP__H - -#include -#include -#include -#include -#include - -#define nil ((void*)0) -#define nelem(x) (sizeof(x)/sizeof((x)[0])) - -typedef struct Regexp Regexp; -typedef struct Prog Prog; -typedef struct ByteProg ByteProg; -typedef struct Inst Inst; -typedef struct Subject Subject; - -struct Regexp -{ - int type; - int n; - int ch; - Regexp *left; - Regexp *right; -}; - -enum /* Regexp.type */ -{ - Alt = 1, - Cat, - Lit, - Dot, - Paren, - Quest, - Star, - Plus, -}; - -Regexp *parse(char*); -Regexp *reg(int type, Regexp *left, Regexp *right); -void printre(Regexp*); -#ifndef re1_5_fatal -void re1_5_fatal(char*); -#endif -void *mal(int); - -struct Prog -{ - Inst *start; - int len; -}; - -struct ByteProg -{ - int bytelen; - int len; - int sub; - char insts[0]; -}; - -struct Inst -{ - int opcode; - int c; - int n; - Inst *x; - Inst *y; - int gen; // global state, oooh! -}; - -enum /* Inst.opcode */ -{ - // Instructions which consume input bytes (and thus fail if none left) - CONSUMERS = 1, - Char = CONSUMERS, - Any, - ASSERTS = 0x50, - Bol = ASSERTS, - Eol, - // Instructions which take relative offset as arg - JUMPS = 0x60, - Jmp = JUMPS, - Split, - RSplit, - // Other (special) instructions - Save = 0x7e, - Match = 0x7f, -}; - -#define inst_is_consumer(inst) ((inst) < ASSERTS) -#define inst_is_jump(inst) ((inst) & 0x70 == JUMPS) - -Prog *compile(Regexp*); -void printprog(Prog*); - -extern int gen; - -enum { - MAXSUB = 20 -}; - -typedef struct Sub Sub; - -struct Sub -{ - int ref; - int nsub; - const char *sub[MAXSUB]; -}; - -Sub *newsub(int n); -Sub *incref(Sub*); -Sub *copy(Sub*); -Sub *update(Sub*, int, const char*); -void decref(Sub*); - -struct Subject { - const char *begin; - const char *end; -}; - - -#define NON_ANCHORED_PREFIX 5 -#define HANDLE_ANCHORED(bytecode, is_anchored) ((is_anchored) ? (bytecode) + NON_ANCHORED_PREFIX : (bytecode)) - -int re1_5_backtrack(ByteProg*, Subject*, const char**, int, int); -int re1_5_pikevm(ByteProg*, Subject*, const char**, int, int); -int re1_5_recursiveloopprog(ByteProg*, Subject*, const char**, int, int); -int re1_5_recursiveprog(ByteProg*, Subject*, const char**, int, int); -int re1_5_thompsonvm(ByteProg*, Subject*, const char**, int, int); - -int re1_5_sizecode(const char *re); -int re1_5_compilecode(ByteProg *prog, const char *re); -void re1_5_dumpcode(ByteProg *prog); -void cleanmarks(ByteProg *prog); - -#endif /*_RE1_5_REGEXP__H*/ -- cgit v1.2.3