/ Check-in [417e7777]
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:More agressive use of /*A-overwrites-X*/ in the parser. Fix an off-by-one error in parser stack overflow detection.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | parser-performance
Files: files | file ages | folders
SHA1: 417e777701bbf4bd67626d4ca3bc2c5d847f6cd0
User & Date: drh 2016-02-17 12:34:03
Context
2016-02-17
13:24
Enhance Lemon to generate more compact and efficient code for yy_reduce(). Update the main SQL grammar to take advantage of the new capabilities. check-in: 53fd040c user: drh tags: trunk
12:34
More agressive use of /*A-overwrites-X*/ in the parser. Fix an off-by-one error in parser stack overflow detection. Closed-Leaf check-in: 417e7777 user: drh tags: parser-performance
04:33
Enhance Lemon so that if reduce code contains a comment of the form "/*A-overwrites-X*/" then a LHS label A is allowed to overwrite the RHS label X. check-in: 5cfe9545 user: drh tags: parser-performance
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/parse.y.

   298    298     v.pExpr = sqlite3PExpr(pParse, TK_UMINUS, X.pExpr, 0, 0);
   299    299     v.zStart = A.z;
   300    300     v.zEnd = X.zEnd;
   301    301     sqlite3AddDefaultValue(pParse,&v);
   302    302   }
   303    303   ccons ::= DEFAULT id(X).              {
   304    304     ExprSpan v;
   305         -  spanExpr(&v, pParse, TK_STRING, &X);
          305  +  spanExpr(&v, pParse, TK_STRING, X);
   306    306     sqlite3AddDefaultValue(pParse,&v);
   307    307   }
   308    308   
   309    309   // In addition to the type name, we also care about the primary key and
   310    310   // UNIQUE constraints.
   311    311   //
   312    312   ccons ::= NULL onconf.
................................................................................
   486    486   %type multiselect_op {int}
   487    487   multiselect_op(A) ::= UNION(OP).             {A = @OP; /*A-overwrites-OP*/}
   488    488   multiselect_op(A) ::= UNION ALL.             {A = TK_ALL;}
   489    489   multiselect_op(A) ::= EXCEPT|INTERSECT(OP).  {A = @OP; /*A-overwrites-OP*/}
   490    490   %endif SQLITE_OMIT_COMPOUND_SELECT
   491    491   oneselect(A) ::= SELECT(S) distinct(D) selcollist(W) from(X) where_opt(Y)
   492    492                    groupby_opt(P) having_opt(Q) orderby_opt(Z) limit_opt(L). {
          493  +#if SELECTTRACE_ENABLED
          494  +  Token s = S; /*A-overwrites-S*/
          495  +#endif
   493    496     A = sqlite3SelectNew(pParse,W,X,Y,P,Q,Z,D,L.pLimit,L.pOffset);
   494    497   #if SELECTTRACE_ENABLED
   495    498     /* Populate the Select.zSelName[] string that is used to help with
   496    499     ** query planner debugging, to differentiate between multiple Select
   497    500     ** objects in a complex query.
   498    501     **
   499    502     ** If the SELECT keyword is immediately followed by a C-style comment
   500    503     ** then extract the first few alphanumeric characters from within that
   501    504     ** comment to be the zSelName value.  Otherwise, the label is #N where
   502    505     ** is an integer that is incremented with each SELECT statement seen.
   503    506     */
   504    507     if( A!=0 ){
   505         -    const char *z = S.z+6;
          508  +    const char *z = s.z+6;
   506    509       int i;
   507    510       sqlite3_snprintf(sizeof(A->zSelName), A->zSelName, "#%d",
   508    511                        ++pParse->nSelect);
   509    512       while( z[0]==' ' ) z++;
   510    513       if( z[0]=='/' && z[1]=='*' ){
   511    514         z += 2;
   512    515         while( z[0]==' ' ) z++;
................................................................................
   848    851       pOut->zEnd = &pEnd->z[pEnd->n];
   849    852     }
   850    853   
   851    854     /* Construct a new Expr object from a single identifier.  Use the
   852    855     ** new Expr to populate pOut.  Set the span of pOut to be the identifier
   853    856     ** that created the expression.
   854    857     */
   855         -  static void spanExpr(ExprSpan *pOut, Parse *pParse, int op, Token *pValue){
   856         -    pOut->pExpr = sqlite3PExpr(pParse, op, 0, 0, pValue);
   857         -    pOut->zStart = pValue->z;
   858         -    pOut->zEnd = &pValue->z[pValue->n];
          858  +  static void spanExpr(ExprSpan *pOut, Parse *pParse, int op, Token t){
          859  +    pOut->pExpr = sqlite3PExpr(pParse, op, 0, 0, &t);
          860  +    pOut->zStart = t.z;
          861  +    pOut->zEnd = &t.z[t.n];
   859    862     }
   860    863   }
   861    864   
   862    865   expr(A) ::= term(A).
   863         -expr(A) ::= LP(B) expr(X) RP(E). {A.pExpr = X.pExpr; spanSet(&A,&B,&E);}
   864         -term(A) ::= NULL(X).             {spanExpr(&A, pParse, @X, &X);}
   865         -expr(A) ::= id(X).               {spanExpr(&A, pParse, TK_ID, &X);}
   866         -expr(A) ::= JOIN_KW(X).          {spanExpr(&A, pParse, TK_ID, &X);}
          866  +expr(A) ::= LP(B) expr(X) RP(E).
          867  +            {spanSet(&A,&B,&E); /*A-overwrites-B*/  A.pExpr = X.pExpr;}
          868  +term(A) ::= NULL(X).        {spanExpr(&A,pParse,@X,X);/*A-overwrites-X*/}
          869  +expr(A) ::= id(X).          {spanExpr(&A,pParse,TK_ID,X); /*A-overwrites-X*/}
          870  +expr(A) ::= JOIN_KW(X).     {spanExpr(&A,pParse,TK_ID,X); /*A-overwrites-X*/}
   867    871   expr(A) ::= nm(X) DOT nm(Y). {
   868    872     Expr *temp1 = sqlite3PExpr(pParse, TK_ID, 0, 0, &X);
   869    873     Expr *temp2 = sqlite3PExpr(pParse, TK_ID, 0, 0, &Y);
   870    874     spanSet(&A,&X,&Y); /*A-overwrites-X*/
   871    875     A.pExpr = sqlite3PExpr(pParse, TK_DOT, temp1, temp2, 0);
   872    876   }
   873    877   expr(A) ::= nm(X) DOT nm(Y) DOT nm(Z). {
................................................................................
   874    878     Expr *temp1 = sqlite3PExpr(pParse, TK_ID, 0, 0, &X);
   875    879     Expr *temp2 = sqlite3PExpr(pParse, TK_ID, 0, 0, &Y);
   876    880     Expr *temp3 = sqlite3PExpr(pParse, TK_ID, 0, 0, &Z);
   877    881     Expr *temp4 = sqlite3PExpr(pParse, TK_DOT, temp2, temp3, 0);
   878    882     spanSet(&A,&X,&Z); /*A-overwrites-X*/
   879    883     A.pExpr = sqlite3PExpr(pParse, TK_DOT, temp1, temp4, 0);
   880    884   }
   881         -term(A) ::= INTEGER|FLOAT|BLOB(X).  {spanExpr(&A, pParse, @X, &X);}
   882         -term(A) ::= STRING(X).              {spanExpr(&A, pParse, @X, &X);}
          885  +term(A) ::= INTEGER|FLOAT|BLOB(X). {spanExpr(&A,pParse,@X,X);/*A-overwrites-X*/}
          886  +term(A) ::= STRING(X).             {spanExpr(&A,pParse,@X,X);/*A-overwrites-X*/}
   883    887   expr(A) ::= VARIABLE(X).     {
   884         -  if( X.n>=2 && X.z[0]=='#' && sqlite3Isdigit(X.z[1]) ){
          888  +  Token t = X; /*A-overwrites-X*/
          889  +  if( t.n>=2 && t.z[0]=='#' && sqlite3Isdigit(t.z[1]) ){
   885    890       /* When doing a nested parse, one can include terms in an expression
   886    891       ** that look like this:   #1 #2 ...  These terms refer to registers
   887    892       ** in the virtual machine.  #N is the N-th register. */
          893  +    spanSet(&A, &t, &t);
   888    894       if( pParse->nested==0 ){
   889         -      sqlite3ErrorMsg(pParse, "near \"%T\": syntax error", &X);
          895  +      sqlite3ErrorMsg(pParse, "near \"%T\": syntax error", &t);
   890    896         A.pExpr = 0;
   891    897       }else{
   892         -      A.pExpr = sqlite3PExpr(pParse, TK_REGISTER, 0, 0, &X);
   893         -      if( A.pExpr ) sqlite3GetInt32(&X.z[1], &A.pExpr->iTable);
          898  +      A.pExpr = sqlite3PExpr(pParse, TK_REGISTER, 0, 0, &t);
          899  +      if( A.pExpr ) sqlite3GetInt32(&t.z[1], &A.pExpr->iTable);
   894    900       }
   895    901     }else{
   896         -    spanExpr(&A, pParse, TK_VARIABLE, &X);
          902  +    spanExpr(&A, pParse, TK_VARIABLE, t);
   897    903       sqlite3ExprAssignVarNumber(pParse, A.pExpr);
   898    904     }
   899         -  spanSet(&A, &X, &X);
   900    905   }
   901    906   expr(A) ::= expr(A) COLLATE ids(C). {
   902    907     A.pExpr = sqlite3ExprAddCollateToken(pParse, A.pExpr, &C, 1);
   903    908     A.zEnd = &C.z[C.n];
   904    909   }
   905    910   %ifndef SQLITE_OMIT_CAST
   906    911   expr(A) ::= CAST(X) LP expr(E) AS typetoken(T) RP(Y). {
          912  +  spanSet(&A,&X,&Y); /*A-overwrites-X*/
   907    913     A.pExpr = sqlite3PExpr(pParse, TK_CAST, E.pExpr, 0, &T);
   908         -  spanSet(&A,&X,&Y);
   909    914   }
   910    915   %endif  SQLITE_OMIT_CAST
   911    916   expr(A) ::= id(X) LP distinct(D) exprlist(Y) RP(E). {
   912    917     if( Y && Y->nExpr>pParse->db->aLimit[SQLITE_LIMIT_FUNCTION_ARG] ){
   913    918       sqlite3ErrorMsg(pParse, "too many arguments on function %T", &X);
   914    919     }
   915    920     A.pExpr = sqlite3ExprFunction(pParse, Y, &X);
................................................................................
  1037   1042     static void spanUnaryPrefix(
  1038   1043       ExprSpan *pOut,        /* Write the new expression node here */
  1039   1044       Parse *pParse,         /* Parsing context to record errors */
  1040   1045       int op,                /* The operator */
  1041   1046       ExprSpan *pOperand,    /* The operand */
  1042   1047       Token *pPreOp         /* The operand token for setting the span */
  1043   1048     ){
  1044         -    pOut->pExpr = sqlite3PExpr(pParse, op, pOperand->pExpr, 0, 0);
  1045   1049       pOut->zStart = pPreOp->z;
         1050  +    pOut->pExpr = sqlite3PExpr(pParse, op, pOperand->pExpr, 0, 0);
  1046   1051       pOut->zEnd = pOperand->zEnd;
  1047   1052     }
  1048   1053   }
  1049   1054   
  1050   1055   
  1051   1056   
  1052         -expr(A) ::= NOT(B) expr(X).    {spanUnaryPrefix(&A,pParse,@B,&X,&B);}
  1053         -expr(A) ::= BITNOT(B) expr(X). {spanUnaryPrefix(&A,pParse,@B,&X,&B);}
         1057  +expr(A) ::= NOT(B) expr(X).  
         1058  +              {spanUnaryPrefix(&A,pParse,@B,&X,&B);/*A-overwrites-B*/}
         1059  +expr(A) ::= BITNOT(B) expr(X).
         1060  +              {spanUnaryPrefix(&A,pParse,@B,&X,&B);/*A-overwrites-B*/}
  1054   1061   expr(A) ::= MINUS(B) expr(X). [BITNOT]
  1055         -                               {spanUnaryPrefix(&A,pParse,TK_UMINUS,&X,&B);}
         1062  +              {spanUnaryPrefix(&A,pParse,TK_UMINUS,&X,&B);/*A-overwrites-B*/}
  1056   1063   expr(A) ::= PLUS(B) expr(X). [BITNOT]
  1057         -                               {spanUnaryPrefix(&A,pParse,TK_UPLUS,&X,&B);}
         1064  +              {spanUnaryPrefix(&A,pParse,TK_UPLUS,&X,&B);/*A-overwrites-B*/}
  1058   1065   
  1059   1066   %type between_op {int}
  1060   1067   between_op(A) ::= BETWEEN.     {A = 0;}
  1061   1068   between_op(A) ::= NOT BETWEEN. {A = 1;}
  1062   1069   expr(A) ::= expr(A) between_op(N) expr(X) AND expr(Y). [BETWEEN] {
  1063   1070     ExprList *pList = sqlite3ExprListAppend(pParse,0, X.pExpr);
  1064   1071     pList = sqlite3ExprListAppend(pParse,pList, Y.pExpr);
................................................................................
  1123   1130           sqlite3ExprListDelete(pParse->db, Y);
  1124   1131         }
  1125   1132         exprNot(pParse, N, &A);
  1126   1133       }
  1127   1134       A.zEnd = &E.z[E.n];
  1128   1135     }
  1129   1136     expr(A) ::= LP(B) select(X) RP(E). {
         1137  +    spanSet(&A,&B,&E); /*A-overwrites-B*/
  1130   1138       A.pExpr = sqlite3PExpr(pParse, TK_SELECT, 0, 0, 0);
  1131   1139       if( A.pExpr ){
  1132   1140         A.pExpr->x.pSelect = X;
  1133   1141         ExprSetProperty(A.pExpr, EP_xIsSelect|EP_Subquery);
  1134   1142         sqlite3ExprSetHeightAndFlags(pParse, A.pExpr);
  1135   1143       }else{
  1136   1144         sqlite3SelectDelete(pParse->db, X);
  1137   1145       }
  1138         -    A.zStart = B.z;
  1139         -    A.zEnd = &E.z[E.n];
  1140   1146     }
  1141   1147     expr(A) ::= expr(A) in_op(N) LP select(Y) RP(E).  [IN] {
  1142   1148       A.pExpr = sqlite3PExpr(pParse, TK_IN, A.pExpr, 0, 0);
  1143   1149       if( A.pExpr ){
  1144   1150         A.pExpr->x.pSelect = Y;
  1145   1151         ExprSetProperty(A.pExpr, EP_xIsSelect|EP_Subquery);
  1146   1152         sqlite3ExprSetHeightAndFlags(pParse, A.pExpr);
................................................................................
  1160   1166       }else{
  1161   1167         sqlite3SrcListDelete(pParse->db, pSrc);
  1162   1168       }
  1163   1169       exprNot(pParse, N, &A);
  1164   1170       A.zEnd = Z.z ? &Z.z[Z.n] : &Y.z[Y.n];
  1165   1171     }
  1166   1172     expr(A) ::= EXISTS(B) LP select(Y) RP(E). {
  1167         -    Expr *p = A.pExpr = sqlite3PExpr(pParse, TK_EXISTS, 0, 0, 0);
         1173  +    Expr *p;
         1174  +    spanSet(&A,&B,&E); /*A-overwrites-B*/
         1175  +    p = A.pExpr = sqlite3PExpr(pParse, TK_EXISTS, 0, 0, 0);
  1168   1176       if( p ){
  1169   1177         p->x.pSelect = Y;
  1170   1178         ExprSetProperty(p, EP_xIsSelect|EP_Subquery);
  1171   1179         sqlite3ExprSetHeightAndFlags(pParse, p);
  1172   1180       }else{
  1173   1181         sqlite3SelectDelete(pParse->db, Y);
  1174   1182       }
  1175         -    A.zStart = B.z;
  1176         -    A.zEnd = &E.z[E.n];
  1177   1183     }
  1178   1184   %endif SQLITE_OMIT_SUBQUERY
  1179   1185   
  1180   1186   /* CASE expressions */
  1181   1187   expr(A) ::= CASE(C) case_operand(X) case_exprlist(Y) case_else(Z) END(E). {
         1188  +  spanSet(&A,&C,&E);  /*A-overwrites-C*/
  1182   1189     A.pExpr = sqlite3PExpr(pParse, TK_CASE, X, 0, 0);
  1183   1190     if( A.pExpr ){
  1184   1191       A.pExpr->x.pList = Z ? sqlite3ExprListAppend(pParse,Y,Z) : Y;
  1185   1192       sqlite3ExprSetHeightAndFlags(pParse, A.pExpr);
  1186   1193     }else{
  1187   1194       sqlite3ExprListDelete(pParse->db, Y);
  1188   1195       sqlite3ExprDelete(pParse->db, Z);
  1189   1196     }
  1190         -  A.zStart = C.z;
  1191         -  A.zEnd = &E.z[E.n];
  1192   1197   }
  1193   1198   %type case_exprlist {ExprList*}
  1194   1199   %destructor case_exprlist {sqlite3ExprListDelete(pParse->db, $$);}
  1195   1200   case_exprlist(A) ::= case_exprlist(A) WHEN expr(Y) THEN expr(Z). {
  1196   1201     A = sqlite3ExprListAppend(pParse,A, Y.pExpr);
  1197   1202     A = sqlite3ExprListAppend(pParse,A, Z.pExpr);
  1198   1203   }
................................................................................
  1411   1416   
  1412   1417   
  1413   1418   %type trigger_cmd {TriggerStep*}
  1414   1419   %destructor trigger_cmd {sqlite3DeleteTriggerStep(pParse->db, $$);}
  1415   1420   // UPDATE 
  1416   1421   trigger_cmd(A) ::=
  1417   1422      UPDATE orconf(R) trnm(X) tridxby SET setlist(Y) where_opt(Z).  
  1418         -   { A = sqlite3TriggerUpdateStep(pParse->db, &X, Y, Z, R); }
         1423  +   {A = sqlite3TriggerUpdateStep(pParse->db, &X, Y, Z, R);}
  1419   1424   
  1420   1425   // INSERT
  1421   1426   trigger_cmd(A) ::= insert_cmd(R) INTO trnm(X) idlist_opt(F) select(S).
  1422         -               {A = sqlite3TriggerInsertStep(pParse->db, &X, F, S, R);}
         1427  +   {A = sqlite3TriggerInsertStep(pParse->db, &X, F, S, R);/*A-overwrites-R*/}
  1423   1428   
  1424   1429   // DELETE
  1425   1430   trigger_cmd(A) ::= DELETE FROM trnm(X) tridxby where_opt(Y).
  1426         -               {A = sqlite3TriggerDeleteStep(pParse->db, &X, Y);}
         1431  +   {A = sqlite3TriggerDeleteStep(pParse->db, &X, Y);}
  1427   1432   
  1428   1433   // SELECT
  1429   1434   trigger_cmd(A) ::= select(X).
  1430         -               {A = sqlite3TriggerSelectStep(pParse->db, X); /*A-overwrites-X*/}
         1435  +   {A = sqlite3TriggerSelectStep(pParse->db, X); /*A-overwrites-X*/}
  1431   1436   
  1432   1437   // The special RAISE expression that may occur in trigger programs
  1433   1438   expr(A) ::= RAISE(X) LP IGNORE RP(Y).  {
  1434   1439     spanSet(&A,&X,&Y);  /*A-overwrites-X*/
  1435   1440     A.pExpr = sqlite3PExpr(pParse, TK_RAISE, 0, 0, 0); 
  1436   1441     if( A.pExpr ){
  1437   1442       A.pExpr->affinity = OE_Ignore;

Changes to tool/lemon.c.

  3473   3473   ** Return 1 if the expanded code requires that "yylhsminor" local variable
  3474   3474   ** to be defined.
  3475   3475   */
  3476   3476   PRIVATE int translate_code(struct lemon *lemp, struct rule *rp){
  3477   3477     char *cp, *xp;
  3478   3478     int i;
  3479   3479     int rc = 0;            /* True if yylhsminor is used */
         3480  +  int dontUseRhs0 = 0;   /* If true, use of left-most RHS label is illegal */
  3480   3481     const char *zSkip = 0; /* The zOvwrt comment within rp->code, or NULL */
  3481   3482     char lhsused = 0;      /* True if the LHS element has been used */
  3482   3483     char lhsdirect;        /* True if LHS writes directly into stack */
  3483   3484     char used[MAXRHS];     /* True for each RHS element which is used */
  3484   3485     char zLhs[50];         /* Convert the LHS symbol into this string */
  3485   3486     char zOvwrt[900];      /* Comment that to allow LHS to overwrite RHS */
  3486   3487   
................................................................................
  3545   3546     append_str(0,0,0,0);
  3546   3547   
  3547   3548     /* This const cast is wrong but harmless, if we're careful. */
  3548   3549     for(cp=(char *)rp->code; *cp; cp++){
  3549   3550       if( cp==zSkip ){
  3550   3551         append_str(zOvwrt,0,0,0);
  3551   3552         cp += lemonStrlen(zOvwrt)-1;
         3553  +      dontUseRhs0 = 1;
  3552   3554         continue;
  3553   3555       }
  3554   3556       if( ISALPHA(*cp) && (cp==rp->code || (!ISALNUM(cp[-1]) && cp[-1]!='_')) ){
  3555   3557         char saved;
  3556   3558         for(xp= &cp[1]; ISALNUM(*xp) || *xp=='_'; xp++);
  3557   3559         saved = *xp;
  3558   3560         *xp = 0;
................................................................................
  3559   3561         if( rp->lhsalias && strcmp(cp,rp->lhsalias)==0 ){
  3560   3562           append_str(zLhs,0,0,0);
  3561   3563           cp = xp;
  3562   3564           lhsused = 1;
  3563   3565         }else{
  3564   3566           for(i=0; i<rp->nrhs; i++){
  3565   3567             if( rp->rhsalias[i] && strcmp(cp,rp->rhsalias[i])==0 ){
  3566         -            if( cp!=rp->code && cp[-1]=='@' ){
         3568  +            if( i==0 && dontUseRhs0 ){
         3569  +              ErrorMsg(lemp->filename,rp->ruleline,
         3570  +                 "Label %s used after '%s'.",
         3571  +                 rp->rhsalias[0], zOvwrt);
         3572  +              lemp->errorcnt++;
         3573  +            }else if( cp!=rp->code && cp[-1]=='@' ){
  3567   3574                 /* If the argument is of the form @X then substituted
  3568   3575                 ** the token number of X, not the value of X */
  3569   3576                 append_str("yymsp[%d].major",-1,i-rp->nrhs+1,0);
  3570   3577               }else{
  3571   3578                 struct symbol *sp = rp->rhs[i];
  3572   3579                 int dtnum;
  3573   3580                 if( sp->type==MULTITERMINAL ){

Changes to tool/lempar.c.

   633    633     if( yyRuleInfo[yyruleno].nrhs==0 ){
   634    634   #ifdef YYTRACKMAXSTACKDEPTH
   635    635       if( yypParser->yyidx>yypParser->yyidxMax ){
   636    636         yypParser->yyidxMax = yypParser->yyidx;
   637    637       }
   638    638   #endif
   639    639   #if YYSTACKDEPTH>0 
   640         -    if( yypParser->yyidx>=YYSTACKDEPTH ){
          640  +    if( yypParser->yyidx>=YYSTACKDEPTH-1 ){
   641    641         yyStackOverflow(yypParser);
   642    642         return;
   643    643       }
   644    644   #else
   645         -    if( yypParser->yyidx>=yypParser->yystksz ){
          645  +    if( yypParser->yyidx>=yypParser->yystksz-1 ){
   646    646         yyGrowStack(yypParser);
   647         -      if( yypParser->yyidx>=yypParser->yystksz ){
          647  +      if( yypParser->yyidx>=yypParser->yystksz-1 ){
   648    648           yyStackOverflow(yypParser);
   649    649           return;
   650    650         }
   651    651       }
   652    652   #endif
   653    653     }
   654    654