icuSources/i18n/collationiterator.cpp

   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