From f98be597025d9651753308391c29ac84d8ff0f52 Mon Sep 17 00:00:00 2001 From: helly Date: Wed, 2 Nov 2005 20:07:33 +0000 Subject: [PATCH] - Fix bug #1297658 underestimation of n in YYFILL(n) --- CHANGELOG | 1 + code.cc | 70 ++++++++++++++------ test/bug1297658.c | 158 +++++++++++++++++++++++++++++++++++++++++++++ test/bug1297658.re | 90 ++++++++++++++++++++++++++ test/cnokw.c | 2 +- 5 files changed, 299 insertions(+), 22 deletions(-) create mode 100644 test/bug1297658.c create mode 100755 test/bug1297658.re diff --git a/CHANGELOG b/CHANGELOG index 49fa8d65..704ab11f 100644 --- a/CHANGELOG +++ b/CHANGELOG @@ -1,5 +1,6 @@ Version 0.9.11 (????-??-??) --------------------------- +- Fixed #1297658 underestimation of n in YYFILL(n). - Applied #1339483 Avoid rebuilds of re2c when running subtargets. - Implemented #1335305 symbol table reimplementation, just slightly modifed. diff --git a/code.cc b/code.cc index 998d875b..44464194 100644 --- a/code.cc +++ b/code.cc @@ -891,8 +891,38 @@ void SCC::traverse(State *x) } } +static +bool state_is_in_non_trivial_SCC( const State* s ) +{ + + // does not link to self + if ( s->link != s ){ + return true; + } + + // or exists i: (s->go.spans[i].to->link == s) + // + // Note: (s->go.spans[i].to == s) is allowed, corresponds to s + // looping back to itself. + // + for (uint i = 0; i < s->go.nSpans; ++i) + { + const State* t = s->go.span[i].to; + + if (t && t->link == s){ + return true; + } + } + // otherwise no + return false; +} + uint maxDist(State *s) { + if ( s->depth != cInfinity ){ + // Already calculated, just return result. + return s->depth; + } uint mm = 0; for (uint i = 0; i < s->go.nSpans; ++i) @@ -903,7 +933,7 @@ uint maxDist(State *s) { uint m = 1; - if (!t->link) + if (!t->link) // marked as non-key state { if (t->depth == -1) { @@ -919,35 +949,33 @@ uint maxDist(State *s) } } + s->depth = mm; return mm; } void calcDepth(State *head) { - State *t; - - for (State *s = head; s; s = s->next) + // mark non-key states by s->link = NULL ; + for (State* s = head; s; s = s->next ) { - if (s->link == s) + if ( (s!=head) && !state_is_in_non_trivial_SCC(s) ) { - for (uint i = 0; i < s->go.nSpans; ++i) - { - t = s->go.span[i].to; - - if (t && t->link == s) - { - goto inSCC; - } - } - - s->link = NULL; - } - else - { -inSCC: - s->depth = maxDist(s); + s->link=NULL; + } else { + // key state, leave alone } } + + for (State* s = head; s; s = s->next ) + { + s->depth = cInfinity; + } + + // calculate max number of transitions before guarantied to reach + // a key state. + for (State* s = head; s; s = s->next ){ + maxDist(s); + } } void DFA::findSCCs() diff --git a/test/bug1297658.c b/test/bug1297658.c new file mode 100644 index 00000000..b6862031 --- /dev/null +++ b/test/bug1297658.c @@ -0,0 +1,158 @@ +/* Generated by re2c 0.9.11.dev on Wed Nov 2 21:06:07 2005 */ +#line 1 "test/bug1297658.re" +#include +#include +#include + +struct Scanner +{ + Scanner(char *_inp) + : inp(_inp), buf(NULL), ptr(NULL), len(0), siz(strlen(_inp)), line(0) + { + fill(0); + cur = buf; + } + + void fill(size_t n) + { + n++; + buf = (char*)realloc(buf, len + n + 1); + if ((len += n) > siz) + { + len = siz; + } + memcpy(buf, inp, len); + buf[len] = '\0'; + lim = buf + len; + eof = buf + siz - 1; + } + + char *inp; + char *cur; + char *buf; + char *ptr; + char *lim; + char *eof; + size_t len; + size_t siz; + size_t line; +}; + +enum What +{ + UNEXPECTED, + FCON, + EOI +}; + +#define YYCTYPE char +#define YYCURSOR s.cur +#define YYLIMIT s.lim +#define YYMARKER s.ptr +#define YYFILL(n) s.fill(n) +#define RET(n) return (n) + +int scan(Scanner &s) +{ +std: + + +#line 61 "" +{ + YYCTYPE yych; + unsigned int yyaccept = 0; + goto yy0; + ++YYCURSOR; +yy0: + if((YYLIMIT - YYCURSOR) < 4) YYFILL(4); + yych = *YYCURSOR; + switch(yych){ + case 0x0A: goto yy6; + case '.': goto yy4; + case '0': goto yy2; + default: goto yy8; + } +yy2: yyaccept = 0; + yych = *(YYMARKER = ++YYCURSOR); + switch(yych){ + case '.': goto yy11; + case '0': goto yy12; + default: goto yy3; + } +yy3: +#line 74 "test/bug1297658.re" +{ + RET(UNEXPECTED); + } +#line 88 "" +yy4: ++YYCURSOR; + switch((yych = *YYCURSOR)) { + case 'L': goto yy10; + case 'e': goto yy9; + default: goto yy5; + } +yy5: +#line 61 "test/bug1297658.re" +{ + RET(FCON); + } +#line 100 "" +yy6: ++YYCURSOR; + goto yy7; +yy7: +#line 66 "test/bug1297658.re" +{ + s.line++; + if(1||s.cur == s.eof) RET(EOI); + goto std; + } +#line 110 "" +yy8: yych = *++YYCURSOR; + goto yy3; +yy9: yych = *++YYCURSOR; + switch(yych){ + case 'L': goto yy10; + default: goto yy5; + } +yy10: yych = *++YYCURSOR; + goto yy5; +yy11: yych = *++YYCURSOR; + switch(yych){ + case 'L': goto yy10; + case 'e': goto yy15; + default: goto yy5; + } +yy12: ++YYCURSOR; + if((YYLIMIT - YYCURSOR) < 3) YYFILL(3); + yych = *YYCURSOR; + goto yy13; +yy13: switch(yych){ + case '.': goto yy11; + case '0': goto yy12; + default: goto yy14; + } +yy14: YYCURSOR = YYMARKER; + switch(yyaccept){ + case 0: goto yy3; + } +yy15: ++YYCURSOR; + switch((yych = *YYCURSOR)) { + case 'L': goto yy10; + default: goto yy5; + } +} +#line 77 "test/bug1297658.re" + +} + +int main(int,char**) +{ + Scanner s("\n0.eL\n00.eL\n"); + + std::cout << "RES(2): " << scan(s) << std::endl; + std::cout << "RES(1): " << scan(s) << std::endl; + std::cout << "RES(2): " << scan(s) << std::endl; + std::cout << "RES(1): " << scan(s) << std::endl; + std::cout << "RES(2): " << scan(s) << std::endl; + std::cout << "RES(0): " << scan(s) << std::endl; +} diff --git a/test/bug1297658.re b/test/bug1297658.re new file mode 100755 index 00000000..663f43c9 --- /dev/null +++ b/test/bug1297658.re @@ -0,0 +1,90 @@ +#include +#include +#include + +struct Scanner +{ + Scanner(char *_inp) + : inp(_inp), buf(NULL), ptr(NULL), len(0), siz(strlen(_inp)), line(0) + { + fill(0); + cur = buf; + } + + void fill(size_t n) + { + n++; + buf = (char*)realloc(buf, len + n + 1); + if ((len += n) > siz) + { + len = siz; + } + memcpy(buf, inp, len); + buf[len] = '\0'; + lim = buf + len; + eof = buf + siz - 1; + } + + char *inp; + char *cur; + char *buf; + char *ptr; + char *lim; + char *eof; + size_t len; + size_t siz; + size_t line; +}; + +enum What +{ + UNEXPECTED, + FCON, + EOI +}; + +#define YYCTYPE char +#define YYCURSOR s.cur +#define YYLIMIT s.lim +#define YYMARKER s.ptr +#define YYFILL(n) s.fill(n) +#define RET(n) return (n) + +int scan(Scanner &s) +{ +std: + +/*!re2c + +("0"* "." "e"? "L"?) | +("0"+ "." "e"? "L"?) + { + RET(FCON); + } + +"\n" + { + s.line++; + if(1||s.cur == s.eof) RET(EOI); + goto std; + } + + +. + { + RET(UNEXPECTED); + } +*/ +} + +int main(int,char**) +{ + Scanner s("\n0.eL\n00.eL\n"); + + std::cout << "RES(2): " << scan(s) << std::endl; + std::cout << "RES(1): " << scan(s) << std::endl; + std::cout << "RES(2): " << scan(s) << std::endl; + std::cout << "RES(1): " << scan(s) << std::endl; + std::cout << "RES(2): " << scan(s) << std::endl; + std::cout << "RES(0): " << scan(s) << std::endl; +} diff --git a/test/cnokw.c b/test/cnokw.c index 8f08ba46..3a576e35 100644 --- a/test/cnokw.c +++ b/test/cnokw.c @@ -133,7 +133,7 @@ std: goto yy0; ++YYCURSOR; yy0: - if((YYLIMIT - YYCURSOR) < 4) YYFILL(4); + if((YYLIMIT - YYCURSOR) < 5) YYFILL(5); yych = *YYCURSOR; switch(yych){ case 0x09: case 0x0B: -- 2.40.0