icuSources/i18n/utf8collationiterator.cpp

   1 /*
   2 *******************************************************************************
   3 * Copyright (C) 2012-2014, International Business Machines
   4 * Corporation and others.  All Rights Reserved.
   5 *******************************************************************************
   6 * utf8collationiterator.cpp
   7 *
   8 * created on: 2012nov12 (from utf16collationiterator.cpp & uitercollationiterator.cpp)
   9 * created by: Markus W. Scherer
  10 */
  11
  12 #include "unicode/utypes.h"
  13
  14 #if !UCONFIG_NO_COLLATION
  15
  16 #include "unicode/utf8.h"
  17 #include "charstr.h"
  18 #include "cmemory.h"
  19 #include "collation.h"
  20 #include "collationdata.h"
  21 #include "collationfcd.h"
  22 #include "collationiterator.h"
  23 #include "normalizer2impl.h"
  24 #include "uassert.h"
  25 #include "utf8collationiterator.h"
  26
  27 U_NAMESPACE_BEGIN
  28
  29 UTF8CollationIterator::~UTF8CollationIterator() {}
  30
  31 void
  32 UTF8CollationIterator::resetToOffset(int32_t newOffset) {
  33     reset();
  34     pos = newOffset;
  35 }
  36
  37 int32_t
  38 UTF8CollationIterator::getOffset() const {
  39     return pos;
  40 }
  41
  42 uint32_t
  43 UTF8CollationIterator::handleNextCE32(UChar32 &c, UErrorCode & /*errorCode*/) {
  44     if(pos == length) {
  45         c = U_SENTINEL;
  46         return Collation::FALLBACK_CE32;
  47     }
  48     // Optimized combination of U8_NEXT_OR_FFFD() and UTRIE2_U8_NEXT32().
  49     c = u8[pos++];
  50     if(c < 0xc0) {
  51         // ASCII 00..7F; trail bytes 80..BF map to error values.
  52         return trie->data32[c];
  53     }
  54     uint8_t t1, t2;
  55     if(c < 0xe0 && pos != length && (t1 = (u8[pos] - 0x80)) <= 0x3f) {
  56         // U+0080..U+07FF; 00..7F map to error values.
  57         uint32_t ce32 = trie->data32[trie->index[(UTRIE2_UTF8_2B_INDEX_2_OFFSET - 0xc0) + c] + t1];
  58         c = ((c & 0x1f) << 6) | t1;
  59         ++pos;
  60         return ce32;
  61     } else if(c <= 0xef &&
  62               ((pos + 1) < length || length < 0) &&
  63               (t1 = (u8[pos] - 0x80)) <= 0x3f && (c != 0xe0 || t1 >= 0x20) &&
  64               (t2 = (u8[pos + 1] - 0x80)) <= 0x3f
  65     ) {
  66         // U+0800..U+FFFF; caller maps surrogates to error values.
  67         c = (UChar)((c << 12) | (t1 << 6) | t2);
  68         pos += 2;
  69         return UTRIE2_GET32_FROM_U16_SINGLE_LEAD(trie, c);
  70     } else {
  71         // Function call for supplementary code points and error cases.
  72         // Illegal byte sequences yield U+FFFD.
  73         c = utf8_nextCharSafeBody(u8, &pos, length, c, -3);
  74         return data->getCE32(c);
  75     }
  76 }
  77
  78 UBool
  79 UTF8CollationIterator::foundNULTerminator() {
  80     if(length < 0) {
  81         length = --pos;
  82         return TRUE;
  83     } else {
  84         return FALSE;
  85     }
  86 }
  87
  88 UBool
  89 UTF8CollationIterator::forbidSurrogateCodePoints() const {
  90     return TRUE;
  91 }
  92
  93 UChar32
  94 UTF8CollationIterator::nextCodePoint(UErrorCode & /*errorCode*/) {
  95     if(pos == length) {
  96         return U_SENTINEL;
  97     }
  98     if(u8[pos] == 0 && length < 0) {
  99         length = pos;
 100         return U_SENTINEL;
 101     }
 102     UChar32 c;
 103     U8_NEXT_OR_FFFD(u8, pos, length, c);
 104     return c;
 105 }
 106
 107 UChar32
 108 UTF8CollationIterator::previousCodePoint(UErrorCode & /*errorCode*/) {
 109     if(pos == 0) {
 110         return U_SENTINEL;
 111     }
 112     UChar32 c;
 113     U8_PREV_OR_FFFD(u8, 0, pos, c);
 114     return c;
 115 }
 116
 117 void
 118 UTF8CollationIterator::forwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
 119     U8_FWD_N(u8, pos, length, num);
 120 }
 121
 122 void
 123 UTF8CollationIterator::backwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
 124     U8_BACK_N(u8, 0, pos, num);
 125 }
 126
 127 // FCDUTF8CollationIterator ------------------------------------------------ ***
 128
 129 FCDUTF8CollationIterator::~FCDUTF8CollationIterator() {}
 130
 131 void
 132 FCDUTF8CollationIterator::resetToOffset(int32_t newOffset) {
 133     reset();
 134     start = pos = newOffset;
 135     state = CHECK_FWD;
 136 }
 137
 138 int32_t
 139 FCDUTF8CollationIterator::getOffset() const {
 140     if(state != IN_NORMALIZED) {
 141         return pos;
 142     } else if(pos == 0) {
 143         return start;
 144     } else {
 145         return limit;
 146     }
 147 }
 148
 149 uint32_t
 150 FCDUTF8CollationIterator::handleNextCE32(UChar32 &c, UErrorCode &errorCode) {
 151     for(;;) {
 152         if(state == CHECK_FWD) {
 153             // Combination of UTF8CollationIterator::handleNextCE32() with FCD check fastpath.
 154             if(pos == length) {
 155                 c = U_SENTINEL;
 156                 return Collation::FALLBACK_CE32;
 157             }
 158             c = u8[pos++];
 159             if(c < 0xc0) {
 160                 // ASCII 00..7F; trail bytes 80..BF map to error values.
 161                 return trie->data32[c];
 162             }
 163             uint8_t t1, t2;
 164             if(c < 0xe0 && pos != length && (t1 = (u8[pos] - 0x80)) <= 0x3f) {
 165                 // U+0080..U+07FF; 00..7F map to error values.
 166                 uint32_t ce32 = trie->data32[trie->index[(UTRIE2_UTF8_2B_INDEX_2_OFFSET - 0xc0) + c] + t1];
 167                 c = ((c & 0x1f) << 6) | t1;
 168                 ++pos;
 169                 if(CollationFCD::hasTccc(c) && pos != length && nextHasLccc()) {
 170                     pos -= 2;
 171                 } else {
 172                     return ce32;
 173                 }
 174             } else if(c <= 0xef &&
 175                       ((pos + 1) < length || length < 0) &&
 176                       (t1 = (u8[pos] - 0x80)) <= 0x3f && (c != 0xe0 || t1 >= 0x20) &&
 177                       (t2 = (u8[pos + 1] - 0x80)) <= 0x3f
 178             ) {
 179                 // U+0800..U+FFFF; caller maps surrogates to error values.
 180                 c = (UChar)((c << 12) | (t1 << 6) | t2);
 181                 pos += 2;
 182                 if(CollationFCD::hasTccc(c) &&
 183                         (CollationFCD::maybeTibetanCompositeVowel(c) ||
 184                             (pos != length && nextHasLccc()))) {
 185                     pos -= 3;
 186                 } else {
 187                     break;  // return CE32(BMP)
 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(c < 0x80) { 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(c < 0x80) {
 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((c = u8[pos - 1]) < 0x80) {
 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