// This file is part of The New Aspell

// Copyright (C) 2004 by Kevin Atkinson under the GNU LGPL

// license version 2.0 or 2.1.  You should have received a copy of the

// LGPL license along with this library if you did not you can find it

// at http://www.gnu.org/.

//

// This code is based on the the MySpell affix code:

//

/*

 * Copyright 2002 Kevin B. Hendricks, Stratford, Ontario, Canada And

 * Contributors.  All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 *

 * 1. Redistributions of source code must retain the above copyright

 *    notice, this list of conditions and the following disclaimer.

 *

 * 2. Redistributions in binary form must reproduce the above copyright

 *    notice, this list of conditions and the following disclaimer in the

 *    documentation and/or other materials provided with the distribution.

 *

 * 3. All modifications to the source code must be clearly marked as

 *    such.  Binary redistributions based on modified source code

 *    must be clearly marked as modified versions in the documentation

 *    and/or other materials provided with the distribution.

 *

 * THIS SOFTWARE IS PROVIDED BY KEVIN B. HENDRICKS AND CONTRIBUTORS

 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS

 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL

 * KEVIN B. HENDRICKS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,

 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,

 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)

 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT

 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY

 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF

 * SUCH DAMAGE.

 *

 */

#include <cstdlib>

#include <cstring>

#include <cstdio>

//#include "iostream.hpp"

#include "affix.hpp"

#include "errors.hpp"

#include "getdata.hpp"

#include "parm_string.hpp"

#include "check_list.hpp"

#include "speller_impl.hpp"

#include "vararray.hpp"

#include "lsort.hpp"

#include "hash-t.hpp"

#include "gettext.h"

using namespace std;

namespace aspeller {

typedef unsigned char byte;

static char EMPTY[1] = {0};

//////////////////////////////////////////////////////////////////////

//

// Entry struct definations

//

struct Conds

{

  char * str;

  unsigned num;

  char conds[SETSIZE];

  char get(byte i) const {return conds[i];}

};

struct AffEntry

{

  const char *   appnd;

  const char *   strip;

  byte           appndl;

  byte           stripl;

  byte           xpflg;

  char           achar;

  const Conds *  conds;

  //unsigned int numconds;

  //char         conds[SETSIZE];

};

// A Prefix Entry

struct PfxEntry : public AffEntry

{

  PfxEntry * next;

  PfxEntry * next_eq;

  PfxEntry * next_ne;

  PfxEntry * flag_next;

  PfxEntry() {}

  bool check(const LookupInfo &, const AffixMgr * pmyMgr,

             ParmString, CheckInfo &, GuessInfo *, bool cross = true) const;

  inline bool          allow_cross() const { return ((xpflg & XPRODUCT) != 0); }

  inline byte flag() const { return achar;  }

  inline const char *  key() const  { return appnd;  }

  bool applicable(SimpleString) const;

  SimpleString add(SimpleString, ObjStack & buf) const;

};

// A Suffix Entry

struct SfxEntry : public AffEntry

{

  const char * rappnd; // this is set in AffixMgr::build_sfxlist

  SfxEntry *   next;

  SfxEntry *   next_eq;

  SfxEntry *   next_ne;

  SfxEntry *   flag_next;

  SfxEntry() {}

  bool check(const LookupInfo &, ParmString, CheckInfo &, GuessInfo *,

             int optflags, AffEntry * ppfx);

  inline bool          allow_cross() const { return ((xpflg & XPRODUCT) != 0); }

  inline byte flag() const { return achar;  }

  inline const char *  key() const  { return rappnd; } 

  bool applicable(SimpleString) const;

  SimpleString add(SimpleString, ObjStack & buf, int limit, SimpleString) const;

};

//////////////////////////////////////////////////////////////////////

//

// Utility functions declarations

//

/* return 1 if s1 is subset of s2 */

static bool isSubset(const char * s1, const char * s2)

{

  while( *s1 && (*s1 == *s2) ) {

    s1++;

    s2++;

  }

  return (*s1 == '\0');

}

// return 1 if s1 (reversed) is a leading subset of end of s2

static bool isRevSubset(const char * s1, const char * end_of_s2, int len)

{

  while( (len > 0) && *s1 && (*s1 == *end_of_s2) ) {

    s1++;

    end_of_s2--;

    len --;

  }

  return (*s1 == '\0');

}

template <class T>

struct AffixLess

{

  bool operator() (T * x, T * y) const {return strcmp(x->key(),y->key()) < 0;}

aspeller::AffixLess<aspeller::PfxEntry>::operator()(aspeller::PfxEntry*, aspeller::PfxEntry*) const

Line

Count

Source

167

6.18k

  bool operator() (T * x, T * y) const {return strcmp(x->key(),y->key()) < 0;}

aspeller::AffixLess<aspeller::SfxEntry>::operator()(aspeller::SfxEntry*, aspeller::SfxEntry*) const

Line

Count

Source

167

6.07M

  bool operator() (T * x, T * y) const {return strcmp(x->key(),y->key()) < 0;}

};

// struct StringLookup {

//   struct Parms {

//     typedef const char * Value;

//     typedef const char * Key;

//     static const bool is_multi = false;

//     hash<const char *> hfun;

//     size_t hash(const char * s) {return hfun(s);}

//     bool equal(const char * x, const char * y) {return strcmp(x,y) == 0;}

//     const char * key(const char * c) {return c;}

//   };

//   typedef HashTable<Parms> Lookup;

//   Lookup lookup;

//   ObjStack * data_buf;

//   StringLookup(ObjStack * b) : data_buf(b) {}

//   const char * dup(const char * orig) {

//     pair<Lookup::iterator, bool> res = lookup.insert(orig);

//     if (res.second) *res.first = data_buf->dup(orig);

//     return *res.first;

//     //return data_buf->dup(orig);

//   }

// };

struct CondsLookupParms {

  typedef const Conds * Value;

  typedef const char * Key;

  static const bool is_multi = false;

  acommon::hash<const char *> hfun;

  size_t hash(const char * s) {return hfun(s);}

  bool equal(const char * x, const char * y) {return strcmp(x,y) == 0;}

  const char * key(const Conds * c) {return c->str;}

};

typedef HashTable<CondsLookupParms> CondsLookup;

// normalizes and checks the cond_str

// returns the length of the new string or -1 if invalid

static int normalize_cond_str(char * str)

{

  char * s = str;

  char * d = str;

  while (*s) {

    if (*s != '[') {

      *d++ = *s++;

    } else if (s[1] == '\0' || s[1] == ']') {

      return -1;

    } else if (s[2] == ']') {

      *d++ = s[1];

      s += 3;

    } else {

      *d++ = *s++;

      if (*s == '^') *d++ = *s++;

      while (*s != ']') {

        if (*s == '\0' || *s == '[') return -1;

        char * min = s;

        for (char * i = s + 1; *i != ']'; ++i) {

          if ((byte)*i < (byte)*min) min = i;}

        char c = *s;

        *d++ = *min;

        *min = c;

        ++s;

      }

      *d++ = *s++;

    }

  }

  *d = '\0';

  return d - str;

}

static void encodeit(CondsLookup &, ObjStack &, 

                     AffEntry * ptr, char * cs);

//////////////////////////////////////////////////////////////////////

//

// Affix Manager

//

PosibErr<void> AffixMgr::setup(ParmString affpath, Conv & iconv)

{

  // register hash manager and load affix data from aff file

  //cpdmin = 3;  // default value

  max_strip_ = 0;

  for (int i=0; i < SETSIZE; i++) {

    pStart[i] = NULL;

    sStart[i] = NULL;

    pFlag[i] = NULL;

    sFlag[i] = NULL;

    max_strip_f[i] = 0;

  }

  return parse_file(affpath, iconv);

}

AffixMgr::AffixMgr(const Language * l) 

  : lang(l), data_buf(1024*16) {}

AffixMgr::~AffixMgr() {}

static inline void max_(int & lhs, int rhs) 

{

  if (lhs < rhs) lhs = rhs;

}

// read in aff file and build up prefix and suffix entry objects 

PosibErr<void> AffixMgr::parse_file(const char * affpath, Conv & iconv)

{

  // io buffers

  String buf; DataPair dp;

  CondsLookup conds_lookup;

  // open the affix file

  affix_file = data_buf.dup(affpath);

  FStream afflst;

  RET_ON_ERR(afflst.open(affpath,"r"));

  // step one is to parse the affix file building up the internal

  // affix data structures

  // read in each line ignoring any that do not

  // start with a known line type indicator

  char prev_aff = '\0';

  while (getdata_pair(afflst,dp,buf)) {

    char affix_type = ' ';

    /* parse in the name of the character set used by the .dict and .aff */

    if (dp.key == "SET") {

      String buf;

      encoding = data_buf.dup(fix_encoding_str(dp.value, buf));

      if (strcmp(encoding, lang->data_encoding()) != 0)

        return make_err(incorrect_encoding, affix_file, lang->data_encoding(), encoding);

    }

    /* parse in the flag used by the controlled compound words */

    //else if (d.key == "COMPOUNDFLAG")

    //  compound = data_buf.dup(d.value);

    /* parse in the flag used by the controlled compound words */

    //else if (d.key == "COMPOUNDMIN")

    //  cpdmin = atoi(d.value); // FiXME

    //else if (dp.key == "TRY" || dp.key == "REP");

    else if (dp.key == "PFX" || dp.key == "SFX")

      affix_type = dp.key[0];

    if (affix_type == ' ') continue;

    //

    // parse this affix: P - prefix, S - suffix

    //

    int numents = 0;      // number of affentry structures to parse

    char achar='\0';      // affix char identifier

    short xpflg=0;

    AffEntry * nptr;

    {

      // split affix header line into pieces

      split(dp);

      if (dp.key.empty()) goto error;

      // key is affix char

      const char * astr = iconv(dp.key);

      if (astr[0] == '\0' || astr[1] != '\0') goto error;

      achar = astr[0];

      if (achar == prev_aff) goto error_count;

      prev_aff = achar;

      split(dp);

      if (dp.key.size != 1 || 

          !(dp.key[0] == 'Y' || dp.key[0] == 'N')) goto error;

      // key is cross product indicator 

      if (dp.key[0] == 'Y') xpflg = XPRODUCT;

      split(dp);

      if (dp.key.empty()) goto error;

      // key is number of affentries

      numents = atoi(dp.key); 

      for (int j = 0; j < numents; j++) {

        getdata_pair(afflst, dp, buf);

        if (affix_type == 'P') {

          nptr = (AffEntry *) data_buf.alloc_bottom(sizeof(PfxEntry));

          new (nptr) PfxEntry;

        } else {

          nptr = (AffEntry *) data_buf.alloc_bottom(sizeof(SfxEntry));

          new (nptr) SfxEntry;

        }

        nptr->xpflg = xpflg;

        split(dp);

        if (dp.key.empty()) goto error;

        // key is affix charter

        if (iconv(dp.key)[0] != achar) goto error_count;

        nptr->achar = achar;

        split(dp);

        if (dp.key.empty()) goto error;

        // key is strip 

        if (dp.key != "0") {

          ParmString s0(iconv(dp.key));

          max_(max_strip_, s0.size());

          max_(max_strip_f[(byte)achar], s0.size());

          nptr->strip = data_buf.dup(s0);

          nptr->stripl = s0.size();

        } else {

          nptr->strip  = "";

          nptr->stripl = 0;

        }

        split(dp);

        if (dp.key.empty()) goto error;

        // key is affix string or 0 for null

        if (dp.key != "0") {

          nptr->appnd  = data_buf.dup(iconv(dp.key));

          nptr->appndl = strlen(nptr->appnd);

        } else {

          nptr->appnd  = "";

          nptr->appndl = 0;

        }

        split(dp);

        if (dp.key.empty()) goto error;

        // key is the conditions descriptions

        char * cond = iconv(dp.key);

        int cond_len = normalize_cond_str(cond);

        if (cond_len < 0)

          return (make_err(invalid_cond, MsgConv(lang)(cond))

                  .with_file(affix_file, dp.line_num));

        if (nptr->stripl != 0) {

          char * cc = cond;

          if (affix_type == 'S') cc += cond_len - nptr->stripl;

          if (cond_len < nptr->stripl || 

              memcmp(cc, nptr->strip, nptr->stripl) != 0)

            return (make_err(invalid_cond_strip, 

                             MsgConv(lang)(cond), MsgConv(lang)(nptr->strip))

                    .with_file(affix_file, dp.line_num));

        }

        encodeit(conds_lookup, data_buf, nptr, cond);

        // now create SfxEntry or PfxEntry objects and use links to

        // build an ordered (sorted by affix string) list

        if (affix_type == 'P')

          build_pfxlist(static_cast<PfxEntry *>(nptr));

        else

          build_sfxlist(static_cast<SfxEntry *>(nptr)); 

      }

    }

    continue;

  error:

    return make_err(corrupt_affix, MsgConv(lang)(achar)).with_file(affix_file, dp.line_num);

  error_count:

    return make_err(corrupt_affix, MsgConv(lang)(achar), 

                    _("Possibly incorrect count.")).with_file(affix_file, dp.line_num);

  }

  afflst.close();

  // now we can speed up performance greatly taking advantage of the 

  // relationship between the affixes and the idea of "subsets".

  // View each prefix as a potential leading subset of another and view

  // each suffix (reversed) as a potential trailing subset of another.

  // To illustrate this relationship if we know the prefix "ab" is

  // found in the word to examine, only prefixes that "ab" is a

  // leading subset of need be examined.  Furthermore is "ab" is not

  // present then none of the prefixes that "ab" is is a subset need

  // be examined.

  // The same argument goes for suffix string that are reversed.

  // Then to top this off why not examine the first char of the word

  // to quickly limit the set of prefixes to examine (i.e. the

  // prefixes to examine must be leading supersets of the first

  // character of the word (if they exist)

  // To take advantage of this "subset" relationship, we need to add

  // two links from entry.  One to take next if the current prefix

  // is found (call it nexteq) and one to take next if the current

  // prefix is not found (call it nextne).

  // Since we have built ordered lists, all that remains is to

  // properly initialize the nextne and nexteq pointers that relate

  // them

  process_pfx_order();

  process_sfx_order();

  //CERR.printf("%u\n", data_buf.calc_size()/1024);

  return no_err;

}

// we want to be able to quickly access prefix information

// both by prefix flag, and sorted by prefix string itself

// so we need to set up two indexes

PosibErr<void> AffixMgr::build_pfxlist(PfxEntry* pfxptr)

{

  PfxEntry * ptr;

  PfxEntry * ep = pfxptr;

  // get the right starting point 

  const char * key = ep->key();

  const byte flg = ep->flag();

  // first index by flag which must exist

  ptr = pFlag[flg];

  ep->flag_next = ptr;

  pFlag[flg] = ep;

  // next insert the affix string, it will be sorted latter

  byte sp = *((const byte *)key);

  ptr = pStart[sp];

  ep->next = ptr;

  pStart[sp] = ep;

  return no_err;

}

// we want to be able to quickly access suffix information

// both by suffix flag, and sorted by the reverse of the

// suffix string itself; so we need to set up two indexes

PosibErr<void> AffixMgr::build_sfxlist(SfxEntry* sfxptr)

{

  SfxEntry * ptr;

  SfxEntry * ep = sfxptr;

  char * tmp = (char *)data_buf.alloc(sfxptr->appndl + 1);

  sfxptr->rappnd = tmp;

  // reverse the string

  char * dest = tmp + sfxptr->appndl;

  *dest-- = 0;

  const char * src = sfxptr->appnd;

  for (; dest >= tmp; --dest, ++src)

    *dest = *src;

  /* get the right starting point */

  const char * key = ep->key();

  const byte flg = ep->flag();

  // first index by flag which must exist

  ptr = sFlag[flg];

  ep->flag_next = ptr;

  sFlag[flg] = ep;

  // next insert the affix string, it will be sorted latter

  byte sp = *((const byte *)key);

  ptr = sStart[sp];

  ep->next = ptr;

  sStart[sp] = ep;

  return no_err;

}

// initialize the PfxEntry links NextEQ and NextNE to speed searching

PosibErr<void> AffixMgr::process_pfx_order()

{

  PfxEntry* ptr;

  // loop through each prefix list starting point

  for (int i=1; i < SETSIZE; i++) {

    ptr = pStart[i];

    if (ptr && ptr->next)

      ptr = pStart[i] = sort(ptr, AffixLess<PfxEntry>());

    // look through the remainder of the list

    //  and find next entry with affix that 

    // the current one is not a subset of

    // mark that as destination for NextNE

    // use next in list that you are a subset

    // of as NextEQ

    for (; ptr != NULL; ptr = ptr->next) {

      PfxEntry * nptr = ptr->next;

      for (; nptr != NULL; nptr = nptr->next) {

        if (! isSubset( ptr->key() , nptr->key() )) break;

      }

      ptr->next_ne = nptr;

      ptr->next_eq = NULL;

      if ((ptr->next) && isSubset(ptr->key() , 

                                  (ptr->next)->key())) 

        ptr->next_eq = ptr->next;

    }

    // now clean up by adding smart search termination strings

    // if you are already a superset of the previous prefix

    // but not a subset of the next, search can end here

    // so set NextNE properly

    ptr = pStart[i];

    for (; ptr != NULL; ptr = ptr->next) {

      PfxEntry * nptr = ptr->next;

      PfxEntry * mptr = NULL;

      for (; nptr != NULL; nptr = nptr->next) {

        if (! isSubset(ptr->key(),nptr->key())) break;

        mptr = nptr;

      }

      if (mptr) mptr->next_ne = NULL;

    }

  }

  return no_err;

}

// initialize the SfxEntry links NextEQ and NextNE to speed searching

PosibErr<void> AffixMgr::process_sfx_order()

{

  SfxEntry* ptr;

  // loop through each prefix list starting point

  for (int i=1; i < SETSIZE; i++) {

    ptr = sStart[i];

    if (ptr && ptr->next)

      ptr = sStart[i] = sort(ptr, AffixLess<SfxEntry>());

    // look through the remainder of the list

    //  and find next entry with affix that 

    // the current one is not a subset of

    // mark that as destination for NextNE

    // use next in list that you are a subset

    // of as NextEQ

    for (; ptr != NULL; ptr = ptr->next) {

      SfxEntry * nptr = ptr->next;

      for (; nptr != NULL; nptr = nptr->next) {

        if (! isSubset(ptr->key(),nptr->key())) break;

      }

      ptr->next_ne = nptr;

      ptr->next_eq = NULL;

      if ((ptr->next) && isSubset(ptr->key(),(ptr->next)->key())) 

        ptr->next_eq = ptr->next;

    }

    // now clean up by adding smart search termination strings:

    // if you are already a superset of the previous suffix

    // but not a subset of the next, search can end here

    // so set NextNE properly

    ptr = sStart[i];

    for (; ptr != NULL; ptr = ptr->next) {

      SfxEntry * nptr = ptr->next;

      SfxEntry * mptr = NULL;

      for (; nptr != NULL; nptr = nptr->next) {

        if (! isSubset(ptr->key(),nptr->key())) break;

        mptr = nptr;

      }

      if (mptr) mptr->next_ne = NULL;

    }

  }

  return no_err;

}

// takes aff file condition string and creates the

// conds array - please see the appendix at the end of the

// file affentry.cxx which describes what is going on here

// in much more detail

static void encodeit(CondsLookup & l, ObjStack & buf, 

                     AffEntry * ptr, char * cs)

{

  byte c;

  int i, j, k;

  // see if we already have this conds matrix

  CondsLookup::iterator itr = l.find(cs);

  if (!(itr == l.end())) {

    ptr->conds = *itr;

    return;

  }

  Conds * cds = (Conds *)buf.alloc_bottom(sizeof(Conds));

  cds->str = buf.dup(cs);

  l.insert(cds);

  ptr->conds = cds;

  int nc = strlen(cs);

  VARARRAYM(byte, mbr, nc + 1, MAXLNLEN);

  // now clear the conditions array

  memset(cds->conds, 0, sizeof(cds->conds));

  // now parse the string to create the conds array

  int neg = 0;   // complement indicator

  int grp = 0;   // group indicator

  int n = 0;     // number of conditions

  int ec = 0;    // end condition indicator

  int nm = 0;    // number of member in group

  // if no condition just return

  if (strcmp(cs,".")==0) {

    cds->num = 0;

    return;

  }

  i = 0;

  while (i < nc) {

    c = *((byte *)(cs + i));

    // start group indicator

    if (c == '[') {

      grp = 1;

      c = 0;

    }

    // complement flag

    if ((grp == 1) && (c == '^')) {

      neg = 1;

      c = 0;

    }

    // end goup indicator

    if (c == ']') {

      ec = 1;

      c = 0;

    }

    // add character of group to list

    if ((grp == 1) && (c != 0)) {

      *(mbr + nm) = c;

      nm++;

      c = 0;

    }

    // end of condition 

    if (c != 0) {

      ec = 1;

    }

    if (ec) {

      if (grp == 1) {

        if (neg == 0) {

          // set the proper bits in the condition array vals for those chars

          for (j=0;j<nm;j++) {

            k = (unsigned int) mbr[j];

            cds->conds[k] = cds->conds[k] | (1 << n);

          }

        } else {

          // complement so set all of them and then unset indicated ones

          for (j=0;j<SETSIZE;j++) cds->conds[j] = cds->conds[j] | (1 << n);

          for (j=0;j<nm;j++) {

            k = (unsigned int) mbr[j];

            cds->conds[k] = cds->conds[k] & ~(1 << n);

          }

        }

        neg = 0;

        grp = 0;   

        nm = 0;

      } else {

        // not a group so just set the proper bit for this char

        // but first handle special case of . inside condition

        if (c == '.') {

          // wild card character so set them all

          for (j=0;j<SETSIZE;j++) cds->conds[j] = cds->conds[j] | (1 << n);

        } else {  

          cds->conds[(unsigned int)c] = cds->conds[(unsigned int)c] | (1 << n);

        }

      }

      n++;

      ec = 0;

    }

    i++;

  }

  cds->num = n;

  return;

}

// check word for prefixes

bool AffixMgr::prefix_check (const LookupInfo & linf, ParmString word, 

                             CheckInfo & ci, GuessInfo * gi, bool cross) const

{

  if (word.empty()) return false;

  // first handle the special case of 0 length prefixes

  PfxEntry * pe = pStart[0];

  while (pe) {

    if (pe->check(linf,this,word,ci,gi)) return true;

    pe = pe->next;

  }

  // now handle the general case

  byte sp = *reinterpret_cast<const byte *>(word.str());

  PfxEntry * pptr = pStart[sp];

  while (pptr) {

    if (isSubset(pptr->key(),word)) {

      if (pptr->check(linf,this,word,ci,gi,cross)) return true;

      pptr = pptr->next_eq;

    } else {

      pptr = pptr->next_ne;

    }

  }

  return false;

}

// check word for suffixes

bool AffixMgr::suffix_check (const LookupInfo & linf, ParmString word, 

                             CheckInfo & ci, GuessInfo * gi,

                             int sfxopts, AffEntry * ppfx) const

{

  if (word.empty()) return false;

  // first handle the special case of 0 length suffixes

  SfxEntry * se = sStart[0];

  while (se) {

    if (se->check(linf, word, ci, gi, sfxopts, ppfx)) return true;

    se = se->next;

  }

  // now handle the general case

  byte sp = *((const byte *)(word + word.size() - 1));

  SfxEntry * sptr = sStart[sp];

  while (sptr) {

    if (isRevSubset(sptr->key(), word + word.size() - 1, word.size())) {

      if (sptr->check(linf, word, ci, gi, sfxopts, ppfx)) return true;

      sptr = sptr->next_eq;

    } else {

      sptr = sptr->next_ne;

    }

  }

  return false;

}

// check if word with affixes is correctly spelled

bool AffixMgr::affix_check(const LookupInfo & linf, ParmString word, 

                           CheckInfo & ci, GuessInfo * gi) const

{

  if (word.empty()) return false;

  // Deal With Case in a semi-intelligent manner

  CasePattern cp = lang->LangImpl::case_pattern(word);

  ParmString pword = word;

  ParmString sword = word;

  CharVector lower;

  if (cp == FirstUpper) {

    lower.append(word, word.size() + 1);

    lower[0] = lang->to_lower(word[0]);

    pword = ParmString(lower.data(), lower.size() - 1);

  } else if (cp == AllUpper) {

    lower.resize(word.size() + 1);

    unsigned int i = 0;

    for (; i != word.size(); ++i)

      lower[i] = lang->to_lower(word[i]);

    lower[i] = '\0';

    pword = ParmString(lower.data(), lower.size() - 1);

    sword = pword;

  }

  // check all prefixes (also crossed with suffixes if allowed) 

  if (prefix_check(linf, pword, ci, gi)) return true;

  // if still not found check all suffixes

  if (suffix_check(linf, sword, ci, gi, 0, NULL)) return true;

  // if still not found check again but with the lower case version

  // which can make a difference if the entire word matches the cond

  // string

  if (cp == FirstUpper) {

    return suffix_check(linf, pword, ci, gi, 0, NULL);

  } else {

    return false;

  }

}

void AffixMgr::munch(ParmString word, GuessInfo * gi, bool cross) const

{

  LookupInfo li(0, LookupInfo::AlwaysTrue);

  CheckInfo ci;

  gi->reset();

  CasePattern cp = lang->LangImpl::case_pattern(word);

  if (cp == AllUpper) return;

  if (cp != FirstUpper)

    prefix_check(li, word, ci, gi, cross);

  suffix_check(li, word, ci, gi, 0, NULL);

}

WordAff * AffixMgr::expand(ParmString word, ParmString aff, 

                           ObjStack & buf, int limit) const

{

  byte * empty = (byte *)buf.alloc(1);

  *empty = 0;

  byte * suf  = (byte *)buf.alloc(aff.size() + 1); 

  byte * suf_e = suf;

  byte * csuf = (byte *)buf.alloc(aff.size() + 1); 

  byte * csuf_e = csuf;

  WordAff * head = (WordAff *)buf.alloc_bottom(sizeof(WordAff));

  WordAff * cur = head;

  cur->word = buf.dup(word);

  cur->aff  = suf;

  for (const byte * c = (const byte *)aff.str(), * end = c + aff.size();

       c != end; 

       ++c) 

  {

    if (sFlag[*c]) *suf_e++ = *c; 

    if (sFlag[*c] && sFlag[*c]->allow_cross()) *csuf_e++ = *c;

    for (PfxEntry * p = pFlag[*c]; p; p = p->flag_next) {

      SimpleString newword = p->add(word, buf);

      if (!newword) continue;

      cur->next = (WordAff *)buf.alloc_bottom(sizeof(WordAff));

      cur = cur->next;

      cur->word = newword;

      cur->aff = p->allow_cross() ? csuf : empty;

    }

  }

  *suf_e = 0;

  *csuf_e = 0;

  cur->next = 0;

  if (limit == 0) return head;

  WordAff * * end = &cur->next;

  WordAff * * very_end = end;

  size_t nsuf_s = suf_e - suf + 1;

  for (WordAff * * cur = &head; cur != end; cur = &(*cur)->next) {

    if ((int)(*cur)->word.size - max_strip_ >= limit) continue;

    byte * nsuf = (byte *)buf.alloc(nsuf_s);

    expand_suffix((*cur)->word, (*cur)->aff, buf, limit, nsuf, &very_end, word);

    (*cur)->aff = nsuf;

  }

  return head;

}

WordAff * AffixMgr::expand_suffix(ParmString word, const byte * aff, 

                                  ObjStack & buf, int limit,

                                  byte * new_aff, WordAff * * * l,

                                  ParmString orig_word) const

{

  WordAff * head = 0;

  if (l) head = **l;

  WordAff * * cur = l ? *l : &head;

  bool expanded     = false;

  bool not_expanded = false;

  if (!orig_word) orig_word = word;

  while (*aff) {

    if ((int)word.size() - max_strip_f[*aff] < limit) {

      for (SfxEntry * p = sFlag[*aff]; p; p = p->flag_next) {

        SimpleString newword = p->add(word, buf, limit, orig_word);

        if (!newword) continue;

        if (newword == EMPTY) {not_expanded = true; continue;}

        *cur = (WordAff *)buf.alloc_bottom(sizeof(WordAff));

        (*cur)->word = newword;

        (*cur)->aff  = (const byte *)EMPTY;

        cur = &(*cur)->next;

        expanded = true;

      }

    }

    if (new_aff && (!expanded || not_expanded)) *new_aff++ = *aff;

    ++aff;

  }

  *cur = 0;

  if (new_aff) *new_aff = 0;

  if (l) *l = cur;

  return head;

}

CheckAffixRes AffixMgr::check_affix(ParmString word, char aff) const

{

  CheckAffixRes res = InvalidAffix;

  for (PfxEntry * p = pFlag[(unsigned char)aff]; p; p = p->flag_next) {

    res = InapplicableAffix;

    if (p->applicable(word)) return ValidAffix;

  }

  for (SfxEntry * p = sFlag[(unsigned char)aff]; p; p = p->flag_next) {

    if (res == InvalidAffix) res = InapplicableAffix;

    if (p->applicable(word)) return ValidAffix;

  }

  return res;

}

//////////////////////////////////////////////////////////////////////

//

// LookupInfo

//

int LookupInfo::lookup (ParmString word, const SensitiveCompare * c, 

                        char achar, 

                        WordEntry & o, GuessInfo * gi) const

{

  SpellerImpl::WS::const_iterator i = begin;

  const char * g = 0;

  if (mode == Word) {

    do {

      (*i)->lookup(word, c, o);

      for (;!o.at_end(); o.adv()) {

        if (TESTAFF(o.aff, achar))

          return 1;

        else

          g = o.word;

      }

      ++i;

    } while (i != end);

  } else if (mode == Clean) {

    do {

      (*i)->clean_lookup(word, o);

      for (;!o.at_end(); o.adv()) {

        if (TESTAFF(o.aff, achar))

          return 1;

        else

          g = o.word;

      }

      ++i;

    } while (i != end);

  } else if (gi) {

    g = gi->dup(word);

  }

  if (gi && g) {

    CheckInfo * ci = gi->add();

    ci->word = g;

    return -1;

  }

  return 0;

}

//////////////////////////////////////////////////////////////////////

//

// Affix Entry

//

bool PfxEntry::applicable(SimpleString word) const

{

  unsigned int cond;

  /* make sure all conditions match */

  if ((word.size > stripl) && (word.size >= conds->num)) {

    const byte * cp = (const byte *) word.str;

    for (cond = 0;  cond < conds->num;  cond++) {

      if ((conds->get(*cp++) & (1 << cond)) == 0)

        break;

    }

    if (cond >= conds->num) return true;

  }