/ Check-in [d66a0f31]
Login

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

Overview
Comment:Adjust the lemon implementation so that it always computes the same PDA regardless of qsort() implementation on the host platform. In other words, make all sorts in lemon stable.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:d66a0f31ebcc56e6f0f462b3db6aab54f7fab816
User & Date: drh 2009-11-03 13:02:26
Context
2009-11-03
13:08
Force all qsort() calls in mkkeywordhash.c to be stable so that we get predictable results on different platforms. check-in: 3b02df27 user: drh tags: trunk
13:02
Adjust the lemon implementation so that it always computes the same PDA regardless of qsort() implementation on the host platform. In other words, make all sorts in lemon stable. check-in: d66a0f31 user: drh tags: trunk
01:22
All SQLITE_MAX_VARIABLE_NUMBER to exceed 32767. The sizes of some structures increase when the compile-time parameter is configured this way. check-in: 16a24b44 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to tool/lemon.c.

365
366
367
368
369
370
371



372
373
374
375
376
377
378
....
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
....
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
....
3512
3513
3514
3515
3516
3517
3518

3519
3520
3521
3522
3523
3524
3525
3526

3527





3528
3529
3530
3531
3532
3533
3534
....
3680
3681
3682
3683
3684
3685
3686

3687
3688
3689
3690
3691
3692
3693
....
4093
4094
4095
4096
4097
4098
4099


4100


4101
4102
4103
4104
4105
4106
4107
....
4397
4398
4399
4400
4401
4402
4403

4404
4405
4406
4407
4408
4409
4410
  rc = ap1->sp->index - ap2->sp->index;
  if( rc==0 ){
    rc = (int)ap1->type - (int)ap2->type;
  }
  if( rc==0 && ap1->type==REDUCE ){
    rc = ap1->x.rp->index - ap2->x.rp->index;
  }



  return rc;
}

/* Sort parser actions */
static struct action *Action_sort(
  struct action *ap
){
................................................................................
  char *ptr, *head;

  if( a==0 ){
    head = b;
  }else if( b==0 ){
    head = a;
  }else{
    if( (*cmp)(a,b)<0 ){
      ptr = a;
      a = NEXT(a);
    }else{
      ptr = b;
      b = NEXT(b);
    }
    head = ptr;
    while( a && b ){
      if( (*cmp)(a,b)<0 ){
        NEXT(ptr) = a;
        ptr = a;
        a = NEXT(a);
      }else{
        NEXT(ptr) = b;
        ptr = b;
        b = NEXT(b);
................................................................................
    for(i=0; i<LISTSIZE-1 && set[i]!=0; i++){
      ep = merge(ep,set[i],cmp,offset);
      set[i] = 0;
    }
    set[i] = ep;
  }
  ep = 0;
  for(i=0; i<LISTSIZE; i++) if( set[i] ) ep = merge(ep,set[i],cmp,offset);
  return ep;
}
/************************ From the file "option.c" **************************/
static char **argv;
static struct s_options *op;
static FILE *errstream;

................................................................................
** of the following structure.  An array of these structures is used
** to order the creation of entries in the yy_action[] table.
*/
struct axset {
  struct state *stp;   /* A pointer to a state */
  int isTkn;           /* True to use tokens.  False for non-terminals */
  int nAction;         /* Number of actions */

};

/*
** Compare to axset structures for sorting purposes
*/
static int axset_compare(const void *a, const void *b){
  struct axset *p1 = (struct axset*)a;
  struct axset *p2 = (struct axset*)b;

  return p2->nAction - p1->nAction;





}

/*
** Write text on "out" that describes the rule "rp".
*/
static void writeRuleText(FILE *out, struct rule *rp){
  int j;
................................................................................
  mxTknOfst = mnTknOfst = 0;
  mxNtOfst = mnNtOfst = 0;

  /* Compute the action table.  In order to try to keep the size of the
  ** action table to a minimum, the heuristic of placing the largest action
  ** sets first is used.
  */

  qsort(ax, lemp->nstate*2, sizeof(ax[0]), axset_compare);
  pActtab = acttab_alloc();
  for(i=0; i<lemp->nstate*2 && ax[i].nAction>0; i++){
    stp = ax[i].stp;
    if( ax[i].isTkn ){
      for(ap=stp->ap; ap; ap=ap->next){
        int action;
................................................................................
  const struct state *pA = *(const struct state**)a;
  const struct state *pB = *(const struct state**)b;
  int n;

  n = pB->nNtAct - pA->nNtAct;
  if( n==0 ){
    n = pB->nTknAct - pA->nTknAct;


  }


  return n;
}


/*
** Renumber and resort states so that states with fewer choices
** occur at the end.  Except, keep state 0 as the first state.
................................................................................
** We find experimentally that leaving the symbols in their original
** order (the order they appeared in the grammar file) gives the
** smallest parser tables in SQLite.
*/
int Symbolcmpp(struct symbol **a, struct symbol **b){
  int i1 = (**a).index + 10000000*((**a).name[0]>'Z');
  int i2 = (**b).index + 10000000*((**b).name[0]>'Z');

  return i1-i2;
}

/* There is one instance of the following structure for each
** associative array of type "x2".
*/
struct s_x2 {







>
>
>







 







|








|







 







|







 







>








>
|
>
>
>
>
>







 







>







 







>
>
|
>
>







 







>







365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
....
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
....
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
....
3515
3516
3517
3518
3519
3520
3521
3522
3523
3524
3525
3526
3527
3528
3529
3530
3531
3532
3533
3534
3535
3536
3537
3538
3539
3540
3541
3542
3543
3544
....
3690
3691
3692
3693
3694
3695
3696
3697
3698
3699
3700
3701
3702
3703
3704
....
4104
4105
4106
4107
4108
4109
4110
4111
4112
4113
4114
4115
4116
4117
4118
4119
4120
4121
4122
....
4412
4413
4414
4415
4416
4417
4418
4419
4420
4421
4422
4423
4424
4425
4426
  rc = ap1->sp->index - ap2->sp->index;
  if( rc==0 ){
    rc = (int)ap1->type - (int)ap2->type;
  }
  if( rc==0 && ap1->type==REDUCE ){
    rc = ap1->x.rp->index - ap2->x.rp->index;
  }
  if( rc==0 ){
    rc = ap2 - ap1;
  }
  return rc;
}

/* Sort parser actions */
static struct action *Action_sort(
  struct action *ap
){
................................................................................
  char *ptr, *head;

  if( a==0 ){
    head = b;
  }else if( b==0 ){
    head = a;
  }else{
    if( (*cmp)(a,b)<=0 ){
      ptr = a;
      a = NEXT(a);
    }else{
      ptr = b;
      b = NEXT(b);
    }
    head = ptr;
    while( a && b ){
      if( (*cmp)(a,b)<=0 ){
        NEXT(ptr) = a;
        ptr = a;
        a = NEXT(a);
      }else{
        NEXT(ptr) = b;
        ptr = b;
        b = NEXT(b);
................................................................................
    for(i=0; i<LISTSIZE-1 && set[i]!=0; i++){
      ep = merge(ep,set[i],cmp,offset);
      set[i] = 0;
    }
    set[i] = ep;
  }
  ep = 0;
  for(i=0; i<LISTSIZE; i++) if( set[i] ) ep = merge(set[i],ep,cmp,offset);
  return ep;
}
/************************ From the file "option.c" **************************/
static char **argv;
static struct s_options *op;
static FILE *errstream;

................................................................................
** of the following structure.  An array of these structures is used
** to order the creation of entries in the yy_action[] table.
*/
struct axset {
  struct state *stp;   /* A pointer to a state */
  int isTkn;           /* True to use tokens.  False for non-terminals */
  int nAction;         /* Number of actions */
  int iOrder;          /* Original order of action sets */
};

/*
** Compare to axset structures for sorting purposes
*/
static int axset_compare(const void *a, const void *b){
  struct axset *p1 = (struct axset*)a;
  struct axset *p2 = (struct axset*)b;
  int c;
  c = p2->nAction - p1->nAction;
  if( c==0 ){
    c = p2->iOrder - p1->iOrder;
  }
  assert( c!=0 || p1==p2 );
  return c;
}

/*
** Write text on "out" that describes the rule "rp".
*/
static void writeRuleText(FILE *out, struct rule *rp){
  int j;
................................................................................
  mxTknOfst = mnTknOfst = 0;
  mxNtOfst = mnNtOfst = 0;

  /* Compute the action table.  In order to try to keep the size of the
  ** action table to a minimum, the heuristic of placing the largest action
  ** sets first is used.
  */
  for(i=0; i<lemp->nstate*2; i++) ax[i].iOrder = i;
  qsort(ax, lemp->nstate*2, sizeof(ax[0]), axset_compare);
  pActtab = acttab_alloc();
  for(i=0; i<lemp->nstate*2 && ax[i].nAction>0; i++){
    stp = ax[i].stp;
    if( ax[i].isTkn ){
      for(ap=stp->ap; ap; ap=ap->next){
        int action;
................................................................................
  const struct state *pA = *(const struct state**)a;
  const struct state *pB = *(const struct state**)b;
  int n;

  n = pB->nNtAct - pA->nNtAct;
  if( n==0 ){
    n = pB->nTknAct - pA->nTknAct;
    if( n==0 ){
      n = pB->statenum - pA->statenum;
    }
  }
  assert( n!=0 );
  return n;
}


/*
** Renumber and resort states so that states with fewer choices
** occur at the end.  Except, keep state 0 as the first state.
................................................................................
** We find experimentally that leaving the symbols in their original
** order (the order they appeared in the grammar file) gives the
** smallest parser tables in SQLite.
*/
int Symbolcmpp(struct symbol **a, struct symbol **b){
  int i1 = (**a).index + 10000000*((**a).name[0]>'Z');
  int i2 = (**b).index + 10000000*((**b).name[0]>'Z');
  assert( i1!=i2 || strcmp((**a).name,(**b).name)==0 );
  return i1-i2;
}

/* There is one instance of the following structure for each
** associative array of type "x2".
*/
struct s_x2 {