source/i18n/utf8collationiterator.cpp

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