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