/*** 2001 September 15**** The author disclaims copyright to this source code.  In place of** a legal notice, here is a blessing:****    May you do good and not evil.**    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.161.2.4 2004/07/20 01:45:49 drh Exp $*/#include "sqliteInt.h"/*** Allocate a new Select structure and return a pointer to that** structure.*/Select *sqliteSelectNew(  ExprList *pEList,     /* which columns to include in the result */  SrcList *pSrc,        /* the FROM clause -- which tables to scan */  Expr *pWhere,         /* the WHERE clause */  ExprList *pGroupBy,   /* the GROUP BY clause */  Expr *pHaving,        /* the HAVING clause */  ExprList *pOrderBy,   /* the ORDER BY clause */  int isDistinct,       /* true if the DISTINCT keyword is present */  int nLimit,           /* LIMIT value.  -1 means not used */  int nOffset           /* OFFSET value.  0 means no offset */){  Select *pNew;  pNew = sqliteMalloc( sizeof(*pNew) );  if( pNew==0 ){    sqliteExprListDelete(pEList);    sqliteSrcListDelete(pSrc);    sqliteExprDelete(pWhere);    sqliteExprListDelete(pGroupBy);    sqliteExprDelete(pHaving);    sqliteExprListDelete(pOrderBy);  }else{    if( pEList==0 ){      pEList = sqliteExprListAppend(0, sqliteExpr(TK_ALL,0,0,0), 0);    }    pNew->pEList = pEList;    pNew->pSrc = pSrc;    pNew->pWhere = pWhere;    pNew->pGroupBy = pGroupBy;    pNew->pHaving = pHaving;    pNew->pOrderBy = pOrderBy;    pNew->isDistinct = isDistinct;    pNew->op = TK_SELECT;    pNew->nLimit = nLimit;    pNew->nOffset = nOffset;    pNew->iLimit = -1;    pNew->iOffset = -1;  }  return pNew;}/*** Given 1 to 3 identifiers preceeding the JOIN keyword, determine the** type of join.  Return an integer constant that expresses that type** in terms of the following bit values:****     JT_INNER**     JT_OUTER**     JT_NATURAL**     JT_LEFT**     JT_RIGHT**** A full outer join is the combination of JT_LEFT and JT_RIGHT.**** If an illegal or unsupported join type is seen, then still return** a join type, but put an error in the pParse structure.*/int sqliteJoinType(Parse *pParse, Token *pA, Token *pB, Token *pC){  int jointype = 0;  Token *apAll[3];  Token *p;  static struct {    const char *zKeyword;    int nChar;    int code;  } keywords[] = {    { "natural", 7, JT_NATURAL },    { "left",    4, JT_LEFT|JT_OUTER },    { "right",   5, JT_RIGHT|JT_OUTER },    { "full",    4, JT_LEFT|JT_RIGHT|JT_OUTER },    { "outer",   5, JT_OUTER },    { "inner",   5, JT_INNER },    { "cross",   5, JT_INNER },  };  int i, j;  apAll[0] = pA;  apAll[1] = pB;  apAll[2] = pC;  for(i=0; i<3 && apAll[i]; i++){    p = apAll[i];    for(j=0; j<sizeof(keywords)/sizeof(keywords[0]); j++){      if( p->n==keywords[j].nChar           && sqliteStrNICmp(p->z, keywords[j].zKeyword, p->n)==0 ){        jointype |= keywords[j].code;        break;      }    }    if( j>=sizeof(keywords)/sizeof(keywords[0]) ){      jointype |= JT_ERROR;      break;    }  }  if(     (jointype & (JT_INNER|JT_OUTER))==(JT_INNER|JT_OUTER) ||     (jointype & JT_ERROR)!=0  ){    static Token dummy = { 0, 0 };    char *zSp1 = " ", *zSp2 = " ";    if( pB==0 ){ pB = &dummy; zSp1 = 0; }    if( pC==0 ){ pC = &dummy; zSp2 = 0; }    sqliteSetNString(&pParse->zErrMsg, "unknown or unsupported join type: ", 0,       pA->z, pA->n, zSp1, 1, pB->z, pB->n, zSp2, 1, pC->z, pC->n, 0);    pParse->nErr++;    jointype = JT_INNER;  }else if( jointype & JT_RIGHT ){    sqliteErrorMsg(pParse,       "RIGHT and FULL OUTER JOINs are not currently supported");    jointype = JT_INNER;  }  return jointype;}/*** Return the index of a column in a table.  Return -1 if the column** is not contained in the table.*/static int columnIndex(Table *pTab, const char *zCol){  int i;  for(i=0; i<pTab->nCol; i++){    if( sqliteStrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;  }  return -1;}/*** Add a term to the WHERE expression in *ppExpr that requires the** zCol column to be equal in the two tables pTab1 and pTab2.*/static void addWhereTerm(  const char *zCol,        /* Name of the column */  const Table *pTab1,      /* First table */  const Table *pTab2,      /* Second table */  Expr **ppExpr            /* Add the equality term to this expression */){  Token dummy;  Expr *pE1a, *pE1b, *pE1c;  Expr *pE2a, *pE2b, *pE2c;  Expr *pE;  dummy.z = zCol;  dummy.n = strlen(zCol);  dummy.dyn = 0;  pE1a = sqliteExpr(TK_ID, 0, 0, &dummy);  pE2a = sqliteExpr(TK_ID, 0, 0, &dummy);  dummy.z = pTab1->zName;  dummy.n = strlen(dummy.z);  pE1b = sqliteExpr(TK_ID, 0, 0, &dummy);  dummy.z = pTab2->zName;  dummy.n = strlen(dummy.z);  pE2b = sqliteExpr(TK_ID, 0, 0, &dummy);  pE1c = sqliteExpr(TK_DOT, pE1b, pE1a, 0);  pE2c = sqliteExpr(TK_DOT, pE2b, pE2a, 0);  pE = sqliteExpr(TK_EQ, pE1c, pE2c, 0);  ExprSetProperty(pE, EP_FromJoin);  if( *ppExpr ){    *ppExpr = sqliteExpr(TK_AND, *ppExpr, pE, 0);  }else{    *ppExpr = pE;  }}/*** Set the EP_FromJoin property on all terms of the given expression.**** The EP_FromJoin property is used on terms of an expression to tell** the LEFT OUTER JOIN processing logic that this term is part of the** join restriction specified in the ON or USING clause and not a part** of the more general WHERE clause.  These terms are moved over to the** WHERE clause during join processing but we need to remember that they** originated in the ON or USING clause.*/static void setJoinExpr(Expr *p){  while( p ){    ExprSetProperty(p, EP_FromJoin);    setJoinExpr(p->pLeft);    p = p->pRight;  } }/*** This routine processes the join information for a SELECT statement.** ON and USING clauses are converted into extra terms of the WHERE clause.** NATURAL joins also create extra WHERE clause terms.**** This routine returns the number of errors encountered.*/static int sqliteProcessJoin(Parse *pParse, Select *p){  SrcList *pSrc;  int i, j;  pSrc = p->pSrc;  for(i=0; i<pSrc->nSrc-1; i++){    struct SrcList_item *pTerm = &pSrc->a[i];    struct SrcList_item *pOther = &pSrc->a[i+1];    if( pTerm->pTab==0 || pOther->pTab==0 ) continue;    /* When the NATURAL keyword is present, add WHERE clause terms for    ** every column that the two tables have in common.    */    if( pTerm->jointype & JT_NATURAL ){      Table *pTab;      if( pTerm->pOn || pTerm->pUsing ){        sqliteErrorMsg(pParse, "a NATURAL join may not have "           "an ON or USING clause", 0);        return 1;      }      pTab = pTerm->pTab;      for(j=0; j<pTab->nCol; j++){        if( columnIndex(pOther->pTab, pTab->aCol[j].zName)>=0 ){          addWhereTerm(pTab->aCol[j].zName, pTab, pOther->pTab, &p->pWhere);        }      }    }    /* Disallow both ON and USING clauses in the same join    */    if( pTerm->pOn && pTerm->pUsing ){      sqliteErrorMsg(pParse, "cannot have both ON and USING "        "clauses in the same join");      return 1;    }    /* Add the ON clause to the end of the WHERE clause, connected by    ** and AND operator.    */    if( pTerm->pOn ){      setJoinExpr(pTerm->pOn);      if( p->pWhere==0 ){        p->pWhere = pTerm->pOn;      }else{        p->pWhere = sqliteExpr(TK_AND, p->pWhere, pTerm->pOn, 0);      }      pTerm->pOn = 0;    }    /* Create extra terms on the WHERE clause for each column named    ** in the USING clause.  Example: If the two tables to be joined are     ** A and B and the USING clause names X, Y, and Z, then add this    ** to the WHERE clause:    A.X=B.X AND A.Y=B.Y AND A.Z=B.Z    ** Report an error if any column mentioned in the USING clause is    ** not contained in both tables to be joined.    */    if( pTerm->pUsing ){      IdList *pList;      int j;      assert( i<pSrc->nSrc-1 );      pList = pTerm->pUsing;      for(j=0; j<pList->nId; j++){        if( columnIndex(pTerm->pTab, pList->a[j].zName)<0 ||            columnIndex(pOther->pTab, pList->a[j].zName)<0 ){          sqliteErrorMsg(pParse, "cannot join using column %s - column "            "not present in both tables", pList->a[j].zName);          return 1;        }        addWhereTerm(pList->a[j].zName, pTerm->pTab, pOther->pTab, &p->pWhere);      }    }  }  return 0;}/*** Delete the given Select structure and all of its substructures.*/void sqliteSelectDelete(Select *p){  if( p==0 ) return;  sqliteExprListDelete(p->pEList);  sqliteSrcListDelete(p->pSrc);  sqliteExprDelete(p->pWhere);  sqliteExprListDelete(p->pGroupBy);  sqliteExprDelete(p->pHaving);  sqliteExprListDelete(p->pOrderBy);  sqliteSelectDelete(p->pPrior);  sqliteFree(p->zSelect);  sqliteFree(p);}/*** Delete the aggregate information from the parse structure.*/static void sqliteAggregateInfoReset(Parse *pParse){  sqliteFree(pParse->aAgg);  pParse->aAgg = 0;  pParse->nAgg = 0;  pParse->useAgg = 0;}/*** Insert code into "v" that will push the record on the top of the** stack into the sorter.*/static void pushOntoSorter(Parse *pParse, Vdbe *v, ExprList *pOrderBy){  char *zSortOrder;  int i;  zSortOrder = sqliteMalloc( pOrderBy->nExpr + 1 );  if( zSortOrder==0 ) return;  for(i=0; i<pOrderBy->nExpr; i++){    int order = pOrderBy->a[i].sortOrder;    int type;    int c;    if( (order & SQLITE_SO_TYPEMASK)==SQLITE_SO_TEXT ){      type = SQLITE_SO_TEXT;    }else if( (order & SQLITE_SO_TYPEMASK)==SQLITE_SO_NUM ){      type = SQLITE_SO_NUM;    }else if( pParse->db->file_format>=4 ){      type = sqliteExprType(pOrderBy->a[i].pExpr);    }else{      type = SQLITE_SO_NUM;    }    if( (order & SQLITE_SO_DIRMASK)==SQLITE_SO_ASC ){      c = type==SQLITE_SO_TEXT ? 'A' : '+';    }else{      c = type==SQLITE_SO_TEXT ? 'D' : '-';    }    zSortOrder[i] = c;    sqliteExprCode(pParse, pOrderBy->a[i].pExpr);  }  zSortOrder[pOrderBy->nExpr] = 0;  sqliteVdbeOp3(v, OP_SortMakeKey, pOrderBy->nExpr, 0, zSortOrder, P3_DYNAMIC);  sqliteVdbeAddOp(v, OP_SortPut, 0, 0);}/*** This routine adds a P3 argument to the last VDBE opcode that was** inserted. The P3 argument added is a string suitable for the ** OP_MakeKey or OP_MakeIdxKey opcodes.  The string consists of** characters 't' or 'n' depending on whether or not the various** fields of the key to be generated should be treated as numeric** or as text.  See the OP_MakeKey and OP_MakeIdxKey opcode** documentation for additional information about the P3 string.** See also the sqliteAddIdxKeyType() routine.*/void sqliteAddKeyType(Vdbe *v, ExprList *pEList){  int nColumn = pEList->nExpr;  char *zType = sqliteMalloc( nColumn+1 );  int i;  if( zType==0 ) return;  for(i=0; i<nColumn; i++){    zType[i] = sqliteExprType(pEList->a[i].pExpr)==SQLITE_SO_NUM ? 'n' : 't';  }  zType[i] = 0;  sqliteVdbeChangeP3(v, -1, zType, P3_DYNAMIC);}/*** Add code to implement the OFFSET and LIMIT*/static void codeLimiter(  Vdbe *v,          /* Generate code into this VM */  Select *p,        /* The SELECT statement being coded */  int iContinue,    /* Jump here to skip the current record */  int iBreak,       /* Jump here to end the loop */  int nPop          /* Number of times to pop stack when jumping */){  if( p->iOffset>=0 ){    int addr = sqliteVdbeCurrentAddr(v) + 2;    if( nPop>0 ) addr++;    sqliteVdbeAddOp(v, OP_MemIncr, p->iOffset, addr);    if( nPop>0 ){      sqliteVdbeAddOp(v, OP_Pop, nPop, 0);    }    sqliteVdbeAddOp(v, OP_Goto, 0, iContinue);  }  if( p->iLimit>=0 ){    sqliteVdbeAddOp(v, OP_MemIncr, p->iLimit, iBreak);  }}/*** This routine generates the code for the inside of the inner loop** of a SELECT.