Some progress on user-defined collation sequences. (CVS 1544)

FossilOrigin-Name: c634e71f1909819fb55c728bc410e5cc390428e3

15 files changed, 555 insertions, 209 deletions

diff --git a/src/build.c b/src/build.c
index 00bf979b0..55b954e0b 100644
--- a/src/build.c
+++ b/src/build.c
@@ -23,7 +23,7 @@
 **     ROLLBACK
 **     PRAGMA
 **
-** $Id: build.c,v 1.210 2004/06/09 00:48:12 drh Exp $
+** $Id: build.c,v 1.211 2004/06/09 09:55:17 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 #include <ctype.h>
@@ -784,7 +784,7 @@ void sqlite3AddDefaultValue(Parse *pParse, Token *pVal, int minusFlag){
 ** If the key is not an INTEGER PRIMARY KEY, then create a unique
 ** index for the key.  No index is created for INTEGER PRIMARY KEYs.
 */
-void sqlite3AddPrimaryKey(Parse *pParse, IdList *pList, int onError){
+void sqlite3AddPrimaryKey(Parse *pParse, ExprList *pList, int onError){
   Table *pTab = pParse->pNewTable;
   char *zType = 0;
   int iCol = -1, i;
@@ -799,7 +799,7 @@ void sqlite3AddPrimaryKey(Parse *pParse, IdList *pList, int onError){
     iCol = pTab->nCol - 1;
     pTab->aCol[iCol].isPrimKey = 1;
   }else{
-    for(i=0; i<pList->nId; i++){
+    for(i=0; i<pList->nExpr; i++){
       for(iCol=0; iCol<pTab->nCol; iCol++){
         if( sqlite3StrICmp(pList->a[i].zName, pTab->aCol[iCol].zName)==0 ){
           break;
@@ -807,7 +807,7 @@ void sqlite3AddPrimaryKey(Parse *pParse, IdList *pList, int onError){
       }
       if( iCol<pTab->nCol ) pTab->aCol[iCol].isPrimKey = 1;
     }
-    if( pList->nId>1 ) iCol = -1;
+    if( pList->nExpr>1 ) iCol = -1;
   }
   if( iCol>=0 && iCol<pTab->nCol ){
     zType = pTab->aCol[iCol].zType;
@@ -821,79 +821,84 @@ void sqlite3AddPrimaryKey(Parse *pParse, IdList *pList, int onError){
   }
 
 primary_key_exit:
-  sqlite3IdListDelete(pList);
+  sqlite3ExprListDelete(pList);
   return;
 }
 
 /*
-** Return a pointer to CollSeq given the name of a collating sequence.
-** If the collating sequence did not previously exist, create it but
-** assign it an NULL comparison function.
-*/
-CollSeq *sqlite3CollateType(Parse *pParse, const char *zType, int nType){
-  CollSeq *pColl;
-  sqlite *db = pParse->db;
-
-  pColl = sqlite3HashFind(&db->aCollSeq, zType, nType);
-  if( pColl==0 ){
-    sqlite3ChangeCollatingFunction(db, zType, nType, 0, 0);
-    pColl = sqlite3HashFind(&db->aCollSeq, zType, nType);
-  }
-  return pColl;
-}
-
-/*
 ** Set the collation function of the most recently parsed table column
 ** to the CollSeq given.
 */
 void sqlite3AddCollateType(Parse *pParse, const char *zType, int nType){
   Table *p;
+  Index *pIdx;
   CollSeq *pColl;
-  sqlite *db = pParse->db;
+  int i;
 
   if( (p = pParse->pNewTable)==0 ) return;
-  pColl = sqlite3HashFind(&db->aCollSeq, zType, nType);
-  if( pColl==0 ){
-    pColl = sqlite3ChangeCollatingFunction(db, zType, nType, 0, 0);
-  }
-  if( pColl ){
-    p->aCol[p->nCol-1].pColl = pColl;
+  i = p->nCol-1;
+
+  pColl = sqlite3LocateCollSeq(pParse, zType, nType);
+  p->aCol[i].pColl = pColl;
+
+  /* If the column is declared as "<name> PRIMARY KEY COLLATE <type>",
+  ** then an index may have been created on this column before the
+  ** collation type was added. Correct this if it is the case.
+  */
+  for(pIdx = p->pIndex; pIdx; pIdx=pIdx->pNext){
+    assert( pIdx->nColumn==1 );
+    if( pIdx->aiColumn[0]==i ) pIdx->keyInfo.aColl[0] = pColl;
   }
 }
 
 /*
-** Create or modify a collating sequence entry in the sqlite.aCollSeq
-** table.
+** Locate and return an entry from the db.aCollSeq hash table. If the entry
+** specified by zName and nName is not found and parameter 'create' is
+** true, then create a new entry.
 **
-** Once an entry is added to the sqlite.aCollSeq table, it can never
-** be removed, though is comparison function or user data can be changed.
+** FIX ME: For now, return NULL if create is not true and the entry is not
+** found. But this needs to change to call the collation factory.
 **
-** Return a pointer to the collating function that was created or modified.
+** FIX ME: If we have a UTF-8 version of the collation function, and a
+** UTF-16 version would be better, should the collation factory be called?
+** If so should a flag be set to say that we already requested such a
+** function and couldn't get one?
 */
-CollSeq *sqlite3ChangeCollatingFunction(
-  sqlite *db,             /* Database into which to insert the collation */
-  const char *zName,      /* Name of the collation */
-  int nName,              /* Number of characters in zName */
-  void *pUser,            /* First argument to xCmp */
-  int (*xCmp)(void*,int,const void*,int,const void*) /* Comparison function */
+CollSeq *sqlite3FindCollSeq(
+  sqlite *db, 
+  const char *zName, 
+  int nName,
+  int create
 ){
   CollSeq *pColl;
-
+  if( nName<0 ) nName = strlen(zName);
   pColl = sqlite3HashFind(&db->aCollSeq, zName, nName);
-  if( pColl==0 ){
-    pColl = sqliteMallocRaw( sizeof(*pColl) + nName + 1 );
-    if( pColl==0 ){
-      return 0;
+  if( 0==pColl && create ){
+    pColl = sqliteMalloc( sizeof(*pColl) + nName + 1 );
+    if( pColl ){
+      pColl->zName = (char*)&pColl[1];
+      memcpy(pColl->zName, zName, nName+1);
+      sqlite3HashInsert(&db->aCollSeq, pColl->zName, nName, pColl);
+    }
+  }
+  return pColl;
+}
+
+CollSeq *sqlite3LocateCollSeq(Parse *pParse, const char *zName, int nName){
+  CollSeq *pColl = sqlite3FindCollSeq(pParse->db, zName, nName, 0);
+  if( !pColl ){
+    if( pParse->nErr==0 ){
+      sqlite3SetNString(&pParse->zErrMsg, 
+          "no such collation sequence: ", -1, 
+          zName, nName, 0);
     }
-    pColl->zName = (char*)&pColl[1];
-    memcpy(pColl->zName, zName, nName+1);
-    sqlite3HashInsert(&db->aCollSeq, pColl->zName, nName, pColl);
+    pParse->nErr++;
   }
-  pColl->pUser = pUser;
-  pColl->xCmp = xCmp;
   return pColl;
 }
 
+
+
 /*
 ** Scan the column type name zType (length nType) and return the
 ** associated affinity type.
@@ -1540,9 +1545,9 @@ exit_drop_table:
 */
 void sqlite3CreateForeignKey(
   Parse *pParse,       /* Parsing context */
-  IdList *pFromCol,    /* Columns in this table that point to other table */
+  ExprList *pFromCol,  /* Columns in this table that point to other table */
   Token *pTo,          /* Name of the other table */
-  IdList *pToCol,      /* Columns in the other table */
+  ExprList *pToCol,    /* Columns in the other table */
   int flags            /* Conflict resolution algorithms. */
 ){
   Table *p = pParse->pNewTable;
@@ -1557,24 +1562,24 @@ void sqlite3CreateForeignKey(
   if( pFromCol==0 ){
     int iCol = p->nCol-1;
     if( iCol<0 ) goto fk_end;
-    if( pToCol && pToCol->nId!=1 ){
+    if( pToCol && pToCol->nExpr!=1 ){
       sqlite3ErrorMsg(pParse, "foreign key on %s"
          " should reference only one column of table %T",
          p->aCol[iCol].zName, pTo);
       goto fk_end;
     }
     nCol = 1;
-  }else if( pToCol && pToCol->nId!=pFromCol->nId ){
+  }else if( pToCol && pToCol->nExpr!=pFromCol->nExpr ){
     sqlite3ErrorMsg(pParse,
         "number of columns in foreign key does not match the number of "
         "columns in the referenced table");
     goto fk_end;
   }else{
-    nCol = pFromCol->nId;
+    nCol = pFromCol->nExpr;
   }
   nByte = sizeof(*pFKey) + nCol*sizeof(pFKey->aCol[0]) + pTo->n + 1;
   if( pToCol ){
-    for(i=0; i<pToCol->nId; i++){
+    for(i=0; i<pToCol->nExpr; i++){
       nByte += strlen(pToCol->a[i].zName) + 1;
     }
   }
@@ -1631,8 +1636,8 @@ void sqlite3CreateForeignKey(
 
 fk_end:
   sqliteFree(pFKey);
-  sqlite3IdListDelete(pFromCol);
-  sqlite3IdListDelete(pToCol);
+  sqlite3ExprListDelete(pFromCol);
+  sqlite3ExprListDelete(pToCol);
 }
 
 /*
@@ -1665,8 +1670,8 @@ void sqlite3CreateIndex(
   Parse *pParse,   /* All information about this parse */
   Token *pName1,   /* First part of index name. May be NULL */
   Token *pName2,   /* Second part of index name. May be NULL */
-  SrcList *pTblName, /* Name of the table to index. Use pParse->pNewTable if 0 */
-  IdList *pList,   /* A list of columns to be indexed */
+  SrcList *pTblName,  /* Table to index. Use pParse->pNewTable if 0 */
+  ExprList *pList,   /* A list of columns to be indexed */
   int onError,     /* OE_Abort, OE_Ignore, OE_Replace, or OE_None */
   Token *pStart,   /* The CREATE token that begins a CREATE TABLE statement */
   Token *pEnd      /* The ")" that closes the CREATE INDEX statement */
@@ -1794,7 +1799,7 @@ void sqlite3CreateIndex(
   if( pList==0 ){
     nullId.z = pTab->aCol[pTab->nCol-1].zName;
     nullId.n = strlen(nullId.z);
-    pList = sqlite3IdListAppend(0, &nullId);
+    pList = sqlite3ExprListAppend(0, 0, &nullId);
     if( pList==0 ) goto exit_create_index;
   }
 
@@ -1802,13 +1807,13 @@ void sqlite3CreateIndex(
   ** Allocate the index structure. 
   */
   pIndex = sqliteMalloc( sizeof(Index) + strlen(zName) + 1 +
-                        (sizeof(int) + sizeof(CollSeq*))*pList->nId );
+                        (sizeof(int) + sizeof(CollSeq*))*pList->nExpr );
   if( pIndex==0 ) goto exit_create_index;
-  pIndex->aiColumn = (int*)&pIndex->keyInfo.aColl[pList->nId];
-  pIndex->zName = (char*)&pIndex->aiColumn[pList->nId];
+  pIndex->aiColumn = (int*)&pIndex->keyInfo.aColl[pList->nExpr];
+  pIndex->zName = (char*)&pIndex->aiColumn[pList->nExpr];
   strcpy(pIndex->zName, zName);
   pIndex->pTable = pTab;
-  pIndex->nColumn = pList->nId;
+  pIndex->nColumn = pList->nExpr;
   pIndex->onError = onError;
   pIndex->autoIndex = pName==0;
   pIndex->iDb = iDb;
@@ -1817,7 +1822,7 @@ void sqlite3CreateIndex(
   ** load the column indices into the Index structure.  Report an error
   ** if any column is not found.
   */
-  for(i=0; i<pList->nId; i++){
+  for(i=0; i<pList->nExpr; i++){
     for(j=0; j<pTab->nCol; j++){
       if( sqlite3StrICmp(pList->a[i].zName, pTab->aCol[j].zName)==0 ) break;
     }
@@ -1828,9 +1833,15 @@ void sqlite3CreateIndex(
       goto exit_create_index;
     }
     pIndex->aiColumn[i] = j;
-    pIndex->keyInfo.aColl[i] = pTab->aCol[j].pColl;
+    if( pList->a[i].pExpr ){
+      assert( pList->a[i].pExpr->pColl );
+      pIndex->keyInfo.aColl[i] = pList->a[i].pExpr->pColl;
+    }else{
+      pIndex->keyInfo.aColl[i] = pTab->aCol[j].pColl;
+    }
+    assert( pIndex->keyInfo.aColl[i] );
   }
-  pIndex->keyInfo.nField = pList->nId;
+  pIndex->keyInfo.nField = pList->nExpr;
 
   /* Link the new Index structure to its table and to the other
   ** in-memory database structures. 
@@ -1915,7 +1926,11 @@ void sqlite3CreateIndex(
     }
     sqlite3VdbeAddOp(v, OP_String8, 0, 0);
     if( pStart && pEnd ){
-      sqlite3VdbeChangeP3(v, -1, "CREATE INDEX ", P3_STATIC);
+      if( onError==OE_None ){
+        sqlite3VdbeChangeP3(v, -1, "CREATE INDEX ", P3_STATIC);
+      }else{
+        sqlite3VdbeChangeP3(v, -1, "CREATE UNIQUE INDEX ", P3_STATIC);
+      }
       sqlite3VdbeAddOp(v, OP_String8, 0, 0);
       n = Addr(pEnd->z) - Addr(pName->z) + 1;
       sqlite3VdbeChangeP3(v, -1, pName->z, n);
@@ -1950,7 +1965,7 @@ void sqlite3CreateIndex(
 
   /* Clean up before exiting */
 exit_create_index:
-  sqlite3IdListDelete(pList);
+  sqlite3ExprListDelete(pList);
   /* sqlite3SrcListDelete(pTable); */
   sqliteFree(zName);
   return;
diff --git a/src/expr.c b/src/expr.c
index 36b421f53..b341f83a6 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.136 2004/06/06 12:41:50 danielk1977 Exp $
+** $Id: expr.c,v 1.137 2004/06/09 09:55:18 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 #include <ctype.h>
@@ -56,6 +56,20 @@ char sqlite3ExprAffinity(Expr *pExpr){
 }
 
 /*
+** Return the default collation sequence for the expression pExpr. If
+** there is no default collation type, return 0.
+*/
+CollSeq *sqlite3ExprCollSeq(Expr *pExpr){
+  if( pExpr ){
+    if( pExpr->pColl ) return pExpr->pColl;
+    if( pExpr->op==TK_AS ){
+      return sqlite3ExprCollSeq(pExpr->pLeft);
+    }
+  }
+  return 0;
+}
+
+/*
 ** pExpr is the left operand of a comparison operator.  aff2 is the
 ** type affinity of the right operand.  This routine returns the
 ** type affinity that should be used for the comparison operator.
@@ -135,6 +149,23 @@ static int binaryCompareP1(Expr *pExpr1, Expr *pExpr2, int jumpIfNull){
 }
 
 /*
+** Return a pointer to the collation sequence that should be used by
+** a binary comparison operator comparing pLeft and pRight.
+**
+** If the left hand expression has a collating sequence type, then it is
+** used. Otherwise the collation sequence for the right hand expression
+** is used, or the default (BINARY) if neither expression has a collating
+** type.
+*/
+static CollSeq* binaryCompareCollSeq(Expr *pLeft, Expr *pRight){
+  CollSeq *pColl = sqlite3ExprCollSeq(pLeft);
+  if( !pColl ){
+    pColl = sqlite3ExprCollSeq(pRight);
+  }
+  return pColl;
+}
+
+/*
 ** Construct a new expression node and return a pointer to it.  Memory
 ** for this node is obtained from sqliteMalloc().  The calling function
 ** is responsible for making sure the node eventually gets freed.
@@ -588,6 +619,7 @@ static int lookupName(
         /* Substitute the rowid (column -1) for the INTEGER PRIMARY KEY */
         pExpr->iColumn = j==pTab->iPKey ? -1 : j;
         pExpr->affinity = pTab->aCol[j].affinity;
+        pExpr->pColl = pTab->aCol[j].pColl;
         break;
       }
     }
@@ -620,6 +652,7 @@ static int lookupName(
           cnt++;
           pExpr->iColumn = j==pTab->iPKey ? -1 : j;
           pExpr->affinity = pTab->aCol[j].affinity;
+          pExpr->pColl = pTab->aCol[j].pColl;
           break;
         }
       }
@@ -798,6 +831,7 @@ int sqlite3ExprResolveIds(
       char affinity;
       Vdbe *v = sqlite3GetVdbe(pParse);
       KeyInfo keyInfo;
+      int addr;        /* Address of OP_OpenTemp instruction */
 
       if( v==0 ) return 1;
       if( sqlite3ExprResolveIds(pParse, pSrcList, pEList, pExpr->pLeft) ){
@@ -819,11 +853,9 @@ int sqlite3ExprResolveIds(
       ** is used.
       */
       pExpr->iTable = pParse->nTab++;
+      addr = sqlite3VdbeAddOp(v, OP_OpenTemp, pExpr->iTable, 0);
       memset(&keyInfo, 0, sizeof(keyInfo));
       keyInfo.nField = 1;
-      keyInfo.aColl[0] = pParse->db->pDfltColl;
-      sqlite3VdbeOp3(v, OP_OpenTemp, pExpr->iTable, 0, \
-           (char*)&keyInfo, P3_KEYINFO);
       sqlite3VdbeAddOp(v, OP_SetNumColumns, pExpr->iTable, 1);
 
       if( pExpr->pSelect ){
@@ -835,6 +867,10 @@ int sqlite3ExprResolveIds(
         int iParm = pExpr->iTable +  (((int)affinity)<<16);
         assert( (pExpr->iTable&0x0000FFFF)==pExpr->iTable );
         sqlite3Select(pParse, pExpr->pSelect, SRT_Set, iParm, 0, 0, 0, 0);
+        if( pExpr->pSelect->pEList && pExpr->pSelect->pEList->nExpr>0 ){ 
+          keyInfo.aColl[0] = binaryCompareCollSeq(pExpr->pLeft,
+              pExpr->pSelect->pEList->a[0].pExpr);
+        }
       }else if( pExpr->pList ){
         /* Case 2:     expr IN (exprlist)
         **
@@ -849,6 +885,7 @@ int sqlite3ExprResolveIds(
           affinity = SQLITE_AFF_NUMERIC;
         }
         affStr = sqlite3AffinityString(affinity);
+        keyInfo.aColl[0] = pExpr->pLeft->pColl;
 
         /* Loop through each expression in <exprlist>. */
         for(i=0; i<pExpr->pList->nExpr; i++){
@@ -871,6 +908,8 @@ int sqlite3ExprResolveIds(
           sqlite3VdbeAddOp(v, OP_PutStrKey, pExpr->iTable, 0);
         }
       }
+      sqlite3VdbeChangeP3(v, addr, (void *)&keyInfo, P3_KEYINFO);
+
       break;
     }
 
@@ -1002,8 +1041,9 @@ int sqlite3ExprCheck(Parse *pParse, Expr *pExpr, int allowAgg, int *pIsAgg){
         nErr = sqlite3ExprCheck(pParse, pExpr->pList->a[i].pExpr,
                                allowAgg && !is_agg, pIsAgg);
       }
-      /** TODO:  Compute pExpr->affinity based on the expected return
-      ** type of the function */
+      /* FIX ME:  Compute pExpr->affinity based on the expected return
+      ** type of the function 
+      */
     }
     default: {
       if( pExpr->pLeft ){
@@ -1155,9 +1195,10 @@ void sqlite3ExprCode(Parse *pParse, Expr *pExpr){
     case TK_NE:
     case TK_EQ: {
       int p1 = binaryCompareP1(pExpr->pLeft, pExpr->pRight, 0);
+      CollSeq *p3 = binaryCompareCollSeq(pExpr->pLeft, pExpr->pRight);
       sqlite3ExprCode(pParse, pExpr->pLeft);
       sqlite3ExprCode(pParse, pExpr->pRight);
-      sqlite3VdbeAddOp(v, op, p1, 0);
+      sqlite3VdbeOp3(v, op, p1, 0, (void *)p3, P3_COLLSEQ);
       break;
     }
     case TK_AND:
@@ -1279,13 +1320,19 @@ void sqlite3ExprCode(Parse *pParse, Expr *pExpr){
       break;
     }
     case TK_BETWEEN: {
+      int p1;
+      CollSeq *p3;
       sqlite3ExprCode(pParse, pExpr->pLeft);
       sqlite3VdbeAddOp(v, OP_Dup, 0, 0);
       sqlite3ExprCode(pParse, pExpr->pList->a[0].pExpr);
-      sqlite3VdbeAddOp(v, OP_Ge, 0, 0);
+      p1 = binaryCompareP1(pExpr->pLeft, pExpr->pList->a[0].pExpr, 0);
+      p3 = binaryCompareCollSeq(pExpr->pLeft, pExpr->pList->a[0].pExpr);
+      sqlite3VdbeOp3(v, OP_Ge, p1, 0, (void *)p3, P3_COLLSEQ);
       sqlite3VdbeAddOp(v, OP_Pull, 1, 0);
       sqlite3ExprCode(pParse, pExpr->pList->a[1].pExpr);
-      sqlite3VdbeAddOp(v, OP_Le, 0, 0);
+      p1 = binaryCompareP1(pExpr->pLeft, pExpr->pList->a[1].pExpr, 0);
+      p3 = binaryCompareCollSeq(pExpr->pLeft, pExpr->pList->a[1].pExpr);
+      sqlite3VdbeOp3(v, OP_Le, p1, 0, (void *)p3, P3_COLLSEQ);
       sqlite3VdbeAddOp(v, OP_And, 0, 0);
       break;
     }
@@ -1312,8 +1359,11 @@ void sqlite3ExprCode(Parse *pParse, Expr *pExpr){
       for(i=0; i<nExpr; i=i+2){
         sqlite3ExprCode(pParse, pExpr->pList->a[i].pExpr);
         if( pExpr->pLeft ){
+          int p1 = binaryCompareP1(pExpr->pLeft, pExpr->pList->a[i].pExpr, 1);
+          CollSeq *p3 = binaryCompareCollSeq(pExpr->pLeft, 
+              pExpr->pList->a[i].pExpr);
           sqlite3VdbeAddOp(v, OP_Dup, 1, 1);
-          jumpInst = sqlite3VdbeAddOp(v, OP_Ne, 1, 0);
+          jumpInst = sqlite3VdbeOp3(v, OP_Ne, p1, 0, (void *)p3, P3_COLLSEQ);
           sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
         }else{
           jumpInst = sqlite3VdbeAddOp(v, OP_IfNot, 1, 0);
@@ -1426,9 +1476,10 @@ void sqlite3ExprIfTrue(Parse *pParse, Expr *pExpr, int dest, int jumpIfNull){
     case TK_NE:
     case TK_EQ: {
       int p1 = binaryCompareP1(pExpr->pLeft, pExpr->pRight, jumpIfNull);
+      CollSeq *p3 = binaryCompareCollSeq(pExpr->pLeft, pExpr->pRight);
       sqlite3ExprCode(pParse, pExpr->pLeft);
       sqlite3ExprCode(pParse, pExpr->pRight);
-      sqlite3VdbeAddOp(v, op, p1, dest);
+      sqlite3VdbeOp3(v, op, p1, dest, (void *)p3, P3_COLLSEQ);
       break;
     }
     case TK_ISNULL:
@@ -1438,13 +1489,27 @@ void sqlite3ExprIfTrue(Parse *pParse, Expr *pExpr, int dest, int jumpIfNull){
       break;
     }
     case TK_BETWEEN: {
+      /* The expression "x BETWEEN y AND z" is implemented as:
+      **
+      ** 1 IF (x < y) GOTO 3
+      ** 2 IF (x <= z) GOTO <dest>
+      ** 3 ...
+      */
       int addr;
+      int p1;
+      CollSeq *p3;
       sqlite3ExprCode(pParse, pExpr->pLeft);
       sqlite3VdbeAddOp(v, OP_Dup, 0, 0);
       sqlite3ExprCode(pParse, pExpr->pList->a[0].pExpr);
-      addr = sqlite3VdbeAddOp(v, OP_Lt, !jumpIfNull, 0);
+      p1 = binaryCompareP1(pExpr->pLeft, pExpr->pList->a[0].pExpr, !jumpIfNull);
+      p3 = binaryCompareCollSeq(pExpr->pLeft, pExpr->pList->a[0].pExpr);
+      addr = sqlite3VdbeOp3(v, OP_Lt, p1, 0, (void *)p3, P3_COLLSEQ);
+
       sqlite3ExprCode(pParse, pExpr->pList->a[1].pExpr);
-      sqlite3VdbeAddOp(v, OP_Le, jumpIfNull, dest);
+      p1 = binaryCompareP1(pExpr->pLeft, pExpr->pList->a[1].pExpr, jumpIfNull);
+      p3 = binaryCompareCollSeq(pExpr->pLeft, pExpr->pList->a[1].pExpr);
+      sqlite3VdbeOp3(v, OP_Le, p1, dest, (void *)p3, P3_COLLSEQ);
+
       sqlite3VdbeAddOp(v, OP_Integer, 0, 0);
       sqlite3VdbeChangeP2(v, addr, sqlite3VdbeCurrentAddr(v));
       sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
@@ -1505,9 +1570,10 @@ void sqlite3ExprIfFalse(Parse *pParse, Expr *pExpr, int dest, int jumpIfNull){
     case TK_NE:
     case TK_EQ: {
       int p1 = binaryCompareP1(pExpr->pLeft, pExpr->pRight, jumpIfNull);
+      CollSeq *p3 = binaryCompareCollSeq(pExpr->pLeft, pExpr->pRight);
       sqlite3ExprCode(pParse, pExpr->pLeft);
       sqlite3ExprCode(pParse, pExpr->pRight);
-      sqlite3VdbeAddOp(v, op, p1, dest);
+      sqlite3VdbeOp3(v, op, p1, dest, (void *)p3, P3_COLLSEQ);
       break;
     }
     case TK_ISNULL:
@@ -1516,33 +1582,29 @@ void sqlite3ExprIfFalse(Parse *pParse, Expr *pExpr, int dest, int jumpIfNull){
       sqlite3VdbeAddOp(v, op, 1, dest);
       break;
     }
-#if 0
-    case TK_IN: {
-      int addr;
-      sqlite3ExprCode(pParse, pExpr->pLeft);
-      addr = sqlite3VdbeCurrentAddr(v);
-      sqlite3VdbeAddOp(v, OP_NotNull, -1, addr+3);
-      sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
-      sqlite3VdbeAddOp(v, OP_Goto, 0, jumpIfNull ? dest : addr+4);
-      if( pExpr->pSelect ){
-        sqlite3VdbeAddOp(v, OP_NotFound, pExpr->iTable, dest);
-      }else{
-        sqlite3VdbeAddOp(v, OP_SetNotFound, pExpr->iTable, dest);
-      }
-      break;
-    }
-#endif
     case TK_BETWEEN: {
+      /* The expression is "x BETWEEN y AND z". It is implemented as:
+      **
+      ** 1 IF (x >= y) GOTO 3
+      ** 2 GOTO <dest>
+      ** 3 IF (x > z) GOTO <dest>
+      */
       int addr;
+      int p1;
+      CollSeq *p3;
       sqlite3ExprCode(pParse, pExpr->pLeft);
       sqlite3VdbeAddOp(v, OP_Dup, 0, 0);
       sqlite3ExprCode(pParse, pExpr->pList->a[0].pExpr);
       addr = sqlite3VdbeCurrentAddr(v);
-      sqlite3VdbeAddOp(v, OP_Ge, !jumpIfNull, addr+3);
+      p1 = binaryCompareP1(pExpr->pLeft, pExpr->pList->a[0].pExpr, !jumpIfNull);
+      p3 = binaryCompareCollSeq(pExpr->pLeft, pExpr->pList->a[0].pExpr);
+      sqlite3VdbeOp3(v, OP_Ge, p1, addr+3, (void *)p3, P3_COLLSEQ);
       sqlite3VdbeAddOp(v, OP_Pop, 1, 0);
       sqlite3VdbeAddOp(v, OP_Goto, 0, dest);
       sqlite3ExprCode(pParse, pExpr->pList->a[1].pExpr);
-      sqlite3VdbeAddOp(v, OP_Gt, jumpIfNull, dest);
+      p1 = binaryCompareP1(pExpr->pLeft, pExpr->pList->a[1].pExpr, jumpIfNull);
+      p3 = binaryCompareCollSeq(pExpr->pLeft, pExpr->pList->a[1].pExpr);
+      sqlite3VdbeOp3(v, OP_Gt, p1, dest, (void *)p3, P3_COLLSEQ);
       break;
     }
     default: {
diff --git a/src/main.c b/src/main.c
index e2fc54cda..81731022f 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.207 2004/06/08 00:02:34 danielk1977 Exp $
+** $Id: main.c,v 1.208 2004/06/09 09:55:18 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 #include "os.h"
@@ -425,6 +425,23 @@ static int binaryCollatingFunc(
 }
 
 /*
+** Another built-in collating sequence: NOCASE. At the moment there is
+** only a UTF-8 implementation.
+*/
+static int nocaseCollatingFunc(
+  void *NotUsed,
+  int nKey1, const void *pKey1,
+  int nKey2, const void *pKey2
+){
+  int r = sqlite3StrNICmp(
+      (const char *)pKey1, (const char *)pKey2, (nKey1>nKey2)?nKey1:nKey2);
+  if( 0==r ){
+    r = nKey1-nKey2;
+  }
+  return r;
+}
+
+/*
 ** Return the ROWID of the most recent insert
 */
 long long int sqlite3_last_insert_rowid(sqlite *db){
@@ -1001,9 +1018,24 @@ static int openDatabase(
     sqlite3HashInit(&db->aDb[i].trigHash, SQLITE_HASH_STRING, 0);
     sqlite3HashInit(&db->aDb[i].aFKey, SQLITE_HASH_STRING, 1);
   }
-  db->pDfltColl =
-     sqlite3ChangeCollatingFunction(db, "BINARY", 6, 0, binaryCollatingFunc);
   
+  /* Add the default collation sequence BINARY. BINARY works for both UTF-8
+  ** and UTF-16, so add a version for each to avoid any unnecessary
+  ** conversions. The only error that can occur here is a malloc() failure.
+  */
+  sqlite3_create_collation(db, "BINARY", 0, 0, binaryCollatingFunc);
+  sqlite3_create_collation(db, "BINARY", 1, 0, binaryCollatingFunc);
+  db->pDfltColl = sqlite3FindCollSeq(db, "BINARY", 6, 0);
+  if( !db->pDfltColl ){
+    rc = db->errCode;
+    assert( rc!=SQLITE_OK );
+    db->magic = SQLITE_MAGIC_CLOSED;
+    goto opendb_out;
+  }
+
+  /* Also add a UTF-8 case-insensitive collation sequence. */
+  sqlite3_create_collation(db, "NOCASE", 0, 0, nocaseCollatingFunc);
+
   /* Open the backend database driver */
   if( zFilename[0]==':' && strcmp(zFilename,":memory:")==0 ){
     db->temp_store = 2;
@@ -1098,3 +1130,41 @@ int sqlite3_reset(sqlite3_stmt *pStmt){
   sqlite3VdbeMakeReady((Vdbe*)pStmt, -1, 0);
   return rc;
 }
+
+int sqlite3_create_collation(
+  sqlite3* db, 
+  const char *zName, 
+  int pref16, 
+  void* pCtx,
+  int(*xCompare)(void*,int,const void*,int,const void*)
+){
+  CollSeq *pColl;
+  int rc = SQLITE_OK;
+  pColl = sqlite3FindCollSeq(db, zName, strlen(zName), 1);
+  if( 0==pColl ){
+   rc = SQLITE_NOMEM;
+  }else if( pref16 ){
+    pColl->xCmp16 = xCompare;
+    pColl->pUser16 = pCtx;
+  }else{
+    pColl->xCmp = xCompare;
+    pColl->pUser = pCtx;
+  }
+  sqlite3Error(db, rc, 0);
+  return SQLITE_OK;
+}
+
+int sqlite3_create_collation16(
+  sqlite3* db, 
+  const char *zName, 
+  int pref16, 
+  void* pCtx,
+  int(*xCompare)(void*,int,const void*,int,const void*)
+){
+  int rc;
+  char *zName8 = sqlite3utf16to8(zName, -1, SQLITE_BIGENDIAN);
+  rc = sqlite3_create_collation(db, zName8, pref16, pCtx, xCompare);
+  sqliteFree(zName8);
+  return rc;
+}
+
diff --git a/src/parse.y b/src/parse.y
index 246cc8928..5e0e1cc84 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.126 2004/06/09 00:48:13 drh Exp $
+** @(#) $Id: parse.y,v 1.127 2004/06/09 09:55:18 danielk1977 Exp $
 */
 %token_prefix TK_
 %token_type {Token}
@@ -423,7 +423,7 @@ on_opt(N) ::= .             {N = 0;}
 
 %type using_opt {IdList*}
 %destructor using_opt {sqlite3IdListDelete($$);}
-using_opt(U) ::= USING LP idxlist(L) RP.  {U = L;}
+using_opt(U) ::= USING LP inscollist(L) RP.  {U = L;}
 using_opt(U) ::= .                        {U = 0;}
 
 
@@ -741,17 +741,32 @@ cmd ::= CREATE(S) uniqueflag(U) INDEX nm(X) dbnm(D)
 uniqueflag(A) ::= UNIQUE.  { A = OE_Abort; }
 uniqueflag(A) ::= .        { A = OE_None; }
 
-%type idxlist {IdList*}
-%destructor idxlist {sqlite3IdListDelete($$);}
-%type idxlist_opt {IdList*}
-%destructor idxlist_opt {sqlite3IdListDelete($$);}
+%type idxlist {ExprList*}
+%destructor idxlist {sqlite3ExprListDelete($$);}
+%type idxlist_opt {ExprList*}
+%destructor idxlist_opt {sqlite3ExprListDelete($$);}
 %type idxitem {Token}
 
 idxlist_opt(A) ::= .                         {A = 0;}
 idxlist_opt(A) ::= LP idxlist(X) RP.         {A = X;}
-idxlist(A) ::= idxlist(X) COMMA idxitem(Y).  {A = sqlite3IdListAppend(X,&Y);}
-idxlist(A) ::= idxitem(Y).                   {A = sqlite3IdListAppend(0,&Y);}
-idxitem(A) ::= nm(X) sortorder.              {A = X;}
+idxlist(A) ::= idxlist(X) COMMA idxitem(Y) collate(C) sortorder.  {
+  Expr *p = 0;
+  if( C.n>0 ){
+    p = sqlite3Expr(TK_COLUMN, 0, 0, 0);
+    if( p ) p->pColl = sqlite3LocateCollSeq(pParse, C.z, C.n);
+  }
+  A = sqlite3ExprListAppend(X, p, &Y);
+}
+idxlist(A) ::= idxitem(Y) collate(C) sortorder. {
+  Expr *p = 0;
+  if( C.n>0 ){
+    p = sqlite3Expr(TK_COLUMN, 0, 0, 0);
+    if( p ) p->pColl = sqlite3LocateCollSeq(pParse, C.z, C.n);
+  }
+  A = sqlite3ExprListAppend(0, p, &Y);
+}
+idxitem(A) ::= nm(X).              {A = X;}
+
 
 ///////////////////////////// The DROP INDEX command /////////////////////////
 //
diff --git a/src/select.c b/src/select.c
index 083f19782..d868a85bb 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.184 2004/06/07 10:00:31 danielk1977 Exp $
+** $Id: select.c,v 1.185 2004/06/09 09:55:18 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 
@@ -546,7 +546,14 @@ static void generateSortTail(
   pInfo->aSortOrder = (char*)&pInfo->aColl[nCol];
   pInfo->nField = nCol;
   for(i=0; i<nCol; i++){
-    pInfo->aColl[i] = db->pDfltColl;
+    /* If a collation sequence was specified explicity, then it
+    ** is stored in pOrderBy->a[i].zName. Otherwise, use the default
+    ** collation type for the expression.
+    */
+    pInfo->aColl[i] = sqlite3ExprCollSeq(pOrderBy->a[i].pExpr);
+    if( !pInfo->aColl[i] ){
+      pInfo->aColl[i] = db->pDfltColl;
+    }
     pInfo->aSortOrder[i] = pOrderBy->a[i].sortOrder;
   }
   sqlite3VdbeOp3(v, OP_Sort, 0, 0, (char*)pInfo, P3_KEYINFO_HANDOFF);
@@ -818,6 +825,10 @@ Table *sqlite3ResultSetOfSelect(Parse *pParse, char *zTabName, Select *pSelect){
     if( zType ){
       pTab->aCol[i].affinity = sqlite3AffinityType(zType, strlen(zType));
     }
+    pTab->aCol[i].pColl = sqlite3ExprCollSeq(p);
+    if( !pTab->aCol[i].pColl ){
+      pTab->aCol[i].pColl = pParse->db->pDfltColl;
+    }
   }
   pTab->iPKey = -1;
   return pTab;
@@ -2222,6 +2233,21 @@ int sqlite3Select(
     }
   }
 
+  /* If there is an ORDER BY clause, resolve any collation sequences
+  ** names that have been explicitly specified.
+  */
+  if( pOrderBy ){
+    for(i=0; i<pOrderBy->nExpr; i++){
+      if( pOrderBy->a[i].zName ){
+        pOrderBy->a[i].pExpr->pColl = 
+            sqlite3LocateCollSeq(pParse, pOrderBy->a[i].zName, -1);
+      }
+    }
+    if( pParse->nErr ){
+      goto select_end;
+    }
+  }
+
   /* Begin generating code.
   */
   v = sqlite3GetVdbe(pParse);
diff --git a/src/sqlite.h.in b/src/sqlite.h.in
index 5a7a809de..296ae9744 100644
--- a/src/sqlite.h.in
+++ b/src/sqlite.h.in
@@ -12,7 +12,7 @@
 ** This header file defines the interface that the SQLite library
 ** presents to client programs.
 **
-** @(#) $Id: sqlite.h.in,v 1.94 2004/06/08 00:02:35 danielk1977 Exp $
+** @(#) $Id: sqlite.h.in,v 1.95 2004/06/09 09:55:18 danielk1977 Exp $
 */
 #ifndef _SQLITE_H_
 #define _SQLITE_H_
@@ -963,6 +963,22 @@ void sqlite3_result_text(sqlite3_context*, const char*, int n, int eCopy);
 void sqlite3_result_text16(sqlite3_context*, const void*, int n, int eCopy);
 void sqlite3_result_value(sqlite3_context*, sqlite3_value*);
 
+int sqlite3_create_collation(
+  sqlite3*, 
+  const char *zName, 
+  int pref16, 
+  void*,
+  int(*xCompare)(void*,int,const void*,int,const void*)
+);
+int sqlite3_create_collation16(
+  sqlite3*, 
+  const char *zName, 
+  int pref16, 
+  void*,
+  int(*xCompare)(void*,int,const void*,int,const void*)
+);
+
+
 #ifdef __cplusplus
 }  /* End of the 'extern "C"' block */
 #endif
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index c738b4363..d7dbe2026 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -11,7 +11,7 @@
 *************************************************************************
 ** Internal interface definitions for SQLite.
 **
-** @(#) $Id: sqliteInt.h,v 1.272 2004/06/09 00:48:13 drh Exp $
+** @(#) $Id: sqliteInt.h,v 1.273 2004/06/09 09:55:19 danielk1977 Exp $
 */
 #include "config.h"
 #include "sqlite3.h"
@@ -488,19 +488,31 @@ struct Column {
 
 /*
 ** A "Collating Sequence" is defined by an instance of the following
-** structure.  Every collating sequence has a name and a comparison
-** function that defines the order of text for that sequence.  The
-** CollSeq.pUser parameter is an extra parameter that passed in as
-** the first argument to the comparison function.
+** structure. Conceptually, a collating sequence consists of a name and
+** a comparison routine that defines the order of that sequence.
 **
-** If CollSeq.xCmp is NULL, it means that the collating sequence is
-** undefined.  Indices built on an undefined collating sequence may
-** not be read or written.
+** There may two seperate implementations of the collation function, one
+** that processes text in UTF-8 encoding (CollSeq.xCmp) and another that
+** processes text encoded in UTF-16 (CollSeq.xCmp16), using the machine
+** native byte order. When a collation sequence is invoked, SQLite selects
+** the version that will require the least expensive encoding
+** transalations, if any.
+**
+** The CollSeq.pUser member variable is an extra parameter that passed in
+** as the first argument to the UTF-8 comparison function, xCmp.
+** CollSeq.pUser16 is the equivalent for the UTF-16 comparison function,
+** xCmp16.
+**
+** If both CollSeq.xCmp and CollSeq.xCmp16 are NULL, it means that the
+** collating sequence is undefined.  Indices built on an undefined
+** collating sequence may not be read or written.
 */
 struct CollSeq {
-  char *zName;         /* Name of the collating sequence */
+  char *zName;         /* Name of the collating sequence, UTF-8 encoded */
   void *pUser;         /* First argument to xCmp() */
-  int (*xCmp)(void*,int,const void*,int,const void*); /* Comparison function */
+  void *pUser16;       /* First argument to xCmp16() */
+  int (*xCmp)(void*,int, const void*, int, const void*);
+  int (*xCmp16)(void*,int, const void*, int, const void*);
 };
 
 /*
@@ -756,6 +768,7 @@ struct Token {
 struct Expr {
   u8 op;                 /* Operation performed by this node */
   char affinity;         /* The affinity of the column or 0 if not a column */
+  CollSeq *pColl;        /* The collation type of the column or 0 */
   u8 iDb;                /* Database referenced by this expression */
   u8 flags;              /* Various flags.  See below */
   Expr *pLeft, *pRight;  /* Left and right subnodes */
@@ -1224,12 +1237,10 @@ void sqlite3OpenMasterTable(Vdbe *v, int);
 void sqlite3StartTable(Parse*,Token*,Token*,Token*,int,int);
 void sqlite3AddColumn(Parse*,Token*);
 void sqlite3AddNotNull(Parse*, int);
-void sqlite3AddPrimaryKey(Parse*, IdList*, int);
+void sqlite3AddPrimaryKey(Parse*, ExprList*, int);
 void sqlite3AddColumnType(Parse*,Token*,Token*);
 void sqlite3AddDefaultValue(Parse*,Token*,int);
 void sqlite3AddCollateType(Parse*, const char*, int);
-CollSeq *sqlite3ChangeCollatingFunction(sqlite*,const char*,int,
-                  void*, int(*)(void*,int,const void*,int,const void*));
 void sqlite3EndTable(Parse*,Token*,Select*);
 void sqlite3CreateView(Parse*,Token*,Token*,Token*,Select*,int);
 int sqlite3ViewGetColumnNames(Parse*,Table*);
@@ -1243,7 +1254,7 @@ void sqlite3SrcListAddAlias(SrcList*, Token*);
 void sqlite3SrcListAssignCursors(Parse*, SrcList*);
 void sqlite3IdListDelete(IdList*);
 void sqlite3SrcListDelete(SrcList*);
-void sqlite3CreateIndex(Parse*,Token*,Token*,SrcList*,IdList*,int,Token*,
+void sqlite3CreateIndex(Parse*,Token*,Token*,SrcList*,ExprList*,int,Token*,
                         Token*);
 void sqlite3DropIndex(Parse*, SrcList*);
 void sqlite3AddKeyType(Vdbe*, ExprList*);
@@ -1324,7 +1335,7 @@ TriggerStep *sqlite3TriggerUpdateStep(Token*, ExprList*, Expr*, int);
 TriggerStep *sqlite3TriggerDeleteStep(Token*, Expr*);
 void sqlite3DeleteTrigger(Trigger*);
 int sqlite3JoinType(Parse*, Token*, Token*, Token*);
-void sqlite3CreateForeignKey(Parse*, IdList*, Token*, IdList*, int);
+void sqlite3CreateForeignKey(Parse*, ExprList*, Token*, ExprList*, int);
 void sqlite3DeferForeignKey(Parse*, int);
 #ifndef SQLITE_OMIT_AUTHORIZATION
   void sqlite3AuthRead(Parse*,Expr*,SrcList*);
@@ -1379,3 +1390,6 @@ int sqlite3TwoPartName(Parse *, Token *, Token *, Token **);
 const char *sqlite3ErrStr(int);
 int sqlite3ReadUniChar(const char *zStr, int *pOffset, u8 *pEnc, int fold);
 int sqlite3ReadSchema(sqlite *db);
+CollSeq *sqlite3FindCollSeq(sqlite *,const char *,int,int);
+CollSeq *sqlite3LocateCollSeq(Parse *pParse, const char *zName, int nName);
+CollSeq *sqlite3ExprCollSeq(Expr *pExpr);
diff --git a/src/tclsqlite.c b/src/tclsqlite.c
index d9c46f2d1..f0aad5f63 100644
--- a/src/tclsqlite.c
+++ b/src/tclsqlite.c
@@ -11,7 +11,7 @@
 *************************************************************************
 ** A TCL Interface to SQLite
 **
-** $Id: tclsqlite.c,v 1.80 2004/06/08 00:02:35 danielk1977 Exp $
+** $Id: tclsqlite.c,v 1.81 2004/06/09 09:55:19 danielk1977 Exp $
 */
 #ifndef NO_TCL     /* Omit this whole file if TCL is unavailable */
 
@@ -43,6 +43,17 @@ struct SqlFunc {
 };
 
 /*
+** New collation sequences function can be created as TCL scripts.  Each such
+** function is described by an instance of the following structure.
+*/
+typedef struct SqlCollate SqlCollate;
+struct SqlCollate {
+  Tcl_Interp *interp;   /* The TCL interpret to execute the function */
+  char *zScript;        /* The script to be run */
+  SqlCollate *pNext;       /* Next function on the list of them all */
+};
+
+/*
 ** There is one instance of this structure for each SQLite database
 ** that has been opened by the SQLite TCL interface.
 */
@@ -56,6 +67,7 @@ struct SqliteDb {
   char *zProgress;      /* The progress callback routine */
   char *zAuth;          /* The authorization callback routine */
   SqlFunc *pFunc;       /* List of SQL functions */
+  SqlCollate *pCollate; /* List of SQL collation functions */
   int rc;               /* Return code of most recent sqlite3_exec() */
   int nChange;         /* Database changes for the most recent eval */
 };
@@ -115,6 +127,11 @@ static void DbDeleteCmd(void *db){
     pDb->pFunc = pFunc->pNext;
     Tcl_Free((char*)pFunc);
   }
+  while( pDb->pCollate ){
+    SqlCollate *pCollate = pDb->pCollate;
+    pDb->pCollate = pCollate->pNext;
+    Tcl_Free((char*)pCollate);
+  }
   if( pDb->zBusy ){
     Tcl_Free(pDb->zBusy);
   }
@@ -201,6 +218,29 @@ static int DbCommitHandler(void *cd){
 }
 
 /*
+** This routine is called to evaluate an SQL collation function implemented
+** using TCL script.
+*/
+static int tclSqlCollate(
+  void *pCtx,
+  int nA,
+  const void *zA,
+  int nB,
+  const void *zB
+){
+  SqlCollate *p = (SqlCollate *)pCtx;
+  Tcl_Obj *pCmd;
+
+  pCmd = Tcl_NewStringObj(p->zScript, -1);
+  Tcl_IncrRefCount(pCmd);
+  Tcl_ListObjAppendElement(p->interp, pCmd, Tcl_NewStringObj(zA, nA));
+  Tcl_ListObjAppendElement(p->interp, pCmd, Tcl_NewStringObj(zB, nB));
+  Tcl_EvalObjEx(p->interp, pCmd, 0);
+  Tcl_DecrRefCount(pCmd);
+  return (atoi(Tcl_GetStringResult(p->interp)));
+}
+
+/*
 ** This routine is called to evaluate an SQL function implemented
 ** using TCL script.
 */
@@ -342,7 +382,7 @@ static int DbObjCmd(void *cd, Tcl_Interp *interp, int objc,Tcl_Obj *const*objv){
     "errorcode",          "eval",                   "function",
     "last_insert_rowid",  "last_statement_changes", "onecolumn",
     "progress",           "rekey",                  "timeout",
-    "trace",
+    "trace",              "collate",
     0                    
   };
   enum DB_enum {
@@ -351,7 +391,7 @@ static int DbObjCmd(void *cd, Tcl_Interp *interp, int objc,Tcl_Obj *const*objv){
     DB_ERRORCODE,         DB_EVAL,                   DB_FUNCTION,
     DB_LAST_INSERT_ROWID, DB_LAST_STATEMENT_CHANGES, DB_ONECOLUMN,        
     DB_PROGRESS,          DB_REKEY,                  DB_TIMEOUT,
-    DB_TRACE
+    DB_TRACE,             DB_COLLATE
   };
 
   if( objc<2 ){
@@ -854,6 +894,35 @@ static int DbObjCmd(void *cd, Tcl_Interp *interp, int objc,Tcl_Obj *const*objv){
     break;
   }
 
+  /*
+  **     $db collate NAME SCRIPT
+  **
+  ** Create a new SQL collation function called NAME.  Whenever
+  ** that function is called, invoke SCRIPT to evaluate the function.
+  */
+  case DB_COLLATE: {
+    SqlCollate *pCollate;
+    char *zName;
+    char *zScript;
+    int nScript;
+    if( objc!=4 ){
+      Tcl_WrongNumArgs(interp, 2, objv, "NAME SCRIPT");
+      return TCL_ERROR;
+    }
+    zName = Tcl_GetStringFromObj(objv[2], 0);
+    zScript = Tcl_GetStringFromObj(objv[3], &nScript);
+    pCollate = (SqlCollate*)Tcl_Alloc( sizeof(*pCollate) + nScript + 1 );
+    if( pCollate==0 ) return TCL_ERROR;
+    pCollate->interp = interp;
+    pCollate->pNext = pDb->pCollate;
+    pCollate->zScript = (char*)&pCollate[1];
+    strcpy(pCollate->zScript, zScript);
+    if( sqlite3_create_collation(pDb->db, zName, 0, pCollate, tclSqlCollate) ){
+      return TCL_ERROR;
+    }
+    break;
+  }
+
   } /* End of the SWITCH statement */
   return rc;
 }
diff --git a/src/test1.c b/src/test1.c
index 77db0444f..2a7d2ee7d 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.71 2004/06/08 00:02:35 danielk1977 Exp $
+** $Id: test1.c,v 1.72 2004/06/09 09:55:19 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 #include "tcl.h"
@@ -1551,47 +1551,6 @@ static int test_data_count(
 }
 
 /*
-** This is a collating function named "REVERSE" which sorts text
-** in reverse order.
-*/
-static int reverseCollatingFunc(
-  void *NotUsed,
-  int nKey1, const void *pKey1,
-  int nKey2, const void *pKey2
-){
-  int rc, n;
-  n = nKey1<nKey2 ? nKey1 : nKey2;
-  rc = memcmp(pKey1, pKey2, n);
-  if( rc==0 ){
-    rc = nKey1 - nKey2;
-  }
-  return -rc;
-}
-
-/*
-** Usage: add_reverse_collating_func DB 
-**
-** This routine adds a collation named "REVERSE" to database given.
-** REVERSE is used for testing only.
-*/
-static int reverse_collfunc(
-  void * clientData,
-  Tcl_Interp *interp,
-  int objc,
-  Tcl_Obj *CONST objv[]
-){
-  sqlite3 *db;
-
-  if( objc!=2 ){
-    Tcl_WrongNumArgs(interp, 1, objv, "DB");
-    return TCL_ERROR;
-  }
-  if( getDbPointer(interp, Tcl_GetString(objv[1]), &db) ) return TCL_ERROR;
-  sqlite3ChangeCollatingFunction(db, "REVERSE", 7, 0, reverseCollatingFunc);
-  return TCL_OK;
-}
-
-/*
 ** Usage: sqlite3_column_text STMT column
 **
 ** Usage: sqlite3_column_decltype STMT column
@@ -1880,7 +1839,6 @@ int Sqlitetest1_Init(Tcl_Interp *interp){
      { "sqlite3_errmsg16",              test_errmsg16      ,0 },
      { "sqlite3_open",                  test_open          ,0 },
      { "sqlite3_open16",                test_open16        ,0 },
-     { "add_reverse_collating_func",    reverse_collfunc   ,0 },
 
      { "sqlite3_prepare",               test_prepare       ,0 },
      { "sqlite3_prepare16",             test_prepare16     ,0 },
diff --git a/src/test5.c b/src/test5.c
index ff3fa6f55..ec1ea0ddb 100644
--- a/src/test5.c
+++ b/src/test5.c
@@ -15,9 +15,10 @@
 ** is used for testing the SQLite routines for converting between
 ** the various supported unicode encodings.
 **
-** $Id: test5.c,v 1.8 2004/06/04 06:22:02 danielk1977 Exp $
+** $Id: test5.c,v 1.9 2004/06/09 09:55:19 danielk1977 Exp $
 */
 #include "sqliteInt.h"
+#include "vdbeInt.h"
 #include "os.h"         /* to get SQLITE_BIGENDIAN */
 #include "tcl.h"
 #include <stdlib.h>
@@ -234,6 +235,52 @@ static int binarize(
   return TCL_OK;
 }
 
+/*
+** Usage: test_value_overhead <repeat-count> <do-calls>.
+**
+** This routine is used to test the overhead of calls to
+** sqlite3_value_text(), on a value that contains a UTF-8 string. The idea
+** is to figure out whether or not it is a problem to use sqlite3_value
+** structures with collation sequence functions.
+**
+** If <do-calls> is 0, then the calls to sqlite3_value_text() are not
+** actually made.
+*/
+static int test_value_overhead(
+  void * clientData,
+  Tcl_Interp *interp,
+  int objc,
+  Tcl_Obj *CONST objv[]
+){
+  int do_calls;
+  int repeat_count;
+  int i;
+  Mem val;
+  const char *zVal;
+
+  if( objc!=3 ){
+    Tcl_AppendResult(interp, "wrong # args: should be \"",
+        Tcl_GetStringFromObj(objv[0], 0), " <repeat-count> <do-calls>", 0);
+    return TCL_ERROR;
+  }
+
+  if( Tcl_GetIntFromObj(interp, objv[1], &repeat_count) ) return TCL_ERROR;
+  if( Tcl_GetIntFromObj(interp, objv[2], &do_calls) ) return TCL_ERROR;
+
+  val.flags = MEM_Str|MEM_Term|MEM_Static;
+  val.z = "hello world";
+  val.type = SQLITE_TEXT;
+  val.enc = TEXT_Utf8;
+
+  for(i=0; i<repeat_count; i++){
+    if( do_calls ){
+      zVal = sqlite3_value_text(&val);
+    }
+  }
+
+  return TCL_OK;
+}
+
 
 /*
 ** Register commands with the TCL interpreter.
@@ -249,11 +296,12 @@ int Sqlitetest5_Init(Tcl_Interp *interp){
     { "sqlite_utf16to16le",      (Tcl_ObjCmdProc*)sqlite_utf16to16le },
     { "sqlite_utf16to16be",      (Tcl_ObjCmdProc*)sqlite_utf16to16be },
     { "binarize",                (Tcl_ObjCmdProc*)binarize },
+    { "test_value_overhead",     (Tcl_ObjCmdProc*)test_value_overhead },
   };
   int i;
   for(i=0; i<sizeof(aCmd)/sizeof(aCmd[0]); i++){
     Tcl_CreateObjCommand(interp, aCmd[i].zName, aCmd[i].xProc, 0, 0);
   }
-
-  return TCL_OK;
+  return SQLITE_OK;
 }
+
diff --git a/src/util.c b/src/util.c
index bdfe54aa6..c79342bbd 100644
--- a/src/util.c
+++ b/src/util.c
@@ -14,7 +14,7 @@
 ** This file contains functions for allocating memory, comparing
 ** strings, and stuff like that.
 **
-** $Id: util.c,v 1.98 2004/06/06 12:41:50 danielk1977 Exp $
+** $Id: util.c,v 1.99 2004/06/09 09:55:19 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 #include <stdarg.h>
@@ -553,7 +553,7 @@ int sqlite3StrNICmp(const char *zLeft, const char *zRight, int N){
   a = (unsigned char *)zLeft;
   b = (unsigned char *)zRight;
   while( N-- > 0 && *a!=0 && UpperToLower[*a]==UpperToLower[*b]){ a++; b++; }
-  return N<0 ? 0 : *a - *b;
+  return N<0 ? 0 : UpperToLower[*a] - UpperToLower[*b];
 }
 
 /*
diff --git a/src/vdbe.c b/src/vdbe.c
index e82a9852d..1390e6d30 100644
--- a/src/vdbe.c
+++ b/src/vdbe.c
@@ -43,7 +43,7 @@
 ** in this file for details.  If in doubt, do not deviate from existing
 ** commenting and indentation practices when changing or adding code.
 **
-** $Id: vdbe.c,v 1.360 2004/06/09 00:48:14 drh Exp $
+** $Id: vdbe.c,v 1.361 2004/06/09 09:55:19 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 #include "os.h"
@@ -1510,25 +1510,25 @@ mismatch:
 /* Opcode: Lt P1 P2 P3
 **
 ** This works just like the Eq opcode except that the jump is taken if
-** the 2nd element down on the task is less than the top of the stack.
+** the 2nd element down on the stack is less than the top of the stack.
 ** See the Eq opcode for additional information.
 */
 /* Opcode: Le P1 P2 P3
 **
 ** This works just like the Eq opcode except that the jump is taken if
-** the 2nd element down on the task is less than or equal to the
+** the 2nd element down on the stack is less than or equal to the
 ** top of the stack.  See the Eq opcode for additional information.
 */
 /* Opcode: Gt P1 P2 P3
 **
 ** This works just like the Eq opcode except that the jump is taken if
-** the 2nd element down on the task is greater than the top of the stack.
+** the 2nd element down on the stack is greater than the top of the stack.
 ** See the Eq opcode for additional information.
 */
 /* Opcode: Ge P1 P2 P3
 **
 ** This works just like the Eq opcode except that the jump is taken if
-** the 2nd element down on the task is greater than or equal to the
+** the 2nd element down on the stack is greater than or equal to the
 ** top of the stack.  See the Eq opcode for additional information.
 */
 case OP_Eq:
diff --git a/src/vdbeaux.c b/src/vdbeaux.c
index a168e4908..ef2ce4fb7 100644
--- a/src/vdbeaux.c
+++ b/src/vdbeaux.c
@@ -1256,7 +1256,7 @@ void sqlite3VdbeDelete(Vdbe *p){
       int j;
       VdbeFunc *pVdbeFunc = (VdbeFunc *)pOp->p3;
       for(j=0; j<pVdbeFunc->nAux; j++){
-        struct AuxData *pAuxData = &pVdbeFunc->apAux[j].pAux;
+        struct AuxData *pAuxData = &pVdbeFunc->apAux[j];
         if( pAuxData->pAux && pAuxData->xDelete ){
           pAuxData->xDelete(pAuxData->pAux);
         }
@@ -1520,6 +1520,11 @@ int sqlite3VdbeRecordCompare(
   int rc = 0;
   const unsigned char *aKey1 = (const unsigned char *)pKey1;
   const unsigned char *aKey2 = (const unsigned char *)pKey2;
+
+  Mem mem1;
+  Mem mem2;
+  mem1.enc = pKeyInfo->enc;
+  mem2.enc = pKeyInfo->enc;
   
   idx1 = sqlite3GetVarint32(pKey1, &szHdr1);
   d1 = szHdr1;
@@ -1527,8 +1532,6 @@ int sqlite3VdbeRecordCompare(
   d2 = szHdr2;
   nField = pKeyInfo->nField;
   while( idx1<szHdr1 && idx2<szHdr2 ){
-    Mem mem1;
-    Mem mem2;
     u32 serial_type1;
     u32 serial_type2;
 
diff --git a/src/vdbemem.c b/src/vdbemem.c
index eaa3b7d59..a8194a0aa 100644
--- a/src/vdbemem.c
+++ b/src/vdbemem.c
@@ -427,12 +427,41 @@ int sqlite3MemCompare(const Mem *pMem1, const Mem *pMem2, const CollSeq *pColl){
     if( (f2 & MEM_Str)==0 ){
       return -1;
     }
-    if( pColl && pColl->xCmp ){
-      return pColl->xCmp(pColl->pUser, pMem1->n, pMem1->z, pMem2->n, pMem2->z);
-    }else{
-      /* If no collating sequence is defined, fall through into the
-      ** blob case below and use memcmp() for the comparison. */
+
+    assert( pMem1->enc==pMem2->enc );
+    assert( pMem1->enc==TEXT_Utf8 || 
+            pMem1->enc==TEXT_Utf16le || pMem1->enc==TEXT_Utf16be );
+
+    /* FIX ME: This may fail if the collation sequence is deleted after
+    ** this vdbe program is compiled. We cannot just use BINARY in this
+    ** case as this may lead to a segfault caused by traversing an index
+    ** table incorrectly.  We need to return an error to the user in this
+    ** case.
+    */
+    assert( !pColl || (pColl->xCmp || pColl->xCmp16) );
+
+    if( pColl ){
+      if( (pMem1->enc==TEXT_Utf8 && pColl->xCmp) || !pColl->xCmp16 ){
+        return pColl->xCmp(
+          pColl->pUser,
+          sqlite3_value_bytes((sqlite3_value *)pMem1),
+          sqlite3_value_text((sqlite3_value *)pMem1),
+          sqlite3_value_bytes((sqlite3_value *)pMem2),
+          sqlite3_value_text((sqlite3_value *)pMem2)
+        );
+      }else{
+        return pColl->xCmp16(
+          pColl->pUser,
+          sqlite3_value_bytes16((sqlite3_value *)pMem1),
+          sqlite3_value_text16((sqlite3_value *)pMem1),
+          sqlite3_value_bytes16((sqlite3_value *)pMem2),
+          sqlite3_value_text16((sqlite3_value *)pMem2)
+        );
+      }
     }
+    /* If a NULL pointer was passed as the collate function, fall through
+    ** to the blob case and use memcmp().
+    */
   }
  
   /* Both values must be blobs.  Compare using memcmp().
diff --git a/src/where.c b/src/where.c
index 50733486e..7d33af48a 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.102 2004/06/09 00:48:15 drh Exp $
+** $Id: where.c,v 1.103 2004/06/09 09:55:20 danielk1977 Exp $
 */
 #include "sqliteInt.h"
 
@@ -208,6 +208,7 @@ static void exprAnalyze(ExprMaskSet *pMaskSet, ExprInfo *pInfo){
 ** set to 0 if the ORDER BY clause is all ASC.
 */
 static Index *findSortingIndex(
+  sqlite *db,
   Table *pTab,            /* The table to be sorted */
   int base,               /* Cursor number for pTab */
   ExprList *pOrderBy,     /* The ORDER BY clause */
@@ -230,10 +231,6 @@ static Index *findSortingIndex(
       ** DESC or ASC.  Indices cannot be used on a mixture. */
       return 0;
     }
-    if( pOrderBy->a[i].zName!=0 ){
-      /* Do not sort by index if there is a COLLATE clause */
-      return 0;
-    }
     p = pOrderBy->a[i].pExpr;
     if( p->op!=TK_COLUMN || p->iTable!=base ){
       /* Can not use an index sort on anything that is not a column in the
@@ -241,7 +238,7 @@ static Index *findSortingIndex(
       return 0;
     }
   }
-  
+
   /* 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.
@@ -251,12 +248,23 @@ static Index *findSortingIndex(
     int nExpr = pOrderBy->nExpr;
     if( pIdx->nColumn < nEqCol || pIdx->nColumn < nExpr ) continue;
     for(i=j=0; i<nEqCol; i++){
+      CollSeq *pColl = sqlite3ExprCollSeq(pOrderBy->a[j].pExpr);
+      if( !pColl ) pColl = db->pDfltColl;
       if( pPreferredIdx->aiColumn[i]!=pIdx->aiColumn[i] ) break;
-      if( j<nExpr && pOrderBy->a[j].pExpr->iColumn==pIdx->aiColumn[i] ){ j++; }
+      if( pPreferredIdx->keyInfo.aColl[i]!=pIdx->keyInfo.aColl[i] ) break;
+      if( j<nExpr && 
+          pOrderBy->a[j].pExpr->iColumn==pIdx->aiColumn[i] &&
+          pColl==pIdx->keyInfo.aColl[i]
+      ){ 
+        j++; 
+      }
     }
     if( i<nEqCol ) continue;
     for(i=0; i+j<nExpr; i++){
-      if( pOrderBy->a[i+j].pExpr->iColumn!=pIdx->aiColumn[i+nEqCol] ) break;
+      CollSeq *pColl = sqlite3ExprCollSeq(pOrderBy->a[i+j].pExpr);
+      if( !pColl ) pColl = db->pDfltColl;
+      if( pOrderBy->a[i+j].pExpr->iColumn!=pIdx->aiColumn[i+nEqCol] ||
+          pColl!=pIdx->keyInfo.aColl[i+nEqCol] ) break;
     }
     if( i+j>=nExpr ){
       pMatch = pIdx;
@@ -532,14 +540,24 @@ WhereInfo *sqlite3WhereBegin(
 
       if( pIdx->nColumn>32 ) continue;  /* Ignore indices too many columns */
       for(j=0; j<nExpr; j++){
+        CollSeq *pColl = sqlite3ExprCollSeq(aExpr[j].p->pLeft);
+        if( !pColl && aExpr[j].p->pRight ){
+          pColl = sqlite3ExprCollSeq(aExpr[j].p->pRight);
+        }
+        if( !pColl ){
+          pColl = pParse->db->pDfltColl;
+        }
         if( aExpr[j].idxLeft==iCur 
              && (aExpr[j].prereqRight & loopMask)==aExpr[j].prereqRight ){
           int iColumn = aExpr[j].p->pLeft->iColumn;
           int k;
           char idxaff = pIdx->pTable->aCol[iColumn].affinity; 
           for(k=0; k<pIdx->nColumn; k++){
-            if( pIdx->aiColumn[k]==iColumn 
-                && sqlite3IndexAffinityOk(aExpr[j].p, idxaff) ){
+            /* If the collating sequences or affinities don't match, 
+            ** ignore this index.  */
+            if( pColl!=pIdx->keyInfo.aColl[k] ) continue;
+            if( !sqlite3IndexAffinityOk(aExpr[j].p, idxaff) ) continue;
+            if( pIdx->aiColumn[k]==iColumn ){
               switch( aExpr[j].p->op ){
                 case TK_IN: {
                   if( k==0 ) inMask |= 1;
@@ -575,8 +593,11 @@ WhereInfo *sqlite3WhereBegin(
           int k;
           char idxaff = pIdx->pTable->aCol[iColumn].affinity; 
           for(k=0; k<pIdx->nColumn; k++){
-            if( pIdx->aiColumn[k]==iColumn 
-                && sqlite3IndexAffinityOk(aExpr[j].p, idxaff) ){
+            /* If the collating sequences or affinities don't match, 
+            ** ignore this index.  */
+            if( pColl!=pIdx->keyInfo.aColl[k] ) continue;
+            if( !sqlite3IndexAffinityOk(aExpr[j].p, idxaff) ) continue;
+            if( pIdx->aiColumn[k]==iColumn ){
               switch( aExpr[j].p->op ){
                 case TK_EQ: {
                   eqMask |= 1<<k;
@@ -655,7 +676,7 @@ WhereInfo *sqlite3WhereBegin(
        pSortIdx = 0;
      }else{
        int nEqCol = (pWInfo->a[0].score+4)/8;
-       pSortIdx = findSortingIndex(pTab, pTabList->a[0].iCursor, 
+       pSortIdx = findSortingIndex(pParse->db, pTab, pTabList->a[0].iCursor, 
                                    *ppOrderBy, pIdx, nEqCol, &bRev);
      }
      if( pSortIdx && (pIdx==0 || pIdx==pSortIdx) ){