SQLite

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains C code routines that are called by the parser
** to handle SELECT statements in SQLite.
**
** $Id: select.c,v 1.188 2004/06/11 13:19:21 danielk1977 Exp $
*/
#include "sqliteInt.h"


/*
** Allocate a new Select structure and return a pointer to that
** structure.

      }
    }
  }

  /* Reset the aggregator
  */
  if( isAgg ){
    int addr = sqlite3VdbeAddOp(v, OP_AggReset, 0, pParse->nAgg);
    for(i=0; i<pParse->nAgg; i++){
      FuncDef *pFunc;
      if( (pFunc = pParse->aAgg[i].pFunc)!=0 && pFunc->xFinalize!=0 ){
        sqlite3VdbeOp3(v, OP_AggInit, 0, i, (char*)pFunc, P3_FUNCDEF);
      }
    }
    if( pGroupBy==0 ){
      sqlite3VdbeAddOp(v, OP_String8, 0, 0);
      sqlite3VdbeAddOp(v, OP_AggFocus, 0, 0);
    }else{
      int sz = sizeof(KeyInfo) + pGroupBy->nExpr*sizeof(CollSeq*);
      KeyInfo *pKey = (KeyInfo *)sqliteMalloc(sz);
      if( 0==pKey ){
        goto select_end;
      }
      pKey->enc = pParse->db->enc;
      pKey->nField = pGroupBy->nExpr;
      for(i=0; i<pGroupBy->nExpr; i++){
        pKey->aColl[i] = sqlite3ExprCollSeq(pParse, pGroupBy->a[i].pExpr);
        if( !pKey->aColl[i] ){
          pKey->aColl[i] = pParse->db->pDfltColl;
        }
      }
      sqlite3VdbeChangeP3(v, addr, (char *)pKey, P3_KEYINFO_HANDOFF);
    }
  }

  /* Initialize the memory cell to NULL
  */
  if( eDest==SRT_Mem ){
    sqlite3VdbeAddOp(v, OP_String8, 0, 0);

**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.365 2004/06/11 13:19:21 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*

/*
** Insert a new aggregate element and make it the element that
** has focus.
**
** Return 0 on success and 1 if memory is exhausted.
*/
static int AggInsert(Agg *p, char *zKey, int nKey){
  AggElem *pElem;
  int i;
  int rc;
  pElem = sqliteMalloc( sizeof(AggElem) + nKey +
                        (p->nMem-1)*sizeof(pElem->aMem[0]) );
  if( pElem==0 ) return SQLITE_NOMEM;
  pElem->zKey = (char*)&pElem->aMem[p->nMem];
  memcpy(pElem->zKey, zKey, nKey);
  pElem->nKey = nKey;

  assert( p->pCsr );
  rc = sqlite3BtreeInsert(p->pCsr, zKey, nKey, &pElem, sizeof(AggElem*));
  if( rc!=SQLITE_OK ){
    sqliteFree(pElem);
    return rc;
  }

  for(i=0; i<p->nMem; i++){
    pElem->aMem[i].flags = MEM_Null;
  }
  p->pCurrent = pElem;
  return 0;
}

/*
** Get the AggElem currently in focus
*/
#if 0
#define AggInFocus(P)   ((P).pCurrent ? (P).pCurrent : _AggInFocus(&(P)))
static AggElem *_AggInFocus(Agg *p){
  HashElem *pElem = sqliteHashFirst(&p->hash);
  if( pElem==0 ){
    AggInsert(p,"",1);
    pElem = sqliteHashFirst(&p->hash);
  }
  return pElem ? sqliteHashData(pElem) : 0;
}
#endif
/*
** Store a pointer to the AggElem currently in focus in *ppElem. Return
** SQLITE_OK if successful, otherwise an error-code.
*/
static int AggInFocus(Agg *p, AggElem **ppElem){
  int rc;
  int res;

  if( p->pCurrent ){
    *ppElem = p->pCurrent;
    return SQLITE_OK;
  }

  rc = sqlite3BtreeFirst(p->pCsr, &res);
  if( rc!=SQLITE_OK ){
    return rc;
  }
  if( res!=0 ){
    rc = AggInsert(p,"",1);
    *ppElem = p->pCurrent;
  }else{
    rc = sqlite3BtreeData(p->pCsr, 0, 4, (char *)ppElem);
  }
  return rc;
}

/*
** Pop the stack N times.
*/
static void popStack(Mem **ppTos, int N){
  Mem *pTos = *ppTos;
  while( N>0 ){

  ** immediately call the destructor for any non-static values.
  */
  if( ctx.pVdbeFunc ){
    int mask = pOp->p2;
    for(i=0; i<ctx.pVdbeFunc->nAux; i++){
      struct AuxData *pAux = &ctx.pVdbeFunc->apAux[i];
      if( (i>31 || !(mask&(1<<i))) && pAux->pAux ){
        if( pAux->xDelete ){
          pAux->xDelete(pAux->pAux);
        }
        pAux->pAux = 0;
      }
    }
    pOp->p3 = (char *)ctx.pVdbeFunc;
    pOp->p3type = P3_VDBEFUNC;
  }

  pMem->i++;
  if( pOp->p2>0 && pMem->i>0 ){
     pc = pOp->p2 - 1;
  }
  break;
}

/* Opcode: AggReset * P2 P3
**
** Reset the aggregator so that it no longer contains any data.
** Future aggregator elements will contain P2 values each and be sorted
** using the KeyInfo structure pointed to by P3.
*/
case OP_AggReset: {
  assert( !pOp->p3 || pOp->p3type==P3_KEYINFO );
  rc = sqlite3VdbeAggReset(db, &p->agg, (KeyInfo *)pOp->p3);
  if( rc!=SQLITE_OK ){
    goto abort_due_to_error;
  }
  p->agg.nMem = pOp->p2;
  p->agg.apFunc = sqliteMalloc( p->agg.nMem*sizeof(p->agg.apFunc[0]) );
  if( p->agg.apFunc==0 ) goto no_mem;
  break;
}

/* Opcode: AggInit * P2 P3

** The order of aggregator opcodes is important.  The order is:
** AggReset AggFocus AggNext.  In other words, you must execute
** AggReset first, then zero or more AggFocus operations, then
** zero or more AggNext operations.  You must not execute an AggFocus
** in between an AggNext and an AggReset.
*/
case OP_AggFocus: {

  char *zKey;
  int nKey;
  int res;
  assert( pTos>=p->aStack );
  Stringify(pTos, db->enc);
  zKey = pTos->z;
  nKey = pTos->n;
  rc = sqlite3BtreeMoveto(p->agg.pCsr, zKey, nKey, &res);
  if( rc!=SQLITE_OK ){
    goto abort_due_to_error;
  }
  if( res==0 ){
    rc = sqlite3BtreeData(p->agg.pCsr, 0, sizeof(AggElem*),
        (char *)&p->agg.pCurrent);
    if( rc!=SQLITE_OK ){
      goto abort_due_to_error;
    }
    pc = pOp->p2 - 1;
  }else{
    rc = AggInsert(&p->agg, zKey, nKey);
    if( rc!=SQLITE_OK ){
      goto abort_due_to_error;
    }
  }
  Release(pTos);
  pTos--;
  break; 
}

/* Opcode: AggSet * P2 *
**
** Move the top of the stack into the P2-th field of the current
** aggregate.  String values are duplicated into new memory.
*/
case OP_AggSet: {
  AggElem *pFocus;
  int i = pOp->p2;
  Mem *pMem;
  rc = AggInFocus(&p->agg, &pFocus);
  if( rc!=SQLITE_OK ) goto abort_due_to_error;
  assert( pTos>=p->aStack );
  if( pFocus==0 ) goto no_mem;
  assert( i>=0 && i<p->agg.nMem );
  Deephemeralize(pTos);
  pMem = &pFocus->aMem[i];
  Release(pMem);
  *pMem = *pTos;

/* Opcode: AggGet * P2 *
**
** Push a new entry onto the stack which is a copy of the P2-th field
** of the current aggregate.  Strings are not duplicated so
** string values will be ephemeral.
*/
case OP_AggGet: {
  AggElem *pFocus;
  Mem *pMem;
  int i = pOp->p2;
  rc = AggInFocus(&p->agg, &pFocus);
  if( rc!=SQLITE_OK ) goto abort_due_to_error;
  if( pFocus==0 ) goto no_mem;
  assert( i>=0 && i<p->agg.nMem );
  pTos++;
  pMem = &pFocus->aMem[i];
  *pTos = *pMem;
  if( pTos->flags & (MEM_Str|MEM_Blob) ){
    pTos->flags &= ~(MEM_Dyn|MEM_Static|MEM_Short);

** The order of aggregator opcodes is important.  The order is:
** AggReset AggFocus AggNext.  In other words, you must execute
** AggReset first, then zero or more AggFocus operations, then
** zero or more AggNext operations.  You must not execute an AggFocus
** in between an AggNext and an AggReset.
*/
case OP_AggNext: {
  int res;
  CHECK_FOR_INTERRUPT;
  if( p->agg.searching==0 ){
    p->agg.searching = 1;
    rc = sqlite3BtreeFirst(p->agg.pCsr, &res);
    if( rc!=SQLITE_OK ) goto abort_due_to_error;
  }else{
    rc = sqlite3BtreeNext(p->agg.pCsr, &res);
    if( rc!=SQLITE_OK ) goto abort_due_to_error;
  }
  if( res!=0 ){
    pc = pOp->p2 - 1;
  }else{
    int i;
    sqlite3_context ctx;
    Mem *aMem;

    rc = sqlite3BtreeData(p->agg.pCsr, 0, sizeof(AggElem*),
        (char *)&p->agg.pCurrent);
    if( rc!=SQLITE_OK ){
      goto abort_due_to_error;
    }
    aMem = p->agg.pCurrent->aMem;
    for(i=0; i<p->agg.nMem; i++){
      int freeCtx;
      if( p->agg.apFunc[i]==0 ) continue;
      if( p->agg.apFunc[i]->xFinalize==0 ) continue;
      ctx.s.flags = MEM_Null;
      ctx.s.z = aMem[i].zShort;

** the GROUP BY clause of a select.
*/
typedef struct Agg Agg;
typedef struct AggElem AggElem;
struct Agg {
  int nMem;            /* Number of values stored in each AggElem */
  AggElem *pCurrent;   /* The AggElem currently in focus */
  FuncDef **apFunc;    /* Information about aggregate functions */
#if 0
  HashElem *pSearch;   /* The hash element for pCurrent */
  Hash hash;           /* Hash table of all aggregate elements */

#endif
  Btree *pBtree;       /* The temporary btree used to group elements */
  BtCursor *pCsr;      /* Read/write cursor to the table in pBtree */
  int nTab;            /* Root page of the table in pBtree */
  u8 searching;        /* True between the first AggNext and AggReset */
};
struct AggElem {
  char *zKey;          /* The key to this AggElem */
  int nKey;            /* Number of bytes in the key, including '\0' at end */
  Mem aMem[1];         /* The values for this AggElem */
};

#define VDBE_MAGIC_DEAD     0xb606c3c8    /* The VDBE has been deallocated */

/*
** Function prototypes
*/
void sqlite3VdbeCleanupCursor(Cursor*);
void sqlite3VdbeSorterReset(Vdbe*);
int sqlite3VdbeAggReset(sqlite *, Agg *, KeyInfo *);
void sqlite3VdbeKeylistFree(Keylist*);
void sqliteVdbePopStack(Vdbe*,int);
int sqlite3VdbeCursorMoveto(Cursor*);
#if !defined(NDEBUG) || defined(VDBE_PROFILE)
void sqlite3VdbePrintOp(FILE*, int, Op*);
#endif
int sqlite3VdbeSerialTypeLen(u32);

    p->azColName = (char**)&p->apArg[n];
    p->apVar = (Mem *)&p->azColName[n];
    for(n=0; n<p->nVar; n++){
      p->apVar[n].flags = MEM_Null;
    }
  }



#ifdef SQLITE_DEBUG
  if( (p->db->flags & SQLITE_VdbeListing)!=0
    || sqlite3OsFileExists("vdbe_explain")
  ){
    int i;
    printf("VDBE Program Listing:\n");
    for(i=0; i<p->nOp; i++){

**
** For installable aggregate functions, if the step function has been
** called, make sure the finalizer function has also been called.  The
** finalizer might need to free memory that was allocated as part of its
** private context.  If the finalizer has not been called yet, call it
** now.
*/
#if 0
void sqlite3VdbeAggReset(Agg *pAgg){
  int i;
  HashElem *p;
  for(p = sqliteHashFirst(&pAgg->hash); p; p = sqliteHashNext(p)){
    AggElem *pElem = sqliteHashData(p);
    assert( pAgg->apFunc!=0 );
    for(i=0; i<pAgg->nMem; i++){

  sqlite3HashClear(&pAgg->hash);
  sqliteFree(pAgg->apFunc);
  pAgg->apFunc = 0;
  pAgg->pCurrent = 0;
  pAgg->pSearch = 0;
  pAgg->nMem = 0;
}
#endif

/*
** Reset an Agg structure.  Delete all its contents.
**
** For installable aggregate functions, if the step function has been
** called, make sure the finalizer function has also been called.  The
** finalizer might need to free memory that was allocated as part of its
** private context.  If the finalizer has not been called yet, call it
** now.
**
** If db is NULL, then this is being called from sqliteVdbeReset(). In
** this case clean up all references to the temp-table used for
** aggregates (if it was ever opened).
**
** If db is not NULL, then this is being called from with an OP_AggReset
** opcode. Open the temp-table, if it has not already been opened and
** delete the contents of the table used for aggregate information, ready
** for the next round of aggregate processing.
*/
int sqlite3VdbeAggReset(sqlite *db, Agg *pAgg, KeyInfo *pKeyInfo){
  int i;
  int rc = 0;
  BtCursor *pCsr = pAgg->pCsr;

  assert( (pCsr && pAgg->nTab>0) || (!pCsr && pAgg->nTab==0)
         || sqlite3_malloc_failed );

  /* If pCsr is not NULL, then the table used for aggregate information
  ** is open. Loop through it and free the AggElem* structure pointed at
  ** by each entry. If the finalizer has not been called for an AggElem,
  ** do that too. Finally, clear the btree table itself.
  */
  if( pCsr ){
    int res;
    assert( pAgg->pBtree );
    assert( pAgg->nTab>0 );

    rc=sqlite3BtreeFirst(pCsr, &res);
    while( res==0 && rc==SQLITE_OK ){
      AggElem *pElem;
      rc = sqlite3BtreeData(pCsr, 0, sizeof(AggElem*), (char *)&pElem);
      if( res!=SQLITE_OK ){
        return rc;
      }
      assert( pAgg->apFunc!=0 );
      for(i=0; i<pAgg->nMem; i++){
        Mem *pMem = &pElem->aMem[i];
        if( pAgg->apFunc[i] && (pMem->flags & MEM_AggCtx)!=0 ){
          sqlite3_context ctx;
          ctx.pFunc = pAgg->apFunc[i];
          ctx.s.flags = MEM_Null;
          ctx.pAgg = pMem->z;
          ctx.cnt = pMem->i;
          ctx.isStep = 0;
          ctx.isError = 0;
          (*pAgg->apFunc[i]->xFinalize)(&ctx);
          if( pMem->z!=0 && pMem->z!=pMem->z ){
            sqliteFree(pMem->z);
          }
        }else if( pMem->flags&MEM_Dyn ){
          sqliteFree(pMem->z);
        }
      }
      sqliteFree(pElem);
      rc=sqlite3BtreeNext(pCsr, &res);
    }
    if( rc!=SQLITE_OK ){
      return rc;
    }

    sqlite3BtreeCloseCursor(pCsr);
    sqlite3BtreeClearTable(pAgg->pBtree, pAgg->nTab);
  }

  /* If db is not NULL and we have not yet and we have not yet opened
  ** the temporary btree then do so and create the table to store aggregate
  ** information.
  **
  ** If db is NULL, then close the temporary btree if it is open.
  */
  if( db ){
    if( !pAgg->pBtree ){
      assert( pAgg->nTab==0 );
      rc = sqlite3BtreeFactory(db, 0, 0, TEMP_PAGES, &pAgg->pBtree);
      if( rc!=SQLITE_OK ) return rc;
      sqlite3BtreeBeginTrans(pAgg->pBtree, 1, 0);
      rc = sqlite3BtreeCreateTable(pAgg->pBtree, &pAgg->nTab, 0);
      if( rc!=SQLITE_OK ) return rc;
    }
    assert( pAgg->nTab!=0 );

    rc = sqlite3BtreeCursor(pAgg->pBtree, pAgg->nTab, 1,
        sqlite3VdbeRecordCompare, pKeyInfo, &pAgg->pCsr);
    if( rc!=SQLITE_OK ) return rc;
  }else{
    if( pAgg->pBtree ){
      sqlite3BtreeClose(pAgg->pBtree);
      pAgg->pBtree = 0;
      pAgg->nTab = 0;
    }
    pAgg->pCsr = 0;
  }

  if( pAgg->apFunc ){ 
    sqliteFree(pAgg->apFunc);
    pAgg->apFunc = 0;
  }
  pAgg->pCurrent = 0;
  pAgg->nMem = 0;
  pAgg->searching = 0;
  return SQLITE_OK;
}


/*
** Delete a keylist
*/
void sqlite3VdbeKeylistFree(Keylist *p){
  while( p ){
    Keylist *pNext = p->pNext;

  }
  p->nField = 0;
  if( p->zLine ){
    sqliteFree(p->zLine);
    p->zLine = 0;
  }
  p->nLineAlloc = 0;
  sqlite3VdbeAggReset(0, &p->agg, 0);
  if( p->keylistStack ){
    int ii;
    for(ii = 0; ii < p->keylistStackDepth; ii++){
      sqlite3VdbeKeylistFree(p->keylistStack[ii]);
    }
    sqliteFree(p->keylistStack);
    p->keylistStackDepth = 0;

    /* If the current encoding does not match the desired encoding, then
    ** we will need to do some translation between encodings.
    */
    char *z;
    int n;
    int rc;

    rc = sqlite3utfTranslate(pMem->z, pMem->n, pMem->enc, (void **)&z, 
        &n, desiredEnc);
    if( rc!=SQLITE_OK ){
      return rc;
    }
    if( pMem->flags&MEM_Dyn ){
      sqliteFree(pMem->z);
    }
    /* Result of sqlite3utfTranslate is currently always dynamically

#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing aggregate functions and the
# GROUP BY and HAVING clauses of SELECT statements.
#
# $Id: select3.test,v 1.11 2004/06/11 13:19:22 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Build some test data
#
do_test select3-1.0 {

    SELECT log*2+1 as x, count(*) FROM t1 GROUP BY x ORDER BY x
  }
} {1 1 3 1 5 2 7 4 9 8 11 15}
do_test select3-2.7 {
  execsql {
    SELECT log*2+1 AS x, count(*) AS y FROM t1 GROUP BY x ORDER BY y
  }
} {3 1 1 1 5 2 7 4 9 8 11 15}
do_test select3-2.8 {
  execsql {
    SELECT log*2+1 AS x, count(*) AS y FROM t1 GROUP BY x ORDER BY 10-(x+y)
  }
} {11 15 9 8 7 4 5 2 3 1 1 1}
do_test select3-2.9 {
  catchsql {