Re: [sqlite] [bug+patch] Old lemon bug reintroduced
On Jan 6, 2010, at 7:50 PM, D. Richard Hipp wrote: > > On Jan 6, 2010, at 7:47 PM, Wilson, Ronald wrote: > >> Does check-in [077a6bee2d] resolve the issue below? >> >> http://www.sqlite.org/src/vinfo/077a6bee2d >> > > > Yes. I didn't realize the issue had a ticket. I'll close it. Silly me - I was right: there is no ticket on this issue. So there is nothing to close. But, yes, the issue with lemon is fixed by the change above. > > D. Richard Hipp > d...@hwaci.com > > > > ___ > sqlite-users mailing list > sqlite-users@sqlite.org > http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users D. Richard Hipp d...@hwaci.com ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [bug+patch] Old lemon bug reintroduced
On Jan 6, 2010, at 7:47 PM, Wilson, Ronald wrote: > Does check-in [077a6bee2d] resolve the issue below? > > http://www.sqlite.org/src/vinfo/077a6bee2d > Yes. I didn't realize the issue had a ticket. I'll close it. D. Richard Hipp d...@hwaci.com ___ sqlite-users mailing list sqlite-users@sqlite.org http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
Re: [sqlite] [bug+patch] Old lemon bug reintroduced
Does check-in [077a6bee2d] resolve the issue below?
http://www.sqlite.org/src/vinfo/077a6bee2d
Ron Wilson, Engineering Project Lead
(o) 434.455.6453, (m) 434.851.1612, www.harris.com
HARRIS CORPORATION | RF Communications Division
assuredcommunications(tm)
> -Original Message-
> From: sqlite-users-boun...@sqlite.org [mailto:sqlite-users-
> boun...@sqlite.org] On Behalf Of Vincent Zweije
> Sent: Thursday, December 03, 2009 4:18 PM
> To: sqlite-users@sqlite.org
> Subject: Re: [sqlite] [bug+patch] Old lemon bug reintroduced
>
>
> It seems my previous message has not gone through, so this is a repeat
> post.
>
> A recent change to the lemon parser generator has reintroduced an old bug.
>
> The old bug report can be found in the debian bug tracking system:
> http://bugs.debian.org/233690
>
> The old bug was fixed in CVS checkin 1249:
> http://www.sqlite.org/cvstrac/chngview?cn=1249
>
> However, the bug was re-introduced in checkin 27d8e684db:
> http://www.sqlite.org/src/info/27d8e684db
>
> Here is a demonstration of the bug with a small grammar, and a patch
> that, at least for me now, appears to fix the bug in the same way as
> the CVS checkin mentioned above.
>
> $fossil status
> repository: /home/vincent/fossil/sqlite
> local-root: /home/vincent/src/sqlite/
> server-code: 3efcb091a6d5857b29c9fa3385fee9ee4e8f866f
> checkout: 2f42f91fe65b0b21671936013df08037091f0cc6 2009-11-20
> 18:48:36 UTC
> parent: cae949ce971ca216e0f8880b2f93866619fa05be 2009-11-20
> 17:23:13 UTC
> tags: trunk
> $cat x.y
> start ::= S0.
> start ::= S1.
> start ::= S2.
> start ::= n0.
> n0 ::= n4 T0.
> n4 ::= .
> n4 ::= n4 T4.
>
> %include{
>
> #include
> #include
> #include "x.h"
>
> void *ParseAlloc(void*(*)(size_t));
> void ParseTrace(FILE*,char*);
> void Parse(void*,int,void*);
> void ParseFree(void*,void(*)(void*));
>
> int main(int argc, char *argv[])
> {
> void *parser = ParseAlloc(&malloc);
> ParseTrace(stderr, "x: ");
> Parse(parser, T0, NULL);
> Parse(parser, 0, NULL);
> ParseFree(parser, &free);
> return 0;
> }
>
> }
> $gcc -o tool/lemon tool/lemon.c
> $tool/lemon -s x.y
> Parser statistics: 6 terminals, 4 nonterminals, 7 rules
>8 states, 0 parser table entries, 0 conflicts
> $gcc -o x x.c
> $./x
> x: Input T0
> x: Shift 7
> x: Stack: T0
> x: Input $
> x: Reduce [n0 ::= n4 T0].
> x: x.c:524: yy_find_reduce_action: Assertion `stateno<=(0)' failed.
> Aborted
> $cat crash.patch
> Index: tool/lemon.c
> ===
> fossil diff /home/vincent/src/sqlite/tool/lemon.c
> --- tool/lemon.c
> +++ tool/lemon.c
> @@ -518,11 +518,11 @@
>** offset is found. In the worst case, we fall out of the loop
> when
>** i reaches p->nAction, which means we append the new transaction
> set.
>**
>** i is the index in p->aAction[] where p->mnLookahead is inserted.
>*/
> - for(i=p->nAction-1; i>=0; i--){
> + for(i=p->nAction+p->mnLookahead-1; i>=0; i--){
> /* First look for an existing action table entry that can be
> reused */
> if( p->aAction[i].lookahead==p->mnLookahead ){
>if( p->aAction[i].action!=p->mnAction ) continue;
>for(j=0; jnLookahead; j++){
> k = p->aLookahead[j].lookahead - p->mnLookahead + i;
> @@ -541,11 +541,11 @@
>}
> }
>}
>if( i<0 ){
> /* If no reusable entry is found, look for an empty slot */
> -for(i=0; inAction; i++){
> +for(i=0; inAction+p->mnLookahead; i++){
>if( p->aAction[i].lookahead<0 ){
> for(j=0; jnLookahead; j++){
>k = p->aLookahead[j].lookahead - p->mnLookahead + i;
>if( k<0 ) break;
>if( p->aAction[k].lookahead>=0 ) break;
>
> $patch -p0 patching file tool/lemon.c
> $gcc -o tool/lemon tool/lemon.c
> $tool/lemon -s x.y
> Parser statistics: 6 terminals, 4 nonterminals, 7 rules
>8 states, 0 parser table entries, 0 conflicts
> $gcc -o x x.c
> $./x
> x: Input T0
> x: Reduce [n4 ::=].
> x: Shift 1
> x: Stack: n4
> x: Shift 7
>
Re: [sqlite] [bug+patch] Old lemon bug reintroduced
did anyone evaluate this? I don't see a patch to lemon.c since the
checkin vincent mentions below. I'm not smart enough to question his
findings, but I use lemon in several projects and I would like to
trust it.
rw
from my mobile 434.851.1612
On Dec 3, 2009, at 10:58 PM, "Vincent Zweije" wrote:
>
> It seems my previous message has not gone through, so this is a repeat
> post.
>
> A recent change to the lemon parser generator has reintroduced an
> old bug.
>
> The old bug report can be found in the debian bug tracking system:
>http://bugs.debian.org/233690
>
> The old bug was fixed in CVS checkin 1249:
>http://www.sqlite.org/cvstrac/chngview?cn=1249
>
> However, the bug was re-introduced in checkin 27d8e684db:
>http://www.sqlite.org/src/info/27d8e684db
>
> Here is a demonstration of the bug with a small grammar, and a patch
> that, at least for me now, appears to fix the bug in the same way as
> the CVS checkin mentioned above.
>
>$fossil status
>repository: /home/vincent/fossil/sqlite
>local-root: /home/vincent/src/sqlite/
>server-code: 3efcb091a6d5857b29c9fa3385fee9ee4e8f866f
>checkout: 2f42f91fe65b0b21671936013df08037091f0cc6 2009-11-20
> 18:48:36 UTC
>parent: cae949ce971ca216e0f8880b2f93866619fa05be 2009-11-20
> 17:23:13 UTC
>tags: trunk
>$cat x.y
>start ::= S0.
>start ::= S1.
>start ::= S2.
>start ::= n0.
>n0 ::= n4 T0.
>n4 ::= .
>n4 ::= n4 T4.
>
>%include{
>
>#include
>#include
>#include "x.h"
>
>void *ParseAlloc(void*(*)(size_t));
>void ParseTrace(FILE*,char*);
>void Parse(void*,int,void*);
>void ParseFree(void*,void(*)(void*));
>
>int main(int argc, char *argv[])
>{
>void *parser = ParseAlloc(&malloc);
>ParseTrace(stderr, "x: ");
>Parse(parser, T0, NULL);
>Parse(parser, 0, NULL);
>ParseFree(parser, &free);
>return 0;
>}
>
>}
>$gcc -o tool/lemon tool/lemon.c
>$tool/lemon -s x.y
>Parser statistics: 6 terminals, 4 nonterminals, 7 rules
> 8 states, 0 parser table entries, 0 conflicts
>$gcc -o x x.c
>$./x
>x: Input T0
>x: Shift 7
>x: Stack: T0
>x: Input $
>x: Reduce [n0 ::= n4 T0].
>x: x.c:524: yy_find_reduce_action: Assertion `stateno<=(0)' failed.
>Aborted
>$cat crash.patch
>Index: tool/lemon.c
>===
>fossil diff /home/vincent/src/sqlite/tool/lemon.c
>--- tool/lemon.c
>+++ tool/lemon.c
>@@ -518,11 +518,11 @@
> ** offset is found. In the worst case, we fall out of the
> loop when
> ** i reaches p->nAction, which means we append the new
> transaction set.
> **
> ** i is the index in p->aAction[] where p->mnLookahead is
> inserted.
> */
>- for(i=p->nAction-1; i>=0; i--){
>+ for(i=p->nAction+p->mnLookahead-1; i>=0; i--){
> /* First look for an existing action table entry that can be
> reused */
> if( p->aAction[i].lookahead==p->mnLookahead ){
> if( p->aAction[i].action!=p->mnAction ) continue;
> for(j=0; jnLookahead; j++){
> k = p->aLookahead[j].lookahead - p->mnLookahead + i;
>@@ -541,11 +541,11 @@
> }
> }
> }
> if( i<0 ){
> /* If no reusable entry is found, look for an empty slot */
>-for(i=0; inAction; i++){
>+for(i=0; inAction+p->mnLookahead; i++){
> if( p->aAction[i].lookahead<0 ){
> for(j=0; jnLookahead; j++){
> k = p->aLookahead[j].lookahead - p->mnLookahead + i;
> if( k<0 ) break;
> if( p->aAction[k].lookahead>=0 ) break;
>
>$patch -p0 patching file tool/lemon.c
>$gcc -o tool/lemon tool/lemon.c
>$tool/lemon -s x.y
>Parser statistics: 6 terminals, 4 nonterminals, 7 rules
> 8 states, 0 parser table entries, 0 conflicts
>$gcc -o x x.c
>$./x
>x: Input T0
>x: Reduce [n4 ::=].
>x: Shift 1
>x: Stack: n4
>x: Shift 7
>x: Stack: n4 T0
>x: Input $
>x: Reduce [n0 ::= n4 T0].
>x: Shift 2
>x: Stack: n0
>x: Reduce [start ::= n0].
>x: Accept!
>x: Popping $
>$
>
> After night of bad sleep thinking, only the second hunk of this patch
> seems necessary.
>
> The upper bound in the first hunk does not need to be increased,
> because (as I understand) the loop looks to reuse an existing action
> set. In fact, it may even be sharpened by only counting down from
> nAction-(mxLookahead-mnLookahead)-1, because otherwise the new action
> set falls off the end of the current action table anyway.
>
> I have not tested this...
>
> Ciao.Vincent.
> --
> Vincent Zweije | "If you're flamed in a group
> you
>
Re: [sqlite] [bug+patch] Old lemon bug reintroduced
It seems my previous message has not gone through, so this is a repeat
post.
A recent change to the lemon parser generator has reintroduced an old bug.
The old bug report can be found in the debian bug tracking system:
http://bugs.debian.org/233690
The old bug was fixed in CVS checkin 1249:
http://www.sqlite.org/cvstrac/chngview?cn=1249
However, the bug was re-introduced in checkin 27d8e684db:
http://www.sqlite.org/src/info/27d8e684db
Here is a demonstration of the bug with a small grammar, and a patch
that, at least for me now, appears to fix the bug in the same way as
the CVS checkin mentioned above.
$fossil status
repository: /home/vincent/fossil/sqlite
local-root: /home/vincent/src/sqlite/
server-code: 3efcb091a6d5857b29c9fa3385fee9ee4e8f866f
checkout: 2f42f91fe65b0b21671936013df08037091f0cc6 2009-11-20 18:48:36
UTC
parent: cae949ce971ca216e0f8880b2f93866619fa05be 2009-11-20 17:23:13
UTC
tags: trunk
$cat x.y
start ::= S0.
start ::= S1.
start ::= S2.
start ::= n0.
n0 ::= n4 T0.
n4 ::= .
n4 ::= n4 T4.
%include{
#include
#include
#include "x.h"
void *ParseAlloc(void*(*)(size_t));
void ParseTrace(FILE*,char*);
void Parse(void*,int,void*);
void ParseFree(void*,void(*)(void*));
int main(int argc, char *argv[])
{
void *parser = ParseAlloc(&malloc);
ParseTrace(stderr, "x: ");
Parse(parser, T0, NULL);
Parse(parser, 0, NULL);
ParseFree(parser, &free);
return 0;
}
}
$gcc -o tool/lemon tool/lemon.c
$tool/lemon -s x.y
Parser statistics: 6 terminals, 4 nonterminals, 7 rules
8 states, 0 parser table entries, 0 conflicts
$gcc -o x x.c
$./x
x: Input T0
x: Shift 7
x: Stack: T0
x: Input $
x: Reduce [n0 ::= n4 T0].
x: x.c:524: yy_find_reduce_action: Assertion `stateno<=(0)' failed.
Aborted
$cat crash.patch
Index: tool/lemon.c
===
fossil diff /home/vincent/src/sqlite/tool/lemon.c
--- tool/lemon.c
+++ tool/lemon.c
@@ -518,11 +518,11 @@
** offset is found. In the worst case, we fall out of the loop when
** i reaches p->nAction, which means we append the new transaction set.
**
** i is the index in p->aAction[] where p->mnLookahead is inserted.
*/
- for(i=p->nAction-1; i>=0; i--){
+ for(i=p->nAction+p->mnLookahead-1; i>=0; i--){
/* First look for an existing action table entry that can be reused */
if( p->aAction[i].lookahead==p->mnLookahead ){
if( p->aAction[i].action!=p->mnAction ) continue;
for(j=0; jnLookahead; j++){
k = p->aLookahead[j].lookahead - p->mnLookahead + i;
@@ -541,11 +541,11 @@
}
}
}
if( i<0 ){
/* If no reusable entry is found, look for an empty slot */
-for(i=0; inAction; i++){
+for(i=0; inAction+p->mnLookahead; i++){
if( p->aAction[i].lookahead<0 ){
for(j=0; jnLookahead; j++){
k = p->aLookahead[j].lookahead - p->mnLookahead + i;
if( k<0 ) break;
if( p->aAction[k].lookahead>=0 ) break;
$patch -p0 | "If you're flamed in a group you
Re: [sqlite] [bug+patch] Old lemon bug reintroduced
It seems my previous messages have not gone through, so this is a
repeat post.
A recent change to the lemon parser generator has reintroduced an old bug.
The old bug report can be found in the debian bug tracking system:
http://bugs.debian.org/233690
The old bug was fixed in CVS checkin 1249:
http://www.sqlite.org/cvstrac/chngview?cn=1249
However, the bug was re-introduced in checkin 27d8e684db:
http://www.sqlite.org/src/info/27d8e684db
Here is a demonstration of the bug with a small grammar, and a patch
that, at least for me now, appears to fix the bug in the same way as
the CVS checkin mentioned above.
$fossil status
repository: /home/vincent/fossil/sqlite
local-root: /home/vincent/src/sqlite/
server-code: 3efcb091a6d5857b29c9fa3385fee9ee4e8f866f
checkout: 2f42f91fe65b0b21671936013df08037091f0cc6 2009-11-20 18:48:36
UTC
parent: cae949ce971ca216e0f8880b2f93866619fa05be 2009-11-20 17:23:13
UTC
tags: trunk
$cat x.y
start ::= S0.
start ::= S1.
start ::= S2.
start ::= n0.
n0 ::= n4 T0.
n4 ::= .
n4 ::= n4 T4.
%include{
#include
#include
#include "x.h"
void *ParseAlloc(void*(*)(size_t));
void ParseTrace(FILE*,char*);
void Parse(void*,int,void*);
void ParseFree(void*,void(*)(void*));
int main(int argc, char *argv[])
{
void *parser = ParseAlloc(&malloc);
ParseTrace(stderr, "x: ");
Parse(parser, T0, NULL);
Parse(parser, 0, NULL);
ParseFree(parser, &free);
return 0;
}
}
$gcc -o tool/lemon tool/lemon.c
$tool/lemon -s x.y
Parser statistics: 6 terminals, 4 nonterminals, 7 rules
8 states, 0 parser table entries, 0 conflicts
$gcc -o x x.c
$./x
x: Input T0
x: Shift 7
x: Stack: T0
x: Input $
x: Reduce [n0 ::= n4 T0].
x: x.c:524: yy_find_reduce_action: Assertion `stateno<=(0)' failed.
Aborted
$cat crash.patch
Index: tool/lemon.c
===
fossil diff /home/vincent/src/sqlite/tool/lemon.c
--- tool/lemon.c
+++ tool/lemon.c
@@ -518,11 +518,11 @@
** offset is found. In the worst case, we fall out of the loop when
** i reaches p->nAction, which means we append the new transaction set.
**
** i is the index in p->aAction[] where p->mnLookahead is inserted.
*/
- for(i=p->nAction-1; i>=0; i--){
+ for(i=p->nAction+p->mnLookahead-1; i>=0; i--){
/* First look for an existing action table entry that can be reused */
if( p->aAction[i].lookahead==p->mnLookahead ){
if( p->aAction[i].action!=p->mnAction ) continue;
for(j=0; jnLookahead; j++){
k = p->aLookahead[j].lookahead - p->mnLookahead + i;
@@ -541,11 +541,11 @@
}
}
}
if( i<0 ){
/* If no reusable entry is found, look for an empty slot */
-for(i=0; inAction; i++){
+for(i=0; inAction+p->mnLookahead; i++){
if( p->aAction[i].lookahead<0 ){
for(j=0; jnLookahead; j++){
k = p->aLookahead[j].lookahead - p->mnLookahead + i;
if( k<0 ) break;
if( p->aAction[k].lookahead>=0 ) break;
$patch -p0 | "If you're flamed in a group you
