/ Check-in [2c17a135]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Change the parser engine so that it (once again) waits for a lookahead token before reducing, even in a SHIFTREDUCE action.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | lemon-update
Files: files | file ages | folders
SHA1: 2c17a1358353a0845b039283be79353f033e2491
User & Date: drh 2015-09-07 19:52:55
Context
2015-09-07
20:02
Fix an unreachable branch in the new parse automaton. Closed-Leaf check-in: e9d604b4 user: drh tags: lemon-update
19:52
Change the parser engine so that it (once again) waits for a lookahead token before reducing, even in a SHIFTREDUCE action. check-in: 2c17a135 user: drh tags: lemon-update
18:23
For the Lemon-generated parser, add a new action type SHIFTREDUCE and use it to further compress the parser tables and improve parser performance. check-in: 531c3974 user: drh tags: lemon-update
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/lempar.c.

   163    163   **
   164    164   **   +  The value of the token stored at this level of the stack.
   165    165   **      (In other words, the "major" token.)
   166    166   **
   167    167   **   +  The semantic value stored at this level of the stack.  This is
   168    168   **      the information used by the action routines in the grammar.
   169    169   **      It is sometimes called the "minor" token.
          170  +**
          171  +** After the "shift" half of a SHIFTREDUCE action, the stateno field
          172  +** actually contains the reduce action for the second half of the
          173  +** SHIFTREDUCE.
   170    174   */
   171    175   struct yyStackEntry {
   172         -  YYACTIONTYPE stateno;  /* The state-number */
          176  +  YYACTIONTYPE stateno;  /* The state-number, or reduce action in SHIFTREDUCE */
   173    177     YYCODETYPE major;      /* The major token value.  This is the code
   174    178                            ** number for the token at this stack level */
   175    179     YYMINORTYPE minor;     /* The user-supplied minor token value.  This
   176    180                            ** is the value of the token  */
   177    181   };
   178    182   typedef struct yyStackEntry yyStackEntry;
   179    183   
................................................................................
   399    403   static int yy_find_shift_action(
   400    404     yyParser *pParser,        /* The parser */
   401    405     YYCODETYPE iLookAhead     /* The look-ahead token */
   402    406   ){
   403    407     int i;
   404    408     int stateno = pParser->yystack[pParser->yyidx].stateno;
   405    409    
          410  +  if( stateno>=YY_MIN_REDUCE ) return stateno;
   406    411     if( stateno>YY_SHIFT_COUNT
   407    412      || (i = yy_shift_ofst[stateno])==YY_SHIFT_USE_DFLT ){
   408    413       return yy_default[stateno];
   409    414     }
   410    415     assert( iLookAhead!=YYNOCODE );
   411    416     i += iLookAhead;
   412    417     if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){
................................................................................
   502    507      while( yypParser->yyidx>=0 ) yy_pop_parser_stack(yypParser);
   503    508      /* Here code is inserted which will execute if the parser
   504    509      ** stack every overflows */
   505    510   %%
   506    511      ParseARG_STORE; /* Suppress warning about unused %extra_argument var */
   507    512   }
   508    513   
          514  +/*
          515  +** Print tracing information for a SHIFT action
          516  +*/
          517  +#ifndef NDEBUG
          518  +static void yyTraceShift(yyParser *yypParser, int yyNewState){
          519  +  if( yyTraceFILE ){
          520  +    int i;
          521  +    if( yyNewState<YYNSTATE ){
          522  +      fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState);
          523  +      fprintf(yyTraceFILE,"%sStack:",yyTracePrompt);
          524  +      for(i=1; i<=yypParser->yyidx; i++)
          525  +        fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]);
          526  +      fprintf(yyTraceFILE,"\n");
          527  +    }else{
          528  +      fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt);
          529  +    }
          530  +  }
          531  +}
          532  +#else
          533  +# define yyTraceShift(X,Y)
          534  +#endif
          535  +
   509    536   /*
   510    537   ** Perform a shift action.  Return the number of errors.
   511    538   */
   512         -static int yy_shift(
          539  +static void yy_shift(
   513    540     yyParser *yypParser,          /* The parser to be shifted */
   514    541     int yyNewState,               /* The new state to shift in */
   515    542     int yyMajor,                  /* The major token to shift in */
   516    543     YYMINORTYPE *yypMinor         /* Pointer to the minor token to shift in */
   517    544   ){
   518    545     yyStackEntry *yytos;
   519    546     yypParser->yyidx++;
................................................................................
   521    548     if( yypParser->yyidx>yypParser->yyidxMax ){
   522    549       yypParser->yyidxMax = yypParser->yyidx;
   523    550     }
   524    551   #endif
   525    552   #if YYSTACKDEPTH>0 
   526    553     if( yypParser->yyidx>=YYSTACKDEPTH ){
   527    554       yyStackOverflow(yypParser, yypMinor);
   528         -    return 1;
          555  +    return;
   529    556     }
   530    557   #else
   531    558     if( yypParser->yyidx>=yypParser->yystksz ){
   532    559       yyGrowStack(yypParser);
   533    560       if( yypParser->yyidx>=yypParser->yystksz ){
   534    561         yyStackOverflow(yypParser, yypMinor);
   535         -      return 1;
          562  +      return;
   536    563       }
   537    564     }
   538    565   #endif
   539    566     yytos = &yypParser->yystack[yypParser->yyidx];
   540    567     yytos->stateno = (YYACTIONTYPE)yyNewState;
   541    568     yytos->major = (YYCODETYPE)yyMajor;
   542    569     yytos->minor = *yypMinor;
   543         -#ifndef NDEBUG
   544         -  if( yyTraceFILE && yypParser->yyidx>0 ){
   545         -    int i;
   546         -    if( yyNewState<YYNSTATE ){
   547         -      fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState);
   548         -      fprintf(yyTraceFILE,"%sStack:",yyTracePrompt);
   549         -      for(i=1; i<=yypParser->yyidx; i++)
   550         -        fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]);
   551         -      fprintf(yyTraceFILE,"\n");
   552         -    }else{
   553         -      fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt);
   554         -    }
   555         -  }
   556         -#endif
   557         -  return 0;
          570  +  yyTraceShift(yypParser, yyNewState);
   558    571   }
   559    572   
   560    573   /* The following table contains information about every rule that
   561    574   ** is used during the reduce.
   562    575   */
   563    576   static const struct {
   564    577     YYCODETYPE lhs;         /* Symbol on the left-hand side of the rule */
................................................................................
   624    637     };
   625    638     assert( yyruleno>=0 && yyruleno<sizeof(yyRuleInfo)/sizeof(yyRuleInfo[0]) );
   626    639     yygoto = yyRuleInfo[yyruleno].lhs;
   627    640     yysize = yyRuleInfo[yyruleno].nrhs;
   628    641     yypParser->yyidx -= yysize;
   629    642     yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto);
   630    643     if( yyact <= YY_MAX_SHIFTREDUCE ){
          644  +    if( yyact>YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
   631    645       /* If the reduce action popped at least
   632    646       ** one element off the stack, then we can push the new element back
   633    647       ** onto the stack here, and skip the stack overflow test in yy_shift().
   634    648       ** That gives a significant speed improvement. */
   635    649       if( yysize ){
   636    650         yypParser->yyidx++;
   637    651         yymsp -= yysize-1;
   638    652         yymsp->stateno = (YYACTIONTYPE)yyact;
   639    653         yymsp->major = (YYCODETYPE)yygoto;
   640    654         yymsp->minor = yygotominor;
   641         -#ifndef NDEBUG
   642         -      if( yyTraceFILE ){
   643         -        fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyact);
   644         -      }
   645         -#endif
          655  +      yyTraceShift(yypParser, yyact);
   646    656       }else{
   647         -      if( yy_shift(yypParser,yyact,yygoto,&yygotominor) ) yyact = 0;
   648         -    }
   649         -    if( yyact>=YY_MIN_SHIFTREDUCE ){
   650         -      yy_reduce(yypParser, yyact - YY_MIN_SHIFTREDUCE);
          657  +      yy_shift(yypParser,yyact,yygoto,&yygotominor);
   651    658       }
   652    659     }else{
   653    660       assert( yyact == YY_ACCEPT_ACTION );
   654    661       yy_accept(yypParser);
   655    662     }
   656    663   }
   657    664   
................................................................................
   771    778       fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]);
   772    779     }
   773    780   #endif
   774    781   
   775    782     do{
   776    783       yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor);
   777    784       if( yyact <= YY_MAX_SHIFTREDUCE ){
   778         -      if( yy_shift(yypParser,yyact,yymajor,&yyminorunion)==0 ){
   779         -        yypParser->yyerrcnt--;
   780         -        yymajor = YYNOCODE;
   781         -        if( yyact > YY_MAX_SHIFT ){
   782         -          yy_reduce(yypParser, yyact-YY_MIN_SHIFTREDUCE);
   783         -        }
   784         -      }
          785  +      if( yyact > YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
          786  +      yy_shift(yypParser,yyact,yymajor,&yyminorunion);
          787  +      yypParser->yyerrcnt--;
          788  +      yymajor = YYNOCODE;
   785    789       }else if( yyact <= YY_MAX_REDUCE ){
   786    790         yy_reduce(yypParser,yyact-YY_MIN_REDUCE);
   787    791       }else{
   788    792         assert( yyact == YY_ERROR_ACTION );
   789    793   #ifdef YYERRORSYMBOL
   790    794         int yymx;
   791    795   #endif
................................................................................
   879    883         if( yyendofinput ){
   880    884           yy_parse_failed(yypParser);
   881    885         }
   882    886         yymajor = YYNOCODE;
   883    887   #endif
   884    888       }
   885    889     }while( yymajor!=YYNOCODE && yypParser->yyidx>=0 );
   886         -#ifdef SQLITE_DEBUG
          890  +#ifndef NDEBUG
   887    891     if( yyTraceFILE ){
   888    892       fprintf(yyTraceFILE,"%sReturn\n",yyTracePrompt);
   889    893     }
   890    894   #endif
   891    895     return;
   892    896   }

Changes to src/parse.y.

   583    583   }
   584    584   
   585    585   // "seltablist" is a "Select Table List" - the content of the FROM clause
   586    586   // in a SELECT statement.  "stl_prefix" is a prefix of this list.
   587    587   //
   588    588   stl_prefix(A) ::= seltablist(X) joinop(Y).    {
   589    589      A = X;
   590         -   if( A && A->nSrc>0 ) A->a[A->nSrc-1].fg.jointype = (u8)Y;
          590  +   if( ALWAYS(A && A->nSrc>0) ) A->a[A->nSrc-1].fg.jointype = (u8)Y;
   591    591   }
   592    592   stl_prefix(A) ::= .                           {A = 0;}
   593    593   seltablist(A) ::= stl_prefix(X) nm(Y) dbnm(D) as(Z) indexed_opt(I)
   594    594                     on_opt(N) using_opt(U). {
   595    595     A = sqlite3SrcListAppendFromTerm(pParse,X,&Y,&D,&Z,0,N,U);
   596    596     sqlite3SrcListIndexedBy(pParse, A, &I);
   597    597   }

Changes to src/tokenize.c.

   455    455     }
   456    456   abort_parse:
   457    457     assert( nErr==0 );
   458    458     if( pParse->rc==SQLITE_OK && db->mallocFailed==0 ){
   459    459       assert( zSql[i]==0 );
   460    460       if( lastTokenParsed!=TK_SEMI ){
   461    461         sqlite3Parser(pEngine, TK_SEMI, pParse->sLastToken, pParse);
          462  +      pParse->zTail = &zSql[i];
   462    463       }
   463    464       if( pParse->rc==SQLITE_OK && db->mallocFailed==0 ){
   464    465         sqlite3Parser(pEngine, 0, pParse->sLastToken, pParse);
   465    466       }
   466    467     }
   467         -  pParse->zTail = &zSql[i];
   468    468   #ifdef YYTRACKMAXSTACKDEPTH
   469    469     sqlite3_mutex_enter(sqlite3MallocMutex());
   470    470     sqlite3StatusSet(SQLITE_STATUS_PARSER_STACK,
   471    471         sqlite3ParserStackPeak(pEngine)
   472    472     );
   473    473     sqlite3_mutex_leave(sqlite3MallocMutex());
   474    474   #endif /* YYDEBUG */

Changes to test/misc1.test.

   642    642   # 2015-03-22: NULL pointer dereference after a syntax error
   643    643   #
   644    644   do_catchsql_test misc1-21.1 {
   645    645     select''like''like''like#0;
   646    646   } {1 {near "#0": syntax error}}
   647    647   do_catchsql_test misc1-21.2 {
   648    648     VALUES(0,0x0MATCH#0;
   649         -} {1 {near "#0": syntax error}}
          649  +} {1 {near ";": syntax error}}
   650    650   
   651    651   # 2015-04-15
   652    652   do_execsql_test misc1-22.1 {
   653    653     SELECT ""+3 FROM (SELECT ""+5);
   654    654   } {3}
   655    655   
   656    656   # 2015-04-19: NULL pointer dereference on a corrupt schema

Changes to tool/lempar.c.

   157    157   **
   158    158   **   +  The value of the token stored at this level of the stack.
   159    159   **      (In other words, the "major" token.)
   160    160   **
   161    161   **   +  The semantic value stored at this level of the stack.  This is
   162    162   **      the information used by the action routines in the grammar.
   163    163   **      It is sometimes called the "minor" token.
          164  +**
          165  +** After the "shift" half of a SHIFTREDUCE action, the stateno field
          166  +** actually contains the reduce action for the second half of the
          167  +** SHIFTREDUCE.
   164    168   */
   165    169   struct yyStackEntry {
   166         -  YYACTIONTYPE stateno;  /* The state-number */
          170  +  YYACTIONTYPE stateno;  /* The state-number, or reduce action in SHIFTREDUCE */
   167    171     YYCODETYPE major;      /* The major token value.  This is the code
   168    172                            ** number for the token at this stack level */
   169    173     YYMINORTYPE minor;     /* The user-supplied minor token value.  This
   170    174                            ** is the value of the token  */
   171    175   };
   172    176   typedef struct yyStackEntry yyStackEntry;
   173    177   
................................................................................
   388    392   */
   389    393   static int yy_find_shift_action(
   390    394     yyParser *pParser,        /* The parser */
   391    395     YYCODETYPE iLookAhead     /* The look-ahead token */
   392    396   ){
   393    397     int i;
   394    398     int stateno = pParser->yystack[pParser->yyidx].stateno;
   395         - 
          399  +
          400  +  if( stateno>=YY_MIN_REDUCE ) return stateno; 
   396    401     if( stateno>YY_SHIFT_COUNT
   397    402      || (i = yy_shift_ofst[stateno])==YY_SHIFT_USE_DFLT ){
   398    403       return yy_default[stateno];
   399    404     }
   400    405     assert( iLookAhead!=YYNOCODE );
   401    406     i += iLookAhead;
   402    407     if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){
................................................................................
   492    497      while( yypParser->yyidx>=0 ) yy_pop_parser_stack(yypParser);
   493    498      /* Here code is inserted which will execute if the parser
   494    499      ** stack every overflows */
   495    500   %%
   496    501      ParseARG_STORE; /* Suppress warning about unused %extra_argument var */
   497    502   }
   498    503   
          504  +/*
          505  +** Print tracing information for a SHIFT action
          506  +*/
          507  +#ifndef NDEBUG
          508  +static void yyTraceShift(yyParser *yypParser, int yyNewState){
          509  +  if( yyTraceFILE ){
          510  +    int i;
          511  +    if( yyNewState<YYNSTATE ){
          512  +      fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState);
          513  +      fprintf(yyTraceFILE,"%sStack:",yyTracePrompt);
          514  +      for(i=1; i<=yypParser->yyidx; i++)
          515  +        fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]);
          516  +      fprintf(yyTraceFILE,"\n");
          517  +    }else{
          518  +      fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt);
          519  +    }
          520  +  }
          521  +}
          522  +#else
          523  +# define yyTraceShift(X,Y)
          524  +#endif
          525  +
   499    526   /*
   500    527   ** Perform a shift action.  Return the number of errors.
   501    528   */
   502         -static int yy_shift(
          529  +static void yy_shift(
   503    530     yyParser *yypParser,          /* The parser to be shifted */
   504    531     int yyNewState,               /* The new state to shift in */
   505    532     int yyMajor,                  /* The major token to shift in */
   506    533     YYMINORTYPE *yypMinor         /* Pointer to the minor token to shift in */
   507    534   ){
   508    535     yyStackEntry *yytos;
   509    536     yypParser->yyidx++;
................................................................................
   511    538     if( yypParser->yyidx>yypParser->yyidxMax ){
   512    539       yypParser->yyidxMax = yypParser->yyidx;
   513    540     }
   514    541   #endif
   515    542   #if YYSTACKDEPTH>0 
   516    543     if( yypParser->yyidx>=YYSTACKDEPTH ){
   517    544       yyStackOverflow(yypParser, yypMinor);
   518         -    return 1;
          545  +    return;
   519    546     }
   520    547   #else
   521    548     if( yypParser->yyidx>=yypParser->yystksz ){
   522    549       yyGrowStack(yypParser);
   523    550       if( yypParser->yyidx>=yypParser->yystksz ){
   524    551         yyStackOverflow(yypParser, yypMinor);
   525         -      return 1;
          552  +      return;
   526    553       }
   527    554     }
   528    555   #endif
   529    556     yytos = &yypParser->yystack[yypParser->yyidx];
   530    557     yytos->stateno = (YYACTIONTYPE)yyNewState;
   531    558     yytos->major = (YYCODETYPE)yyMajor;
   532    559     yytos->minor = *yypMinor;
   533         -#ifndef NDEBUG
   534         -  if( yyTraceFILE && yypParser->yyidx>0 ){
   535         -    int i;
   536         -    if( yyNewState<YYNSTATE ){
   537         -      fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState);
   538         -      fprintf(yyTraceFILE,"%sStack:",yyTracePrompt);
   539         -      for(i=1; i<=yypParser->yyidx; i++)
   540         -        fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]);
   541         -      fprintf(yyTraceFILE,"\n");
   542         -    }else{
   543         -      fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt);
   544         -    }
   545         -  }
   546         -#endif
   547         -  return 0;
          560  +  yyTraceShift(yypParser, yyNewState);
   548    561   }
   549    562   
   550    563   /* The following table contains information about every rule that
   551    564   ** is used during the reduce.
   552    565   */
   553    566   static const struct {
   554    567     YYCODETYPE lhs;         /* Symbol on the left-hand side of the rule */
................................................................................
   612    625     */
   613    626   %%
   614    627     };
   615    628     yygoto = yyRuleInfo[yyruleno].lhs;
   616    629     yysize = yyRuleInfo[yyruleno].nrhs;
   617    630     yypParser->yyidx -= yysize;
   618    631     yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto);
   619         -  if( yyact < YY_MAX_SHIFTREDUCE ){
          632  +  if( yyact <= YY_MAX_SHIFTREDUCE ){
          633  +    if( yyact>YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
   620    634       /* If the reduce action popped at least
   621    635       ** one element off the stack, then we can push the new element back
   622    636       ** onto the stack here, and skip the stack overflow test in yy_shift().
   623    637       ** That gives a significant speed improvement. */
   624    638       if( yysize ){
   625    639         yypParser->yyidx++;
   626    640         yymsp -= yysize-1;
   627    641         yymsp->stateno = (YYACTIONTYPE)yyact;
   628    642         yymsp->major = (YYCODETYPE)yygoto;
   629    643         yymsp->minor = yygotominor;
   630         -#ifndef NDEBUG
   631         -      if( yyTraceFILE ){
   632         -        fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyact);
   633         -      }
   634         -#endif
          644  +      yyTraceShift(yypParser, yyact);
   635    645       }else{
   636         -      if( yy_shift(yypParser,yyact,yygoto,&yygotominor) ) yyact = 0;
   637         -    }
   638         -    if( yyact>=YY_MIN_SHIFTREDUCE ){
   639         -      yy_reduce(yypParser, yyact - YY_MIN_SHIFTREDUCE);
          646  +      yy_shift(yypParser,yyact,yygoto,&yygotominor);
   640    647       }
   641    648     }else{
   642    649       assert( yyact == YY_ACCEPT_ACTION );
   643    650       yy_accept(yypParser);
   644    651     }
   645    652   }
   646    653   
................................................................................
   756    763       fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]);
   757    764     }
   758    765   #endif
   759    766   
   760    767     do{
   761    768       yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor);
   762    769       if( yyact <= YY_MAX_SHIFTREDUCE ){
   763         -      if( yy_shift(yypParser,yyact,yymajor,&yyminorunion)==0 ){
   764         -        yypParser->yyerrcnt--;
   765         -        yymajor = YYNOCODE;
   766         -        if( yyact > YY_MAX_SHIFT ){
   767         -          yy_reduce(yypParser, yyact-YY_MIN_SHIFTREDUCE);
   768         -        }
   769         -      }
          770  +      if( yyact > YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
          771  +      yy_shift(yypParser,yyact,yymajor,&yyminorunion);
          772  +      yypParser->yyerrcnt--;
          773  +      yymajor = YYNOCODE;
   770    774       }else if( yyact <= YY_MAX_REDUCE ){
   771    775         yy_reduce(yypParser,yyact-YY_MIN_REDUCE);
   772    776       }else{
   773    777         assert( yyact == YY_ERROR_ACTION );
   774    778   #ifdef YYERRORSYMBOL
   775    779         int yymx;
   776    780   #endif