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
~UTF8CollationIterator()31 UTF8CollationIterator::~UTF8CollationIterator() {}
32
33 void
resetToOffset(int32_t newOffset)34 UTF8CollationIterator::resetToOffset(int32_t newOffset) {
35 reset();
36 pos = newOffset;
37 }
38
39 int32_t
getOffset() const40 UTF8CollationIterator::getOffset() const {
41 return pos;
42 }
43
44 uint32_t
handleNextCE32(UChar32 & c,UErrorCode &)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
foundNULTerminator()80 UTF8CollationIterator::foundNULTerminator() {
81 if(length < 0) {
82 length = --pos;
83 return TRUE;
84 } else {
85 return FALSE;
86 }
87 }
88
89 UBool
forbidSurrogateCodePoints() const90 UTF8CollationIterator::forbidSurrogateCodePoints() const {
91 return TRUE;
92 }
93
94 UChar32
nextCodePoint(UErrorCode &)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
previousCodePoint(UErrorCode &)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
forwardNumCodePoints(int32_t num,UErrorCode &)119 UTF8CollationIterator::forwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
120 U8_FWD_N(u8, pos, length, num);
121 }
122
123 void
backwardNumCodePoints(int32_t num,UErrorCode &)124 UTF8CollationIterator::backwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
125 U8_BACK_N(u8, 0, pos, num);
126 }
127
128 // FCDUTF8CollationIterator ------------------------------------------------ ***
129
~FCDUTF8CollationIterator()130 FCDUTF8CollationIterator::~FCDUTF8CollationIterator() {}
131
132 void
resetToOffset(int32_t newOffset)133 FCDUTF8CollationIterator::resetToOffset(int32_t newOffset) {
134 reset();
135 start = pos = newOffset;
136 state = CHECK_FWD;
137 }
138
139 int32_t
getOffset() const140 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
handleNextCE32(UChar32 & c,UErrorCode & errorCode)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
nextHasLccc() const222 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
previousHasTccc() const235 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
handleGetTrailSurrogate()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
foundNULTerminator()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
nextCodePoint(UErrorCode & errorCode)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
previousCodePoint(UErrorCode & errorCode)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
forwardNumCodePoints(int32_t num,UErrorCode & errorCode)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
backwardNumCodePoints(int32_t num,UErrorCode & errorCode)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
switchToForward()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
nextSegment(UErrorCode & errorCode)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
switchToBackward()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
previousSegment(UErrorCode & errorCode)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
normalize(const UnicodeString & s,UErrorCode & errorCode)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