1 /*

     2 ** 2006 September 30

     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 ** Implementation of the full-text-search tokenizer that implements

    13 ** a Porter stemmer.

    14 */

    15 

    16 /*

    17 ** The code in this file is only compiled if:

    18 **

    19 **     * The FTS1 module is being built as an extension

    20 **       (in which case SQLITE_CORE is not defined), or

    21 **

    22 **     * The FTS1 module is being built into the core of

    23 **       SQLite (in which case SQLITE_ENABLE_FTS1 is defined).

    24 */

    25 #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS1)

    26 

    27 

    28 #include <assert.h>

    29 #include <stdlib.h>

    30 #include <stdio.h>

    31 #include <string.h>

    32 #include <ctype.h>

    33 

    34 #include "fts1_tokenizer.h"

    35 

    36 /*

    37 ** Class derived from sqlite3_tokenizer

    38 */

    39 typedef struct porter_tokenizer {

    40   sqlite3_tokenizer base;      /* Base class */

    41 } porter_tokenizer;

    42 

    43 /*

    44 ** Class derived from sqlit3_tokenizer_cursor

    45 */

    46 typedef struct porter_tokenizer_cursor {

    47   sqlite3_tokenizer_cursor base;

    48   const char *zInput;          /* input we are tokenizing */

    49   int nInput;                  /* size of the input */

    50   int iOffset;                 /* current position in zInput */

    51   int iToken;                  /* index of next token to be returned */

    52   char *zToken;                /* storage for current token */

    53   int nAllocated;              /* space allocated to zToken buffer */

    54 } porter_tokenizer_cursor;

    55 

    56 

    57 /* Forward declaration */

    58 static const sqlite3_tokenizer_module porterTokenizerModule;

    59 

    60 

    61 /*

    62 ** Create a new tokenizer instance.

    63 */

    64 static int porterCreate(

    65   int argc, const char * const *argv,

    66   sqlite3_tokenizer **ppTokenizer

    67 ){

    68   porter_tokenizer *t;

    69   t = (porter_tokenizer *) calloc(sizeof(*t), 1);

    70   if( t==NULL ) return SQLITE_NOMEM;

    71 

    72   *ppTokenizer = &t->base;

    73   return SQLITE_OK;

    74 }

    75 

    76 /*

    77 ** Destroy a tokenizer

    78 */

    79 static int porterDestroy(sqlite3_tokenizer *pTokenizer){

    80   free(pTokenizer);

    81   return SQLITE_OK;

    82 }

    83 

    84 /*

    85 ** Prepare to begin tokenizing a particular string.  The input

    86 ** string to be tokenized is zInput[0..nInput-1].  A cursor

    87 ** used to incrementally tokenize this string is returned in 

    88 ** *ppCursor.

    89 */

    90 static int porterOpen(

    91   sqlite3_tokenizer *pTokenizer,         /* The tokenizer */

    92   const char *zInput, int nInput,        /* String to be tokenized */

    93   sqlite3_tokenizer_cursor **ppCursor    /* OUT: Tokenization cursor */

    94 ){

    95   porter_tokenizer_cursor *c;

    96 

    97   c = (porter_tokenizer_cursor *) malloc(sizeof(*c));

    98   if( c==NULL ) return SQLITE_NOMEM;

    99 

   100   c->zInput = zInput;

   101   if( zInput==0 ){

   102     c->nInput = 0;

   103   }else if( nInput<0 ){

   104     c->nInput = (int)strlen(zInput);

   105   }else{

   106     c->nInput = nInput;

   107   }

   108   c->iOffset = 0;                 /* start tokenizing at the beginning */

   109   c->iToken = 0;

   110   c->zToken = NULL;               /* no space allocated, yet. */

   111   c->nAllocated = 0;

   112 

   113   *ppCursor = &c->base;

   114   return SQLITE_OK;

   115 }

   116 

   117 /*

   118 ** Close a tokenization cursor previously opened by a call to

   119 ** porterOpen() above.

   120 */

   121 static int porterClose(sqlite3_tokenizer_cursor *pCursor){

   122   porter_tokenizer_cursor *c = (porter_tokenizer_cursor *) pCursor;

   123   free(c->zToken);

   124   free(c);

   125   return SQLITE_OK;

   126 }

   127 /*

   128 ** Vowel or consonant

   129 */

   130 static const char cType[] = {

   131    0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0,

   132    1, 1, 1, 2, 1

   133 };

   134 

   135 /*

   136 ** isConsonant() and isVowel() determine if their first character in

   137 ** the string they point to is a consonant or a vowel, according

   138 ** to Porter ruls.  

   139 **

   140 ** A consonate is any letter other than 'a', 'e', 'i', 'o', or 'u'.

   141 ** 'Y' is a consonant unless it follows another consonant,

   142 ** in which case it is a vowel.

   143 **

   144 ** In these routine, the letters are in reverse order.  So the 'y' rule

   145 ** is that 'y' is a consonant unless it is followed by another

   146 ** consonent.

   147 */

   148 static int isVowel(const char*);

   149 static int isConsonant(const char *z){

   150   int j;

   151   char x = *z;

   152   if( x==0 ) return 0;

   153   assert( x>='a' && x<='z' );

   154   j = cType[x-'a'];

   155   if( j<2 ) return j;

   156   return z[1]==0 || isVowel(z + 1);

   157 }

   158 static int isVowel(const char *z){

   159   int j;

   160   char x = *z;

   161   if( x==0 ) return 0;

   162   assert( x>='a' && x<='z' );

   163   j = cType[x-'a'];

   164   if( j<2 ) return 1-j;

   165   return isConsonant(z + 1);

   166 }

   167 

   168 /*

   169 ** Let any sequence of one or more vowels be represented by V and let

   170 ** C be sequence of one or more consonants.  Then every word can be

   171 ** represented as:

   172 **

   173 **           [C] (VC){m} [V]

   174 **

   175 ** In prose:  A word is an optional consonant followed by zero or

   176 ** vowel-consonant pairs followed by an optional vowel.  "m" is the

   177 ** number of vowel consonant pairs.  This routine computes the value

   178 ** of m for the first i bytes of a word.

   179 **

   180 ** Return true if the m-value for z is 1 or more.  In other words,

   181 ** return true if z contains at least one vowel that is followed

   182 ** by a consonant.

   183 **

   184 ** In this routine z[] is in reverse order.  So we are really looking

   185 ** for an instance of of a consonant followed by a vowel.

   186 */

   187 static int m_gt_0(const char *z){

   188   while( isVowel(z) ){ z++; }

   189   if( *z==0 ) return 0;

   190   while( isConsonant(z) ){ z++; }

   191   return *z!=0;

   192 }

   193 

   194 /* Like mgt0 above except we are looking for a value of m which is

   195 ** exactly 1

   196 */

   197 static int m_eq_1(const char *z){

   198   while( isVowel(z) ){ z++; }

   199   if( *z==0 ) return 0;

   200   while( isConsonant(z) ){ z++; }

   201   if( *z==0 ) return 0;

   202   while( isVowel(z) ){ z++; }

   203   if( *z==0 ) return 1;

   204   while( isConsonant(z) ){ z++; }

   205   return *z==0;

   206 }

   207 

   208 /* Like mgt0 above except we are looking for a value of m>1 instead

   209 ** or m>0

   210 */

   211 static int m_gt_1(const char *z){

   212   while( isVowel(z) ){ z++; }

   213   if( *z==0 ) return 0;

   214   while( isConsonant(z) ){ z++; }

   215   if( *z==0 ) return 0;

   216   while( isVowel(z) ){ z++; }

   217   if( *z==0 ) return 0;

   218   while( isConsonant(z) ){ z++; }

   219   return *z!=0;

   220 }

   221 

   222 /*

   223 ** Return TRUE if there is a vowel anywhere within z[0..n-1]

   224 */

   225 static int hasVowel(const char *z){

   226   while( isConsonant(z) ){ z++; }

   227   return *z!=0;

   228 }

   229 

   230 /*

   231 ** Return TRUE if the word ends in a double consonant.

   232 **

   233 ** The text is reversed here. So we are really looking at

   234 ** the first two characters of z[].

   235 */

   236 static int doubleConsonant(const char *z){

   237   return isConsonant(z) && z[0]==z[1] && isConsonant(z+1);

   238 }

   239 

   240 /*

   241 ** Return TRUE if the word ends with three letters which

   242 ** are consonant-vowel-consonent and where the final consonant

   243 ** is not 'w', 'x', or 'y'.

   244 **

   245 ** The word is reversed here.  So we are really checking the

   246 ** first three letters and the first one cannot be in [wxy].

   247 */

   248 static int star_oh(const char *z){

   249   return

   250     z[0]!=0 && isConsonant(z) &&

   251     z[0]!='w' && z[0]!='x' && z[0]!='y' &&

   252     z[1]!=0 && isVowel(z+1) &&

   253     z[2]!=0 && isConsonant(z+2);

   254 }

   255 

   256 /*

   257 ** If the word ends with zFrom and xCond() is true for the stem

   258 ** of the word that preceeds the zFrom ending, then change the 

   259 ** ending to zTo.

   260 **

   261 ** The input word *pz and zFrom are both in reverse order.  zTo

   262 ** is in normal order. 

   263 **

   264 ** Return TRUE if zFrom matches.  Return FALSE if zFrom does not

   265 ** match.  Not that TRUE is returned even if xCond() fails and

   266 ** no substitution occurs.

   267 */

   268 static int stem(

   269   char **pz,             /* The word being stemmed (Reversed) */

   270   const char *zFrom,     /* If the ending matches this... (Reversed) */

   271   const char *zTo,       /* ... change the ending to this (not reversed) */

   272   int (*xCond)(const char*)   /* Condition that must be true */

   273 ){

   274   char *z = *pz;

   275   while( *zFrom && *zFrom==*z ){ z++; zFrom++; }

   276   if( *zFrom!=0 ) return 0;

   277   if( xCond && !xCond(z) ) return 1;

   278   while( *zTo ){

   279     *(--z) = *(zTo++);

   280   }

   281   *pz = z;

   282   return 1;

   283 }

   284 

   285 /*

   286 ** This is the fallback stemmer used when the porter stemmer is

   287 ** inappropriate.  The input word is copied into the output with

   288 ** US-ASCII case folding.  If the input word is too long (more

   289 ** than 20 bytes if it contains no digits or more than 6 bytes if

   290 ** it contains digits) then word is truncated to 20 or 6 bytes

   291 ** by taking 10 or 3 bytes from the beginning and end.

   292 */

   293 static void copy_stemmer(const char *zIn, int nIn, char *zOut, int *pnOut){

   294   int i, mx, j;

   295   int hasDigit = 0;

   296   for(i=0; i<nIn; i++){

   297     int c = zIn[i];

   298     if( c>='A' && c<='Z' ){

   299       zOut[i] = c - 'A' + 'a';

   300     }else{

   301       if( c>='0' && c<='9' ) hasDigit = 1;

   302       zOut[i] = c;

   303     }

   304   }

   305   mx = hasDigit ? 3 : 10;

   306   if( nIn>mx*2 ){

   307     for(j=mx, i=nIn-mx; i<nIn; i++, j++){

   308       zOut[j] = zOut[i];

   309     }

   310     i = j;

   311   }

   312   zOut[i] = 0;

   313   *pnOut = i;

   314 }

   315 

   316 

   317 /*

   318 ** Stem the input word zIn[0..nIn-1].  Store the output in zOut.

   319 ** zOut is at least big enough to hold nIn bytes.  Write the actual

   320 ** size of the output word (exclusive of the '\0' terminator) into *pnOut.

   321 **

   322 ** Any upper-case characters in the US-ASCII character set ([A-Z])

   323 ** are converted to lower case.  Upper-case UTF characters are

   324 ** unchanged.

   325 **

   326 ** Words that are longer than about 20 bytes are stemmed by retaining

   327 ** a few bytes from the beginning and the end of the word.  If the

   328 ** word contains digits, 3 bytes are taken from the beginning and

   329 ** 3 bytes from the end.  For long words without digits, 10 bytes

   330 ** are taken from each end.  US-ASCII case folding still applies.

   331 ** 

   332 ** If the input word contains not digits but does characters not 

   333 ** in [a-zA-Z] then no stemming is attempted and this routine just 

   334 ** copies the input into the input into the output with US-ASCII

   335 ** case folding.

   336 **

   337 ** Stemming never increases the length of the word.  So there is

   338 ** no chance of overflowing the zOut buffer.

   339 */

   340 static void porter_stemmer(const char *zIn, int nIn, char *zOut, int *pnOut){

   341   int i, j, c;

   342   char zReverse[28];

   343   char *z, *z2;

   344   if( nIn<3 || nIn>=sizeof(zReverse)-7 ){

   345     /* The word is too big or too small for the porter stemmer.

   346     ** Fallback to the copy stemmer */

   347     copy_stemmer(zIn, nIn, zOut, pnOut);

   348     return;

   349   }

   350   for(i=0, j=sizeof(zReverse)-6; i<nIn; i++, j--){

   351     c = zIn[i];

   352     if( c>='A' && c<='Z' ){

   353       zReverse[j] = c + 'a' - 'A';

   354     }else if( c>='a' && c<='z' ){

   355       zReverse[j] = c;

   356     }else{

   357       /* The use of a character not in [a-zA-Z] means that we fallback

   358       ** to the copy stemmer */

   359       copy_stemmer(zIn, nIn, zOut, pnOut);

   360       return;

   361     }

   362   }

   363   memset(&zReverse[sizeof(zReverse)-5], 0, 5);

   364   z = &zReverse[j+1];

   365 

   366 

   367   /* Step 1a */

   368   if( z[0]=='s' ){

   369     if(

   370      !stem(&z, "sess", "ss", 0) &&

   371      !stem(&z, "sei", "i", 0)  &&

   372      !stem(&z, "ss", "ss", 0)

   373     ){

   374       z++;

   375     }

   376   }

   377 

   378   /* Step 1b */  

   379   z2 = z;

   380   if( stem(&z, "dee", "ee", m_gt_0) ){

   381     /* Do nothing.  The work was all in the test */

   382   }else if( 

   383      (stem(&z, "gni", "", hasVowel) || stem(&z, "de", "", hasVowel))

   384       && z!=z2

   385   ){

   386      if( stem(&z, "ta", "ate", 0) ||

   387          stem(&z, "lb", "ble", 0) ||

   388          stem(&z, "zi", "ize", 0) ){

   389        /* Do nothing.  The work was all in the test */

   390      }else if( doubleConsonant(z) && (*z!='l' && *z!='s' && *z!='z') ){

   391        z++;

   392      }else if( m_eq_1(z) && star_oh(z) ){

   393        *(--z) = 'e';

   394      }

   395   }

   396 

   397   /* Step 1c */

   398   if( z[0]=='y' && hasVowel(z+1) ){

   399     z[0] = 'i';

   400   }

   401 

   402   /* Step 2 */

   403   switch( z[1] ){

   404    case 'a':

   405      stem(&z, "lanoita", "ate", m_gt_0) ||

   406      stem(&z, "lanoit", "tion", m_gt_0);

   407      break;

   408    case 'c':

   409      stem(&z, "icne", "ence", m_gt_0) ||

   410      stem(&z, "icna", "ance", m_gt_0);

   411      break;

   412    case 'e':

   413      stem(&z, "rezi", "ize", m_gt_0);

   414      break;

   415    case 'g':

   416      stem(&z, "igol", "log", m_gt_0);

   417      break;

   418    case 'l':

   419      stem(&z, "ilb", "ble", m_gt_0) ||

   420      stem(&z, "illa", "al", m_gt_0) ||

   421      stem(&z, "iltne", "ent", m_gt_0) ||

   422      stem(&z, "ile", "e", m_gt_0) ||

   423      stem(&z, "ilsuo", "ous", m_gt_0);

   424      break;

   425    case 'o':

   426      stem(&z, "noitazi", "ize", m_gt_0) ||

   427      stem(&z, "noita", "ate", m_gt_0) ||

   428      stem(&z, "rota", "ate", m_gt_0);

   429      break;

   430    case 's':

   431      stem(&z, "msila", "al", m_gt_0) ||

   432      stem(&z, "ssenevi", "ive", m_gt_0) ||

   433      stem(&z, "ssenluf", "ful", m_gt_0) ||

   434      stem(&z, "ssensuo", "ous", m_gt_0);

   435      break;

   436    case 't':

   437      stem(&z, "itila", "al", m_gt_0) ||

   438      stem(&z, "itivi", "ive", m_gt_0) ||

   439      stem(&z, "itilib", "ble", m_gt_0);

   440      break;

   441   }

   442 

   443   /* Step 3 */

   444   switch( z[0] ){

   445    case 'e':

   446      stem(&z, "etaci", "ic", m_gt_0) ||

   447      stem(&z, "evita", "", m_gt_0)   ||

   448      stem(&z, "ezila", "al", m_gt_0);

   449      break;

   450    case 'i':

   451      stem(&z, "itici", "ic", m_gt_0);

   452      break;

   453    case 'l':

   454      stem(&z, "laci", "ic", m_gt_0) ||

   455      stem(&z, "luf", "", m_gt_0);

   456      break;

   457    case 's':

   458      stem(&z, "ssen", "", m_gt_0);

   459      break;

   460   }

   461 

   462   /* Step 4 */

   463   switch( z[1] ){

   464    case 'a':

   465      if( z[0]=='l' && m_gt_1(z+2) ){

   466        z += 2;

   467      }

   468      break;

   469    case 'c':

   470      if( z[0]=='e' && z[2]=='n' && (z[3]=='a' || z[3]=='e')  && m_gt_1(z+4)  ){

   471        z += 4;

   472      }

   473      break;

   474    case 'e':

   475      if( z[0]=='r' && m_gt_1(z+2) ){

   476        z += 2;

   477      }

   478      break;

   479    case 'i':

   480      if( z[0]=='c' && m_gt_1(z+2) ){

   481        z += 2;

   482      }

   483      break;

   484    case 'l':

   485      if( z[0]=='e' && z[2]=='b' && (z[3]=='a' || z[3]=='i') && m_gt_1(z+4) ){

   486        z += 4;

   487      }

   488      break;

   489    case 'n':

   490      if( z[0]=='t' ){

   491        if( z[2]=='a' ){

   492          if( m_gt_1(z+3) ){

   493            z += 3;

   494          }

   495        }else if( z[2]=='e' ){

   496          stem(&z, "tneme", "", m_gt_1) ||

   497          stem(&z, "tnem", "", m_gt_1) ||

   498          stem(&z, "tne", "", m_gt_1);

   499        }

   500      }

   501      break;

   502    case 'o':

   503      if( z[0]=='u' ){

   504        if( m_gt_1(z+2) ){

   505          z += 2;

   506        }

   507      }else if( z[3]=='s' || z[3]=='t' ){

   508        stem(&z, "noi", "", m_gt_1);

   509      }

   510      break;

   511    case 's':

   512      if( z[0]=='m' && z[2]=='i' && m_gt_1(z+3) ){

   513        z += 3;

   514      }

   515      break;

   516    case 't':

   517      stem(&z, "eta", "", m_gt_1) ||

   518      stem(&z, "iti", "", m_gt_1);

   519      break;

   520    case 'u':

   521      if( z[0]=='s' && z[2]=='o' && m_gt_1(z+3) ){

   522        z += 3;

   523      }

   524      break;

   525    case 'v':

   526    case 'z':

   527      if( z[0]=='e' && z[2]=='i' && m_gt_1(z+3) ){

   528        z += 3;

   529      }

   530      break;

   531   }

   532 

   533   /* Step 5a */

   534   if( z[0]=='e' ){

   535     if( m_gt_1(z+1) ){

   536       z++;

   537     }else if( m_eq_1(z+1) && !star_oh(z+1) ){

   538       z++;

   539     }

   540   }

   541 

   542   /* Step 5b */

   543   if( m_gt_1(z) && z[0]=='l' && z[1]=='l' ){

   544     z++;

   545   }

   546 

   547   /* z[] is now the stemmed word in reverse order.  Flip it back

   548   ** around into forward order and return.

   549   */

   550   *pnOut = i = strlen(z);

   551   zOut[i] = 0;

   552   while( *z ){

   553     zOut[--i] = *(z++);

   554   }

   555 }

   556 

   557 /*

   558 ** Characters that can be part of a token.  We assume any character

   559 ** whose value is greater than 0x80 (any UTF character) can be

   560 ** part of a token.  In other words, delimiters all must have

   561 ** values of 0x7f or lower.

   562 */

   563 static const char isIdChar[] = {

   564 /* x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 xA xB xC xD xE xF */

   565     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,  /* 3x */

   566     0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 4x */

   567     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1,  /* 5x */

   568     0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,  /* 6x */

   569     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0,  /* 7x */

   570 };

   571 #define idChar(C)  (((ch=C)&0x80)!=0 || (ch>0x2f && isIdChar[ch-0x30]))

   572 #define isDelim(C) (((ch=C)&0x80)==0 && (ch<0x30 || !isIdChar[ch-0x30]))

   573 

   574 /*

   575 ** Extract the next token from a tokenization cursor.  The cursor must

   576 ** have been opened by a prior call to porterOpen().

   577 */

   578 static int porterNext(

   579   sqlite3_tokenizer_cursor *pCursor,  /* Cursor returned by porterOpen */

   580   const char **pzToken,               /* OUT: *pzToken is the token text */

   581   int *pnBytes,                       /* OUT: Number of bytes in token */

   582   int *piStartOffset,                 /* OUT: Starting offset of token */

   583   int *piEndOffset,                   /* OUT: Ending offset of token */

   584   int *piPosition                     /* OUT: Position integer of token */

   585 ){

   586   porter_tokenizer_cursor *c = (porter_tokenizer_cursor *) pCursor;

   587   const char *z = c->zInput;

   588 

   589   while( c->iOffset<c->nInput ){

   590     int iStartOffset, ch;

   591 

   592     /* Scan past delimiter characters */

   593     while( c->iOffset<c->nInput && isDelim(z[c->iOffset]) ){

   594       c->iOffset++;

   595     }

   596 

   597     /* Count non-delimiter characters. */

   598     iStartOffset = c->iOffset;

   599     while( c->iOffset<c->nInput && !isDelim(z[c->iOffset]) ){

   600       c->iOffset++;

   601     }

   602 

   603     if( c->iOffset>iStartOffset ){

   604       int n = c->iOffset-iStartOffset;

   605       if( n>c->nAllocated ){

   606         c->nAllocated = n+20;

   607         c->zToken = realloc(c->zToken, c->nAllocated);

   608         if( c->zToken==NULL ) return SQLITE_NOMEM;

   609       }

   610       porter_stemmer(&z[iStartOffset], n, c->zToken, pnBytes);

   611       *pzToken = c->zToken;

   612       *piStartOffset = iStartOffset;

   613       *piEndOffset = c->iOffset;

   614       *piPosition = c->iToken++;

   615       return SQLITE_OK;

   616     }

   617   }

   618   return SQLITE_DONE;

   619 }

   620 

   621 /*

   622 ** The set of routines that implement the porter-stemmer tokenizer

   623 */

   624 static const sqlite3_tokenizer_module porterTokenizerModule = {

   625   0,

   626   porterCreate,

   627   porterDestroy,

   628   porterOpen,

   629   porterClose,

   630   porterNext,

   631 };

   632 

   633 /*

   634 ** Allocate a new porter tokenizer.  Return a pointer to the new

   635 ** tokenizer in *ppModule

   636 */

   637 void sqlite3Fts1PorterTokenizerModule(

   638   sqlite3_tokenizer_module const**ppModule

   639 ){

   640   *ppModule = &porterTokenizerModule;

   641 }

   642 

   643 #endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS1) */