1 // 2016 and later: Unicode, Inc. and others. 2 // License & terms of use: http://www.unicode.org/copyright.html 3 /* 4 ******************************************************************************* 5 * Copyright (C) 2010-2014, International Business Machines 6 * Corporation and others. All Rights Reserved. 7 ******************************************************************************* 8 * collationiterator.cpp 9 * 10 * created on: 2010oct27 11 * created by: Markus W. Scherer 12 */ 13 14 #include "utypeinfo.h" // for 'typeid' to work 15 16 #include "unicode/utypes.h" 17 18 #if !UCONFIG_NO_COLLATION 19 20 #include "unicode/ucharstrie.h" 21 #include "unicode/ustringtrie.h" 22 #include "charstr.h" 23 #include "cmemory.h" 24 #include "collation.h" 25 #include "collationdata.h" 26 #include "collationfcd.h" 27 #include "collationiterator.h" 28 #include "normalizer2impl.h" 29 #include "uassert.h" 30 #include "uvectr32.h" 31 32 U_NAMESPACE_BEGIN 33 34 CollationIterator::CEBuffer::~CEBuffer() {} 35 36 UBool 37 CollationIterator::CEBuffer::ensureAppendCapacity(int32_t appCap, UErrorCode &errorCode) { 38 int32_t capacity = buffer.getCapacity(); 39 if((length + appCap) <= capacity) { return TRUE; } 40 if(U_FAILURE(errorCode)) { return FALSE; } 41 do { 42 if(capacity < 1000) { 43 capacity *= 4; 44 } else { 45 capacity *= 2; 46 } 47 } while(capacity < (length + appCap)); 48 int64_t *p = buffer.resize(capacity, length); 49 if(p == NULL) { 50 errorCode = U_MEMORY_ALLOCATION_ERROR; 51 return FALSE; 52 } 53 return TRUE; 54 } 55 56 // State of combining marks skipped in discontiguous contraction. 57 // We create a state object on first use and keep it around deactivated between uses. 58 class SkippedState : public UMemory { 59 public: 60 // Born active but empty. 61 SkippedState() : pos(0), skipLengthAtMatch(0) {} 62 void clear() { 63 oldBuffer.remove(); 64 pos = 0; 65 // The newBuffer is reset by setFirstSkipped(). 66 } 67 68 UBool isEmpty() const { return oldBuffer.isEmpty(); } 69 70 UBool hasNext() const { return pos < oldBuffer.length(); } 71 72 // Requires hasNext(). 73 UChar32 next() { 74 UChar32 c = oldBuffer.char32At(pos); 75 pos += U16_LENGTH(c); 76 return c; 77 } 78 79 // Accounts for one more input code point read beyond the end of the marks buffer. 80 void incBeyond() { 81 U_ASSERT(!hasNext()); 82 ++pos; 83 } 84 85 // Goes backward through the skipped-marks buffer. 86 // Returns the number of code points read beyond the skipped marks 87 // that need to be backtracked through normal input. 88 int32_t backwardNumCodePoints(int32_t n) { 89 int32_t length = oldBuffer.length(); 90 int32_t beyond = pos - length; 91 if(beyond > 0) { 92 if(beyond >= n) { 93 // Not back far enough to re-enter the oldBuffer. 94 pos -= n; 95 return n; 96 } else { 97 // Back out all beyond-oldBuffer code points and re-enter the buffer. 98 pos = oldBuffer.moveIndex32(length, beyond - n); 99 return beyond; 100 } 101 } else { 102 // Go backwards from inside the oldBuffer. 103 pos = oldBuffer.moveIndex32(pos, -n); 104 return 0; 105 } 106 } 107 108 void setFirstSkipped(UChar32 c) { 109 skipLengthAtMatch = 0; 110 newBuffer.setTo(c); 111 } 112 113 void skip(UChar32 c) { 114 newBuffer.append(c); 115 } 116 117 void recordMatch() { skipLengthAtMatch = newBuffer.length(); } 118 119 // Replaces the characters we consumed with the newly skipped ones. 120 void replaceMatch() { 121 // Note: UnicodeString.replace() pins pos to at most length(). 122 oldBuffer.replace(0, pos, newBuffer, 0, skipLengthAtMatch); 123 pos = 0; 124 } 125 126 void saveTrieState(const UCharsTrie &trie) { trie.saveState(state); } 127 void resetToTrieState(UCharsTrie &trie) const { trie.resetToState(state); } 128 129 private: 130 // Combining marks skipped in previous discontiguous-contraction matching. 131 // After that discontiguous contraction was completed, we start reading them from here. 132 UnicodeString oldBuffer; 133 // Combining marks newly skipped in current discontiguous-contraction matching. 134 // These might have been read from the normal text or from the oldBuffer. 135 UnicodeString newBuffer; 136 // Reading index in oldBuffer, 137 // or counter for how many code points have been read beyond oldBuffer (pos-oldBuffer.length()). 138 int32_t pos; 139 // newBuffer.length() at the time of the last matching character. 140 // When a partial match fails, we back out skipped and partial-matching input characters. 141 int32_t skipLengthAtMatch; 142 // We save the trie state before we attempt to match a character, 143 // so that we can skip it and try the next one. 144 UCharsTrie::State state; 145 }; 146 147 CollationIterator::CollationIterator(const CollationIterator &other) 148 : UObject(other), 149 trie(other.trie), 150 data(other.data), 151 cesIndex(other.cesIndex), 152 skipped(NULL), 153 numCpFwd(other.numCpFwd), 154 isNumeric(other.isNumeric) { 155 UErrorCode errorCode = U_ZERO_ERROR; 156 int32_t length = other.ceBuffer.length; 157 if(length > 0 && ceBuffer.ensureAppendCapacity(length, errorCode)) { 158 for(int32_t i = 0; i < length; ++i) { 159 ceBuffer.set(i, other.ceBuffer.get(i)); 160 } 161 ceBuffer.length = length; 162 } else { 163 cesIndex = 0; 164 } 165 } 166 167 CollationIterator::~CollationIterator() { 168 delete skipped; 169 } 170 171 UBool 172 CollationIterator::operator==(const CollationIterator &other) const { 173 // Subclasses: Call this method and then add more specific checks. 174 // Compare the iterator state but not the collation data (trie & data fields): 175 // Assume that the caller compares the data. 176 // Ignore skipped since that should be unused between calls to nextCE(). 177 // (It only stays around to avoid another memory allocation.) 178 if(!(typeid(*this) == typeid(other) && 179 ceBuffer.length == other.ceBuffer.length && 180 cesIndex == other.cesIndex && 181 numCpFwd == other.numCpFwd && 182 isNumeric == other.isNumeric)) { 183 return FALSE; 184 } 185 for(int32_t i = 0; i < ceBuffer.length; ++i) { 186 if(ceBuffer.get(i) != other.ceBuffer.get(i)) { return FALSE; } 187 } 188 return TRUE; 189 } 190 191 void 192 CollationIterator::reset() { 193 cesIndex = ceBuffer.length = 0; 194 if(skipped != NULL) { skipped->clear(); } 195 } 196 197 int32_t 198 CollationIterator::fetchCEs(UErrorCode &errorCode) { 199 while(U_SUCCESS(errorCode) && nextCE(errorCode) != Collation::NO_CE) { 200 // No need to loop for each expansion CE. 201 cesIndex = ceBuffer.length; 202 } 203 return ceBuffer.length; 204 } 205 206 uint32_t 207 CollationIterator::handleNextCE32(UChar32 &c, UErrorCode &errorCode) { 208 c = nextCodePoint(errorCode); 209 return (c < 0) ? Collation::FALLBACK_CE32 : data->getCE32(c); 210 } 211 212 UChar 213 CollationIterator::handleGetTrailSurrogate() { 214 return 0; 215 } 216 217 UBool 218 CollationIterator::foundNULTerminator() { 219 return FALSE; 220 } 221 222 UBool 223 CollationIterator::forbidSurrogateCodePoints() const { 224 return FALSE; 225 } 226 227 uint32_t 228 CollationIterator::getDataCE32(UChar32 c) const { 229 return data->getCE32(c); 230 } 231 232 uint32_t 233 CollationIterator::getCE32FromBuilderData(uint32_t /*ce32*/, UErrorCode &errorCode) { 234 if(U_SUCCESS(errorCode)) { errorCode = U_INTERNAL_PROGRAM_ERROR; } 235 return 0; 236 } 237 238 int64_t 239 CollationIterator::nextCEFromCE32(const CollationData *d, UChar32 c, uint32_t ce32, 240 UErrorCode &errorCode) { 241 --ceBuffer.length; // Undo ceBuffer.incLength(). 242 appendCEsFromCE32(d, c, ce32, TRUE, errorCode); 243 if(U_SUCCESS(errorCode)) { 244 return ceBuffer.get(cesIndex++); 245 } else { 246 return Collation::NO_CE_PRIMARY; 247 } 248 } 249 250 void 251 CollationIterator::appendCEsFromCE32(const CollationData *d, UChar32 c, uint32_t ce32, 252 UBool forward, UErrorCode &errorCode) { 253 while(Collation::isSpecialCE32(ce32)) { 254 switch(Collation::tagFromCE32(ce32)) { 255 case Collation::FALLBACK_TAG: 256 case Collation::RESERVED_TAG_3: 257 if(U_SUCCESS(errorCode)) { errorCode = U_INTERNAL_PROGRAM_ERROR; } 258 return; 259 case Collation::LONG_PRIMARY_TAG: 260 ceBuffer.append(Collation::ceFromLongPrimaryCE32(ce32), errorCode); 261 return; 262 case Collation::LONG_SECONDARY_TAG: 263 ceBuffer.append(Collation::ceFromLongSecondaryCE32(ce32), errorCode); 264 return; 265 case Collation::LATIN_EXPANSION_TAG: 266 if(ceBuffer.ensureAppendCapacity(2, errorCode)) { 267 ceBuffer.set(ceBuffer.length, Collation::latinCE0FromCE32(ce32)); 268 ceBuffer.set(ceBuffer.length + 1, Collation::latinCE1FromCE32(ce32)); 269 ceBuffer.length += 2; 270 } 271 return; 272 case Collation::EXPANSION32_TAG: { 273 const uint32_t *ce32s = d->ce32s + Collation::indexFromCE32(ce32); 274 int32_t length = Collation::lengthFromCE32(ce32); 275 if(ceBuffer.ensureAppendCapacity(length, errorCode)) { 276 do { 277 ceBuffer.appendUnsafe(Collation::ceFromCE32(*ce32s++)); 278 } while(--length > 0); 279 } 280 return; 281 } 282 case Collation::EXPANSION_TAG: { 283 const int64_t *ces = d->ces + Collation::indexFromCE32(ce32); 284 int32_t length = Collation::lengthFromCE32(ce32); 285 if(ceBuffer.ensureAppendCapacity(length, errorCode)) { 286 do { 287 ceBuffer.appendUnsafe(*ces++); 288 } while(--length > 0); 289 } 290 return; 291 } 292 case Collation::BUILDER_DATA_TAG: 293 ce32 = getCE32FromBuilderData(ce32, errorCode); 294 if(U_FAILURE(errorCode)) { return; } 295 if(ce32 == Collation::FALLBACK_CE32) { 296 d = data->base; 297 ce32 = d->getCE32(c); 298 } 299 break; 300 case Collation::PREFIX_TAG: 301 if(forward) { backwardNumCodePoints(1, errorCode); } 302 ce32 = getCE32FromPrefix(d, ce32, errorCode); 303 if(forward) { forwardNumCodePoints(1, errorCode); } 304 break; 305 case Collation::CONTRACTION_TAG: { 306 const UChar *p = d->contexts + Collation::indexFromCE32(ce32); 307 uint32_t defaultCE32 = CollationData::readCE32(p); // Default if no suffix match. 308 if(!forward) { 309 // Backward contractions are handled by previousCEUnsafe(). 310 // c has contractions but they were not found. 311 ce32 = defaultCE32; 312 break; 313 } 314 UChar32 nextCp; 315 if(skipped == NULL && numCpFwd < 0) { 316 // Some portion of nextCE32FromContraction() pulled out here as an ASCII fast path, 317 // avoiding the function call and the nextSkippedCodePoint() overhead. 318 nextCp = nextCodePoint(errorCode); 319 if(nextCp < 0) { 320 // No more text. 321 ce32 = defaultCE32; 322 break; 323 } else if((ce32 & Collation::CONTRACT_NEXT_CCC) != 0 && 324 !CollationFCD::mayHaveLccc(nextCp)) { 325 // All contraction suffixes start with characters with lccc!=0 326 // but the next code point has lccc==0. 327 backwardNumCodePoints(1, errorCode); 328 ce32 = defaultCE32; 329 break; 330 } 331 } else { 332 nextCp = nextSkippedCodePoint(errorCode); 333 if(nextCp < 0) { 334 // No more text. 335 ce32 = defaultCE32; 336 break; 337 } else if((ce32 & Collation::CONTRACT_NEXT_CCC) != 0 && 338 !CollationFCD::mayHaveLccc(nextCp)) { 339 // All contraction suffixes start with characters with lccc!=0 340 // but the next code point has lccc==0. 341 backwardNumSkipped(1, errorCode); 342 ce32 = defaultCE32; 343 break; 344 } 345 } 346 ce32 = nextCE32FromContraction(d, ce32, p + 2, defaultCE32, nextCp, errorCode); 347 if(ce32 == Collation::NO_CE32) { 348 // CEs from a discontiguous contraction plus the skipped combining marks 349 // have been appended already. 350 return; 351 } 352 break; 353 } 354 case Collation::DIGIT_TAG: 355 if(isNumeric) { 356 appendNumericCEs(ce32, forward, errorCode); 357 return; 358 } else { 359 // Fetch the non-numeric-collation CE32 and continue. 360 ce32 = d->ce32s[Collation::indexFromCE32(ce32)]; 361 break; 362 } 363 case Collation::U0000_TAG: 364 U_ASSERT(c == 0); 365 if(forward && foundNULTerminator()) { 366 // Handle NUL-termination. (Not needed in Java.) 367 ceBuffer.append(Collation::NO_CE, errorCode); 368 return; 369 } else { 370 // Fetch the normal ce32 for U+0000 and continue. 371 ce32 = d->ce32s[0]; 372 break; 373 } 374 case Collation::HANGUL_TAG: { 375 const uint32_t *jamoCE32s = d->jamoCE32s; 376 c -= Hangul::HANGUL_BASE; 377 UChar32 t = c % Hangul::JAMO_T_COUNT; 378 c /= Hangul::JAMO_T_COUNT; 379 UChar32 v = c % Hangul::JAMO_V_COUNT; 380 c /= Hangul::JAMO_V_COUNT; 381 if((ce32 & Collation::HANGUL_NO_SPECIAL_JAMO) != 0) { 382 // None of the Jamo CE32s are isSpecialCE32(). 383 // Avoid recursive function calls and per-Jamo tests. 384 if(ceBuffer.ensureAppendCapacity(t == 0 ? 2 : 3, errorCode)) { 385 ceBuffer.set(ceBuffer.length, Collation::ceFromCE32(jamoCE32s[c])); 386 ceBuffer.set(ceBuffer.length + 1, Collation::ceFromCE32(jamoCE32s[19 + v])); 387 ceBuffer.length += 2; 388 if(t != 0) { 389 ceBuffer.appendUnsafe(Collation::ceFromCE32(jamoCE32s[39 + t])); 390 } 391 } 392 return; 393 } else { 394 // We should not need to compute each Jamo code point. 395 // In particular, there should be no offset or implicit ce32. 396 appendCEsFromCE32(d, U_SENTINEL, jamoCE32s[c], forward, errorCode); 397 appendCEsFromCE32(d, U_SENTINEL, jamoCE32s[19 + v], forward, errorCode); 398 if(t == 0) { return; } 399 // offset 39 = 19 + 21 - 1: 400 // 19 = JAMO_L_COUNT 401 // 21 = JAMO_T_COUNT 402 // -1 = omit t==0 403 ce32 = jamoCE32s[39 + t]; 404 c = U_SENTINEL; 405 break; 406 } 407 } 408 case Collation::LEAD_SURROGATE_TAG: { 409 U_ASSERT(forward); // Backward iteration should never see lead surrogate code _unit_ data. 410 U_ASSERT(U16_IS_LEAD(c)); 411 UChar trail; 412 if(U16_IS_TRAIL(trail = handleGetTrailSurrogate())) { 413 c = U16_GET_SUPPLEMENTARY(c, trail); 414 ce32 &= Collation::LEAD_TYPE_MASK; 415 if(ce32 == Collation::LEAD_ALL_UNASSIGNED) { 416 ce32 = Collation::UNASSIGNED_CE32; // unassigned-implicit 417 } else if(ce32 == Collation::LEAD_ALL_FALLBACK || 418 (ce32 = d->getCE32FromSupplementary(c)) == Collation::FALLBACK_CE32) { 419 // fall back to the base data 420 d = d->base; 421 ce32 = d->getCE32FromSupplementary(c); 422 } 423 } else { 424 // c is an unpaired surrogate. 425 ce32 = Collation::UNASSIGNED_CE32; 426 } 427 break; 428 } 429 case Collation::OFFSET_TAG: 430 U_ASSERT(c >= 0); 431 ceBuffer.append(d->getCEFromOffsetCE32(c, ce32), errorCode); 432 return; 433 case Collation::IMPLICIT_TAG: 434 U_ASSERT(c >= 0); 435 if(U_IS_SURROGATE(c) && forbidSurrogateCodePoints()) { 436 ce32 = Collation::FFFD_CE32; 437 break; 438 } else { 439 ceBuffer.append(Collation::unassignedCEFromCodePoint(c), errorCode); 440 return; 441 } 442 } 443 } 444 ceBuffer.append(Collation::ceFromSimpleCE32(ce32), errorCode); 445 } 446 447 uint32_t 448 CollationIterator::getCE32FromPrefix(const CollationData *d, uint32_t ce32, 449 UErrorCode &errorCode) { 450 const UChar *p = d->contexts + Collation::indexFromCE32(ce32); 451 ce32 = CollationData::readCE32(p); // Default if no prefix match. 452 p += 2; 453 // Number of code points read before the original code point. 454 int32_t lookBehind = 0; 455 UCharsTrie prefixes(p); 456 for(;;) { 457 UChar32 c = previousCodePoint(errorCode); 458 if(c < 0) { break; } 459 ++lookBehind; 460 UStringTrieResult match = prefixes.nextForCodePoint(c); 461 if(USTRINGTRIE_HAS_VALUE(match)) { 462 ce32 = (uint32_t)prefixes.getValue(); 463 } 464 if(!USTRINGTRIE_HAS_NEXT(match)) { break; } 465 } 466 forwardNumCodePoints(lookBehind, errorCode); 467 return ce32; 468 } 469 470 UChar32 471 CollationIterator::nextSkippedCodePoint(UErrorCode &errorCode) { 472 if(skipped != NULL && skipped->hasNext()) { return skipped->next(); } 473 if(numCpFwd == 0) { return U_SENTINEL; } 474 UChar32 c = nextCodePoint(errorCode); 475 if(skipped != NULL && !skipped->isEmpty() && c >= 0) { skipped->incBeyond(); } 476 if(numCpFwd > 0 && c >= 0) { --numCpFwd; } 477 return c; 478 } 479 480 void 481 CollationIterator::backwardNumSkipped(int32_t n, UErrorCode &errorCode) { 482 if(skipped != NULL && !skipped->isEmpty()) { 483 n = skipped->backwardNumCodePoints(n); 484 } 485 backwardNumCodePoints(n, errorCode); 486 if(numCpFwd >= 0) { numCpFwd += n; } 487 } 488 489 uint32_t 490 CollationIterator::nextCE32FromContraction(const CollationData *d, uint32_t contractionCE32, 491 const UChar *p, uint32_t ce32, UChar32 c, 492 UErrorCode &errorCode) { 493 // c: next code point after the original one 494 495 // Number of code points read beyond the original code point. 496 // Needed for discontiguous contraction matching. 497 int32_t lookAhead = 1; 498 // Number of code points read since the last match (initially only c). 499 int32_t sinceMatch = 1; 500 // Normally we only need a contiguous match, 501 // and therefore need not remember the suffixes state from before a mismatch for retrying. 502 // If we are already processing skipped combining marks, then we do track the state. 503 UCharsTrie suffixes(p); 504 if(skipped != NULL && !skipped->isEmpty()) { skipped->saveTrieState(suffixes); } 505 UStringTrieResult match = suffixes.firstForCodePoint(c); 506 for(;;) { 507 UChar32 nextCp; 508 if(USTRINGTRIE_HAS_VALUE(match)) { 509 ce32 = (uint32_t)suffixes.getValue(); 510 if(!USTRINGTRIE_HAS_NEXT(match) || (c = nextSkippedCodePoint(errorCode)) < 0) { 511 return ce32; 512 } 513 if(skipped != NULL && !skipped->isEmpty()) { skipped->saveTrieState(suffixes); } 514 sinceMatch = 1; 515 } else if(match == USTRINGTRIE_NO_MATCH || (nextCp = nextSkippedCodePoint(errorCode)) < 0) { 516 // No match for c, or partial match (USTRINGTRIE_NO_VALUE) and no further text. 517 // Back up if necessary, and try a discontiguous contraction. 518 if((contractionCE32 & Collation::CONTRACT_TRAILING_CCC) != 0 && 519 // Discontiguous contraction matching extends an existing match. 520 // If there is no match yet, then there is nothing to do. 521 ((contractionCE32 & Collation::CONTRACT_SINGLE_CP_NO_MATCH) == 0 || 522 sinceMatch < lookAhead)) { 523 // The last character of at least one suffix has lccc!=0, 524 // allowing for discontiguous contractions. 525 // UCA S2.1.1 only processes non-starters immediately following 526 // "a match in the table" (sinceMatch=1). 527 if(sinceMatch > 1) { 528 // Return to the state after the last match. 529 // (Return to sinceMatch=0 and re-fetch the first partially-matched character.) 530 backwardNumSkipped(sinceMatch, errorCode); 531 c = nextSkippedCodePoint(errorCode); 532 lookAhead -= sinceMatch - 1; 533 sinceMatch = 1; 534 } 535 if(d->getFCD16(c) > 0xff) { 536 return nextCE32FromDiscontiguousContraction( 537 d, suffixes, ce32, lookAhead, c, errorCode); 538 } 539 } 540 break; 541 } else { 542 // Continue after partial match (USTRINGTRIE_NO_VALUE) for c. 543 // It does not have a result value, therefore it is not itself "a match in the table". 544 // If a partially-matched c has ccc!=0 then 545 // it might be skipped in discontiguous contraction. 546 c = nextCp; 547 ++sinceMatch; 548 } 549 ++lookAhead; 550 match = suffixes.nextForCodePoint(c); 551 } 552 backwardNumSkipped(sinceMatch, errorCode); 553 return ce32; 554 } 555 556 uint32_t 557 CollationIterator::nextCE32FromDiscontiguousContraction( 558 const CollationData *d, UCharsTrie &suffixes, uint32_t ce32, 559 int32_t lookAhead, UChar32 c, 560 UErrorCode &errorCode) { 561 if(U_FAILURE(errorCode)) { return 0; } 562 563 // UCA section 3.3.2 Contractions: 564 // Contractions that end with non-starter characters 565 // are known as discontiguous contractions. 566 // ... discontiguous contractions must be detected in input text 567 // whenever the final sequence of non-starter characters could be rearranged 568 // so as to make a contiguous matching sequence that is canonically equivalent. 569 570 // UCA: http://www.unicode.org/reports/tr10/#S2.1 571 // S2.1 Find the longest initial substring S at each point that has a match in the table. 572 // S2.1.1 If there are any non-starters following S, process each non-starter C. 573 // S2.1.2 If C is not blocked from S, find if S + C has a match in the table. 574 // Note: A non-starter in a string is called blocked 575 // if there is another non-starter of the same canonical combining class or zero 576 // between it and the last character of canonical combining class 0. 577 // S2.1.3 If there is a match, replace S by S + C, and remove C. 578 579 // First: Is a discontiguous contraction even possible? 580 uint16_t fcd16 = d->getFCD16(c); 581 U_ASSERT(fcd16 > 0xff); // The caller checked this already, as a shortcut. 582 UChar32 nextCp = nextSkippedCodePoint(errorCode); 583 if(nextCp < 0) { 584 // No further text. 585 backwardNumSkipped(1, errorCode); 586 return ce32; 587 } 588 ++lookAhead; 589 uint8_t prevCC = (uint8_t)fcd16; 590 fcd16 = d->getFCD16(nextCp); 591 if(fcd16 <= 0xff) { 592 // The next code point after c is a starter (S2.1.1 "process each non-starter"). 593 backwardNumSkipped(2, errorCode); 594 return ce32; 595 } 596 597 // We have read and matched (lookAhead-2) code points, 598 // read non-matching c and peeked ahead at nextCp. 599 // Return to the state before the mismatch and continue matching with nextCp. 600 if(skipped == NULL || skipped->isEmpty()) { 601 if(skipped == NULL) { 602 skipped = new SkippedState(); 603 if(skipped == NULL) { 604 errorCode = U_MEMORY_ALLOCATION_ERROR; 605 return 0; 606 } 607 } 608 suffixes.reset(); 609 if(lookAhead > 2) { 610 // Replay the partial match so far. 611 backwardNumCodePoints(lookAhead, errorCode); 612 suffixes.firstForCodePoint(nextCodePoint(errorCode)); 613 for(int32_t i = 3; i < lookAhead; ++i) { 614 suffixes.nextForCodePoint(nextCodePoint(errorCode)); 615 } 616 // Skip c (which did not match) and nextCp (which we will try now). 617 forwardNumCodePoints(2, errorCode); 618 } 619 skipped->saveTrieState(suffixes); 620 } else { 621 // Reset to the trie state before the failed match of c. 622 skipped->resetToTrieState(suffixes); 623 } 624 625 skipped->setFirstSkipped(c); 626 // Number of code points read since the last match (at this point: c and nextCp). 627 int32_t sinceMatch = 2; 628 c = nextCp; 629 for(;;) { 630 UStringTrieResult match; 631 // "If C is not blocked from S, find if S + C has a match in the table." (S2.1.2) 632 if(prevCC < (fcd16 >> 8) && USTRINGTRIE_HAS_VALUE(match = suffixes.nextForCodePoint(c))) { 633 // "If there is a match, replace S by S + C, and remove C." (S2.1.3) 634 // Keep prevCC unchanged. 635 ce32 = (uint32_t)suffixes.getValue(); 636 sinceMatch = 0; 637 skipped->recordMatch(); 638 if(!USTRINGTRIE_HAS_NEXT(match)) { break; } 639 skipped->saveTrieState(suffixes); 640 } else { 641 // No match for "S + C", skip C. 642 skipped->skip(c); 643 skipped->resetToTrieState(suffixes); 644 prevCC = (uint8_t)fcd16; 645 } 646 if((c = nextSkippedCodePoint(errorCode)) < 0) { break; } 647 ++sinceMatch; 648 fcd16 = d->getFCD16(c); 649 if(fcd16 <= 0xff) { 650 // The next code point after c is a starter (S2.1.1 "process each non-starter"). 651 break; 652 } 653 } 654 backwardNumSkipped(sinceMatch, errorCode); 655 UBool isTopDiscontiguous = skipped->isEmpty(); 656 skipped->replaceMatch(); 657 if(isTopDiscontiguous && !skipped->isEmpty()) { 658 // We did get a match after skipping one or more combining marks, 659 // and we are not in a recursive discontiguous contraction. 660 // Append CEs from the contraction ce32 661 // and then from the combining marks that we skipped before the match. 662 c = U_SENTINEL; 663 for(;;) { 664 appendCEsFromCE32(d, c, ce32, TRUE, errorCode); 665 // Fetch CE32s for skipped combining marks from the normal data, with fallback, 666 // rather than from the CollationData where we found the contraction. 667 if(!skipped->hasNext()) { break; } 668 c = skipped->next(); 669 ce32 = getDataCE32(c); 670 if(ce32 == Collation::FALLBACK_CE32) { 671 d = data->base; 672 ce32 = d->getCE32(c); 673 } else { 674 d = data; 675 } 676 // Note: A nested discontiguous-contraction match 677 // replaces consumed combining marks with newly skipped ones 678 // and resets the reading position to the beginning. 679 } 680 skipped->clear(); 681 ce32 = Collation::NO_CE32; // Signal to the caller that the result is in the ceBuffer. 682 } 683 return ce32; 684 } 685 686 void 687 CollationIterator::appendNumericCEs(uint32_t ce32, UBool forward, UErrorCode &errorCode) { 688 // Collect digits. 689 CharString digits; 690 if(forward) { 691 for(;;) { 692 char digit = Collation::digitFromCE32(ce32); 693 digits.append(digit, errorCode); 694 if(numCpFwd == 0) { break; } 695 UChar32 c = nextCodePoint(errorCode); 696 if(c < 0) { break; } 697 ce32 = data->getCE32(c); 698 if(ce32 == Collation::FALLBACK_CE32) { 699 ce32 = data->base->getCE32(c); 700 } 701 if(!Collation::hasCE32Tag(ce32, Collation::DIGIT_TAG)) { 702 backwardNumCodePoints(1, errorCode); 703 break; 704 } 705 if(numCpFwd > 0) { --numCpFwd; } 706 } 707 } else { 708 for(;;) { 709 char digit = Collation::digitFromCE32(ce32); 710 digits.append(digit, errorCode); 711 UChar32 c = previousCodePoint(errorCode); 712 if(c < 0) { break; } 713 ce32 = data->getCE32(c); 714 if(ce32 == Collation::FALLBACK_CE32) { 715 ce32 = data->base->getCE32(c); 716 } 717 if(!Collation::hasCE32Tag(ce32, Collation::DIGIT_TAG)) { 718 forwardNumCodePoints(1, errorCode); 719 break; 720 } 721 } 722 // Reverse the digit string. 723 char *p = digits.data(); 724 char *q = p + digits.length() - 1; 725 while(p < q) { 726 char digit = *p; 727 *p++ = *q; 728 *q-- = digit; 729 } 730 } 731 if(U_FAILURE(errorCode)) { return; } 732 int32_t pos = 0; 733 do { 734 // Skip leading zeros. 735 while(pos < (digits.length() - 1) && digits[pos] == 0) { ++pos; } 736 // Write a sequence of CEs for at most 254 digits at a time. 737 int32_t segmentLength = digits.length() - pos; 738 if(segmentLength > 254) { segmentLength = 254; } 739 appendNumericSegmentCEs(digits.data() + pos, segmentLength, errorCode); 740 pos += segmentLength; 741 } while(U_SUCCESS(errorCode) && pos < digits.length()); 742 } 743 744 void 745 CollationIterator::appendNumericSegmentCEs(const char *digits, int32_t length, UErrorCode &errorCode) { 746 U_ASSERT(1 <= length && length <= 254); 747 U_ASSERT(length == 1 || digits[0] != 0); 748 uint32_t numericPrimary = data->numericPrimary; 749 // Note: We use primary byte values 2..255: digits are not compressible. 750 if(length <= 7) { 751 // Very dense encoding for small numbers. 752 int32_t value = digits[0]; 753 for(int32_t i = 1; i < length; ++i) { 754 value = value * 10 + digits[i]; 755 } 756 // Primary weight second byte values: 757 // 74 byte values 2.. 75 for small numbers in two-byte primary weights. 758 // 40 byte values 76..115 for medium numbers in three-byte primary weights. 759 // 16 byte values 116..131 for large numbers in four-byte primary weights. 760 // 124 byte values 132..255 for very large numbers with 4..127 digit pairs. 761 int32_t firstByte = 2; 762 int32_t numBytes = 74; 763 if(value < numBytes) { 764 // Two-byte primary for 0..73, good for day & month numbers etc. 765 uint32_t primary = numericPrimary | ((firstByte + value) << 16); 766 ceBuffer.append(Collation::makeCE(primary), errorCode); 767 return; 768 } 769 value -= numBytes; 770 firstByte += numBytes; 771 numBytes = 40; 772 if(value < numBytes * 254) { 773 // Three-byte primary for 74..10233=74+40*254-1, good for year numbers and more. 774 uint32_t primary = numericPrimary | 775 ((firstByte + value / 254) << 16) | ((2 + value % 254) << 8); 776 ceBuffer.append(Collation::makeCE(primary), errorCode); 777 return; 778 } 779 value -= numBytes * 254; 780 firstByte += numBytes; 781 numBytes = 16; 782 if(value < numBytes * 254 * 254) { 783 // Four-byte primary for 10234..1042489=10234+16*254*254-1. 784 uint32_t primary = numericPrimary | (2 + value % 254); 785 value /= 254; 786 primary |= (2 + value % 254) << 8; 787 value /= 254; 788 primary |= (firstByte + value % 254) << 16; 789 ceBuffer.append(Collation::makeCE(primary), errorCode); 790 return; 791 } 792 // original value > 1042489 793 } 794 U_ASSERT(length >= 7); 795 796 // The second primary byte value 132..255 indicates the number of digit pairs (4..127), 797 // then we generate primary bytes with those pairs. 798 // Omit trailing 00 pairs. 799 // Decrement the value for the last pair. 800 801 // Set the exponent. 4 pairs->132, 5 pairs->133, ..., 127 pairs->255. 802 int32_t numPairs = (length + 1) / 2; 803 uint32_t primary = numericPrimary | ((132 - 4 + numPairs) << 16); 804 // Find the length without trailing 00 pairs. 805 while(digits[length - 1] == 0 && digits[length - 2] == 0) { 806 length -= 2; 807 } 808 // Read the first pair. 809 uint32_t pair; 810 int32_t pos; 811 if(length & 1) { 812 // Only "half a pair" if we have an odd number of digits. 813 pair = digits[0]; 814 pos = 1; 815 } else { 816 pair = digits[0] * 10 + digits[1]; 817 pos = 2; 818 } 819 pair = 11 + 2 * pair; 820 // Add the pairs of digits between pos and length. 821 int32_t shift = 8; 822 while(pos < length) { 823 if(shift == 0) { 824 // Every three pairs/bytes we need to store a 4-byte-primary CE 825 // and start with a new CE with the '0' primary lead byte. 826 primary |= pair; 827 ceBuffer.append(Collation::makeCE(primary), errorCode); 828 primary = numericPrimary; 829 shift = 16; 830 } else { 831 primary |= pair << shift; 832 shift -= 8; 833 } 834 pair = 11 + 2 * (digits[pos] * 10 + digits[pos + 1]); 835 pos += 2; 836 } 837 primary |= (pair - 1) << shift; 838 ceBuffer.append(Collation::makeCE(primary), errorCode); 839 } 840 841 int64_t 842 CollationIterator::previousCE(UVector32 &offsets, UErrorCode &errorCode) { 843 if(ceBuffer.length > 0) { 844 // Return the previous buffered CE. 845 return ceBuffer.get(--ceBuffer.length); 846 } 847 offsets.removeAllElements(); 848 int32_t limitOffset = getOffset(); 849 UChar32 c = previousCodePoint(errorCode); 850 if(c < 0) { return Collation::NO_CE; } 851 if(data->isUnsafeBackward(c, isNumeric)) { 852 return previousCEUnsafe(c, offsets, errorCode); 853 } 854 // Simple, safe-backwards iteration: 855 // Get a CE going backwards, handle prefixes but no contractions. 856 uint32_t ce32 = data->getCE32(c); 857 const CollationData *d; 858 if(ce32 == Collation::FALLBACK_CE32) { 859 d = data->base; 860 ce32 = d->getCE32(c); 861 } else { 862 d = data; 863 } 864 if(Collation::isSimpleOrLongCE32(ce32)) { 865 return Collation::ceFromCE32(ce32); 866 } 867 appendCEsFromCE32(d, c, ce32, FALSE, errorCode); 868 if(U_SUCCESS(errorCode)) { 869 if(ceBuffer.length > 1) { 870 offsets.addElement(getOffset(), errorCode); 871 // For an expansion, the offset of each non-initial CE is the limit offset, 872 // consistent with forward iteration. 873 while(offsets.size() <= ceBuffer.length) { 874 offsets.addElement(limitOffset, errorCode); 875 }; 876 } 877 return ceBuffer.get(--ceBuffer.length); 878 } else { 879 return Collation::NO_CE_PRIMARY; 880 } 881 } 882 883 int64_t 884 CollationIterator::previousCEUnsafe(UChar32 c, UVector32 &offsets, UErrorCode &errorCode) { 885 // We just move through the input counting safe and unsafe code points 886 // without collecting the unsafe-backward substring into a buffer and 887 // switching to it. 888 // This is to keep the logic simple. Otherwise we would have to handle 889 // prefix matching going before the backward buffer, switching 890 // to iteration and back, etc. 891 // In the most important case of iterating over a normal string, 892 // reading from the string itself is already maximally fast. 893 // The only drawback there is that after getting the CEs we always 894 // skip backward to the safe character rather than switching out 895 // of a backwardBuffer. 896 // But this should not be the common case for previousCE(), 897 // and correctness and maintainability are more important than 898 // complex optimizations. 899 // Find the first safe character before c. 900 int32_t numBackward = 1; 901 while((c = previousCodePoint(errorCode)) >= 0) { 902 ++numBackward; 903 if(!data->isUnsafeBackward(c, isNumeric)) { 904 break; 905 } 906 } 907 // Set the forward iteration limit. 908 // Note: This counts code points. 909 // We cannot enforce a limit in the middle of a surrogate pair or similar. 910 numCpFwd = numBackward; 911 // Reset the forward iterator. 912 cesIndex = 0; 913 U_ASSERT(ceBuffer.length == 0); 914 // Go forward and collect the CEs. 915 int32_t offset = getOffset(); 916 while(numCpFwd > 0) { 917 // nextCE() normally reads one code point. 918 // Contraction matching and digit specials read more and check numCpFwd. 919 --numCpFwd; 920 // Append one or more CEs to the ceBuffer. 921 (void)nextCE(errorCode); 922 U_ASSERT(U_FAILURE(errorCode) || ceBuffer.get(ceBuffer.length - 1) != Collation::NO_CE); 923 // No need to loop for getting each expansion CE from nextCE(). 924 cesIndex = ceBuffer.length; 925 // However, we need to write an offset for each CE. 926 // This is for CollationElementIterator::getOffset() to return 927 // intermediate offsets from the unsafe-backwards segment. 928 U_ASSERT(offsets.size() < ceBuffer.length); 929 offsets.addElement(offset, errorCode); 930 // For an expansion, the offset of each non-initial CE is the limit offset, 931 // consistent with forward iteration. 932 offset = getOffset(); 933 while(offsets.size() < ceBuffer.length) { 934 offsets.addElement(offset, errorCode); 935 }; 936 } 937 U_ASSERT(offsets.size() == ceBuffer.length); 938 // End offset corresponding to just after the unsafe-backwards segment. 939 offsets.addElement(offset, errorCode); 940 // Reset the forward iteration limit 941 // and move backward to before the segment for which we fetched CEs. 942 numCpFwd = -1; 943 backwardNumCodePoints(numBackward, errorCode); 944 // Use the collected CEs and return the last one. 945 cesIndex = 0; // Avoid cesIndex > ceBuffer.length when that gets decremented. 946 if(U_SUCCESS(errorCode)) { 947 return ceBuffer.get(--ceBuffer.length); 948 } else { 949 return Collation::NO_CE_PRIMARY; 950 } 951 } 952 953 U_NAMESPACE_END 954 955 #endif // !UCONFIG_NO_COLLATION 956
