path: root/comm/mailnews/extensions/fts3/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
** consonant.
*/
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 precedes 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 delimiter (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 delimiter.  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 delimiter 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 delimiter, '.'
 *  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 delimiters.  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) */