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