ext/hunspell/suggestmgr.cxx

   1 #include "license.hunspell"
   2 #include "license.myspell"
   3
   4 #ifndef MOZILLA_CLIENT
   5 #include <cstdlib>
   6 #include <cstring>
   7 #include <cstdio>
   8 #include <cctype>
   9 #else
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #include <stdio.h>
  13 #include <ctype.h>
  14 #endif
  15
  16 #include "suggestmgr.hxx"
  17
  18 #ifndef MOZILLA_CLIENT
  19 #ifndef W32
  20 using namespace std;
  21 #endif
  22 #endif
  23
  24
  25 SuggestMgr::SuggestMgr(const char * tryme, int maxn,
  26                        AffixMgr * aptr)
  27 {
  28
  29   // register affix manager and check in string of chars to
  30   // try when building candidate suggestions
  31   pAMgr = aptr;
  32
  33   ctryl = 0;
  34   ctry = NULL;
  35   ctry_utf = NULL;
  36
  37   maxSug = maxn;
  38   nosplitsugs = 0;
  39   maxngramsugs = MAXNGRAMSUGS;
  40
  41   utf8 = 0;
  42   complexprefixes = 0;
  43
  44   if (pAMgr) {
  45         char * enc = pAMgr->get_encoding();
  46         csconv = get_current_cs(enc);
  47         free(enc);
  48         nosplitsugs = pAMgr->get_nosplitsugs();
  49         if (pAMgr->get_maxngramsugs() >= 0) maxngramsugs = pAMgr->get_maxngramsugs();
  50         utf8 = pAMgr->get_utf8();
  51         complexprefixes = pAMgr->get_complexprefixes();
  52   }
  53
  54   if (tryme) {
  55     if (utf8) {
  56         w_char t[MAXSWL];
  57         ctryl = u8_u16(t, MAXSWL, tryme);
  58         ctry_utf = (w_char *) malloc(ctryl * sizeof(w_char));
  59         memcpy(ctry_utf, t, ctryl * sizeof(w_char));
  60     } else {
  61         ctry = mystrdup(tryme);
  62         ctryl = strlen(ctry);
  63     }
  64   }
  65 }
  66
  67
  68 SuggestMgr::~SuggestMgr()
  69 {
  70   pAMgr = NULL;
  71   if (ctry) free(ctry);
  72   ctry = NULL;
  73   if (ctry_utf) free(ctry_utf);
  74   ctry_utf = NULL;
  75   ctryl = 0;
  76   maxSug = 0;
  77 }
  78
  79 int SuggestMgr::testsug(char** wlst, const char * candidate, int wl, int ns, int cpdsuggest,
  80    int * timer, time_t * timelimit) {
  81       int cwrd = 1;
  82       if (ns == maxSug) return maxSug;
  83       for (int k=0; k < ns; k++) {
  84         if (strcmp(candidate,wlst[k]) == 0) cwrd = 0;
  85       }
  86       if ((cwrd) && checkword(candidate, wl, cpdsuggest, timer, timelimit)) {
  87         wlst[ns] = mystrdup(candidate);
  88         if (wlst[ns] == NULL) {
  89             for (int j=0; j<ns; j++) free(wlst[j]);
  90             return -1;
  91         }
  92         ns++;
  93       }
  94       return ns;
  95 }
  96
  97 // generate suggestions for a mispelled word
  98 //    pass in address of array of char * pointers
  99
 100 int SuggestMgr::suggest(char*** slst, const char * w, int nsug)
 101 {
 102     int nocompoundtwowords = 0;
 103     char ** wlst;
 104     w_char word_utf[MAXSWL];
 105     int wl = 0;
 106
 107   char w2[MAXWORDUTF8LEN];
 108   const char * word = w;
 109
 110   // word reversing wrapper for complex prefixes
 111   if (complexprefixes) {
 112     strcpy(w2, w);
 113     if (utf8) reverseword_utf(w2); else reverseword(w2);
 114     word = w2;
 115   }
 116
 117     if (*slst) {
 118         wlst = *slst;
 119     } else {
 120         wlst = (char **) malloc(maxSug * sizeof(char *));
 121         if (wlst == NULL) return -1;
 122         for (int i = 0; i < maxSug; i++) {
 123             wlst[i] = NULL;
 124         }
 125     }
 126
 127     if (utf8) {
 128         wl = u8_u16(word_utf, MAXSWL, word);
 129     }
 130
 131     for (int cpdsuggest=0; (cpdsuggest<2) && (nocompoundtwowords==0); cpdsuggest++) {
 132
 133     // suggestions for an uppercase word (html -> HTML)
 134     if ((nsug < maxSug) && (nsug > -1)) {
 135         nsug = (utf8) ? capchars_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 136                     capchars(wlst, word, nsug, cpdsuggest);
 137     }
 138
 139     // perhaps we made a typical fault of spelling
 140     if ((nsug < maxSug) && (nsug > -1))
 141     nsug = replchars(wlst, word, nsug, cpdsuggest);
 142
 143     // perhaps we made chose the wrong char from a related set
 144     if ((nsug < maxSug) && (nsug > -1) && (cpdsuggest == 0)) {
 145       nsug = mapchars(wlst, word, nsug);
 146     }
 147
 148     // did we swap the order of chars by mistake
 149     if ((nsug < maxSug) && (nsug > -1)) {
 150         nsug = (utf8) ? swapchar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 151                     swapchar(wlst, word, nsug, cpdsuggest);
 152     }
 153
 154     // did we swap the order of non adjacent chars by mistake
 155     if ((nsug < maxSug) && (nsug > -1)) {
 156         nsug = (utf8) ? longswapchar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 157                     longswapchar(wlst, word, nsug, cpdsuggest);
 158     }
 159
 160     // did we forgot a char
 161     if ((nsug < maxSug) && (nsug > -1)) {
 162         nsug = (utf8) ? forgotchar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 163                     forgotchar(wlst, word, nsug, cpdsuggest);
 164     }
 165
 166     // did we move a char
 167     if ((nsug < maxSug) && (nsug > -1)) {
 168         nsug = (utf8) ? movechar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 169                     movechar(wlst, word, nsug, cpdsuggest);
 170     }
 171
 172     // did we add a char that should not be there
 173     if ((nsug < maxSug) && (nsug > -1)) {
 174         nsug = (utf8) ? extrachar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 175                     extrachar(wlst, word, nsug, cpdsuggest);
 176     }
 177
 178     // did we just hit the wrong key in place of a good char
 179     if ((nsug < maxSug) && (nsug > -1)) {
 180         nsug = (utf8) ? badchar_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 181                     badchar(wlst, word, nsug, cpdsuggest);
 182     }
 183
 184     // did we double two characters
 185     if ((nsug < maxSug) && (nsug > -1)) {
 186         nsug = (utf8) ? doubletwochars_utf(wlst, word_utf, wl, nsug, cpdsuggest) :
 187                     doubletwochars(wlst, word, nsug, cpdsuggest);
 188     }
 189
 190
 191     // only suggest compound words when no other suggestion
 192     if ((cpdsuggest==0) && (nsug>0)) nocompoundtwowords=1;
 193
 194     // perhaps we forgot to hit space and two words ran together
 195     if ((!nosplitsugs) && (nsug < maxSug) && (nsug > -1)) {
 196                 nsug = twowords(wlst, word, nsug, cpdsuggest);
 197         }
 198
 199     } // repeating ``for'' statement compounding support
 200
 201     if (nsug < 0) {
 202      // we ran out of memory - we should free up as much as possible
 203        for (int i = 0; i < maxSug; i++)
 204          if (wlst[i] != NULL) free(wlst[i]);
 205        free(wlst);
 206        wlst = NULL;
 207     }
 208
 209     *slst = wlst;
 210     return nsug;
 211 }
 212
 213 // generate suggestions for a word with typical mistake
 214 //    pass in address of array of char * pointers
 215 #ifdef HUNSPELL_EXPERIMENTAL
 216 int SuggestMgr::suggest_auto(char*** slst, const char * w, int nsug)
 217 {
 218     int nocompoundtwowords = 0;
 219     char ** wlst;
 220
 221   char w2[MAXWORDUTF8LEN];
 222   const char * word = w;
 223
 224   // word reversing wrapper for complex prefixes
 225   if (complexprefixes) {
 226     strcpy(w2, w);
 227     if (utf8) reverseword_utf(w2); else reverseword(w2);
 228     word = w2;
 229   }
 230
 231     if (*slst) {
 232         wlst = *slst;
 233     } else {
 234         wlst = (char **) malloc(maxSug * sizeof(char *));
 235         if (wlst == NULL) return -1;
 236     }
 237
 238     for (int cpdsuggest=0; (cpdsuggest<2) && (nocompoundtwowords==0); cpdsuggest++) {
 239
 240     // perhaps we made a typical fault of spelling
 241     if ((nsug < maxSug) && (nsug > -1))
 242     nsug = replchars(wlst, word, nsug, cpdsuggest);
 243
 244     // perhaps we made chose the wrong char from a related set
 245     if ((nsug < maxSug) && (nsug > -1) && (cpdsuggest == 0))
 246       nsug = mapchars(wlst, word, nsug);
 247
 248     if ((cpdsuggest==0) && (nsug>0)) nocompoundtwowords=1;
 249
 250     // perhaps we forgot to hit space and two words ran together
 251
 252     if ((nsug < maxSug) && (nsug > -1) && check_forbidden(word, strlen(word))) {
 253                 nsug = twowords(wlst, word, nsug, cpdsuggest);
 254         }
 255
 256     } // repeating ``for'' statement compounding support
 257
 258     if (nsug < 0) {
 259        for (int i=0;i<maxSug; i++)
 260          if (wlst[i] != NULL) free(wlst[i]);
 261        free(wlst);
 262        return -1;
 263     }
 264
 265     *slst = wlst;
 266     return nsug;
 267 }
 268 #endif // END OF HUNSPELL_EXPERIMENTAL CODE
 269
 270 // suggestions for an uppercase word (html -> HTML)
 271 int SuggestMgr::capchars_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 272 {
 273   char candidate[MAXSWUTF8L];
 274   w_char candidate_utf[MAXSWL];
 275   memcpy(candidate_utf, word, wl * sizeof(w_char));
 276   mkallcap_utf(candidate_utf, wl, pAMgr->get_langnum());
 277   u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 278   return testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 279 }
 280
 281 // suggestions for an uppercase word (html -> HTML)
 282 int SuggestMgr::capchars(char** wlst, const char * word, int ns, int cpdsuggest)
 283 {
 284   char candidate[MAXSWUTF8L];
 285   strcpy(candidate, word);
 286   mkallcap(candidate, csconv);
 287   return testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 288 }
 289
 290 // suggestions for when chose the wrong char out of a related set
 291 int SuggestMgr::mapchars(char** wlst, const char * word, int ns)
 292 {
 293   time_t timelimit;
 294   int timer;
 295
 296   int wl = strlen(word);
 297   if (wl < 2 || ! pAMgr) return ns;
 298
 299   int nummap = pAMgr->get_nummap();
 300   struct mapentry* maptable = pAMgr->get_maptable();
 301   if (maptable==NULL) return ns;
 302
 303   timelimit = time(NULL);
 304   timer = MINTIMER;
 305   if (utf8) {
 306     w_char w[MAXSWL];
 307     int len = u8_u16(w, MAXSWL, word);
 308     ns = map_related_utf(w, len, 0, wlst, ns, maptable, nummap, &timer, &timelimit);
 309   } else ns = map_related(word, 0, wlst, ns, maptable, nummap, &timer, &timelimit);
 310   return ns;
 311 }
 312
 313 int SuggestMgr::map_related(const char * word, int i, char** wlst, int ns,
 314     const mapentry* maptable, int nummap, int * timer, time_t * timelimit)
 315 {
 316   char c = *(word + i);
 317   if (c == 0) {
 318       int cwrd = 1;
 319       int wl = strlen(word);
 320       for (int m=0; m < ns; m++)
 321           if (strcmp(word,wlst[m]) == 0) cwrd = 0;
 322       if ((cwrd) && (checkword(word, wl, 0, timer, timelimit) ||
 323         checkword(word, wl, 1, timer, timelimit))) {
 324           if (ns < maxSug) {
 325               wlst[ns] = mystrdup(word);
 326               if (wlst[ns] == NULL) return -1;
 327               ns++;
 328           }
 329       }
 330       return ns;
 331   }
 332   int in_map = 0;
 333   for (int j = 0; j < nummap; j++) {
 334     if (strchr(maptable[j].set,c) != 0) {
 335       in_map = 1;
 336       char * newword = mystrdup(word);
 337       for (int k = 0; k < maptable[j].len; k++) {
 338         *(newword + i) = *(maptable[j].set + k);
 339         ns = map_related(newword, (i+1), wlst, ns, maptable, nummap, timer, timelimit);
 340         if (!(*timelimit)) return ns;
 341       }
 342       free(newword);
 343     }
 344   }
 345   if (!in_map) {
 346      i++;
 347      ns = map_related(word, i, wlst, ns, maptable, nummap, timer, timelimit);
 348   }
 349   return ns;
 350 }
 351
 352 int SuggestMgr::map_related_utf(w_char * word, int len, int i, char** wlst, int ns,
 353     const mapentry* maptable, int nummap, int * timer, time_t * timelimit)
 354 {
 355   if (i == len) {
 356       int cwrd = 1;
 357       int wl;
 358       char s[MAXSWUTF8L];
 359       u16_u8(s, MAXSWUTF8L, word, len);
 360       wl = strlen(s);
 361       for (int m=0; m < ns; m++)
 362           if (strcmp(s,wlst[m]) == 0) cwrd = 0;
 363       if ((cwrd) && (checkword(s, wl, 0, timer, timelimit) ||
 364             checkword(s, wl, 1, timer, timelimit))) {
 365           if (ns < maxSug) {
 366               wlst[ns] = mystrdup(s);
 367               if (wlst[ns] == NULL) return -1;
 368               ns++;
 369           }
 370       }
 371       return ns;
 372   }
 373   int in_map = 0;
 374   unsigned short c = *((unsigned short *) word + i);
 375   for (int j = 0; j < nummap; j++) {
 376     if (flag_bsearch((unsigned short *) maptable[j].set_utf16, c, maptable[j].len)) {
 377       in_map = 1;
 378       for (int k = 0; k < maptable[j].len; k++) {
 379         *(word + i) = *(maptable[j].set_utf16 + k);
 380         ns = map_related_utf(word, len, i + 1, wlst, ns, maptable, nummap, timer, timelimit);
 381         if (!(*timelimit)) return ns;
 382       }
 383       *((unsigned short *) word + i) = c;
 384     }
 385   }
 386   if (!in_map) {
 387      i++;
 388      ns = map_related_utf(word, len, i, wlst, ns, maptable, nummap, timer, timelimit);
 389   }
 390   return ns;
 391 }
 392
 393
 394
 395 // suggestions for a typical fault of spelling, that
 396 // differs with more, than 1 letter from the right form.
 397 int SuggestMgr::replchars(char** wlst, const char * word, int ns, int cpdsuggest)
 398 {
 399   char candidate[MAXSWUTF8L];
 400   const char * r;
 401   int lenr, lenp;
 402   int wl = strlen(word);
 403   if (wl < 2 || ! pAMgr) return ns;
 404   int numrep = pAMgr->get_numrep();
 405   struct replentry* reptable = pAMgr->get_reptable();
 406   if (reptable==NULL) return ns;
 407   for (int i=0; i < numrep; i++ ) {
 408       r = word;
 409       lenr = strlen(reptable[i].pattern2);
 410       lenp = strlen(reptable[i].pattern);
 411       // search every occurence of the pattern in the word
 412       while ((r=strstr(r, reptable[i].pattern)) != NULL) {
 413           strcpy(candidate, word);
 414           if (r-word + lenr + strlen(r+lenp) >= MAXSWUTF8L) break;
 415           strcpy(candidate+(r-word),reptable[i].pattern2);
 416           strcpy(candidate+(r-word)+lenr, r+lenp);
 417           ns = testsug(wlst, candidate, wl-lenp+lenr, ns, cpdsuggest, NULL, NULL);
 418           if (ns == -1) return -1;
 419           r++; // search for the next letter
 420       }
 421    }
 422    return ns;
 423 }
 424
 425 // perhaps we doubled two characters (pattern aba -> ababa, for example vacation -> vacacation)
 426 int SuggestMgr::doubletwochars(char** wlst, const char * word, int ns, int cpdsuggest)
 427 {
 428   char candidate[MAXSWUTF8L];
 429   int state=0;
 430   int wl = strlen(word);
 431   if (wl < 5 || ! pAMgr) return ns;
 432   for (int i=2; i < wl; i++ ) {
 433       if (word[i]==word[i-2]) {
 434           state++;
 435           if (state==3) {
 436             strcpy(candidate,word);
 437             strcpy(candidate+i-1,word+i+1);
 438             ns = testsug(wlst, candidate, wl-2, ns, cpdsuggest, NULL, NULL);
 439             if (ns == -1) return -1;
 440             state=0;
 441           }
 442       } else {
 443             state=0;
 444       }
 445   }
 446   return ns;
 447 }
 448
 449 // perhaps we doubled two characters (pattern aba -> ababa, for example vacation -> vacacation)
 450 int SuggestMgr::doubletwochars_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 451 {
 452   //w_char        tmpc;
 453   w_char        candidate_utf[MAXSWL];
 454   char          candidate[MAXSWUTF8L];
 455   int state=0;
 456   if (wl < 5 || ! pAMgr) return ns;
 457   for (int i=2; i < wl; i++) {
 458       if ((word[i].l==word[i-2].l) && (word[i].h==word[i-2].h))  {
 459           state++;
 460           if (state==3) {
 461             memcpy(candidate_utf, word, (i - 1) * sizeof(w_char));
 462             memcpy(candidate_utf+i-1, word+i+1, (wl-i-1) * sizeof(w_char));
 463             u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl-2);
 464             ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 465             if (ns == -1) return -1;
 466             state=0;
 467           }
 468       } else {
 469             state=0;
 470       }
 471   }
 472   return ns;
 473 }
 474
 475 // error is wrong char in place of correct one
 476 int SuggestMgr::badchar(char ** wlst, const char * word, int ns, int cpdsuggest)
 477 {
 478   char  tmpc;
 479   char  candidate[MAXSWUTF8L];
 480   time_t timelimit = time(NULL);
 481   int timer = MINTIMER;
 482   int wl = strlen(word);
 483   strcpy(candidate, word);
 484   // swap out each char one by one and try all the tryme
 485   // chars in its place to see if that makes a good word
 486   for (int i=0; i < wl; i++) {
 487     tmpc = candidate[i];
 488     for (int j=0; j < ctryl; j++) {
 489        if (ctry[j] == tmpc) continue;
 490        candidate[i] = ctry[j];
 491        ns = testsug(wlst, candidate, wl, ns, cpdsuggest, &timer, &timelimit);
 492        if (ns == -1) return -1;
 493        if (!timelimit) return ns;
 494        candidate[i] = tmpc;
 495     }
 496   }
 497   return ns;
 498 }
 499
 500 // error is wrong char in place of correct one
 501 int SuggestMgr::badchar_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 502 {
 503   w_char        tmpc;
 504   w_char        candidate_utf[MAXSWL];
 505   char          candidate[MAXSWUTF8L];
 506   time_t timelimit = time(NULL);
 507   int timer = MINTIMER;
 508   memcpy(candidate_utf, word, wl * sizeof(w_char));
 509   // swap out each char one by one and try all the tryme
 510   // chars in its place to see if that makes a good word
 511   for (int i=0; i < wl; i++) {
 512     tmpc = candidate_utf[i];
 513     for (int j=0; j < ctryl; j++) {
 514        if ((ctry_utf[j].l == tmpc.l) && (ctry_utf[j].h == tmpc.h)) continue;
 515        candidate_utf[i] = ctry_utf[j];
 516        u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 517        ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, &timer, &timelimit);
 518        if (ns == -1) return -1;
 519        if (!timelimit) return ns;
 520        candidate_utf[i] = tmpc;
 521     }
 522   }
 523   return ns;
 524 }
 525
 526 // error is word has an extra letter it does not need
 527 int SuggestMgr::extrachar_utf(char** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 528 {
 529    char candidate[MAXSWUTF8L];
 530    w_char candidate_utf[MAXSWL];
 531    const w_char * p;
 532    w_char * r;
 533    if (wl < 2) return ns;
 534    // try omitting one char of word at a time
 535    memcpy(candidate_utf, word + 1, (wl - 1) * sizeof(w_char));
 536    for (p = word, r = candidate_utf;  p < word + wl;  ) {
 537        u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl - 1);
 538        ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 539        if (ns == -1) return -1;
 540        *r++ = *p++;
 541    }
 542    return ns;
 543 }
 544
 545 // error is word has an extra letter it does not need
 546 int SuggestMgr::extrachar(char** wlst, const char * word, int ns, int cpdsuggest)
 547 {
 548    char    candidate[MAXSWUTF8L];
 549    const char *  p;
 550    char *  r;
 551    int wl = strlen(word);
 552    if (wl < 2) return ns;
 553    // try omitting one char of word at a time
 554    strcpy (candidate, word + 1);
 555    for (p = word, r = candidate;  *p != 0;  ) {
 556       ns = testsug(wlst, candidate, wl-1, ns, cpdsuggest, NULL, NULL);
 557       if (ns == -1) return -1;
 558       *r++ = *p++;
 559    }
 560    return ns;
 561 }
 562
 563
 564 // error is missing a letter it needs
 565 int SuggestMgr::forgotchar(char ** wlst, const char * word, int ns, int cpdsuggest)
 566 {
 567    char candidate[MAXSWUTF8L];
 568    const char * p;
 569    char *       q;
 570    //int cwrd;
 571    time_t timelimit = time(NULL);
 572    int timer = MINTIMER;
 573    int wl = strlen(word);
 574    // try inserting a tryme character before every letter
 575    strcpy(candidate + 1, word);
 576    for (p = word, q = candidate;  *p != 0;  )  {
 577       for (int i = 0;  i < ctryl;  i++) {
 578          *q = ctry[i];
 579          ns = testsug(wlst, candidate, wl+1, ns, cpdsuggest, &timer, &timelimit);
 580          if (ns == -1) return -1;
 581          if (!timelimit) return ns;
 582       }
 583       *q++ = *p++;
 584    }
 585    // now try adding one to end */
 586    for (int i = 0;  i < ctryl;  i++) {
 587       *q = ctry[i];
 588       ns = testsug(wlst, candidate, wl+1, ns, cpdsuggest, NULL, NULL);
 589       if (ns == -1) return -1;
 590    }
 591    return ns;
 592 }
 593
 594 // error is missing a letter it needs
 595 int SuggestMgr::forgotchar_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 596 {
 597    w_char  candidate_utf[MAXSWL];
 598    char    candidate[MAXSWUTF8L];
 599    const w_char * p;
 600    w_char * q;
 601    int cwrd;
 602    time_t timelimit = time(NULL);
 603    int timer = MINTIMER;
 604    // try inserting a tryme character before every letter
 605    memcpy (candidate_utf + 1, word, wl * sizeof(w_char));
 606    for (p = word, q = candidate_utf;  p < (word + wl); )  {
 607       for (int i = 0;  i < ctryl;  i++) {
 608          *q = ctry_utf[i];
 609          cwrd = 1;
 610          u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl + 1);
 611          ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, &timer, &timelimit);
 612          if (ns == -1) return -1;
 613          if (!timelimit) return ns;
 614        }
 615       *q++ = *p++;
 616    }
 617    // now try adding one to end */
 618    for (int i = 0;  i < ctryl;  i++) {
 619       *q = ctry_utf[i];
 620       cwrd = 1;
 621       u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl + 1);
 622       ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 623       if (ns == -1) return -1;
 624    }
 625    return ns;
 626 }
 627
 628
 629 /* error is should have been two words */
 630 int SuggestMgr::twowords(char ** wlst, const char * word, int ns, int cpdsuggest)
 631 {
 632     char candidate[MAXSWUTF8L];
 633     char * p;
 634     int c1, c2;
 635     int forbidden = 0;
 636     int cwrd;
 637
 638     int wl=strlen(word);
 639     if (wl < 3) return ns;
 640
 641     if (pAMgr->get_langnum() == LANG_hu) forbidden = check_forbidden(word, wl);
 642
 643     strcpy(candidate + 1, word);
 644
 645     // split the string into two pieces after every char
 646     // if both pieces are good words make them a suggestion
 647     for (p = candidate + 1;  p[1] != '\0';  p++) {
 648        p[-1] = *p;
 649        // go to end of the UTF-8 character
 650        while (utf8 && ((p[1] & 0xc0) == 0x80)) {
 651          p++;
 652          p[-1] = *p;
 653        }
 654        *p = '\0';
 655        c1 = checkword(candidate,strlen(candidate), cpdsuggest, NULL, NULL);
 656        if (c1) {
 657          c2 = checkword((p+1),strlen(p+1), cpdsuggest, NULL, NULL);
 658          if (c2) {
 659             *p = ' ';
 660
 661             // spec. Hungarian code (need a better compound word support)
 662             if ((pAMgr->get_langnum() == LANG_hu) && !forbidden &&
 663                 // if 3 repeating letter, use - instead of space
 664                 (((p[-1] == p[1]) && (((p>candidate+1) && (p[-1] == p[-2])) || (p[-1] == p[2]))) ||
 665                 // or multiple compounding, with more, than 6 syllables
 666                 ((c1 == 3) && (c2 >= 2)))) *p = '-';
 667
 668             cwrd = 1;
 669             for (int k=0; k < ns; k++)
 670                 if (strcmp(candidate,wlst[k]) == 0) cwrd = 0;
 671             if (ns < maxSug) {
 672                 if (cwrd) {
 673                     wlst[ns] = mystrdup(candidate);
 674                     if (wlst[ns] == NULL) return -1;
 675                     ns++;
 676                 }
 677             } else return ns;
 678          }
 679        }
 680     }
 681     return ns;
 682 }
 683
 684
 685 // error is adjacent letter were swapped
 686 int SuggestMgr::swapchar(char ** wlst, const char * word, int ns, int cpdsuggest)
 687 {
 688    char candidate[MAXSWUTF8L];
 689    char * p;
 690    char tmpc;
 691    int wl=strlen(word);
 692    // try swapping adjacent chars one by one
 693    strcpy(candidate, word);
 694    for (p = candidate;  p[1] != 0;  p++) {
 695       tmpc = *p;
 696       *p = p[1];
 697       p[1] = tmpc;
 698       ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
 699       if (ns == -1) return -1;
 700       p[1] = *p;
 701       *p = tmpc;
 702    }
 703    return ns;
 704 }
 705
 706 // error is adjacent letter were swapped
 707 int SuggestMgr::swapchar_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 708 {
 709    w_char candidate_utf[MAXSWL];
 710    char   candidate[MAXSWUTF8L];
 711    w_char * p;
 712    w_char tmpc;
 713    // try swapping adjacent chars one by one
 714    memcpy (candidate_utf, word, wl * sizeof(w_char));
 715    for (p = candidate_utf;  p < (candidate_utf + wl - 1);  p++) {
 716       tmpc = *p;
 717       *p = p[1];
 718       p[1] = tmpc;
 719       u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 720       ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
 721       if (ns == -1) return -1;
 722       p[1] = *p;
 723       *p = tmpc;
 724    }
 725    return ns;
 726 }
 727
 728 // error is not adjacent letter were swapped
 729 int SuggestMgr::longswapchar(char ** wlst, const char * word, int ns, int cpdsuggest)
 730 {
 731    char candidate[MAXSWUTF8L];
 732    char * p;
 733    char * q;
 734    char tmpc;
 735    int wl=strlen(word);
 736    // try swapping not adjacent chars one by one
 737    strcpy(candidate, word);
 738    for (p = candidate;  *p != 0;  p++) {
 739     for (q = candidate;  *q != 0;  q++) {
 740      if (abs(p-q) > 1) {
 741       tmpc = *p;
 742       *p = *q;
 743       *q = tmpc;
 744       ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
 745       if (ns == -1) return -1;
 746       *q = *p;
 747       *p = tmpc;
 748      }
 749     }
 750    }
 751    return ns;
 752 }
 753
 754
 755 // error is adjacent letter were swapped
 756 int SuggestMgr::longswapchar_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 757 {
 758    w_char candidate_utf[MAXSWL];
 759    char   candidate[MAXSWUTF8L];
 760    w_char * p;
 761    w_char * q;
 762    w_char tmpc;
 763    // try swapping not adjacent chars
 764    memcpy (candidate_utf, word, wl * sizeof(w_char));
 765    for (p = candidate_utf;  p < (candidate_utf + wl);  p++) {
 766      for (q = candidate_utf;  q < (candidate_utf + wl);  q++) {
 767        if (abs(p-q) > 1) {
 768          tmpc = *p;
 769          *p = *q;
 770          *q = tmpc;
 771          ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 772          if (ns == -1) return -1;
 773          *q = *p;
 774          *p = tmpc;
 775        }
 776      }
 777    }
 778    return ns;
 779 }
 780
 781 // error is a letter was moved
 782 int SuggestMgr::movechar(char ** wlst, const char * word, int ns, int cpdsuggest)
 783 {
 784    char candidate[MAXSWUTF8L];
 785    char * p;
 786    char * q;
 787    char tmpc;
 788
 789    int wl=strlen(word);
 790    // try moving a char
 791    strcpy(candidate, word);
 792    for (p = candidate;  *p != 0;  p++) {
 793      for (q = p + 1;  (*q != 0) && ((q - p) < 10);  q++) {
 794       tmpc = *(q-1);
 795       *(q-1) = *q;
 796       *q = tmpc;
 797       if ((q-p) < 2) continue; // omit swap char
 798       ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 799       if (ns == -1) return -1;
 800     }
 801     strcpy(candidate, word);
 802    }
 803    for (p = candidate + wl - 1;  p > candidate;  p--) {
 804      for (q = p - 1;  (q >= candidate) && ((p - q) < 10);  q--) {
 805       tmpc = *(q+1);
 806       *(q+1) = *q;
 807       *q = tmpc;
 808       if ((p-q) < 2) continue; // omit swap char
 809       ns = testsug(wlst, candidate, strlen(candidate), ns, cpdsuggest, NULL, NULL);
 810       if (ns == -1) return -1;
 811     }
 812     strcpy(candidate, word);
 813    }
 814    return ns;
 815 }
 816
 817 // error is a letter was moved
 818 int SuggestMgr::movechar_utf(char ** wlst, const w_char * word, int wl, int ns, int cpdsuggest)
 819 {
 820    w_char candidate_utf[MAXSWL];
 821    char   candidate[MAXSWUTF8L];
 822    w_char * p;
 823    w_char * q;
 824    w_char tmpc;
 825    // try moving a char
 826    memcpy (candidate_utf, word, wl * sizeof(w_char));
 827    for (p = candidate_utf;  p < (candidate_utf + wl);  p++) {
 828      for (q = p + 1;  (q < (candidate_utf + wl)) && ((q - p) < 10);  q++) {
 829          tmpc = *(q-1);
 830          *(q-1) = *q;
 831          *q = tmpc;
 832          if ((q-p) < 2) continue; // omit swap char
 833          u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 834          ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
 835          if (ns == -1) return -1;
 836      }
 837      memcpy (candidate_utf, word, wl * sizeof(w_char));
 838    }
 839    for (p = candidate_utf + wl - 1;  p > candidate_utf;  p--) {
 840      for (q = p - 1;  (q >= candidate_utf) && ((p - q) < 10);  q--) {
 841          tmpc = *(q+1);
 842          *(q+1) = *q;
 843          *q = tmpc;
 844          if ((p-q) < 2) continue; // omit swap char
 845          u16_u8(candidate, MAXSWUTF8L, candidate_utf, wl);
 846          ns = testsug(wlst, candidate, wl, ns, cpdsuggest, NULL, NULL);
 847          if (ns == -1) return -1;
 848      }
 849      memcpy (candidate_utf, word, wl * sizeof(w_char));
 850    }
 851    return ns;
 852 }
 853
 854 // generate a set of suggestions for very poorly spelled words
 855 int SuggestMgr::ngsuggest(char** wlst, char * w, HashMgr* pHMgr)
 856 {
 857
 858   int i, j;
 859   int lval;
 860   int sc;
 861   int lp;
 862   int nonbmp = 0;
 863
 864   if (!pHMgr) return 0;
 865
 866   // exhaustively search through all root words
 867   // keeping track of the MAX_ROOTS most similar root words
 868   struct hentry * roots[MAX_ROOTS];
 869   int scores[MAX_ROOTS];
 870   for (i = 0; i < MAX_ROOTS; i++) {
 871     roots[i] = NULL;
 872     scores[i] = -100 * i;
 873   }
 874   lp = MAX_ROOTS - 1;
 875
 876   char w2[MAXWORDUTF8LEN];
 877   char * word = w;
 878
 879   // word reversing wrapper for complex prefixes
 880   if (complexprefixes) {
 881     strcpy(w2, w);
 882     if (utf8) reverseword_utf(w2); else reverseword(w2);
 883     word = w2;
 884   }
 885
 886   char mw[MAXSWUTF8L];
 887   w_char u8[MAXSWL];
 888   int nc = strlen(word);
 889   int n = (utf8) ? u8_u16(u8, MAXSWL, word) : nc;
 890
 891   // set character based ngram suggestion for words with non-BMP Unicode characters
 892   if (n == -1) {
 893     utf8 = 0;
 894     n = nc;
 895     nonbmp = 1;
 896   }
 897
 898   struct hentry* hp = NULL;
 899   int col = -1;
 900   while ((hp = pHMgr->walk_hashtable(col, hp))) {
 901     if ((hp->astr) && (pAMgr) &&
 902        (TESTAFF(hp->astr, pAMgr->get_forbiddenword(), hp->alen) ||
 903           TESTAFF(hp->astr, pAMgr->get_nosuggest(), hp->alen) ||
 904           TESTAFF(hp->astr, pAMgr->get_onlyincompound(), hp->alen))) continue;
 905     sc = ngram(3, word, hp->word, NGRAM_LONGER_WORSE);
 906     if (sc > scores[lp]) {
 907       scores[lp] = sc;
 908       roots[lp] = hp;
 909       lval = sc;
 910       for (j=0; j < MAX_ROOTS; j++)
 911         if (scores[j] < lval) {
 912           lp = j;
 913           lval = scores[j];
 914         }
 915     }
 916   }
 917
 918   // find minimum threshhold for a passable suggestion
 919   // mangle original word three differnt ways
 920   // and score them to generate a minimum acceptable score
 921   int thresh = 0;
 922   for (int sp = 1; sp < 4; sp++) {
 923      if (utf8) {
 924        for (int k=sp; k < n; k+=4) *((unsigned short *) u8 + k) = '*';
 925        u16_u8(mw, MAXSWUTF8L, u8, n);
 926        thresh = thresh + ngram(n, word, mw, NGRAM_ANY_MISMATCH);
 927      } else {
 928        strcpy(mw, word);
 929        for (int k=sp; k < n; k+=4) *(mw + k) = '*';
 930        thresh = thresh + ngram(n, word, mw, NGRAM_ANY_MISMATCH);
 931      }
 932   }
 933   thresh = thresh / 3;
 934   thresh--;
 935
 936   // now expand affixes on each of these root words and
 937   // and use length adjusted ngram scores to select
 938   // possible suggestions
 939   char * guess[MAX_GUESS];
 940   int gscore[MAX_GUESS];
 941   for(i=0;i<MAX_GUESS;i++) {
 942      guess[i] = NULL;
 943      gscore[i] = -100 * i;
 944   }
 945
 946   lp = MAX_GUESS - 1;
 947
 948   struct guessword * glst;
 949   glst = (struct guessword *) calloc(MAX_WORDS,sizeof(struct guessword));
 950   if (! glst) {
 951     if (nonbmp) utf8 = 1;
 952     return 0;
 953   }
 954
 955   for (i = 0; i < MAX_ROOTS; i++) {
 956
 957       if (roots[i]) {
 958         struct hentry * rp = roots[i];
 959         int nw = pAMgr->expand_rootword(glst, MAX_WORDS, rp->word, rp->wlen,
 960                                         rp->astr, rp->alen, word, nc);
 961
 962         for (int k = 0; k < nw ; k++) {
 963            sc = ngram(n, word, glst[k].word, NGRAM_ANY_MISMATCH);
 964            if ((sc > thresh)) {
 965               if (sc > gscore[lp]) {
 966                  if (guess[lp]) free (guess[lp]);
 967                  gscore[lp] = sc;
 968                  guess[lp] = glst[k].word;
 969                  lval = sc;
 970                  for (j=0; j < MAX_GUESS; j++)
 971                     if (gscore[j] < lval) {
 972                        lp = j;
 973                        lval = gscore[j];
 974                     }
 975               } else free (glst[k].word);
 976            } else free(glst[k].word);
 977         }
 978       }
 979   }
 980   free(glst);
 981
 982   // now we are done generating guesses
 983   // sort in order of decreasing score
 984
 985   bubblesort(&guess[0], &gscore[0], MAX_GUESS);
 986
 987   // weight suggestions with a similarity index, based on
 988   // the longest common subsequent algorithm and resort
 989
 990   int is_swap;
 991   for (i=0; i < MAX_GUESS; i++) {
 992       if (guess[i]) {
 993         // lowering guess[i]
 994         char gl[MAXSWUTF8L];
 995         int len;
 996         if (utf8) {
 997           w_char _w[MAXSWL];
 998           len = u8_u16(_w, MAXSWL, guess[i]);
 999           mkallsmall_utf(_w, len, pAMgr->get_langnum());
1000           u16_u8(gl, MAXSWUTF8L, _w, len);
1001         } else {
1002           strcpy(gl, guess[i]);
1003           mkallsmall(gl, csconv);
1004           len = strlen(guess[i]);
1005         }
1006
1007         int _lcs = lcslen(word, gl);
1008
1009         // same characters with different casing
1010         if ((n == len) && (n == _lcs)) {
1011             gscore[i] += 2000;
1012             break;
1013         }
1014
1015         // heuristic weigthing of ngram scores
1016         gscore[i] +=
1017           // length of longest common subsequent minus lenght difference
1018           2 * _lcs - abs((int) (n - len)) +
1019           // weight equal first letter
1020           equalfirstletter(word, gl) +
1021           // weight equal character positions
1022           ((_lcs == commoncharacterpositions(word, gl, &is_swap)) ? 1: 0) +
1023           // swap character (not neighboring)
1024           ((is_swap) ? 1000 : 0);
1025       }
1026   }
1027
1028   bubblesort(&guess[0], &gscore[0], MAX_GUESS);
1029
1030   // copy over
1031
1032   int ns = 0;
1033   int same = 0;
1034   for (i=0; i < MAX_GUESS; i++) {
1035     if (guess[i]) {
1036       if ((ns < maxngramsugs) && (ns < maxSug) && (!same || (gscore[i] > 1000))) {
1037         int unique = 1;
1038         // we have excellent suggestion(s)
1039         if (gscore[i] > 1000) same = 1;
1040         for (j=0; j < ns; j++)
1041           // don't suggest previous suggestions or a previous suggestion with prefixes or affixes
1042           if (strstr(guess[i], wlst[j]) ||
1043             // check forbidden words
1044             !checkword(guess[i], strlen(guess[i]), 0, NULL, NULL)) unique = 0;
1045         if (unique) wlst[ns++] = guess[i]; else free(guess[i]);
1046       } else free(guess[i]);
1047     }
1048   }
1049
1050   if (nonbmp) utf8 = 1;
1051   return ns;
1052 }
1053
1054
1055 // see if a candidate suggestion is spelled correctly
1056 // needs to check both root words and words with affixes
1057
1058 // obsolote MySpell-HU modifications:
1059 // return value 2 and 3 marks compounding with hyphen (-)
1060 // `3' marks roots without suffix
1061 int SuggestMgr::checkword(const char * word, int len, int cpdsuggest, int * timer, time_t * timelimit)
1062 {
1063   struct hentry * rv=NULL;
1064   int nosuffix = 0;
1065
1066   // check time limit
1067   if (timer) {
1068     (*timer)--;
1069     if (!(*timer) && timelimit) {
1070       if (time(NULL) > *timelimit) {
1071         *timelimit = 0;
1072         return 0;
1073       }
1074       *timer = MAXPLUSTIMER;
1075     }
1076   }
1077
1078   if (pAMgr) {
1079     if (cpdsuggest==1) {
1080       if (pAMgr->get_compound()) {
1081         rv = pAMgr->compound_check(word,len,0,0,0,0,NULL,0,NULL,NULL,1);
1082         if (rv) return 3; // XXX obsolote categorisation
1083         }
1084         return 0;
1085     }
1086
1087     rv = pAMgr->lookup(word);
1088
1089     if (rv) {
1090         if ((rv->astr) && (TESTAFF(rv->astr,pAMgr->get_forbiddenword(),rv->alen)
1091                || TESTAFF(rv->astr,pAMgr->get_nosuggest(),rv->alen))) return 0;
1092         if (rv->astr && (TESTAFF(rv->astr,pAMgr->get_pseudoroot(),rv->alen) ||
1093             TESTAFF(rv->astr,pAMgr->get_onlyincompound(),rv->alen))) rv = NULL;
1094     } else rv = pAMgr->prefix_check(word, len, 0); // only prefix, and prefix + suffix XXX
1095
1096     if (rv) {
1097         nosuffix=1;
1098     } else {
1099         rv = pAMgr->suffix_check(word, len, 0, NULL, NULL, 0, NULL); // only suffix
1100     }
1101
1102     if (!rv && pAMgr->have_contclass()) {
1103         rv = pAMgr->suffix_check_twosfx(word, len, 0, NULL, FLAG_NULL);
1104         if (!rv) rv = pAMgr->prefix_check_twosfx(word, len, 1, FLAG_NULL);
1105     }
1106
1107     // check forbidden words
1108     if ((rv) && (rv->astr) && (TESTAFF(rv->astr,pAMgr->get_forbiddenword(),rv->alen)
1109       || TESTAFF(rv->astr,pAMgr->get_nosuggest(),rv->alen) ||
1110       TESTAFF(rv->astr,pAMgr->get_onlyincompound(),rv->alen))) return 0;
1111
1112     if (rv) { // XXX obsolote
1113       if ((pAMgr->get_compoundflag()) &&
1114           TESTAFF(rv->astr, pAMgr->get_compoundflag(), rv->alen)) return 2 + nosuffix;
1115       return 1;
1116     }
1117   }
1118   return 0;
1119 }
1120
1121 int SuggestMgr::check_forbidden(const char * word, int len)
1122 {
1123   struct hentry * rv = NULL;
1124
1125   if (pAMgr) {
1126     rv = pAMgr->lookup(word);
1127     if (rv && rv->astr && (TESTAFF(rv->astr,pAMgr->get_pseudoroot(),rv->alen) ||
1128         TESTAFF(rv->astr,pAMgr->get_onlyincompound(),rv->alen))) rv = NULL;
1129     if (!(pAMgr->prefix_check(word,len,1)))
1130         rv = pAMgr->suffix_check(word,len, 0, NULL, NULL, 0, NULL); // prefix+suffix, suffix
1131     // check forbidden words
1132     if ((rv) && (rv->astr) && TESTAFF(rv->astr,pAMgr->get_forbiddenword(),rv->alen)) return 1;
1133    }
1134     return 0;
1135 }
1136
1137 #ifdef HUNSPELL_EXPERIMENTAL
1138 // suggest stems, XXX experimental code
1139 int SuggestMgr::suggest_stems(char*** slst, const char * w, int nsug)
1140 {
1141     char buf[MAXSWUTF8L];
1142     char ** wlst;
1143     int prevnsug = nsug;
1144
1145   char w2[MAXWORDUTF8LEN];
1146   const char * word = w;
1147
1148   // word reversing wrapper for complex prefixes
1149   if (complexprefixes) {
1150     strcpy(w2, w);
1151     if (utf8) reverseword_utf(w2); else reverseword(w2);
1152     word = w2;
1153   }
1154
1155     if (*slst) {
1156         wlst = *slst;
1157     } else {
1158         wlst = (char **) calloc(maxSug, sizeof(char *));
1159         if (wlst == NULL) return -1;
1160     }
1161     // perhaps there are a fix stem in the dictionary
1162     if ((nsug < maxSug) && (nsug > -1)) {
1163
1164     nsug = fixstems(wlst, word, nsug);
1165     if (nsug == prevnsug) {
1166         char * s = mystrdup(word);
1167         char * p = s + strlen(s);
1168         while ((*p != '-') && (p != s)) p--;
1169         if (*p == '-') {
1170             *p = '\0';
1171             nsug = fixstems(wlst, s, nsug);
1172             if ((nsug == prevnsug) && (nsug < maxSug) && (nsug >= 0)) {
1173                 char * t;
1174                 buf[0] = '\0';
1175                 for (t = s; (t[0] != '\0') && ((t[0] >= '0') || (t[0] <= '9')); t++); // is a number?
1176                 if (*t != '\0') strcpy(buf, "# ");
1177                 strcat(buf, s);
1178                 wlst[nsug] = mystrdup(buf);
1179                 if (wlst[nsug] == NULL) return -1;
1180                 nsug++;
1181             }
1182             p++;
1183             nsug = fixstems(wlst, p, nsug);
1184         }
1185
1186         free(s);
1187     }
1188     }
1189
1190     if (nsug < 0) {
1191        for (int i=0;i<maxSug; i++)
1192          if (wlst[i] != NULL) free(wlst[i]);
1193          free(wlst);
1194        return -1;
1195     }
1196
1197     *slst = wlst;
1198     return nsug;
1199 }
1200
1201
1202 // there are fix stems in dictionary
1203 int SuggestMgr::fixstems(char ** wlst, const char * word, int ns)
1204 {
1205     char buf[MAXSWUTF8L];
1206     char prefix[MAXSWUTF8L] = "";
1207
1208     int dicstem = 1; // 0 = lookup, 1= affix, 2 = compound
1209     int cpdindex = 0;
1210     struct hentry * rv = NULL;
1211
1212     int wl = strlen(word);
1213     int cmpdstemnum;
1214     int cmpdstem[MAXCOMPOUND];
1215
1216     if (pAMgr) {
1217         rv = pAMgr->lookup(word);
1218         if (rv) {
1219             dicstem = 0;
1220         } else {
1221             // try stripping off affixes
1222             rv = pAMgr->affix_check(word, wl);
1223
1224             // else try check compound word
1225             if (!rv && pAMgr->get_compound()) {
1226                 rv = pAMgr->compound_check(word, wl,
1227                      0, 0, 100, 0, NULL, 0, &cmpdstemnum, cmpdstem,1);
1228
1229                 if (rv) {
1230                     dicstem = 2;
1231                     for (int j = 0; j < cmpdstemnum; j++) {
1232                         cpdindex += cmpdstem[j];
1233                     }
1234                     if(! (pAMgr->lookup(word + cpdindex)))
1235                         pAMgr->affix_check(word + cpdindex, wl - cpdindex); // for prefix
1236                 }
1237             }
1238
1239
1240             if (pAMgr->get_prefix()) {
1241                 strcpy(prefix, pAMgr->get_prefix());
1242             }
1243
1244             // XXX obsolete, will be a general solution for stemming
1245             if ((prefix) && (strncmp(prefix, "leg", 3)==0)) prefix[0] = '\0'; // (HU)
1246         }
1247
1248     }
1249
1250
1251
1252     if ((rv) && (ns < maxSug)) {
1253
1254         // check fixstem flag and not_valid_stem flag
1255         // first word
1256         if ((ns < maxSug) && (dicstem < 2)) {
1257             strcpy(buf, prefix);
1258             if ((dicstem > 0) && pAMgr->get_derived()) {
1259                 // XXX obsolote
1260                    if (strlen(prefix) == 1) {
1261                         strcat(buf, (pAMgr->get_derived()) + 1);
1262                    } else {
1263                         strcat(buf, pAMgr->get_derived());
1264                    }
1265                 } else {
1266                         // special stem in affix description
1267                         const char * wordchars = pAMgr->get_wordchars();
1268                         if (rv->description &&
1269                            (strchr(wordchars, *(rv->description)))) {
1270                            char * desc = (rv->description) + 1;
1271                            while (strchr(wordchars, *desc)) desc++;
1272                            strncat(buf, rv->description, desc - (rv->description));
1273                         } else {
1274                             strcat(buf, rv->word);
1275                         }
1276                 }
1277             wlst[ns] = mystrdup(buf);
1278             if (wlst[ns] == NULL) return -1;
1279             ns++;
1280         }
1281
1282         if (dicstem == 2) {
1283
1284             // compound stem
1285
1286 //          if (rv->astr && (strchr(rv->astr, '0') == NULL)) {
1287             if (rv->astr) {
1288                 strcpy(buf, word);
1289                 buf[cpdindex] = '\0';
1290                 if (prefix) strcat(buf, prefix);
1291                 if (pAMgr->get_derived()) {
1292                         strcat(buf, pAMgr->get_derived());
1293                 } else {
1294                         // special stem in affix description
1295                         const char * wordchars = pAMgr->get_wordchars();
1296                         if (rv->description &&
1297                            (strchr(wordchars, *(rv->description)))) {
1298                            char * desc = (rv->description) + 1;
1299                            while (strchr(wordchars, *desc)) desc++;
1300                            strncat(buf, rv->description, desc - (rv->description));
1301                         } else {
1302                             strcat(buf, rv->word);
1303                         }
1304                 }
1305                 if (ns < maxSug) {
1306                     wlst[ns] = mystrdup(buf);
1307                     if (wlst[ns] == NULL) return -1;
1308                     ns++;
1309                 }
1310             }
1311         }
1312     }
1313     return ns;
1314 }
1315
1316 // suggest possible stems
1317 int SuggestMgr::suggest_pos_stems(char*** slst, const char * w, int nsug)
1318 {
1319     char ** wlst;
1320
1321     struct hentry * rv = NULL;
1322
1323   char w2[MAXSWUTF8L];
1324   const char * word = w;
1325
1326   // word reversing wrapper for complex prefixes
1327   if (complexprefixes) {
1328     strcpy(w2, w);
1329     if (utf8) reverseword_utf(w2); else reverseword(w2);
1330     word = w2;
1331   }
1332
1333     int wl = strlen(word);
1334
1335
1336     if (*slst) {
1337         wlst = *slst;
1338     } else {
1339         wlst = (char **) calloc(maxSug, sizeof(char *));
1340         if (wlst == NULL) return -1;
1341     }
1342
1343     rv = pAMgr->suffix_check(word, wl, 0, NULL, wlst, maxSug, &nsug);
1344
1345     // delete dash from end of word
1346     if (nsug > 0) {
1347         for (int j=0; j < nsug; j++) {
1348             if (wlst[j][strlen(wlst[j]) - 1] == '-') wlst[j][strlen(wlst[j]) - 1] = '\0';
1349         }
1350     }
1351
1352     *slst = wlst;
1353     return nsug;
1354 }
1355
1356
1357 char * SuggestMgr::suggest_morph(const char * w)
1358 {
1359     char result[MAXLNLEN];
1360     char * r = (char *) result;
1361     char * st;
1362
1363     struct hentry * rv = NULL;
1364
1365     *result = '\0';
1366
1367     if (! pAMgr) return NULL;
1368
1369   char w2[MAXSWUTF8L];
1370   const char * word = w;
1371
1372   // word reversing wrapper for complex prefixes
1373   if (complexprefixes) {
1374     strcpy(w2, w);
1375     if (utf8) reverseword_utf(w2); else reverseword(w2);
1376     word = w2;
1377   }
1378
1379     rv = pAMgr->lookup(word);
1380
1381     while (rv) {
1382         if ((!rv->astr) || !(TESTAFF(rv->astr, pAMgr->get_forbiddenword(), rv->alen) ||
1383             TESTAFF(rv->astr, pAMgr->get_pseudoroot(), rv->alen) ||
1384             TESTAFF(rv->astr,pAMgr->get_onlyincompound(),rv->alen))) {
1385             if (rv->description && ((!rv->astr) ||
1386                 !TESTAFF(rv->astr, pAMgr->get_lemma_present(), rv->alen)))
1387                     strcat(result, word);
1388             if (rv->description) strcat(result, rv->description);
1389             strcat(result, "\n");
1390         }
1391         rv = rv->next_homonym;
1392     }
1393
1394     st = pAMgr->affix_check_morph(word,strlen(word));
1395     if (st) {
1396         strcat(result, st);
1397         free(st);
1398     }
1399
1400     if (pAMgr->get_compound() && (*result == '\0'))
1401         pAMgr->compound_check_morph(word, strlen(word),
1402                      0, 0, 100, 0,NULL, 0, &r, NULL);
1403
1404     return (*result) ? mystrdup(line_uniq(delete_zeros(result))) : NULL;
1405 }
1406
1407 char * SuggestMgr::suggest_morph_for_spelling_error(const char * word)
1408 {
1409     char * p = NULL;
1410     char ** wlst = (char **) calloc(maxSug, sizeof(char *));
1411     // we will use only the first suggestion
1412     for (int i = 0; i < maxSug - 1; i++) wlst[i] = "";
1413     int ns = suggest(&wlst, word, maxSug - 1);
1414     if (ns == maxSug) {
1415         p = suggest_morph(wlst[maxSug - 1]);
1416         free(wlst[maxSug - 1]);
1417     }
1418     if (wlst) free(wlst);
1419     return p;
1420 }
1421 #endif // END OF HUNSPELL_EXPERIMENTAL CODE
1422
1423
1424 // generate an n-gram score comparing s1 and s2
1425 int SuggestMgr::ngram(int n, char * s1, const char * s2, int uselen)
1426 {
1427   int nscore = 0;
1428   int ns;
1429   int l1;
1430   int l2;
1431
1432   if (utf8) {
1433     w_char su1[MAXSWL];
1434     w_char su2[MAXSWL];
1435     l1 = u8_u16(su1, MAXSWL, s1);
1436     l2 = u8_u16(su2, MAXSWL, s2);
1437     if (!l2 || (l1==-1) || (l2==-1)) return 0;
1438     // decapitalize dictionary word
1439     if (complexprefixes) {
1440       mkallsmall_utf(su2+l2-1, 1, pAMgr->get_langnum());
1441     } else {
1442       mkallsmall_utf(su2, 1, pAMgr->get_langnum());
1443     }
1444     for (int j = 1; j <= n; j++) {
1445       ns = 0;
1446       for (int i = 0; i <= (l1-j); i++) {
1447         for (int l = 0; l <= (l2-j); l++) {
1448             int k;
1449             for (k = 0; (k < j); k++) {
1450               w_char * c1 = su1 + i + k;
1451               w_char * c2 = su2 + l + k;
1452               if ((c1->l != c2->l) || (c1->h != c2->h)) break;
1453             }
1454             if (k == j) {
1455                 ns++;
1456                 break;
1457             }
1458         }
1459       }
1460       nscore = nscore + ns;
1461       if (ns < 2) break;
1462     }
1463   } else {
1464     char t[MAXSWUTF8L];
1465     l1 = strlen(s1);
1466     l2 = strlen(s2);
1467     if (!l2) return 0;
1468     strcpy(t, s2);
1469     if (complexprefixes) {
1470       *(t+l2-1) = csconv[((unsigned char)*(t+l2-1))].clower;
1471     } else {
1472     mkallsmall(t, csconv);
1473     }
1474     for (int j = 1; j <= n; j++) {
1475       ns = 0;
1476       for (int i = 0; i <= (l1-j); i++) {
1477         char c = *(s1 + i + j);
1478         *(s1 + i + j) = '\0';
1479         if (strstr(t,(s1+i))) ns++;
1480         *(s1 + i + j ) = c;
1481       }
1482       nscore = nscore + ns;
1483       if (ns < 2) break;
1484     }
1485   }
1486
1487   ns = 0;
1488   if (uselen == NGRAM_LONGER_WORSE) ns = (l2-l1)-2;
1489   if (uselen == NGRAM_ANY_MISMATCH) ns = abs(l2-l1)-2;
1490   ns = (nscore - ((ns > 0) ? ns : 0));
1491   return ns;
1492 }
1493
1494 int SuggestMgr::equalfirstletter(char * s1, const char * s2) {
1495   if (utf8) {
1496     w_char su1[MAXSWL];
1497     w_char su2[MAXSWL];
1498     // decapitalize dictionary word
1499     if (complexprefixes) {
1500       int l1 = u8_u16(su1, MAXSWL, s1);
1501       int l2 = u8_u16(su2, MAXSWL, s2);
1502       if (*((short *)su1+l1-1) == *((short *)su2+l2-1)) return 1;
1503     } else {
1504       u8_u16(su1, 1, s1);
1505       u8_u16(su2, 1, s2);
1506       if (*((short *)su1) == *((short *)su2)) return 1;
1507     }
1508   } else {
1509     if (complexprefixes) {
1510       int l1 = strlen(s1);
1511       int l2 = strlen(s2);
1512       if (*(s2+l1-1) == *(s2+l2-1)) return 1;
1513     } else {
1514       if (*s1 == *s2) return 1;
1515     }
1516   }
1517   return 0;
1518 }
1519
1520 int SuggestMgr::commoncharacterpositions(char * s1, const char * s2, int * is_swap) {
1521   int num = 0;
1522   int diff = 0;
1523   int diffpos[2];
1524   *is_swap = 0;
1525   if (utf8) {
1526     w_char su1[MAXSWL];
1527     w_char su2[MAXSWL];
1528     int l1 = u8_u16(su1, MAXSWL, s1);
1529     int l2 = u8_u16(su2, MAXSWL, s2);
1530     if (!l2 || (l1==-1) || (l2==-1)) return 0;
1531     // decapitalize dictionary word
1532     if (complexprefixes) {
1533       mkallsmall_utf(su2+l2-1, 1, pAMgr->get_langnum());
1534     } else {
1535       mkallsmall_utf(su2, 1, pAMgr->get_langnum());
1536     }
1537     for (int i = 0; (i < l1) && (i < l2); i++) {
1538       if (((short *) su1)[i] == ((short *) su2)[i]) {
1539         num++;
1540       } else {
1541         if (diff < 2) diffpos[diff] = i;
1542         diff++;
1543       }
1544     }
1545     if ((diff == 2) && (l1 == l2) &&
1546         (((short *) su1)[diffpos[0]] == ((short *) su2)[diffpos[1]]) &&
1547         (((short *) su1)[diffpos[1]] == ((short *) su2)[diffpos[0]])) *is_swap = 1;
1548   } else {
1549     int i;
1550     char t[MAXSWUTF8L];
1551     strcpy(t, s2);
1552     // decapitalize dictionary word
1553     if (complexprefixes) {
1554       int l2 = strlen(t);
1555       *(t+l2-1) = csconv[((unsigned char)*(t+l2-1))].clower;
1556     } else {
1557       mkallsmall(t, csconv);
1558     }
1559     for (i = 0; (*(s1+i) != 0) && (*(t+i) != 0); i++) {
1560       if (*(s1+i) == *(t+i)) {
1561         num++;
1562       } else {
1563         if (diff < 2) diffpos[diff] = i;
1564         diff++;
1565       }
1566     }
1567     if ((diff == 2) && (*(s1+i) == 0) && (*(t+i) == 0) &&
1568       (*(s1+diffpos[0]) == *(t+diffpos[1])) &&
1569       (*(s1+diffpos[1]) == *(t+diffpos[0]))) *is_swap = 1;
1570   }
1571   return num;
1572 }
1573
1574 int SuggestMgr::mystrlen(const char * word) {
1575   if (utf8) {
1576     w_char w[MAXSWL];
1577     return u8_u16(w, MAXSWL, word);
1578   } else return strlen(word);
1579 }
1580
1581 // sort in decreasing order of score
1582 void SuggestMgr::bubblesort(char** rword, int* rsc, int n )
1583 {
1584       int m = 1;
1585       while (m < n) {
1586           int j = m;
1587           while (j > 0) {
1588             if (rsc[j-1] < rsc[j]) {
1589                 int sctmp = rsc[j-1];
1590                 char * wdtmp = rword[j-1];
1591                 rsc[j-1] = rsc[j];
1592                 rword[j-1] = rword[j];
1593                 rsc[j] = sctmp;
1594                 rword[j] = wdtmp;
1595                 j--;
1596             } else break;
1597           }
1598           m++;
1599       }
1600       return;
1601 }
1602
1603 // longest common subsequence
1604 void SuggestMgr::lcs(const char * s, const char * s2, int * l1, int * l2, char ** result) {
1605   int n, m;
1606   w_char su[MAXSWL];
1607   w_char su2[MAXSWL];
1608   char * b;
1609   char * c;
1610   int i;
1611   int j;
1612   if (utf8) {
1613     m = u8_u16(su, MAXSWL, s);
1614     n = u8_u16(su2, MAXSWL, s2);
1615   } else {
1616     m = strlen(s);
1617     n = strlen(s2);
1618   }
1619   c = (char *) malloc((m + 1) * (n + 1));
1620   b = (char *) malloc((m + 1) * (n + 1));
1621   for (i = 1; i <= m; i++) c[i*(n+1)] = 0;
1622   for (j = 0; j <= n; j++) c[j] = 0;
1623   for (i = 1; i <= m; i++) {
1624     for (j = 1; j <= n; j++) {
1625       if ((utf8) && (*((short *) su+i-1) == *((short *)su2+j-1))
1626           || (!utf8) && ((*(s+i-1)) == (*(s2+j-1)))) {
1627         c[i*(n+1) + j] = c[(i-1)*(n+1) + j-1]+1;
1628         b[i*(n+1) + j] = LCS_UPLEFT;
1629       } else if (c[(i-1)*(n+1) + j] >= c[i*(n+1) + j-1]) {
1630         c[i*(n+1) + j] = c[(i-1)*(n+1) + j];
1631         b[i*(n+1) + j] = LCS_UP;
1632       } else {
1633         c[i*(n+1) + j] = c[i*(n+1) + j-1];
1634         b[i*(n+1) + j] = LCS_LEFT;
1635       }
1636     }
1637   }
1638   *result = b;
1639   free(c);
1640   *l1 = m;
1641   *l2 = n;
1642 }
1643
1644 int SuggestMgr::lcslen(const char * s, const char* s2) {
1645   int m;
1646   int n;
1647   int i;
1648   int j;
1649   char * result;
1650   int len = 0;
1651   lcs(s, s2, &m, &n, &result);
1652   i = m;
1653   j = n;
1654   while ((i != 0) && (j != 0)) {
1655     if (result[i*(n+1) + j] == LCS_UPLEFT) {
1656       len++;
1657       i--;
1658       j--;
1659     } else if (result[i*(n+1) + j] == LCS_UP) {
1660       i--;
1661     } else j--;
1662   }
1663   if (result) free(result);
1664   return len;
1665 }