mirror of
https://github.com/tursodatabase/libsql.git
synced 2024-12-16 03:19:00 +00:00
315 lines
9.4 KiB
C
315 lines
9.4 KiB
C
/*
|
|
** 2013-02-28
|
|
**
|
|
** 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 to implement the next_char(A,T,F,W,C) SQL function.
|
|
**
|
|
** The next_char(A,T,F,W,C) function finds all valid "next" characters for
|
|
** string A given the vocabulary in T.F. If the W value exists and is a
|
|
** non-empty string, then it is an SQL expression that limits the entries
|
|
** in T.F that will be considered. If C exists and is a non-empty string,
|
|
** then it is the name of the collating sequence to use for comparison. If
|
|
**
|
|
** Only the first three arguments are required. If the C parameter is
|
|
** omitted or is NULL or is an empty string, then the default collating
|
|
** sequence of T.F is used for comparision. If the W parameter is omitted
|
|
** or is NULL or is an empty string, then no filtering of the output is
|
|
** done.
|
|
**
|
|
** The T.F column should be indexed using collation C or else this routine
|
|
** will be quite slow.
|
|
**
|
|
** For example, suppose an application has a dictionary like this:
|
|
**
|
|
** CREATE TABLE dictionary(word TEXT UNIQUE);
|
|
**
|
|
** Further suppose that for user keypad entry, it is desired to disable
|
|
** (gray out) keys that are not valid as the next character. If the
|
|
** the user has previously entered (say) 'cha' then to find all allowed
|
|
** next characters (and thereby determine when keys should not be grayed
|
|
** out) run the following query:
|
|
**
|
|
** SELECT next_char('cha','dictionary','word');
|
|
**
|
|
** IMPLEMENTATION NOTES:
|
|
**
|
|
** The next_char function is implemented using recursive SQL that makes
|
|
** use of the table name and column name as part of a query. If either
|
|
** the table name or column name are keywords or contain special characters,
|
|
** then they should be escaped. For example:
|
|
**
|
|
** SELECT next_char('cha','[dictionary]','[word]');
|
|
**
|
|
** This also means that the table name can be a subquery:
|
|
**
|
|
** SELECT next_char('cha','(SELECT word AS w FROM dictionary)','w');
|
|
*/
|
|
#include "sqlite3ext.h"
|
|
SQLITE_EXTENSION_INIT1
|
|
#include <string.h>
|
|
|
|
/*
|
|
** A structure to hold context of the next_char() computation across
|
|
** nested function calls.
|
|
*/
|
|
typedef struct nextCharContext nextCharContext;
|
|
struct nextCharContext {
|
|
sqlite3 *db; /* Database connection */
|
|
sqlite3_stmt *pStmt; /* Prepared statement used to query */
|
|
const unsigned char *zPrefix; /* Prefix to scan */
|
|
int nPrefix; /* Size of zPrefix in bytes */
|
|
int nAlloc; /* Space allocated to aResult */
|
|
int nUsed; /* Space used in aResult */
|
|
unsigned int *aResult; /* Array of next characters */
|
|
int mallocFailed; /* True if malloc fails */
|
|
int otherError; /* True for any other failure */
|
|
};
|
|
|
|
/*
|
|
** Append a result character if the character is not already in the
|
|
** result.
|
|
*/
|
|
static void nextCharAppend(nextCharContext *p, unsigned c){
|
|
int i;
|
|
for(i=0; i<p->nUsed; i++){
|
|
if( p->aResult[i]==c ) return;
|
|
}
|
|
if( p->nUsed+1 > p->nAlloc ){
|
|
unsigned int *aNew;
|
|
int n = p->nAlloc*2 + 30;
|
|
aNew = sqlite3_realloc64(p->aResult, n*sizeof(unsigned int));
|
|
if( aNew==0 ){
|
|
p->mallocFailed = 1;
|
|
return;
|
|
}else{
|
|
p->aResult = aNew;
|
|
p->nAlloc = n;
|
|
}
|
|
}
|
|
p->aResult[p->nUsed++] = c;
|
|
}
|
|
|
|
/*
|
|
** Write a character into z[] as UTF8. Return the number of bytes needed
|
|
** to hold the character
|
|
*/
|
|
static int writeUtf8(unsigned char *z, unsigned c){
|
|
if( c<0x00080 ){
|
|
z[0] = (unsigned char)(c&0xff);
|
|
return 1;
|
|
}
|
|
if( c<0x00800 ){
|
|
z[0] = 0xC0 + (unsigned char)((c>>6)&0x1F);
|
|
z[1] = 0x80 + (unsigned char)(c & 0x3F);
|
|
return 2;
|
|
}
|
|
if( c<0x10000 ){
|
|
z[0] = 0xE0 + (unsigned char)((c>>12)&0x0F);
|
|
z[1] = 0x80 + (unsigned char)((c>>6) & 0x3F);
|
|
z[2] = 0x80 + (unsigned char)(c & 0x3F);
|
|
return 3;
|
|
}
|
|
z[0] = 0xF0 + (unsigned char)((c>>18) & 0x07);
|
|
z[1] = 0x80 + (unsigned char)((c>>12) & 0x3F);
|
|
z[2] = 0x80 + (unsigned char)((c>>6) & 0x3F);
|
|
z[3] = 0x80 + (unsigned char)(c & 0x3F);
|
|
return 4;
|
|
}
|
|
|
|
/*
|
|
** Read a UTF8 character out of z[] and write it into *pOut. Return
|
|
** the number of bytes in z[] that were used to construct the character.
|
|
*/
|
|
static int readUtf8(const unsigned char *z, unsigned *pOut){
|
|
static const unsigned char validBits[] = {
|
|
0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
|
|
0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
|
|
0x10, 0x11, 0x12, 0x13, 0x14, 0x15, 0x16, 0x17,
|
|
0x18, 0x19, 0x1a, 0x1b, 0x1c, 0x1d, 0x1e, 0x1f,
|
|
0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
|
|
0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
|
|
0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
|
|
0x00, 0x01, 0x02, 0x03, 0x00, 0x01, 0x00, 0x00,
|
|
};
|
|
unsigned c = z[0];
|
|
if( c<0xc0 ){
|
|
*pOut = c;
|
|
return 1;
|
|
}else{
|
|
int n = 1;
|
|
c = validBits[c-0xc0];
|
|
while( (z[n] & 0xc0)==0x80 ){
|
|
c = (c<<6) + (0x3f & z[n++]);
|
|
}
|
|
if( c<0x80 || (c&0xFFFFF800)==0xD800 || (c&0xFFFFFFFE)==0xFFFE ){
|
|
c = 0xFFFD;
|
|
}
|
|
*pOut = c;
|
|
return n;
|
|
}
|
|
}
|
|
|
|
/*
|
|
** The nextCharContext structure has been set up. Add all "next" characters
|
|
** to the result set.
|
|
*/
|
|
static void findNextChars(nextCharContext *p){
|
|
unsigned cPrev = 0;
|
|
unsigned char zPrev[8];
|
|
int n, rc;
|
|
|
|
for(;;){
|
|
sqlite3_bind_text(p->pStmt, 1, (char*)p->zPrefix, p->nPrefix,
|
|
SQLITE_STATIC);
|
|
n = writeUtf8(zPrev, cPrev+1);
|
|
sqlite3_bind_text(p->pStmt, 2, (char*)zPrev, n, SQLITE_STATIC);
|
|
rc = sqlite3_step(p->pStmt);
|
|
if( rc==SQLITE_DONE ){
|
|
sqlite3_reset(p->pStmt);
|
|
return;
|
|
}else if( rc!=SQLITE_ROW ){
|
|
p->otherError = rc;
|
|
return;
|
|
}else{
|
|
const unsigned char *zOut = sqlite3_column_text(p->pStmt, 0);
|
|
unsigned cNext;
|
|
n = readUtf8(zOut+p->nPrefix, &cNext);
|
|
sqlite3_reset(p->pStmt);
|
|
nextCharAppend(p, cNext);
|
|
cPrev = cNext;
|
|
if( p->mallocFailed ) return;
|
|
}
|
|
}
|
|
}
|
|
|
|
|
|
/*
|
|
** next_character(A,T,F,W)
|
|
**
|
|
** Return a string composted of all next possible characters after
|
|
** A for elements of T.F. If W is supplied, then it is an SQL expression
|
|
** that limits the elements in T.F that are considered.
|
|
*/
|
|
static void nextCharFunc(
|
|
sqlite3_context *context,
|
|
int argc,
|
|
sqlite3_value **argv
|
|
){
|
|
nextCharContext c;
|
|
const unsigned char *zTable = sqlite3_value_text(argv[1]);
|
|
const unsigned char *zField = sqlite3_value_text(argv[2]);
|
|
const unsigned char *zWhere;
|
|
const unsigned char *zCollName;
|
|
char *zWhereClause = 0;
|
|
char *zColl = 0;
|
|
char *zSql;
|
|
int rc;
|
|
|
|
memset(&c, 0, sizeof(c));
|
|
c.db = sqlite3_context_db_handle(context);
|
|
c.zPrefix = sqlite3_value_text(argv[0]);
|
|
c.nPrefix = sqlite3_value_bytes(argv[0]);
|
|
if( zTable==0 || zField==0 || c.zPrefix==0 ) return;
|
|
if( argc>=4
|
|
&& (zWhere = sqlite3_value_text(argv[3]))!=0
|
|
&& zWhere[0]!=0
|
|
){
|
|
zWhereClause = sqlite3_mprintf("AND (%s)", zWhere);
|
|
if( zWhereClause==0 ){
|
|
sqlite3_result_error_nomem(context);
|
|
return;
|
|
}
|
|
}else{
|
|
zWhereClause = "";
|
|
}
|
|
if( argc>=5
|
|
&& (zCollName = sqlite3_value_text(argv[4]))!=0
|
|
&& zCollName[0]!=0
|
|
){
|
|
zColl = sqlite3_mprintf("collate \"%w\"", zCollName);
|
|
if( zColl==0 ){
|
|
sqlite3_result_error_nomem(context);
|
|
if( zWhereClause[0] ) sqlite3_free(zWhereClause);
|
|
return;
|
|
}
|
|
}else{
|
|
zColl = "";
|
|
}
|
|
zSql = sqlite3_mprintf(
|
|
"SELECT %s FROM %s"
|
|
" WHERE %s>=(?1 || ?2) %s"
|
|
" AND %s<=(?1 || char(1114111)) %s" /* 1114111 == 0x10ffff */
|
|
" %s"
|
|
" ORDER BY 1 %s ASC LIMIT 1",
|
|
zField, zTable, zField, zColl, zField, zColl, zWhereClause, zColl
|
|
);
|
|
if( zWhereClause[0] ) sqlite3_free(zWhereClause);
|
|
if( zColl[0] ) sqlite3_free(zColl);
|
|
if( zSql==0 ){
|
|
sqlite3_result_error_nomem(context);
|
|
return;
|
|
}
|
|
|
|
rc = sqlite3_prepare_v2(c.db, zSql, -1, &c.pStmt, 0);
|
|
sqlite3_free(zSql);
|
|
if( rc ){
|
|
sqlite3_result_error(context, sqlite3_errmsg(c.db), -1);
|
|
return;
|
|
}
|
|
findNextChars(&c);
|
|
if( c.mallocFailed ){
|
|
sqlite3_result_error_nomem(context);
|
|
}else{
|
|
unsigned char *pRes;
|
|
pRes = sqlite3_malloc64( c.nUsed*4 + 1 );
|
|
if( pRes==0 ){
|
|
sqlite3_result_error_nomem(context);
|
|
}else{
|
|
int i;
|
|
int n = 0;
|
|
for(i=0; i<c.nUsed; i++){
|
|
n += writeUtf8(pRes+n, c.aResult[i]);
|
|
}
|
|
pRes[n] = 0;
|
|
sqlite3_result_text(context, (const char*)pRes, n, sqlite3_free);
|
|
}
|
|
}
|
|
sqlite3_finalize(c.pStmt);
|
|
sqlite3_free(c.aResult);
|
|
}
|
|
|
|
#ifdef _WIN32
|
|
__declspec(dllexport)
|
|
#endif
|
|
int sqlite3_nextchar_init(
|
|
sqlite3 *db,
|
|
char **pzErrMsg,
|
|
const sqlite3_api_routines *pApi
|
|
){
|
|
int rc = SQLITE_OK;
|
|
SQLITE_EXTENSION_INIT2(pApi);
|
|
(void)pzErrMsg; /* Unused parameter */
|
|
rc = sqlite3_create_function(db, "next_char", 3,
|
|
SQLITE_UTF8|SQLITE_INNOCUOUS, 0,
|
|
nextCharFunc, 0, 0);
|
|
if( rc==SQLITE_OK ){
|
|
rc = sqlite3_create_function(db, "next_char", 4,
|
|
SQLITE_UTF8|SQLITE_INNOCUOUS, 0,
|
|
nextCharFunc, 0, 0);
|
|
}
|
|
if( rc==SQLITE_OK ){
|
|
rc = sqlite3_create_function(db, "next_char", 5,
|
|
SQLITE_UTF8|SQLITE_INNOCUOUS, 0,
|
|
nextCharFunc, 0, 0);
|
|
}
|
|
return rc;
|
|
}
|