// © 2016 and later: Unicode, Inc. and others.
// License & terms of use: http://www.unicode.org/copyright.html
/*
*******************************************************************************
* Copyright (C) 2012-2014, International Business Machines
* Corporation and others. All Rights Reserved.
*******************************************************************************
* utf8collationiterator.cpp
*
* created on: 2012nov12 (from utf16collationiterator.cpp & uitercollationiterator.cpp)
* created by: Markus W. Scherer
*/
#include "unicode/utypes.h"
#if !UCONFIG_NO_COLLATION
#include "unicode/utf8.h"
#include "charstr.h"
#include "cmemory.h"
#include "collation.h"
#include "collationdata.h"
#include "collationfcd.h"
#include "collationiterator.h"
#include "normalizer2impl.h"
#include "uassert.h"
#include "utf8collationiterator.h"
U_NAMESPACE_BEGIN
UTF8CollationIterator::~UTF8CollationIterator() {}
void
UTF8CollationIterator::resetToOffset(int32_t newOffset) {
reset();
pos = newOffset;
}
int32_t
UTF8CollationIterator::getOffset() const {
return pos;
}
uint32_t
UTF8CollationIterator::handleNextCE32(UChar32 &c, UErrorCode & /*errorCode*/) {
if(pos == length) {
c = U_SENTINEL;
return Collation::FALLBACK_CE32;
}
// Optimized combination of U8_NEXT_OR_FFFD() and UTRIE2_U8_NEXT32().
c = u8[pos++];
if(U8_IS_SINGLE(c)) {
// ASCII 00..7F
return trie->data32[c];
}
uint8_t t1, t2;
if(0xe0 <= c && c < 0xf0 &&
((pos + 1) < length || length < 0) &&
U8_IS_VALID_LEAD3_AND_T1(c, t1 = u8[pos]) &&
(t2 = (u8[pos + 1] - 0x80)) <= 0x3f) {
// U+0800..U+FFFF except surrogates
c = (((c & 0xf) << 12) | ((t1 & 0x3f) << 6) | t2);
pos += 2;
return UTRIE2_GET32_FROM_U16_SINGLE_LEAD(trie, c);
} else if(c < 0xe0 && c >= 0xc2 && pos != length && (t1 = (u8[pos] - 0x80)) <= 0x3f) {
// U+0080..U+07FF
uint32_t ce32 = trie->data32[trie->index[(UTRIE2_UTF8_2B_INDEX_2_OFFSET - 0xc0) + c] + t1];
c = ((c & 0x1f) << 6) | t1;
++pos;
return ce32;
} else {
// Function call for supplementary code points and error cases.
// Illegal byte sequences yield U+FFFD.
c = utf8_nextCharSafeBody(u8, &pos, length, c, -3);
return data->getCE32(c);
}
}
UBool
UTF8CollationIterator::foundNULTerminator() {
if(length < 0) {
length = --pos;
return TRUE;
} else {
return FALSE;
}
}
UBool
UTF8CollationIterator::forbidSurrogateCodePoints() const {
return TRUE;
}
UChar32
UTF8CollationIterator::nextCodePoint(UErrorCode & /*errorCode*/) {
if(pos == length) {
return U_SENTINEL;
}
if(u8[pos] == 0 && length < 0) {
length = pos;
return U_SENTINEL;
}
UChar32 c;
U8_NEXT_OR_FFFD(u8, pos, length, c);
return c;
}
UChar32
UTF8CollationIterator::previousCodePoint(UErrorCode & /*errorCode*/) {
if(pos == 0) {
return U_SENTINEL;
}
UChar32 c;
U8_PREV_OR_FFFD(u8, 0, pos, c);
return c;
}
void
UTF8CollationIterator::forwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
U8_FWD_N(u8, pos, length, num);
}
void
UTF8CollationIterator::backwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
U8_BACK_N(u8, 0, pos, num);
}
// FCDUTF8CollationIterator ------------------------------------------------ ***
FCDUTF8CollationIterator::~FCDUTF8CollationIterator() {}
void
FCDUTF8CollationIterator::resetToOffset(int32_t newOffset) {
reset();
start = pos = newOffset;
state = CHECK_FWD;
}
int32_t
FCDUTF8CollationIterator::getOffset() const {
if(state != IN_NORMALIZED) {
return pos;
} else if(pos == 0) {
return start;
} else {
return limit;
}
}
uint32_t
FCDUTF8CollationIterator::handleNextCE32(UChar32 &c, UErrorCode &errorCode) {
for(;;) {
if(state == CHECK_FWD) {
// Combination of UTF8CollationIterator::handleNextCE32() with FCD check fastpath.
if(pos == length) {
c = U_SENTINEL;
return Collation::FALLBACK_CE32;
}
c = u8[pos++];
if(U8_IS_SINGLE(c)) {
// ASCII 00..7F
return trie->data32[c];
}
uint8_t t1, t2;
if(0xe0 <= c && c < 0xf0 &&
((pos + 1) < length || length < 0) &&
U8_IS_VALID_LEAD3_AND_T1(c, t1 = u8[pos]) &&
(t2 = (u8[pos + 1] - 0x80)) <= 0x3f) {
// U+0800..U+FFFF except surrogates
c = (((c & 0xf) << 12) | ((t1 & 0x3f) << 6) | t2);
pos += 2;
if(CollationFCD::hasTccc(c) &&
(CollationFCD::maybeTibetanCompositeVowel(c) ||
(pos != length && nextHasLccc()))) {
pos -= 3;
} else {
break; // return CE32(BMP)
}
} else if(c < 0xe0 && c >= 0xc2 && pos != length && (t1 = (u8[pos] - 0x80)) <= 0x3f) {
// U+0080..U+07FF
uint32_t ce32 = trie->data32[trie->index[(UTRIE2_UTF8_2B_INDEX_2_OFFSET - 0xc0) + c] + t1];
c = ((c & 0x1f) << 6) | t1;
++pos;
if(CollationFCD::hasTccc(c) && pos != length && nextHasLccc()) {
pos -= 2;
} else {
return ce32;
}
} else {
// Function call for supplementary code points and error cases.
// Illegal byte sequences yield U+FFFD.
c = utf8_nextCharSafeBody(u8, &pos, length, c, -3);
if(c == 0xfffd) {
return Collation::FFFD_CE32;
} else {
U_ASSERT(c > 0xffff);
if(CollationFCD::hasTccc(U16_LEAD(c)) && pos != length && nextHasLccc()) {
pos -= 4;
} else {
return data->getCE32FromSupplementary(c);
}
}
}
if(!nextSegment(errorCode)) {
c = U_SENTINEL;
return Collation::FALLBACK_CE32;
}
continue;
} else if(state == IN_FCD_SEGMENT && pos != limit) {
return UTF8CollationIterator::handleNextCE32(c, errorCode);
} else if(state == IN_NORMALIZED && pos != normalized.length()) {
c = normalized[pos++];
break;
} else {
switchToForward();
}
}
return UTRIE2_GET32_FROM_U16_SINGLE_LEAD(trie, c);
}
UBool
FCDUTF8CollationIterator::nextHasLccc() const {
U_ASSERT(state == CHECK_FWD && pos != length);
// The lowest code point with ccc!=0 is U+0300 which is CC 80 in UTF-8.
// CJK U+4000..U+DFFF except U+Axxx are also FCD-inert. (Lead bytes E4..ED except EA.)
UChar32 c = u8[pos];
if(c < 0xcc || (0xe4 <= c && c <= 0xed && c != 0xea)) { return FALSE; }
int32_t i = pos;
U8_NEXT_OR_FFFD(u8, i, length, c);
if(c > 0xffff) { c = U16_LEAD(c); }
return CollationFCD::hasLccc(c);
}
UBool
FCDUTF8CollationIterator::previousHasTccc() const {
U_ASSERT(state == CHECK_BWD && pos != 0);
UChar32 c = u8[pos - 1];
if(U8_IS_SINGLE(c)) { return FALSE; }
int32_t i = pos;
U8_PREV_OR_FFFD(u8, 0, i, c);
if(c > 0xffff) { c = U16_LEAD(c); }
return CollationFCD::hasTccc(c);
}
UChar
FCDUTF8CollationIterator::handleGetTrailSurrogate() {
if(state != IN_NORMALIZED) { return 0; }
U_ASSERT(pos < normalized.length());
UChar trail;
if(U16_IS_TRAIL(trail = normalized[pos])) { ++pos; }
return trail;
}
UBool
FCDUTF8CollationIterator::foundNULTerminator() {
if(state == CHECK_FWD && length < 0) {
length = --pos;
return TRUE;
} else {
return FALSE;
}
}
UChar32
FCDUTF8CollationIterator::nextCodePoint(UErrorCode &errorCode) {
UChar32 c;
for(;;) {
if(state == CHECK_FWD) {
if(pos == length || ((c = u8[pos]) == 0 && length < 0)) {
return U_SENTINEL;
}
if(U8_IS_SINGLE(c)) {
++pos;
return c;
}
U8_NEXT_OR_FFFD(u8, pos, length, c);
if(CollationFCD::hasTccc(c <= 0xffff ? c : U16_LEAD(c)) &&
(CollationFCD::maybeTibetanCompositeVowel(c) ||
(pos != length && nextHasLccc()))) {
// c is not FCD-inert, therefore it is not U+FFFD and it has a valid byte sequence
// and we can use U8_LENGTH() rather than a previous-position variable.
pos -= U8_LENGTH(c);
if(!nextSegment(errorCode)) {
return U_SENTINEL;
}
continue;
}
return c;
} else if(state == IN_FCD_SEGMENT && pos != limit) {
U8_NEXT_OR_FFFD(u8, pos, length, c);
return c;
} else if(state == IN_NORMALIZED && pos != normalized.length()) {
c = normalized.char32At(pos);
pos += U16_LENGTH(c);
return c;
} else {
switchToForward();
}
}
}
UChar32
FCDUTF8CollationIterator::previousCodePoint(UErrorCode &errorCode) {
UChar32 c;
for(;;) {
if(state == CHECK_BWD) {
if(pos == 0) {
return U_SENTINEL;
}
if(U8_IS_SINGLE(c = u8[pos - 1])) {
--pos;
return c;
}
U8_PREV_OR_FFFD(u8, 0, pos, c);
if(CollationFCD::hasLccc(c <= 0xffff ? c : U16_LEAD(c)) &&
(CollationFCD::maybeTibetanCompositeVowel(c) ||
(pos != 0 && previousHasTccc()))) {
// c is not FCD-inert, therefore it is not U+FFFD and it has a valid byte sequence
// and we can use U8_LENGTH() rather than a previous-position variable.
pos += U8_LENGTH(c);
if(!previousSegment(errorCode)) {
return U_SENTINEL;
}
continue;
}
return c;
} else if(state == IN_FCD_SEGMENT && pos != start) {
U8_PREV_OR_FFFD(u8, 0, pos, c);
return c;
} else if(state >= IN_NORMALIZED && pos != 0) {
c = normalized.char32At(pos - 1);
pos -= U16_LENGTH(c);
return c;
} else {
switchToBackward();
}
}
}
void
FCDUTF8CollationIterator::forwardNumCodePoints(int32_t num, UErrorCode &errorCode) {
// Specify the class to avoid a virtual-function indirection.
// In Java, we would declare this class final.
while(num > 0 && FCDUTF8CollationIterator::nextCodePoint(errorCode) >= 0) {
--num;
}
}
void
FCDUTF8CollationIterator::backwardNumCodePoints(int32_t num, UErrorCode &errorCode) {
// Specify the class to avoid a virtual-function indirection.
// In Java, we would declare this class final.
while(num > 0 && FCDUTF8CollationIterator::previousCodePoint(errorCode) >= 0) {
--num;
}
}
void
FCDUTF8CollationIterator::switchToForward() {
U_ASSERT(state == CHECK_BWD ||
(state == IN_FCD_SEGMENT && pos == limit) ||
(state == IN_NORMALIZED && pos == normalized.length()));
if(state == CHECK_BWD) {
// Turn around from backward checking.
start = pos;
if(pos == limit) {
state = CHECK_FWD; // Check forward.
} else { // pos < limit
state = IN_FCD_SEGMENT; // Stay in FCD segment.
}
} else {
// Reached the end of the FCD segment.
if(state == IN_FCD_SEGMENT) {
// The input text segment is FCD, extend it forward.
} else {
// The input text segment needed to be normalized.
// Switch to checking forward from it.
start = pos = limit;
}
state = CHECK_FWD;
}
}
UBool
FCDUTF8CollationIterator::nextSegment(UErrorCode &errorCode) {
if(U_FAILURE(errorCode)) { return FALSE; }
U_ASSERT(state == CHECK_FWD && pos != length);
// The input text [start..pos[ passes the FCD check.
int32_t segmentStart = pos;
// Collect the characters being checked, in case they need to be normalized.
UnicodeString s;
uint8_t prevCC = 0;
for(;;) {
// Fetch the next character and its fcd16 value.
int32_t cpStart = pos;
UChar32 c;
U8_NEXT_OR_FFFD(u8, pos, length, c);
uint16_t fcd16 = nfcImpl.getFCD16(c);
uint8_t leadCC = (uint8_t)(fcd16 >> 8);
if(leadCC == 0 && cpStart != segmentStart) {
// FCD boundary before this character.
pos = cpStart;
break;
}
s.append(c);
if(leadCC != 0 && (prevCC > leadCC || CollationFCD::isFCD16OfTibetanCompositeVowel(fcd16))) {
// Fails FCD check. Find the next FCD boundary and normalize.
while(pos != length) {
cpStart = pos;
U8_NEXT_OR_FFFD(u8, pos, length, c);
if(nfcImpl.getFCD16(c) <= 0xff) {
pos = cpStart;
break;
}
s.append(c);
}
if(!normalize(s, errorCode)) { return FALSE; }
start = segmentStart;
limit = pos;
state = IN_NORMALIZED;
pos = 0;
return TRUE;
}
prevCC = (uint8_t)fcd16;
if(pos == length || prevCC == 0) {
// FCD boundary after the last character.
break;
}
}
limit = pos;
pos = segmentStart;
U_ASSERT(pos != limit);
state = IN_FCD_SEGMENT;
return TRUE;
}
void
FCDUTF8CollationIterator::switchToBackward() {
U_ASSERT(state == CHECK_FWD ||
(state == IN_FCD_SEGMENT && pos == start) ||
(state >= IN_NORMALIZED && pos == 0));
if(state == CHECK_FWD) {
// Turn around from forward checking.
limit = pos;
if(pos == start) {
state = CHECK_BWD; // Check backward.
} else { // pos > start
state = IN_FCD_SEGMENT; // Stay in FCD segment.
}
} else {
// Reached the start of the FCD segment.
if(state == IN_FCD_SEGMENT) {
// The input text segment is FCD, extend it backward.
} else {
// The input text segment needed to be normalized.
// Switch to checking backward from it.
limit = pos = start;
}
state = CHECK_BWD;
}
}
UBool
FCDUTF8CollationIterator::previousSegment(UErrorCode &errorCode) {
if(U_FAILURE(errorCode)) { return FALSE; }
U_ASSERT(state == CHECK_BWD && pos != 0);
// The input text [pos..limit[ passes the FCD check.
int32_t segmentLimit = pos;
// Collect the characters being checked, in case they need to be normalized.
UnicodeString s;
uint8_t nextCC = 0;
for(;;) {
// Fetch the previous character and its fcd16 value.
int32_t cpLimit = pos;
UChar32 c;
U8_PREV_OR_FFFD(u8, 0, pos, c);
uint16_t fcd16 = nfcImpl.getFCD16(c);
uint8_t trailCC = (uint8_t)fcd16;
if(trailCC == 0 && cpLimit != segmentLimit) {
// FCD boundary after this character.
pos = cpLimit;
break;
}
s.append(c);
if(trailCC != 0 && ((nextCC != 0 && trailCC > nextCC) ||
CollationFCD::isFCD16OfTibetanCompositeVowel(fcd16))) {
// Fails FCD check. Find the previous FCD boundary and normalize.
while(fcd16 > 0xff && pos != 0) {
cpLimit = pos;
U8_PREV_OR_FFFD(u8, 0, pos, c);
fcd16 = nfcImpl.getFCD16(c);
if(fcd16 == 0) {
pos = cpLimit;
break;
}
s.append(c);
}
s.reverse();
if(!normalize(s, errorCode)) { return FALSE; }
limit = segmentLimit;
start = pos;
state = IN_NORMALIZED;
pos = normalized.length();
return TRUE;
}
nextCC = (uint8_t)(fcd16 >> 8);
if(pos == 0 || nextCC == 0) {
// FCD boundary before the following character.
break;
}
}
start = pos;
pos = segmentLimit;
U_ASSERT(pos != start);
state = IN_FCD_SEGMENT;
return TRUE;
}
UBool
FCDUTF8CollationIterator::normalize(const UnicodeString &s, UErrorCode &errorCode) {
// NFD without argument checking.
U_ASSERT(U_SUCCESS(errorCode));
nfcImpl.decompose(s, normalized, errorCode);
return U_SUCCESS(errorCode);
}
U_NAMESPACE_END
#endif // !UCONFIG_NO_COLLATION