Home | History | Annotate | Download | only in i18n
      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
    530