icuSources/i18n/utf8collationiterator.cpp

   1 // © 2016 and later: Unicode, Inc. and others.
   2 // License & terms of use: http://www.unicode.org/copyright.html
   3 /*
   4 *******************************************************************************
   5 * Copyright (C) 2012-2014, International Business Machines
   6 * Corporation and others.  All Rights Reserved.
   7 *******************************************************************************
   8 * utf8collationiterator.cpp
   9 *
  10 * created on: 2012nov12 (from utf16collationiterator.cpp & uitercollationiterator.cpp)
  11 * created by: Markus W. Scherer
  12 */
  13
  14 #include "unicode/utypes.h"
  15
  16 #if !UCONFIG_NO_COLLATION
  17
  18 #include "unicode/utf8.h"
  19 #include "charstr.h"
  20 #include "cmemory.h"
  21 #include "collation.h"
  22 #include "collationdata.h"
  23 #include "collationfcd.h"
  24 #include "collationiterator.h"
  25 #include "normalizer2impl.h"
  26 #include "uassert.h"
  27 #include "utf8collationiterator.h"
  28
  29 U_NAMESPACE_BEGIN
  30
  31 UTF8CollationIterator::~UTF8CollationIterator() {}
  32
  33 void
  34 UTF8CollationIterator::resetToOffset(int32_t newOffset) {
  35     reset();
  36     pos = newOffset;
  37 }
  38
  39 int32_t
  40 UTF8CollationIterator::getOffset() const {
  41     return pos;
  42 }
  43
  44 uint32_t
  45 UTF8CollationIterator::handleNextCE32(UChar32 &c, UErrorCode & /*errorCode*/) {
  46     if(pos == length) {
  47         c = U_SENTINEL;
  48         return Collation::FALLBACK_CE32;
  49     }
  50     // Optimized combination of U8_NEXT_OR_FFFD() and UTRIE2_U8_NEXT32().
  51     c = u8[pos++];
  52     if(U8_IS_SINGLE(c)) {
  53         // ASCII 00..7F
  54         return trie->data32[c];
  55     }
  56     uint8_t t1, t2;
  57     if(0xe0 <= c && c < 0xf0 &&
  58             ((pos + 1) < length || length < 0) &&
  59             U8_IS_VALID_LEAD3_AND_T1(c, t1 = u8[pos]) &&
  60             (t2 = (u8[pos + 1] - 0x80)) <= 0x3f) {
  61         // U+0800..U+FFFF except surrogates
  62         c = (((c & 0xf) << 12) | ((t1 & 0x3f) << 6) | t2);
  63         pos += 2;
  64         return UTRIE2_GET32_FROM_U16_SINGLE_LEAD(trie, c);
  65     } else if(c < 0xe0 && c >= 0xc2 && pos != length && (t1 = (u8[pos] - 0x80)) <= 0x3f) {
  66         // U+0080..U+07FF
  67         uint32_t ce32 = trie->data32[trie->index[(UTRIE2_UTF8_2B_INDEX_2_OFFSET - 0xc0) + c] + t1];
  68         c = ((c & 0x1f) << 6) | t1;
  69         ++pos;
  70         return ce32;
  71     } else {
  72         // Function call for supplementary code points and error cases.
  73         // Illegal byte sequences yield U+FFFD.
  74         c = utf8_nextCharSafeBody(u8, &pos, length, c, -3);
  75         return data->getCE32(c);
  76     }
  77 }
  78
  79 UBool
  80 UTF8CollationIterator::foundNULTerminator() {
  81     if(length < 0) {
  82         length = --pos;
  83         return TRUE;
  84     } else {
  85         return FALSE;
  86     }
  87 }
  88
  89 UBool
  90 UTF8CollationIterator::forbidSurrogateCodePoints() const {
  91     return TRUE;
  92 }
  93
  94 UChar32
  95 UTF8CollationIterator::nextCodePoint(UErrorCode & /*errorCode*/) {
  96     if(pos == length) {
  97         return U_SENTINEL;
  98     }
  99     if(u8[pos] == 0 && length < 0) {
 100         length = pos;
 101         return U_SENTINEL;
 102     }
 103     UChar32 c;
 104     U8_NEXT_OR_FFFD(u8, pos, length, c);
 105     return c;
 106 }
 107
 108 UChar32
 109 UTF8CollationIterator::previousCodePoint(UErrorCode & /*errorCode*/) {
 110     if(pos == 0) {
 111         return U_SENTINEL;
 112     }
 113     UChar32 c;
 114     U8_PREV_OR_FFFD(u8, 0, pos, c);
 115     return c;
 116 }
 117
 118 void
 119 UTF8CollationIterator::forwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
 120     U8_FWD_N(u8, pos, length, num);
 121 }
 122
 123 void
 124 UTF8CollationIterator::backwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
 125     U8_BACK_N(u8, 0, pos, num);
 126 }
 127
 128 // FCDUTF8CollationIterator ------------------------------------------------ ***
 129
 130 FCDUTF8CollationIterator::~FCDUTF8CollationIterator() {}
 131
 132 void
 133 FCDUTF8CollationIterator::resetToOffset(int32_t newOffset) {
 134     reset();
 135     start = pos = newOffset;
 136     state = CHECK_FWD;
 137 }
 138
 139 int32_t
 140 FCDUTF8CollationIterator::getOffset() const {
 141     if(state != IN_NORMALIZED) {
 142         return pos;
 143     } else if(pos == 0) {
 144         return start;
 145     } else {
 146         return limit;
 147     }
 148 }
 149
 150 uint32_t
 151 FCDUTF8CollationIterator::handleNextCE32(UChar32 &c, UErrorCode &errorCode) {
 152     for(;;) {
 153         if(state == CHECK_FWD) {
 154             // Combination of UTF8CollationIterator::handleNextCE32() with FCD check fastpath.
 155             if(pos == length) {
 156                 c = U_SENTINEL;
 157                 return Collation::FALLBACK_CE32;
 158             }
 159             c = u8[pos++];
 160             if(U8_IS_SINGLE(c)) {
 161                 // ASCII 00..7F
 162                 return trie->data32[c];
 163             }
 164             uint8_t t1, t2;
 165             if(0xe0 <= c && c < 0xf0 &&
 166                     ((pos + 1) < length || length < 0) &&
 167                     U8_IS_VALID_LEAD3_AND_T1(c, t1 = u8[pos]) &&
 168                     (t2 = (u8[pos + 1] - 0x80)) <= 0x3f) {
 169                 // U+0800..U+FFFF except surrogates
 170                 c = (((c & 0xf) << 12) | ((t1 & 0x3f) << 6) | t2);
 171                 pos += 2;
 172                 if(CollationFCD::hasTccc(c) &&
 173                         (CollationFCD::maybeTibetanCompositeVowel(c) ||
 174                             (pos != length && nextHasLccc()))) {
 175                     pos -= 3;
 176                 } else {
 177                     break;  // return CE32(BMP)
 178                 }
 179             } else if(c < 0xe0 && c >= 0xc2 && pos != length && (t1 = (u8[pos] - 0x80)) <= 0x3f) {
 180                 // U+0080..U+07FF
 181                 uint32_t ce32 = trie->data32[trie->index[(UTRIE2_UTF8_2B_INDEX_2_OFFSET - 0xc0) + c] + t1];
 182                 c = ((c & 0x1f) << 6) | t1;
 183                 ++pos;
 184                 if(CollationFCD::hasTccc(c) && pos != length && nextHasLccc()) {
 185                     pos -= 2;
 186                 } else {
 187                     return ce32;
 188                 }
 189             } else {
 190                 // Function call for supplementary code points and error cases.
 191                 // Illegal byte sequences yield U+FFFD.
 192                 c = utf8_nextCharSafeBody(u8, &pos, length, c, -3);
 193                 if(c == 0xfffd) {
 194                     return Collation::FFFD_CE32;
 195                 } else {
 196                     U_ASSERT(c > 0xffff);
 197                     if(CollationFCD::hasTccc(U16_LEAD(c)) && pos != length && nextHasLccc()) {
 198                         pos -= 4;
 199                     } else {
 200                         return data->getCE32FromSupplementary(c);
 201                     }
 202                 }
 203             }
 204             if(!nextSegment(errorCode)) {
 205                 c = U_SENTINEL;
 206                 return Collation::FALLBACK_CE32;
 207             }
 208             continue;
 209         } else if(state == IN_FCD_SEGMENT && pos != limit) {
 210             return UTF8CollationIterator::handleNextCE32(c, errorCode);
 211         } else if(state == IN_NORMALIZED && pos != normalized.length()) {
 212             c = normalized[pos++];
 213             break;
 214         } else {
 215             switchToForward();
 216         }
 217     }
 218     return UTRIE2_GET32_FROM_U16_SINGLE_LEAD(trie, c);
 219 }
 220
 221 UBool
 222 FCDUTF8CollationIterator::nextHasLccc() const {
 223     U_ASSERT(state == CHECK_FWD && pos != length);
 224     // The lowest code point with ccc!=0 is U+0300 which is CC 80 in UTF-8.
 225     // CJK U+4000..U+DFFF except U+Axxx are also FCD-inert. (Lead bytes E4..ED except EA.)
 226     UChar32 c = u8[pos];
 227     if(c < 0xcc || (0xe4 <= c && c <= 0xed && c != 0xea)) { return FALSE; }
 228     int32_t i = pos;
 229     U8_NEXT_OR_FFFD(u8, i, length, c);
 230     if(c > 0xffff) { c = U16_LEAD(c); }
 231     return CollationFCD::hasLccc(c);
 232 }
 233
 234 UBool
 235 FCDUTF8CollationIterator::previousHasTccc() const {
 236     U_ASSERT(state == CHECK_BWD && pos != 0);
 237     UChar32 c = u8[pos - 1];
 238     if(U8_IS_SINGLE(c)) { return FALSE; }
 239     int32_t i = pos;
 240     U8_PREV_OR_FFFD(u8, 0, i, c);
 241     if(c > 0xffff) { c = U16_LEAD(c); }
 242     return CollationFCD::hasTccc(c);
 243 }
 244
 245 UChar
 246 FCDUTF8CollationIterator::handleGetTrailSurrogate() {
 247     if(state != IN_NORMALIZED) { return 0; }
 248     U_ASSERT(pos < normalized.length());
 249     UChar trail;
 250     if(U16_IS_TRAIL(trail = normalized[pos])) { ++pos; }
 251     return trail;
 252 }
 253
 254 UBool
 255 FCDUTF8CollationIterator::foundNULTerminator() {
 256     if(state == CHECK_FWD && length < 0) {
 257         length = --pos;
 258         return TRUE;
 259     } else {
 260         return FALSE;
 261     }
 262 }
 263
 264 UChar32
 265 FCDUTF8CollationIterator::nextCodePoint(UErrorCode &errorCode) {
 266     UChar32 c;
 267     for(;;) {
 268         if(state == CHECK_FWD) {
 269             if(pos == length || ((c = u8[pos]) == 0 && length < 0)) {
 270                 return U_SENTINEL;
 271             }
 272             if(U8_IS_SINGLE(c)) {
 273                 ++pos;
 274                 return c;
 275             }
 276             U8_NEXT_OR_FFFD(u8, pos, length, c);
 277             if(CollationFCD::hasTccc(c <= 0xffff ? c : U16_LEAD(c)) &&
 278                     (CollationFCD::maybeTibetanCompositeVowel(c) ||
 279                         (pos != length && nextHasLccc()))) {
 280                 // c is not FCD-inert, therefore it is not U+FFFD and it has a valid byte sequence
 281                 // and we can use U8_LENGTH() rather than a previous-position variable.
 282                 pos -= U8_LENGTH(c);
 283                 if(!nextSegment(errorCode)) {
 284                     return U_SENTINEL;
 285                 }
 286                 continue;
 287             }
 288             return c;
 289         } else if(state == IN_FCD_SEGMENT && pos != limit) {
 290             U8_NEXT_OR_FFFD(u8, pos, length, c);
 291             return c;
 292         } else if(state == IN_NORMALIZED && pos != normalized.length()) {
 293             c = normalized.char32At(pos);
 294             pos += U16_LENGTH(c);
 295             return c;
 296         } else {
 297             switchToForward();
 298         }
 299     }
 300 }
 301
 302 UChar32
 303 FCDUTF8CollationIterator::previousCodePoint(UErrorCode &errorCode) {
 304     UChar32 c;
 305     for(;;) {
 306         if(state == CHECK_BWD) {
 307             if(pos == 0) {
 308                 return U_SENTINEL;
 309             }
 310             if(U8_IS_SINGLE(c = u8[pos - 1])) {
 311                 --pos;
 312                 return c;
 313             }
 314             U8_PREV_OR_FFFD(u8, 0, pos, c);
 315             if(CollationFCD::hasLccc(c <= 0xffff ? c : U16_LEAD(c)) &&
 316                     (CollationFCD::maybeTibetanCompositeVowel(c) ||
 317                         (pos != 0 && previousHasTccc()))) {
 318                 // c is not FCD-inert, therefore it is not U+FFFD and it has a valid byte sequence
 319                 // and we can use U8_LENGTH() rather than a previous-position variable.
 320                 pos += U8_LENGTH(c);
 321                 if(!previousSegment(errorCode)) {
 322                     return U_SENTINEL;
 323                 }
 324                 continue;
 325             }
 326             return c;
 327         } else if(state == IN_FCD_SEGMENT && pos != start) {
 328             U8_PREV_OR_FFFD(u8, 0, pos, c);
 329             return c;
 330         } else if(state >= IN_NORMALIZED && pos != 0) {
 331             c = normalized.char32At(pos - 1);
 332             pos -= U16_LENGTH(c);
 333             return c;
 334         } else {
 335             switchToBackward();
 336         }
 337     }
 338 }
 339
 340 void
 341 FCDUTF8CollationIterator::forwardNumCodePoints(int32_t num, UErrorCode &errorCode) {
 342     // Specify the class to avoid a virtual-function indirection.
 343     // In Java, we would declare this class final.
 344     while(num > 0 && FCDUTF8CollationIterator::nextCodePoint(errorCode) >= 0) {
 345         --num;
 346     }
 347 }
 348
 349 void
 350 FCDUTF8CollationIterator::backwardNumCodePoints(int32_t num, UErrorCode &errorCode) {
 351     // Specify the class to avoid a virtual-function indirection.
 352     // In Java, we would declare this class final.
 353     while(num > 0 && FCDUTF8CollationIterator::previousCodePoint(errorCode) >= 0) {
 354         --num;
 355     }
 356 }
 357
 358 void
 359 FCDUTF8CollationIterator::switchToForward() {
 360     U_ASSERT(state == CHECK_BWD ||
 361              (state == IN_FCD_SEGMENT && pos == limit) ||
 362              (state == IN_NORMALIZED && pos == normalized.length()));
 363     if(state == CHECK_BWD) {
 364         // Turn around from backward checking.
 365         start = pos;
 366         if(pos == limit) {
 367             state = CHECK_FWD;  // Check forward.
 368         } else {  // pos < limit
 369             state = IN_FCD_SEGMENT;  // Stay in FCD segment.
 370         }
 371     } else {
 372         // Reached the end of the FCD segment.
 373         if(state == IN_FCD_SEGMENT) {
 374             // The input text segment is FCD, extend it forward.
 375         } else {
 376             // The input text segment needed to be normalized.
 377             // Switch to checking forward from it.
 378             start = pos = limit;
 379         }
 380         state = CHECK_FWD;
 381     }
 382 }
 383
 384 UBool
 385 FCDUTF8CollationIterator::nextSegment(UErrorCode &errorCode) {
 386     if(U_FAILURE(errorCode)) { return FALSE; }
 387     U_ASSERT(state == CHECK_FWD && pos != length);
 388     // The input text [start..pos[ passes the FCD check.
 389     int32_t segmentStart = pos;
 390     // Collect the characters being checked, in case they need to be normalized.
 391     UnicodeString s;
 392     uint8_t prevCC = 0;
 393     for(;;) {
 394         // Fetch the next character and its fcd16 value.
 395         int32_t cpStart = pos;
 396         UChar32 c;
 397         U8_NEXT_OR_FFFD(u8, pos, length, c);
 398         uint16_t fcd16 = nfcImpl.getFCD16(c);
 399         uint8_t leadCC = (uint8_t)(fcd16 >> 8);
 400         if(leadCC == 0 && cpStart != segmentStart) {
 401             // FCD boundary before this character.
 402             pos = cpStart;
 403             break;
 404         }
 405         s.append(c);
 406         if(leadCC != 0 && (prevCC > leadCC || CollationFCD::isFCD16OfTibetanCompositeVowel(fcd16))) {
 407             // Fails FCD check. Find the next FCD boundary and normalize.
 408             while(pos != length) {
 409                 cpStart = pos;
 410                 U8_NEXT_OR_FFFD(u8, pos, length, c);
 411                 if(nfcImpl.getFCD16(c) <= 0xff) {
 412                     pos = cpStart;
 413                     break;
 414                 }
 415                 s.append(c);
 416             }
 417             if(!normalize(s, errorCode)) { return FALSE; }
 418             start = segmentStart;
 419             limit = pos;
 420             state = IN_NORMALIZED;
 421             pos = 0;
 422             return TRUE;
 423         }
 424         prevCC = (uint8_t)fcd16;
 425         if(pos == length || prevCC == 0) {
 426             // FCD boundary after the last character.
 427             break;
 428         }
 429     }
 430     limit = pos;
 431     pos = segmentStart;
 432     U_ASSERT(pos != limit);
 433     state = IN_FCD_SEGMENT;
 434     return TRUE;
 435 }
 436
 437 void
 438 FCDUTF8CollationIterator::switchToBackward() {
 439     U_ASSERT(state == CHECK_FWD ||
 440              (state == IN_FCD_SEGMENT && pos == start) ||
 441              (state >= IN_NORMALIZED && pos == 0));
 442     if(state == CHECK_FWD) {
 443         // Turn around from forward checking.
 444         limit = pos;
 445         if(pos == start) {
 446             state = CHECK_BWD;  // Check backward.
 447         } else {  // pos > start
 448             state = IN_FCD_SEGMENT;  // Stay in FCD segment.
 449         }
 450     } else {
 451         // Reached the start of the FCD segment.
 452         if(state == IN_FCD_SEGMENT) {
 453             // The input text segment is FCD, extend it backward.
 454         } else {
 455             // The input text segment needed to be normalized.
 456             // Switch to checking backward from it.
 457             limit = pos = start;
 458         }
 459         state = CHECK_BWD;
 460     }
 461 }
 462
 463 UBool
 464 FCDUTF8CollationIterator::previousSegment(UErrorCode &errorCode) {
 465     if(U_FAILURE(errorCode)) { return FALSE; }
 466     U_ASSERT(state == CHECK_BWD && pos != 0);
 467     // The input text [pos..limit[ passes the FCD check.
 468     int32_t segmentLimit = pos;
 469     // Collect the characters being checked, in case they need to be normalized.
 470     UnicodeString s;
 471     uint8_t nextCC = 0;
 472     for(;;) {
 473         // Fetch the previous character and its fcd16 value.
 474         int32_t cpLimit = pos;
 475         UChar32 c;
 476         U8_PREV_OR_FFFD(u8, 0, pos, c);
 477         uint16_t fcd16 = nfcImpl.getFCD16(c);
 478         uint8_t trailCC = (uint8_t)fcd16;
 479         if(trailCC == 0 && cpLimit != segmentLimit) {
 480             // FCD boundary after this character.
 481             pos = cpLimit;
 482             break;
 483         }
 484         s.append(c);
 485         if(trailCC != 0 && ((nextCC != 0 && trailCC > nextCC) ||
 486                             CollationFCD::isFCD16OfTibetanCompositeVowel(fcd16))) {
 487             // Fails FCD check. Find the previous FCD boundary and normalize.
 488             while(fcd16 > 0xff && pos != 0) {
 489                 cpLimit = pos;
 490                 U8_PREV_OR_FFFD(u8, 0, pos, c);
 491                 fcd16 = nfcImpl.getFCD16(c);
 492                 if(fcd16 == 0) {
 493                     pos = cpLimit;
 494                     break;
 495                 }
 496                 s.append(c);
 497             }
 498             s.reverse();
 499             if(!normalize(s, errorCode)) { return FALSE; }
 500             limit = segmentLimit;
 501             start = pos;
 502             state = IN_NORMALIZED;
 503             pos = normalized.length();
 504             return TRUE;
 505         }
 506         nextCC = (uint8_t)(fcd16 >> 8);
 507         if(pos == 0 || nextCC == 0) {
 508             // FCD boundary before the following character.
 509             break;
 510         }
 511     }
 512     start = pos;
 513     pos = segmentLimit;
 514     U_ASSERT(pos != start);
 515     state = IN_FCD_SEGMENT;
 516     return TRUE;
 517 }
 518
 519 UBool
 520 FCDUTF8CollationIterator::normalize(const UnicodeString &s, UErrorCode &errorCode) {
 521     // NFD without argument checking.
 522     U_ASSERT(U_SUCCESS(errorCode));
 523     nfcImpl.decompose(s, normalized, errorCode);
 524     return U_SUCCESS(errorCode);
 525 }
 526
 527 U_NAMESPACE_END
 528
 529 #endif  // !UCONFIG_NO_COLLATION