pTopNC = pTopNC->pNext;
    }
    return WRC_Prune;
  } else {
    return WRC_Abort;
  }
}






















/*
** This routine is callback for sqlite3WalkExpr().
**
** Resolve symbolic names into TK_COLUMN operators for the current
** node in the expression tree.  Return 0 to continue the search down
** the tree or 2 to abort the tree walk.

      pTopNC = pTopNC->pNext;
    }
    return WRC_Prune;
  } else {
    return WRC_Abort;
  }
}

/*
** Allocate and return a pointer to an expression to load the column iCol
** from datasource iSrc datasource in SrcList pSrc.
*/
Expr *sqlite3CreateColumnExpr(sqlite3 *db, SrcList *pSrc, int iSrc, int iCol){
  Expr *p = sqlite3ExprAlloc(db, TK_COLUMN, 0, 0);
  if( p ){
    struct SrcList_item *pItem = &pSrc->a[iSrc];
    p->pTab = pItem->pTab;
    p->iTable = pItem->iCursor;
    if( p->pTab->iPKey==iCol ){
      p->iColumn = -1;
    }else{
      p->iColumn = iCol;
      pItem->colUsed |= ((Bitmask)1)<<(iCol>=BMS ? BMS-1 : iCol);
    }
    ExprSetProperty(p, EP_Resolved);
  }
  return p;
}

/*
** This routine is callback for sqlite3WalkExpr().
**
** Resolve symbolic names into TK_COLUMN operators for the current
** node in the expression tree.  Return 0 to continue the search down
** the tree or 2 to abort the tree walk.

  for(i=0; i<pTab->nCol; i++){
    if( sqlite3StrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;
  }
  return -1;
}

/*
** Create an expression node for an identifier with the name of zName


*/
Expr *sqlite3CreateIdExpr(Parse *pParse, const char *zName){
  return sqlite3Expr(pParse->db, TK_ID, zName);
}


/*

** 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(
  Parse *pParse,           /* Parsing context */
  const char *zCol,        /* Name of the column */
  const Table *pTab1,      /* First table */
  const char *zAlias1,     /* Alias for first table.  May be NULL */
  const Table *pTab2,      /* Second table */
  const char *zAlias2,     /* Alias for second table.  May be NULL */
  int iRightJoinTable,     /* VDBE cursor for the right table */
  Expr **ppExpr,           /* Add the equality term to this expression */
  int isOuterJoin          /* True if dealing with an OUTER join */
){

  Expr *pE1a, *pE1b, *pE1c;
  Expr *pE2a, *pE2b, *pE2c;
  Expr *pE;


  pE1a = sqlite3CreateIdExpr(pParse, zCol);
  pE2a = sqlite3CreateIdExpr(pParse, zCol);
  if( zAlias1==0 ){
    zAlias1 = pTab1->zName;
  }
  pE1b = sqlite3CreateIdExpr(pParse, zAlias1);
  if( zAlias2==0 ){
    zAlias2 = pTab2->zName;


  }
  pE2b = sqlite3CreateIdExpr(pParse, zAlias2);
  pE1c = sqlite3PExpr(pParse, TK_DOT, pE1b, pE1a, 0);
  pE2c = sqlite3PExpr(pParse, TK_DOT, pE2b, pE2a, 0);
  pE = sqlite3PExpr(pParse, TK_EQ, pE1c, pE2c, 0);
  if( pE && isOuterJoin ){
    ExprSetProperty(pE, EP_FromJoin);
    assert( !ExprHasAnyProperty(pE, EP_TokenOnly|EP_Reduced) );
    ExprSetIrreducible(pE);
    pE->iRightJoinTable = (i16)iRightJoinTable;
  }
  *ppExpr = sqlite3ExprAnd(pParse->db,*ppExpr, pE);
}

/*
** Set the EP_FromJoin property on all terms of the given expression.
** And set the Expr.iRightJoinTable to iTable for every term in the
** expression.
**
................................................................................
      if( pRight->pOn || pRight->pUsing ){
        sqlite3ErrorMsg(pParse, "a NATURAL join may not have "
           "an ON or USING clause", 0);
        return 1;
      }
      for(j=0; j<pLeftTab->nCol; j++){
        char *zName = pLeftTab->aCol[j].zName;
        if( columnIndex(pRightTab, zName)>=0 ){

          addWhereTerm(pParse, zName, pLeftTab, pLeft->zAlias, 
                              pRightTab, pRight->zAlias,
                              pRight->iCursor, &p->pWhere, isOuter);
          
        }
      }
    }

    /* Disallow both ON and USING clauses in the same join
    */
    if( pRight->pOn && pRight->pUsing ){
................................................................................
    ** Report an error if any column mentioned in the USING clause is
    ** not contained in both tables to be joined.
    */
    if( pRight->pUsing ){
      IdList *pList = pRight->pUsing;
      for(j=0; j<pList->nId; j++){
        char *zName = pList->a[j].zName;
        if( columnIndex(pLeftTab, zName)<0 || columnIndex(pRightTab, zName)<0 ){


          sqlite3ErrorMsg(pParse, "cannot join using column %s - column "
            "not present in both tables", zName);
          return 1;
        }
        addWhereTerm(pParse, zName, pLeftTab, pLeft->zAlias, 
                            pRightTab, pRight->zAlias,
                            pRight->iCursor, &p->pWhere, isOuter);
      }
    }
  }
  return 0;
}

/*

  for(i=0; i<pTab->nCol; i++){
    if( sqlite3StrICmp(pTab->aCol[i].zName, zCol)==0 ) return i;
  }
  return -1;
}

/*
** This function is used to add terms implied by JOIN syntax to the
** WHERE clause expression of a SELECT statement. The new term, which
** is ANDed with the existing WHERE clause, is of the form:
**




**    (tab1.col1 = tab2.col2)
**
** where tab1 is the iSrc'th table in SrcList pSrc and tab2 is the 
** (iSrc+1)'th. Column col1 is column iColLeft of tab1, and col2 is
** column iColRight of tab2.
*/
static void addWhereTerm(
  Parse *pParse,                  /* Parsing context */
  SrcList *pSrc,                  /* List of tables in FROM clause */
  int iSrc,                       /* Index of first table to join in pSrc */
  int iColLeft,                   /* Index of column in first table */
  int iColRight,                  /* Index of column in second table */
  int isOuterJoin,                /* True if this is an OUTER join */
  Expr **ppWhere                  /* IN/OUT: The WHERE clause to add to */


){
  sqlite3 *db = pParse->db;
  Expr *pE1;
  Expr *pE2;
  Expr *pEq;

  assert( pSrc->nSrc>(iSrc+1) );
  assert( pSrc->a[iSrc].pTab );
  assert( pSrc->a[iSrc+1].pTab );






  pE1 = sqlite3CreateColumnExpr(db, pSrc, iSrc, iColLeft);
  pE2 = sqlite3CreateColumnExpr(db, pSrc, iSrc+1, iColRight);




  pEq = sqlite3PExpr(pParse, TK_EQ, pE1, pE2, 0);
  if( pEq && isOuterJoin ){
    ExprSetProperty(pEq, EP_FromJoin);
    assert( !ExprHasAnyProperty(pEq, EP_TokenOnly|EP_Reduced) );
    ExprSetIrreducible(pEq);
    pEq->iRightJoinTable = (i16)pE2->iTable;
  }
  *ppWhere = sqlite3ExprAnd(db, *ppWhere, pEq);
}

/*
** Set the EP_FromJoin property on all terms of the given expression.
** And set the Expr.iRightJoinTable to iTable for every term in the
** expression.
**
................................................................................
      if( pRight->pOn || pRight->pUsing ){
        sqlite3ErrorMsg(pParse, "a NATURAL join may not have "
           "an ON or USING clause", 0);
        return 1;
      }
      for(j=0; j<pLeftTab->nCol; j++){
        char *zName = pLeftTab->aCol[j].zName;
        int iRightCol = columnIndex(pRightTab, zName);
        if( iRightCol>=0 ){
          addWhereTerm(pParse, pSrc, i, j, iRightCol, isOuter, &p->pWhere);



        }
      }
    }

    /* Disallow both ON and USING clauses in the same join
    */
    if( pRight->pOn && pRight->pUsing ){
................................................................................
    ** Report an error if any column mentioned in the USING clause is
    ** not contained in both tables to be joined.
    */
    if( pRight->pUsing ){
      IdList *pList = pRight->pUsing;
      for(j=0; j<pList->nId; j++){
        char *zName = pList->a[j].zName;
        int iLeftCol = columnIndex(pLeftTab, zName);
        int iRightCol = columnIndex(pRightTab, zName);
        if( iLeftCol<0 || iRightCol<0 ){
          sqlite3ErrorMsg(pParse, "cannot join using column %s - column "
            "not present in both tables", zName);
          return 1;
        }
        addWhereTerm(pParse, pSrc, i, iLeftCol, iRightCol, isOuter, &p->pWhere);


      }
    }
  }
  return 0;
}

/*

void sqlite3Vacuum(Parse*);
int sqlite3RunVacuum(char**, sqlite3*);
char *sqlite3NameFromToken(sqlite3*, Token*);
int sqlite3ExprCompare(Expr*, Expr*);
void sqlite3ExprAnalyzeAggregates(NameContext*, Expr*);
void sqlite3ExprAnalyzeAggList(NameContext*,ExprList*);
Vdbe *sqlite3GetVdbe(Parse*);
Expr *sqlite3CreateIdExpr(Parse *, const char*);
void sqlite3PrngSaveState(void);
void sqlite3PrngRestoreState(void);
void sqlite3PrngResetState(void);
void sqlite3RollbackAll(sqlite3*);
void sqlite3CodeVerifySchema(Parse*, int);
void sqlite3BeginTransaction(Parse*, int);
void sqlite3CommitTransaction(Parse*);
................................................................................
int sqlite3OpenTempDatabase(Parse *);

void sqlite3StrAccumInit(StrAccum*, char*, int, int);
void sqlite3StrAccumAppend(StrAccum*,const char*,int);
char *sqlite3StrAccumFinish(StrAccum*);
void sqlite3StrAccumReset(StrAccum*);
void sqlite3SelectDestInit(SelectDest*,int,int);


void sqlite3BackupRestart(sqlite3_backup *);
void sqlite3BackupUpdate(sqlite3_backup *, Pgno, const u8 *);

/*
** The interface to the LEMON-generated parser
*/

void sqlite3Vacuum(Parse*);
int sqlite3RunVacuum(char**, sqlite3*);
char *sqlite3NameFromToken(sqlite3*, Token*);
int sqlite3ExprCompare(Expr*, Expr*);
void sqlite3ExprAnalyzeAggregates(NameContext*, Expr*);
void sqlite3ExprAnalyzeAggList(NameContext*,ExprList*);
Vdbe *sqlite3GetVdbe(Parse*);

void sqlite3PrngSaveState(void);
void sqlite3PrngRestoreState(void);
void sqlite3PrngResetState(void);
void sqlite3RollbackAll(sqlite3*);
void sqlite3CodeVerifySchema(Parse*, int);
void sqlite3BeginTransaction(Parse*, int);
void sqlite3CommitTransaction(Parse*);
................................................................................
int sqlite3OpenTempDatabase(Parse *);

void sqlite3StrAccumInit(StrAccum*, char*, int, int);
void sqlite3StrAccumAppend(StrAccum*,const char*,int);
char *sqlite3StrAccumFinish(StrAccum*);
void sqlite3StrAccumReset(StrAccum*);
void sqlite3SelectDestInit(SelectDest*,int,int);
Expr *sqlite3CreateColumnExpr(sqlite3 *, SrcList *, int, int);

void sqlite3BackupRestart(sqlite3_backup *);
void sqlite3BackupUpdate(sqlite3_backup *, Pgno, const u8 *);

/*
** The interface to the LEMON-generated parser
*/

  sqlite3 *db = pParse->db; /* Database connection */
  const char *pVTab = (const char*)sqlite3GetVTable(db, pTab);
  SelectDest dest;

  /* Construct the SELECT statement that will find the new values for
  ** all updated rows. 
  */
  pEList = sqlite3ExprListAppend(pParse, 0, 
                                 sqlite3CreateIdExpr(pParse, "_rowid_"));
  if( pRowid ){
    pEList = sqlite3ExprListAppend(pParse, pEList,
                                   sqlite3ExprDup(db, pRowid, 0));
  }
  assert( pTab->iPKey<0 );
  for(i=0; i<pTab->nCol; i++){
    if( aXRef[i]>=0 ){
      pExpr = sqlite3ExprDup(db, pChanges->a[aXRef[i]].pExpr, 0);
    }else{
      pExpr = sqlite3CreateIdExpr(pParse, pTab->aCol[i].zName);
    }
    pEList = sqlite3ExprListAppend(pParse, pEList, pExpr);
  }
  pSelect = sqlite3SelectNew(pParse, pEList, pSrc, pWhere, 0, 0, 0, 0, 0, 0);
  
  /* Create the ephemeral table into which the update results will
  ** be stored.

  sqlite3 *db = pParse->db; /* Database connection */
  const char *pVTab = (const char*)sqlite3GetVTable(db, pTab);
  SelectDest dest;

  /* Construct the SELECT statement that will find the new values for
  ** all updated rows. 
  */
  pEList = sqlite3ExprListAppend(pParse, 0, sqlite3Expr(db, TK_ID, "_rowid_"));

  if( pRowid ){
    pEList = sqlite3ExprListAppend(pParse, pEList,
                                   sqlite3ExprDup(db, pRowid, 0));
  }
  assert( pTab->iPKey<0 );
  for(i=0; i<pTab->nCol; i++){
    if( aXRef[i]>=0 ){
      pExpr = sqlite3ExprDup(db, pChanges->a[aXRef[i]].pExpr, 0);
    }else{
      pExpr = sqlite3Expr(db, TK_ID, pTab->aCol[i].zName);
    }
    pEList = sqlite3ExprListAppend(pParse, pEList, pExpr);
  }
  pSelect = sqlite3SelectNew(pParse, pEList, pSrc, pWhere, 0, 0, 0, 0, 0, 0);
  
  /* Create the ephemeral table into which the update results will
  ** be stored.

** create an sqlite3_value structure containing this value, again with
** affinity aff applied to it, instead.
**
** If neither of the above apply, set *pp to NULL.
**
** If an error occurs, return an error code. Otherwise, SQLITE_OK.
*/

static int valueFromExpr(
  Parse *pParse, 
  Expr *pExpr, 
  u8 aff, 
  sqlite3_value **pp
){
  if( (pExpr->op==TK_VARIABLE)
................................................................................
    int iVar = pExpr->iColumn;
    sqlite3VdbeSetVarmask(pParse->pVdbe, iVar, 0);
    *pp = sqlite3VdbeGetValue(pParse->pReprepare, iVar, aff);
    return SQLITE_OK;
  }
  return sqlite3ValueFromExpr(pParse->db, pExpr, SQLITE_UTF8, aff, pp);
}


/*
** This function is used to estimate the number of rows that will be visited
** by scanning an index for a range of values. The range may have an upper
** bound, a lower bound, or both. The WHERE clause terms that set the upper
** and lower bounds are represented by pLower and pUpper respectively. For
** example, assuming that index p is on t1(a):

** create an sqlite3_value structure containing this value, again with
** affinity aff applied to it, instead.
**
** If neither of the above apply, set *pp to NULL.
**
** If an error occurs, return an error code. Otherwise, SQLITE_OK.
*/
#ifdef SQLITE_ENABLE_STAT2
static int valueFromExpr(
  Parse *pParse, 
  Expr *pExpr, 
  u8 aff, 
  sqlite3_value **pp
){
  if( (pExpr->op==TK_VARIABLE)
................................................................................
    int iVar = pExpr->iColumn;
    sqlite3VdbeSetVarmask(pParse->pVdbe, iVar, 0);
    *pp = sqlite3VdbeGetValue(pParse->pReprepare, iVar, aff);
    return SQLITE_OK;
  }
  return sqlite3ValueFromExpr(pParse->db, pExpr, SQLITE_UTF8, aff, pp);
}
#endif

/*
** This function is used to estimate the number of rows that will be visited
** by scanning an index for a range of values. The range may have an upper
** bound, a lower bound, or both. The WHERE clause terms that set the upper
** and lower bounds are represented by pLower and pUpper respectively. For
** example, assuming that index p is on t1(a):

  do_test join-10.3 {
    execsql {
      SELECT * FROM t23 LEFT JOIN (SELECT * FROM t24);
    }
  } {1 2 3 {} {} {}}

} ;# ifcapable subquery


































































finish_test

  do_test join-10.3 {
    execsql {
      SELECT * FROM t23 LEFT JOIN (SELECT * FROM t24);
    }
  } {1 2 3 {} {} {}}

} ;# ifcapable subquery

#-------------------------------------------------------------------------
# The following tests are to ensure that bug b73fb0bd64 is fixed.
#
do_test join-11.1 {
  drop_all_tables
  execsql {
    CREATE TABLE t1(a INTEGER PRIMARY KEY, b TEXT);
    CREATE TABLE t2(a INTEGER PRIMARY KEY, b TEXT);
    INSERT INTO t1 VALUES(1,'abc');
    INSERT INTO t1 VALUES(2,'def');
    INSERT INTO t2 VALUES(1,'abc');
    INSERT INTO t2 VALUES(2,'def');
    SELECT * FROM t1 NATURAL JOIN t2;
  }
} {1 abc 2 def}

do_test join-11.2 {
  execsql { SELECT a FROM t1 JOIN t1 USING (a)}
} {1 2}
do_test join-11.3 {
  execsql { SELECT a FROM t1 JOIN t1 AS t2 USING (a)}
} {1 2}
do_test join-11.3 {
  execsql { SELECT * FROM t1 NATURAL JOIN t1 AS t2}
} {1 abc 2 def}
do_test join-11.4 {
  execsql { SELECT * FROM t1 NATURAL JOIN t1 }
} {1 abc 2 def}

do_test join-11.5 {
  drop_all_tables
  execsql {
    CREATE TABLE t1(a COLLATE nocase, b);
    CREATE TABLE t2(a, b);
    INSERT INTO t1 VALUES('ONE', 1);
    INSERT INTO t1 VALUES('two', 2);
    INSERT INTO t2 VALUES('one', 1);
    INSERT INTO t2 VALUES('two', 2);
  }
} {}
do_test join-11.6 {
  execsql { SELECT * FROM t1 NATURAL JOIN t2 }
} {ONE 1 two 2}
do_test join-11.7 {
  execsql { SELECT * FROM t2 NATURAL JOIN t1 }
} {two 2}

do_test join-11.8 {
  drop_all_tables
  execsql {
    CREATE TABLE t1(a, b TEXT);
    CREATE TABLE t2(b INTEGER, a);
    INSERT INTO t1 VALUES('one', '1.0');
    INSERT INTO t1 VALUES('two', '2');
    INSERT INTO t2 VALUES(1, 'one');
    INSERT INTO t2 VALUES(2, 'two');
  }
} {}
do_test join-11.9 {
  execsql { SELECT * FROM t1 NATURAL JOIN t2 }
} {one 1.0 two 2}
do_test join-11.10 {
  execsql { SELECT * FROM t2 NATURAL JOIN t1 }
} {1 one 2 two}

finish_test