path: root/mailnews/extensions/fts3/src/fts3_porter.c

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

/*
 * This file is based on the SQLite FTS3 Porter Stemmer implementation.
 *
 * This is an attempt to provide some level of full-text search to users of
 *  Thunderbird who use languages that are not space/punctuation delimited.
 *  This is accomplished by performing bi-gram indexing of characters fall
 *  into the unicode space occupied by character sets used in such languages.
 *
 * Bi-gram indexing means that given the string "12345" we would index the
 *  pairs "12", "23", "34", and "45" (with position information).  We do this
 *  because we are not sure where the word/semantic boundaries are in that
 *  string.  Then, when a user searches for "234" the FTS3 engine tokenizes the
 *  search query into "23" and "34".  Using special phrase-logic FTS3 requires
 *  the matches to have the tokens "23" and "34" adjacent to each other and in
 *  that order.  In theory if the user searched for "2345" we we could just
 *  search for "23 NEAR/2 34".  Unfortunately, NEAR does not imply ordering,
 *  so even though that would be more efficient, we would lose correctness
 *  and cannot do it.
 *
 * The efficiency and usability of bi-gram search assumes that the character
 *  space is large enough and actually observed bi-grams sufficiently
 *  distributed throughout the potential space so that the search bi-grams
 *  generated when the user issues a query find a 'reasonable' number of
 *  documents for each bi-gram match.
 *
 * Mozilla contributors:
 *   Makoto Kato <m_kato@ga2.so-net.ne.jp>
 *   Andrew Sutherland <asutherland@asutherland.org>
 */

/*
** The code in this file is only compiled if:
**
**     * The FTS3 module is being built as an extension
**       (in which case SQLITE_CORE is not defined), or
**
**     * The FTS3 module is being built into the core of
**       SQLite (in which case SQLITE_ENABLE_FTS3 is defined).
*/
#if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)


#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>

#include "fts3_tokenizer.h"

/* need some defined to compile without sqlite3 code */

#define sqlite3_malloc malloc
#define sqlite3_free free
#define sqlite3_realloc realloc

static const unsigned char sqlite3Utf8Trans1[] = {
  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,
};

typedef unsigned char u8;

/**
 * SQLite helper macro from sqlite3.c (really utf.c) to encode a unicode
 * character into utf8.
 *
 * @param zOut A pointer to the current write position that is updated by
 *     the routine.  At entry it should point to one-past the last valid
 *     encoded byte.  The same holds true at exit.
 * @param c The character to encode; this should be an unsigned int.
 */
#define WRITE_UTF8(zOut, c) {                          \
  if( c<0x0080 ){                                      \
    *zOut++ = (u8)(c&0xff);                            \
  }                                                    \
  else if( c<0x0800 ){                                 \
    *zOut++ = 0xC0 + (u8)((c>>6) & 0x1F);              \
    *zOut++ = 0x80 + (u8)(c & 0x3F);                   \
  }                                                    \
  else if( c<0x10000 ){                                \
    *zOut++ = 0xE0 + (u8)((c>>12) & 0x0F);             \
    *zOut++ = 0x80 + (u8)((c>>6) & 0x3F);              \
    *zOut++ = 0x80 + (u8)(c & 0x3F);                   \
  }else{                                               \
    *zOut++ = 0xf0 + (u8)((c>>18) & 0x07);             \
    *zOut++ = 0x80 + (u8)((c>>12) & 0x3F);             \
    *zOut++ = 0x80 + (u8)((c>>6) & 0x3F);              \
    *zOut++ = 0x80 + (u8)(c & 0x3F);                   \
  }                                                    \
}

/**
 * Fudge factor to avoid buffer overwrites when WRITE_UTF8 is involved.
 *
 * Our normalization table includes entries that may result in a larger
 *  utf-8 encoding.  Namely, 023a maps to 2c65.  This is a growth from 2 bytes
 *  as utf-8 encoded to 3 bytes.  This is currently the only transition possible
 *  because 1-byte encodings are known to stay 1-byte and our normalization
 *  table is 16-bit and so can't generate a 4-byte encoded output.
 *
 * For simplicity, we just multiple by 2 which covers the current case and
 *  potential growth for 2-byte to 4-byte growth.  We can afford to do this
 *  because we're not talking about a lot of memory here as a rule.
 */
#define MAX_UTF8_GROWTH_FACTOR 2

/**
 * Helper from sqlite3.c to read a single UTF8 character.
 *
 * The clever bit with multi-byte reading is that you keep going until you find
 *  a byte whose top bits are not '10'.  A single-byte UTF8 character will have
 *  '00' or '01', and a multi-byte UTF8 character must start with '11'.
 *
 * In the event of illegal UTF-8 this macro may read an arbitrary number of
 *  characters but will never read past zTerm.  The resulting character value
 *  of illegal UTF-8 can be anything, although efforts are made to return the
 *  illegal character (0xfffd) for UTF-16 surrogates.
 *
 * @param zIn A pointer to the current position that is updated by the routine,
 *     pointing at the start of the next character when the routine returns.
 * @param zTerm A pointer one past the end of the buffer.
 * @param c The 'unsigned int' to hold the resulting character value.  Do not
 *      use a short or a char.
 */
#define READ_UTF8(zIn, zTerm, c) {                         \
  c = *(zIn++);                                            \
  if( c>=0xc0 ){                                           \
    c = sqlite3Utf8Trans1[c-0xc0];                         \
    while( zIn!=zTerm && (*zIn & 0xc0)==0x80 ){            \
      c = (c<<6) + (0x3f & *(zIn++));                      \
    }                                                      \
    if( c<0x80                                             \
        || (c&0xFFFFF800)==0xD800                          \
        || (c&0xFFFFFFFE)==0xFFFE ){  c = 0xFFFD; }        \
  }                                                        \
}

/* end of compatible block to complie codes */

/*
** 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 */
  unsigned char *zToken;       /* storage for current token */
  int nAllocated;              /* space allocated to zToken buffer */
  /**
   * Store the offset of the second character in the bi-gram pair that we just
   *  emitted so that we can consider it being the first character in a bi-gram
   *  pair.
   * The value 0 indicates that there is no previous such character.  This is
   *  an acceptable sentinel value because the 0th offset can never be the
   *  offset of the second in a bi-gram pair.
   *
   * For example, let us say we are tokenizing a string of 4 CJK characters 
   *  represented by the byte-string "11223344" where each repeated digit
   *  indicates 2-bytes of storage used to encode the character in UTF-8.
   *  (It actually takes 3, btw.)  Then on the passes to emit each token,
   *  the iOffset and iPrevGigramOffset values at entry will be:
   *
   * 1122: iOffset = 0, iPrevBigramOffset = 0
   * 2233: iOffset = 4, iPrevBigramOffset = 2
   * 3344: iOffset = 6, iPrevBigramOffset = 4
   * (nothing will be emitted): iOffset = 8, iPrevBigramOffset = 6
   */
  int iPrevBigramOffset;       /* previous result was bi-gram */
} porter_tokenizer_cursor;


/* Forward declaration */
static const sqlite3_tokenizer_module porterTokenizerModule;

/* from normalize.c */
extern unsigned int normalize_character(const unsigned int c);

/*
** 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;
  c->iPrevBigramOffset = 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;
}

/**
 * Voiced sound mark is only on Japanese.  It is like accent.  It combines with
 * previous character.  Example, "サ" (Katakana) with "゛" (voiced sound mark) is
 * "ザ".  Although full-width character mapping has combined character like "ザ",
 * there is no combined character on half-width Katanaka character mapping.
 */
static int isVoicedSoundMark(const unsigned int c)
{
  if (c == 0xff9e || c == 0xff9f || c == 0x3099 || c == 0x309a)
    return 1;
  return 0;
}

/**
 * How many unicode characters to take from the front and back of a term in
 * |copy_stemmer|.
 */
#define COPY_STEMMER_COPY_HALF_LEN 10

/**
 * Normalizing but non-stemming term copying.
 *
 * The original function would take 10 bytes from the front and 10 bytes from
 * the back if there were no digits in the string and it was more than 20
 * bytes long.  If there were digits involved that would decrease to 3 bytes
 * from the front and 3 from the back.  This would potentially corrupt utf-8
 * encoded characters, which is fine from the perspective of the FTS3 logic.
 *
 * In our revised form we now operate on a unicode character basis rather than
 * a byte basis.  Additionally we use the same length limit even if there are
 * digits involved because it's not clear digit token-space reduction is saving
 * us from anything and could be hurting.  Specifically, if no one is ever
 * going to search on things with digits, then we should just remove them.
 * Right now, the space reduction is going to increase false positives when
 * people do search on them and increase the number of collisions sufficiently
 * to make it really expensive.  The caveat is there will be some increase in
 * index size which could be meaningful if people are receiving lots of emails
 * full of distinct numbers.
 *
 * In order to do the copy-from-the-front and copy-from-the-back trick, once
 * we reach N characters in, we set zFrontEnd to the current value of zOut
 * (which represents the termination of the first part of the result string)
 * and set zBackStart to the value of zOutStart.  We then advanced zBackStart
 * along a character at a time as we write more characters.  Once we have
 * traversed the entire string, if zBackStart > zFrontEnd, then we know
 * the string should be shrunk using the characters in the two ranges.
 *
 * (It would be faster to scan from the back with specialized logic but that
 * particular logic seems easy to screw up and we don't have unit tests in here
 * to the extent required.)
 *
 * @param zIn Input string to normalize and potentially shrink.
 * @param nBytesIn The number of bytes in zIn, distinct from the number of
 *     unicode characters encoded in zIn.
 * @param zOut The string to write our output into.  This must have at least
 *     nBytesIn * MAX_UTF8_GROWTH_FACTOR in order to compensate for
 *     normalization that results in a larger utf-8 encoding.
 * @param pnBytesOut Integer to write the number of bytes in zOut into.
 */
static void copy_stemmer(const unsigned char *zIn, const int nBytesIn,
                         unsigned char *zOut, int *pnBytesOut){
  const unsigned char *zInTerm = zIn + nBytesIn;
  unsigned char *zOutStart = zOut;
  unsigned int c;
  unsigned int charCount = 0;
  unsigned char *zFrontEnd = NULL, *zBackStart = NULL;
  unsigned int trashC;

  /* copy normalized character */
  while (zIn < zInTerm) {
    READ_UTF8(zIn, zInTerm, c);
    c = normalize_character(c);

    /* ignore voiced/semi-voiced sound mark */
    if (!isVoicedSoundMark(c)) {
      /* advance one non-voiced sound mark character. */
      if (zBackStart)
        READ_UTF8(zBackStart, zOut, trashC);

      WRITE_UTF8(zOut, c);
      charCount++;
      if (charCount == COPY_STEMMER_COPY_HALF_LEN) {
        zFrontEnd = zOut;
        zBackStart = zOutStart;
      }
    }
  }

  /* if we need to shrink the string, transplant the back bytes */
  if (zBackStart > zFrontEnd) { /* this handles when both are null too */
    size_t backBytes = zOut - zBackStart;
    memmove(zFrontEnd, zBackStart, backBytes);
    zOut = zFrontEnd + backBytes;
  }
  *zOut = 0;
  *pnBytesOut = zOut - zOutStart;
}


/*
** 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 unsigned char *zIn,
  unsigned int nIn,
  unsigned char *zOut,
  int *pnOut
){
  unsigned int i, j, c;
  char zReverse[28];
  char *z, *z2;
  const unsigned char *zTerm = zIn + nIn;
  const unsigned char *zTmp = zIn;

  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 (j = sizeof(zReverse) - 6; zTmp < zTerm; j--) {
    READ_UTF8(zTmp, zTerm, c);
    c = normalize_character(c);
    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':
     (void) (stem(&z, "lanoita", "ate", m_gt_0) ||
             stem(&z, "lanoit", "tion", m_gt_0));
     break;
   case 'c':
     (void) (stem(&z, "icne", "ence", m_gt_0) ||
             stem(&z, "icna", "ance", m_gt_0));
     break;
   case 'e':
     (void) (stem(&z, "rezi", "ize", m_gt_0));
     break;
   case 'g':
     (void) (stem(&z, "igol", "log", m_gt_0));
     break;
   case 'l':
     (void) (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':
     (void) (stem(&z, "noitazi", "ize", m_gt_0) ||
             stem(&z, "noita", "ate", m_gt_0) ||
             stem(&z, "rota", "ate", m_gt_0));
     break;
   case 's':
     (void) (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':
     (void) (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':
     (void) (stem(&z, "etaci", "ic", m_gt_0) ||
             stem(&z, "evita", "", m_gt_0)   ||
             stem(&z, "ezila", "al", m_gt_0));
     break;
   case 'i':
     (void) (stem(&z, "itici", "ic", m_gt_0));
     break;
   case 'l':
     (void) (stem(&z, "laci", "ic", m_gt_0) ||
             stem(&z, "luf", "", m_gt_0));
     break;
   case 's':
     (void) (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' ){
         (void) (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' ){
       (void) (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':
     (void) (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++);
  }
}

/**
 * Indicate whether characters in the 0x30 - 0x7f region can be part of a token.
 * Letters and numbers can; punctuation (and 'del') can't.
 */
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 */
};

/**
 * Test whether a character is a (non-ascii) space character or not.  isDelim
 *  uses the existing porter stemmer logic for anything in the ASCII (< 0x80)
 *  space which covers 0x20.
 *
 * 0x2000-0x206F is the general punctuation table.  0x2000 - 0x200b are spaces.
 *  The spaces 0x2000 - 0x200a are all defined as roughly equivalent to a
 *  standard 0x20 space.  0x200b is a "zero width space" (ZWSP) and not like an
 *  0x20 space.  0x202f is a narrow no-break space and roughly equivalent to an
 *  0x20 space.  0x205f is a "medium mathematical space" and defined as roughly
 *  equivalent to an 0x20 space.
 */
#define IS_UNI_SPACE(x) (((x)>=0x2000&&(x)<=0x200a) || (x)==0x202f || (x)==0x205f)
/**
 * What we are checking for:
 * - 0x3001: Ideographic comma (-> 0x2c ',')
 * - 0x3002: Ideographic full stop (-> 0x2e '.')
 * - 0xff0c: fullwidth comma (~ wide 0x2c ',')
 * - 0xff0e: fullwidth full stop (~ wide 0x2e '.')
 * - 0xff61: halfwidth ideographic full stop (~ narrow 0x3002)
 * - 0xff64: halfwidth ideographic comma (~ narrow 0x3001)
 *
 * It is possible we should be treating other things as delimiters!
 */
#define IS_JA_DELIM(x) (((x)==0x3001)||((x)==0xFF64)||((x)==0xFF0E)||((x)==0x3002)||((x)==0xFF61)||((x)==0xFF0C))

/**
 * The previous character was a delimeter (which includes the start of the
 *  string).
 */
#define BIGRAM_RESET   0
/**
 * The previous character was a CJK character and we have only seen one of them.
 *  If we had seen more than one in a row it would be the BIGRAM_USE state.
 */
#define BIGRAM_UNKNOWN 1
/**
 * We have seen two or more CJK characters in a row.
 */
#define BIGRAM_USE     2
/**
 * The previous character was ASCII or something in the unicode general scripts
 *  area that we do not believe is a delimeter.  We call it 'alpha' as in
 *  alphabetic/alphanumeric and something that should be tokenized based on
 *  delimiters rather than on a bi-gram basis.
 */
#define BIGRAM_ALPHA   3

static int isDelim(
  const unsigned char *zCur,    /* IN: current pointer of token */
  const unsigned char *zTerm,   /* IN: one character beyond end of token */
  int *len,                     /* OUT: analyzed bytes in this token */
  int *state                    /* IN/OUT: analyze state */
){
  const unsigned char *zIn = zCur;
  unsigned int c;
  int delim;

  /* get the unicode character to analyze */
  READ_UTF8(zIn, zTerm, c);
  c = normalize_character(c);
  *len = zIn - zCur;

  /* ASCII character range has rule */
  if( c < 0x80 ){
    // This is original porter stemmer isDelim logic.
    // 0x0 - 0x1f are all control characters, 0x20 is space, 0x21-0x2f are
    //  punctuation.
    delim = (c < 0x30 || !porterIdChar[c - 0x30]);
    // cases: "&a", "&."
    if (*state == BIGRAM_USE || *state == BIGRAM_UNKNOWN ){
      /* previous maybe CJK and current is ascii */
      *state = BIGRAM_ALPHA; /*ascii*/
      delim = 1; /* must break */
    } else if (delim == 1) {
      // cases: "a.", ".."
      /* this is delimiter character */
      *state = BIGRAM_RESET; /*reset*/
    } else {
      // cases: "aa", ".a"
      *state = BIGRAM_ALPHA; /*ascii*/
    }
    return delim;
  }

  // (at this point we must be a non-ASCII character)

  /* voiced/semi-voiced sound mark is ignore */
  if (isVoicedSoundMark(c) && *state != BIGRAM_ALPHA) {
    /* ignore this because it is combined with previous char */
   return 0;
  }

  /* this isn't CJK range, so return as no delim */
  // Anything less than 0x2000 (except to U+0E00-U+0EFF and  U+1780-U+17FF) 
  // is the general scripts area and should not be bi-gram indexed.
  // 0xa000 - 0a4cf is the Yi area.  It is apparently a phonetic language whose
  //  usage does not appear to have simple delimeter rules, so we're leaving it
  //  as bigram processed.  This is a guess, if you know better, let us know.
  //  (We previously bailed on this range too.)
  // Addition, U+0E00-U+0E7F is Thai, U+0E80-U+0EFF is Laos,
  // and U+1780-U+17FF is Khmer.  It is no easy way to break each word.
  // So these should use bi-gram too. 
  // cases: "aa", ".a", "&a"
  if (c < 0xe00 ||
     (c >= 0xf00 && c < 0x1780) ||
     (c >= 0x1800 && c < 0x2000)) {
    *state = BIGRAM_ALPHA; /* not really ASCII but same idea; tokenize it */
    return 0;
  }

  // (at this point we must be a bi-grammable char or delimiter)

  /* this is space character or delim character */
  // cases: "a.", "..", "&."
  if( IS_UNI_SPACE(c) || IS_JA_DELIM(c) ){
    *state = BIGRAM_RESET; /* reset */
    return 1; /* it actually is a delimiter; report as such */
  }

  // (at this point we must be a bi-grammable char)

  // cases: "a&"
  if( *state==BIGRAM_ALPHA ){
    /* Previous is ascii and current maybe CJK */
    *state = BIGRAM_UNKNOWN; /* mark as unknown */
    return 1; /* break to emit the ASCII token*/
  }

  /* We have no rule for CJK!. use bi-gram */
  // cases: "&&"
  if( *state==BIGRAM_UNKNOWN || *state==BIGRAM_USE ){
    /* previous state is unknown.  mark as bi-gram */
    *state = BIGRAM_USE;
    return 1; /* break to emit the digram */
  }

  // cases: ".&" (*state == BIGRAM_RESET)
  *state = BIGRAM_UNKNOWN; /* mark as unknown */
  return 0; /* no need to break; nothing to emit */
}

/**
 * Generate a new token.  There are basically three types of token we can
 *  generate:
 * - A porter stemmed token.  This is a word entirely comprised of ASCII
 *    characters.  We run the porter stemmer algorithm against the word.
 *    Because we have no way to know what is and is not an English word
 *    (the only language for which the porter stemmer was designed), this
 *    could theoretically map multiple words that are not variations of the
 *    same word down to the same root, resulting in potentially unexpected
 *    result inclusions in the search results.  We accept this result because
 *    there's not a lot we can do about it and false positives are much
 *    better than false negatives.
 * - A copied token; case/accent-folded but not stemmed.  We call the porter
 *    stemmer for all non-CJK cases and it diverts to the copy stemmer if it
 *    sees any non-ASCII characters (after folding) or if the string is too
 *    long.  The copy stemmer will shrink the string if it is deemed too long.
 * - A bi-gram token; two CJK-ish characters.  For query reasons we generate a
 *    series of overlapping bi-grams.  (We can't require the user to start their
 *    search based on the arbitrary context of the indexed documents.)
 *
 * It may be useful to think of this function as operating at the points between
 *  characters.  While we are considering the 'current' character (the one after
 *  the 'point'), we are also interested in the 'previous' character (the one
 *  preceding the point).
 * At any 'point', there are a number of possible situations which I will
 *  illustrate with pairs of characters. 'a' means alphanumeric ASCII or a
 *  non-ASCII character that is not bi-grammable or a delimeter, '.'
 *  means a delimiter (space or punctuation), '&' means a bi-grammable
 *  character.
 * - aa: We are in the midst of a token.  State remains BIGRAM_ALPHA.
 * - a.: We will generate a porter stemmed or copied token.  State was
 *        BIGRAM_ALPHA, gets set to BIGRAM_RESET.
 * - a&: We will generate a porter stemmed or copied token; we will set our
 *        state to BIGRAM_UNKNOWN to indicate we have seen one bigram character
 *        but that it is not yet time to emit a bigram.
 * - .a: We are starting a token.  State was BIGRAM_RESET, gets set to
 *        BIGRAM_ALPHA.
 * - ..: We skip/eat the delimeters.  State stays BIGRAM_RESET.
 * - .&: State set to BIGRAM_UNKNOWN to indicate we have seen one bigram char.
 * - &a: If the state was BIGRAM_USE, we generate a bi-gram token.  If the state
 *        was BIGRAM_UNKNOWN we had only seen one CJK character and so don't do
 *        anything.  State is set to BIGRAM_ALPHA.
 * - &.: Same as the "&a" case, but state is set to BIGRAM_RESET.
 * - &&: We will generate a bi-gram token.  State was either BIGRAM_UNKNOWN or
 *        BIGRAM_USE, gets set to BIGRAM_USE.
 */
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 unsigned char *z = (unsigned char *) c->zInput;
  int len = 0;
  int state;

  while( c->iOffset < c->nInput ){
    int iStartOffset, numChars;

    /*
     * This loop basically has two modes of operation:
     * - general processing (iPrevBigramOffset == 0 here)
     * - CJK processing (iPrevBigramOffset != 0 here)
     *
     * In an general processing pass we skip over all the delimiters, leaving us
     *  at a character that promises to produce a token.  This could be a CJK
     *  token (state == BIGRAM_USE) or an ALPHA token (state == BIGRAM_ALPHA).
     * If it was a CJK token, we transition into CJK state for the next loop.
     * If it was an alpha token, our current offset is pointing at a delimiter
     *  (which could be a CJK character), so it is good that our next pass
     *  through the function and loop will skip over any delimiters.  If the
     *  delimiter we hit was a CJK character, the next time through we will
     *  not treat it as a delimiter though; the entry state for that scan is
     *  BIGRAM_RESET so the transition is not treated as a delimiter!
     * 
     * The CJK pass always starts with the second character in a bi-gram emitted
     *  as a token in the previous step.  No delimiter skipping is required
     *  because we know that first character might produce a token for us.  It
     *  only 'might' produce a token because the previous pass performed no
     *  lookahead and cannot be sure it is followed by another CJK character.
     *  This is why 
     */

    // If we have a previous bigram offset
    if (c->iPrevBigramOffset == 0) {
      /* Scan past delimiter characters */
      state = BIGRAM_RESET; /* reset */
      while (c->iOffset < c->nInput &&
             isDelim(z + c->iOffset, z + c->nInput, &len, &state)) {
        c->iOffset += len;
      }

    } else {
      /* for bigram indexing, use previous offset */
      c->iOffset = c->iPrevBigramOffset;
    }

    /* Count non-delimiter characters. */
    iStartOffset = c->iOffset;
    numChars = 0;

    // Start from a reset state.  This means the first character we see
    //  (which will not be a delimiter) determines which of ALPHA or CJK modes
    //  we are operating in.  (It won't be a delimiter because in a 'general'
    //  pass as defined above, we will have eaten all the delimiters, and in
    //  a CJK pass we are guaranteed that the first character is CJK.)
    state = BIGRAM_RESET; /* state is reset */
    // Advance until it is time to emit a token.
    // For ALPHA characters, this means advancing until we encounter a delimiter
    //  or a CJK character.  iOffset will be pointing at the delimiter or CJK
    //  character, aka one beyond the last ALPHA character.
    // For CJK characters this means advancing until we encounter an ALPHA
    //  character, a delimiter, or we have seen two consecutive CJK
    //  characters.  iOffset points at the ALPHA/delimiter in the first 2 cases
    //  and the second of two CJK characters in the last case.
    // Because of the way this loop is structured, iOffset is only updated
    //  when we don't terminate.  However, if we terminate, len still contains
    //  the number of bytes in the character found at iOffset.  (This is useful
    //  in the CJK case.)
    while (c->iOffset < c->nInput &&
           !isDelim(z + c->iOffset, z + c->nInput, &len, &state)) {
      c->iOffset += len;
      numChars++;
    }

    if (state == BIGRAM_USE) {
      /* Split word by bigram */
      // Right now iOffset is pointing at the second character in a pair.
      //  Save this offset so next-time through we start with that as the
      //  first character.
      c->iPrevBigramOffset = c->iOffset;
      // And now advance so that iOffset is pointing at the character after
      //  the second character in the bi-gram pair.  Also count the char.
      c->iOffset += len;
      numChars++;
    } else {
      /* Reset bigram offset */
      c->iPrevBigramOffset = 0;
    }

    /* We emit a token if:
     *  - there are two ideograms together,
     *  - there are three chars or more,
     *  - we think this is a query and wildcard magic is desired.
     * We think is a wildcard query when we have a single character, it starts
     *  at the start of the buffer, it's CJK, our current offset is one shy of
     *  nInput and the character at iOffset is '*'.  Because the state gets
     *  clobbered by the incidence of '*' our requirement for CJK is that the
     *  implied character length is at least 3 given that it takes at least 3
     *  bytes to encode to 0x2000.
     */
    // It is possible we have no token to emit here if iPrevBigramOffset was not
    //  0 on entry and there was no second CJK character.  iPrevBigramOffset
    //  will now be 0 if that is the case (and c->iOffset == iStartOffset).
    if (// allow two-character words only if in bigram
        (numChars == 2 && state == BIGRAM_USE) ||
        // otherwise, drop two-letter words (considered stop-words)
        (numChars >=3) ||
        // wildcard case:
        (numChars == 1 && iStartOffset == 0 &&
         (c->iOffset >= 3) &&
         (c->iOffset == c->nInput - 1) &&
         (z[c->iOffset] == '*'))) {
      /* figure out the number of bytes to copy/stem */
      int n = c->iOffset - iStartOffset;
      /* make sure there is enough buffer space */
      if (n * MAX_UTF8_GROWTH_FACTOR > c->nAllocated) {
        c->nAllocated = n * MAX_UTF8_GROWTH_FACTOR + 20;
        c->zToken = sqlite3_realloc(c->zToken, c->nAllocated);
        if (c->zToken == NULL)
          return SQLITE_NOMEM;
      }

      if (state == BIGRAM_USE) {
        /* This is by bigram. So it is unnecessary to convert word */
        copy_stemmer(&z[iStartOffset], n, c->zToken, pnBytes);
      } else {
        porter_stemmer(&z[iStartOffset], n, c->zToken, pnBytes);
      }
      *pzToken = (const char*)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 sqlite3Fts3PorterTokenizerModule(
  sqlite3_tokenizer_module const**ppModule
){
  *ppModule = &porterTokenizerModule;
}

#endif /* !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) */