src/myspell/suggestmgr.cxx

   1 #include "license.hunspell"
   2 #include "license.myspell"
   3
   4 #include <stdlib.h>
   5 #include <string.h>
   6 #include <stdio.h>
   7 #include <ctype.h>
   8
   9 #include "suggestmgr.hxx"
  10 #include "htypes.hxx"
  11 #include "csutil.hxx"
  12
  13 const w_char W_VLINE = { '\0', '|' };
  14
  15 SuggestMgr::SuggestMgr(const char * tryme, int maxn,
  16                        AffixMgr * aptr)
  17 {
  18
  19   // register affix manager and check in string of chars to
  20   // try when building candidate suggestions
  21   pAMgr = aptr;
  22
  23   csconv = NULL;
  24
  25   ckeyl = 0;
  26   ckey = NULL;
  27   ckey_utf = NULL;
  28
  29   ctryl = 0;
  30   ctry = NULL;
  31   ctry_utf = NULL;
  32
  33   utf8 = 0;
  34   langnum = 0;
  35   complexprefixes = 0;
  36
  37   maxSug = maxn;
  38   nosplitsugs = 0;
  39   maxngramsugs = MAXNGRAMSUGS;
  40   maxcpdsugs = MAXCOMPOUNDSUGS;
  41
  42   if (pAMgr) {
  43         langnum = pAMgr->get_langnum();
  44         ckey = pAMgr->get_key_string();
  45         nosplitsugs = pAMgr->get_nosplitsugs();
  46         if (pAMgr->get_maxngramsugs() >= 0)
  47             maxngramsugs = pAMgr->get_maxngramsugs();
  48         utf8 = pAMgr->get_utf8();
  49         if (pAMgr->get_maxcpdsugs() >= 0)
  50             maxcpdsugs = pAMgr->get_maxcpdsugs();
  51         if (!utf8)
  52         {
  53             char * enc = pAMgr->get_encoding();
  54             csconv = get_current_cs(enc);
  55             free(enc);
  56         }
  57         complexprefixes = pAMgr->get_complexprefixes();
  58   }
  59
  60   if (ckey) {
  61     if (utf8) {
  62         w_char t[MAXSWL];
  63         ckeyl = u8_u16(t, MAXSWL, ckey);
  64         ckey_utf = (w_char *) malloc(ckeyl * sizeof(w_char));
  65         if (ckey_utf) memcpy(ckey_utf, t, ckeyl * sizeof(w_char));
  66         else ckeyl = 0;
  67     } else {
  68         ckeyl = strlen(ckey);
  69     }
  70   }
  71
  72   if (tryme) {
  73     ctry = mystrdup(tryme);
  74     if (ctry) ctryl = strlen(ctry);
  75     if (ctry && utf8) {
  76         w_char t[MAXSWL];
  77         ctryl = u8_u16(t, MAXSWL, tryme);
  78         ctry_utf = (w_char *) malloc(ctryl * sizeof(w_char));
  79         if (ctry_utf) memcpy(ctry_utf, t, ctryl * sizeof(w_char));
  80         else ctryl = 0;
  81     }
  82   }
  83 }
  84
  85
  86 SuggestMgr::~SuggestMgr()
  87 {
  88   pAMgr = NULL;
  89   if (ckey) free(ckey);
  90   ckey = NULL;
  91   if (ckey_utf) free(ckey_utf);
  92   ckey_utf = NULL;
  93   ckeyl = 0;
  94   if (ctry) free(ctry);
  95   ctry = NULL;
  96   if (ctry_utf) free(ctry_utf);
  97   ctry_utf = NULL;
  98   ctryl = 0;
  99   maxSug = 0;
 100 #ifdef MOZILLA_CLIENT
 101   delete [] csconv;
 102 #endif
 103 }
 104
 105 int SuggestMgr::testsug(char** wlst, const char * candidate, int wl, int ns, int cpdsuggest,
 106    int * timer, clock_t * timelimit) {
 107       int cwrd = 1;
 108       if (ns == maxSug) return maxSug;
 109       for (int k=0; k < ns; k++) {
 110         if (strcmp(candidate,wlst[k]) == 0) cwrd = 0;
 111       }
 112       if ((cwrd) && checkword(candidate, wl, cpdsuggest, timer, timelimit)) {
 113         wlst[ns] = mystrdup(candidate);
 114         if (wlst[ns] == NULL) {
 115             for (int j=0; j<ns; j++) free(wlst[j]);
 116             return -1;
 117         }
 118         ns++;
 119       }
 120       return ns;
 121 }
 122
 123 // generate suggestions for a misspelled word
 124 //    pass in address of array of char * pointers
 125 // onlycompoundsug: probably bad suggestions (need for ngram sugs, too)
 126
 127 int SuggestMgr::suggest(char*** slst, const char * w, int nsug,
 128     int * onlycompoundsug)
 129 {
 130   int nocompoundtwowords = 0;
 131   char ** wlst;
 132   w_char word_utf[MAXSWL];
 133   int wl = 0;
 134   int nsugorig = nsug;
 135   char w2[MAXWORDUTF8LEN];
 136   const char * word = w;
 137   int oldSug = 0;
 138
 139   // word reversing wrapper for complex prefixes
 140   if (complexprefixes) {
 141     strcpy(w2, w);
 142     if (utf8) reverseword_utf(w2); else reverseword(w2);
 143     word = w2;
 144   }
 145
 146     if (*slst) {
 147         wlst = *slst;
 148     } else {
 149         wlst = (char **) malloc(maxSug * sizeof(char *));
 150         if (wlst == NULL) return -1;
 151         for (int i = 0; i < maxSug; i++) {
 152             wlst[i] = NULL;
 153         }
 154     }
 155
 156     if (utf8) {
 157         wl = u8_u16(word_utf, MAXSWL, word);
 158     }
 159
 160     for (int cpdsuggest=0; (cpdsuggest<2) && (nocompoundtwowords==0); cpdsuggest++) {
 161
 162     // limit compound suggestion
 163     if (cpdsuggest > 0) oldSug = nsug;
 164
 165     // suggestions for an uppercase word (html -> HTML)
 166     if ((nsug < maxSug) && (nsug > -1)) {
 167         nsug = (utf8) ? capchars_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 168                     capchars(wlst, word, nsug, cpdsuggest);
 169     }
 170
 171     // perhaps we made a typical fault of spelling
 172     if ((nsug < maxSug) && (nsug > -1) && (!cpdsuggest || (nsug < oldSug + maxcpdsugs))) {
 173       nsug = replchars(wlst, word, nsug, cpdsuggest);
 174     }
 175
 176     // perhaps we made chose the wrong char from a related set
 177     if ((nsug < maxSug) && (nsug > -1) && (!cpdsuggest || (nsug < oldSug + maxcpdsugs))) {
 178       nsug = mapchars(wlst, word, nsug, cpdsuggest);
 179     }
 180
 181     // did we swap the order of chars by mistake
 182     if ((nsug < maxSug) && (nsug > -1) && (!cpdsuggest || (nsug < oldSug + maxcpdsugs))) {
 183         nsug = (utf8) ? swapchar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 184                     swapchar(wlst, word, nsug, cpdsuggest);
 185     }
 186
 187     // did we swap the order of non adjacent chars by mistake
 188     if ((nsug < maxSug) && (nsug > -1) && (!cpdsuggest || (nsug < oldSug + maxcpdsugs))) {
 189         nsug = (utf8) ? longswapchar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 190                     longswapchar(wlst, word, nsug, cpdsuggest);
 191     }
 192
 193     // did we just hit the wrong key in place of a good char (case and keyboard)
 194     if ((nsug < maxSug) && (nsug > -1) && (!cpdsuggest || (nsug < oldSug + maxcpdsugs))) {
 195         nsug = (utf8) ? badcharkey_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 196                     badcharkey(wlst, word, nsug, cpdsuggest);
 197     }
 198
 199     // only suggest compound words when no other suggestion
 200     if ((cpdsuggest == 0) && (nsug > nsugorig)) nocompoundtwowords=1;
 201
 202     // did we add a char that should not be there
 203     if ((nsug < maxSug) && (nsug > -1) && (!cpdsuggest || (nsug < oldSug + maxcpdsugs))) {
 204         nsug = (utf8) ? extrachar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 205                     extrachar(wlst, word, nsug, cpdsuggest);
 206     }
 207
 208
 209     // did we forgot a char
 210     if ((nsug < maxSug) && (nsug > -1) && (!cpdsuggest || (nsug < oldSug + maxcpdsugs))) {
 211         nsug = (utf8) ? forgotchar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 212                     forgotchar(wlst, word, nsug, cpdsuggest);
 213     }
 214
 215     // did we move a char
 216     if ((nsug < maxSug) && (nsug > -1) && (!cpdsuggest || (nsug < oldSug + maxcpdsugs))) {
 217         nsug = (utf8) ? movechar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 218                     movechar(wlst, word, nsug, cpdsuggest);
 219     }
 220
 221     // did we just hit the wrong key in place of a good char
 222     if ((nsug < maxSug) && (nsug > -1) && (!cpdsuggest || (nsug < oldSug + maxcpdsugs))) {
 223         nsug = (utf8) ? badchar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 224                     badchar(wlst, word, nsug, cpdsuggest);
 225     }
 226
 227     // did we double two characters
 228     if ((nsug < maxSug) && (nsug > -1) && (!cpdsuggest || (nsug < oldSug + maxcpdsugs))) {
 229         nsug = (utf8) ? doubletwochars_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 230                     doubletwochars(wlst, word, nsug, cpdsuggest);
 231     }
 232
 233     // perhaps we forgot to hit space and two words ran together
 234     if (!nosplitsugs && (nsug < maxSug) && (nsug > -1) && (!cpdsuggest || (nsug < oldSug + maxcpdsugs))) {
 235         nsug = twowords(wlst, word, nsug, cpdsuggest);
 236     }
 237
 238     } // repeating ``for'' statement compounding support
 239
 240     if (nsug < 0) {
 241      // we ran out of memory - we should free up as much as possible
 242        for (int i = 0; i < maxSug; i++)
 243          if (wlst[i] != NULL) free(wlst[i]);
 244        free(wlst);
 245        wlst = NULL;
 246     }
 247
 248     if (!nocompoundtwowords && (nsug > 0) && onlycompoundsug) *onlycompoundsug = 1;
 249
 250     *slst = wlst;
 251     return nsug;
 252 }
 253
 254 // generate suggestions for a word with typical mistake
 255 //    pass in address of array of char * pointers
 256 #ifdef HUNSPELL_EXPERIMENTAL
 257 int SuggestMgr::suggest_auto(char*** slst, const char * w, int nsug)
 258 {
 259     int nocompoundtwowords = 0;
 260     char ** wlst;
 261     int oldSug;
 262
 263   char w2[MAXWORDUTF8LEN];
 264   const char * word = w;
 265
 266   // word reversing wrapper for complex prefixes
 267   if (complexprefixes) {
 268     strcpy(w2, w);
 269     if (utf8) reverseword_utf(w2); else reverseword(w2);
 270     word = w2;
 271   }
 272
 273     if (*slst) {
 274         wlst = *slst;
 275     } else {
 276         wlst = (char **) malloc(maxSug * sizeof(char *));
 277         if (wlst == NULL) return -1;
 278     }
 279
 280     for (int cpdsuggest=0; (cpdsuggest<2) && (nocompoundtwowords==0); cpdsuggest++) {
 281
 282     // limit compound suggestion
 283     if (cpdsuggest > 0) oldSug = nsug;
 284
 285     // perhaps we made a typical fault of spelling
 286     if ((nsug < maxSug) && (nsug > -1))
 287     nsug = replchars(wlst, word, nsug, cpdsuggest);
 288
 289     // perhaps we made chose the wrong char from a related set
 290     if ((nsug < maxSug) && (nsug > -1) && (!cpdsuggest || (nsug < oldSug + maxcpdsugs)))
 291       nsug = mapchars(wlst, word, nsug, cpdsuggest);
 292
 293     if ((cpdsuggest==0) && (nsug>0)) nocompoundtwowords=1;
 294
 295     // perhaps we forgot to hit space and two words ran together
 296
 297     if ((nsug < maxSug) && (nsug > -1) && (!cpdsuggest || (nsug < oldSug + maxcpdsugs)) && check_forbidden(word, strlen(word))) {
 298                 nsug = twowords(wlst, word, nsug, cpdsuggest);
 299         }
 300
 301     } // repeating ``for'' statement compounding support
 302
 303     if (nsug < 0) {
 304        for (int i=0;i<maxSug; i++)
 305          if (wlst[i] != NULL) free(wlst[i]);
 306        free(wlst);
 307        return -1;
 308     }
 309
 310     *slst = wlst;
 311     return nsug;
 312 }
 313 #endif // END OF HUNSPELL_EXPERIMENTAL CODE
 314
 315 // suggestions for an uppercase word (html -> HTML)
 316 int SuggestMgr::capchars_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 317 {
 318   char candidate[MAXSWUTF8L];
 319   w_char candidate_utf[MAXSWL];
 320   memcpy(candidate_utf, word, wl * sizeof(w_char));
 321   mkallcap_utf(candidate_utf, wl, langnum);
 322   u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 323   return testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 324 }
 325
 326 // suggestions for an uppercase word (html -> HTML)
 327 int SuggestMgr::capchars(char** wlst, const char * word, int ns, int cpdsuggest)
 328 {
 329   char candidate[MAXSWUTF8L];
 330   strcpy(candidate, word);
 331   mkallcap(candidate, csconv);
 332   return testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 333 }
 334
 335 // suggestions for when chose the wrong char out of a related set
 336 int SuggestMgr::mapchars(char** wlst, const char * word, int ns, int cpdsuggest)
 337 {
 338   char candidate[MAXSWUTF8L];
 339   clock_t timelimit;
 340   int timer;
 341   candidate[0] = '\0';
 342
 343   int wl = strlen(word);
 344   if (wl < 2 || ! pAMgr) return ns;
 345
 346   int nummap = pAMgr->get_nummap();
 347   struct mapentry* maptable = pAMgr->get_maptable();
 348   if (maptable==NULL) return ns;
 349
 350   timelimit = clock();
 351   timer = MINTIMER;
 352   return map_related(word, (char *) &candidate, 0, 0, wlst, cpdsuggest, ns, maptable, nummap, &timer, &timelimit);
 353 }
 354
 355 int SuggestMgr::map_related(const char * word, char * candidate, int wn, int cn,
 356     char** wlst, int cpdsuggest,  int ns,
 357     const mapentry* maptable, int nummap, int * timer, clock_t * timelimit)
 358 {
 359   if (*(word + wn) == '\0') {
 360       int cwrd = 1;
 361       *(candidate + cn) = '\0';
 362       int wl = strlen(candidate);
 363       for (int m=0; m < ns; m++)
 364           if (strcmp(candidate, wlst[m]) == 0) cwrd = 0;
 365       if ((cwrd) && checkword(candidate, wl, cpdsuggest, timer, timelimit)) {
 366           if (ns < maxSug) {
 367               wlst[ns] = mystrdup(candidate);
 368               if (wlst[ns] == NULL) return -1;
 369               ns++;
 370           }
 371       }
 372       return ns;
 373   }
 374   int in_map = 0;
 375   for (int j = 0; j < nummap; j++) {
 376     for (int k = 0; k < maptable[j].len; k++) {
 377       int len = strlen(maptable[j].set[k]);
 378       if (strncmp(maptable[j].set[k], word + wn, len) == 0) {
 379         in_map = 1;
 380         for (int l = 0; l < maptable[j].len; l++) {
 381           strcpy(candidate + cn, maptable[j].set[l]);
 382           ns = map_related(word, candidate, wn + len, strlen(candidate), wlst,
 383                 cpdsuggest, ns, maptable, nummap, timer, timelimit);
 384           if (!(*timer)) return ns;
 385         }
 386       }
 387     }
 388   }
 389   if (!in_map) {
 390      *(candidate + cn) = *(word + wn);
 391      ns = map_related(word, candidate, wn + 1, cn + 1, wlst, cpdsuggest,
 392         ns, maptable, nummap, timer, timelimit);
 393   }
 394   return ns;
 395 }
 396
 397 // suggestions for a typical fault of spelling, that
 398 // differs with more, than 1 letter from the right form.
 399 int SuggestMgr::replchars(char** wlst, const char * word, int ns, int cpdsuggest)
 400 {
 401   char candidate[MAXSWUTF8L];
 402   const char * r;
 403   int lenr, lenp;
 404   int wl = strlen(word);
 405   if (wl < 2 || ! pAMgr) return ns;
 406   int numrep = pAMgr->get_numrep();
 407   struct replentry* reptable = pAMgr->get_reptable();
 408   if (reptable==NULL) return ns;
 409   for (int i=0; i < numrep; i++ ) {
 410       r = word;
 411       lenr = strlen(reptable[i].pattern2);
 412       lenp = strlen(reptable[i].pattern);
 413       // search every occurence of the pattern in the word
 414       while ((r=strstr(r, reptable[i].pattern)) != NULL && (!reptable[i].end || strlen(r) == strlen(reptable[i].pattern)) &&
 415         (!reptable[i].start || r == word)) {
 416           strcpy(candidate, word);
 417           if (r-word + lenr + strlen(r+lenp) >= MAXSWUTF8L) break;
 418           strcpy(candidate+(r-word),reptable[i].pattern2);
 419           strcpy(candidate+(r-word)+lenr, r+lenp);
 420           ns = testsug(wlst, candidate, wl-lenp+lenr, ns, cpdsuggest, NULL, NULL);
 421           if (ns == -1) return -1;
 422           // check REP suggestions with space
 423           char * sp = strchr(candidate, ' ');
 424           if (sp) {
 425             char * prev = candidate;
 426             while (sp) {
 427               *sp = '\0';
 428               if (checkword(prev, strlen(prev), 0, NULL, NULL)) {
 429                 int oldns = ns;
 430                 *sp = ' ';
 431                 ns = testsug(wlst, sp + 1, strlen(sp + 1), ns, cpdsuggest, NULL, NULL);
 432                 if (ns == -1) return -1;
 433                 if (oldns < ns) {
 434                   free(wlst[ns - 1]);
 435                   wlst[ns - 1] = mystrdup(candidate);
 436                   if (!wlst[ns - 1]) return -1;
 437                 }
 438               }
 439               *sp = ' ';
 440               prev = sp + 1;
 441               sp = strchr(prev, ' ');
 442             }
 443           }
 444           r++; // search for the next letter
 445       }
 446    }
 447    return ns;
 448 }
 449
 450 // perhaps we doubled two characters (pattern aba -> ababa, for example vacation -> vacacation)
 451 int SuggestMgr::doubletwochars(char** wlst, const char * word, int ns, int cpdsuggest)
 452 {
 453   char candidate[MAXSWUTF8L];
 454   int state=0;
 455   int wl = strlen(word);
 456   if (wl < 5 || ! pAMgr) return ns;
 457   for (int i=2; i < wl; i++ ) {
 458       if (word[i]==word[i-2]) {
 459           state++;
 460           if (state==3) {
 461             strcpy(candidate,word);
 462             strcpy(candidate+i-1,word+i+1);
 463             ns = testsug(wlst, candidate, wl-2, ns, cpdsuggest, NULL, NULL);
 464             if (ns == -1) return -1;
 465             state=0;
 466           }
 467       } else {
 468             state=0;
 469       }
 470   }
 471   return ns;
 472 }
 473
 474 // perhaps we doubled two characters (pattern aba -> ababa, for example vacation -> vacacation)
 475 int SuggestMgr::doubletwochars_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 476 {
 477   w_char        candidate_utf[MAXSWL];
 478   char          candidate[MAXSWUTF8L];
 479   int state=0;
 480   if (wl < 5 || ! pAMgr) return ns;
 481   for (int i=2; i < wl; i++) {
 482       if (w_char_eq(word[i], word[i-2]))  {
 483           state++;
 484           if (state==3) {
 485             memcpy(candidate_utf, word, (i - 1) * sizeof(w_char));
 486             memcpy(candidate_utf+i-1, word+i+1, (wl-i-1) * sizeof(w_char));
 487             u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl-2);
 488             ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 489             if (ns == -1) return -1;
 490             state=0;
 491           }
 492       } else {
 493             state=0;
 494       }
 495   }
 496   return ns;
 497 }
 498
 499 // error is wrong char in place of correct one (case and keyboard related version)
 500 int SuggestMgr::badcharkey(char ** wlst, const char * word, int ns, int cpdsuggest)
 501 {
 502   char  tmpc;
 503   char  candidate[MAXSWUTF8L];
 504   int wl = strlen(word);
 505   strcpy(candidate, word);
 506   // swap out each char one by one and try uppercase and neighbor
 507   // keyboard chars in its place to see if that makes a good word
 508
 509   for (int i=0; i < wl; i++) {
 510     tmpc = candidate[i];
 511     // check with uppercase letters
 512     candidate[i] = csconv[((unsigned char)tmpc)].cupper;
 513     if (tmpc != candidate[i]) {
 514        ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
 515        if (ns == -1) return -1;
 516        candidate[i] = tmpc;
 517     }
 518     // check neighbor characters in keyboard string
 519     if (!ckey) continue;
 520     char * loc = strchr(ckey, tmpc);
 521     while (loc) {
 522        if ((loc > ckey) && (*(loc - 1) != '|')) {
 523           candidate[i] = *(loc - 1);
 524           ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
 525           if (ns == -1) return -1;
 526        }
 527        if ((*(loc + 1) != '|') && (*(loc + 1) != '\0')) {
 528           candidate[i] = *(loc + 1);
 529           ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
 530           if (ns == -1) return -1;
 531        }
 532        loc = strchr(loc + 1, tmpc);
 533     }
 534     candidate[i] = tmpc;
 535   }
 536   return ns;
 537 }
 538
 539 // error is wrong char in place of correct one (case and keyboard related version)
 540 int SuggestMgr::badcharkey_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 541 {
 542   w_char        tmpc;
 543   w_char        candidate_utf[MAXSWL];
 544   char          candidate[MAXSWUTF8L];
 545   memcpy(candidate_utf, word, wl * sizeof(w_char));
 546   // swap out each char one by one and try all the tryme
 547   // chars in its place to see if that makes a good word
 548   for (int i=0; i < wl; i++) {
 549     tmpc = candidate_utf[i];
 550     // check with uppercase letters
 551     mkallcap_utf(candidate_utf + i, 1, langnum);
 552     if (!w_char_eq(tmpc, candidate_utf[i])) {
 553        u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 554        ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 555        if (ns == -1) return -1;
 556        candidate_utf[i] = tmpc;
 557     }
 558     // check neighbor characters in keyboard string
 559     if (!ckey) continue;
 560     w_char * loc = ckey_utf;
 561     while ((loc < (ckey_utf + ckeyl)) && !w_char_eq(*loc, tmpc)) loc++;
 562     while (loc < (ckey_utf + ckeyl)) {
 563        if ((loc > ckey_utf) && !w_char_eq(*(loc - 1), W_VLINE)) {
 564           candidate_utf[i] = *(loc - 1);
 565           u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 566           ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 567           if (ns == -1) return -1;
 568        }
 569        if (((loc + 1) < (ckey_utf + ckeyl)) && !w_char_eq(*(loc + 1), W_VLINE)) {
 570           candidate_utf[i] = *(loc + 1);
 571           u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 572           ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 573           if (ns == -1) return -1;
 574        }
 575        do { loc++; } while ((loc < (ckey_utf + ckeyl)) && !w_char_eq(*loc, tmpc));
 576     }
 577     candidate_utf[i] = tmpc;
 578   }
 579   return ns;
 580 }
 581
 582 // error is wrong char in place of correct one
 583 int SuggestMgr::badchar(char ** wlst, const char * word, int ns, int cpdsuggest)
 584 {
 585   char  tmpc;
 586   char  candidate[MAXSWUTF8L];
 587   clock_t timelimit = clock();
 588   int timer = MINTIMER;
 589   int wl = strlen(word);
 590   strcpy(candidate, word);
 591   // swap out each char one by one and try all the tryme
 592   // chars in its place to see if that makes a good word
 593   for (int j=0; j < ctryl; j++) {
 594     for (int i=wl-1; i >= 0; i--) {
 595        tmpc = candidate[i];
 596        if (ctry[j] == tmpc) continue;
 597        candidate[i] = ctry[j];
 598        ns = testsug(wlst, candidate, wl, ns, cpdsuggest, &timer, &timelimit);
 599        if (ns == -1) return -1;
 600        if (!timer) return ns;
 601        candidate[i] = tmpc;
 602     }
 603   }
 604   return ns;
 605 }
 606
 607 // error is wrong char in place of correct one
 608 int SuggestMgr::badchar_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 609 {
 610   w_char        tmpc;
 611   w_char        candidate_utf[MAXSWL];
 612   char          candidate[MAXSWUTF8L];
 613   clock_t timelimit = clock();
 614   int timer = MINTIMER;
 615   memcpy(candidate_utf, word, wl * sizeof(w_char));
 616   // swap out each char one by one and try all the tryme
 617   // chars in its place to see if that makes a good word
 618   for (int j=0; j < ctryl; j++) {
 619     for (int i=wl-1; i >= 0; i--) {
 620        tmpc = candidate_utf[i];
 621        if (w_char_eq(tmpc, ctry_utf[j])) continue;
 622        candidate_utf[i] = ctry_utf[j];
 623        u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 624        ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, &timer, &timelimit);
 625        if (ns == -1) return -1;
 626        if (!timer) return ns;
 627        candidate_utf[i] = tmpc;
 628     }
 629   }
 630   return ns;
 631 }
 632
 633 // error is word has an extra letter it does not need
 634 int SuggestMgr::extrachar_utf(char** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 635 {
 636    char   candidate[MAXSWUTF8L];
 637    w_char candidate_utf[MAXSWL];
 638    w_char * p;
 639    w_char tmpc = W_VLINE; // not used value, only for VCC warning message
 640    if (wl < 2) return ns;
 641    // try omitting one char of word at a time
 642    memcpy(candidate_utf, word, wl * sizeof(w_char));
 643    for (p = candidate_utf + wl - 1;  p >= candidate_utf; p--) {
 644        w_char tmpc2 = *p;
 645        if (p < candidate_utf + wl - 1) *p = tmpc;
 646        u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl - 1);
 647        ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 648        if (ns == -1) return -1;
 649        tmpc = tmpc2;
 650    }
 651    return ns;
 652 }
 653
 654 // error is word has an extra letter it does not need
 655 int SuggestMgr::extrachar(char** wlst, const char * word, int ns, int cpdsuggest)
 656 {
 657    char    tmpc = '\0';
 658    char    candidate[MAXSWUTF8L];
 659    char *  p;
 660    int wl = strlen(word);
 661    if (wl < 2) return ns;
 662    // try omitting one char of word at a time
 663    strcpy (candidate, word);
 664    for (p = candidate + wl - 1; p >=candidate; p--) {
 665       char tmpc2 = *p;
 666       *p = tmpc;
 667       ns = testsug(wlst, candidate, wl-1, ns, cpdsuggest, NULL, NULL);
 668       if (ns == -1) return -1;
 669       tmpc = tmpc2;
 670    }
 671    return ns;
 672 }
 673
 674 // error is missing a letter it needs
 675 int SuggestMgr::forgotchar(char ** wlst, const char * word, int ns, int cpdsuggest)
 676 {
 677    char candidate[MAXSWUTF8L];
 678    char * p;
 679    clock_t timelimit = clock();
 680    int timer = MINTIMER;
 681    int wl = strlen(word);
 682    // try inserting a tryme character before every letter (and the null terminator)
 683    for (int i = 0;  i < ctryl;  i++) {
 684       strcpy(candidate, word);
 685       for (p = candidate + wl;  p >= candidate; p--)  {
 686          *(p+1) = *p;
 687          *p = ctry[i];
 688          ns = testsug(wlst, candidate, wl+1, ns, cpdsuggest, &timer, &timelimit);
 689          if (ns == -1) return -1;
 690          if (!timer) return ns;
 691       }
 692    }
 693    return ns;
 694 }
 695
 696 // error is missing a letter it needs
 697 int SuggestMgr::forgotchar_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 698 {
 699    w_char  candidate_utf[MAXSWL];
 700    char    candidate[MAXSWUTF8L];
 701    w_char * p;
 702    clock_t timelimit = clock();
 703    int timer = MINTIMER;
 704    // try inserting a tryme character at the end of the word and before every letter
 705    for (int i = 0;  i < ctryl;  i++) {
 706       memcpy (candidate_utf, word, wl * sizeof(w_char));
 707       for (p = candidate_utf + wl;  p >= candidate_utf; p--)  {
 708          *(p + 1) = *p;
 709          *p = ctry_utf[i];
 710          u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl + 1);
 711          ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, &timer, &timelimit);
 712          if (ns == -1) return -1;
 713          if (!timer) return ns;
 714       }
 715    }
 716    return ns;
 717 }
 718
 719
 720 /* error is should have been two words */
 721 int SuggestMgr::twowords(char ** wlst, const char * word, int ns, int cpdsuggest)
 722 {
 723     char candidate[MAXSWUTF8L];
 724     char * p;
 725     int c1, c2;
 726     int forbidden = 0;
 727     int cwrd;
 728
 729     int wl=strlen(word);
 730     if (wl < 3) return ns;
 731
 732     if (langnum == LANG_hu) forbidden = check_forbidden(word, wl);
 733
 734     strcpy(candidate + 1, word);
 735     // split the string into two pieces after every char
 736     // if both pieces are good words make them a suggestion
 737     for (p = candidate + 1;  p[1] != '\0';  p++) {
 738        p[-1] = *p;
 739        // go to end of the UTF-8 character
 740        while (utf8 && ((p[1] & 0xc0) == 0x80)) {
 741          *p = p[1];
 742          p++;
 743        }
 744        if (utf8 && p[1] == '\0') break; // last UTF-8 character
 745        *p = '\0';
 746        c1 = checkword(candidate,strlen(candidate), cpdsuggest, NULL, NULL);
 747        if (c1) {
 748          c2 = checkword((p+1),strlen(p+1), cpdsuggest, NULL, NULL);
 749          if (c2) {
 750             *p = ' ';
 751
 752             // spec. Hungarian code (need a better compound word support)
 753             if ((langnum == LANG_hu) && !forbidden &&
 754                 // if 3 repeating letter, use - instead of space
 755                 (((p[-1] == p[1]) && (((p>candidate+1) && (p[-1] == p[-2])) || (p[-1] == p[2]))) ||
 756                 // or multiple compounding, with more, than 6 syllables
 757                 ((c1 == 3) && (c2 >= 2)))) *p = '-';
 758
 759             cwrd = 1;
 760             for (int k=0; k < ns; k++)
 761                 if (strcmp(candidate,wlst[k]) == 0) cwrd = 0;
 762             if (ns < maxSug) {
 763                 if (cwrd) {
 764                     wlst[ns] = mystrdup(candidate);
 765                     if (wlst[ns] == NULL) return -1;
 766                     ns++;
 767                 }
 768             } else return ns;
 769             // add two word suggestion with dash, if TRY string contains
 770             // "a" or "-"
 771             // NOTE: cwrd doesn't modified for REP twoword sugg.
 772             if (ctry && (strchr(ctry, 'a') || strchr(ctry, '-')) &&
 773                 mystrlen(p + 1) > 1 &&
 774                 mystrlen(candidate) - mystrlen(p) > 1) {
 775                 *p = '-';
 776                 for (int k=0; k < ns; k++)
 777                     if (strcmp(candidate,wlst[k]) == 0) cwrd = 0;
 778                 if (ns < maxSug) {
 779                     if (cwrd) {
 780                         wlst[ns] = mystrdup(candidate);
 781                         if (wlst[ns] == NULL) return -1;
 782                         ns++;
 783                     }
 784                 } else return ns;
 785             }
 786          }
 787        }
 788     }
 789     return ns;
 790 }
 791
 792
 793 // error is adjacent letter were swapped
 794 int SuggestMgr::swapchar(char ** wlst, const char * word, int ns, int cpdsuggest)
 795 {
 796    char candidate[MAXSWUTF8L];
 797    char * p;
 798    char tmpc;
 799    int wl=strlen(word);
 800    // try swapping adjacent chars one by one
 801    strcpy(candidate, word);
 802    for (p = candidate;  p[1] != 0;  p++) {
 803       tmpc = *p;
 804       *p = p[1];
 805       p[1] = tmpc;
 806       ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
 807       if (ns == -1) return -1;
 808       p[1] = *p;
 809       *p = tmpc;
 810    }
 811    // try double swaps for short words
 812    // ahev -> have, owudl -> would
 813    if (wl == 4 || wl == 5) {
 814      candidate[0] = word[1];
 815      candidate[1] = word[0];
 816      candidate[2] = word[2];
 817      candidate[wl - 2] = word[wl - 1];
 818      candidate[wl - 1] = word[wl - 2];
 819      ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
 820      if (ns == -1) return -1;
 821      if (wl == 5) {
 822         candidate[0] = word[0];
 823         candidate[1] = word[2];
 824         candidate[2] = word[1];
 825         ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
 826         if (ns == -1) return -1;
 827      }
 828    }
 829    return ns;
 830 }
 831
 832 // error is adjacent letter were swapped
 833 int SuggestMgr::swapchar_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 834 {
 835    w_char candidate_utf[MAXSWL];
 836    char   candidate[MAXSWUTF8L];
 837    w_char * p;
 838    w_char tmpc;
 839    int len = 0;
 840    // try swapping adjacent chars one by one
 841    memcpy (candidate_utf, word, wl * sizeof(w_char));
 842    for (p = candidate_utf;  p < (candidate_utf + wl - 1);  p++) {
 843       tmpc = *p;
 844       *p = p[1];
 845       p[1] = tmpc;
 846       u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 847       if (len == 0) len = strlen(candidate);
 848       ns = testsug(wlst, candidate, len, ns, cpdsuggest, NULL, NULL);
 849       if (ns == -1) return -1;
 850       p[1] = *p;
 851       *p = tmpc;
 852    }
 853    // try double swaps for short words
 854    // ahev -> have, owudl -> would, suodn -> sound
 855    if (wl == 4 || wl == 5) {
 856      candidate_utf[0] = word[1];
 857      candidate_utf[1] = word[0];
 858      candidate_utf[2] = word[2];
 859      candidate_utf[wl - 2] = word[wl - 1];
 860      candidate_utf[wl - 1] = word[wl - 2];
 861      u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 862      ns = testsug(wlst, candidate, len, ns, cpdsuggest, NULL, NULL);
 863      if (ns == -1) return -1;
 864      if (wl == 5) {
 865         candidate_utf[0] = word[0];
 866         candidate_utf[1] = word[2];
 867         candidate_utf[2] = word[1];
 868         u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 869         ns = testsug(wlst, candidate, len, ns, cpdsuggest, NULL, NULL);
 870         if (ns == -1) return -1;
 871      }
 872    }
 873    return ns;
 874 }
 875
 876 // error is not adjacent letter were swapped
 877 int SuggestMgr::longswapchar(char ** wlst, const char * word, int ns, int cpdsuggest)
 878 {
 879    char candidate[MAXSWUTF8L];
 880    char * p;
 881    char * q;
 882    char tmpc;
 883    int wl=strlen(word);
 884    // try swapping not adjacent chars one by one
 885    strcpy(candidate, word);
 886    for (p = candidate;  *p != 0;  p++) {
 887     for (q = candidate;  *q != 0;  q++) {
 888      if (abs((int)(p-q)) > 1) {
 889       tmpc = *p;
 890       *p = *q;
 891       *q = tmpc;
 892       ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
 893       if (ns == -1) return -1;
 894       *q = *p;
 895       *p = tmpc;
 896      }
 897     }
 898    }
 899    return ns;
 900 }
 901
 902
 903 // error is adjacent letter were swapped
 904 int SuggestMgr::longswapchar_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 905 {
 906    w_char candidate_utf[MAXSWL];
 907    char   candidate[MAXSWUTF8L];
 908    w_char * p;
 909    w_char * q;
 910    w_char tmpc;
 911    // try swapping not adjacent chars
 912    memcpy (candidate_utf, word, wl * sizeof(w_char));
 913    for (p = candidate_utf;  p < (candidate_utf + wl);  p++) {
 914      for (q = candidate_utf;  q < (candidate_utf + wl);  q++) {
 915        if (abs((int)(p-q)) > 1) {
 916          tmpc = *p;
 917          *p = *q;
 918          *q = tmpc;
 919          u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 920          ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 921          if (ns == -1) return -1;
 922          *q = *p;
 923          *p = tmpc;
 924        }
 925      }
 926    }
 927    return ns;
 928 }
 929
 930 // error is a letter was moved
 931 int SuggestMgr::movechar(char ** wlst, const char * word, int ns, int cpdsuggest)
 932 {
 933    char candidate[MAXSWUTF8L];
 934    char * p;
 935    char * q;
 936    char tmpc;
 937
 938    int wl=strlen(word);
 939    // try moving a char
 940    strcpy(candidate, word);
 941    for (p = candidate;  *p != 0;  p++) {
 942      for (q = p + 1;  (*q != 0) && ((q - p) < 10);  q++) {
 943       tmpc = *(q-1);
 944       *(q-1) = *q;
 945       *q = tmpc;
 946       if ((q-p) < 2) continue; // omit swap char
 947       ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
 948       if (ns == -1) return -1;
 949     }
 950     strcpy(candidate, word);
 951    }
 952    for (p = candidate + wl - 1;  p > candidate;  p--) {
 953      for (q = p - 1;  (q >= candidate) && ((p - q) < 10);  q--) {
 954       tmpc = *(q+1);
 955       *(q+1) = *q;
 956       *q = tmpc;
 957       if ((p-q) < 2) continue; // omit swap char
 958       ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
 959       if (ns == -1) return -1;
 960     }
 961     strcpy(candidate, word);
 962    }
 963    return ns;
 964 }
 965
 966 // error is a letter was moved
 967 int SuggestMgr::movechar_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 968 {
 969    w_char candidate_utf[MAXSWL];
 970    char   candidate[MAXSWUTF8L];
 971    w_char * p;
 972    w_char * q;
 973    w_char tmpc;
 974    // try moving a char
 975    memcpy (candidate_utf, word, wl * sizeof(w_char));
 976    for (p = candidate_utf;  p < (candidate_utf + wl);  p++) {
 977      for (q = p + 1;  (q < (candidate_utf + wl)) && ((q - p) < 10);  q++) {
 978          tmpc = *(q-1);
 979          *(q-1) = *q;
 980          *q = tmpc;
 981          if ((q-p) < 2) continue; // omit swap char
 982          u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 983          ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 984          if (ns == -1) return -1;
 985      }
 986      memcpy (candidate_utf, word, wl * sizeof(w_char));
 987    }
 988    for (p = candidate_utf + wl - 1;  p > candidate_utf;  p--) {
 989      for (q = p - 1;  (q >= candidate_utf) && ((p - q) < 10);  q--) {
 990          tmpc = *(q+1);
 991          *(q+1) = *q;
 992          *q = tmpc;
 993          if ((p-q) < 2) continue; // omit swap char
 994          u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 995          ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 996          if (ns == -1) return -1;
 997      }
 998      memcpy (candidate_utf, word, wl * sizeof(w_char));
 999    }
1000    return ns;
1001 }
1002
1003 // generate a set of suggestions for very poorly spelled words
1004 int SuggestMgr::ngsuggest(char** wlst, char * w, int ns, HashMgr** pHMgr, int md)
1005 {
1006
1007   int i, j;
1008   int lval;
1009   int sc, scphon;
1010   int lp, lpphon;
1011   int nonbmp = 0;
1012
1013   // exhaustively search through all root words
1014   // keeping track of the MAX_ROOTS most similar root words
1015   struct hentry * roots[MAX_ROOTS];
1016   char * rootsphon[MAX_ROOTS];
1017   int scores[MAX_ROOTS];
1018   int scoresphon[MAX_ROOTS];
1019   for (i = 0; i < MAX_ROOTS; i++) {
1020     roots[i] = NULL;
1021     scores[i] = -100 * i;
1022     rootsphon[i] = NULL;
1023     scoresphon[i] = -100 * i;
1024   }
1025   lp = MAX_ROOTS - 1;
1026   lpphon = MAX_ROOTS - 1;
1027   scphon = -20000;
1028
1029   char w2[MAXWORDUTF8LEN];
1030   char f[MAXSWUTF8L];
1031   char * word = w;
1032
1033   // word reversing wrapper for complex prefixes
1034   if (complexprefixes) {
1035     strcpy(w2, w);
1036     if (utf8) reverseword_utf(w2); else reverseword(w2);
1037     word = w2;
1038   }
1039
1040   char mw[MAXSWUTF8L];
1041   w_char u8[MAXSWL];
1042   int nc = strlen(word);
1043   int n = (utf8) ? u8_u16(u8, MAXSWL, word) : nc;
1044
1045   // set character based ngram suggestion for words with non-BMP Unicode characters
1046   if (n == -1) {
1047     utf8 = 0;
1048     n = nc;
1049     nonbmp = 1;
1050   }
1051
1052   struct hentry* hp = NULL;
1053   int col = -1;
1054   phonetable * ph = (pAMgr) ? pAMgr->get_phonetable() : NULL;
1055   char target[MAXSWUTF8L];
1056   char candidate[MAXSWUTF8L];
1057   if (ph) {
1058     if (utf8) {
1059       w_char _w[MAXSWL];
1060       int _wl = u8_u16(_w, MAXSWL, word);
1061       mkallcap_utf(_w, _wl, langnum);
1062       u16_u8(candidate, MAXSWUTF8L, _w, _wl);
1063     } else {
1064       strcpy(candidate, word);
1065       mkallcap(candidate, csconv);
1066     }
1067     phonet(candidate, target, n, *ph);
1068   }
1069
1070   FLAG forbiddenword = pAMgr ? pAMgr->get_forbiddenword() : FLAG_NULL;
1071   FLAG nosuggest = pAMgr ? pAMgr->get_nosuggest() : FLAG_NULL;
1072   FLAG nongramsuggest = pAMgr ? pAMgr->get_nongramsuggest() : FLAG_NULL;
1073   FLAG onlyincompound = pAMgr ? pAMgr->get_onlyincompound() : FLAG_NULL;
1074
1075   for (i = 0; i < md; i++) {
1076   while (0 != (hp = (pHMgr[i])->walk_hashtable(col, hp))) {
1077     if ((hp->astr) && (pAMgr) &&
1078        (TESTAFF(hp->astr, forbiddenword, hp->alen) ||
1079           TESTAFF(hp->astr, ONLYUPCASEFLAG, hp->alen) ||
1080           TESTAFF(hp->astr, nosuggest, hp->alen) ||
1081           TESTAFF(hp->astr, nongramsuggest, hp->alen) ||
1082           TESTAFF(hp->astr, onlyincompound, hp->alen))) continue;
1083
1084     sc = ngram(3, word, HENTRY_WORD(hp), NGRAM_LONGER_WORSE + NGRAM_LOWERING) +
1085         leftcommonsubstring(word, HENTRY_WORD(hp));
1086
1087     // check special pronounciation
1088     if ((hp->var & H_OPT_PHON) && copy_field(f, HENTRY_DATA(hp), MORPH_PHON)) {
1089         int sc2 = ngram(3, word, f, NGRAM_LONGER_WORSE + NGRAM_LOWERING) +
1090                 + leftcommonsubstring(word, f);
1091         if (sc2 > sc) sc = sc2;
1092     }
1093
1094     scphon = -20000;
1095     if (ph && (sc > 2) && (abs(n - (int) hp->clen) <= 3)) {
1096       char target2[MAXSWUTF8L];
1097       if (utf8) {
1098         w_char _w[MAXSWL];
1099         int _wl = u8_u16(_w, MAXSWL, HENTRY_WORD(hp));
1100         mkallcap_utf(_w, _wl, langnum);
1101         u16_u8(candidate, MAXSWUTF8L, _w, _wl);
1102       } else {
1103         strcpy(candidate, HENTRY_WORD(hp));
1104         mkallcap(candidate, csconv);
1105       }
1106       phonet(candidate, target2, -1, *ph);
1107       scphon = 2 * ngram(3, target, target2, NGRAM_LONGER_WORSE);
1108     }
1109
1110     if (sc > scores[lp]) {
1111       scores[lp] = sc;
1112       roots[lp] = hp;
1113       lval = sc;
1114       for (j=0; j < MAX_ROOTS; j++)
1115         if (scores[j] < lval) {
1116           lp = j;
1117           lval = scores[j];
1118         }
1119     }
1120
1121
1122     if (scphon > scoresphon[lpphon]) {
1123       scoresphon[lpphon] = scphon;
1124       rootsphon[lpphon] = HENTRY_WORD(hp);
1125       lval = scphon;
1126       for (j=0; j < MAX_ROOTS; j++)
1127         if (scoresphon[j] < lval) {
1128           lpphon = j;
1129           lval = scoresphon[j];
1130         }
1131     }
1132   }}
1133
1134   // find minimum threshold for a passable suggestion
1135   // mangle original word three differnt ways
1136   // and score them to generate a minimum acceptable score
1137   int thresh = 0;
1138   for (int sp = 1; sp < 4; sp++) {
1139      if (utf8) {
1140        for (int k=sp; k < n; k+=4) *((unsigned short *) u8 + k) = '*';
1141        u16_u8(mw, MAXSWUTF8L, u8, n);
1142        thresh = thresh + ngram(n, word, mw, NGRAM_ANY_MISMATCH + NGRAM_LOWERING);
1143      } else {
1144        strcpy(mw, word);
1145        for (int k=sp; k < n; k+=4) *(mw + k) = '*';
1146        thresh = thresh + ngram(n, word, mw, NGRAM_ANY_MISMATCH + NGRAM_LOWERING);
1147      }
1148   }
1149   thresh = thresh / 3;
1150   thresh--;
1151
1152   // now expand affixes on each of these root words and
1153   // and use length adjusted ngram scores to select
1154   // possible suggestions
1155   char * guess[MAX_GUESS];
1156   char * guessorig[MAX_GUESS];
1157   int gscore[MAX_GUESS];
1158   for(i=0;i<MAX_GUESS;i++) {
1159      guess[i] = NULL;
1160      guessorig[i] = NULL;
1161      gscore[i] = -100 * i;
1162   }
1163
1164   lp = MAX_GUESS - 1;
1165
1166   struct guessword * glst;
1167   glst = (struct guessword *) calloc(MAX_WORDS,sizeof(struct guessword));
1168   if (! glst) {
1169     if (nonbmp) utf8 = 1;
1170     return ns;
1171   }
1172
1173   for (i = 0; i < MAX_ROOTS; i++) {
1174       if (roots[i]) {
1175         struct hentry * rp = roots[i];
1176         int nw = pAMgr->expand_rootword(glst, MAX_WORDS, HENTRY_WORD(rp), rp->blen,
1177                     rp->astr, rp->alen, word, nc,
1178                     ((rp->var & H_OPT_PHON) ? copy_field(f, HENTRY_DATA(rp), MORPH_PHON) : NULL));
1179
1180         for (int k = 0; k < nw ; k++) {
1181            sc = ngram(n, word, glst[k].word, NGRAM_ANY_MISMATCH + NGRAM_LOWERING) +
1182                leftcommonsubstring(word, glst[k].word);
1183
1184            if (sc > thresh) {
1185               if (sc > gscore[lp]) {
1186                  if (guess[lp]) {
1187                     free (guess[lp]);
1188                     if (guessorig[lp]) {
1189                         free(guessorig[lp]);
1190                         guessorig[lp] = NULL;
1191                     }
1192                  }
1193                  gscore[lp] = sc;
1194                  guess[lp] = glst[k].word;
1195                  guessorig[lp] = glst[k].orig;
1196                  lval = sc;
1197                  for (j=0; j < MAX_GUESS; j++)
1198                     if (gscore[j] < lval) {
1199                        lp = j;
1200                        lval = gscore[j];
1201                     }
1202               } else {
1203                 free(glst[k].word);
1204                 if (glst[k].orig) free(glst[k].orig);
1205               }
1206            } else {
1207                 free(glst[k].word);
1208                 if (glst[k].orig) free(glst[k].orig);
1209            }
1210         }
1211       }
1212   }
1213   free(glst);
1214
1215   // now we are done generating guesses
1216   // sort in order of decreasing score
1217
1218
1219   bubblesort(&guess[0], &guessorig[0], &gscore[0], MAX_GUESS);
1220   if (ph) bubblesort(&rootsphon[0], NULL, &scoresphon[0], MAX_ROOTS);
1221
1222   // weight suggestions with a similarity index, based on
1223   // the longest common subsequent algorithm and resort
1224
1225   int is_swap = 0;
1226   int re;
1227   float fact = 1.0;
1228   if (pAMgr) {
1229         int maxd = pAMgr->get_maxdiff();
1230         if (maxd >= 0) fact = (10.0 - maxd)/5.0;
1231   }
1232
1233   for (i=0; i < MAX_GUESS; i++) {
1234       if (guess[i]) {
1235         // lowering guess[i]
1236         char gl[MAXSWUTF8L];
1237         int len;
1238         if (utf8) {
1239           w_char _w[MAXSWL];
1240           len = u8_u16(_w, MAXSWL, guess[i]);
1241           mkallsmall_utf(_w, len, langnum);
1242           u16_u8(gl, MAXSWUTF8L, _w, len);
1243         } else {
1244           strcpy(gl, guess[i]);
1245           mkallsmall(gl, csconv);
1246           len = strlen(guess[i]);
1247         }
1248
1249         int _lcs = lcslen(word, gl);
1250
1251         // same characters with different casing
1252         if ((n == len) && (n == _lcs)) {
1253             gscore[i] += 2000;
1254             break;
1255         }
1256         // using 2-gram instead of 3, and other weightening
1257         gscore[i] =
1258           // length of longest common subsequent minus length difference
1259           2 * _lcs - abs((int) (n - len)) +
1260           // weight length of the left common substring
1261           leftcommonsubstring(word, gl) +
1262           // weight equal character positions
1263           (commoncharacterpositions(word, gl, &is_swap) ? 1: 0) +
1264           // swap character (not neighboring)
1265           ((is_swap) ? 10 : 0) +
1266           // ngram
1267           ngram(4, word, gl, NGRAM_ANY_MISMATCH + NGRAM_LOWERING) +
1268           // weighted ngrams
1269           (re = ngram(2, word, gl, NGRAM_ANY_MISMATCH + NGRAM_LOWERING + NGRAM_WEIGHTED)) +
1270           (re += ngram(2, gl, word, NGRAM_ANY_MISMATCH + NGRAM_LOWERING + NGRAM_WEIGHTED)) +
1271           // different limit for dictionaries with PHONE rules
1272           (ph ? (re < len * fact ? -1000 : 0) : (re < (n + len)*fact? -1000 : 0));
1273       }
1274   }
1275
1276   bubblesort(&guess[0], &guessorig[0], &gscore[0], MAX_GUESS);
1277
1278 // phonetic version
1279   if (ph) for (i=0; i < MAX_ROOTS; i++) {
1280       if (rootsphon[i]) {
1281         // lowering rootphon[i]
1282         char gl[MAXSWUTF8L];
1283         int len;
1284         if (utf8) {
1285           w_char _w[MAXSWL];
1286           len = u8_u16(_w, MAXSWL, rootsphon[i]);
1287           mkallsmall_utf(_w, len, langnum);
1288           u16_u8(gl, MAXSWUTF8L, _w, len);
1289         } else {
1290           strcpy(gl, rootsphon[i]);
1291           mkallsmall(gl, csconv);
1292           len = strlen(rootsphon[i]);
1293         }
1294
1295         // heuristic weigthing of ngram scores
1296         scoresphon[i] += 2 * lcslen(word, gl) - abs((int) (n - len)) +
1297           // weight length of the left common substring
1298           leftcommonsubstring(word, gl);
1299       }
1300   }
1301
1302   if (ph) bubblesort(&rootsphon[0], NULL, &scoresphon[0], MAX_ROOTS);
1303
1304   // copy over
1305   int oldns = ns;
1306
1307   int same = 0;
1308   for (i=0; i < MAX_GUESS; i++) {
1309     if (guess[i]) {
1310       if ((ns < oldns + maxngramsugs) && (ns < maxSug) && (!same || (gscore[i] > 1000))) {
1311         int unique = 1;
1312         // leave only excellent suggestions, if exists
1313         if (gscore[i] > 1000) same = 1; else if (gscore[i] < -100) {
1314             same = 1;
1315             // keep the best ngram suggestions, unless in ONLYMAXDIFF mode
1316             if (ns > oldns || (pAMgr && pAMgr->get_onlymaxdiff())) {
1317                 free(guess[i]);
1318                 if (guessorig[i]) free(guessorig[i]);
1319                 continue;
1320             }
1321         }
1322         for (j = 0; j < ns; j++) {
1323           // don't suggest previous suggestions or a previous suggestion with prefixes or affixes
1324           if ((!guessorig[i] && strstr(guess[i], wlst[j])) ||
1325              (guessorig[i] && strstr(guessorig[i], wlst[j])) ||
1326             // check forbidden words
1327             !checkword(guess[i], strlen(guess[i]), 0, NULL, NULL)) unique = 0;
1328         }
1329         if (unique) {
1330             wlst[ns++] = guess[i];
1331             if (guessorig[i]) {
1332                 free(guess[i]);
1333                 wlst[ns-1] = guessorig[i];
1334             }
1335         } else {
1336             free(guess[i]);
1337             if (guessorig[i]) free(guessorig[i]);
1338         }
1339       } else {
1340         free(guess[i]);
1341         if (guessorig[i]) free(guessorig[i]);
1342       }
1343     }
1344   }
1345
1346   oldns = ns;
1347   if (ph) for (i=0; i < MAX_ROOTS; i++) {
1348     if (rootsphon[i]) {
1349       if ((ns < oldns + MAXPHONSUGS) && (ns < maxSug)) {
1350         int unique = 1;
1351         for (j = 0; j < ns; j++) {
1352           // don't suggest previous suggestions or a previous suggestion with prefixes or affixes
1353           if (strstr(rootsphon[i], wlst[j]) ||
1354             // check forbidden words
1355             !checkword(rootsphon[i], strlen(rootsphon[i]), 0, NULL, NULL)) unique = 0;
1356         }
1357         if (unique) {
1358             wlst[ns++] = mystrdup(rootsphon[i]);
1359             if (!wlst[ns - 1]) return ns - 1;
1360         }
1361       }
1362     }
1363   }
1364
1365   if (nonbmp) utf8 = 1;
1366 //  if (specpron) free(specpron);
1367   return ns;
1368 }
1369
1370
1371 // see if a candidate suggestion is spelled correctly
1372 // needs to check both root words and words with affixes
1373
1374 // obsolote MySpell-HU modifications:
1375 // return value 2 and 3 marks compounding with hyphen (-)
1376 // `3' marks roots without suffix
1377 int SuggestMgr::checkword(const char * word, int len, int cpdsuggest, int * timer, clock_t * timelimit)
1378 {
1379   struct hentry * rv=NULL;
1380   struct hentry * rv2=NULL;
1381   int nosuffix = 0;
1382
1383   // check time limit
1384   if (timer) {
1385     (*timer)--;
1386     if (!(*timer) && timelimit) {
1387       if ((clock() - *timelimit) > TIMELIMIT) return 0;
1388       *timer = MAXPLUSTIMER;
1389     }
1390   }
1391
1392   if (pAMgr) {
1393     if (cpdsuggest==1) {
1394       if (pAMgr->get_compound()) {
1395         rv = pAMgr->compound_check(word, len, 0, 0, 100, 0, NULL, 0, 1, 0); //EXT
1396         if (rv && (!(rv2 = pAMgr->lookup(word)) || !rv2->astr ||
1397             !(TESTAFF(rv2->astr,pAMgr->get_forbiddenword(),rv2->alen) ||
1398             TESTAFF(rv2->astr,pAMgr->get_nosuggest(),rv2->alen)))) return 3; // XXX obsolote categorisation + only ICONV needs affix flag check?
1399         }
1400         return 0;
1401     }
1402
1403     rv = pAMgr->lookup(word);
1404
1405     if (rv) {
1406         if ((rv->astr) && (TESTAFF(rv->astr,pAMgr->get_forbiddenword(),rv->alen)
1407                || TESTAFF(rv->astr,pAMgr->get_nosuggest(),rv->alen))) return 0;
1408         while (rv) {
1409             if (rv->astr && (TESTAFF(rv->astr,pAMgr->get_needaffix(),rv->alen) ||
1410                 TESTAFF(rv->astr, ONLYUPCASEFLAG, rv->alen) ||
1411             TESTAFF(rv->astr,pAMgr->get_onlyincompound(),rv->alen))) {
1412                 rv = rv->next_homonym;
1413             } else break;
1414         }
1415     } else rv = pAMgr->prefix_check(word, len, 0); // only prefix, and prefix + suffix XXX
1416
1417     if (rv) {
1418         nosuffix=1;
1419     } else {
1420         rv = pAMgr->suffix_check(word, len, 0, NULL, NULL, 0, NULL); // only suffix
1421     }
1422
1423     if (!rv && pAMgr->have_contclass()) {
1424         rv = pAMgr->suffix_check_twosfx(word, len, 0, NULL, FLAG_NULL);
1425         if (!rv) rv = pAMgr->prefix_check_twosfx(word, len, 1, FLAG_NULL);
1426     }
1427
1428     // check forbidden words
1429     if ((rv) && (rv->astr) && (TESTAFF(rv->astr,pAMgr->get_forbiddenword(),rv->alen) ||
1430       TESTAFF(rv->astr, ONLYUPCASEFLAG, rv->alen) ||
1431       TESTAFF(rv->astr,pAMgr->get_nosuggest(),rv->alen) ||
1432       TESTAFF(rv->astr,pAMgr->get_onlyincompound(),rv->alen))) return 0;
1433
1434     if (rv) { // XXX obsolote
1435       if ((pAMgr->get_compoundflag()) &&
1436           TESTAFF(rv->astr, pAMgr->get_compoundflag(), rv->alen)) return 2 + nosuffix;
1437       return 1;
1438     }
1439   }
1440   return 0;
1441 }
1442
1443 int SuggestMgr::check_forbidden(const char * word, int len)
1444 {
1445   struct hentry * rv = NULL;
1446
1447   if (pAMgr) {
1448     rv = pAMgr->lookup(word);
1449     if (rv && rv->astr && (TESTAFF(rv->astr,pAMgr->get_needaffix(),rv->alen) ||
1450         TESTAFF(rv->astr,pAMgr->get_onlyincompound(),rv->alen))) rv = NULL;
1451     if (!(pAMgr->prefix_check(word,len,1)))
1452         rv = pAMgr->suffix_check(word,len, 0, NULL, NULL, 0, NULL); // prefix+suffix, suffix
1453     // check forbidden words
1454     if ((rv) && (rv->astr) && TESTAFF(rv->astr,pAMgr->get_forbiddenword(),rv->alen)) return 1;
1455    }
1456     return 0;
1457 }
1458
1459 #ifdef HUNSPELL_EXPERIMENTAL
1460 // suggest possible stems
1461 int SuggestMgr::suggest_pos_stems(char*** slst, const char * w, int nsug)
1462 {
1463     char ** wlst;
1464
1465     struct hentry * rv = NULL;
1466
1467   char w2[MAXSWUTF8L];
1468   const char * word = w;
1469
1470   // word reversing wrapper for complex prefixes
1471   if (complexprefixes) {
1472     strcpy(w2, w);
1473     if (utf8) reverseword_utf(w2); else reverseword(w2);
1474     word = w2;
1475   }
1476
1477     int wl = strlen(word);
1478
1479
1480     if (*slst) {
1481         wlst = *slst;
1482     } else {
1483         wlst = (char **) calloc(maxSug, sizeof(char *));
1484         if (wlst == NULL) return -1;
1485     }
1486
1487     rv = pAMgr->suffix_check(word, wl, 0, NULL, wlst, maxSug, &nsug);
1488
1489     // delete dash from end of word
1490     if (nsug > 0) {
1491         for (int j=0; j < nsug; j++) {
1492             if (wlst[j][strlen(wlst[j]) - 1] == '-') wlst[j][strlen(wlst[j]) - 1] = '\0';
1493         }
1494     }
1495
1496     *slst = wlst;
1497     return nsug;
1498 }
1499 #endif // END OF HUNSPELL_EXPERIMENTAL CODE
1500
1501
1502 char * SuggestMgr::suggest_morph(const char * w)
1503 {
1504     char result[MAXLNLEN];
1505     char * r = (char *) result;
1506     char * st;
1507
1508     struct hentry * rv = NULL;
1509
1510     *result = '\0';
1511
1512     if (! pAMgr) return NULL;
1513
1514   char w2[MAXSWUTF8L];
1515   const char * word = w;
1516
1517   // word reversing wrapper for complex prefixes
1518   if (complexprefixes) {
1519     strcpy(w2, w);
1520     if (utf8) reverseword_utf(w2); else reverseword(w2);
1521     word = w2;
1522   }
1523
1524     rv = pAMgr->lookup(word);
1525
1526     while (rv) {
1527         if ((!rv->astr) || !(TESTAFF(rv->astr, pAMgr->get_forbiddenword(), rv->alen) ||
1528             TESTAFF(rv->astr, pAMgr->get_needaffix(), rv->alen) ||
1529             TESTAFF(rv->astr,pAMgr->get_onlyincompound(),rv->alen))) {
1530                 if (!HENTRY_FIND(rv, MORPH_STEM)) {
1531                     mystrcat(result, " ", MAXLNLEN);
1532                     mystrcat(result, MORPH_STEM, MAXLNLEN);
1533                     mystrcat(result, word, MAXLNLEN);
1534                 }
1535                 if (HENTRY_DATA(rv)) {
1536                     mystrcat(result, " ", MAXLNLEN);
1537                     mystrcat(result, HENTRY_DATA2(rv), MAXLNLEN);
1538                 }
1539                 mystrcat(result, "\n", MAXLNLEN);
1540         }
1541         rv = rv->next_homonym;
1542     }
1543
1544     st = pAMgr->affix_check_morph(word,strlen(word));
1545     if (st) {
1546         mystrcat(result, st, MAXLNLEN);
1547         free(st);
1548     }
1549
1550     if (pAMgr->get_compound() && (*result == '\0'))
1551         pAMgr->compound_check_morph(word, strlen(word),
1552                      0, 0, 100, 0,NULL, 0, &r, NULL);
1553
1554     return (*result) ? mystrdup(line_uniq(result, MSEP_REC)) : NULL;
1555 }
1556
1557 #ifdef HUNSPELL_EXPERIMENTAL
1558 char * SuggestMgr::suggest_morph_for_spelling_error(const char * word)
1559 {
1560     char * p = NULL;
1561     char ** wlst = (char **) calloc(maxSug, sizeof(char *));
1562     if (!**wlst) return NULL;
1563     // we will use only the first suggestion
1564     for (int i = 0; i < maxSug - 1; i++) wlst[i] = "";
1565     int ns = suggest(&wlst, word, maxSug - 1, NULL);
1566     if (ns == maxSug) {
1567         p = suggest_morph(wlst[maxSug - 1]);
1568         free(wlst[maxSug - 1]);
1569     }
1570     if (wlst) free(wlst);
1571     return p;
1572 }
1573 #endif // END OF HUNSPELL_EXPERIMENTAL CODE
1574
1575 /* affixation */
1576 char * SuggestMgr::suggest_hentry_gen(hentry * rv, char * pattern)
1577 {
1578     char result[MAXLNLEN];
1579     *result = '\0';
1580     int sfxcount = get_sfxcount(pattern);
1581
1582     if (get_sfxcount(HENTRY_DATA(rv)) > sfxcount) return NULL;
1583
1584     if (HENTRY_DATA(rv)) {
1585         char * aff = pAMgr->morphgen(HENTRY_WORD(rv), rv->blen, rv->astr, rv->alen,
1586             HENTRY_DATA(rv), pattern, 0);
1587         if (aff) {
1588             mystrcat(result, aff, MAXLNLEN);
1589             mystrcat(result, "\n", MAXLNLEN);
1590             free(aff);
1591         }
1592     }
1593
1594     // check all allomorphs
1595     char allomorph[MAXLNLEN];
1596     char * p = NULL;
1597     if (HENTRY_DATA(rv)) p = (char *) strstr(HENTRY_DATA2(rv), MORPH_ALLOMORPH);
1598     while (p) {
1599         struct hentry * rv2 = NULL;
1600         p += MORPH_TAG_LEN;
1601         int plen = fieldlen(p);
1602         strncpy(allomorph, p, plen);
1603         allomorph[plen] = '\0';
1604         rv2 = pAMgr->lookup(allomorph);
1605         while (rv2) {
1606 //            if (HENTRY_DATA(rv2) && get_sfxcount(HENTRY_DATA(rv2)) <= sfxcount) {
1607             if (HENTRY_DATA(rv2)) {
1608                 char * st = (char *) strstr(HENTRY_DATA2(rv2), MORPH_STEM);
1609                 if (st && (strncmp(st + MORPH_TAG_LEN,
1610                    HENTRY_WORD(rv), fieldlen(st + MORPH_TAG_LEN)) == 0)) {
1611                     char * aff = pAMgr->morphgen(HENTRY_WORD(rv2), rv2->blen, rv2->astr, rv2->alen,
1612                         HENTRY_DATA(rv2), pattern, 0);
1613                     if (aff) {
1614                         mystrcat(result, aff, MAXLNLEN);
1615                         mystrcat(result, "\n", MAXLNLEN);
1616                         free(aff);
1617                     }
1618                 }
1619             }
1620             rv2 = rv2->next_homonym;
1621         }
1622         p = strstr(p + plen, MORPH_ALLOMORPH);
1623     }
1624
1625     return (*result) ? mystrdup(result) : NULL;
1626 }
1627
1628 char * SuggestMgr::suggest_gen(char ** desc, int n, char * pattern) {
1629   char result[MAXLNLEN];
1630   char result2[MAXLNLEN];
1631   char newpattern[MAXLNLEN];
1632   *newpattern = '\0';
1633   if (n == 0) return 0;
1634   *result2 = '\0';
1635   struct hentry * rv = NULL;
1636   if (!pAMgr) return NULL;
1637
1638 // search affixed forms with and without derivational suffixes
1639   while(1) {
1640
1641   for (int k = 0; k < n; k++) {
1642     *result = '\0';
1643     // add compound word parts (except the last one)
1644     char * s = (char *) desc[k];
1645     char * part = strstr(s, MORPH_PART);
1646     if (part) {
1647         char * nextpart = strstr(part + 1, MORPH_PART);
1648         while (nextpart) {
1649             copy_field(result + strlen(result), part, MORPH_PART);
1650             part = nextpart;
1651             nextpart = strstr(part + 1, MORPH_PART);
1652         }
1653         s = part;
1654     }
1655
1656     char **pl;
1657     char tok[MAXLNLEN];
1658     strcpy(tok, s);
1659     char * alt = strstr(tok, " | ");
1660     while (alt) {
1661         alt[1] = MSEP_ALT;
1662         alt = strstr(alt, " | ");
1663     }
1664     int pln = line_tok(tok, &pl, MSEP_ALT);
1665     for (int i = 0; i < pln; i++) {
1666             // remove inflectional and terminal suffixes
1667             char * is = strstr(pl[i], MORPH_INFL_SFX);
1668             if (is) *is = '\0';
1669             char * ts = strstr(pl[i], MORPH_TERM_SFX);
1670             while (ts) {
1671                 *ts = '_';
1672                 ts = strstr(pl[i], MORPH_TERM_SFX);
1673             }
1674             char * st = strstr(s, MORPH_STEM);
1675             if (st) {
1676                 copy_field(tok, st, MORPH_STEM);
1677                 rv = pAMgr->lookup(tok);
1678                 while (rv) {
1679                     char newpat[MAXLNLEN];
1680                     strcpy(newpat, pl[i]);
1681                     strcat(newpat, pattern);
1682                     char * sg = suggest_hentry_gen(rv, newpat);
1683                     if (!sg) sg = suggest_hentry_gen(rv, pattern);
1684                     if (sg) {
1685                         char ** gen;
1686                         int genl = line_tok(sg, &gen, MSEP_REC);
1687                         free(sg);
1688                         sg = NULL;
1689                         for (int j = 0; j < genl; j++) {
1690                             if (strstr(pl[i], MORPH_SURF_PFX)) {
1691                                 int r2l = strlen(result2);
1692                                 result2[r2l] = MSEP_REC;
1693                                 strcpy(result2 + r2l + 1, result);
1694                                 copy_field(result2 + strlen(result2), pl[i], MORPH_SURF_PFX);
1695                                 mystrcat(result2, gen[j], MAXLNLEN);
1696                             } else {
1697                                 sprintf(result2 + strlen(result2), "%c%s%s",
1698                                     MSEP_REC, result, gen[j]);
1699                             }
1700                         }
1701                         freelist(&gen, genl);
1702                     }
1703                     rv = rv->next_homonym;
1704                 }
1705             }
1706     }
1707     freelist(&pl, pln);
1708   }
1709
1710   if (*result2 || !strstr(pattern, MORPH_DERI_SFX)) break;
1711   strcpy(newpattern, pattern);
1712   pattern = newpattern;
1713   char * ds = strstr(pattern, MORPH_DERI_SFX);
1714   while (ds) {
1715     strncpy(ds, MORPH_TERM_SFX, MORPH_TAG_LEN);
1716     ds = strstr(pattern, MORPH_DERI_SFX);
1717   }
1718  }
1719   return (*result2 ? mystrdup(result2) : NULL);
1720 }
1721
1722
1723 // generate an n-gram score comparing s1 and s2
1724 int SuggestMgr::ngram(int n, char * s1, const char * s2, int opt)
1725 {
1726   int nscore = 0;
1727   int ns;
1728   int l1;
1729   int l2;
1730   int test = 0;
1731
1732   if (utf8) {
1733     w_char su1[MAXSWL];
1734     w_char su2[MAXSWL];
1735     l1 = u8_u16(su1, MAXSWL, s1);
1736     l2 = u8_u16(su2, MAXSWL, s2);
1737     if ((l2 <= 0) || (l1 == -1)) return 0;
1738     // lowering dictionary word
1739     if (opt & NGRAM_LOWERING) mkallsmall_utf(su2, l2, langnum);
1740     for (int j = 1; j <= n; j++) {
1741       ns = 0;
1742       for (int i = 0; i <= (l1-j); i++) {
1743         int k = 0;
1744         for (int l = 0; l <= (l2-j); l++) {
1745             for (k = 0; k < j; k++) {
1746               w_char * c1 = su1 + i + k;
1747               w_char * c2 = su2 + l + k;
1748               if ((c1->l != c2->l) || (c1->h != c2->h)) break;
1749             }
1750             if (k == j) {
1751                 ns++;
1752                 break;
1753             }
1754         }
1755         if (k != j && opt & NGRAM_WEIGHTED) {
1756           ns--;
1757           test++;
1758           if (i == 0 || i == l1-j) ns--; // side weight
1759         }
1760       }
1761       nscore = nscore + ns;
1762       if (ns < 2 && !(opt & NGRAM_WEIGHTED)) break;
1763     }
1764   } else {
1765     l2 = strlen(s2);
1766     if (l2 == 0) return 0;
1767     l1 = strlen(s1);
1768     char *t = mystrdup(s2);
1769     if (opt & NGRAM_LOWERING) mkallsmall(t, csconv);
1770     for (int j = 1; j <= n; j++) {
1771       ns = 0;
1772       for (int i = 0; i <= (l1-j); i++) {
1773         char c = *(s1 + i + j);
1774         *(s1 + i + j) = '\0';
1775         if (strstr(t,(s1+i))) {
1776           ns++;
1777         } else if (opt & NGRAM_WEIGHTED) {
1778           ns--;
1779 test++;
1780           if (i == 0 || i == l1-j) ns--; // side weight
1781         }
1782         *(s1 + i + j ) = c;
1783       }
1784       nscore = nscore + ns;
1785       if (ns < 2 && !(opt & NGRAM_WEIGHTED)) break;
1786     }
1787     free(t);
1788   }
1789
1790   ns = 0;
1791   if (opt & NGRAM_LONGER_WORSE) ns = (l2-l1)-2;
1792   if (opt & NGRAM_ANY_MISMATCH) ns = abs(l2-l1)-2;
1793   ns = (nscore - ((ns > 0) ? ns : 0));
1794   return ns;
1795 }
1796
1797 // length of the left common substring of s1 and (decapitalised) s2
1798 int SuggestMgr::leftcommonsubstring(char * s1, const char * s2) {
1799   if (utf8) {
1800     w_char su1[MAXSWL];
1801     w_char su2[MAXSWL];
1802     su1[0].l = su2[0].l = su1[0].h = su2[0].h = 0;
1803     // decapitalize dictionary word
1804     if (complexprefixes) {
1805       int l1 = u8_u16(su1, MAXSWL, s1);
1806       int l2 = u8_u16(su2, MAXSWL, s2);
1807       if (*((short *)su1+l1-1) == *((short *)su2+l2-1)) return 1;
1808     } else {
1809       int i;
1810       u8_u16(su1, 1, s1);
1811       u8_u16(su2, 1, s2);
1812       unsigned short idx = (su2->h << 8) + su2->l;
1813       unsigned short otheridx = (su1->h << 8) + su1->l;
1814       if (otheridx != idx &&
1815          (otheridx != unicodetolower(idx, langnum))) return 0;
1816       int l1 = u8_u16(su1, MAXSWL, s1);
1817       int l2 = u8_u16(su2, MAXSWL, s2);
1818       for(i = 1; (i < l1) && (i < l2) &&
1819          (su1[i].l == su2[i].l) && (su1[i].h == su2[i].h); i++);
1820       return i;
1821     }
1822   } else {
1823     if (complexprefixes) {
1824       int l1 = strlen(s1);
1825       int l2 = strlen(s2);
1826       if (*(s2+l1-1) == *(s2+l2-1)) return 1;
1827     } else {
1828       char * olds = s1;
1829       // decapitalise dictionary word
1830       if ((*s1 != *s2) && (*s1 != csconv[((unsigned char)*s2)].clower)) return 0;
1831       do {
1832         s1++; s2++;
1833       } while ((*s1 == *s2) && (*s1 != '\0'));
1834       return (int)(s1 - olds);
1835     }
1836   }
1837   return 0;
1838 }
1839
1840 int SuggestMgr::commoncharacterpositions(char * s1, const char * s2, int * is_swap) {
1841   int num = 0;
1842   int diff = 0;
1843   int diffpos[2];
1844   *is_swap = 0;
1845   if (utf8) {
1846     w_char su1[MAXSWL];
1847     w_char su2[MAXSWL];
1848     int l1 = u8_u16(su1, MAXSWL, s1);
1849     int l2 = u8_u16(su2, MAXSWL, s2);
1850     // decapitalize dictionary word
1851     if (complexprefixes) {
1852       mkallsmall_utf(su2+l2-1, 1, langnum);
1853     } else {
1854       mkallsmall_utf(su2, 1, langnum);
1855     }
1856     for (int i = 0; (i < l1) && (i < l2); i++) {
1857       if (((short *) su1)[i] == ((short *) su2)[i]) {
1858         num++;
1859       } else {
1860         if (diff < 2) diffpos[diff] = i;
1861         diff++;
1862       }
1863     }
1864     if ((diff == 2) && (l1 == l2) &&
1865         (((short *) su1)[diffpos[0]] == ((short *) su2)[diffpos[1]]) &&
1866         (((short *) su1)[diffpos[1]] == ((short *) su2)[diffpos[0]])) *is_swap = 1;
1867   } else {
1868     int i;
1869     char t[MAXSWUTF8L];
1870     strcpy(t, s2);
1871     // decapitalize dictionary word
1872     if (complexprefixes) {
1873       int l2 = strlen(t);
1874       *(t+l2-1) = csconv[((unsigned char)*(t+l2-1))].clower;
1875     } else {
1876       mkallsmall(t, csconv);
1877     }
1878     for (i = 0; (*(s1+i) != 0) && (*(t+i) != 0); i++) {
1879       if (*(s1+i) == *(t+i)) {
1880         num++;
1881       } else {
1882         if (diff < 2) diffpos[diff] = i;
1883         diff++;
1884       }
1885     }
1886     if ((diff == 2) && (*(s1+i) == 0) && (*(t+i) == 0) &&
1887       (*(s1+diffpos[0]) == *(t+diffpos[1])) &&
1888       (*(s1+diffpos[1]) == *(t+diffpos[0]))) *is_swap = 1;
1889   }
1890   return num;
1891 }
1892
1893 int SuggestMgr::mystrlen(const char * word) {
1894   if (utf8) {
1895     w_char w[MAXSWL];
1896     return u8_u16(w, MAXSWL, word);
1897   } else return strlen(word);
1898 }
1899
1900 // sort in decreasing order of score
1901 void SuggestMgr::bubblesort(char** rword, char** rword2, int* rsc, int n )
1902 {
1903       int m = 1;
1904       while (m < n) {
1905           int j = m;
1906           while (j > 0) {
1907             if (rsc[j-1] < rsc[j]) {
1908                 int sctmp = rsc[j-1];
1909                 char * wdtmp = rword[j-1];
1910                 rsc[j-1] = rsc[j];
1911                 rword[j-1] = rword[j];
1912                 rsc[j] = sctmp;
1913                 rword[j] = wdtmp;
1914                 if (rword2) {
1915                     wdtmp = rword2[j-1];
1916                     rword2[j-1] = rword2[j];
1917                     rword2[j] = wdtmp;
1918                 }
1919                 j--;
1920             } else break;
1921           }
1922           m++;
1923       }
1924       return;
1925 }
1926
1927 // longest common subsequence
1928 void SuggestMgr::lcs(const char * s, const char * s2, int * l1, int * l2, char ** result) {
1929   int n, m;
1930   w_char su[MAXSWL];
1931   w_char su2[MAXSWL];
1932   char * b;
1933   char * c;
1934   int i;
1935   int j;
1936   if (utf8) {
1937     m = u8_u16(su, MAXSWL, s);
1938     n = u8_u16(su2, MAXSWL, s2);
1939   } else {
1940     m = strlen(s);
1941     n = strlen(s2);
1942   }
1943   c = (char *) malloc((m + 1) * (n + 1));
1944   b = (char *) malloc((m + 1) * (n + 1));
1945   if (!c || !b) {
1946     if (c) free(c);
1947     if (b) free(b);
1948     *result = NULL;
1949     return;
1950   }
1951   for (i = 1; i <= m; i++) c[i*(n+1)] = 0;
1952   for (j = 0; j <= n; j++) c[j] = 0;
1953   for (i = 1; i <= m; i++) {
1954     for (j = 1; j <= n; j++) {
1955       if ( ((utf8) && (*((short *) su+i-1) == *((short *)su2+j-1)))
1956           || ((!utf8) && ((*(s+i-1)) == (*(s2+j-1))))) {
1957         c[i*(n+1) + j] = c[(i-1)*(n+1) + j-1]+1;
1958         b[i*(n+1) + j] = LCS_UPLEFT;
1959       } else if (c[(i-1)*(n+1) + j] >= c[i*(n+1) + j-1]) {
1960         c[i*(n+1) + j] = c[(i-1)*(n+1) + j];
1961         b[i*(n+1) + j] = LCS_UP;
1962       } else {
1963         c[i*(n+1) + j] = c[i*(n+1) + j-1];
1964         b[i*(n+1) + j] = LCS_LEFT;
1965       }
1966     }
1967   }
1968   *result = b;
1969   free(c);
1970   *l1 = m;
1971   *l2 = n;
1972 }
1973
1974 int SuggestMgr::lcslen(const char * s, const char* s2) {
1975   int m;
1976   int n;
1977   int i;
1978   int j;
1979   char * result;
1980   int len = 0;
1981   lcs(s, s2, &m, &n, &result);
1982   if (!result) return 0;
1983   i = m;
1984   j = n;
1985   while ((i != 0) && (j != 0)) {
1986     if (result[i*(n+1) + j] == LCS_UPLEFT) {
1987       len++;
1988       i--;
1989       j--;
1990     } else if (result[i*(n+1) + j] == LCS_UP) {
1991       i--;
1992     } else j--;
1993   }
1994   free(result);
1995   return len;
1996 }