MCL/sf/os/persistentdata: comparison persistentstorage/sqlite3api/SQLite/fts2

equal deleted inserted replaced

--1:000000000000
+:08ec8eefde2f
+/*
+** 2006 September 30
+**
+** 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.
+**
+*************************************************************************
+** Implementation of the full-text-search tokenizer that implements
+** a Porter stemmer.
+*/
+/*
+** The code in this file is only compiled if:
+**
+**     * The FTS2 module is being built as an extension
+**       (in which case SQLITE_CORE is not defined), or
+**
+**     * The FTS2 module is being built into the core of
+**       SQLite (in which case SQLITE_ENABLE_FTS2 is defined).
+*/
+#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS2)
+#include <assert.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <ctype.h>
+#include "fts2_tokenizer.h"
+/*
+** Class derived from sqlite3_tokenizer
+*/
+typedef struct porter_tokenizer {
+sqlite3_tokenizer base;      /* Base class */
+} porter_tokenizer;
+/*
+** Class derived from sqlit3_tokenizer_cursor
+*/
+typedef struct porter_tokenizer_cursor {
+sqlite3_tokenizer_cursor base;
+const char *zInput;          /* input we are tokenizing */
+int nInput;                  /* size of the input */
+int iOffset;                 /* current position in zInput */
+int iToken;                  /* index of next token to be returned */
+char *zToken;                /* storage for current token */
+int nAllocated;              /* space allocated to zToken buffer */
+} porter_tokenizer_cursor;
+/* Forward declaration */
+static const sqlite3_tokenizer_module porterTokenizerModule;
+/*
+** Create a new tokenizer instance.
+*/
+static int porterCreate(
+int argc, const char * const *argv,
+sqlite3_tokenizer **ppTokenizer
+){
+porter_tokenizer *t;
+t = (porter_tokenizer *) sqlite3_malloc(sizeof(*t));
+if( t==NULL ) return SQLITE_NOMEM;
+memset(t, 0, sizeof(*t));
+*ppTokenizer = &t->base;
+return SQLITE_OK;
+}
+/*
+** Destroy a tokenizer
+*/
+static int porterDestroy(sqlite3_tokenizer *pTokenizer){
+sqlite3_free(pTokenizer);
+return SQLITE_OK;
+}
+/*
+** Prepare to begin tokenizing a particular string.  The input
+** string to be tokenized is zInput[0..nInput-1].  A cursor
+** used to incrementally tokenize this string is returned in
+** *ppCursor.
+*/
+static int porterOpen(
+sqlite3_tokenizer *pTokenizer,         /* The tokenizer */
+const char *zInput, int nInput,        /* String to be tokenized */
+sqlite3_tokenizer_cursor **ppCursor    /* OUT: Tokenization cursor */
+){
+porter_tokenizer_cursor *c;
+c = (porter_tokenizer_cursor *) sqlite3_malloc(sizeof(*c));
+if( c==NULL ) return SQLITE_NOMEM;
+c->zInput = zInput;
+if( zInput==0 ){
+c->nInput = 0;
+}else if( nInput<0 ){
+c->nInput = (int)strlen(zInput);
+}else{
+c->nInput = nInput;
+}
+c->iOffset = 0;                 /* start tokenizing at the beginning */
+c->iToken = 0;
+c->zToken = NULL;               /* no space allocated, yet. */
+c->nAllocated = 0;
+*ppCursor = &c->base;
+return SQLITE_OK;
+}
+/*
+** Close a tokenization cursor previously opened by a call to
+** porterOpen() above.
+*/
+static int porterClose(sqlite3_tokenizer_cursor *pCursor){
+porter_tokenizer_cursor *c = (porter_tokenizer_cursor *) pCursor;
+sqlite3_free(c->zToken);
+sqlite3_free(c);
+return SQLITE_OK;
+}
+/*
+** Vowel or consonant
+*/
+static const char cType[] = {
+0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0,
+1, 1, 1, 2, 1
+};
+/*
+** isConsonant() and isVowel() determine if their first character in
+** the string they point to is a consonant or a vowel, according
+** to Porter ruls.
+**
+** A consonate is any letter other than 'a', 'e', 'i', 'o', or 'u'.
+** 'Y' is a consonant unless it follows another consonant,
+** in which case it is a vowel.
+**
+** In these routine, the letters are in reverse order.  So the 'y' rule
+** is that 'y' is a consonant unless it is followed by another
+** consonent.
+*/
+static int isVowel(const char*);
+static int isConsonant(const char *z){
+int j;
+char x = *z;
+if( x==0 ) return 0;
+assert( x>='a' && x<='z' );
+j = cType[x-'a'];
+if( j<2 ) return j;
+return z[1]==0 || isVowel(z + 1);
+}
+static int isVowel(const char *z){
+int j;
+char x = *z;
+if( x==0 ) return 0;
+assert( x>='a' && x<='z' );
+j = cType[x-'a'];
+if( j<2 ) return 1-j;
+return isConsonant(z + 1);
+}
+/*
+** Let any sequence of one or more vowels be represented by V and let
+** C be sequence of one or more consonants.  Then every word can be
+** represented as:
+**
+**           [C] (VC){m} [V]
+**
+** In prose:  A word is an optional consonant followed by zero or
+** vowel-consonant pairs followed by an optional vowel.  "m" is the
+** number of vowel consonant pairs.  This routine computes the value
+** of m for the first i bytes of a word.
+**
+** Return true if the m-value for z is 1 or more.  In other words,
+** return true if z contains at least one vowel that is followed
+** by a consonant.
+**
+** In this routine z[] is in reverse order.  So we are really looking
+** for an instance of of a consonant followed by a vowel.
+*/
+static int m_gt_0(const char *z){
+while( isVowel(z) ){ z++; }
+if( *z==0 ) return 0;
+while( isConsonant(z) ){ z++; }
+return *z!=0;
+}
+/* Like mgt0 above except we are looking for a value of m which is
+** exactly 1
+*/
+static int m_eq_1(const char *z){
+while( isVowel(z) ){ z++; }
+if( *z==0 ) return 0;
+while( isConsonant(z) ){ z++; }
+if( *z==0 ) return 0;
+while( isVowel(z) ){ z++; }
+if( *z==0 ) return 1;
+while( isConsonant(z) ){ z++; }
+return *z==0;
+}
+/* Like mgt0 above except we are looking for a value of m>1 instead
+** or m>0
+*/
+static int m_gt_1(const char *z){
+while( isVowel(z) ){ z++; }
+if( *z==0 ) return 0;
+while( isConsonant(z) ){ z++; }
+if( *z==0 ) return 0;
+while( isVowel(z) ){ z++; }
+if( *z==0 ) return 0;
+while( isConsonant(z) ){ z++; }
+return *z!=0;
+}
+/*
+** Return TRUE if there is a vowel anywhere within z[0..n-1]
+*/
+static int hasVowel(const char *z){
+while( isConsonant(z) ){ z++; }
+return *z!=0;
+}
+/*
+** Return TRUE if the word ends in a double consonant.
+**
+** The text is reversed here. So we are really looking at
+** the first two characters of z[].
+*/
+static int doubleConsonant(const char *z){
+return isConsonant(z) && z[0]==z[1] && isConsonant(z+1);
+}
+/*
+** Return TRUE if the word ends with three letters which
+** are consonant-vowel-consonent and where the final consonant
+** is not 'w', 'x', or 'y'.
+**
+** The word is reversed here.  So we are really checking the
+** first three letters and the first one cannot be in [wxy].
+*/
+static int star_oh(const char *z){
+return
+z[0]!=0 && isConsonant(z) &&
+z[0]!='w' && z[0]!='x' && z[0]!='y' &&
+z[1]!=0 && isVowel(z+1) &&
+z[2]!=0 && isConsonant(z+2);
+}
+/*
+** If the word ends with zFrom and xCond() is true for the stem
+** of the word that preceeds the zFrom ending, then change the
+** ending to zTo.
+**
+** The input word *pz and zFrom are both in reverse order.  zTo
+** is in normal order.
+**
+** Return TRUE if zFrom matches.  Return FALSE if zFrom does not
+** match.  Not that TRUE is returned even if xCond() fails and
+** no substitution occurs.
+*/
+static int stem(
+char **pz,             /* The word being stemmed (Reversed) */
+const char *zFrom,     /* If the ending matches this... (Reversed) */
+const char *zTo,       /* ... change the ending to this (not reversed) */
+int (*xCond)(const char*)   /* Condition that must be true */
+){
+char *z = *pz;
+while( *zFrom && *zFrom==*z ){ z++; zFrom++; }
+if( *zFrom!=0 ) return 0;
+if( xCond && !xCond(z) ) return 1;
+while( *zTo ){
+*(--z) = *(zTo++);
+}
+*pz = z;
+return 1;
+}
+/*
+** This is the fallback stemmer used when the porter stemmer is
+** inappropriate.  The input word is copied into the output with
+** US-ASCII case folding.  If the input word is too long (more
+** than 20 bytes if it contains no digits or more than 6 bytes if
+** it contains digits) then word is truncated to 20 or 6 bytes
+** by taking 10 or 3 bytes from the beginning and end.
+*/
+static void copy_stemmer(const char *zIn, int nIn, char *zOut, int *pnOut){
+int i, mx, j;
+int hasDigit = 0;
+for(i=0; i<nIn; i++){
+int c = zIn[i];
+if( c>='A' && c<='Z' ){
+zOut[i] = c - 'A' + 'a';
+}else{
+if( c>='0' && c<='9' ) hasDigit = 1;
+zOut[i] = c;
+}
+}
+mx = hasDigit ? 3 : 10;
+if( nIn>mx*2 ){
+for(j=mx, i=nIn-mx; i<nIn; i++, j++){
+zOut[j] = zOut[i];
+}
+i = j;
+}
+zOut[i] = 0;
+*pnOut = i;
+}
+/*
+** Stem the input word zIn[0..nIn-1].  Store the output in zOut.
+** zOut is at least big enough to hold nIn bytes.  Write the actual
+** size of the output word (exclusive of the '\0' terminator) into *pnOut.
+**
+** Any upper-case characters in the US-ASCII character set ([A-Z])
+** are converted to lower case.  Upper-case UTF characters are
+** unchanged.
+**
+** Words that are longer than about 20 bytes are stemmed by retaining
+** a few bytes from the beginning and the end of the word.  If the
+** word contains digits, 3 bytes are taken from the beginning and
+** 3 bytes from the end.  For long words without digits, 10 bytes
+** are taken from each end.  US-ASCII case folding still applies.
+**
+** If the input word contains not digits but does characters not
+** in [a-zA-Z] then no stemming is attempted and this routine just
+** copies the input into the input into the output with US-ASCII
+** case folding.
+**
+** Stemming never increases the length of the word.  So there is
+** no chance of overflowing the zOut buffer.
+*/
+static void porter_stemmer(const char *zIn, int nIn, char *zOut, int *pnOut){
+int i, j, c;
+char zReverse[28];
+char *z, *z2;
+if( nIn<3 || nIn>=sizeof(zReverse)-7 ){
+/* The word is too big or too small for the porter stemmer.
+** Fallback to the copy stemmer */
+copy_stemmer(zIn, nIn, zOut, pnOut);
+return;
+}
+for(i=0, j=sizeof(zReverse)-6; i<nIn; i++, j--){
+c = zIn[i];
+if( c>='A' && c<='Z' ){
+zReverse[j] = c + 'a' - 'A';
+}else if( c>='a' && c<='z' ){
+zReverse[j] = c;
+}else{
+/* The use of a character not in [a-zA-Z] means that we fallback
+** to the copy stemmer */
+copy_stemmer(zIn, nIn, zOut, pnOut);
+return;
+}
+}
+memset(&zReverse[sizeof(zReverse)-5], 0, 5);
+z = &zReverse[j+1];
+/* Step 1a */
+if( z[0]=='s' ){
+if(
+!stem(&z, "sess", "ss", 0) &&
+!stem(&z, "sei", "i", 0)  &&
+!stem(&z, "ss", "ss", 0)
+){
+z++;
+}
+}
+/* Step 1b */
+z2 = z;
+if( stem(&z, "dee", "ee", m_gt_0) ){
+/* Do nothing.  The work was all in the test */
+}else if(
+(stem(&z, "gni", "", hasVowel) || stem(&z, "de", "", hasVowel))
+&& z!=z2
+){
+if( stem(&z, "ta", "ate", 0) ||
+stem(&z, "lb", "ble", 0) ||
+stem(&z, "zi", "ize", 0) ){
+/* Do nothing.  The work was all in the test */
+}else if( doubleConsonant(z) && (*z!='l' && *z!='s' && *z!='z') ){
+z++;
+}else if( m_eq_1(z) && star_oh(z) ){
+*(--z) = 'e';
+}
+}
+/* Step 1c */
+if( z[0]=='y' && hasVowel(z+1) ){
+z[0] = 'i';
+}
+/* Step 2 */
+switch( z[1] ){
+case 'a':
+stem(&z, "lanoita", "ate", m_gt_0) ||
+stem(&z, "lanoit", "tion", m_gt_0);
+break;
+case 'c':
+stem(&z, "icne", "ence", m_gt_0) ||
+stem(&z, "icna", "ance", m_gt_0);
+break;
+case 'e':
+stem(&z, "rezi", "ize", m_gt_0);
+break;
+case 'g':
+stem(&z, "igol", "log", m_gt_0);
+break;
+case 'l':
+stem(&z, "ilb", "ble", m_gt_0) ||
+stem(&z, "illa", "al", m_gt_0) ||
+stem(&z, "iltne", "ent", m_gt_0) ||
+stem(&z, "ile", "e", m_gt_0) ||
+stem(&z, "ilsuo", "ous", m_gt_0);
+break;
+case 'o':
+stem(&z, "noitazi", "ize", m_gt_0) ||
+stem(&z, "noita", "ate", m_gt_0) ||
+stem(&z, "rota", "ate", m_gt_0);
+break;
+case 's':
+stem(&z, "msila", "al", m_gt_0) ||
+stem(&z, "ssenevi", "ive", m_gt_0) ||
+stem(&z, "ssenluf", "ful", m_gt_0) ||
+stem(&z, "ssensuo", "ous", m_gt_0);
+break;
+case 't':
+stem(&z, "itila", "al", m_gt_0) ||
+stem(&z, "itivi", "ive", m_gt_0) ||
+stem(&z, "itilib", "ble", m_gt_0);
+break;
+}
+/* Step 3 */
+switch( z[0] ){
+case 'e':
+stem(&z, "etaci", "ic", m_gt_0) ||
+stem(&z, "evita", "", m_gt_0)   ||
+stem(&z, "ezila", "al", m_gt_0);
+break;
+case 'i':
+stem(&z, "itici", "ic", m_gt_0);
+break;
+case 'l':
+stem(&z, "laci", "ic", m_gt_0) ||
+stem(&z, "luf", "", m_gt_0);
+break;
+case 's':
+stem(&z, "ssen", "", m_gt_0);
+break;
+}
+/* Step 4 */
+switch( z[1] ){
+case 'a':
+if( z[0]=='l' && m_gt_1(z+2) ){
+z += 2;
+}
+break;
+case 'c':
+if( z[0]=='e' && z[2]=='n' && (z[3]=='a' || z[3]=='e')  && m_gt_1(z+4)  ){
+z += 4;
+}
+break;
+case 'e':
+if( z[0]=='r' && m_gt_1(z+2) ){
+z += 2;
+}
+break;
+case 'i':
+if( z[0]=='c' && m_gt_1(z+2) ){
+z += 2;
+}
+break;
+case 'l':
+if( z[0]=='e' && z[2]=='b' && (z[3]=='a' || z[3]=='i') && m_gt_1(z+4) ){
+z += 4;
+}
+break;
+case 'n':
+if( z[0]=='t' ){
+if( z[2]=='a' ){
+if( m_gt_1(z+3) ){
+z += 3;
+}
+}else if( z[2]=='e' ){
+stem(&z, "tneme", "", m_gt_1) ||
+stem(&z, "tnem", "", m_gt_1) ||
+stem(&z, "tne", "", m_gt_1);
+}
+}
+break;
+case 'o':
+if( z[0]=='u' ){
+if( m_gt_1(z+2) ){
+z += 2;
+}
+}else if( z[3]=='s' || z[3]=='t' ){
+stem(&z, "noi", "", m_gt_1);
+}
+break;
+case 's':
+if( z[0]=='m' && z[2]=='i' && m_gt_1(z+3) ){
+z += 3;
+}
+break;
+case 't':
+stem(&z, "eta", "", m_gt_1) ||
+stem(&z, "iti", "", m_gt_1);
+break;
+case 'u':
+if( z[0]=='s' && z[2]=='o' && m_gt_1(z+3) ){
+z += 3;
+}
+break;
+case 'v':
+case 'z':
+if( z[0]=='e' && z[2]=='i' && m_gt_1(z+3) ){
+z += 3;
+}
+break;
+}
+/* Step 5a */
+if( z[0]=='e' ){
+if( m_gt_1(z+1) ){
+z++;
+}else if( m_eq_1(z+1) && !star_oh(z+1) ){
+z++;
+}
+}
+/* Step 5b */
+if( m_gt_1(z) && z[0]=='l' && z[1]=='l' ){
+z++;
+}
+/* z[] is now the stemmed word in reverse order.  Flip it back
+** around into forward order and return.
+*/
+*pnOut = i = strlen(z);
+zOut[i] = 0;
+while( *z ){
+zOut[--i] = *(z++);
+}
+}
+/*
+** Characters that can be part of a token.  We assume any character
+** whose value is greater than 0x80 (any UTF character) can be
+** part of a token.  In other words, delimiters all must have
+** values of 0x7f or lower.
+*/
+static const char porterIdChar[] = {
+/* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */
+1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,  /* 3x */
+0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 4x */
+1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1,  /* 5x */
+0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 6x */
+1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0,  /* 7x */
+};
+#define isDelim(C) (((ch=C)&0x80)==0 && (ch<0x30 || !porterIdChar[ch-0x30]))
+/*
+** Extract the next token from a tokenization cursor.  The cursor must
+** have been opened by a prior call to porterOpen().
+*/
+static int porterNext(
+sqlite3_tokenizer_cursor *pCursor,  /* Cursor returned by porterOpen */
+const char **pzToken,               /* OUT: *pzToken is the token text */
+int *pnBytes,                       /* OUT: Number of bytes in token */
+int *piStartOffset,                 /* OUT: Starting offset of token */
+int *piEndOffset,                   /* OUT: Ending offset of token */
+int *piPosition                     /* OUT: Position integer of token */
+){
+porter_tokenizer_cursor *c = (porter_tokenizer_cursor *) pCursor;
+const char *z = c->zInput;
+while( c->iOffset<c->nInput ){
+int iStartOffset, ch;
+/* Scan past delimiter characters */
+while( c->iOffset<c->nInput && isDelim(z[c->iOffset]) ){
+c->iOffset++;
+}
+/* Count non-delimiter characters. */
+iStartOffset = c->iOffset;
+while( c->iOffset<c->nInput && !isDelim(z[c->iOffset]) ){
+c->iOffset++;
+}
+if( c->iOffset>iStartOffset ){
+int n = c->iOffset-iStartOffset;
+if( n>c->nAllocated ){
+c->nAllocated = n+20;
+c->zToken = sqlite3_realloc(c->zToken, c->nAllocated);
+if( c->zToken==NULL ) return SQLITE_NOMEM;
+}
+porter_stemmer(&z[iStartOffset], n, c->zToken, pnBytes);
+*pzToken = c->zToken;
+*piStartOffset = iStartOffset;
+*piEndOffset = c->iOffset;
+*piPosition = c->iToken++;
+return SQLITE_OK;
+}
+}
+return SQLITE_DONE;
+}
+/*
+** The set of routines that implement the porter-stemmer tokenizer
+*/
+static const sqlite3_tokenizer_module porterTokenizerModule = {
+0,
+porterCreate,
+porterDestroy,
+porterOpen,
+porterClose,
+porterNext,
+};
+/*
+** Allocate a new porter tokenizer.  Return a pointer to the new
+** tokenizer in *ppModule
+*/
+void sqlite3Fts2PorterTokenizerModule(
+sqlite3_tokenizer_module const**ppModule
+){
+*ppModule = &porterTokenizerModule;
+}
+#endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS2) */