Quelle  affixmgr.cxx   Sprache: C

/* ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 *
 * Copyright (C) 2002-2022 Németh László
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * Hunspell is based on MySpell which is Copyright (C) 2002 Kevin Hendricks.
 *
 * Contributor(s): David Einstein, Davide Prina, Giuseppe Modugno,
 * Gianluca Turconi, Simon Brouwer, Noll János, Bíró Árpád,
 * Goldman Eleonóra, Sarlós Tamás, Bencsáth Boldizsár, Halácsy Péter,
 * Dvornik László, Gefferth András, Nagy Viktor, Varga Dániel, Chris Halls,
 * Rene Engelhard, Bram Moolenaar, Dafydd Jones, Harri Pitkänen
 *
 * Alternatively, the contents of this file may be used under the terms of
 * either the GNU General Public License Version 2 or later (the "GPL"), or
 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 * in which case the provisions of the GPL or the LGPL are applicable instead
 * of those above. If you wish to allow use of your version of this file only
 * under the terms of either the GPL or the LGPL, and not to allow others to
 * use your version of this file under the terms of the MPL, indicate your
 * decision by deleting the provisions above and replace them with the notice
 * and other provisions required by the GPL or the LGPL. If you do not delete
 * the provisions above, a recipient may use your version of this file under
 * the terms of any one of the MPL, the GPL or the LGPL.
 *
 * ***** END LICENSE BLOCK ***** */
/*
 * 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 <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <ctype.h>
#include <time.h>

#include <algorithm>
#include <limits>
#include <string>
#include <vector>

#include "affixmgr.hxx"
#include "affentry.hxx"
#include "langnum.hxx"

#include "csutil.hxx"

AffixMgr::AffixMgr(const char* affpath,
                   const std::vector<HashMgr*>& ptr,
                   const char* key)
  : alldic(ptr)
  , pHMgr(ptr[0]) {

  // register hash manager and load affix data from aff file
  csconv = NULL;
  utf8 = 0;
  complexprefixes = 0;
  parsedmaptable = false;
  parsedbreaktable = false;
  iconvtable = NULL;
  oconvtable = NULL;
  // allow simplified compound forms (see 3rd field of CHECKCOMPOUNDPATTERN)
  simplifiedcpd = 0;
  parsedcheckcpd = false;
  parseddefcpd = false;
  phone = NULL;
  compoundflag = FLAG_NULL;        // permits word in compound forms
  compoundbegin = FLAG_NULL;       // may be first word in compound forms
  compoundmiddle = FLAG_NULL;      // may be middle word in compound forms
  compoundend = FLAG_NULL;         // may be last word in compound forms
  compoundroot = FLAG_NULL;        // compound word signing flag
  compoundpermitflag = FLAG_NULL;  // compound permitting flag for suffixed word
  compoundforbidflag = FLAG_NULL;  // compound fordidden flag for suffixed word
  compoundmoresuffixes = 0;        // allow more suffixes within compound words
  checkcompounddup = 0;            // forbid double words in compounds
  checkcompoundrep = 0;  // forbid bad compounds (may be non-compound word with
                         // a REP substitution)
  checkcompoundcase =
      0;  // forbid upper and lowercase combinations at word bounds
  checkcompoundtriple = 0;  // forbid compounds with triple letters
  simplifiedtriple = 0;     // allow simplified triple letters in compounds
                            // (Schiff+fahrt -> Schiffahrt)
  forbiddenword = FORBIDDENWORD;  // forbidden word signing flag
  nosuggest = FLAG_NULL;  // don't suggest words signed with NOSUGGEST flag
  nongramsuggest = FLAG_NULL;
  langnum = 0;  // language code (see http://l10n.openoffice.org/languages.html)
  needaffix = FLAG_NULL;  // forbidden root, allowed only with suffixes
  cpdwordmax = -1;        // default: unlimited wordcount in compound words
  cpdmin = -1;            // undefined
  cpdmaxsyllable = 0;     // default: unlimited syllablecount in compound words
  pfxappnd = NULL;  // previous prefix for counting syllables of the prefix BUG
  sfxappnd = NULL;  // previous suffix for counting syllables of the suffix BUG
  sfxextra = 0;     // modifier for syllable count of sfxappnd BUG
  checknum = 0;               // checking numbers, and word with numbers
  havecontclass = 0;  // flags of possible continuing classes (double affix)
  // LEMMA_PRESENT: not put root into the morphological output. Lemma presents
  // in morhological description in dictionary file. It's often combined with
  // PSEUDOROOT.
  lemma_present = FLAG_NULL;
  circumfix = FLAG_NULL;
  onlyincompound = FLAG_NULL;
  maxngramsugs = -1;  // undefined
  maxdiff = -1;       // undefined
  onlymaxdiff = 0;
  maxcpdsugs = -1;  // undefined
  nosplitsugs = 0;
  sugswithdots = 0;
  keepcase = 0;
  forceucase = 0;
  warn = 0;
  forbidwarn = 0;
  checksharps = 0;
  substandard = FLAG_NULL;
  fullstrip = 0;

  sfx = NULL;
  pfx = NULL;

  for (int i = 0; i < SETSIZE; i++) {
    pStart[i] = NULL;
    sStart[i] = NULL;
    pFlag[i] = NULL;
    sFlag[i] = NULL;
  }

  for (int j = 0; j < CONTSIZE; j++) {
    contclasses[j] = 0;
  }

  if (parse_file(affpath, key)) {
    HUNSPELL_WARNING(stderr, "Failure loading aff file %s\n", affpath);
  }

  if (cpdmin == -1)
    cpdmin = MINCPDLEN;
}

AffixMgr::~AffixMgr() {
  // pass through linked prefix entries and clean up
  for (int i = 0; i < SETSIZE; i++) {
    pFlag[i] = NULL;
    PfxEntry* ptr = pStart[i];
    PfxEntry* nptr = NULL;
    while (ptr) {
      nptr = ptr->getNext();
      delete (ptr);
      ptr = nptr;
      nptr = NULL;
    }
  }

  // pass through linked suffix entries and clean up
  for (int j = 0; j < SETSIZE; j++) {
    sFlag[j] = NULL;
    SfxEntry* ptr = sStart[j];
    SfxEntry* nptr = NULL;
    while (ptr) {
      nptr = ptr->getNext();
      delete (ptr);
      ptr = nptr;
      nptr = NULL;
    }
    sStart[j] = NULL;
  }

  delete iconvtable;
  delete oconvtable;
  delete phone;

  FREE_FLAG(compoundflag);
  FREE_FLAG(compoundbegin);
  FREE_FLAG(compoundmiddle);
  FREE_FLAG(compoundend);
  FREE_FLAG(compoundpermitflag);
  FREE_FLAG(compoundforbidflag);
  FREE_FLAG(compoundroot);
  FREE_FLAG(forbiddenword);
  FREE_FLAG(nosuggest);
  FREE_FLAG(nongramsuggest);
  FREE_FLAG(needaffix);
  FREE_FLAG(lemma_present);
  FREE_FLAG(circumfix);
  FREE_FLAG(onlyincompound);

  cpdwordmax = 0;
  pHMgr = NULL;
  cpdmin = 0;
  cpdmaxsyllable = 0;
  free_utf_tbl();
  checknum = 0;
#ifdef MOZILLA_CLIENT
  delete[] csconv;
#endif
}

void AffixMgr::finishFileMgr(FileMgr* afflst) {
  delete afflst;

  // convert affix trees to sorted list
  process_pfx_tree_to_list();
  process_sfx_tree_to_list();
}

// read in aff file and build up prefix and suffix entry objects
int AffixMgr::parse_file(const char* affpath, const char* key) {

  // checking flag duplication
  char dupflags[CONTSIZE];
  char dupflags_ini = 1;

  // first line indicator for removing byte order mark
  int firstline = 1;

  // open the affix file
  FileMgr* afflst = new FileMgr(affpath, key);
  if (!afflst) {
    HUNSPELL_WARNING(
        stderr, "error: could not open affix description file %s\n", affpath);
    return 1;
  }

  // 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
  std::string line;
  while (afflst->getline(line)) {
    mychomp(line);

    /* remove byte order mark */
    if (firstline) {
      firstline = 0;
      // Affix file begins with byte order mark: possible incompatibility with
      // old Hunspell versions
      if (line.compare(0, 3, "\xEF\xBB\xBF", 3) == 0) {
        line.erase(0, 3);
      }
    }

    /* parse in the keyboard string */
    if (line.compare(0, 3, "KEY", 3) == 0) {
      if (!parse_string(line, keystring, afflst->getlinenum())) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the try string */
    if (line.compare(0, 3, "TRY", 3) == 0) {
      if (!parse_string(line, trystring, afflst->getlinenum())) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the name of the character set used by the .dict and .aff */
    if (line.compare(0, 3, "SET", 3) == 0) {
      if (!parse_string(line, encoding, afflst->getlinenum())) {
        finishFileMgr(afflst);
        return 1;
      }
      if (encoding == "UTF-8") {
        utf8 = 1;
#ifndef OPENOFFICEORG
#ifndef MOZILLA_CLIENT
        initialize_utf_tbl();
#endif
#endif
      }
    }

    /* parse COMPLEXPREFIXES for agglutinative languages with right-to-left
     * writing system */
    if (line.compare(0, 15, "COMPLEXPREFIXES", 15) == 0)
      complexprefixes = 1;

    /* parse in the flag used by the controlled compound words */
    if (line.compare(0, 12, "COMPOUNDFLAG", 12) == 0) {
      if (!parse_flag(line, &compoundflag, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the flag used by compound words */
    if (line.compare(0, 13, "COMPOUNDBEGIN", 13) == 0) {
      if (complexprefixes) {
        if (!parse_flag(line, &compoundend, afflst)) {
          finishFileMgr(afflst);
          return 1;
        }
      } else {
        if (!parse_flag(line, &compoundbegin, afflst)) {
          finishFileMgr(afflst);
          return 1;
        }
      }
    }

    /* parse in the flag used by compound words */
    if (line.compare(0, 14, "COMPOUNDMIDDLE", 14) == 0) {
      if (!parse_flag(line, &compoundmiddle, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the flag used by compound words */
    if (line.compare(0, 11, "COMPOUNDEND", 11) == 0) {
      if (complexprefixes) {
        if (!parse_flag(line, &compoundbegin, afflst)) {
          finishFileMgr(afflst);
          return 1;
        }
      } else {
        if (!parse_flag(line, &compoundend, afflst)) {
          finishFileMgr(afflst);
          return 1;
        }
      }
    }

    /* parse in the data used by compound_check() method */
    if (line.compare(0, 15, "COMPOUNDWORDMAX", 15) == 0) {
      if (!parse_num(line, &cpdwordmax, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the flag sign compounds in dictionary */
    if (line.compare(0, 12, "COMPOUNDROOT", 12) == 0) {
      if (!parse_flag(line, &compoundroot, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the flag used by compound_check() method */
    if (line.compare(0, 18, "COMPOUNDPERMITFLAG", 18) == 0) {
      if (!parse_flag(line, &compoundpermitflag, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the flag used by compound_check() method */
    if (line.compare(0, 18, "COMPOUNDFORBIDFLAG", 18) == 0) {
      if (!parse_flag(line, &compoundforbidflag, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    if (line.compare(0, 20, "COMPOUNDMORESUFFIXES", 20) == 0) {
      compoundmoresuffixes = 1;
    }

    if (line.compare(0, 16, "CHECKCOMPOUNDDUP", 16) == 0) {
      checkcompounddup = 1;
    }

    if (line.compare(0, 16, "CHECKCOMPOUNDREP", 16) == 0) {
      checkcompoundrep = 1;
    }

    if (line.compare(0, 19, "CHECKCOMPOUNDTRIPLE", 19) == 0) {
      checkcompoundtriple = 1;
    }

    if (line.compare(0, 16, "SIMPLIFIEDTRIPLE", 16) == 0) {
      simplifiedtriple = 1;
    }

    if (line.compare(0, 17, "CHECKCOMPOUNDCASE", 17) == 0) {
      checkcompoundcase = 1;
    }

    if (line.compare(0, 9, "NOSUGGEST", 9) == 0) {
      if (!parse_flag(line, &nosuggest, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    if (line.compare(0, 14, "NONGRAMSUGGEST", 14) == 0) {
      if (!parse_flag(line, &nongramsuggest, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the flag used by forbidden words */
    if (line.compare(0, 13, "FORBIDDENWORD", 13) == 0) {
      if (!parse_flag(line, &forbiddenword, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the flag used by forbidden words (is deprecated) */
    if (line.compare(0, 13, "LEMMA_PRESENT", 13) == 0) {
      if (!parse_flag(line, &lemma_present, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the flag used by circumfixes */
    if (line.compare(0, 9, "CIRCUMFIX", 9) == 0) {
      if (!parse_flag(line, &circumfix, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the flag used by fogemorphemes */
    if (line.compare(0, 14, "ONLYINCOMPOUND", 14) == 0) {
      if (!parse_flag(line, &onlyincompound, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the flag used by `needaffixs' (is deprecated) */
    if (line.compare(0, 10, "PSEUDOROOT", 10) == 0) {
      if (!parse_flag(line, &needaffix, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the flag used by `needaffixs' */
    if (line.compare(0, 9, "NEEDAFFIX", 9) == 0) {
      if (!parse_flag(line, &needaffix, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the minimal length for words in compounds */
    if (line.compare(0, 11, "COMPOUNDMIN", 11) == 0) {
      if (!parse_num(line, &cpdmin, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
      if (cpdmin < 1)
        cpdmin = 1;
    }

    /* parse in the max. words and syllables in compounds */
    if (line.compare(0, 16, "COMPOUNDSYLLABLE", 16) == 0) {
      if (!parse_cpdsyllable(line, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the flag used by compound_check() method */
    if (line.compare(0, 11, "SYLLABLENUM", 11) == 0) {
      if (!parse_string(line, cpdsyllablenum, afflst->getlinenum())) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the flag used by the controlled compound words */
    if (line.compare(0, 8, "CHECKNUM", 8) == 0) {
      checknum = 1;
    }

    /* parse in the extra word characters */
    if (line.compare(0, 9, "WORDCHARS", 9) == 0) {
      if (!parse_array(line, wordchars, wordchars_utf16,
                       utf8, afflst->getlinenum())) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the ignored characters (for example, Arabic optional diacretics
     * charachters */
    if (line.compare(0, 6, "IGNORE", 6) == 0) {
      if (!parse_array(line, ignorechars, ignorechars_utf16,
                       utf8, afflst->getlinenum())) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the input conversion table */
    if (line.compare(0, 5, "ICONV", 5) == 0) {
      if (!parse_convtable(line, afflst, &iconvtable, "ICONV")) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the output conversion table */
    if (line.compare(0, 5, "OCONV", 5) == 0) {
      if (!parse_convtable(line, afflst, &oconvtable, "OCONV")) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the phonetic translation table */
    if (line.compare(0, 5, "PHONE", 5) == 0) {
      if (!parse_phonetable(line, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the checkcompoundpattern table */
    if (line.compare(0, 20, "CHECKCOMPOUNDPATTERN", 20) == 0) {
      if (!parse_checkcpdtable(line, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the defcompound table */
    if (line.compare(0, 12, "COMPOUNDRULE", 12) == 0) {
      if (!parse_defcpdtable(line, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the related character map table */
    if (line.compare(0, 3, "MAP", 3) == 0) {
      if (!parse_maptable(line, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the word breakpoints table */
    if (line.compare(0, 5, "BREAK", 5) == 0) {
      if (!parse_breaktable(line, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the language for language specific codes */
    if (line.compare(0, 4, "LANG", 4) == 0) {
      if (!parse_string(line, lang, afflst->getlinenum())) {
        finishFileMgr(afflst);
        return 1;
      }
      langnum = get_lang_num(lang);
    }

    if (line.compare(0, 7, "VERSION", 7) == 0) {
      size_t startpos = line.find_first_not_of(" \t", 7);
      if (startpos != std::string::npos) {
          version = line.substr(startpos);
      }
    }

    if (line.compare(0, 12, "MAXNGRAMSUGS", 12) == 0) {
      if (!parse_num(line, &maxngramsugs, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    if (line.compare(0, 11, "ONLYMAXDIFF", 11) == 0)
      onlymaxdiff = 1;

    if (line.compare(0, 7, "MAXDIFF", 7) == 0) {
      if (!parse_num(line, &maxdiff, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    if (line.compare(0, 10, "MAXCPDSUGS", 10) == 0) {
      if (!parse_num(line, &maxcpdsugs, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    if (line.compare(0, 11, "NOSPLITSUGS", 11) == 0) {
      nosplitsugs = 1;
    }

    if (line.compare(0, 9, "FULLSTRIP", 9) == 0) {
      fullstrip = 1;
    }

    if (line.compare(0, 12, "SUGSWITHDOTS", 12) == 0) {
      sugswithdots = 1;
    }

    /* parse in the flag used by forbidden words */
    if (line.compare(0, 8, "KEEPCASE", 8) == 0) {
      if (!parse_flag(line, &keepcase, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the flag used by `forceucase' */
    if (line.compare(0, 10, "FORCEUCASE", 10) == 0) {
      if (!parse_flag(line, &forceucase, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    /* parse in the flag used by `warn' */
    if (line.compare(0, 4, "WARN", 4) == 0) {
      if (!parse_flag(line, &warn, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    if (line.compare(0, 10, "FORBIDWARN", 10) == 0) {
      forbidwarn = 1;
    }

    /* parse in the flag used by the affix generator */
    if (line.compare(0, 11, "SUBSTANDARD", 11) == 0) {
      if (!parse_flag(line, &substandard, afflst)) {
        finishFileMgr(afflst);
        return 1;
      }
    }

    if (line.compare(0, 11, "CHECKSHARPS", 11) == 0) {
      checksharps = 1;
    }

    /* parse this affix: P - prefix, S - suffix */
    // affix type
    char ft = ' ';
    if (line.compare(0, 3, "PFX", 3) == 0)
      ft = complexprefixes ? 'S' : 'P';
    if (line.compare(0, 3, "SFX", 3) == 0)
      ft = complexprefixes ? 'P' : 'S';
    if (ft != ' ') {
      if (dupflags_ini) {
        memset(dupflags, 0, sizeof(dupflags));
        dupflags_ini = 0;
      }
      if (!parse_affix(line, ft, afflst, dupflags)) {
        finishFileMgr(afflst);
        return 1;
      }
    }
  }

  finishFileMgr(afflst);
  // affix trees are sorted now

  // 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();

  /* get encoding for CHECKCOMPOUNDCASE */
  if (!utf8) {
    csconv = get_current_cs(get_encoding());
    for (int i = 0; i <= 255; i++) {
      if ((csconv[i].cupper != csconv[i].clower) &&
          (wordchars.find((char)i) == std::string::npos)) {
        wordchars.push_back((char)i);
      }
    }

  }

  // default BREAK definition
  if (!parsedbreaktable) {
    breaktable.push_back("-");
    breaktable.push_back("^-");
    breaktable.push_back("-$");
    parsedbreaktable = true;
  }
  return 0;
}

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

int AffixMgr::build_pfxtree(PfxEntry* pfxptr) {
  PfxEntry* ptr;
  PfxEntry* pptr;
  PfxEntry* ep = pfxptr;

  // get the right starting points
  const char* key = ep->getKey();
  const unsigned char flg = (unsigned char)(ep->getFlag() & 0x00FF);

  // first index by flag which must exist
  ptr = pFlag[flg];
  ep->setFlgNxt(ptr);
  pFlag[flg] = ep;

  // handle the special case of null affix string
  if (strlen(key) == 0) {
    // always inset them at head of list at element 0
    ptr = pStart[0];
    ep->setNext(ptr);
    pStart[0] = ep;
    return 0;
  }

  // now handle the normal case
  ep->setNextEQ(NULL);
  ep->setNextNE(NULL);

  unsigned char sp = *((const unsigned char*)key);
  ptr = pStart[sp];

  // handle the first insert
  if (!ptr) {
    pStart[sp] = ep;
    return 0;
  }

  // otherwise use binary tree insertion so that a sorted
  // list can easily be generated later
  pptr = NULL;
  for (;;) {
    pptr = ptr;
    if (strcmp(ep->getKey(), ptr->getKey()) <= 0) {
      ptr = ptr->getNextEQ();
      if (!ptr) {
        pptr->setNextEQ(ep);
        break;
      }
    } else {
      ptr = ptr->getNextNE();
      if (!ptr) {
        pptr->setNextNE(ep);
        break;
      }
    }
  }
  return 0;
}

// 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
int AffixMgr::build_sfxtree(SfxEntry* sfxptr) {

  sfxptr->initReverseWord();

  SfxEntry* ptr;
  SfxEntry* pptr;
  SfxEntry* ep = sfxptr;

  /* get the right starting point */
  const char* key = ep->getKey();
  const unsigned char flg = (unsigned char)(ep->getFlag() & 0x00FF);

  // first index by flag which must exist
  ptr = sFlag[flg];
  ep->setFlgNxt(ptr);
  sFlag[flg] = ep;

  // next index by affix string

  // handle the special case of null affix string
  if (strlen(key) == 0) {
    // always inset them at head of list at element 0
    ptr = sStart[0];
    ep->setNext(ptr);
    sStart[0] = ep;
    return 0;
  }

  // now handle the normal case
  ep->setNextEQ(NULL);
  ep->setNextNE(NULL);

  unsigned char sp = *((const unsigned char*)key);
  ptr = sStart[sp];

  // handle the first insert
  if (!ptr) {
    sStart[sp] = ep;
    return 0;
  }

  // otherwise use binary tree insertion so that a sorted
  // list can easily be generated later
  pptr = NULL;
  for (;;) {
    pptr = ptr;
    if (strcmp(ep->getKey(), ptr->getKey()) <= 0) {
      ptr = ptr->getNextEQ();
      if (!ptr) {
        pptr->setNextEQ(ep);
        break;
      }
    } else {
      ptr = ptr->getNextNE();
      if (!ptr) {
        pptr->setNextNE(ep);
        break;
      }
    }
  }
  return 0;
}

// convert from binary tree to sorted list
int AffixMgr::process_pfx_tree_to_list() {
  for (int i = 1; i < SETSIZE; i++) {
    pStart[i] = process_pfx_in_order(pStart[i], NULL);
  }
  return 0;
}

PfxEntry* AffixMgr::process_pfx_in_order(PfxEntry* ptr, PfxEntry* nptr) {
  if (ptr) {
    nptr = process_pfx_in_order(ptr->getNextNE(), nptr);
    ptr->setNext(nptr);
    nptr = process_pfx_in_order(ptr->getNextEQ(), ptr);
  }
  return nptr;
}

// convert from binary tree to sorted list
int AffixMgr::process_sfx_tree_to_list() {
  for (int i = 1; i < SETSIZE; i++) {
    sStart[i] = process_sfx_in_order(sStart[i], NULL);
  }
  return 0;
}

SfxEntry* AffixMgr::process_sfx_in_order(SfxEntry* ptr, SfxEntry* nptr) {
  if (ptr) {
    nptr = process_sfx_in_order(ptr->getNextNE(), nptr);
    ptr->setNext(nptr);
    nptr = process_sfx_in_order(ptr->getNextEQ(), ptr);
  }
  return nptr;
}

// reinitialize the PfxEntry links NextEQ and NextNE to speed searching
// using the idea of leading subsets this time
int AffixMgr::process_pfx_order() {
  PfxEntry* ptr;

  // loop through each prefix list starting point
  for (int i = 1; i < SETSIZE; i++) {
    ptr = pStart[i];

    // 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->getNext()) {
      PfxEntry* nptr = ptr->getNext();
      for (; nptr != NULL; nptr = nptr->getNext()) {
        if (!isSubset(ptr->getKey(), nptr->getKey()))
          break;
      }
      ptr->setNextNE(nptr);
      ptr->setNextEQ(NULL);
      if ((ptr->getNext()) &&
          isSubset(ptr->getKey(), (ptr->getNext())->getKey()))
        ptr->setNextEQ(ptr->getNext());
    }

    // 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->getNext()) {
      PfxEntry* nptr = ptr->getNext();
      PfxEntry* mptr = NULL;
      for (; nptr != NULL; nptr = nptr->getNext()) {
        if (!isSubset(ptr->getKey(), nptr->getKey()))
          break;
        mptr = nptr;
      }
      if (mptr)
        mptr->setNextNE(NULL);
    }
  }
  return 0;
}

// initialize the SfxEntry links NextEQ and NextNE to speed searching
// using the idea of leading subsets this time
int AffixMgr::process_sfx_order() {
  SfxEntry* ptr;

  // loop through each prefix list starting point
  for (int i = 1; i < SETSIZE; i++) {
    ptr = sStart[i];

    // 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->getNext()) {
      SfxEntry* nptr = ptr->getNext();
      for (; nptr != NULL; nptr = nptr->getNext()) {
        if (!isSubset(ptr->getKey(), nptr->getKey()))
          break;
      }
      ptr->setNextNE(nptr);
      ptr->setNextEQ(NULL);
      if ((ptr->getNext()) &&
          isSubset(ptr->getKey(), (ptr->getNext())->getKey()))
        ptr->setNextEQ(ptr->getNext());
    }

    // 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->getNext()) {
      SfxEntry* nptr = ptr->getNext();
      SfxEntry* mptr = NULL;
      for (; nptr != NULL; nptr = nptr->getNext()) {
        if (!isSubset(ptr->getKey(), nptr->getKey()))
          break;
        mptr = nptr;
      }
      if (mptr)
        mptr->setNextNE(NULL);
    }
  }
  return 0;
}

// add flags to the result for dictionary debugging
std::string& AffixMgr::debugflag(std::string& result, unsigned short flag) {
  char* st = encode_flag(flag);
  result.push_back(MSEP_FLD);
  result.append(MORPH_FLAG);
  if (st) {
    result.append(st);
    free(st);
  }
  return result;
}

// calculate the character length of the condition
int AffixMgr::condlen(const char* st) {
  int l = 0;
  bool group = false;
  for (; *st; st++) {
    if (*st == '[') {
      group = true;
      l++;
    } else if (*st == ']')
      group = false;
    else if (!group && (!utf8 || (!(*st & 0x80) || ((*st & 0xc0) == 0x80))))
      l++;
  }
  return l;
}

int AffixMgr::encodeit(AffEntry& entry, const char* cs) {
  if (strcmp(cs, ".") != 0) {
    entry.numconds = (char)condlen(cs);
    const size_t cslen = strlen(cs);
    const size_t short_part = std::min<size_t>(MAXCONDLEN, cslen);
    memcpy(entry.c.conds, cs, short_part);
    if (short_part < MAXCONDLEN) {
      //blank out the remaining space
      memset(entry.c.conds + short_part, 0, MAXCONDLEN - short_part);
    } else if (cs[MAXCONDLEN]) {
      //there is more conditions than fit in fixed space, so its
      //a long condition
      entry.opts |= aeLONGCOND;
      entry.c.l.conds2 = mystrdup(cs + MAXCONDLEN_1);
      if (!entry.c.l.conds2)
        return 1;
    }
  } else {
    entry.numconds = 0;
    entry.c.conds[0] = '\0';
  }
  return 0;
}

// return 1 if s1 is a leading subset of s2 (dots are for infixes)
inline int AffixMgr::isSubset(const char* s1, const char* s2) {
  while (((*s1 == *s2) || (*s1 == '.')) && (*s1 != '\0')) {
    s1++;
    s2++;
  }
  return (*s1 == '\0');
}

// check word for prefixes
struct hentry* AffixMgr::prefix_check(const char* word,
                                      int len,
                                      char in_compound,
                                      const FLAG needflag) {
  struct hentry* rv = NULL;

  pfx = NULL;
  pfxappnd = NULL;
  sfxappnd = NULL;
  sfxextra = 0;

  // first handle the special case of 0 length prefixes
  PfxEntry* pe = pStart[0];
  while (pe) {
    if (
        // fogemorpheme
        ((in_compound != IN_CPD_NOT) ||
         !(pe->getCont() &&
           (TESTAFF(pe->getCont(), onlyincompound, pe->getContLen())))) &&
        // permit prefixes in compounds
        ((in_compound != IN_CPD_END) ||
         (pe->getCont() &&
          (TESTAFF(pe->getCont(), compoundpermitflag, pe->getContLen()))))) {
      // check prefix
      rv = pe->checkword(word, len, in_compound, needflag);
      if (rv) {
        pfx = pe;  // BUG: pfx not stateless
        return rv;
      }
    }
    pe = pe->getNext();
  }

  // now handle the general case
  unsigned char sp = *((const unsigned char*)word);
  PfxEntry* pptr = pStart[sp];

  while (pptr) {
    if (isSubset(pptr->getKey(), word)) {
      if (
          // fogemorpheme
          ((in_compound != IN_CPD_NOT) ||
           !(pptr->getCont() &&
             (TESTAFF(pptr->getCont(), onlyincompound, pptr->getContLen())))) &&
          // permit prefixes in compounds
          ((in_compound != IN_CPD_END) ||
           (pptr->getCont() && (TESTAFF(pptr->getCont(), compoundpermitflag,
                                        pptr->getContLen()))))) {
        // check prefix
        rv = pptr->checkword(word, len, in_compound, needflag);
        if (rv) {
          pfx = pptr;  // BUG: pfx not stateless
          return rv;
        }
      }
      pptr = pptr->getNextEQ();
    } else {
      pptr = pptr->getNextNE();
    }
  }

  return NULL;
}

// check word for prefixes and two-level suffixes
struct hentry* AffixMgr::prefix_check_twosfx(const char* word,
                                             int len,
                                             char in_compound,
                                             const FLAG needflag) {
  struct hentry* rv = NULL;

  pfx = NULL;
  sfxappnd = NULL;
  sfxextra = 0;

  // first handle the special case of 0 length prefixes
  PfxEntry* pe = pStart[0];

  while (pe) {
    rv = pe->check_twosfx(word, len, in_compound, needflag);
    if (rv)
      return rv;
    pe = pe->getNext();
  }

  // now handle the general case
  unsigned char sp = *((const unsigned char*)word);
  PfxEntry* pptr = pStart[sp];

  while (pptr) {
    if (isSubset(pptr->getKey(), word)) {
      rv = pptr->check_twosfx(word, len, in_compound, needflag);
      if (rv) {
        pfx = pptr;
        return rv;
      }
      pptr = pptr->getNextEQ();
    } else {
      pptr = pptr->getNextNE();
    }
  }

  return NULL;
}

// check word for prefixes and morph
std::string AffixMgr::prefix_check_morph(const char* word,
                                         int len,
                                         char in_compound,
                                         const FLAG needflag) {

  std::string result;

  pfx = NULL;
  sfxappnd = NULL;
  sfxextra = 0;

  // first handle the special case of 0 length prefixes
  PfxEntry* pe = pStart[0];
  while (pe) {
    std::string st = pe->check_morph(word, len, in_compound, needflag);
    if (!st.empty()) {
      result.append(st);
    }
    pe = pe->getNext();
  }

  // now handle the general case
  unsigned char sp = *((const unsigned char*)word);
  PfxEntry* pptr = pStart[sp];

  while (pptr) {
    if (isSubset(pptr->getKey(), word)) {
      std::string st = pptr->check_morph(word, len, in_compound, needflag);
      if (!st.empty()) {
        // fogemorpheme
        if ((in_compound != IN_CPD_NOT) ||
            !((pptr->getCont() && (TESTAFF(pptr->getCont(), onlyincompound,
                                           pptr->getContLen()))))) {
          result.append(st);
          pfx = pptr;
        }
      }
      pptr = pptr->getNextEQ();
    } else {
      pptr = pptr->getNextNE();
    }
  }

  return result;
}

// check word for prefixes and morph and two-level suffixes
std::string AffixMgr::prefix_check_twosfx_morph(const char* word,
                                                int len,
                                                char in_compound,
                                                const FLAG needflag) {
  std::string result;

  pfx = NULL;
  sfxappnd = NULL;
  sfxextra = 0;

  // first handle the special case of 0 length prefixes
  PfxEntry* pe = pStart[0];
  while (pe) {
    std::string st = pe->check_twosfx_morph(word, len, in_compound, needflag);
    if (!st.empty()) {
      result.append(st);
    }
    pe = pe->getNext();
  }

  // now handle the general case
  unsigned char sp = *((const unsigned char*)word);
  PfxEntry* pptr = pStart[sp];

  while (pptr) {
    if (isSubset(pptr->getKey(), word)) {
      std::string st = pptr->check_twosfx_morph(word, len, in_compound, needflag);
      if (!st.empty()) {
        result.append(st);
        pfx = pptr;
      }
      pptr = pptr->getNextEQ();
    } else {
      pptr = pptr->getNextNE();
    }
  }

  return result;
}

// Is word a non-compound with a REP substitution (see checkcompoundrep)?
int AffixMgr::cpdrep_check(const char* word, int wl) {

  if ((wl < 2) || get_reptable().empty())
    return 0;

  for (size_t i = 0; i < get_reptable().size(); ++i) {
    // use only available mid patterns
    if (!get_reptable()[i].outstrings[0].empty()) {
      const char* r = word;
      const size_t lenp = get_reptable()[i].pattern.size();
      // search every occurence of the pattern in the word
      while ((r = strstr(r, get_reptable()[i].pattern.c_str())) != NULL) {
        std::string candidate(word);
        candidate.replace(r - word, lenp, get_reptable()[i].outstrings[0]);
        if (candidate_check(candidate.c_str(), candidate.size()))
          return 1;
        ++r;  // search for the next letter
      }
    }
  }

 return 0;
}

// forbid compound words, if they are in the dictionary as a
// word pair separated by space
int AffixMgr::cpdwordpair_check(const char * word, int wl) {
  if (wl > 2) {
    std::string candidate(word);
    for (size_t i = 1; i < candidate.size(); i++) {
      // go to end of the UTF-8 character
      if (utf8 && ((word[i] & 0xc0) == 0x80))
          continue;
      candidate.insert(i, 1, ' ');
      if (candidate_check(candidate.c_str(), candidate.size()))
        return 1;
      candidate.erase(i, 1);
    }
  }

  return 0;
}

// forbid compoundings when there are special patterns at word bound
int AffixMgr::cpdpat_check(const char* word,
                           int pos,
                           hentry* r1,
                           hentry* r2,
                           const char /*affixed*/) {
  for (size_t i = 0; i < checkcpdtable.size(); ++i) {
    size_t len;
    if (isSubset(checkcpdtable[i].pattern2.c_str(), word + pos) &&
        (!r1 || !checkcpdtable[i].cond ||
         (r1->astr && TESTAFF(r1->astr, checkcpdtable[i].cond, r1->alen))) &&
        (!r2 || !checkcpdtable[i].cond2 ||
         (r2->astr && TESTAFF(r2->astr, checkcpdtable[i].cond2, r2->alen))) &&
        // zero length pattern => only TESTAFF
        // zero pattern (0/flag) => unmodified stem (zero affixes allowed)
        (checkcpdtable[i].pattern.empty() ||
         ((checkcpdtable[i].pattern[0] == '0' && r1->blen <= pos &&
           strncmp(word + pos - r1->blen, r1->word, r1->blen) == 0) ||
          (checkcpdtable[i].pattern[0] != '0' &&
           ((len = checkcpdtable[i].pattern.size()) != 0) &&
           strncmp(word + pos - len, checkcpdtable[i].pattern.c_str(), len) == 0)))) {
      return 1;
    }
  }
  return 0;
}

// forbid compounding with neighbouring upper and lower case characters at word
// bounds
int AffixMgr::cpdcase_check(const char* word, int pos) {
  if (utf8) {
    const char* p;
    for (p = word + pos - 1; (*p & 0xc0) == 0x80; p--)
      ;
    std::string pair(p);
    std::vector<w_char> pair_u;
    u8_u16(pair_u, pair);
    unsigned short a = pair_u.size() > 1 ? ((pair_u[1].h << 8) + pair_u[1].l) : 0;
    unsigned short b = !pair_u.empty() ? ((pair_u[0].h << 8) + pair_u[0].l) : 0;
    if (((unicodetoupper(a, langnum) == a) ||
         (unicodetoupper(b, langnum) == b)) &&
        (a != '-') && (b != '-'))
      return 1;
  } else {
    unsigned char a = *(word + pos - 1);
    unsigned char b = *(word + pos);
    if ((csconv[a].ccase || csconv[b].ccase) && (a != '-') && (b != '-'))
      return 1;
  }
  return 0;
}

struct metachar_data {
  signed short btpp;  // metacharacter (*, ?) position for backtracking
  signed short btwp;  // word position for metacharacters
  int btnum;          // number of matched characters in metacharacter
};

// check compound patterns
int AffixMgr::defcpd_check(hentry*** words,
                           short wnum,
                           hentry* rv,
                           hentry** def,
                           char all) {
  int w = 0;

  if (!*words) {
    w = 1;
    *words = def;
  }

  if (!*words) {
    return 0;
  }

  std::vector<metachar_data> btinfo(1);

  short bt = 0;

  (*words)[wnum] = rv;

  // has the last word COMPOUNDRULE flag?
  if (rv->alen == 0) {
    (*words)[wnum] = NULL;
    if (w)
      *words = NULL;
    return 0;
  }
  int ok = 0;
  for (size_t i = 0; i < defcpdtable.size(); ++i) {
    for (size_t j = 0; j < defcpdtable[i].size(); ++j) {
      if (defcpdtable[i][j] != '*' && defcpdtable[i][j] != '?' &&
          TESTAFF(rv->astr, defcpdtable[i][j], rv->alen)) {
        ok = 1;
        break;
      }
    }
  }
  if (ok == 0) {
    (*words)[wnum] = NULL;
    if (w)
      *words = NULL;
    return 0;
  }

  for (size_t i = 0; i < defcpdtable.size(); ++i) {
    size_t pp = 0;  // pattern position
    signed short wp = 0;  // "words" position
    int ok2;
    ok = 1;
    ok2 = 1;
    do {
      while ((pp < defcpdtable[i].size()) && (wp <= wnum)) {
        if (((pp + 1) < defcpdtable[i].size()) &&
            ((defcpdtable[i][pp + 1] == '*') ||
             (defcpdtable[i][pp + 1] == '?'))) {
          int wend = (defcpdtable[i][pp + 1] == '?') ? wp : wnum;
          ok2 = 1;
          pp += 2;
          btinfo[bt].btpp = pp;
          btinfo[bt].btwp = wp;
          while (wp <= wend) {
            if (!(*words)[wp]->alen ||
                !TESTAFF((*words)[wp]->astr, defcpdtable[i][pp - 2],
                         (*words)[wp]->alen)) {
              ok2 = 0;
              break;
            }
            wp++;
          }
          if (wp <= wnum)
            ok2 = 0;
          btinfo[bt].btnum = wp - btinfo[bt].btwp;
          if (btinfo[bt].btnum > 0) {
            ++bt;
            btinfo.resize(bt+1);
          }
          if (ok2)
            break;
        } else {
          ok2 = 1;
          if (!(*words)[wp] || !(*words)[wp]->alen ||
              !TESTAFF((*words)[wp]->astr, defcpdtable[i][pp],
                       (*words)[wp]->alen)) {
            ok = 0;
            break;
          }
          pp++;
          wp++;
          if ((defcpdtable[i].size() == pp) && !(wp > wnum))
            ok = 0;
        }
      }
      if (ok && ok2) {
        size_t r = pp;
        while ((defcpdtable[i].size() > r) && ((r + 1) < defcpdtable[i].size()) &&
               ((defcpdtable[i][r + 1] == '*') ||
                (defcpdtable[i][r + 1] == '?')))
          r += 2;
        if (defcpdtable[i].size() <= r)
          return 1;
      }
      // backtrack
      if (bt)
        do {
          ok = 1;
          btinfo[bt - 1].btnum--;
          pp = btinfo[bt - 1].btpp;
          wp = btinfo[bt - 1].btwp + (signed short)btinfo[bt - 1].btnum;
        } while ((btinfo[bt - 1].btnum < 0) && --bt);
    } while (bt);

    if (ok && ok2 && (!all || (defcpdtable[i].size() <= pp)))
      return 1;

    // check zero ending
    while (ok && ok2 && (defcpdtable[i].size() > pp) &&
           ((pp + 1) < defcpdtable[i].size()) &&
           ((defcpdtable[i][pp + 1] == '*') ||
            (defcpdtable[i][pp + 1] == '?')))
      pp += 2;
    if (ok && ok2 && (defcpdtable[i].size() <= pp))
      return 1;
  }
  (*words)[wnum] = NULL;
  if (w)
    *words = NULL;
  return 0;
}

inline int AffixMgr::candidate_check(const char* word, int len) {

  struct hentry* rv = lookup(word);
  if (rv)
    return 1;

  //  rv = prefix_check(word,len,1);
  //  if (rv) return 1;

  rv = affix_check(word, len);
  if (rv)
    return 1;
  return 0;
}

// calculate number of syllable for compound-checking
short AffixMgr::get_syllable(const std::string& word) {
  if (cpdmaxsyllable == 0)
    return 0;

  short num = 0;

  if (!utf8) {
    for (size_t i = 0; i < word.size(); ++i) {
      if (std::binary_search(cpdvowels.begin(), cpdvowels.end(),
                             word[i])) {
        ++num;
      }
    }
  } else if (!cpdvowels_utf16.empty()) {
    std::vector<w_char> w;
    u8_u16(w, word);
    for (size_t i = 0; i < w.size(); ++i) {
      if (std::binary_search(cpdvowels_utf16.begin(),
                             cpdvowels_utf16.end(),
                             w[i])) {
        ++num;
      }
    }
  }

  return num;
}

void AffixMgr::setcminmax(int* cmin, int* cmax, const char* word, int len) {
  if (utf8) {
    int i;
    for (*cmin = 0, i = 0; (i < cpdmin) && *cmin < len; i++) {
      for ((*cmin)++; *cmin < len && (word[*cmin] & 0xc0) == 0x80; (*cmin)++)
        ;
    }
    for (*cmax = len, i = 0; (i < (cpdmin - 1)) && *cmax >= 0; i++) {
      for ((*cmax)--; *cmax >= 0 && (word[*cmax] & 0xc0) == 0x80; (*cmax)--)
        ;
    }
  } else {
    *cmin = cpdmin;
    *cmax = len - cpdmin + 1;
  }
}

// check if compound word is correctly spelled
// hu_mov_rule = spec. Hungarian rule (XXX)
struct hentry* AffixMgr::compound_check(const std::string& word,
                                        short wordnum,
                                        short numsyllable,
                                        short maxwordnum,
                                        short wnum,
                                        hentry** words = NULL,
                                        hentry** rwords = NULL,
                                        char hu_mov_rule = 0,
                                        char is_sug = 0,
                                        int* info = NULL) {
  int i;
  short oldnumsyllable, oldnumsyllable2, oldwordnum, oldwordnum2;
  struct hentry* rv = NULL;
  struct hentry* rv_first;
  std::string st;
  char ch = '\0';
  int cmin;
  int cmax;
  int striple = 0;
  size_t scpd = 0;
  int soldi = 0;
  int oldcmin = 0;
  int oldcmax = 0;
  int oldlen = 0;
  int checkedstriple = 0;
  char affixed = 0;
  hentry** oldwords = words;
  size_t len = word.size();

  int checked_prefix;

  // add a time limit to handle possible
  // combinatorical explosion of the overlapping words

  HUNSPELL_THREAD_LOCAL clock_t timelimit;

  if (wordnum == 0) {
      // get the start time, seeing as we're reusing this set to 0
      // to flag timeout, use clock() + 1 to avoid start clock()
      // of 0 as being a timeout
      timelimit = clock() + 1;
  }
  else if (timelimit != 0 && (clock() > timelimit + TIMELIMIT)) {
      timelimit = 0;
  }

  setcminmax(&cmin, &cmax, word.c_str(), len);

  st.assign(word);

  for (i = cmin; i < cmax; i++) {
    // go to end of the UTF-8 character
    if (utf8) {
      for (; (st[i] & 0xc0) == 0x80; i++)
        ;
      if (i >= cmax)
        return NULL;
    }

    words = oldwords;
    int onlycpdrule = (words) ? 1 : 0;

    do {  // onlycpdrule loop

      oldnumsyllable = numsyllable;
      oldwordnum = wordnum;
      checked_prefix = 0;

      do {  // simplified checkcompoundpattern loop

        if (timelimit == 0)
          return 0;

        if (scpd > 0) {
          for (; scpd <= checkcpdtable.size() &&
                 (checkcpdtable[scpd - 1].pattern3.empty() ||
                  strncmp(word.c_str() + i, checkcpdtable[scpd - 1].pattern3.c_str(),
                          checkcpdtable[scpd - 1].pattern3.size()) != 0);
               scpd++)
            ;

          if (scpd > checkcpdtable.size())
            break;  // break simplified checkcompoundpattern loop
          st.replace(i, std::string::npos, checkcpdtable[scpd - 1].pattern);
          soldi = i;
          i += checkcpdtable[scpd - 1].pattern.size();
          st.replace(i, std::string::npos, checkcpdtable[scpd - 1].pattern2);
          st.replace(i + checkcpdtable[scpd - 1].pattern2.size(), std::string::npos,
                 word.substr(soldi + checkcpdtable[scpd - 1].pattern3.size()));

          oldlen = len;
          len += checkcpdtable[scpd - 1].pattern.size() +
                 checkcpdtable[scpd - 1].pattern2.size() -
                 checkcpdtable[scpd - 1].pattern3.size();
          oldcmin = cmin;
          oldcmax = cmax;
          setcminmax(&cmin, &cmax, st.c_str(), len);

          cmax = len - cpdmin + 1;
        }

        ch = st[i];
        st[i] = '\0';

        sfx = NULL;
        pfx = NULL;

        // FIRST WORD

        affixed = 1;
        rv = lookup(st.c_str());  // perhaps without prefix

        // forbid dictionary stems with COMPOUNDFORBIDFLAG in
        // compound words, overriding the effect of COMPOUNDPERMITFLAG
        if ((rv) && compoundforbidflag &&
                TESTAFF(rv->astr, compoundforbidflag, rv->alen) && !hu_mov_rule)
            continue;

        // search homonym with compound flag
        while ((rv) && !hu_mov_rule &&
               ((needaffix && TESTAFF(rv->astr, needaffix, rv->alen)) ||
                !((compoundflag && !words && !onlycpdrule &&
                   TESTAFF(rv->astr, compoundflag, rv->alen)) ||
                  (compoundbegin && !wordnum && !onlycpdrule &&
                   TESTAFF(rv->astr, compoundbegin, rv->alen)) ||
                  (compoundmiddle && wordnum && !words && !onlycpdrule &&
                   TESTAFF(rv->astr, compoundmiddle, rv->alen)) ||
                  (!defcpdtable.empty() && onlycpdrule &&
                   ((!words && !wordnum &&
                     defcpd_check(&words, wnum, rv, rwords, 0)) ||
                    (words &&
                     defcpd_check(&words, wnum, rv, rwords, 0))))) ||
                (scpd != 0 && checkcpdtable[scpd - 1].cond != FLAG_NULL &&
                 !TESTAFF(rv->astr, checkcpdtable[scpd - 1].cond, rv->alen)))) {
          rv = rv->next_homonym;
        }

        if (rv)
          affixed = 0;

        if (!rv) {
          if (onlycpdrule)
            break;
          if (compoundflag &&
              !(rv = prefix_check(st.c_str(), i,
                                  hu_mov_rule ? IN_CPD_OTHER : IN_CPD_BEGIN,
                                  compoundflag))) {
            if (((rv = suffix_check(
                      st.c_str(), i, 0, NULL, FLAG_NULL, compoundflag,
                      hu_mov_rule ? IN_CPD_OTHER : IN_CPD_BEGIN)) ||
                 (compoundmoresuffixes &&
                  (rv = suffix_check_twosfx(st.c_str(), i, 0, NULL, compoundflag)))) &&
                !hu_mov_rule && sfx->getCont() &&
                ((compoundforbidflag &&
                  TESTAFF(sfx->getCont(), compoundforbidflag,
                          sfx->getContLen())) ||
                 (compoundend &&
                  TESTAFF(sfx->getCont(), compoundend, sfx->getContLen())))) {
              rv = NULL;
            }
          }

          if (rv ||
              (((wordnum == 0) && compoundbegin &&
                ((rv = suffix_check(
                      st.c_str(), i, 0, NULL, FLAG_NULL, compoundbegin,
                      hu_mov_rule ? IN_CPD_OTHER : IN_CPD_BEGIN)) ||
                 (compoundmoresuffixes &&
                  (rv = suffix_check_twosfx(
                       st.c_str(), i, 0, NULL,
                       compoundbegin))) ||  // twofold suffixes + compound
                 (rv = prefix_check(st.c_str(), i,
                                    hu_mov_rule ? IN_CPD_OTHER : IN_CPD_BEGIN,
                                    compoundbegin)))) ||
               ((wordnum > 0) && compoundmiddle &&
                ((rv = suffix_check(
                      st.c_str(), i, 0, NULL, FLAG_NULL, compoundmiddle,
                      hu_mov_rule ? IN_CPD_OTHER : IN_CPD_BEGIN)) ||
                 (compoundmoresuffixes &&
                  (rv = suffix_check_twosfx(
                       st.c_str(), i, 0, NULL,
                       compoundmiddle))) ||  // twofold suffixes + compound
                 (rv = prefix_check(st.c_str(), i,
                                    hu_mov_rule ? IN_CPD_OTHER : IN_CPD_BEGIN,
                                    compoundmiddle))))))
            checked_prefix = 1;
          // else check forbiddenwords and needaffix
        } else if (rv->astr && (TESTAFF(rv->astr, forbiddenword, rv->alen) ||
                                TESTAFF(rv->astr, needaffix, rv->alen) ||
                                TESTAFF(rv->astr, ONLYUPCASEFLAG, rv->alen) ||
                                (is_sug && nosuggest &&
                                 TESTAFF(rv->astr, nosuggest, rv->alen)))) {
          st[i] = ch;
          // continue;
          break;
        }

        // check non_compound flag in suffix and prefix
        if ((rv) && !hu_mov_rule &&
            ((pfx && pfx->getCont() &&
              TESTAFF(pfx->getCont(), compoundforbidflag, pfx->getContLen())) ||
             (sfx && sfx->getCont() &&
              TESTAFF(sfx->getCont(), compoundforbidflag,
                      sfx->getContLen())))) {
          rv = NULL;
        }

        // check compoundend flag in suffix and prefix
        if ((rv) && !checked_prefix && compoundend && !hu_mov_rule &&
            ((pfx && pfx->getCont() &&
              TESTAFF(pfx->getCont(), compoundend, pfx->getContLen())) ||
             (sfx && sfx->getCont() &&
              TESTAFF(sfx->getCont(), compoundend, sfx->getContLen())))) {
          rv = NULL;
        }

        // check compoundmiddle flag in suffix and prefix
        if ((rv) && !checked_prefix && (wordnum == 0) && compoundmiddle &&
            !hu_mov_rule &&
            ((pfx && pfx->getCont() &&
              TESTAFF(pfx->getCont(), compoundmiddle, pfx->getContLen())) ||
             (sfx && sfx->getCont() &&
              TESTAFF(sfx->getCont(), compoundmiddle, sfx->getContLen())))) {
          rv = NULL;
        }

        // check forbiddenwords
        if ((rv) && (rv->astr) &&
            (TESTAFF(rv->astr, forbiddenword, rv->alen) ||
             TESTAFF(rv->astr, ONLYUPCASEFLAG, rv->alen) ||
             (is_sug && nosuggest && TESTAFF(rv->astr, nosuggest, rv->alen)))) {
          return NULL;
        }

        // increment word number, if the second root has a compoundroot flag
        if ((rv) && compoundroot &&
            (TESTAFF(rv->astr, compoundroot, rv->alen))) {
          wordnum++;
        }

        // first word is acceptable in compound words?
        if (((rv) &&
             (checked_prefix || (words && words[wnum]) ||
              (compoundflag && TESTAFF(rv->astr, compoundflag, rv->alen)) ||
              ((oldwordnum == 0) && compoundbegin &&
               TESTAFF(rv->astr, compoundbegin, rv->alen)) ||
              ((oldwordnum > 0) && compoundmiddle &&
               TESTAFF(rv->astr, compoundmiddle, rv->alen))

              // LANG_hu section: spec. Hungarian rule
              || ((langnum == LANG_hu) && hu_mov_rule &&
                  (TESTAFF(
                       rv->astr, 'F',
                       rv->alen) ||  // XXX hardwired Hungarian dictionary codes
                   TESTAFF(rv->astr, 'G', rv->alen) ||
                   TESTAFF(rv->astr, 'H', rv->alen)))
              // END of LANG_hu section
              ) &&
             (
                 // test CHECKCOMPOUNDPATTERN conditions
                 scpd == 0 || checkcpdtable[scpd - 1].cond == FLAG_NULL ||
                 TESTAFF(rv->astr, checkcpdtable[scpd - 1].cond, rv->alen)) &&
             !((checkcompoundtriple && scpd == 0 &&
                !words &&  // test triple letters
                (word[i - 1] == word[i]) &&
                (((i > 1) && (word[i - 1] == word[i - 2])) ||
                 ((word[i - 1] == word[i + 1]))  // may be word[i+1] == '\0'
                 )) ||
               (checkcompoundcase && scpd == 0 && !words &&
                cpdcase_check(word.c_str(), i))))
            // LANG_hu section: spec. Hungarian rule
            || ((!rv) && (langnum == LANG_hu) && hu_mov_rule &&
                (rv = affix_check(st.c_str(), i)) &&
                (sfx && sfx->getCont() &&
                 (  // XXX hardwired Hungarian dic. codes
                     TESTAFF(sfx->getCont(), (unsigned short)'x',
                             sfx->getContLen()) ||
                     TESTAFF(
                         sfx->getCont(), (unsigned short)'%',
                         sfx->getContLen()))))) {  // first word is ok condition

          // LANG_hu section: spec. Hungarian rule
          if (langnum == LANG_hu) {
            // calculate syllable number of the word
            numsyllable += get_syllable(st.substr(0, i));
            // + 1 word, if syllable number of the prefix > 1 (hungarian
            // convention)
            if (pfx && (get_syllable(pfx->getKey()) > 1))
              wordnum++;
          }
          // END of LANG_hu section

          // NEXT WORD(S)
          rv_first = rv;
          st[i] = ch;

          do {  // striple loop

            // check simplifiedtriple
            if (simplifiedtriple) {
              if (striple) {
                checkedstriple = 1;
                i--;  // check "fahrt" instead of "ahrt" in "Schiffahrt"
              } else if (i > 2 && word[i - 1] == word[i - 2])
                striple = 1;
            }

            rv = lookup(st.c_str() + i);  // perhaps without prefix

            // search homonym with compound flag
            while ((rv) &&
                   ((needaffix && TESTAFF(rv->astr, needaffix, rv->alen)) ||
                    !((compoundflag && !words &&
                       TESTAFF(rv->astr, compoundflag, rv->alen)) ||
                      (compoundend && !words &&
                       TESTAFF(rv->astr, compoundend, rv->alen)) ||
                      (!defcpdtable.empty() && words &&
                       defcpd_check(&words, wnum + 1, rv, NULL, 1))) ||
                    (scpd != 0 && checkcpdtable[scpd - 1].cond2 != FLAG_NULL &&
                     !TESTAFF(rv->astr, checkcpdtable[scpd - 1].cond2,
                              rv->alen)))) {
              rv = rv->next_homonym;
            }

            // check FORCEUCASE
            if (rv && forceucase && (rv) &&
                (TESTAFF(rv->astr, forceucase, rv->alen)) &&
                !(info && *info & SPELL_ORIGCAP))
              rv = NULL;

            if (rv && words && words[wnum + 1])
              return rv_first;

            oldnumsyllable2 = numsyllable;
            oldwordnum2 = wordnum;

            // LANG_hu section: spec. Hungarian rule, XXX hardwired dictionary
            // code
            if ((rv) && (langnum == LANG_hu) &&
                (TESTAFF(rv->astr, 'I', rv->alen)) &&
                !(TESTAFF(rv->astr, 'J', rv->alen))) {
              numsyllable--;
            }
            // END of LANG_hu section

            // increment word number, if the second root has a compoundroot flag
            if ((rv) && (compoundroot) &&
                (TESTAFF(rv->astr, compoundroot, rv->alen))) {
              wordnum++;
            }

            // check forbiddenwords
            if ((rv) && (rv->astr) &&
                (TESTAFF(rv->astr, forbiddenword, rv->alen) ||
                 TESTAFF(rv->astr, ONLYUPCASEFLAG, rv->alen) ||
                 (is_sug && nosuggest &&
                  TESTAFF(rv->astr, nosuggest, rv->alen))))
              return NULL;

            // second word is acceptable, as a root?
            // hungarian conventions: compounding is acceptable,
            // when compound forms consist of 2 words, or if more,
            // then the syllable number of root words must be 6, or lesser.

            if ((rv) &&
                ((compoundflag && TESTAFF(rv->astr, compoundflag, rv->alen)) ||
                 (compoundend && TESTAFF(rv->astr, compoundend, rv->alen))) &&
                (((cpdwordmax == -1) || (wordnum + 1 < cpdwordmax)) ||
                 ((cpdmaxsyllable != 0) &&
                  (numsyllable + get_syllable(std::string(HENTRY_WORD(rv), rv->blen)) <=
                   cpdmaxsyllable))) &&
                (
                    // test CHECKCOMPOUNDPATTERN
                    checkcpdtable.empty() || scpd != 0 ||
                    !cpdpat_check(word.c_str(), i, rv_first, rv, 0)) &&
                ((!checkcompounddup || (rv != rv_first)))
                // test CHECKCOMPOUNDPATTERN conditions
                &&
                (scpd == 0 || checkcpdtable[scpd - 1].cond2 == FLAG_NULL ||
                 TESTAFF(rv->astr, checkcpdtable[scpd - 1].cond2, rv->alen))) {
              // forbid compound word, if it is a non-compound word with typical
              // fault
              if ((checkcompoundrep && cpdrep_check(word.c_str(), len)) ||
                      cpdwordpair_check(word.c_str(), len))
                return NULL;
              return rv_first;
            }

            numsyllable = oldnumsyllable2;
            wordnum = oldwordnum2;

            // perhaps second word has prefix or/and suffix
            sfx = NULL;
            sfxflag = FLAG_NULL;
            rv = (compoundflag && !onlycpdrule)
                     ? affix_check((word.c_str() + i), strlen(word.c_str() + i), compoundflag,
                                   IN_CPD_END)
                     : NULL;
            if (!rv && compoundend && !onlycpdrule) {
              sfx = NULL;
              pfx = NULL;
              rv = affix_check((word.c_str() + i), strlen(word.c_str() + i), compoundend,
                               IN_CPD_END);
            }

            if (!rv && !defcpdtable.empty() && words) {
              rv = affix_check((word.c_str() + i), strlen(word.c_str() + i), 0, IN_CPD_END);
              if (rv && defcpd_check(&words, wnum + 1, rv, NULL, 1))
                return rv_first;
              rv = NULL;
            }

            // test CHECKCOMPOUNDPATTERN conditions (allowed forms)
            if (rv &&
                !(scpd == 0 || checkcpdtable[scpd - 1].cond2 == FLAG_NULL ||
                  TESTAFF(rv->astr, checkcpdtable[scpd - 1].cond2, rv->alen)))
              rv = NULL;

            // test CHECKCOMPOUNDPATTERN conditions (forbidden compounds)
            if (rv && !checkcpdtable.empty() && scpd == 0 &&
                cpdpat_check(word.c_str(), i, rv_first, rv, affixed))
              rv = NULL;

            // check non_compound flag in suffix and prefix
            if ((rv) && ((pfx && pfx->getCont() &&
                          TESTAFF(pfx->getCont(), compoundforbidflag,
                                  pfx->getContLen())) ||
                         (sfx && sfx->getCont() &&
                          TESTAFF(sfx->getCont(), compoundforbidflag,
                                  sfx->getContLen())))) {
              rv = NULL;
            }

            // check FORCEUCASE
            if (rv && forceucase && (rv) &&
                (TESTAFF(rv->astr, forceucase, rv->alen)) &&
                !(info && *info & SPELL_ORIGCAP))
              rv = NULL;

            // check forbiddenwords
            if ((rv) && (rv->astr) &&
                (TESTAFF(rv->astr, forbiddenword, rv->alen) ||
                 TESTAFF(rv->astr, ONLYUPCASEFLAG, rv->alen) ||
                 (is_sug && nosuggest &&
                  TESTAFF(rv->astr, nosuggest, rv->alen))))
              return NULL;

            // pfxappnd = prefix of word+i, or NULL
            // calculate syllable number of prefix.
            // hungarian convention: when syllable number of prefix is more,
            // than 1, the prefix+word counts as two words.

            if (langnum == LANG_hu) {
              // calculate syllable number of the word
              numsyllable += get_syllable(word.c_str() + i);

              // - affix syllable num.
              // XXX only second suffix (inflections, not derivations)
              if (sfxappnd) {
                std::string tmp(sfxappnd);
                reverseword(tmp);
                numsyllable -= short(get_syllable(tmp) + sfxextra);
              } else {
                numsyllable -= short(sfxextra);
              }

              // + 1 word, if syllable number of the prefix > 1 (hungarian
              // convention)
              if (pfx && (get_syllable(pfx->getKey()) > 1))
                wordnum++;

              // increment syllable num, if last word has a SYLLABLENUM flag
              // and the suffix is beginning `s'

              if (!cpdsyllablenum.empty()) {
                switch (sfxflag) {
                  case 'c': {
                    numsyllable += 2;
                    break;
                  }
                  case 'J': {
                    numsyllable += 1;
                    break;
                  }
                  case 'I': {
                    if (rv && TESTAFF(rv->astr, 'J', rv->alen))
                      numsyllable += 1;
                    break;
                  }
                }
              }
            }

            // increment word number, if the second word has a compoundroot flag
            if ((rv) && (compoundroot) &&
                (TESTAFF(rv->astr, compoundroot, rv->alen))) {
              wordnum++;
            }
            // second word is acceptable, as a word with prefix or/and suffix?
            // hungarian conventions: compounding is acceptable,
            // when compound forms consist 2 word, otherwise
--> --------------------

--> maximum size reached

--> --------------------