icuSources/common/caniter.cpp

   1 /*
   2  *****************************************************************************
   3  * Copyright (C) 1996-2010, International Business Machines Corporation and  *
   4  * others. All Rights Reserved.                                              *
   5  *****************************************************************************
   6  */
   7
   8 #include "unicode/utypes.h"
   9
  10 #if !UCONFIG_NO_NORMALIZATION
  11
  12 #include "unicode/caniter.h"
  13 #include "unicode/normalizer2.h"
  14 #include "unicode/uchar.h"
  15 #include "unicode/uniset.h"
  16 #include "unicode/usetiter.h"
  17 #include "unicode/ustring.h"
  18 #include "cmemory.h"
  19 #include "hash.h"
  20 #include "normalizer2impl.h"
  21
  22 /**
  23  * This class allows one to iterate through all the strings that are canonically equivalent to a given
  24  * string. For example, here are some sample results:
  25 Results for: {LATIN CAPITAL LETTER A WITH RING ABOVE}{LATIN SMALL LETTER D}{COMBINING DOT ABOVE}{COMBINING CEDILLA}
  26 1: \u0041\u030A\u0064\u0307\u0327
  27  = {LATIN CAPITAL LETTER A}{COMBINING RING ABOVE}{LATIN SMALL LETTER D}{COMBINING DOT ABOVE}{COMBINING CEDILLA}
  28 2: \u0041\u030A\u0064\u0327\u0307
  29  = {LATIN CAPITAL LETTER A}{COMBINING RING ABOVE}{LATIN SMALL LETTER D}{COMBINING CEDILLA}{COMBINING DOT ABOVE}
  30 3: \u0041\u030A\u1E0B\u0327
  31  = {LATIN CAPITAL LETTER A}{COMBINING RING ABOVE}{LATIN SMALL LETTER D WITH DOT ABOVE}{COMBINING CEDILLA}
  32 4: \u0041\u030A\u1E11\u0307
  33  = {LATIN CAPITAL LETTER A}{COMBINING RING ABOVE}{LATIN SMALL LETTER D WITH CEDILLA}{COMBINING DOT ABOVE}
  34 5: \u00C5\u0064\u0307\u0327
  35  = {LATIN CAPITAL LETTER A WITH RING ABOVE}{LATIN SMALL LETTER D}{COMBINING DOT ABOVE}{COMBINING CEDILLA}
  36 6: \u00C5\u0064\u0327\u0307
  37  = {LATIN CAPITAL LETTER A WITH RING ABOVE}{LATIN SMALL LETTER D}{COMBINING CEDILLA}{COMBINING DOT ABOVE}
  38 7: \u00C5\u1E0B\u0327
  39  = {LATIN CAPITAL LETTER A WITH RING ABOVE}{LATIN SMALL LETTER D WITH DOT ABOVE}{COMBINING CEDILLA}
  40 8: \u00C5\u1E11\u0307
  41  = {LATIN CAPITAL LETTER A WITH RING ABOVE}{LATIN SMALL LETTER D WITH CEDILLA}{COMBINING DOT ABOVE}
  42 9: \u212B\u0064\u0307\u0327
  43  = {ANGSTROM SIGN}{LATIN SMALL LETTER D}{COMBINING DOT ABOVE}{COMBINING CEDILLA}
  44 10: \u212B\u0064\u0327\u0307
  45  = {ANGSTROM SIGN}{LATIN SMALL LETTER D}{COMBINING CEDILLA}{COMBINING DOT ABOVE}
  46 11: \u212B\u1E0B\u0327
  47  = {ANGSTROM SIGN}{LATIN SMALL LETTER D WITH DOT ABOVE}{COMBINING CEDILLA}
  48 12: \u212B\u1E11\u0307
  49  = {ANGSTROM SIGN}{LATIN SMALL LETTER D WITH CEDILLA}{COMBINING DOT ABOVE}
  50  *<br>Note: the code is intended for use with small strings, and is not suitable for larger ones,
  51  * since it has not been optimized for that situation.
  52  *@author M. Davis
  53  *@draft
  54  */
  55
  56 // public
  57
  58 U_NAMESPACE_BEGIN
  59
  60 // TODO: add boilerplate methods.
  61
  62 UOBJECT_DEFINE_RTTI_IMPLEMENTATION(CanonicalIterator)
  63
  64 /**
  65  *@param source string to get results for
  66  */
  67 CanonicalIterator::CanonicalIterator(const UnicodeString &sourceStr, UErrorCode &status) :
  68     pieces(NULL),
  69     pieces_length(0),
  70     pieces_lengths(NULL),
  71     current(NULL),
  72     current_length(0),
  73     nfd(*Normalizer2Factory::getNFDInstance(status)),
  74     nfcImpl(*Normalizer2Factory::getNFCImpl(status))
  75 {
  76     if(U_SUCCESS(status) && nfcImpl.ensureCanonIterData(status)) {
  77       setSource(sourceStr, status);
  78     }
  79 }
  80
  81 CanonicalIterator::~CanonicalIterator() {
  82   cleanPieces();
  83 }
  84
  85 void CanonicalIterator::cleanPieces() {
  86     int32_t i = 0;
  87     if(pieces != NULL) {
  88         for(i = 0; i < pieces_length; i++) {
  89             if(pieces[i] != NULL) {
  90                 delete[] pieces[i];
  91             }
  92         }
  93         uprv_free(pieces);
  94         pieces = NULL;
  95         pieces_length = 0;
  96     }
  97     if(pieces_lengths != NULL) {
  98         uprv_free(pieces_lengths);
  99         pieces_lengths = NULL;
 100     }
 101     if(current != NULL) {
 102         uprv_free(current);
 103         current = NULL;
 104         current_length = 0;
 105     }
 106 }
 107
 108 /**
 109  *@return gets the source: NOTE: it is the NFD form of source
 110  */
 111 UnicodeString CanonicalIterator::getSource() {
 112   return source;
 113 }
 114
 115 /**
 116  * Resets the iterator so that one can start again from the beginning.
 117  */
 118 void CanonicalIterator::reset() {
 119     done = FALSE;
 120     for (int i = 0; i < current_length; ++i) {
 121         current[i] = 0;
 122     }
 123 }
 124
 125 /**
 126  *@return the next string that is canonically equivalent. The value null is returned when
 127  * the iteration is done.
 128  */
 129 UnicodeString CanonicalIterator::next() {
 130     int32_t i = 0;
 131
 132     if (done) {
 133       buffer.setToBogus();
 134       return buffer;
 135     }
 136
 137     // delete old contents
 138     buffer.remove();
 139
 140     // construct return value
 141
 142     for (i = 0; i < pieces_length; ++i) {
 143         buffer.append(pieces[i][current[i]]);
 144     }
 145     //String result = buffer.toString(); // not needed
 146
 147     // find next value for next time
 148
 149     for (i = current_length - 1; ; --i) {
 150         if (i < 0) {
 151             done = TRUE;
 152             break;
 153         }
 154         current[i]++;
 155         if (current[i] < pieces_lengths[i]) break; // got sequence
 156         current[i] = 0;
 157     }
 158     return buffer;
 159 }
 160
 161 /**
 162  *@param set the source string to iterate against. This allows the same iterator to be used
 163  * while changing the source string, saving object creation.
 164  */
 165 void CanonicalIterator::setSource(const UnicodeString &newSource, UErrorCode &status) {
 166     int32_t list_length = 0;
 167     UChar32 cp = 0;
 168     int32_t start = 0;
 169     int32_t i = 0;
 170     UnicodeString *list = NULL;
 171
 172     nfd.normalize(newSource, source, status);
 173     if(U_FAILURE(status)) {
 174       return;
 175     }
 176     done = FALSE;
 177
 178     cleanPieces();
 179
 180     // catch degenerate case
 181     if (newSource.length() == 0) {
 182         pieces = (UnicodeString **)uprv_malloc(sizeof(UnicodeString *));
 183         pieces_lengths = (int32_t*)uprv_malloc(1 * sizeof(int32_t));
 184         pieces_length = 1;
 185         current = (int32_t*)uprv_malloc(1 * sizeof(int32_t));
 186         current_length = 1;
 187         if (pieces == NULL || pieces_lengths == NULL || current == NULL) {
 188             status = U_MEMORY_ALLOCATION_ERROR;
 189             goto CleanPartialInitialization;
 190         }
 191         current[0] = 0;
 192         pieces[0] = new UnicodeString[1];
 193         pieces_lengths[0] = 1;
 194         if (pieces[0] == 0) {
 195             status = U_MEMORY_ALLOCATION_ERROR;
 196             goto CleanPartialInitialization;
 197         }
 198         return;
 199     }
 200
 201
 202     list = new UnicodeString[source.length()];
 203     if (list == 0) {
 204         status = U_MEMORY_ALLOCATION_ERROR;
 205         goto CleanPartialInitialization;
 206     }
 207
 208     // i should initialy be the number of code units at the
 209     // start of the string
 210     i = UTF16_CHAR_LENGTH(source.char32At(0));
 211     //int32_t i = 1;
 212     // find the segments
 213     // This code iterates through the source string and
 214     // extracts segments that end up on a codepoint that
 215     // doesn't start any decompositions. (Analysis is done
 216     // on the NFD form - see above).
 217     for (; i < source.length(); i += UTF16_CHAR_LENGTH(cp)) {
 218         cp = source.char32At(i);
 219         if (nfcImpl.isCanonSegmentStarter(cp)) {
 220             source.extract(start, i-start, list[list_length++]); // add up to i
 221             start = i;
 222         }
 223     }
 224     source.extract(start, i-start, list[list_length++]); // add last one
 225
 226
 227     // allocate the arrays, and find the strings that are CE to each segment
 228     pieces = (UnicodeString **)uprv_malloc(list_length * sizeof(UnicodeString *));
 229     pieces_length = list_length;
 230     pieces_lengths = (int32_t*)uprv_malloc(list_length * sizeof(int32_t));
 231     current = (int32_t*)uprv_malloc(list_length * sizeof(int32_t));
 232     current_length = list_length;
 233     if (pieces == NULL || pieces_lengths == NULL || current == NULL) {
 234         status = U_MEMORY_ALLOCATION_ERROR;
 235         goto CleanPartialInitialization;
 236     }
 237
 238     for (i = 0; i < current_length; i++) {
 239         current[i] = 0;
 240     }
 241     // for each segment, get all the combinations that can produce
 242     // it after NFD normalization
 243     for (i = 0; i < pieces_length; ++i) {
 244         //if (PROGRESS) printf("SEGMENT\n");
 245         pieces[i] = getEquivalents(list[i], pieces_lengths[i], status);
 246     }
 247
 248     delete[] list;
 249     return;
 250 // Common section to cleanup all local variables and reset object variables.
 251 CleanPartialInitialization:
 252     if (list != NULL) {
 253         delete[] list;
 254     }
 255     cleanPieces();
 256 }
 257
 258 /**
 259  * Dumb recursive implementation of permutation.
 260  * TODO: optimize
 261  * @param source the string to find permutations for
 262  * @return the results in a set.
 263  */
 264 void U_EXPORT2 CanonicalIterator::permute(UnicodeString &source, UBool skipZeros, Hashtable *result, UErrorCode &status) {
 265     if(U_FAILURE(status)) {
 266         return;
 267     }
 268     //if (PROGRESS) printf("Permute: %s\n", UToS(Tr(source)));
 269     int32_t i = 0;
 270
 271     // optimization:
 272     // if zero or one character, just return a set with it
 273     // we check for length < 2 to keep from counting code points all the time
 274     if (source.length() <= 2 && source.countChar32() <= 1) {
 275         UnicodeString *toPut = new UnicodeString(source);
 276         /* test for NULL */
 277         if (toPut == 0) {
 278             status = U_MEMORY_ALLOCATION_ERROR;
 279             return;
 280         }
 281         result->put(source, toPut, status);
 282         return;
 283     }
 284
 285     // otherwise iterate through the string, and recursively permute all the other characters
 286     UChar32 cp;
 287     Hashtable subpermute(status);
 288     if(U_FAILURE(status)) {
 289         return;
 290     }
 291     subpermute.setValueDeleter(uhash_deleteUnicodeString);
 292
 293     for (i = 0; i < source.length(); i += UTF16_CHAR_LENGTH(cp)) {
 294         cp = source.char32At(i);
 295         const UHashElement *ne = NULL;
 296         int32_t el = -1;
 297         UnicodeString subPermuteString = source;
 298
 299         // optimization:
 300         // if the character is canonical combining class zero,
 301         // don't permute it
 302         if (skipZeros && i != 0 && u_getCombiningClass(cp) == 0) {
 303             //System.out.println("Skipping " + Utility.hex(UTF16.valueOf(source, i)));
 304             continue;
 305         }
 306
 307         subpermute.removeAll();
 308
 309         // see what the permutations of the characters before and after this one are
 310         //Hashtable *subpermute = permute(source.substring(0,i) + source.substring(i + UTF16.getCharCount(cp)));
 311         permute(subPermuteString.replace(i, UTF16_CHAR_LENGTH(cp), NULL, 0), skipZeros, &subpermute, status);
 312         /* Test for buffer overflows */
 313         if(U_FAILURE(status)) {
 314             return;
 315         }
 316         // The upper replace is destructive. The question is do we have to make a copy, or we don't care about the contents
 317         // of source at this point.
 318
 319         // prefix this character to all of them
 320         ne = subpermute.nextElement(el);
 321         while (ne != NULL) {
 322             UnicodeString *permRes = (UnicodeString *)(ne->value.pointer);
 323             UnicodeString *chStr = new UnicodeString(cp);
 324             //test for  NULL
 325             if (chStr == NULL) {
 326                 status = U_MEMORY_ALLOCATION_ERROR;
 327                 return;
 328             }
 329             chStr->append(*permRes); //*((UnicodeString *)(ne->value.pointer));
 330             //if (PROGRESS) printf("  Piece: %s\n", UToS(*chStr));
 331             result->put(*chStr, chStr, status);
 332             ne = subpermute.nextElement(el);
 333         }
 334     }
 335     //return result;
 336 }
 337
 338 // privates
 339
 340 // we have a segment, in NFD. Find all the strings that are canonically equivalent to it.
 341 UnicodeString* CanonicalIterator::getEquivalents(const UnicodeString &segment, int32_t &result_len, UErrorCode &status) {
 342     Hashtable result(status);
 343     Hashtable permutations(status);
 344     Hashtable basic(status);
 345     if (U_FAILURE(status)) {
 346         return 0;
 347     }
 348     result.setValueDeleter(uhash_deleteUnicodeString);
 349     permutations.setValueDeleter(uhash_deleteUnicodeString);
 350     basic.setValueDeleter(uhash_deleteUnicodeString);
 351
 352     UChar USeg[256];
 353     int32_t segLen = segment.extract(USeg, 256, status);
 354     getEquivalents2(&basic, USeg, segLen, status);
 355
 356     // now get all the permutations
 357     // add only the ones that are canonically equivalent
 358     // TODO: optimize by not permuting any class zero.
 359
 360     const UHashElement *ne = NULL;
 361     int32_t el = -1;
 362     //Iterator it = basic.iterator();
 363     ne = basic.nextElement(el);
 364     //while (it.hasNext())
 365     while (ne != NULL) {
 366         //String item = (String) it.next();
 367         UnicodeString item = *((UnicodeString *)(ne->value.pointer));
 368
 369         permutations.removeAll();
 370         permute(item, CANITER_SKIP_ZEROES, &permutations, status);
 371         const UHashElement *ne2 = NULL;
 372         int32_t el2 = -1;
 373         //Iterator it2 = permutations.iterator();
 374         ne2 = permutations.nextElement(el2);
 375         //while (it2.hasNext())
 376         while (ne2 != NULL) {
 377             //String possible = (String) it2.next();
 378             //UnicodeString *possible = new UnicodeString(*((UnicodeString *)(ne2->value.pointer)));
 379             UnicodeString possible(*((UnicodeString *)(ne2->value.pointer)));
 380             UnicodeString attempt;
 381             nfd.normalize(possible, attempt, status);
 382
 383             // TODO: check if operator == is semanticaly the same as attempt.equals(segment)
 384             if (attempt==segment) {
 385                 //if (PROGRESS) printf("Adding Permutation: %s\n", UToS(Tr(*possible)));
 386                 // TODO: use the hashtable just to catch duplicates - store strings directly (somehow).
 387                 result.put(possible, new UnicodeString(possible), status); //add(possible);
 388             } else {
 389                 //if (PROGRESS) printf("-Skipping Permutation: %s\n", UToS(Tr(*possible)));
 390             }
 391
 392             ne2 = permutations.nextElement(el2);
 393         }
 394         ne = basic.nextElement(el);
 395     }
 396
 397     /* Test for buffer overflows */
 398     if(U_FAILURE(status)) {
 399         return 0;
 400     }
 401     // convert into a String[] to clean up storage
 402     //String[] finalResult = new String[result.size()];
 403     UnicodeString *finalResult = NULL;
 404     int32_t resultCount;
 405     if((resultCount = result.count())) {
 406         finalResult = new UnicodeString[resultCount];
 407         if (finalResult == 0) {
 408             status = U_MEMORY_ALLOCATION_ERROR;
 409             return NULL;
 410         }
 411     }
 412     else {
 413         status = U_ILLEGAL_ARGUMENT_ERROR;
 414         return NULL;
 415     }
 416     //result.toArray(finalResult);
 417     result_len = 0;
 418     el = -1;
 419     ne = result.nextElement(el);
 420     while(ne != NULL) {
 421         finalResult[result_len++] = *((UnicodeString *)(ne->value.pointer));
 422         ne = result.nextElement(el);
 423     }
 424
 425
 426     return finalResult;
 427 }
 428
 429 Hashtable *CanonicalIterator::getEquivalents2(Hashtable *fillinResult, const UChar *segment, int32_t segLen, UErrorCode &status) {
 430
 431     if (U_FAILURE(status)) {
 432         return NULL;
 433     }
 434
 435     //if (PROGRESS) printf("Adding: %s\n", UToS(Tr(segment)));
 436
 437     UnicodeString toPut(segment, segLen);
 438
 439     fillinResult->put(toPut, new UnicodeString(toPut), status);
 440
 441     UnicodeSet starts;
 442
 443     // cycle through all the characters
 444     UChar32 cp;
 445     for (int32_t i = 0; i < segLen; i += UTF16_CHAR_LENGTH(cp)) {
 446         // see if any character is at the start of some decomposition
 447         UTF_GET_CHAR(segment, 0, i, segLen, cp);
 448         if (!nfcImpl.getCanonStartSet(cp, starts)) {
 449             continue;
 450         }
 451         // if so, see which decompositions match
 452         UnicodeSetIterator iter(starts);
 453         while (iter.next()) {
 454             UChar32 cp2 = iter.getCodepoint();
 455             Hashtable remainder(status);
 456             remainder.setValueDeleter(uhash_deleteUnicodeString);
 457             if (extract(&remainder, cp2, segment, segLen, i, status) == NULL) {
 458                 continue;
 459             }
 460
 461             // there were some matches, so add all the possibilities to the set.
 462             UnicodeString prefix(segment, i);
 463             prefix += cp2;
 464
 465             int32_t el = -1;
 466             const UHashElement *ne = remainder.nextElement(el);
 467             while (ne != NULL) {
 468                 UnicodeString item = *((UnicodeString *)(ne->value.pointer));
 469                 UnicodeString *toAdd = new UnicodeString(prefix);
 470                 /* test for NULL */
 471                 if (toAdd == 0) {
 472                     status = U_MEMORY_ALLOCATION_ERROR;
 473                     return NULL;
 474                 }
 475                 *toAdd += item;
 476                 fillinResult->put(*toAdd, toAdd, status);
 477
 478                 //if (PROGRESS) printf("Adding: %s\n", UToS(Tr(*toAdd)));
 479
 480                 ne = remainder.nextElement(el);
 481             }
 482         }
 483     }
 484
 485     /* Test for buffer overflows */
 486     if(U_FAILURE(status)) {
 487         return NULL;
 488     }
 489     return fillinResult;
 490 }
 491
 492 /**
 493  * See if the decomposition of cp2 is at segment starting at segmentPos
 494  * (with canonical rearrangment!)
 495  * If so, take the remainder, and return the equivalents
 496  */
 497 Hashtable *CanonicalIterator::extract(Hashtable *fillinResult, UChar32 comp, const UChar *segment, int32_t segLen, int32_t segmentPos, UErrorCode &status) {
 498 //Hashtable *CanonicalIterator::extract(UChar32 comp, const UnicodeString &segment, int32_t segLen, int32_t segmentPos, UErrorCode &status) {
 499     //if (PROGRESS) printf(" extract: %s, ", UToS(Tr(UnicodeString(comp))));
 500     //if (PROGRESS) printf("%s, %i\n", UToS(Tr(segment)), segmentPos);
 501
 502     if (U_FAILURE(status)) {
 503         return NULL;
 504     }
 505
 506     UnicodeString temp(comp);
 507     int32_t inputLen=temp.length();
 508     UnicodeString decompString;
 509     nfd.normalize(temp, decompString, status);
 510     const UChar *decomp=decompString.getBuffer();
 511     int32_t decompLen=decompString.length();
 512
 513     // See if it matches the start of segment (at segmentPos)
 514     UBool ok = FALSE;
 515     UChar32 cp;
 516     int32_t decompPos = 0;
 517     UChar32 decompCp;
 518     U16_NEXT(decomp, decompPos, decompLen, decompCp);
 519
 520     int32_t i = segmentPos;
 521     while(i < segLen) {
 522         U16_NEXT(segment, i, segLen, cp);
 523
 524         if (cp == decompCp) { // if equal, eat another cp from decomp
 525
 526             //if (PROGRESS) printf("  matches: %s\n", UToS(Tr(UnicodeString(cp))));
 527
 528             if (decompPos == decompLen) { // done, have all decomp characters!
 529                 temp.append(segment+i, segLen-i);
 530                 ok = TRUE;
 531                 break;
 532             }
 533             U16_NEXT(decomp, decompPos, decompLen, decompCp);
 534         } else {
 535             //if (PROGRESS) printf("  buffer: %s\n", UToS(Tr(UnicodeString(cp))));
 536
 537             // brute force approach
 538             temp.append(cp);
 539
 540             /* TODO: optimize
 541             // since we know that the classes are monotonically increasing, after zero
 542             // e.g. 0 5 7 9 0 3
 543             // we can do an optimization
 544             // there are only a few cases that work: zero, less, same, greater
 545             // if both classes are the same, we fail
 546             // if the decomp class < the segment class, we fail
 547
 548             segClass = getClass(cp);
 549             if (decompClass <= segClass) return null;
 550             */
 551         }
 552     }
 553     if (!ok)
 554         return NULL; // we failed, characters left over
 555
 556     //if (PROGRESS) printf("Matches\n");
 557
 558     if (inputLen == temp.length()) {
 559         fillinResult->put(UnicodeString(), new UnicodeString(), status);
 560         return fillinResult; // succeed, but no remainder
 561     }
 562
 563     // brute force approach
 564     // check to make sure result is canonically equivalent
 565     UnicodeString trial;
 566     nfd.normalize(temp, trial, status);
 567     if(U_FAILURE(status) || trial.compare(segment+segmentPos, segLen - segmentPos) != 0) {
 568         return NULL;
 569     }
 570
 571     return getEquivalents2(fillinResult, temp.getBuffer()+inputLen, temp.length()-inputLen, status);
 572 }
 573
 574 U_NAMESPACE_END
 575
 576 #endif /* #if !UCONFIG_NO_NORMALIZATION */