/ Check-in [e22c090f]
Login

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

Overview
Comment:Another attempt at fixing the table generator in lemon. Again, this does not effect the SQLite grammar.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: e22c090f35b3a2bac64781d33aa1123ed765dbbf
User & Date: drh 2010-01-07 03:53:04
Context
2010-01-07
10:54
Fixes to problems in FTS3 snippet() function found by th3 tests. check-in: 3b5ccd26 user: dan tags: trunk
03:53
Another attempt at fixing the table generator in lemon. Again, this does not effect the SQLite grammar. check-in: e22c090f user: drh tags: trunk
2010-01-06
18:36
Fix a segfault that can occur following an OOM in the FTS3 snippet() function check-in: c7e5966e user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to tool/lemon.c.

   405    405   /********************** New code to implement the "acttab" module ***********/
   406    406   /*
   407    407   ** This module implements routines use to construct the yy_action[] table.
   408    408   */
   409    409   
   410    410   /*
   411    411   ** The state of the yy_action table under construction is an instance of
   412         -** the following structure
          412  +** the following structure.
          413  +**
          414  +** The yy_action table maps the pair (state_number, lookahead) into an
          415  +** action_number.  The table is an array of integers pairs.  The state_number
          416  +** determines an initial offset into the yy_action array.  The lookahead
          417  +** value is then added to this initial offset to get an index X into the
          418  +** yy_action array. If the aAction[X].lookahead equals the value of the
          419  +** of the lookahead input, then the value of the action_number output is
          420  +** aAction[X].action.  If the lookaheads do not match then the
          421  +** default action for the state_number is returned.
          422  +**
          423  +** All actions associated with a single state_number are first entered
          424  +** into aLookahead[] using multiple calls to acttab_action().  Then the 
          425  +** actions for that single state_number are placed into the aAction[] 
          426  +** array with a single call to acttab_insert().  The acttab_insert() call
          427  +** also resets the aLookahead[] array in preparation for the next
          428  +** state number.
   413    429   */
   414    430   typedef struct acttab acttab;
   415    431   struct acttab {
   416    432     int nAction;                 /* Number of used slots in aAction[] */
   417    433     int nActionAlloc;            /* Slots allocated for aAction[] */
   418    434     struct {
   419    435       int lookahead;             /* Value of the lookahead token */
................................................................................
   450    466       fprintf(stderr,"Unable to allocate memory for a new acttab.");
   451    467       exit(1);
   452    468     }
   453    469     memset(p, 0, sizeof(*p));
   454    470     return p;
   455    471   }
   456    472   
   457         -/* Add a new action to the current transaction set
          473  +/* Add a new action to the current transaction set.  
          474  +**
          475  +** This routine is called once for each lookahead for a particular
          476  +** state.
   458    477   */
   459    478   void acttab_action(acttab *p, int lookahead, int action){
   460    479     if( p->nLookahead>=p->nLookaheadAlloc ){
   461    480       p->nLookaheadAlloc += 25;
   462    481       p->aLookahead = realloc( p->aLookahead,
   463    482                                sizeof(p->aLookahead[0])*p->nLookaheadAlloc );
   464    483       if( p->aLookahead==0 ){
................................................................................
   487    506   ** into the current action table.  Then reset the transaction set back
   488    507   ** to an empty set in preparation for a new round of acttab_action() calls.
   489    508   **
   490    509   ** Return the offset into the action table of the new transaction.
   491    510   */
   492    511   int acttab_insert(acttab *p){
   493    512     int i, j, k, n;
   494         -  int nActtab;     /* Number of slots in the p->aAction[] table */
   495    513     assert( p->nLookahead>0 );
   496    514   
   497    515     /* Make sure we have enough space to hold the expanded action table
   498    516     ** in the worst case.  The worst case occurs if the transaction set
   499    517     ** must be appended to the current action table
   500    518     */
   501    519     n = p->mxLookahead + 1;
   502         -  nActtab = p->nAction + n;
   503         -  if( nActtab >= p->nActionAlloc ){
          520  +  if( p->nAction + n >= p->nActionAlloc ){
   504    521       int oldAlloc = p->nActionAlloc;
   505    522       p->nActionAlloc = p->nAction + n + p->nActionAlloc + 20;
   506    523       p->aAction = realloc( p->aAction,
   507    524                             sizeof(p->aAction[0])*p->nActionAlloc);
   508    525       if( p->aAction==0 ){
   509    526         fprintf(stderr,"malloc failed\n");
   510    527         exit(1);
................................................................................
   511    528       }
   512    529       for(i=oldAlloc; i<p->nActionAlloc; i++){
   513    530         p->aAction[i].lookahead = -1;
   514    531         p->aAction[i].action = -1;
   515    532       }
   516    533     }
   517    534   
   518         -  /* Scan the existing action table looking for an offset where we can
   519         -  ** insert the current transaction set.  Fall out of the loop when that
   520         -  ** offset is found.  In the worst case, we fall out of the loop when
   521         -  ** i reaches nActtab, which means we append the new transaction set.
          535  +  /* Scan the existing action table looking for an offset that is a 
          536  +  ** duplicate of the current transaction set.  Fall out of the loop
          537  +  ** if and when the duplicate is found.
   522    538     **
   523    539     ** i is the index in p->aAction[] where p->mnLookahead is inserted.
   524    540     */
   525         -  for(i=nActtab-1; i>=0; i--){
   526         -    /* First look for an existing action table entry that can be reused */
          541  +  for(i=p->nAction-1; i>=0; i--){
   527    542       if( p->aAction[i].lookahead==p->mnLookahead ){
          543  +      /* All lookaheads and actions in the aLookahead[] transaction
          544  +      ** must match against the candidate aAction[i] entry. */
   528    545         if( p->aAction[i].action!=p->mnAction ) continue;
   529    546         for(j=0; j<p->nLookahead; j++){
   530    547           k = p->aLookahead[j].lookahead - p->mnLookahead + i;
   531    548           if( k<0 || k>=p->nAction ) break;
   532    549           if( p->aLookahead[j].lookahead!=p->aAction[k].lookahead ) break;
   533    550           if( p->aLookahead[j].action!=p->aAction[k].action ) break;
   534    551         }
   535    552         if( j<p->nLookahead ) continue;
          553  +
          554  +      /* No possible lookahead value that is not in the aLookahead[]
          555  +      ** transaction is allowed to match aAction[i] */
   536    556         n = 0;
   537    557         for(j=0; j<p->nAction; j++){
   538    558           if( p->aAction[j].lookahead<0 ) continue;
   539    559           if( p->aAction[j].lookahead==j+p->mnLookahead-i ) n++;
   540    560         }
   541    561         if( n==p->nLookahead ){
   542         -        break;  /* Same as a prior transaction set */
          562  +        break;  /* An exact match is found at offset i */
   543    563         }
   544    564       }
   545    565     }
          566  +
          567  +  /* If no existing offsets exactly match the current transaction, find an
          568  +  ** an empty offset in the aAction[] table in which we can add the
          569  +  ** aLookahead[] transaction.
          570  +  */
   546    571     if( i<0 ){
   547         -    /* If no reusable entry is found, look for an empty slot */
   548         -    for(i=0; i<nActtab; i++){
          572  +    /* Look for holes in the aAction[] table that fit the current
          573  +    ** aLookahead[] transaction.  Leave i set to the offset of the hole.
          574  +    ** If no holes are found, i is left at p->nAction, which means the
          575  +    ** transaction will be appended. */
          576  +    for(i=0; i<p->nActionAlloc - p->mxLookahead; i++){
   549    577         if( p->aAction[i].lookahead<0 ){
   550    578           for(j=0; j<p->nLookahead; j++){
   551    579             k = p->aLookahead[j].lookahead - p->mnLookahead + i;
   552    580             if( k<0 ) break;
   553    581             if( p->aAction[k].lookahead>=0 ) break;
   554    582           }
   555    583           if( j<p->nLookahead ) continue;