Add support for subqueries in the FROM clause of a SELECT. Still need

to add tests for this feature. (CVS 372)

FossilOrigin-Name: 89ffa9ff132858b62a91df1fb7fe49b2d58c01e7

4 files changed, 174 insertions, 47 deletions

diff --git a/src/parse.y b/src/parse.y
index 7959e0b6f..fc5180c73 100644
--- a/src/parse.y
+++ b/src/parse.y
@@ -14,7 +14,7 @@
 ** the parser.  Lemon will also generate a header file containing
 ** numeric codes for all of the tokens.
 **
-** @(#) $Id: parse.y,v 1.48 2002/02/03 17:37:36 drh Exp $
+** @(#) $Id: parse.y,v 1.49 2002/02/18 01:17:00 drh Exp $
 */
 %token_prefix TK_
 %token_type {Token}
@@ -257,6 +257,15 @@ seltablist(A) ::= stl_prefix(X) ids(Y) as ids(Z). {
   A = sqliteIdListAppend(X,&Y);
   sqliteIdListAddAlias(A,&Z);
 }
+seltablist(A) ::= stl_prefix(X) LP select(S) RP. {
+  A = sqliteIdListAppend(X,0);
+  A->a[A->nId-1].pSelect = S;
+}
+seltablist(A) ::= stl_prefix(X) LP select(S) RP as ids(Z). {
+  A = sqliteIdListAppend(X,0);
+  A->a[A->nId-1].pSelect = S;
+  sqliteIdListAddAlias(A,&Z);
+}
 
 %type orderby_opt {ExprList*}
 %destructor orderby_opt {sqliteExprListDelete($$);}
diff --git a/src/select.c b/src/select.c
index 611d70ea0..29f149751 100644
--- a/src/select.c
+++ b/src/select.c
@@ -12,7 +12,7 @@
 ** This file contains C code routines that are called by the parser
 ** to handle SELECT statements in SQLite.
 **
-** $Id: select.c,v 1.59 2002/02/17 00:30:36 drh Exp $
+** $Id: select.c,v 1.60 2002/02/18 01:17:00 drh Exp $
 */
 #include "sqliteInt.h"
 
@@ -273,7 +273,7 @@ void generateColumnNames(Parse *pParse, IdList *pTabList, ExprList *pEList){
         sqliteFree(zName);
       }else{
         sqliteVdbeAddOp(v, OP_ColumnName, i, 0);
-        sqliteVdbeChangeP3(v, -1, zCol, P3_STATIC);
+        sqliteVdbeChangeP3(v, -1, zCol, 0);
       }
     }else if( p->span.z && p->span.z[0] ){
       int addr = sqliteVdbeAddOp(v,OP_ColumnName, i, 0);
@@ -304,10 +304,47 @@ static const char *selectOpName(int id){
 }
 
 /*
+** Given a SELECT statement, generate a Table structure that describes
+** the result set of that SELECT.
+*/
+Table *sqliteResultSetOfSelect(Parse *pParse, char *zTabName, Select *pSelect){
+  Table *pTab;
+  int i;
+  ExprList *pEList;
+  static int fillInColumnList(Parse*, Select*);
+
+  if( fillInColumnList(pParse, pSelect) ){
+    return 0;
+  }
+  pTab = sqliteMalloc( sizeof(Table) );
+  if( pTab==0 ){
+    return 0;
+  }
+  pTab->zName = zTabName ? sqliteStrDup(zTabName) : 0;
+  pEList = pSelect->pEList;
+  pTab->nCol = pEList->nExpr;
+  pTab->aCol = sqliteMalloc( sizeof(pTab->aCol[0])*pTab->nCol );
+  for(i=0; i<pTab->nCol; i++){
+    Expr *p;
+    if( pEList->a[i].zName ){
+      pTab->aCol[i].zName = sqliteStrDup(pEList->a[i].zName);
+    }else if( (p=pEList->a[i].pExpr)->span.z && p->span.z[0] ){
+      sqliteSetNString(&pTab->aCol[i].zName, p->span.z, p->span.n, 0);
+    }else{
+      char zBuf[30];
+      sprintf(zBuf, "column%d", i+1);
+      pTab->aCol[i].zName = sqliteStrDup(zBuf);
+    }
+  }
+  pTab->iPKey = -1;
+  return pTab;
+}
+
+/*
 ** For the given SELECT statement, do two things.
 **
 **    (1)  Fill in the pTabList->a[].pTab fields in the IdList that 
-**         defines the set of tables that should be scanned.
+**         defines the set of tables that should be scanned. 
 **
 **    (2)  If the columns to be extracted variable (pEList) is NULL
 **         (meaning that a "*" was used in the SQL statement) then
@@ -334,22 +371,25 @@ static int fillInColumnList(Parse *pParse, Select *p){
       return 0;
     }
     if( pTabList->a[i].zName==0 ){
-      /* No table name is given.  Instead, there is a (SELECT ...) statement
-      ** the results of which should be used in place of the table.  The
-      ** way this is implemented is that the (SELECT ...) writes its results
-      ** into a temporary table which is then scanned like any other table.
-      */
-      sqliteSetString(&pParse->zErrMsg, 
-          "(SELECT...) in a FROM clause is not yet implemented.", 0);
-      pParse->nErr++;
-      return 1;
-    }
-    pTabList->a[i].pTab = sqliteFindTable(pParse->db, pTabList->a[i].zName);
-    if( pTabList->a[i].pTab==0 ){
-      sqliteSetString(&pParse->zErrMsg, "no such table: ", 
-         pTabList->a[i].zName, 0);
-      pParse->nErr++;
-      return 1;
+      /* A sub-query in the FROM clause of a SELECT */
+      Table *pTab;
+      assert( pTabList->a[i].pSelect!=0 );
+      pTabList->a[i].pTab = pTab = 
+        sqliteResultSetOfSelect(pParse, pTabList->a[i].zAlias,
+                                        pTabList->a[i].pSelect);
+      if( pTab==0 ){
+        return 1;
+      }
+      pTab->isTransient = 1;
+    }else{
+      /* An ordinary table name in the FROM clause */
+      pTabList->a[i].pTab = sqliteFindTable(pParse->db, pTabList->a[i].zName);
+      if( pTabList->a[i].pTab==0 ){
+        sqliteSetString(&pParse->zErrMsg, "no such table: ", 
+           pTabList->a[i].zName, 0);
+        pParse->nErr++;
+        return 1;
+      }
     }
   }
 
@@ -375,23 +415,27 @@ static int fillInColumnList(Parse *pParse, Select *p){
         for(i=0; i<pTabList->nId; i++){
           Table *pTab = pTabList->a[i].pTab;
           for(j=0; j<pTab->nCol; j++){
-            Expr *pExpr = sqliteExpr(TK_DOT, 0, 0, 0);
-            if( pExpr==0 ) break;
-            pExpr->pLeft = sqliteExpr(TK_ID, 0, 0, 0);
-            if( pExpr->pLeft==0 ){ sqliteExprDelete(pExpr); break; }
-            if( pTabList->a[i].zAlias && pTabList->a[i].zAlias[0] ){
-              pExpr->pLeft->token.z = pTabList->a[i].zAlias;
-              pExpr->pLeft->token.n = strlen(pTabList->a[i].zAlias);
+            Expr *pExpr, *pLeft, *pRight;
+            pRight = sqliteExpr(TK_ID, 0, 0, 0);
+            if( pRight==0 ) break;
+            pRight->token.z = pTab->aCol[j].zName;
+            pRight->token.n = strlen(pTab->aCol[j].zName);
+            if( pTab->zName ){
+              pLeft = sqliteExpr(TK_ID, 0, 0, 0);
+              if( pLeft==0 ) break;
+              if( pTabList->a[i].zAlias && pTabList->a[i].zAlias[0] ){
+                pLeft->token.z = pTabList->a[i].zAlias;
+                pLeft->token.n = strlen(pTabList->a[i].zAlias);
+              }else{
+                pLeft->token.z = pTab->zName;
+                pLeft->token.n = strlen(pTab->zName);
+              }
+              pExpr = sqliteExpr(TK_DOT, pLeft, pRight, 0);
+              if( pExpr==0 ) break;
             }else{
-              pExpr->pLeft->token.z = pTab->zName;
-              pExpr->pLeft->token.n = strlen(pTab->zName);
+              pExpr = pRight;
+              pExpr->span = pExpr->token;
             }
-            pExpr->pRight = sqliteExpr(TK_ID, 0, 0, 0);
-            if( pExpr->pRight==0 ){ sqliteExprDelete(pExpr); break; }
-            pExpr->pRight->token.z = pTab->aCol[j].zName;
-            pExpr->pRight->token.n = strlen(pTab->aCol[j].zName);
-            pExpr->span.z = "";
-            pExpr->span.n = 0;
             pNew = sqliteExprListAppend(pNew, pExpr, 0);
           }
         }
@@ -897,6 +941,20 @@ int sqliteSelect(
   v = sqliteGetVdbe(pParse);
   if( v==0 ) goto select_end;
 
+  /* Generate code for all sub-queries in the FROM clause
+  */
+  for(i=0; i<pTabList->nId; i++){
+    int oldNTab;
+    Table *pTab = pTabList->a[i].pTab;
+    if( !pTab->isTransient ) continue;
+    assert( pTabList->a[i].pSelect!=0 );
+    oldNTab = pParse->nTab;
+    pParse->nTab += i+1;
+    sqliteVdbeAddOp(v, OP_OpenTemp, oldNTab+i, 0);
+    sqliteSelect(pParse, pTabList->a[i].pSelect, SRT_Table, oldNTab+i);
+    pParse->nTab = oldNTab;
+  }
+
   /* Set the limiter
   */
   if( p->nLimit<=0 ){
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 70be7c430..03da707bb 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -11,7 +11,7 @@
 *************************************************************************
 ** Internal interface definitions for SQLite.
 **
-** @(#) $Id: sqliteInt.h,v 1.85 2002/02/17 00:30:36 drh Exp $
+** @(#) $Id: sqliteInt.h,v 1.86 2002/02/18 01:17:00 drh Exp $
 */
 #include "sqlite.h"
 #include "hash.h"
@@ -220,8 +220,33 @@ struct Column {
 };
 
 /*
-** Each SQL table is represented in memory by
-** an instance of the following structure.
+** Each SQL table is represented in memory by an instance of the
+** following structure.
+**
+** Expr.zName is the name of the table.  The case of the original
+** CREATE TABLE statement is stored, but case is not significant for
+** comparisons.
+**
+** Expr.nCol is the number of columns in this table.  Expr.aCol is a
+** pointer to an array of Column structures, one for each column.
+**
+** If the table has an INTEGER PRIMARY KEY, then Expr.iPKey is the index of
+** the column that is that key.   Otherwise Expr.iPKey is negative.  Note
+** that the datatype of the PRIMARY KEY must be INTEGER for this field to
+** be set.  An INTEGER PRIMARY KEY is used as the rowid for each row of
+** the table.  If a table has no INTEGER PRIMARY KEY, then a random rowid
+** is generated for each row of the table.  Expr.hasPrimKey is true if
+** the table has any PRIMARY KEY, INTEGER or otherwise.
+**
+** Expr.tnum is the page number for the root BTree page of the table in the
+** database file.  If Expr.isTemp is true, then this page occurs in the
+** auxiliary database file, not the main database file.  If Expr.isTransient
+** is true, then the table is stored in a file that is automatically deleted
+** when the VDBE cursor to the table is closed.  In this case Expr.tnum 
+** refers VDBE cursor number that holds the table open, not to the root
+** page number.  Transient tables are used to hold the results of a
+** sub-query that appears instead of a real table name in the FROM clause 
+** of a SELECT statement.
 */
 struct Table {
   char *zName;     /* Name of the table */
@@ -229,18 +254,18 @@ struct Table {
   Column *aCol;    /* Information about each column */
   int iPKey;       /* If not less then 0, use aCol[iPKey] as the primary key */
   Index *pIndex;   /* List of SQL indexes on this table. */
-  int tnum;        /* Page containing root for this table */
+  int tnum;        /* Root BTree node for this table (see note above) */
   u8 readOnly;     /* True if this table should not be written by the user */
   u8 isCommit;     /* True if creation of this table has been committed */
   u8 isTemp;       /* True if stored in db->pBeTemp instead of db->pBe */
+  u8 isTransient;  /* True if automatically deleted when VDBE finishes */
   u8 hasPrimKey;   /* True if there exists a primary key */
   u8 keyConf;      /* What to do in case of uniqueness conflict on iPKey */
 };
 
 /*
-** SQLite supports 4 or 5 different ways to resolve a contraint
-** error.  (Only 4 are implemented as of this writing.  The fifth method
-** "ABORT" is planned.)  ROLLBACK processing means that a constraint violation
+** SQLite supports 5 different ways to resolve a contraint
+** error.  ROLLBACK processing means that a constraint violation
 ** causes the operation in proces to fail and for the current transaction
 ** to be rolled back.  ABORT processing means the operation in process
 ** fails and any prior changes from that one operation are backed out,
@@ -307,7 +332,37 @@ struct Token {
 
 /*
 ** Each node of an expression in the parse tree is an instance
-** of this structure
+** of this structure.
+**
+** Expr.op is the opcode.  The integer parser token codes are reused
+** as opcodes here.  For example, the parser defines TK_GE to be an integer
+** code representing the ">=" operator.  This same integer code is reused
+** to represent the greater-than-or-equal-to operator in the expression
+** tree.
+**
+** Expr.pRight and Expr.pLeft are subexpressions.  Expr.pList is a list
+** of argument if the expression is a function.
+**
+** Expr.token is the operator token for this node.  Expr.span is the complete
+** subexpression represented by this node and all its decendents.  These
+** fields are used for error reporting and for reconstructing the text of
+** an expression to use as the column name in a SELECT statement.
+**
+** An expression of the form ID or ID.ID refers to a column in a table.
+** For such expressions, Expr.op is set to TK_COLUMN and Expr.iTable is
+** the integer cursor number of a VDBE cursor pointing to that table and
+** Expr.iColumn is the column number for the specific column.  If the
+** expression is used as a result in an aggregate SELECT, then the
+** value is also stored in the Expr.iAgg column in the aggregate so that
+** it can be accessed after all aggregates are computed.
+**
+** If the expression is a function, the Expr.iTable is an integer code
+** representing which function.
+**
+** The Expr.pSelect field points to a SELECT statement.  The SELECT might
+** be the right operand of an IN operator.  Or, if a scalar SELECT appears
+** in an expression the opcode is TK_SELECT and Expr.pSelect is the only
+** operand.
 */
 struct Expr {
   int op;                /* Operation performed by this node */
diff --git a/src/where.c b/src/where.c
index dd1120239..48cf4b302 100644
--- a/src/where.c
+++ b/src/where.c
@@ -13,7 +13,7 @@
 ** the WHERE clause of SQL statements.  Also found here are subroutines
 ** to generate VDBE code to evaluate expressions.
 **
-** $Id: where.c,v 1.34 2002/02/13 23:22:54 drh Exp $
+** $Id: where.c,v 1.35 2002/02/18 01:17:00 drh Exp $
 */
 #include "sqliteInt.h"
 
@@ -188,6 +188,7 @@ WhereInfo *sqliteWhereBegin(
   pWInfo->pTabList = pTabList;
   base = pWInfo->base = pParse->nTab;
   nCur = base + pTabList->nId;
+  pParse->nTab += nCur*2;
 
   /* Split the WHERE clause into as many as 32 separate subexpressions
   ** where each subexpression is separated by an AND operator.  Any additional
@@ -202,7 +203,7 @@ WhereInfo *sqliteWhereBegin(
   /* Analyze all of the subexpressions.
   */
   for(i=0; i<nExpr; i++){
-    exprAnalyze(pParse->nTab, &aExpr[i]);
+    exprAnalyze(base, &aExpr[i]);
   }
 
   /* Figure out a good nesting order for the tables.  aOrder[0] will
@@ -396,6 +397,7 @@ WhereInfo *sqliteWhereBegin(
     Table *pTab;
 
     pTab = pTabList->a[i].pTab;
+    if( pTab->isTransient ) continue;
     openOp = pTab->isTemp ? OP_OpenAux : OP_Open;
     sqliteVdbeAddOp(v, openOp, base+i, pTab->tnum);
     sqliteVdbeChangeP3(v, -1, pTab->zName, P3_STATIC);
@@ -771,8 +773,9 @@ void sqliteWhereEnd(WhereInfo *pWInfo){
   int i;
   int base = pWInfo->base;
   WhereLevel *pLevel;
+  IdList *pTabList = pWInfo->pTabList;
 
-  for(i=pWInfo->pTabList->nId-1; i>=0; i--){
+  for(i=pTabList->nId-1; i>=0; i--){
     pLevel = &pWInfo->a[i];
     sqliteVdbeResolveLabel(v, pLevel->cont);
     if( pLevel->op!=OP_Noop ){
@@ -781,13 +784,15 @@ void sqliteWhereEnd(WhereInfo *pWInfo){
     sqliteVdbeResolveLabel(v, pLevel->brk);
   }
   sqliteVdbeResolveLabel(v, pWInfo->iBreak);
-  for(i=0; i<pWInfo->pTabList->nId; i++){
+  for(i=0; i<pTabList->nId; i++){
+    if( pTabList->a[i].pTab->isTransient ) continue;
     pLevel = &pWInfo->a[i];
     sqliteVdbeAddOp(v, OP_Close, base+i, 0);
     if( pLevel->pIdx!=0 ){
       sqliteVdbeAddOp(v, OP_Close, pLevel->iCur, 0);
     }
   }
+  pWInfo->pParse->nTab = base;
   sqliteFree(pWInfo);
   return;
 }