SQLite

Check-in [2c17a13583]
Login

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
Timelines: family | ancestors | descendants | both | lemon-update
Files: files | file ages | folders
SHA1: 2c17a1358353a0845b039283be79353f033e2491
User & Date: drh 2015-09-07 19:52:55.484
Context
2015-09-07
20:02
Fix an unreachable branch in the new parse automaton. (Closed-Leaf check-in: e9d604b430 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: 2c17a13583 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: 531c3974b3 user: drh tags: lemon-update)
Changes
Side-by-Side Diff Ignore Whitespace Patch
Changes to src/lempar.c.
︙
163
164
165
166
167
168
169




170
171
172

173
174
175
176
177
178
179

163
164
165
166
167
168
169
170
171
172
173
174
175

176
177
178
179
180
181
182
183








+
+
+
+


-
+








**
**   +  The value of the token stored at this level of the stack.
**      (In other words, the "major" token.)
**
**   +  The semantic value stored at this level of the stack.  This is
**      the information used by the action routines in the grammar.
**      It is sometimes called the "minor" token.
**
** After the "shift" half of a SHIFTREDUCE action, the stateno field
** actually contains the reduce action for the second half of the
** SHIFTREDUCE.
*/
struct yyStackEntry {
  YYACTIONTYPE stateno;  /* The state-number */
  YYACTIONTYPE stateno;  /* The state-number, or reduce action in SHIFTREDUCE */
  YYCODETYPE major;      /* The major token value.  This is the code
                         ** number for the token at this stack level */
  YYMINORTYPE minor;     /* The user-supplied minor token value.  This
                         ** is the value of the token  */
};
typedef struct yyStackEntry yyStackEntry;
︙
399
400
401
402
403
404
405

406
407
408
409
410
411
412

403
404
405
406
407
408
409
410
411
412
413
414
415
416
417








+








static int yy_find_shift_action(
  yyParser *pParser,        /* The parser */
  YYCODETYPE iLookAhead     /* The look-ahead token */
){
  int i;
  int stateno = pParser->yystack[pParser->yyidx].stateno;
 
  if( stateno>=YY_MIN_REDUCE ) return stateno;
  if( stateno>YY_SHIFT_COUNT
   || (i = yy_shift_ofst[stateno])==YY_SHIFT_USE_DFLT ){
    return yy_default[stateno];
  }
  assert( iLookAhead!=YYNOCODE );
  i += iLookAhead;
  if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){
︙
502
503
504
505
506
507
508
509






















510
511
512

513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528

529
530
531
532
533
534
535

536
537
538
539
540
541
542
543
544
545
546

547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564

507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538

539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554

555
556
557
558
559
560
561

562
563
564
565
566
567
568
569




570











571
572
573
574
575
576
577









+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+


-
+















-
+






-
+







-
-
-
-
+
-
-
-
-
-
-
-
-
-
-
-








   while( yypParser->yyidx>=0 ) yy_pop_parser_stack(yypParser);
   /* Here code is inserted which will execute if the parser
   ** stack every overflows */
%%
   ParseARG_STORE; /* Suppress warning about unused %extra_argument var */
}

/*
** Print tracing information for a SHIFT action
*/
#ifndef NDEBUG
static void yyTraceShift(yyParser *yypParser, int yyNewState){
  if( yyTraceFILE ){
    int i;
    if( yyNewState<YYNSTATE ){
      fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState);
      fprintf(yyTraceFILE,"%sStack:",yyTracePrompt);
      for(i=1; i<=yypParser->yyidx; i++)
        fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]);
      fprintf(yyTraceFILE,"\n");
    }else{
      fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt);
    }
  }
}
#else
# define yyTraceShift(X,Y)
#endif

/*
** Perform a shift action.  Return the number of errors.
*/
static int yy_shift(
static void yy_shift(
  yyParser *yypParser,          /* The parser to be shifted */
  int yyNewState,               /* The new state to shift in */
  int yyMajor,                  /* The major token to shift in */
  YYMINORTYPE *yypMinor         /* Pointer to the minor token to shift in */
){
  yyStackEntry *yytos;
  yypParser->yyidx++;
#ifdef YYTRACKMAXSTACKDEPTH
  if( yypParser->yyidx>yypParser->yyidxMax ){
    yypParser->yyidxMax = yypParser->yyidx;
  }
#endif
#if YYSTACKDEPTH>0 
  if( yypParser->yyidx>=YYSTACKDEPTH ){
    yyStackOverflow(yypParser, yypMinor);
    return 1;
    return;
  }
#else
  if( yypParser->yyidx>=yypParser->yystksz ){
    yyGrowStack(yypParser);
    if( yypParser->yyidx>=yypParser->yystksz ){
      yyStackOverflow(yypParser, yypMinor);
      return 1;
      return;
    }
  }
#endif
  yytos = &yypParser->yystack[yypParser->yyidx];
  yytos->stateno = (YYACTIONTYPE)yyNewState;
  yytos->major = (YYCODETYPE)yyMajor;
  yytos->minor = *yypMinor;
#ifndef NDEBUG
  if( yyTraceFILE && yypParser->yyidx>0 ){
    int i;
    if( yyNewState<YYNSTATE ){
  yyTraceShift(yypParser, yyNewState);
      fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState);
      fprintf(yyTraceFILE,"%sStack:",yyTracePrompt);
      for(i=1; i<=yypParser->yyidx; i++)
        fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]);
      fprintf(yyTraceFILE,"\n");
    }else{
      fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt);
    }
  }
#endif
  return 0;
}

/* The following table contains information about every rule that
** is used during the reduce.
*/
static const struct {
  YYCODETYPE lhs;         /* Symbol on the left-hand side of the rule */
︙
624
625
626
627
628
629
630

631
632
633
634
635
636
637
638
639
640
641
642

643
644
645
646
647

648
649
650
651
652
653
654
655
656
657

637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654


655



656

657



658
659
660
661
662
663
664








+










-
-
+
-
-
-

-
+
-
-
-








  };
  assert( yyruleno>=0 && yyruleno<sizeof(yyRuleInfo)/sizeof(yyRuleInfo[0]) );
  yygoto = yyRuleInfo[yyruleno].lhs;
  yysize = yyRuleInfo[yyruleno].nrhs;
  yypParser->yyidx -= yysize;
  yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto);
  if( yyact <= YY_MAX_SHIFTREDUCE ){
    if( yyact>YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
    /* If the reduce action popped at least
    ** one element off the stack, then we can push the new element back
    ** onto the stack here, and skip the stack overflow test in yy_shift().
    ** That gives a significant speed improvement. */
    if( yysize ){
      yypParser->yyidx++;
      yymsp -= yysize-1;
      yymsp->stateno = (YYACTIONTYPE)yyact;
      yymsp->major = (YYCODETYPE)yygoto;
      yymsp->minor = yygotominor;
#ifndef NDEBUG
      if( yyTraceFILE ){
      yyTraceShift(yypParser, yyact);
        fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyact);
      }
#endif
    }else{
      if( yy_shift(yypParser,yyact,yygoto,&yygotominor) ) yyact = 0;
      yy_shift(yypParser,yyact,yygoto,&yygotominor);
    }
    if( yyact>=YY_MIN_SHIFTREDUCE ){
      yy_reduce(yypParser, yyact - YY_MIN_SHIFTREDUCE);
    }
  }else{
    assert( yyact == YY_ACCEPT_ACTION );
    yy_accept(yypParser);
  }
}
︙
771
772
773
774
775
776
777

778
779
780



781
782
783
784
785
786
787
788
789
790
791

778
779
780
781
782
783
784
785



786
787
788




789
790
791
792
793
794
795








+
-
-
-
+
+
+
-
-
-
-








    fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]);
  }
#endif

  do{
    yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor);
    if( yyact <= YY_MAX_SHIFTREDUCE ){
      if( yyact > YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
      if( yy_shift(yypParser,yyact,yymajor,&yyminorunion)==0 ){
        yypParser->yyerrcnt--;
        yymajor = YYNOCODE;
      yy_shift(yypParser,yyact,yymajor,&yyminorunion);
      yypParser->yyerrcnt--;
      yymajor = YYNOCODE;
        if( yyact > YY_MAX_SHIFT ){
          yy_reduce(yypParser, yyact-YY_MIN_SHIFTREDUCE);
        }
      }
    }else if( yyact <= YY_MAX_REDUCE ){
      yy_reduce(yypParser,yyact-YY_MIN_REDUCE);
    }else{
      assert( yyact == YY_ERROR_ACTION );
#ifdef YYERRORSYMBOL
      int yymx;
#endif
︙
879
880
881
882
883
884
885
886

887
888
889
890
891
892

883
884
885
886
887
888
889

890
891
892
893
894
895
896








-
+







      if( yyendofinput ){
        yy_parse_failed(yypParser);
      }
      yymajor = YYNOCODE;
#endif
    }
  }while( yymajor!=YYNOCODE && yypParser->yyidx>=0 );
#ifdef SQLITE_DEBUG
#ifndef NDEBUG
  if( yyTraceFILE ){
    fprintf(yyTraceFILE,"%sReturn\n",yyTracePrompt);
  }
#endif
  return;
}
Changes to src/parse.y.
︙
583
584
585
586
587
588
589
590

591
592
593
594
595
596
597

583
584
585
586
587
588
589

590
591
592
593
594
595
596
597








-
+








}

// "seltablist" is a "Select Table List" - the content of the FROM clause
// in a SELECT statement.  "stl_prefix" is a prefix of this list.
//
stl_prefix(A) ::= seltablist(X) joinop(Y).    {
   A = X;
   if( A && A->nSrc>0 ) A->a[A->nSrc-1].fg.jointype = (u8)Y;
   if( ALWAYS(A && A->nSrc>0) ) A->a[A->nSrc-1].fg.jointype = (u8)Y;
}
stl_prefix(A) ::= .                           {A = 0;}
seltablist(A) ::= stl_prefix(X) nm(Y) dbnm(D) as(Z) indexed_opt(I)
                  on_opt(N) using_opt(U). {
  A = sqlite3SrcListAppendFromTerm(pParse,X,&Y,&D,&Z,0,N,U);
  sqlite3SrcListIndexedBy(pParse, A, &I);
}
︙
Changes to src/tokenize.c.
︙
455
456
457
458
459
460
461

462
463
464
465
466
467
468
469
470
471
472
473
474

455
456
457
458
459
460
461
462
463
464
465
466
467

468
469
470
471
472
473
474








+





-








  }
abort_parse:
  assert( nErr==0 );
  if( pParse->rc==SQLITE_OK && db->mallocFailed==0 ){
    assert( zSql[i]==0 );
    if( lastTokenParsed!=TK_SEMI ){
      sqlite3Parser(pEngine, TK_SEMI, pParse->sLastToken, pParse);
      pParse->zTail = &zSql[i];
    }
    if( pParse->rc==SQLITE_OK && db->mallocFailed==0 ){
      sqlite3Parser(pEngine, 0, pParse->sLastToken, pParse);
    }
  }
  pParse->zTail = &zSql[i];
#ifdef YYTRACKMAXSTACKDEPTH
  sqlite3_mutex_enter(sqlite3MallocMutex());
  sqlite3StatusSet(SQLITE_STATUS_PARSER_STACK,
      sqlite3ParserStackPeak(pEngine)
  );
  sqlite3_mutex_leave(sqlite3MallocMutex());
#endif /* YYDEBUG */
︙
Changes to test/misc1.test.
︙
642
643
644
645
646
647
648
649

650
651
652
653
654
655
656

642
643
644
645
646
647
648

649
650
651
652
653
654
655
656








-
+








# 2015-03-22: NULL pointer dereference after a syntax error
#
do_catchsql_test misc1-21.1 {
  select''like''like''like#0;
} {1 {near "#0": syntax error}}
do_catchsql_test misc1-21.2 {
  VALUES(0,0x0MATCH#0;
} {1 {near "#0": syntax error}}
} {1 {near ";": syntax error}}

# 2015-04-15
do_execsql_test misc1-22.1 {
  SELECT ""+3 FROM (SELECT ""+5);
} {3}

# 2015-04-19: NULL pointer dereference on a corrupt schema
︙
Changes to tool/lempar.c.
︙
157
158
159
160
161
162
163




164
165
166

167
168
169
170
171
172
173

157
158
159
160
161
162
163
164
165
166
167
168
169

170
171
172
173
174
175
176
177








+
+
+
+


-
+








**
**   +  The value of the token stored at this level of the stack.
**      (In other words, the "major" token.)
**
**   +  The semantic value stored at this level of the stack.  This is
**      the information used by the action routines in the grammar.
**      It is sometimes called the "minor" token.
**
** After the "shift" half of a SHIFTREDUCE action, the stateno field
** actually contains the reduce action for the second half of the
** SHIFTREDUCE.
*/
struct yyStackEntry {
  YYACTIONTYPE stateno;  /* The state-number */
  YYACTIONTYPE stateno;  /* The state-number, or reduce action in SHIFTREDUCE */
  YYCODETYPE major;      /* The major token value.  This is the code
                         ** number for the token at this stack level */
  YYMINORTYPE minor;     /* The user-supplied minor token value.  This
                         ** is the value of the token  */
};
typedef struct yyStackEntry yyStackEntry;
︙
388
389
390
391
392
393
394
395


396
397
398
399
400
401
402

392
393
394
395
396
397
398

399
400
401
402
403
404
405
406
407








-
+
+








*/
static int yy_find_shift_action(
  yyParser *pParser,        /* The parser */
  YYCODETYPE iLookAhead     /* The look-ahead token */
){
  int i;
  int stateno = pParser->yystack[pParser->yyidx].stateno;
 

  if( stateno>=YY_MIN_REDUCE ) return stateno; 
  if( stateno>YY_SHIFT_COUNT
   || (i = yy_shift_ofst[stateno])==YY_SHIFT_USE_DFLT ){
    return yy_default[stateno];
  }
  assert( iLookAhead!=YYNOCODE );
  i += iLookAhead;
  if( i<0 || i>=YY_ACTTAB_COUNT || yy_lookahead[i]!=iLookAhead ){
︙
492
493
494
495
496
497
498
499






















500
501
502

503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518

519
520
521
522
523
524
525

526
527
528
529
530
531
532
533
534
535
536

537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554

497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528

529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544

545
546
547
548
549
550
551

552
553
554
555
556
557
558
559




560











561
562
563
564
565
566
567









+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+


-
+















-
+






-
+







-
-
-
-
+
-
-
-
-
-
-
-
-
-
-
-








   while( yypParser->yyidx>=0 ) yy_pop_parser_stack(yypParser);
   /* Here code is inserted which will execute if the parser
   ** stack every overflows */
%%
   ParseARG_STORE; /* Suppress warning about unused %extra_argument var */
}

/*
** Print tracing information for a SHIFT action
*/
#ifndef NDEBUG
static void yyTraceShift(yyParser *yypParser, int yyNewState){
  if( yyTraceFILE ){
    int i;
    if( yyNewState<YYNSTATE ){
      fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState);
      fprintf(yyTraceFILE,"%sStack:",yyTracePrompt);
      for(i=1; i<=yypParser->yyidx; i++)
        fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]);
      fprintf(yyTraceFILE,"\n");
    }else{
      fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt);
    }
  }
}
#else
# define yyTraceShift(X,Y)
#endif

/*
** Perform a shift action.  Return the number of errors.
*/
static int yy_shift(
static void yy_shift(
  yyParser *yypParser,          /* The parser to be shifted */
  int yyNewState,               /* The new state to shift in */
  int yyMajor,                  /* The major token to shift in */
  YYMINORTYPE *yypMinor         /* Pointer to the minor token to shift in */
){
  yyStackEntry *yytos;
  yypParser->yyidx++;
#ifdef YYTRACKMAXSTACKDEPTH
  if( yypParser->yyidx>yypParser->yyidxMax ){
    yypParser->yyidxMax = yypParser->yyidx;
  }
#endif
#if YYSTACKDEPTH>0 
  if( yypParser->yyidx>=YYSTACKDEPTH ){
    yyStackOverflow(yypParser, yypMinor);
    return 1;
    return;
  }
#else
  if( yypParser->yyidx>=yypParser->yystksz ){
    yyGrowStack(yypParser);
    if( yypParser->yyidx>=yypParser->yystksz ){
      yyStackOverflow(yypParser, yypMinor);
      return 1;
      return;
    }
  }
#endif
  yytos = &yypParser->yystack[yypParser->yyidx];
  yytos->stateno = (YYACTIONTYPE)yyNewState;
  yytos->major = (YYCODETYPE)yyMajor;
  yytos->minor = *yypMinor;
#ifndef NDEBUG
  if( yyTraceFILE && yypParser->yyidx>0 ){
    int i;
    if( yyNewState<YYNSTATE ){
  yyTraceShift(yypParser, yyNewState);
      fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyNewState);
      fprintf(yyTraceFILE,"%sStack:",yyTracePrompt);
      for(i=1; i<=yypParser->yyidx; i++)
        fprintf(yyTraceFILE," %s",yyTokenName[yypParser->yystack[i].major]);
      fprintf(yyTraceFILE,"\n");
    }else{
      fprintf(yyTraceFILE,"%sShift *\n",yyTracePrompt);
    }
  }
#endif
  return 0;
}

/* The following table contains information about every rule that
** is used during the reduce.
*/
static const struct {
  YYCODETYPE lhs;         /* Symbol on the left-hand side of the rule */
︙
612
613
614
615
616
617
618
619


620
621
622
623
624
625
626
627
628
629
630
631

632
633
634
635
636

637
638
639
640
641
642
643
644
645
646

625
626
627
628
629
630
631

632
633
634
635
636
637
638
639
640
641
642
643


644



645

646



647
648
649
650
651
652
653








-
+
+










-
-
+
-
-
-

-
+
-
-
-








  */
%%
  };
  yygoto = yyRuleInfo[yyruleno].lhs;
  yysize = yyRuleInfo[yyruleno].nrhs;
  yypParser->yyidx -= yysize;
  yyact = yy_find_reduce_action(yymsp[-yysize].stateno,(YYCODETYPE)yygoto);
  if( yyact < YY_MAX_SHIFTREDUCE ){
  if( yyact <= YY_MAX_SHIFTREDUCE ){
    if( yyact>YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
    /* If the reduce action popped at least
    ** one element off the stack, then we can push the new element back
    ** onto the stack here, and skip the stack overflow test in yy_shift().
    ** That gives a significant speed improvement. */
    if( yysize ){
      yypParser->yyidx++;
      yymsp -= yysize-1;
      yymsp->stateno = (YYACTIONTYPE)yyact;
      yymsp->major = (YYCODETYPE)yygoto;
      yymsp->minor = yygotominor;
#ifndef NDEBUG
      if( yyTraceFILE ){
      yyTraceShift(yypParser, yyact);
        fprintf(yyTraceFILE,"%sShift %d\n",yyTracePrompt,yyact);
      }
#endif
    }else{
      if( yy_shift(yypParser,yyact,yygoto,&yygotominor) ) yyact = 0;
      yy_shift(yypParser,yyact,yygoto,&yygotominor);
    }
    if( yyact>=YY_MIN_SHIFTREDUCE ){
      yy_reduce(yypParser, yyact - YY_MIN_SHIFTREDUCE);
    }
  }else{
    assert( yyact == YY_ACCEPT_ACTION );
    yy_accept(yypParser);
  }
}
︙
756
757
758
759
760
761
762

763
764
765



766
767
768
769
770
771
772
773
774
775
776

763
764
765
766
767
768
769
770



771
772
773




774
775
776
777
778
779
780








+
-
-
-
+
+
+
-
-
-
-








    fprintf(yyTraceFILE,"%sInput %s\n",yyTracePrompt,yyTokenName[yymajor]);
  }
#endif

  do{
    yyact = yy_find_shift_action(yypParser,(YYCODETYPE)yymajor);
    if( yyact <= YY_MAX_SHIFTREDUCE ){
      if( yyact > YY_MAX_SHIFT ) yyact += YY_MIN_REDUCE - YY_MIN_SHIFTREDUCE;
      if( yy_shift(yypParser,yyact,yymajor,&yyminorunion)==0 ){
        yypParser->yyerrcnt--;
        yymajor = YYNOCODE;
      yy_shift(yypParser,yyact,yymajor,&yyminorunion);
      yypParser->yyerrcnt--;
      yymajor = YYNOCODE;
        if( yyact > YY_MAX_SHIFT ){
          yy_reduce(yypParser, yyact-YY_MIN_SHIFTREDUCE);
        }
      }
    }else if( yyact <= YY_MAX_REDUCE ){
      yy_reduce(yypParser,yyact-YY_MIN_REDUCE);
    }else{
      assert( yyact == YY_ERROR_ACTION );
#ifdef YYERRORSYMBOL
      int yymx;
#endif
︙