**    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.364 2007/12/08 21:10:20 drh Exp $
*/
#include "sqliteInt.h"


/*
** Delete all the content of a Select structure but do not deallocate
** the select structure itself.
................................................................................
  }
  if( db->mallocFailed ){
    rc = SQLITE_NOMEM;
  }
  return rc;
}

/*
** During the process of matching ORDER BY terms to columns of the 
** result set, the Exprlist.a[].done flag can be set to one of the
** following values:
*/
#define ORDERBY_MATCH_NONE     0   /* No match found */
#define ORDERBY_MATCH_PARTIAL  1   /* A good match, but not perfect */
#define ORDERBY_MATCH_EXACT    2   /* An exact match seen */

#ifndef SQLITE_OMIT_COMPOUND_SELECT
/*
** This routine associates entries in an ORDER BY expression list with
** columns in a result.  For each ORDER BY expression, the opcode of
** the top-level node is changed to TK_COLUMN and the iColumn value of
** the top-level node is filled in with column number and the iTable
** value of the top-level node is filled with iTable parameter.
**
** If there are prior SELECT clauses, they are processed first.  A match
** in an earlier SELECT takes precedence over a later SELECT.
**
** Any entry that does not match is flagged as an error.  The number
** of errors is returned.
*/
static int matchOrderbyToColumn(
  Parse *pParse,          /* A place to leave error messages */
  Select *pSelect,        /* Match to result columns of this SELECT */
  ExprList *pOrderBy,     /* The ORDER BY values to match against columns */
  int iTable,             /* Insert this value in iTable */
  int rightMost           /* TRUE for outermost recursive invocation */
){
  int nErr = 0;
  int i, j;
  ExprList *pEList;
  sqlite3 *db = pParse->db;
  NameContext nc;


  if( pSelect==0 || pOrderBy==0 ) return 1;
  if( rightMost ){
    assert( pSelect->pOrderBy==pOrderBy );
    for(i=0; i<pOrderBy->nExpr; i++){
      pOrderBy->a[i].done = ORDERBY_MATCH_NONE;
    }
  }
  if( pSelect->pPrior
      && matchOrderbyToColumn(pParse, pSelect->pPrior, pOrderBy, iTable, 0) ){
    return 1;
  }
  if( sqlite3SelectResolve(pParse, pSelect, 0) ){
    return 1;
  }
  memset(&nc, 0, sizeof(nc));
  nc.pParse = pParse;
  nc.pSrcList = pSelect->pSrc;

  nc.pEList = pEList = pSelect->pEList;
  nc.allowAgg = 1;
  for(i=0; nErr==0 && i<pOrderBy->nExpr; i++){
    struct ExprList_item *pItem;
    Expr *pE = pOrderBy->a[i].pExpr;
    int iCol = -1;
    int match = ORDERBY_MATCH_NONE;
    Expr *pDup;

    if( pOrderBy->a[i].done==ORDERBY_MATCH_EXACT ){
      continue;
    }
    if( sqlite3ExprIsInteger(pE, &iCol) ){
      if( iCol<=0 || iCol>pEList->nExpr ){
        sqlite3ErrorMsg(pParse,
          "ORDER BY position %d should be between 1 and %d",
          iCol, pEList->nExpr);

        nErr++;
        break;
      }
      if( !rightMost ) continue;
      iCol--;

      match = ORDERBY_MATCH_EXACT;



    }
    if( !match && pParse->nErr==0 && (pDup = sqlite3ExprDup(db, pE))!=0 ){







      nc.nErr = 0;
      assert( pParse->zErrMsg==0 );
      if( sqlite3ExprResolveNames(&nc, pDup) ){
        sqlite3ErrorClear(pParse);
      }else{

        for(j=0, pItem=pEList->a; j<pEList->nExpr; j++, pItem++){
          if( sqlite3ExprCompare(pItem->pExpr, pDup) ){





            iCol = j;
            match = ORDERBY_MATCH_PARTIAL;
            break;
          }
        }
      }

      sqlite3ExprDelete(pDup);
    }
    if( match ){






      pE->op = TK_COLUMN;
      pE->iTable = iTable;
      pE->iAgg = -1;
      if( pOrderBy->a[i].done!=ORDERBY_MATCH_NONE && pE->iColumn!=iCol ){
        sqlite3ErrorMsg(pParse,
          "ORDER BY term number %d is ambiguous", i+1);
        nErr++;
      }
      pE->iColumn = iCol;
      pOrderBy->a[i].done = match;
    }else if( rightMost && pOrderBy->a[i].done==ORDERBY_MATCH_NONE ){
      sqlite3ErrorMsg(pParse,
        "ORDER BY term number %d does not match any result column", i+1);
      nErr++;
      break;
    }
  }





  return nErr;  
}
#endif /* #ifndef SQLITE_OMIT_COMPOUND_SELECT */

/*
** Get a VDBE for the given parser context.  Create a new one if necessary.
** If an error occurs, return NULL and leave a message in pParse.
*/
................................................................................
        */
        unionTab = iParm;
      }else{
        /* We will need to create our own temporary table to hold the
        ** intermediate results.
        */
        unionTab = pParse->nTab++;
        if( pOrderBy && matchOrderbyToColumn(pParse, p, pOrderBy, unionTab,1) ){
          rc = 1;
          goto multi_select_end;
        }
        addr = sqlite3VdbeAddOp(v, OP_OpenEphemeral, unionTab, 0);
        if( priorOp==SRT_Table ){
          assert( nSetP2<sizeof(aSetP2)/sizeof(aSetP2[0]) );
          aSetP2[nSetP2++] = addr;
................................................................................

      /* INTERSECT is different from the others since it requires
      ** two temporary tables.  Hence it has its own case.  Begin
      ** by allocating the tables we will need.
      */
      tab1 = pParse->nTab++;
      tab2 = pParse->nTab++;
      if( pOrderBy && matchOrderbyToColumn(pParse,p,pOrderBy,tab1,1) ){
        rc = 1;
        goto multi_select_end;
      }
      createSortingIndex(pParse, p, pOrderBy);

      addr = sqlite3VdbeAddOp(v, OP_OpenEphemeral, tab1, 0);
      assert( p->addrOpenEphm[0] == -1 );

**    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.365 2007/12/10 18:51:48 danielk1977 Exp $
*/
#include "sqliteInt.h"


/*
** Delete all the content of a Select structure but do not deallocate
** the select structure itself.
................................................................................
  }
  if( db->mallocFailed ){
    rc = SQLITE_NOMEM;
  }
  return rc;
}










#ifndef SQLITE_OMIT_COMPOUND_SELECT
/*
** This routine associates entries in an ORDER BY expression list with
** columns in a result.  For each ORDER BY expression, the opcode of
** the top-level node is changed to TK_COLUMN and the iColumn value of
** the top-level node is filled in with column number and the iTable
** value of the top-level node is filled with iTable parameter.
**



** Any entry that does not match is flagged as an error.  The number
** of errors is returned.
*/
static int matchOrderbyToColumn(
  Parse *pParse,          /* A place to leave error messages */
  Select *pSelect,        /* Match to result columns of this SELECT */
  ExprList *pOrderBy,     /* The ORDER BY values to match against columns */
  int iTable              /* Insert this value in iTable */

){
  int nErr = 0;
  int i, j;

  sqlite3 *db = pParse->db;

  int nExpr;

  if( pSelect==0 || pOrderBy==0 ) return 1;










  if( sqlite3SelectResolve(pParse, pSelect, 0) ){
    return 1;
  }




  nExpr = pSelect->pEList->nExpr;

  for(i=0; nErr==0 && i<pOrderBy->nExpr; i++){

    Expr *pE = pOrderBy->a[i].pExpr;
    int iCol = -1;






    if( sqlite3ExprIsInteger(pE, &iCol) ){
      if( iCol<=0 || iCol>nExpr ){
        sqlite3ErrorMsg(pParse,
          "ORDER BY position %d should be between 1 and %d",

          iCol, nExpr);
        nErr++;
        break;
      }

      iCol--;
    }else{
      Select *p;
      for(p=pSelect; p; p=p->pPrior){
        ExprList *pEList = p->pEList;
        Expr *pDup = sqlite3ExprDup(db, pE);


        NameContext nc;

        memset(&nc, 0, sizeof(nc));
        nc.pParse = pParse;
        nc.pSrcList = p->pSrc;
        nc.pEList = pEList;
        nc.allowAgg = 1;
        nc.nErr = 0;

        if( sqlite3ExprResolveNames(&nc, pDup) ){
          sqlite3ErrorClear(pParse);
        }else{
          struct ExprList_item *pItem;
          for(j=0, pItem=pEList->a; j<pEList->nExpr; j++, pItem++){
            if( sqlite3ExprCompare(pItem->pExpr, pDup) ){
              if( iCol>=0 && iCol!=j ){
                sqlite3ErrorMsg(
                    pParse, "ORDER BY term number %d is ambiguous", i+1
                );
              }else{
                iCol = j;


              }
            }
          }
        }
        sqlite3ExprDelete(pDup);
      }

    }

    if( iCol<0 ){
      sqlite3ErrorMsg(pParse,
        "ORDER BY term number %d does not match any result column", i+1);
    }else{
      pE->op = TK_COLUMN;
      pE->iTable = iTable;
      pE->iAgg = -1;





      pE->iColumn = iCol;
      pOrderBy->a[i].done = 1;





    }

    if( pParse->nErr ){
      return pParse->nErr;
    }
  }

  return SQLITE_OK;
}
#endif /* #ifndef SQLITE_OMIT_COMPOUND_SELECT */

/*
** Get a VDBE for the given parser context.  Create a new one if necessary.
** If an error occurs, return NULL and leave a message in pParse.
*/
................................................................................
        */
        unionTab = iParm;
      }else{
        /* We will need to create our own temporary table to hold the
        ** intermediate results.
        */
        unionTab = pParse->nTab++;
        if( pOrderBy && matchOrderbyToColumn(pParse, p, pOrderBy, unionTab) ){
          rc = 1;
          goto multi_select_end;
        }
        addr = sqlite3VdbeAddOp(v, OP_OpenEphemeral, unionTab, 0);
        if( priorOp==SRT_Table ){
          assert( nSetP2<sizeof(aSetP2)/sizeof(aSetP2[0]) );
          aSetP2[nSetP2++] = addr;
................................................................................

      /* INTERSECT is different from the others since it requires
      ** two temporary tables.  Hence it has its own case.  Begin
      ** by allocating the tables we will need.
      */
      tab1 = pParse->nTab++;
      tab2 = pParse->nTab++;
      if( pOrderBy && matchOrderbyToColumn(pParse,p,pOrderBy,tab1) ){
        rc = 1;
        goto multi_select_end;
      }
      createSortingIndex(pParse, p, pOrderBy);

      addr = sqlite3VdbeAddOp(v, OP_OpenEphemeral, tab1, 0);
      assert( p->addrOpenEphm[0] == -1 );

#    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 UNION, INTERSECT and EXCEPT operators
# in SELECT statements.
#
# $Id: select4.test,v 1.21 2007/12/08 21:10:20 drh Exp $

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

# Most tests in this file depend on compound-select. But there are a couple
# right at the end that test DISTINCT, so we cannot omit the entire file.
#
................................................................................
      SELECT 4 AS a, 5 AS b
    ) ORDER BY x LIMIT 1;
  }
} {x 0 y 1}
} ;# ifcapable subquery

do_test select4-9.8 {
  execsql2 {
    SELECT 0 AS x, 1 AS y
    UNION
    SELECT 2 AS y, -3 AS x
    ORDER BY x LIMIT 1;
  }
} {x 0 y 1}

do_test select4-9.9.1 {
  execsql2 {
    SELECT 1 AS a, 2 AS b UNION ALL SELECT 3 AS b, 4 AS a
  }
} {a 1 b 2 a 3 b 4}

ifcapable subquery {

#    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 UNION, INTERSECT and EXCEPT operators
# in SELECT statements.
#
# $Id: select4.test,v 1.22 2007/12/10 18:51:48 danielk1977 Exp $

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

# Most tests in this file depend on compound-select. But there are a couple
# right at the end that test DISTINCT, so we cannot omit the entire file.
#
................................................................................
      SELECT 4 AS a, 5 AS b
    ) ORDER BY x LIMIT 1;
  }
} {x 0 y 1}
} ;# ifcapable subquery

do_test select4-9.8 {
  catchsql {
    SELECT 0 AS x, 1 AS y
    UNION
    SELECT 2 AS y, -3 AS x
    ORDER BY x LIMIT 1;
  }
} {1 {ORDER BY term number 1 is ambiguous}}

do_test select4-9.9.1 {
  execsql2 {
    SELECT 1 AS a, 2 AS b UNION ALL SELECT 3 AS b, 4 AS a
  }
} {a 1 b 2 a 3 b 4}

ifcapable subquery {

# 2007 Dec 4
#
# 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 is to test that the issues surrounding expressions in
# ORDER BY clauses on compound SELECT statements raised by ticket
# #2822 have been dealt with.
#
# $Id: tkt2822.test,v 1.1 2007/12/10 18:51:48 danielk1977 Exp $
#

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

# Test plan:
#
#   tkt2820-1.* - Simple identifier as ORDER BY expression.
#   tkt2820-2.* - More complex ORDER BY expressions.

do_test tkt2820-1.1 {
  execsql {
    CREATE TABLE t1(a, b, c);
    CREATE TABLE t2(c, b, a);

    INSERT INTO t1 VALUES(1, 2, 3);
    INSERT INTO t2 VALUES(3, 2, 1);
  }
} {}

# If an ORDER BY expression matches two different columns, it is an error.
#
do_test tkt2820-1.2 {
  catchsql {
    SELECT a, b FROM t1 UNION ALL SELECT b, a FROM t2 ORDER BY a;
  }
} {1 {ORDER BY term number 1 is ambiguous}}
do_test tkt2820-1.3 {
  catchsql {
    SELECT a, b, c FROM t2 UNION ALL SELECT c, b, a FROM t1 ORDER BY a;
  }
} {1 {ORDER BY term number 1 is ambiguous}}

# But not if it matches the same column in two or more of the
# compounded SELECT statements.
#
do_test tkt2820-1.4 {
  execsql {
    SELECT a, b, c FROM t2 UNION ALL SELECT a, b, c FROM t1 ORDER BY a;
  }
} {1 2 3 1 2 3}

do_test tkt2820-1.5 {
  execsql {
    SELECT a, b FROM t2 UNION ALL SELECT c, b FROM t1 ORDER BY c;
  }
} {1 2 3 2}

# If a match cannot be found in any SELECT, return an error.
#
do_test tkt2820-1.6 {
  catchsql {
    SELECT * FROM t2 UNION ALL SELECT * FROM t1 ORDER BY d;
  }
} {1 {ORDER BY term number 1 does not match any result column}}


do_test tkt2820-2.1 {
  execsql {
    SELECT a+1, b+1 FROM t1 UNION ALL SELECT a, c FROM t2 ORDER BY a+1;
  }
} {1 3 2 3}
do_test tkt2820-2.2 {
  catchsql {
    SELECT a+1, b+1 FROM t1 UNION ALL SELECT a, c FROM t2 ORDER BY a+2;
  }
} {1 {ORDER BY term number 1 does not match any result column}}
do_test tkt2820-2.3 {
  catchsql {
    SELECT a+1, b+1 FROM t1 UNION ALL SELECT c, a+1 FROM t2 ORDER BY a+1;
  }
} {1 {ORDER BY term number 1 is ambiguous}}

do_test tkt2820-2.4 {
  execsql {
    SELECT t1.a, b+1 FROM t1 UNION ALL SELECT c, a+1 FROM t2 ORDER BY a;
  }
} {1 3 3 2}
do_test tkt2820-2.5 {
  execsql {
    SELECT t1.a, b+1 FROM t1 UNION ALL SELECT c, a+1 FROM t2 ORDER BY t1.a;
  }
} {1 3 3 2}

finish_test