Add initial infrastructure for cursors. In where.c, optimize out clauses

of the form "ORDER BY rowid" if a table scan is being performed.  Do a
reverse table scan if "ORDER BY rowid DESC" is present. (CVS 2141)

FossilOrigin-Name: fc8c1393c86017a816beb52725b68af3b973f979

17 files changed, 671 insertions, 93 deletions

diff --git a/main.mk b/main.mk
index be16417df..a15f5e800 100644
--- a/main.mk
+++ b/main.mk
@@ -54,7 +54,7 @@ TCCX = $(TCC) $(OPTS) $(THREADSAFE) $(USLEEP) -I. -I$(TOP)/src
 
 # Object files for the SQLite library.
 #
-LIBOBJ+= attach.o auth.o btree.o build.o date.o delete.o \
+LIBOBJ+= attach.o auth.o btree.o build.o cursor.o date.o delete.o \
          expr.o func.o hash.o insert.o \
          main.o opcodes.o os_mac.o os_unix.o os_win.o \
          pager.o parse.o pragma.o printf.o random.o \
@@ -71,6 +71,7 @@ SRC = \
   $(TOP)/src/btree.c \
   $(TOP)/src/btree.h \
   $(TOP)/src/build.c \
+  $(TOP)/src/cursor.c \
   $(TOP)/src/date.c \
   $(TOP)/src/delete.c \
   $(TOP)/src/expr.c \
@@ -226,6 +227,9 @@ config.h:
 	echo >>config.h
 	rm -f temp.c temp
 
+cursor.o:	$(TOP)/src/cursor.c $(HDR)
+	$(TCCX) -c $(TOP)/src/cursor.c
+
 date.o:	$(TOP)/src/date.c $(HDR)
 	$(TCCX) -c $(TOP)/src/date.c
 
diff --git a/manifest b/manifest
index 567a4c04b..6aae0d09e 100644
--- a/manifest
+++ b/manifest
@@ -1,5 +1,5 @@
-C Fix\sa\slong-standing\sbug\sin\sbtree.c\sin\sthe\ssqlite3BtreePrevious()\sroutine.\nThe\sproblem\shas\sgone\sunnoticed\sbefore\snow\sbecause\sit\sonly\soccurs\swhen\syou\nuse\sthe\sOP_Prev\sopcode\son\sa\sB+Tree.\s(CVS\s2140)
-D 2004-11-22T19:07:10
+C Add\sinitial\sinfrastructure\sfor\scursors.\s\sIn\swhere.c,\soptimize\sout\sclauses\nof\sthe\sform\s"ORDER\sBY\srowid"\sif\sa\stable\sscan\sis\sbeing\sperformed.\s\sDo\sa\nreverse\stable\sscan\sif\s"ORDER\sBY\srowid\sDESC"\sis\spresent.\s(CVS\s2141)
+D 2004-11-22T19:12:20
 F Makefile.in 8291610f5839939a5fbff4dbbf85adb0fe1ac37f
 F Makefile.linux-gcc a9e5a0d309fa7c38e7c14d3ecf7690879d3a5457
 F README a01693e454a00cc117967e3f9fdab2d4d52e9bc1
@@ -16,7 +16,7 @@ F doc/lemon.html f0f682f50210928c07e562621c3b7e8ab912a538
 F doc/report1.txt a031aaf37b185e4fa540223cb516d3bccec7eeac
 F install-sh 9d4de14ab9fb0facae2f48780b874848cbf2f895
 F ltmain.sh f6b283068efa69f06eb8aa1fe4bddfdbdeb35826
-F main.mk 31af0ba9d4d0f03a5db4051a6f2ca527dfae3daf
+F main.mk cdbb576b8a789e8d0428d39c07600097628198a0
 F mkdll.sh 468d4f41d3ea98221371df4825cfbffbaac4d7e4
 F mkopcodec.awk 14a794f7b206976afc416b30fe8e0fc97f3434e9
 F mkopcodeh.awk 4090944e4de0a2ccb99aa0083290f73bce4db406
@@ -32,15 +32,16 @@ F src/auth.c 3b81f2a42f48a62c2c9c9b0eda31a157c681edea
 F src/btree.c 05fe410ebbcbac72b66bc3aeeadf7e5588b0699e
 F src/btree.h 861e40b759a195ba63819740e484390012cf81ab
 F src/build.c b62389de594d0b413068d6e067794249a1f1d209
+F src/cursor.c dddc11922f583645318c9446d0d1920d0bc940cd
 F src/date.c 65536e7ea04fdde6e0551264fca15966966e171f
 F src/delete.c cf185995e20a61c0fecc2a9a9a3b19bd18bd05b3
-F src/expr.c 511c27a8858ca12614f495c9c90f5d12db11e6c2
+F src/expr.c b985b42a3bce753040ab3415669d8a39b0538e5f
 F src/func.c b668e5ad043176049454c95a6a780367a0e8f6bb
 F src/hash.c a97721a55440b7bea31ffe471bb2f6b4123cddd5
 F src/hash.h 1b0c445e1c89ff2aaad9b4605ba61375af001e84
 F src/insert.c 9524a6c3e86cbdbae3313f6a083bb9a3e7a2462b
 F src/legacy.c d58ea507bce885298a2c8c3cbb0f4bff5d47830b
-F src/main.c 9abc4f08cda08361ea6cb921f622a3f7b44389a7
+F src/main.c fc383dc9cf03847b96e5ed9942696467725cfdfd
 F src/md5.c 7ae1c39044b95de2f62e066f47bb1deb880a1070
 F src/os.h 38258df2db895499b6e2957dbf17f25e0df71667
 F src/os_common.h 0e7f428ba0a6c40a61bc56c4e96f493231301b73
@@ -54,17 +55,17 @@ F src/os_win.c 9482dfc92f289b68205bb2c9315757c7e3946bfb
 F src/os_win.h 41a946bea10f61c158ce8645e7646b29d44f122b
 F src/pager.c ee88fcecb081e3635c281bc09d604e934429e2f5
 F src/pager.h 9eba8c53dd91eae7f3f90743b2ee242da02a9862
-F src/parse.y 0a4bdfd7b65d9761b41a862d09a17c90c1f526f7
-F src/pragma.c 0b43b8cac4870bfa041bf2ca29d7ce47b76362d6
+F src/parse.y ceba179b9703657180963568f54b0e75f33e36e1
+F src/pragma.c d6406e12c9eac353b3a026b50d41e4fd561afcc2
 F src/printf.c 3d20b21cfecadacecac3fb7274e746cb81d3d357
 F src/random.c eff68e3f257e05e81eae6c4d50a51eb88beb4ff3
-F src/select.c 7b17db766e669fc85837af50cc110d0988d31ee9
+F src/select.c b00478f33d6a9beb56f85b5d6b2e7325793c0bdf
 F src/shell.c e8f4f486cbf6e60d81173146ac8a6522c930fa51
 F src/sqlite.h.in 6d0e82c24ef3f84a10b468119f3943a5dfc806c7
-F src/sqliteInt.h d16d54eeefb24b4b1d0e9fa80593bf110a293aab
+F src/sqliteInt.h f783c2793ca02b1e8bee587f526932a43da14173
 F src/table.c 25b3ff2b39b7d87e8d4a5da0713d68dfc06cbee9
 F src/tclsqlite.c 7f1a1a678140e6901c8954590ca2aabe50b48f71
-F src/test1.c 21b1cc9358678da579d7aad8f16a40735a837078
+F src/test1.c b7d94c54e58f95452387a5cabdf98b2be8059f29
 F src/test2.c b11fa244fff02190707dd0879987c37c75e61fc8
 F src/test3.c 6f1ec93e13632a004b527049535079eda84c459d
 F src/test4.c 7c6b9fc33dd1f3f93c7f1ee6e5e6d016afa6c1df
@@ -81,9 +82,9 @@ F src/vdbeInt.h 6017100adff362b8dfa37a69e3f1431f084bfa5b
 F src/vdbeapi.c 74be7f96c0a1ac275661f8b32276ac521d9ce37c
 F src/vdbeaux.c dc06bbb8511d07f8d45ed2ea760f35f0736a690c
 F src/vdbemem.c 5876c8abf4374fef671f4fd8dc333ef3fc95a2f0
-F src/where.c f8a9e0bca6cb0a6fc4c189ed9fa771e75ad68bc8
+F src/where.c be486196af29c4be8cc49275bc483a8af4cb8dcd
 F test/all.test 929bfa932b55e75c96fe2203f7650ba451c1862c
-F test/alter.test 2f0355d92bc360f897c0893f24cf4024e2719e56
+F test/alter.test 95c57a4f461fa81293e0dccef7f83889aadb169a
 F test/attach.test a71117bab079c8a3a955e2d0270a76f9cb445935
 F test/attach2.test 399128a7b3b209a339a8dbf53ca2ed42eb982d1a
 F test/attach3.test c05c70b933afbde0901dab9da3e66ee842c09f38
@@ -107,13 +108,14 @@ F test/capi3b.test 5b6a66f9f295f79f443b5d3f33187fa5ef6cf336
 F test/collate1.test f79736d2ebf5492167ee4d1f4ab4c09dda776b03
 F test/collate2.test 12fd658d8f5106a8a5c8a77d66919d8c89394036
 F test/collate3.test 5fe8077bd82c53112974f56f51f06cbd06d71374
-F test/collate4.test c29c8d4b66cf45b36fa112c28493cdb451a8409b
+F test/collate4.test a7bb41adf16e211f52b925613110af5c70ae7792
 F test/collate5.test 7999fb3122386bae38acd8ccd61e0b7c5a30e289
 F test/collate6.test 6c9470d1606ee3e564675b229653e320c49ec638
 F test/conflict.test c5b849b01cfbe0a4f63a90cba6f68e2fe3a75f87
 F test/corrupt.test 0080ddcece23e8ba47c44608c4fb73fd4d1d8ce2
 F test/crash.test 48b481769dd0ead25b0dfc0150853bfa39a3b65c
 F test/crashtest1.c 09c1c7d728ccf4feb9e481671e29dda5669bbcc2
+F test/cursor.test 376eabf81c727e15debc72d255d2c2624b9076c7
 F test/date.test dda578ec1857837156bd8b32f8e09d81d7d7881c
 F test/delete.test fc29491f6a7ac899ce29f4549a104809e245d9a6
 F test/delete2.test e382b6a97787197eb8b93dd4ccd37797c3725ea3
@@ -198,14 +200,14 @@ F test/utf16.test 459c2f5ab80c60092c603630a348c32d6e59c558
 F test/vacuum.test f18eccdee5b538d46298c64d6a060cfbf97bbc23
 F test/varint.test ab7b110089a08b9926ed7390e7e97bdefeb74102
 F test/view.test 3f96df86f1c61ee850b945204683773bbbb8643e
-F test/where.test 8a016d444252553a0c7c3a4c806d3f782f7337eb
+F test/where.test 6914a44678693e78d379eab389140a33334633a2
 F tool/diffdb.c 7524b1b5df217c20cd0431f6789851a4e0cb191b
 F tool/lemon.c 250b30bcf3f1f422a2cad24b1597314777058a4b
 F tool/lempar.c 1e61d2b6cb9d8affa264a13336bc0c088498caa4
 F tool/memleak.awk b744b6109566206c746d826f6ecdba34662216bc
 F tool/memleak2.awk 9cc20c8e8f3c675efac71ea0721ee6874a1566e8
 F tool/memleak3.tcl 336eb50b0849dbf99b1d5462d9c37291b01b2b43
-F tool/mkkeywordhash.c c2254c191456316ce5d3f72a6b44fbf3c6492816
+F tool/mkkeywordhash.c e83ab9c16c5cf217f57cb49ad09a3a1dc5209485
 F tool/mkopts.tcl 66ac10d240cc6e86abd37dc908d50382f84ff46e x
 F tool/opcodeDoc.awk b3a2a3d5d3075b8bd90b7afe24283efdd586659c
 F tool/report1.txt 9eae07f26a8fc53889b45fc833a66a33daa22816
@@ -259,7 +261,7 @@ F www/tclsqlite.tcl 560ecd6a916b320e59f2917317398f3d59b7cc25
 F www/vdbe.tcl 095f106d93875c94b47367384ebc870517431618
 F www/version3.tcl 092a01f5ef430d2c4acc0ae558d74c4bb89638a0
 F www/whentouse.tcl fdacb0ba2d39831e8a6240d05a490026ad4c4e4c
-P 894c142d115b31506b6b8212e1b850ea28c4ca11
-R 78d02c023016240adef0039c2e3bd491
+P 3d2536c479c943b3a55047898068625f91c872ae
+R 72745c2cddac7210800e29c25c7bccd9
 U drh
-Z 4ee95f7b7946cb01ce979cf0cc317f8a
+Z a1c5d9d0383eefbb16dbdfab1a5f6edc
diff --git a/manifest.uuid b/manifest.uuid
index e9d5427a1..1b26bb4bd 100644
--- a/manifest.uuid
+++ b/manifest.uuid
@@ -1 +1 @@
-3d2536c479c943b3a55047898068625f91c872ae
\ No newline at end of file
+fc8c1393c86017a816beb52725b68af3b973f979
\ No newline at end of file
diff --git a/src/cursor.c b/src/cursor.c
new file mode 100644
index 000000000..061fcb699
--- /dev/null
+++ b/src/cursor.c
@@ -0,0 +1,169 @@
+/*
+** 2004 November 21
+**
+** 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 code used to implement the DECLARE...CURSOR syntax
+** of SQL and related processing.
+**
+** Do not confuse SQL cursors and B-tree cursors.  An SQL cursor (as
+** implemented by this file) is a user-visible cursor that is created
+** using the DECLARE...CURSOR command and deleted using CLOSE.  A
+** B-tree cursor is an abstraction of the b-tree layer.  See the btree.c
+** module for additional information.  There is also a VDBE-cursor that
+** is used by the VDBE module.  Even though all these objects are called
+** cursors, they are really very different things.  It is worth your while
+** to fully understand the difference.
+**
+** @(#) $Id: cursor.c,v 1.1 2004/11/22 19:12:20 drh Exp $
+*/
+#ifndef SQLITE_OMIT_CURSOR
+#include "sqliteInt.h"
+#include "vdbeInt.h"
+
+/*
+** Delete a cursor object.
+*/
+void sqlite3CursorDelete(SqlCursor *p){
+  if( p ){
+    int i;
+    sqlite3SelectDelete(p->pSelect);
+    for(i=0; i<p->nPtr; i++){
+      sqlite3VdbeMemRelease(&p->aPtr[i]);
+    }
+    sqliteFree(p->aPtr);
+    sqliteFree(p);
+  }
+}
+
+/*
+** Look up a cursor by name.  Return NULL if not found.
+*/
+static SqlCursor *findCursor(sqlite3 *db, Token *pName){
+  int i;
+  SqlCursor *p;
+  for(i=0; i<db->nSqlCursor; i++){
+    p = db->apSqlCursor[i];
+    if( p && sqlite3StrNICmp(p->zName, pName->z, pName->n)==0 ){
+      return p;
+    }
+  }
+  return 0;
+}  
+
+/*
+** The parser calls this routine in order to create a new cursor.
+** The arguments are the name of the new cursor and the SELECT statement
+** that the new cursor will access.
+*/
+void sqlite3CursorCreate(Parse *pParse, Token *pName, Select *pSelect){
+  SqlCursor *pNew;
+  sqlite3 *db = pParse->db;
+  int i;
+  
+
+  pNew = findCursor(db, pName);
+  if( pNew ){
+    sqlite3ErrorMsg(pParse, "another cursor named %T already exists", pName);
+    goto end_create_cursor;
+  }
+  if( pSelect==0 ){
+    /* This can only happen due to a prior malloc failure */
+    goto end_create_cursor;
+  }
+  for(i=0; i<db->nSqlCursor; i++){
+    if( db->apSqlCursor[i]==0 ) break;
+  }
+  if( i>=db->nSqlCursor ){
+    db->apSqlCursor = sqliteRealloc(db->apSqlCursor, (i+1)*sizeof(pNew));
+    db->nSqlCursor = i+1;
+  }
+  db->apSqlCursor[i] = pNew = sqliteMallocRaw( sizeof(*pNew) + pName->n + 1 );
+  if( pNew==0 ) goto end_create_cursor;
+  pNew->zName = (char*)&pNew[1];
+  memcpy(pNew->zName, pName->z, pName->n);
+  pNew->zName[pName->n] = 0;
+  pNew->pSelect = sqlite3SelectDup(pSelect);
+  pNew->nPtr = 0;
+  pNew->aPtr = 0;
+  pNew->idx = i;
+
+end_create_cursor:
+  sqlite3SelectDelete(pSelect);
+}
+
+/*
+** The parser calls this routine in response to a CLOSE command.  Delete
+** the cursor named in the argument.
+*/
+void sqlite3CursorClose(Parse *pParse, Token *pName){
+  SqlCursor *p;
+  sqlite3 *db = pParse->db;
+
+  p = findCursor(db, pName);
+  if( p==0 ){
+    sqlite3ErrorMsg(pParse, "no such cursor: %T", pName);
+    return;
+  }
+  assert( p->idx>=0 && p->idx<db->nSqlCursor );
+  assert( db->apSqlCursor[p->idx]==p );
+  db->apSqlCursor[p->idx] = 0;
+  sqlite3CursorDelete(p);
+}
+
+/*
+** The parser calls this routine when it sees a complete FETCH statement.
+** This routine generates code to implement the FETCH.
+**
+** Information about the direction of the FETCH has already been inserted
+** into the pParse structure by parser rules.  The arguments specify the
+** name of the cursor from which we are fetching and the optional INTO
+** clause.
+*/
+void sqlite3Fetch(Parse *pParse, Token *pName, IdList *pInto){
+  SqlCursor *p;
+  sqlite3 *db = pParse->db;
+  Select *pCopy;
+  Fetch sFetch;
+
+  p = findCursor(db, pName);
+  if( p==0 ){
+    sqlite3ErrorMsg(pParse, "no such cursor: %T", pName);
+    return;
+  }
+  sFetch.pCursor = p;
+  pCopy = sqlite3SelectDup(p->pSelect);
+  pCopy->pFetch = &sFetch;
+  switch( pParse->fetchDir ){
+    case TK_FIRST: {
+      break;
+    }
+    case TK_LAST: {
+      break;
+    }
+    case TK_NEXT: {
+      break;
+    }
+    case TK_PRIOR: {
+      break;
+    }
+    case TK_ABSOLUTE: {
+      break;
+    }
+    default: {
+      assert( pParse->fetchDir==TK_RELATIVE );
+      break;
+    }
+  }
+  sqlite3Select(pParse, pCopy, SRT_Callback, 0, 0, 0, 0, 0);
+end_fetch:
+  sqlite3IdListDelete(pInto);
+}
+
+#endif /* SQLITE_OMIT_CURSOR */
diff --git a/src/expr.c b/src/expr.c
index ce3337d51..03fd866bd 100644
--- a/src/expr.c
+++ b/src/expr.c
@@ -12,7 +12,7 @@
 ** This file contains routines used for analyzing expressions and
 ** for generating VDBE code that evaluates expressions in SQLite.
 **
-** $Id: expr.c,v 1.172 2004/11/20 20:44:14 drh Exp $
+** $Id: expr.c,v 1.173 2004/11/22 19:12:20 drh Exp $
 */
 #include "sqliteInt.h"
 #include <ctype.h>
@@ -503,10 +503,10 @@ Select *sqlite3SelectDup(Select *p){
   pNew->pPrior = sqlite3SelectDup(p->pPrior);
   pNew->nLimit = p->nLimit;
   pNew->nOffset = p->nOffset;
-  pNew->zSelect = 0;
   pNew->iLimit = -1;
   pNew->iOffset = -1;
   pNew->ppOpenTemp = 0;
+  pNew->pFetch = 0;
   return pNew;
 }
 
diff --git a/src/main.c b/src/main.c
index 08470f722..9a9b96e08 100644
--- a/src/main.c
+++ b/src/main.c
@@ -14,7 +14,7 @@
 ** other files are for internal use by SQLite and should not be
 ** accessed by users of the library.
 **
-** $Id: main.c,v 1.267 2004/11/22 05:26:27 danielk1977 Exp $
+** $Id: main.c,v 1.268 2004/11/22 19:12:20 drh Exp $
 */
 #include "sqliteInt.h"
 #include "os.h"
@@ -500,6 +500,13 @@ int sqlite3_close(sqlite3 *db){
     sqlite3ValueFree(db->pErr);
   }
 
+#ifndef SQLITE_OMIT_CURSOR
+  for(j=0; j<db->nSqlCursor; j++){
+    sqlite3CursorDelete(db->apSqlCursor[j]);
+  }
+  sqliteFree(db->apSqlCursor);
+#endif
+
   db->magic = SQLITE_MAGIC_ERROR;
   sqliteFree(db);
   return SQLITE_OK;
diff --git a/src/parse.y b/src/parse.y
index e0d270197..7579361a8 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.157 2004/11/17 16:41:30 danielk1977 Exp $
+** @(#) $Id: parse.y,v 1.158 2004/11/22 19:12:21 drh Exp $
 */
 %token_prefix TK_
 %token_type {Token}
@@ -598,6 +598,9 @@ term(A) ::= INTEGER(X).      {A = sqlite3Expr(@X, 0, 0, &X);}
 term(A) ::= FLOAT(X).        {A = sqlite3Expr(@X, 0, 0, &X);}
 term(A) ::= STRING(X).       {A = sqlite3Expr(@X, 0, 0, &X);}
 expr(A) ::= BLOB(X).         {A = sqlite3Expr(@X, 0, 0, &X);}
+%ifndef SQLITE_OMIT_CURSOR
+expr(A) ::= CURRENT OF id.
+%endif 
 expr(A) ::= REGISTER(X).     {A = sqlite3RegisterExpr(pParse, &X);}
 expr(A) ::= VARIABLE(X).     {
   Token *pToken = &X;
@@ -955,3 +958,32 @@ cmd ::= ALTER TABLE fullname(X) RENAME TO nm(Z). {
   sqlite3AlterRenameTable(pParse,X,&Z);
 }
 %endif
+
+////////////////////////////// CURSORS //////////////////////////////////////
+%ifndef SQLITE_OMIT_CURSOR
+cmd ::= DECLARE nm(X) CURSOR FOR select(Y).  {sqlite3CursorCreate(pParse,&X,Y);}
+cmd ::= CLOSE nm(X).                         {sqlite3CursorClose(pParse,&X);}
+
+cmd ::= FETCH direction FROM nm(N) into_opt(D).
+                                      {sqlite3Fetch(pParse,&N,D);}
+
+%type into_opt {IdList*}
+%destructor into_opt {sqlite3IdListDelete($$);}
+into_opt(A) ::= .                     {A = 0;}
+into_opt(A) ::= INTO inscollist(X).   {A = X;}
+direction ::= NEXT(X) count_opt(Y).   {pParse->fetchDir=@X; pParse->dirArg1=Y;}
+direction ::= PRIOR(X) count_opt(Y).  {pParse->fetchDir=@X; pParse->dirArg1=Y;}
+direction ::= FIRST(X) count_opt(Y).  {pParse->fetchDir=@X; pParse->dirArg1=Y;}
+direction ::= LAST(X) count_opt(Y).   {pParse->fetchDir=@X; pParse->dirArg1=Y;}
+direction ::= ABSOLUTE(X) signed(Z) comma_count_opt(Y).
+                   {pParse->fetchDir=@X; pParse->dirArg1=Y; pParse->dirArg2=Z;}
+direction ::= RELATIVE(X) signed(Z) comma_count_opt(Y).
+                   {pParse->fetchDir=@X; pParse->dirArg1=Y; pParse->dirArg2=Z;}
+
+%type count_opt {int}
+count_opt(A) ::= .          {A = 1;}
+count_opt(A) ::= signed(X). {A = X;}
+%type comma_count_opt {int}
+comma_count_opt(A) ::= .                 {A = 1;}
+comma_count_opt(A) ::= COMMA signed(X).  {A = X;}
+%endif // SQLITE_OMIT_CURSOR
diff --git a/src/pragma.c b/src/pragma.c
index 10b282cdf..3d094d385 100644
--- a/src/pragma.c
+++ b/src/pragma.c
@@ -11,7 +11,7 @@
 *************************************************************************
 ** This file contains code used to implement the PRAGMA command.
 **
-** $Id: pragma.c,v 1.78 2004/11/13 15:59:15 drh Exp $
+** $Id: pragma.c,v 1.79 2004/11/22 19:12:21 drh Exp $
 */
 #include "sqliteInt.h"
 #include <ctype.h>
@@ -478,6 +478,24 @@ void sqlite3Pragma(
       sqlite3VdbeAddOp(v, OP_Callback, 3, 0);
     }
   }else
+
+#ifndef SQLITE_OMIT_CURSOR
+  if( sqlite3StrICmp(zLeft, "cursor_list")==0 ){
+    int i;
+    if( sqlite3ReadSchema(pParse) ) goto pragma_out;
+    sqlite3VdbeSetNumCols(v, 2);
+    sqlite3VdbeSetColName(v, 0, "seq", P3_STATIC);
+    sqlite3VdbeSetColName(v, 1, "name", P3_STATIC);
+    for(i=0; i<db->nSqlCursor; i++){
+      SqlCursor *p = db->apSqlCursor[i];
+      if( p==0 ) continue;
+      assert( p->zName!=0 );
+      sqlite3VdbeAddOp(v, OP_Integer, i, 0);
+      sqlite3VdbeOp3(v, OP_String8, 0, 0, p->zName, 0);
+      sqlite3VdbeAddOp(v, OP_Callback, 2, 0);
+    }
+  }else
+#endif /* SQLITE_OMIT_CURSOR */
 #endif /* SQLITE_OMIT_SCHEMA_PRAGMAS */
 
 #ifndef SQLITE_OMIT_FOREIGN_KEY
diff --git a/src/select.c b/src/select.c
index 412ee8eb6..d17c26960 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.215 2004/11/22 10:02:11 danielk1977 Exp $
+** $Id: select.c,v 1.216 2004/11/22 19:12:21 drh Exp $
 */
 #include "sqliteInt.h"
 
@@ -298,7 +298,6 @@ void sqlite3SelectDelete(Select *p){
   sqlite3ExprDelete(p->pHaving);
   sqlite3ExprListDelete(p->pOrderBy);
   sqlite3SelectDelete(p->pPrior);
-  sqliteFree(p->zSelect);
   sqliteFree(p);
 }
 
@@ -2276,6 +2275,12 @@ int sqlite3Select(
   /* If there is are a sequence of queries, do the earlier ones first.
   */
   if( p->pPrior ){
+#ifndef SQLITE_OMIT_CURSOR
+    if( p->pFetch ){
+      sqlite3ErrorMsg(pParse, "cursors cannot be used on compound queries");
+      goto select_end;
+    }
+#endif
     return multiSelect(pParse, p, eDest, iParm, aff);
   }
 #endif
@@ -2360,6 +2365,26 @@ int sqlite3Select(
     goto select_end;
   }
 
+  /* We cannot use a SQL cursor on a join or on a DISTINCT query
+  */
+#ifndef SQLITE_OMIT_CURSOR
+  if( p->pFetch ){
+    if( p->isDistinct ){
+      sqlite3ErrorMsg(pParse, "cursors cannot be used on DISTINCT queries");
+      goto select_end;
+    }
+    if( pTabList->nSrc>0 ){
+      sqlite3ErrorMsg(pParse, "cursors cannot be used on joins");
+      goto select_end;
+    }
+    if( pTabList->a[0].pSelect ){
+      sqlite3ErrorMsg(pParse, "cursor cannot be used with nested queries "
+          "or views");
+      goto select_end;
+    }
+  }
+#endif
+
   /* Begin generating code.
   */
   v = sqlite3GetVdbe(pParse);
@@ -2522,8 +2547,16 @@ int sqlite3Select(
 
   /* Begin the database scan
   */
-  pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0, 
-                            pGroupBy ? 0 : &pOrderBy);
+#if 0 /* ndef SQLITE_OMIT_CURSOR */
+  if( p->pFetch ){
+    pWInfo = sqlite3WhereBeginFetch(pParse, pTabList, pWhere,
+                                    pOrderby, p->pFetch);
+  }else
+#endif
+  {
+    pWInfo = sqlite3WhereBegin(pParse, pTabList, pWhere, 0,
+                               pGroupBy ? 0 : &pOrderBy);
+  }
   if( pWInfo==0 ) goto select_end;
 
   /* Use the standard inner loop if we are not dealing with
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 9be16bc95..0616d05a3 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -11,7 +11,7 @@
 *************************************************************************
 ** Internal interface definitions for SQLite.
 **
-** @(#) $Id: sqliteInt.h,v 1.342 2004/11/22 10:02:11 danielk1977 Exp $
+** @(#) $Id: sqliteInt.h,v 1.343 2004/11/22 19:12:21 drh Exp $
 */
 #ifndef _SQLITEINT_H_
 #define _SQLITEINT_H_
@@ -307,6 +307,8 @@ typedef struct AuthContext AuthContext;
 typedef struct KeyClass KeyClass;
 typedef struct CollSeq CollSeq;
 typedef struct KeyInfo KeyInfo;
+typedef struct SqlCursor SqlCursor;
+typedef struct Fetch Fetch;
 
 /*
 ** Each database file to be accessed by the system is an instance
@@ -420,7 +422,10 @@ struct sqlite3 {
   void *pProgressArg;           /* Argument to the progress callback */
   int nProgressOps;             /* Number of opcodes for progress callback */
 #endif
-
+#ifndef SQLITE_OMIT_CURSOR
+  int nSqlCursor;               /* Number of slots in apSqlCursor[] */
+  SqlCursor **apSqlCursor;      /* Pointers to all active SQL cursors */
+#endif
   int errCode;                  /* Most recent error code (SQLITE_*) */
   u8 enc;                       /* Text encoding for this database. */
   u8 autoCommit;                /* The auto-commit flag. */
@@ -429,9 +434,8 @@ struct sqlite3 {
   void *pCollNeededArg;
   sqlite3_value *pValue;        /* Value used for transient conversions */
   sqlite3_value *pErr;          /* Most recent error message */
-
   char *zErrMsg;                /* Most recent error message (UTF-8 encoded) */
-  char *zErrMsg16;              /* Most recent error message (UTF-8 encoded) */
+  char *zErrMsg16;              /* Most recent error message (UTF-16 encoded) */
 };
 
 /*
@@ -929,17 +933,19 @@ struct WhereInfo {
 };
 
 /*
+** An instance of the following structure is used to store information
+** about a single FETCH sql command.
+*/
+struct Fetch {
+  SqlCursor *pCursor;  /* Cursor used by the fetch */
+  int isBackwards;     /* Cursor moves backwards if true, forward if false */
+  int doRewind;        /* True to rewind cursor before starting */
+};
+
+/*
 ** An instance of the following structure contains all information
 ** needed to generate code for a single SELECT statement.
 **
-** The zSelect field is used when the Select structure must be persistent.
-** Normally, the expression tree points to tokens in the original input
-** string that encodes the select.  But if the Select structure must live
-** longer than its input string (for example when it is used to describe
-** a VIEW) we have to make a copy of the input string so that the nodes
-** of the expression tree will have something to point to.  zSelect is used
-** to hold that copy.
-**
 ** nLimit is set to -1 if there is no LIMIT clause.  nOffset is set to 0.
 ** If there is a LIMIT clause, the parser sets nLimit to the value of the
 ** limit and nOffset to the value of the offset (or 0 if there is not
@@ -958,8 +964,8 @@ struct Select {
   Select *pPrior;        /* Prior select in a compound select statement */
   int nLimit, nOffset;   /* LIMIT and OFFSET values.  -1 means not used */
   int iLimit, iOffset;   /* Memory registers holding LIMIT & OFFSET counters */
-  char *zSelect;         /* Complete text of the SELECT command */
   IdList **ppOpenTemp;   /* OP_OpenTemp addresses used by multi-selects */
+  Fetch *pFetch;         /* If this stmt is part of a FETCH command */
 };
 
 /*
@@ -1039,6 +1045,11 @@ struct Parse {
   u8 explain;          /* True if the EXPLAIN flag is found on the query */
   u8 useAgg;           /* If true, extract field values from the aggregator
                        ** while generating expressions.  Normally false */
+#ifndef SQLITE_OMIT_CURSOR
+  u8 fetchDir;         /* The direction argument to the FETCH command */
+  int dirArg1;         /* First argument to the direction */
+  int dirArg2;         /* Second argument to the direction */
+#endif
   int nAgg;            /* Number of aggregate expressions */
   AggExpr *aAgg;       /* An array of aggregate expressions */
   Token sErrToken;     /* The token at which the error occurred */
@@ -1050,6 +1061,7 @@ struct Parse {
   Trigger *pNewTrigger;     /* Trigger under construct by a CREATE TRIGGER */
   TriggerStack *trigStack;  /* Trigger actions being coded */
   const char *zAuthContext; /* The 6th parameter to db->xAuth callbacks */
+  
 };
 
 /*
@@ -1212,6 +1224,18 @@ typedef struct {
   char **pzErrMsg;    /* Error message stored here */
 } InitData;
 
+/*
+** Each SQL cursor (a cursor created by the DECLARE ... CURSOR syntax)
+** is represented by an instance of the following structure.
+*/
+struct SqlCursor {
+  char *zName;           /* Name of this cursor */
+  int idx;               /* Index of this cursor in db->apSqlCursor[] */
+  Select *pSelect;       /* The SELECT statement that defines this cursor */
+  int nPtr;              /* Number of slots in aPtr[] */
+  sqlite3_value *aPtr;   /* Values that define the current cursor position */
+};
+
 
 /*
  * This global flag is set for performance testing of triggers. When it is set
@@ -1314,6 +1338,7 @@ void sqlite3SelectUnbind(Select*);
 Table *sqlite3SrcListLookup(Parse*, SrcList*);
 int sqlite3IsReadOnly(Parse*, Table*, int);
 void sqlite3OpenTableForReading(Vdbe*, int iCur, Table*);
+void sqlite3OpenTable(Vdbe*, int iCur, Table*, int);
 void sqlite3DeleteFrom(Parse*, SrcList*, Expr*);
 void sqlite3Update(Parse*, SrcList*, ExprList*, Expr*, int);
 WhereInfo *sqlite3WhereBegin(Parse*, SrcList*, Expr*, int, ExprList**);
@@ -1463,4 +1488,11 @@ void sqlite3AlterRenameTable(Parse*, SrcList*, Token*);
 int sqlite3GetToken(const unsigned char *, int *);
 void sqlite3NestedParse(Parse*, const char*, ...);
 
+#ifndef SQLITE_OMIT_CURSOR
+void sqlite3CursorDelete(SqlCursor*);
+void sqlite3CursorCreate(Parse*, Token*, Select*);
+void sqlite3CursorClose(Parse*, Token*);
+void sqlite3Fetch(Parse*, Token*, IdList*);
+#endif /* SQLITE_OMIT_CURSOR */
+
 #endif
diff --git a/src/test1.c b/src/test1.c
index c7ba77cf5..b6e8a5b41 100644
--- a/src/test1.c
+++ b/src/test1.c
@@ -13,7 +13,7 @@
 ** is not included in the SQLite library.  It is used for automated
 ** testing of the SQLite library.
 **
-** $Id: test1.c,v 1.116 2004/11/20 19:18:01 drh Exp $
+** $Id: test1.c,v 1.117 2004/11/22 19:12:21 drh Exp $
 */
 #include "sqliteInt.h"
 #include "tcl.h"
@@ -2552,6 +2552,12 @@ static void set_options(Tcl_Interp *interp){
   Tcl_SetVar2(interp, "sqlite_options", "conflict", "1", TCL_GLOBAL_ONLY);
 #endif
 
+#ifdef SQLITE_OMIT_CURSOR
+  Tcl_SetVar2(interp, "sqlite_options", "cursor", "0", TCL_GLOBAL_ONLY);
+#else
+  Tcl_SetVar2(interp, "sqlite_options", "cursor", "1", TCL_GLOBAL_ONLY);
+#endif
+
 #ifdef SQLITE_OMIT_DATETIME_FUNCS
   Tcl_SetVar2(interp, "sqlite_options", "datetime", "0", TCL_GLOBAL_ONLY);
 #else
diff --git a/src/where.c b/src/where.c
index c3f8082fc..97cf37d69 100644
--- a/src/where.c
+++ b/src/where.c
@@ -12,7 +12,7 @@
 ** This module contains C code that generates VDBE code used to process
 ** the WHERE clause of SQL statements.
 **
-** $Id: where.c,v 1.118 2004/11/22 10:02:20 danielk1977 Exp $
+** $Id: where.c,v 1.119 2004/11/22 19:12:21 drh Exp $
 */
 #include "sqliteInt.h"
 
@@ -248,9 +248,13 @@ static void exprAnalyze(SrcList *pSrc, ExprMaskSet *pMaskSet, ExprInfo *pInfo){
 ** All terms of the ORDER BY clause must be either ASC or DESC.  The
 ** *pbRev value is set to 1 if the ORDER BY clause is all DESC and it is
 ** set to 0 if the ORDER BY clause is all ASC.
+**
+** TODO:  If earlier terms of an ORDER BY clause match all terms of a
+** UNIQUE index, then subsequent terms of the ORDER BY can be ignored.
+** This optimization needs to be implemented.
 */
 static Index *findSortingIndex(
-  Parse *pParse,
+  Parse *pParse,          /* Parsing context */
   Table *pTab,            /* The table to be sorted */
   int base,               /* Cursor number for pTab */
   ExprList *pOrderBy,     /* The ORDER BY clause */
@@ -258,14 +262,15 @@ static Index *findSortingIndex(
   int nEqCol,             /* Number of index columns used with == constraints */
   int *pbRev              /* Set to 1 if ORDER BY is DESC */
 ){
-  int i, j;
-  Index *pMatch;
-  Index *pIdx;
-  int sortOrder;
+  int i, j;                    /* Loop counters */
+  Index *pMatch;               /* Best matching index so far */
+  Index *pIdx;                 /* Current index */
+  int sortOrder;               /* Which direction we are sorting */
   sqlite3 *db = pParse->db;
 
   assert( pOrderBy!=0 );
   assert( pOrderBy->nExpr>0 );
+  assert( pPreferredIdx!=0 || nEqCol==0 );
   sortOrder = pOrderBy->a[0].sortOrder;
   for(i=0; i<pOrderBy->nExpr; i++){
     Expr *p;
@@ -282,9 +287,10 @@ static Index *findSortingIndex(
     }
   }
 
-  /* If we get this far, it means the ORDER BY clause consists only of
-  ** ascending columns in the left-most table of the FROM clause.  Now
-  ** check for a matching index.
+  /* If we get this far, it means the ORDER BY clause consists of columns
+  ** that are all either ascending or descending and which refer only to
+  ** the left-most table of the FROM clause.  Find the index that is best
+  ** used for sorting.
   */
   pMatch = 0;
   for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
@@ -314,13 +320,34 @@ static Index *findSortingIndex(
       if( pIdx==pPreferredIdx ) break;
     }
   }
-  if( pMatch && pbRev ){
-    *pbRev = sortOrder==SQLITE_SO_DESC;
-  }
+  *pbRev = sortOrder==SQLITE_SO_DESC;
   return pMatch;
 }
 
 /*
+** Check table to see if the ORDER BY clause in pOrderBy can be satisfied
+** by sorting in order of ROWID.  Return true if so and set *pbRev to be
+** true for reverse ROWID and false for forward ROWID order.
+*/
+static int sortableByRowid(
+  int base,               /* Cursor number for table to be sorted */
+  ExprList *pOrderBy,     /* The ORDER BY clause */
+  int *pbRev              /* Set to 1 if ORDER BY is DESC */
+){
+  Expr *p;
+
+  assert( pOrderBy!=0 );
+  assert( pOrderBy->nExpr>0 );
+  p = pOrderBy->a[0].pExpr;
+  if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1 ){
+    *pbRev = pOrderBy->a[0].sortOrder;
+    return 1;
+  }
+  return 0;
+}
+
+
+/*
 ** Disable a term in the WHERE clause.  Except, do not disable the term
 ** if it controls a LEFT OUTER JOIN and it did not originate in the ON
 ** or USING clause of that join.
@@ -615,6 +642,12 @@ WhereInfo *sqlite3WhereBegin(
         }
       }
     }
+
+    /* If we found a term that tests ROWID with == or IN, that term
+    ** will be used to locate the rows in the database table.  There
+    ** is not need to continue into the code below that looks for
+    ** an index.  We will always use the ROWID over an index.
+    */
     if( iDirectEq[i]>=0 ){
       loopMask |= mask;
       pLevel->pIdx = 0;
@@ -735,35 +768,43 @@ WhereInfo *sqlite3WhereBegin(
   ** use of an index on the first table.
   */
   if( ppOrderBy && *ppOrderBy && pTabList->nSrc>0 ){
-     Index *pSortIdx;
-     Index *pIdx;
-     Table *pTab;
-     int bRev = 0;
+     Index *pSortIdx = 0;     /* Index that satisfies the ORDER BY clause */
+     Index *pIdx;             /* Index derived from the WHERE clause */
+     Table *pTab;             /* Left-most table in the FROM clause */
+     int bRev = 0;            /* True to reverse the output order */
+     int iCur;                /* Btree-cursor that will be used by pTab */
+     WhereLevel *pLevel0 = &pWInfo->a[0];
 
      pTab = pTabList->a[0].pTab;
-     pIdx = pWInfo->a[0].pIdx;
-     if( pIdx && pWInfo->a[0].score==4 ){
+     pIdx = pLevel0->pIdx;
+     iCur = pTabList->a[0].iCursor;
+     if( pIdx==0 && sortableByRowid(iCur, *ppOrderBy, &bRev) ){
+       /* The ORDER BY clause specifies ROWID order, which is what we
+       ** were going to be doing anyway...
+       */
+       *ppOrderBy = 0;
+       pLevel0->bRev = bRev;
+     }else if( pLevel0->score==4 ){
        /* If there is already an IN index on the left-most table,
        ** it will not give the correct sort order.
        ** So, pretend that no suitable index is found.
        */
-       pSortIdx = 0;
      }else if( iDirectEq[0]>=0 || iDirectLt[0]>=0 || iDirectGt[0]>=0 ){
        /* If the left-most column is accessed using its ROWID, then do
-       ** not try to sort by index.
+       ** not try to sort by index.  But do delete the ORDER BY clause
+       ** if it is redundant.
        */
-       pSortIdx = 0;
      }else{
-       int nEqCol = (pWInfo->a[0].score+4)/8;
-       pSortIdx = findSortingIndex(pParse, pTab, pTabList->a[0].iCursor, 
+       int nEqCol = (pLevel0->score+4)/8;
+       pSortIdx = findSortingIndex(pParse, pTab, iCur, 
                                    *ppOrderBy, pIdx, nEqCol, &bRev);
      }
      if( pSortIdx && (pIdx==0 || pIdx==pSortIdx) ){
        if( pIdx==0 ){
-         pWInfo->a[0].pIdx = pSortIdx;
-         pWInfo->a[0].iCur = pParse->nTab++;
+         pLevel0->pIdx = pSortIdx;
+         pLevel0->iCur = pParse->nTab++;
        }
-       pWInfo->a[0].bRev = bRev;
+       pLevel0->bRev = bRev;
        *ppOrderBy = 0;
      }
   }
@@ -828,7 +869,7 @@ WhereInfo *sqlite3WhereBegin(
       pLevel->op = OP_Noop;
     }else if( pIdx!=0 && pLevel->score>0 && pLevel->score%4==0 ){
       /* Case 2:  There is an index and all terms of the WHERE clause that
-      **          refer to the index use the "==" or "IN" operators.
+      **          refer to the index using the "==" or "IN" operators.
       */
       int start;
       int nColumn = (pLevel->score+4)/8;
@@ -892,9 +933,15 @@ WhereInfo *sqlite3WhereBegin(
       */
       int testOp = OP_Noop;
       int start;
+      int bRev = pLevel->bRev;
 
       brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
       cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
+      if( bRev ){
+        int t = iDirectGt[i];
+        iDirectGt[i] = iDirectLt[i];
+        iDirectLt[i] = t;
+      }
       if( iDirectGt[i]>=0 ){
         Expr *pX;
         k = iDirectGt[i];
@@ -905,10 +952,10 @@ WhereInfo *sqlite3WhereBegin(
         assert( pTerm->idxLeft==iCur );
         sqlite3ExprCode(pParse, pX->pRight);
         sqlite3VdbeAddOp(v, OP_ForceInt, pX->op==TK_LT || pX->op==TK_GT, brk);
-        sqlite3VdbeAddOp(v, OP_MoveGe, iCur, brk);
+        sqlite3VdbeAddOp(v, bRev ? OP_MoveLt : OP_MoveGe, iCur, brk);
         disableTerm(pLevel, &pTerm->p);
       }else{
-        sqlite3VdbeAddOp(v, OP_Rewind, iCur, brk);
+        sqlite3VdbeAddOp(v, bRev ? OP_Last : OP_Rewind, iCur, brk);
       }
       if( iDirectLt[i]>=0 ){
         Expr *pX;
@@ -922,14 +969,14 @@ WhereInfo *sqlite3WhereBegin(
         pLevel->iMem = pParse->nMem++;
         sqlite3VdbeAddOp(v, OP_MemStore, pLevel->iMem, 1);
         if( pX->op==TK_LT || pX->op==TK_GT ){
-          testOp = OP_Ge;
+          testOp = bRev ? OP_Le : OP_Ge;
         }else{
-          testOp = OP_Gt;
+          testOp = bRev ? OP_Lt : OP_Gt;
         }
         disableTerm(pLevel, &pTerm->p);
       }
       start = sqlite3VdbeCurrentAddr(v);
-      pLevel->op = OP_Next;
+      pLevel->op = bRev ? OP_Prev : OP_Next;
       pLevel->p1 = iCur;
       pLevel->p2 = start;
       if( testOp!=OP_Noop ){
@@ -943,12 +990,19 @@ WhereInfo *sqlite3WhereBegin(
       **          scan of the entire database table.
       */
       int start;
+      int opRewind;
 
       brk = pLevel->brk = sqlite3VdbeMakeLabel(v);
       cont = pLevel->cont = sqlite3VdbeMakeLabel(v);
-      sqlite3VdbeAddOp(v, OP_Rewind, iCur, brk);
+      if( pLevel->bRev ){
+        opRewind = OP_Last;
+        pLevel->op = OP_Prev;
+      }else{
+        opRewind = OP_Rewind;
+        pLevel->op = OP_Next;
+      }
+      sqlite3VdbeAddOp(v, opRewind, iCur, brk);
       start = sqlite3VdbeCurrentAddr(v);
-      pLevel->op = OP_Next;
       pLevel->p1 = iCur;
       pLevel->p2 = start;
       haveKey = 0;
diff --git a/test/alter.test b/test/alter.test
index 1781690a8..24e66d494 100644
--- a/test/alter.test
+++ b/test/alter.test
@@ -1,14 +1,17 @@
+# 2004 November 10
 #
-# The author or author's hereby grant to the public domain a non-exclusive,
-# fully paid-up, perpetual, license in the software and all related
-# intellectual property to make, have made, use, have used, reproduce,
-# prepare derivative works, distribute, perform and display the work.  
+# 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 implements regression tests for SQLite library.  The
 # focus of this script is testing the ALTER TABLE statement.
 #
-# $Id: alter.test,v 1.7 2004/11/22 13:35:42 danielk1977 Exp $
+# $Id: alter.test,v 1.8 2004/11/22 19:12:21 drh Exp $
 #
 
 set testdir [file dirname $argv0]
diff --git a/test/collate4.test b/test/collate4.test
index e7111c807..24b926792 100644
--- a/test/collate4.test
+++ b/test/collate4.test
@@ -12,7 +12,7 @@
 # This file implements regression tests for SQLite library.  The
 # focus of this script is page cache subsystem.
 #
-# $Id: collate4.test,v 1.4 2004/11/03 16:27:02 drh Exp $
+# $Id: collate4.test,v 1.5 2004/11/22 19:12:21 drh Exp $
 
 set testdir [file dirname $argv0]
 source $testdir/tester.tcl
@@ -669,6 +669,7 @@ do_test collate4-4.15 {
 # These indices are never used for sorting in SQLite. And you can't
 # create another index on an INTEGER PRIMARY KEY column, so we don't have 
 # to test that.
+# (Revised 2004-Nov-22):  The ROWID can be used for sorting now.
 #
 do_test collate4-6.0 {
   execsql {
@@ -682,12 +683,12 @@ do_test collate4-6.1 {
   cksort {
     SELECT * FROM collate4t1 ORDER BY 1;
   }
-} {10 15 101 sort}
+} {10 15 101 nosort}
 do_test collate4-6.2 {
   cksort {
     SELECT * FROM collate4t1 ORDER BY oid;
   }
-} {10 15 101 sort}
+} {10 15 101 nosort}
 do_test collate4-6.3 {
   cksort {
     SELECT * FROM collate4t1 ORDER BY oid||'' COLLATE TEXT;
diff --git a/test/cursor.test b/test/cursor.test
new file mode 100644
index 000000000..dcd83a2a4
--- /dev/null
+++ b/test/cursor.test
@@ -0,0 +1,136 @@
+# 2004 November 22
+#
+# 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 implements regression tests for SQLite library.  The
+# focus of this script is DECLARE...CURSOR functionality
+#
+# $Id: cursor.test,v 1.1 2004/11/22 19:12:21 drh Exp $
+#
+
+set testdir [file dirname $argv0]
+source $testdir/tester.tcl
+
+# If SQLITE_OMIT_CURSOR is defined, omit this file.
+ifcapable {!cursor} {
+  finish_test
+  return
+}
+
+########
+# Test the logic that creates and destroys cursors
+########
+do_test cursor-1.1 {
+  execsql {
+    CREATE TABLE t1(a,b,c);
+    CREATE INDEX t1i1 ON t1(a);
+    CREATE INDEX t1i2 ON t1(b,c);
+  }
+  execsql {
+    DECLARE c1 CURSOR FOR SELECT c FROM t1 ORDER BY a;
+  }
+} {}
+ifcapable schema_pragmas {
+  do_test cursor-1.2 {
+    execsql {PRAGMA cursor_list}
+  } {0 c1}
+}
+do_test cursor-1.3 {
+  execsql {
+    DECLARE c2 CURSOR FOR SELECT a FROM t1 ORDER BY b, c;
+  }
+} {}
+ifcapable schema_pragmas {
+  do_test cursor-1.4 {
+    execsql {PRAGMA cursor_list}
+  } {0 c1 1 c2}
+}
+do_test cursor-1.5 {
+  catchsql {
+    CLOSE c3;
+  }
+} {1 {no such cursor: c3}}
+ifcapable schema_pragmas {
+  do_test cursor-1.6 {
+    execsql {PRAGMA cursor_list}
+  } {0 c1 1 c2}
+}
+do_test cursor-1.7 {
+  catchsql {
+    CLOSE c1;
+  }
+} {0 {}}
+ifcapable schema_pragmas {
+  do_test cursor-1.8 {
+    execsql {PRAGMA cursor_list}
+  } {1 c2}
+}
+do_test cursor-1.9 {
+  catchsql {
+    CLOSE c1;
+  }
+} {1 {no such cursor: c1}}
+ifcapable schema_pragmas {
+  do_test cursor-1.10 {
+    execsql {PRAGMA cursor_list}
+  } {1 c2}
+}
+do_test cursor-1.11 {
+  catchsql {
+    DECLARE c2 CURSOR FOR SELECT * FROM t1;
+  }
+} {1 {another cursor named c2 already exists}}
+do_test cursor-1.12 {
+  catchsql {
+    DECLARE c3 CURSOR FOR SELECT * FROM t1;
+  }
+} {0 {}}
+ifcapable schema_pragmas {
+  do_test cursor-1.13 {
+    execsql {PRAGMA cursor_list}
+  } {0 c3 1 c2}
+}
+do_test cursor-1.14 {
+  execsql {
+    CLOSE c2;
+    CLOSE c3;
+  }
+} {}
+ifcapable schema_pragmas {
+  do_test cursor-1.15 {
+    execsql {PRAGMA cursor_list}
+  } {}
+}
+
+set all {}
+for {set i 1} {$i<=50} {incr i} {
+  lappend all [expr {$i-1}] x$i
+  do_test cursor-2.1.$i.1 {
+    execsql "DECLARE x$i CURSOR FOR SELECT * FROM t1"
+  } {}
+  ifcapable schema_pragmas {
+    do_test cursor-2.1.$i.2 {
+      execsql {PRAGMA cursor_list}
+    } $all
+  }
+}
+for {set i 1} {$i<=50} {incr i} {
+  set all [lrange $all 2 end]
+  do_test cursor-2.2.$i.1 {
+    execsql "CLOSE x$i"
+  } {}
+  ifcapable schema_pragmas {
+    do_test cursor-2.2.$i.2 {
+      execsql {PRAGMA cursor_list}
+    } $all
+  }
+}  
+
+
+finish_test
diff --git a/test/where.test b/test/where.test
index 74f8e5f69..17533fac4 100644
--- a/test/where.test
+++ b/test/where.test
@@ -11,7 +11,7 @@
 # This file implements regression tests for SQLite library.  The
 # focus of this file is testing the use of indices in WHERE clases.
 #
-# $Id: where.test,v 1.23 2004/11/03 16:27:02 drh Exp $
+# $Id: where.test,v 1.24 2004/11/22 19:12:21 drh Exp $
 
 set testdir [file dirname $argv0]
 source $testdir/tester.tcl
@@ -508,6 +508,47 @@ do_test where-6.19 {
     SELECT y FROM t1 ORDER BY w LIMIT 3;
   }
 } {4 9 16 nosort}
+do_test where-6.20 {
+  cksort {
+    SELECT y FROM t1 ORDER BY rowid LIMIT 3;
+  }
+} {4 9 16 nosort}
+do_test where-6.21 {
+  cksort {
+    SELECT y FROM t1 ORDER BY rowid, y LIMIT 3;
+  }
+} {4 9 16 nosort}
+do_test where-6.22 {
+  cksort {
+    SELECT y FROM t1 ORDER BY rowid, y DESC LIMIT 3;
+  }
+} {4 9 16 nosort}
+do_test where-6.23 {
+  cksort {
+    SELECT y FROM t1 WHERE y>4 ORDER BY rowid, w, x LIMIT 3;
+  }
+} {9 16 25 nosort}
+do_test where-6.24 {
+  cksort {
+    SELECT y FROM t1 WHERE y>=9 ORDER BY rowid, x DESC, w LIMIT 3;
+  }
+} {9 16 25 nosort}
+do_test where-6.25 {
+  cksort {
+    SELECT y FROM t1 WHERE y>4 AND y<25 ORDER BY rowid;
+  }
+} {9 16 nosort}
+do_test where-6.26 {
+  cksort {
+    SELECT y FROM t1 WHERE y>=4 AND y<=25 ORDER BY oid;
+  }
+} {4 9 16 25 nosort}
+do_test where-6.27 {
+  cksort {
+    SELECT y FROM t1 WHERE y<=25 ORDER BY _rowid_, w+y;
+  }
+} {4 9 16 25 nosort}
+
 
 # Tests for reverse-order sorting.
 #
@@ -661,6 +702,31 @@ do_test where-7.30 {
     SELECT w FROM t1 WHERE x=6 AND y>=10201 ORDER BY y DESC;
   }
 } {100 nosort}
+do_test where-7.31 {
+  cksort {
+    SELECT y FROM t1 ORDER BY rowid DESC LIMIT 3
+  }
+} {10201 10000 9801 nosort}
+do_test where-7.32 {
+  cksort {
+    SELECT y FROM t1 WHERE y<25 ORDER BY rowid DESC, x
+  }
+} {16 9 4 nosort}
+do_test where-7.33 {
+  cksort {
+    SELECT y FROM t1 WHERE y<=25 ORDER BY rowid DESC, x
+  }
+} {25 16 9 4 nosort}
+do_test where-7.34 {
+  cksort {
+    SELECT y FROM t1 WHERE y<25 AND y>4 ORDER BY rowid DESC, y DESC
+  }
+} {16 9 nosort}
+do_test where-7.35 {
+  cksort {
+    SELECT y FROM t1 WHERE y<25 AND y>=4 ORDER BY rowid DESC
+  }
+} {16 9 4 nosort}
 
 do_test where-8.1 {
   execsql {
diff --git a/tool/mkkeywordhash.c b/tool/mkkeywordhash.c
index 3ab67f583..16601be46 100644
--- a/tool/mkkeywordhash.c
+++ b/tool/mkkeywordhash.c
@@ -55,40 +55,45 @@ struct Keyword {
 #else
 #  define CONFLICT   32
 #endif
+#ifdef SQLITE_OMIT_CURSOR
+#  define CURSOR     0
+#else
+#  define CURSOR     64
+#endif
 #ifdef SQLITE_OMIT_EXPLAIN
 #  define EXPLAIN    0
 #else
-#  define EXPLAIN    64
+#  define EXPLAIN    128
 #endif
 #ifdef SQLITE_OMIT_FOREIGN_KEY
 #  define FKEY       0
 #else
-#  define FKEY       128
+#  define FKEY       256
 #endif
 #ifdef SQLITE_OMIT_PRAGMA
 #  define PRAGMA     0
 #else
-#  define PRAGMA     256
+#  define PRAGMA     512
 #endif
 #ifdef SQLITE_OMIT_REINDEX
 #  define REINDEX    0
 #else
-#  define REINDEX    512
+#  define REINDEX    1024
 #endif
 #ifdef SQLITE_OMIT_TRIGGER
 #  define TRIGGER    0
 #else
-#  define TRIGGER    1024
+#  define TRIGGER    2048
 #endif
 #ifdef SQLITE_OMIT_VACUUM
 #  define VACUUM     0
 #else
-#  define VACUUM     2048
+#  define VACUUM     4096
 #endif
 #ifdef SQLITE_OMIT_VIEW
 #  define VIEW       0
 #else
-#  define VIEW       4096
+#  define VIEW       8192
 #endif
 
 
@@ -97,6 +102,7 @@ struct Keyword {
 */
 static Keyword aKeywordTable[] = {
   { "ABORT",            "TK_ABORT",        CONFLICT|TRIGGER       },
+  { "ABSOLUTE",         "TK_ABSOLUTE",     CURSOR                 },
   { "AFTER",            "TK_AFTER",        TRIGGER                },
   { "ALL",              "TK_ALL",          ALWAYS                 },
   { "ALTER",            "TK_ALTER",        ALTER                  },
@@ -112,16 +118,20 @@ static Keyword aKeywordTable[] = {
   { "CASCADE",          "TK_CASCADE",      FKEY                   },
   { "CASE",             "TK_CASE",         ALWAYS                 },
   { "CHECK",            "TK_CHECK",        ALWAYS                 },
+  { "CLOSE",            "TK_CLOSE",        CURSOR                 },
   { "COLLATE",          "TK_COLLATE",      ALWAYS                 },
   { "COMMIT",           "TK_COMMIT",       ALWAYS                 },
   { "CONFLICT",         "TK_CONFLICT",     CONFLICT               },
   { "CONSTRAINT",       "TK_CONSTRAINT",   ALWAYS                 },
   { "CREATE",           "TK_CREATE",       ALWAYS                 },
   { "CROSS",            "TK_JOIN_KW",      ALWAYS                 },
+  { "CURSOR",           "TK_CURSOR",       CURSOR                 },
+  { "CURRENT",          "TK_CURRENT",      CURSOR                 },
   { "CURRENT_DATE",     "TK_CDATE",        ALWAYS                 },
   { "CURRENT_TIME",     "TK_CTIME",        ALWAYS                 },
   { "CURRENT_TIMESTAMP","TK_CTIMESTAMP",   ALWAYS                 },
   { "DATABASE",         "TK_DATABASE",     ATTACH                 },
+  { "DECLARE",          "TK_DECLARE",      CURSOR                 },
   { "DEFAULT",          "TK_DEFAULT",      ALWAYS                 },
   { "DEFERRED",         "TK_DEFERRED",     ALWAYS                 },
   { "DEFERRABLE",       "TK_DEFERRABLE",   FKEY                   },
@@ -138,6 +148,8 @@ static Keyword aKeywordTable[] = {
   { "EXCLUSIVE",        "TK_EXCLUSIVE",    ALWAYS                 },
   { "EXPLAIN",          "TK_EXPLAIN",      EXPLAIN                },
   { "FAIL",             "TK_FAIL",         CONFLICT|TRIGGER       },
+  { "FETCH",            "TK_FETCH",        CURSOR                 },
+  { "FIRST",            "TK_FIRST",        CURSOR                 },
   { "FOR",              "TK_FOR",          TRIGGER                },
   { "FOREIGN",          "TK_FOREIGN",      FKEY                   },
   { "FROM",             "TK_FROM",         ALWAYS                 },
@@ -164,6 +176,7 @@ static Keyword aKeywordTable[] = {
   { "LIMIT",            "TK_LIMIT",        ALWAYS                 },
   { "MATCH",            "TK_MATCH",        ALWAYS                 },
   { "NATURAL",          "TK_JOIN_KW",      ALWAYS                 },
+  { "NEXT",             "TK_NEXT",         CURSOR                 },
   { "NOT",              "TK_NOT",          ALWAYS                 },
   { "NOTNULL",          "TK_NOTNULL",      ALWAYS                 },
   { "NULL",             "TK_NULL",         ALWAYS                 },
@@ -174,10 +187,12 @@ static Keyword aKeywordTable[] = {
   { "ORDER",            "TK_ORDER",        ALWAYS                 },
   { "OUTER",            "TK_JOIN_KW",      ALWAYS                 },
   { "PRAGMA",           "TK_PRAGMA",       PRAGMA                 },
+  { "PRIOR",            "TK_PRIOR",        CURSOR                 },
   { "PRIMARY",          "TK_PRIMARY",      ALWAYS                 },
   { "RAISE",            "TK_RAISE",        TRIGGER                },
   { "REFERENCES",       "TK_REFERENCES",   FKEY                   },
   { "REINDEX",          "TK_REINDEX",      REINDEX                },
+  { "RELATIVE",         "TK_RELATIVE",     CURSOR                 },
   { "RENAME",           "TK_RENAME",       ALTER                  },
   { "REPLACE",          "TK_REPLACE",      CONFLICT               },
   { "RESTRICT",         "TK_RESTRICT",     FKEY                   },