/*

 ** 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) */