ext/misc/nextchar.c

   1 /*
   2 ** 2013-02-28
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 ******************************************************************************
  12 **
  13 ** This file contains code to implement the next_char(A,T,F,W,C) SQL function.
  14 **
  15 ** The next_char(A,T,F,W,C) function finds all valid "next" characters for
  16 ** string A given the vocabulary in T.F.  If the W value exists and is a
  17 ** non-empty string, then it is an SQL expression that limits the entries
  18 ** in T.F that will be considered.  If C exists and is a non-empty string,
  19 ** then it is the name of the collating sequence to use for comparison.  If
  20 **
  21 ** Only the first three arguments are required.  If the C parameter is
  22 ** omitted or is NULL or is an empty string, then the default collating
  23 ** sequence of T.F is used for comparision.  If the W parameter is omitted
  24 ** or is NULL or is an empty string, then no filtering of the output is
  25 ** done.
  26 **
  27 ** The T.F column should be indexed using collation C or else this routine
  28 ** will be quite slow.
  29 **
  30 ** For example, suppose an application has a dictionary like this:
  31 **
  32 **   CREATE TABLE dictionary(word TEXT UNIQUE);
  33 **
  34 ** Further suppose that for user keypad entry, it is desired to disable
  35 ** (gray out) keys that are not valid as the next character.  If the
  36 ** the user has previously entered (say) 'cha' then to find all allowed
  37 ** next characters (and thereby determine when keys should not be grayed
  38 ** out) run the following query:
  39 **
  40 **   SELECT next_char('cha','dictionary','word');
  41 **
  42 ** IMPLEMENTATION NOTES:
  43 **
  44 ** The next_char function is implemented using recursive SQL that makes
  45 ** use of the table name and column name as part of a query.  If either
  46 ** the table name or column name are keywords or contain special characters,
  47 ** then they should be escaped.  For example:
  48 **
  49 **   SELECT next_char('cha','[dictionary]','[word]');
  50 **
  51 ** This also means that the table name can be a subquery:
  52 **
  53 **   SELECT next_char('cha','(SELECT word AS w FROM dictionary)','w');
  54 */
  55 #include "sqlite3ext.h"
  56 SQLITE_EXTENSION_INIT1
  57 #include <string.h>
  58
  59 /*
  60 ** A structure to hold context of the next_char() computation across
  61 ** nested function calls.
  62 */
  63 typedef struct nextCharContext nextCharContext;
  64 struct nextCharContext {
  65   sqlite3 *db;                      /* Database connection */
  66   sqlite3_stmt *pStmt;              /* Prepared statement used to query */
  67   const unsigned char *zPrefix;     /* Prefix to scan */
  68   int nPrefix;                      /* Size of zPrefix in bytes */
  69   int nAlloc;                       /* Space allocated to aResult */
  70   int nUsed;                        /* Space used in aResult */
  71   unsigned int *aResult;            /* Array of next characters */
  72   int mallocFailed;                 /* True if malloc fails */
  73   int otherError;                   /* True for any other failure */
  74 };
  75
  76 /*
  77 ** Append a result character if the character is not already in the
  78 ** result.
  79 */
  80 static void nextCharAppend(nextCharContext *p, unsigned c){
  81   int i;
  82   for(i=0; i<p->nUsed; i++){
  83     if( p->aResult[i]==c ) return;
  84   }
  85   if( p->nUsed+1 > p->nAlloc ){
  86     unsigned int *aNew;
  87     int n = p->nAlloc*2 + 30;
  88     aNew = sqlite3_realloc(p->aResult, n*sizeof(unsigned int));
  89     if( aNew==0 ){
  90       p->mallocFailed = 1;
  91       return;
  92     }else{
  93       p->aResult = aNew;
  94       p->nAlloc = n;
  95     }
  96   }
  97   p->aResult[p->nUsed++] = c;
  98 }
  99
 100 /*
 101 ** Write a character into z[] as UTF8.  Return the number of bytes needed
 102 ** to hold the character
 103 */
 104 static int writeUtf8(unsigned char *z, unsigned c){
 105   if( c<0x00080 ){
 106     z[0] = (unsigned char)(c&0xff);
 107     return 1;
 108   }
 109   if( c<0x00800 ){
 110     z[0] = 0xC0 + (unsigned char)((c>>6)&0x1F);
 111     z[1] = 0x80 + (unsigned char)(c & 0x3F);
 112     return 2;
 113   }
 114   if( c<0x10000 ){
 115     z[0] = 0xE0 + (unsigned char)((c>>12)&0x0F);
 116     z[1] = 0x80 + (unsigned char)((c>>6) & 0x3F);
 117     z[2] = 0x80 + (unsigned char)(c & 0x3F);
 118     return 3;
 119   }
 120   z[0] = 0xF0 + (unsigned char)((c>>18) & 0x07);
 121   z[1] = 0x80 + (unsigned char)((c>>12) & 0x3F);
 122   z[2] = 0x80 + (unsigned char)((c>>6) & 0x3F);
 123   z[3] = 0x80 + (unsigned char)(c & 0x3F);
 124   return 4;
 125 }
 126
 127 /*
 128 ** Read a UTF8 character out of z[] and write it into *pOut.  Return
 129 ** the number of bytes in z[] that were used to construct the character.
 130 */
 131 static int readUtf8(const unsigned char *z, unsigned *pOut){
 132   static const unsigned char validBits[] = {
 133     0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
 134     0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
 135     0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
 136     0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
 137     0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
 138     0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
 139     0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
 140     0x00, 0x01, 0x02, 0x03, 0x00, 0x01, 0x00, 0x00,
 141   };
 142   unsigned c = z[0];
 143   if( c<0xc0 ){
 144     *pOut = c;
 145     return 1;
 146   }else{
 147     int n = 1;
 148     c = validBits[c-0xc0];
 149     while( (z[n] & 0xc0)==0x80 ){
 150       c = (c<<6) + (0x3f & z[n++]);
 151     }
 152     if( c<0x80 || (c&0xFFFFF800)==0xD800 || (c&0xFFFFFFFE)==0xFFFE ){
 153       c = 0xFFFD;
 154     }
 155     *pOut = c;
 156     return n;
 157   }
 158 }
 159
 160 /*
 161 ** The nextCharContext structure has been set up.  Add all "next" characters
 162 ** to the result set.
 163 */
 164 static void findNextChars(nextCharContext *p){
 165   unsigned cPrev = 0;
 166   unsigned char zPrev[8];
 167   int n, rc;
 168
 169   for(;;){
 170     sqlite3_bind_text(p->pStmt, 1, (char*)p->zPrefix, p->nPrefix,
 171                       SQLITE_STATIC);
 172     n = writeUtf8(zPrev, cPrev+1);
 173     sqlite3_bind_text(p->pStmt, 2, (char*)zPrev, n, SQLITE_STATIC);
 174     rc = sqlite3_step(p->pStmt);
 175     if( rc==SQLITE_DONE ){
 176       sqlite3_reset(p->pStmt);
 177       return;
 178     }else if( rc!=SQLITE_ROW ){
 179       p->otherError = rc;
 180       return;
 181     }else{
 182       const unsigned char *zOut = sqlite3_column_text(p->pStmt, 0);
 183       unsigned cNext;
 184       n = readUtf8(zOut+p->nPrefix, &cNext);
 185       sqlite3_reset(p->pStmt);
 186       nextCharAppend(p, cNext);
 187       cPrev = cNext;
 188       if( p->mallocFailed ) return;
 189     }
 190   }
 191 }
 192
 193
 194 /*
 195 ** next_character(A,T,F,W)
 196 **
 197 ** Return a string composted of all next possible characters after
 198 ** A for elements of T.F.  If W is supplied, then it is an SQL expression
 199 ** that limits the elements in T.F that are considered.
 200 */
 201 static void nextCharFunc(
 202   sqlite3_context *context,
 203   int argc,
 204   sqlite3_value **argv
 205 ){
 206   nextCharContext c;
 207   const unsigned char *zTable = sqlite3_value_text(argv[1]);
 208   const unsigned char *zField = sqlite3_value_text(argv[2]);
 209   const unsigned char *zWhere;
 210   const unsigned char *zCollName;
 211   char *zWhereClause = 0;
 212   char *zColl = 0;
 213   char *zSql;
 214   int rc;
 215
 216   memset(&c, 0, sizeof(c));
 217   c.db = sqlite3_context_db_handle(context);
 218   c.zPrefix = sqlite3_value_text(argv[0]);
 219   c.nPrefix = sqlite3_value_bytes(argv[0]);
 220   if( zTable==0 || zField==0 || c.zPrefix==0 ) return;
 221   if( argc>=4
 222    && (zWhere = sqlite3_value_text(argv[3]))!=0
 223    && zWhere[0]!=0
 224   ){
 225     zWhereClause = sqlite3_mprintf("AND (%s)", zWhere);
 226     if( zWhereClause==0 ){
 227       sqlite3_result_error_nomem(context);
 228       return;
 229     }
 230   }else{
 231     zWhereClause = "";
 232   }
 233   if( argc>=5
 234    && (zCollName = sqlite3_value_text(argv[4]))!=0
 235    && zCollName[0]!=0
 236   ){
 237     zColl = sqlite3_mprintf("collate \"%w\"", zCollName);
 238     if( zColl==0 ){
 239       sqlite3_result_error_nomem(context);
 240       if( zWhereClause[0] ) sqlite3_free(zWhereClause);
 241       return;
 242     }
 243   }else{
 244     zColl = "";
 245   }
 246   zSql = sqlite3_mprintf(
 247     "SELECT %s FROM %s"
 248     " WHERE %s>=(?1 || ?2) %s"
 249     "   AND %s<=(?1 || char(1114111)) %s" /* 1114111 == 0x10ffff */
 250     "   %s"
 251     " ORDER BY 1 %s ASC LIMIT 1",
 252     zField, zTable, zField, zColl, zField, zColl, zWhereClause, zColl
 253   );
 254   if( zWhereClause[0] ) sqlite3_free(zWhereClause);
 255   if( zColl[0] ) sqlite3_free(zColl);
 256   if( zSql==0 ){
 257     sqlite3_result_error_nomem(context);
 258     return;
 259   }
 260
 261   rc = sqlite3_prepare_v2(c.db, zSql, -1, &c.pStmt, 0);
 262   sqlite3_free(zSql);
 263   if( rc ){
 264     sqlite3_result_error(context, sqlite3_errmsg(c.db), -1);
 265     return;
 266   }
 267   findNextChars(&c);
 268   if( c.mallocFailed ){
 269     sqlite3_result_error_nomem(context);
 270   }else{
 271     unsigned char *pRes;
 272     pRes = sqlite3_malloc( c.nUsed*4 + 1 );
 273     if( pRes==0 ){
 274       sqlite3_result_error_nomem(context);
 275     }else{
 276       int i;
 277       int n = 0;
 278       for(i=0; i<c.nUsed; i++){
 279         n += writeUtf8(pRes+n, c.aResult[i]);
 280       }
 281       pRes[n] = 0;
 282       sqlite3_result_text(context, (const char*)pRes, n, sqlite3_free);
 283     }
 284   }
 285   sqlite3_finalize(c.pStmt);
 286   sqlite3_free(c.aResult);
 287 }
 288
 289 #ifdef _WIN32
 290 __declspec(dllexport)
 291 #endif
 292 int sqlite3_nextchar_init(
 293   sqlite3 *db,
 294   char **pzErrMsg,
 295   const sqlite3_api_routines *pApi
 296 ){
 297   int rc = SQLITE_OK;
 298   SQLITE_EXTENSION_INIT2(pApi);
 299   (void)pzErrMsg;  /* Unused parameter */
 300   rc = sqlite3_create_function(db, "next_char", 3, SQLITE_UTF8, 0,
 301                                nextCharFunc, 0, 0);
 302   if( rc==SQLITE_OK ){
 303     rc = sqlite3_create_function(db, "next_char", 4, SQLITE_UTF8, 0,
 304                                  nextCharFunc, 0, 0);
 305   }
 306   if( rc==SQLITE_OK ){
 307     rc = sqlite3_create_function(db, "next_char", 5, SQLITE_UTF8, 0,
 308                                  nextCharFunc, 0, 0);
 309   }
 310   return rc;
 311 }