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