[sqlite] Lemon reduce action merge bug

[Richard Hipp]

On 4/30/16, Kelvin Sherlock  wrote:
>
> Here are a couple more edge cases I noticed:
>

Thanks for the deep-diving on Lemon!  All changes are now checked in.

For passive listeners - none of the bugs that Kelvin has found in
Lemon have any impact on SQLite.  They only come up when using Lemon
on other non-SQLite grammars.  Furthermore, all of the bugs arise (I
think) from recent enhancements I made to Lemon that help the SQLite
parser run faster.
-- 
D. Richard Hipp
drh at sqlite.org

[sqlite] Lemon reduce action merge bug

[Kelvin Sherlock]

> On Apr 29, 2016, at 7:29 AM, Richard Hipp  wrote:
> 
> On 4/28/16, Kelvin Sherlock  wrote:
>> I believe the lemon reduce action optimizer needs to compare the codePrefix
>> and codeSuffix.
> 
> Thanks for the bug report.  A fix has now been checked in.
> 
> -- 
> D. Richard Hipp
> drh at sqlite.org

Here are a couple more edge cases I noticed:

---

bug_report ::= rule.

%destructor malloc{free($$)}

rule ::= .
rule ::= malloc . /* 1 */
rule ::= malloc malloc . /* 2 */

malloc(X) ::= ID . { X = malloc(100); }

---

1. the rhs[0] destructor will not be called since the lhsalias null check 
happens first and the codePrefix is never generated.

The empty lhsalias check can be moved down to compensate:

@@ -3552,30 +3552,30 @@ PRIVATE int translate_code(struct lemon *lemp, struct 
rule *rp){
   if( rp->code==0 ){
 static char newlinestr[2] = { '\n', '\0' };
 rp->code = newlinestr;
 rp->line = rp->ruleline;
   }


-  if( rp->lhsalias==0 ){
-/* There is no LHS value symbol. */
-lhsdirect = 1;
-  }else if( rp->nrhs==0 ){
+  if( rp->nrhs==0 ){
 /* If there are no RHS symbols, then writing directly to the LHS is ok */
 lhsdirect = 1;
   }else if( rp->rhsalias[0]==0 ){
 /* The left-most RHS symbol has not value.  LHS direct is ok.  But
 ** we have to call the distructor on the RHS symbol first. */
 lhsdirect = 1;
 if( has_destructor(rp->rhs[0],lemp) ){
   append_str(0,0,0,0);
   append_str("  yy_destructor(yypParser,%d,[%d].minor);\n", 0,
  rp->rhs[0]->index,1-rp->nrhs);
   rp->codePrefix = Strsafe(append_str(0,0,0,0));
 }
+  }else if( rp->lhsalias==0 ){
+/* There is no LHS value symbol. */
+lhsdirect = 1;
   }else if( strcmp(rp->lhsalias,rp->rhsalias[0])==0 ){
 /* The LHS symbol and the left-most RHS symbol are the same, so 
 ** direct writing is allowed */
 lhsdirect = 1;
 lhsused = 1;
 used[0] = 1;


2. if there is a codePrefix or codeSuffix but no code, it will be merged into 
the default rule and the prefix/suffix will be lost.

@@ -3715,7 +3715,7 @@ PRIVATE int translate_code(struct lemon *lemp, struct 
rule *rp){

   /* Suffix code generation complete */
   cp = append_str(0,0,0,0);
-  if( cp ) rp->codeSuffix = Strsafe(cp);
+  if( cp && cp[0] ) rp->codeSuffix = Strsafe(cp);

   return rc;
 }

@@ -4397,7 +4397,8 @@ void ReportTable(
   for(rp=lemp->rule; rp; rp=rp->next){
 struct rule *rp2;   /* Other rules with the same action */
 if( rp->code==0 ) continue;
-if( rp->code[0]=='\n' && rp->code[1]==0 ) continue; /* Will be default: */
+if( rp->code[0]=='\n' && rp->code[1]==0 && rp->codePrefix==0
+  && rp->codeSuffix==0 ) continue; /* Will be default: */
 fprintf(out,"  case %d: /* ", rp->iRule);
 writeRuleText(out, rp);
 fprintf(out, " */\n"); lineno++;
@@ -4419,7 +4420,8 @@ void ReportTable(
   fprintf(out,"  default:\n"); lineno++;
   for(rp=lemp->rule; rp; rp=rp->next){
 if( rp->code==0 ) continue;
-assert( rp->code[0]=='\n' && rp->code[1]==0 );
+assert( rp->code[0]=='\n' && rp->code[1]==0 && rp->codePrefix==0
+  && rp->codeSuffix==0 );
 fprintf(out,"  /* (%d) ", rp->iRule);
 writeRuleText(out, rp);
 fprintf(out, " */ yytestcase(yyruleno==%d);\n", rp->iRule); lineno++;


Thanks,
Kelvin

[sqlite] Lemon reduce action merge bug

[Richard Hipp]

On 4/28/16, Kelvin Sherlock  wrote:
> I believe the lemon reduce action optimizer needs to compare the codePrefix
> and codeSuffix.

Thanks for the bug report.  A fix has now been checked in.

-- 
D. Richard Hipp
drh at sqlite.org

[sqlite] Lemon reduce action merge bug

[Kelvin Sherlock]

I believe the lemon reduce action optimizer needs to compare the codePrefix and 
codeSuffix. Consider this example:

8<

%type malloc {void *}
%destructor malloc {free($$)}
%type contrived_example {int}

bug_report ::= contrived_example.

contrived_example(LHS) ::= INT INT INT. { LHS = 0; }
contrived_example(LHS) ::= malloc malloc malloc. { LHS = 0; }

malloc(LHS) ::= . { LHS = malloc(100); } 

8< 

Since the code (but not the codeSuffix) matches, they will be merged together 
into this:

  case 0: /* contrived_example ::= INT INT INT */
  case 1: /* contrived_example ::= malloc malloc malloc */ 
yytestcase(yyruleno==1);
#line 8 "bug.lemon"
{ yymsp[-2].minor.yy4 = 0; }
#line 725 "bug.c"
break;

or this:

/** Begin reduce actions **/
  case 0: /* contrived_example ::= malloc malloc malloc */
  case 1: /* contrived_example ::= INT INT INT */ yytestcase(yyruleno==1);
{  yy_destructor(yypParser,3,[-2].minor);
#line 8 "bug.lemon"
{ yymsp[-2].minor.yy4 = 0; }
#line 726 "bug.c"
  yy_destructor(yypParser,3,[-1].minor);
  yy_destructor(yypParser,3,[0].minor);
}
break;

depending on which rule is first.

patch:

diff --git a/lemon.c b/lemon.c
index 903fe97..dca5a08 100644
--- a/lemon.c
+++ b/lemon.c
@@ -4402,7 +4402,11 @@ void ReportTable(
 writeRuleText(out, rp);
 fprintf(out, " */\n"); lineno++;
 for(rp2=rp->next; rp2; rp2=rp2->next){
-  if( rp2->code==rp->code ){
+  if(
+rp2->code==rp->code && 
+rp2->codePrefix==rp->codePrefix &&
+rp2->codeSuffix==rp->codeSuffix
+  ){
 fprintf(out,"  case %d: /* ", rp2->iRule);
 writeRuleText(out, rp2);
 fprintf(out," */ yytestcase(yyruleno==%d);\n", rp2->iRule); lineno++;


Thanks,
Kelvin Sherlock