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
~UTF8CollationIterator()29 UTF8CollationIterator::~UTF8CollationIterator() {}
30
31 void
resetToOffset(int32_t newOffset)32 UTF8CollationIterator::resetToOffset(int32_t newOffset) {
33 reset();
34 pos = newOffset;
35 }
36
37 int32_t
getOffset() const38 UTF8CollationIterator::getOffset() const {
39 return pos;
40 }
41
42 uint32_t
handleNextCE32(UChar32 & c,UErrorCode &)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
foundNULTerminator()79 UTF8CollationIterator::foundNULTerminator() {
80 if(length < 0) {
81 length = --pos;
82 return TRUE;
83 } else {
84 return FALSE;
85 }
86 }
87
88 UBool
forbidSurrogateCodePoints() const89 UTF8CollationIterator::forbidSurrogateCodePoints() const {
90 return TRUE;
91 }
92
93 UChar32
nextCodePoint(UErrorCode &)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
previousCodePoint(UErrorCode &)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
forwardNumCodePoints(int32_t num,UErrorCode &)118 UTF8CollationIterator::forwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
119 U8_FWD_N(u8, pos, length, num);
120 }
121
122 void
backwardNumCodePoints(int32_t num,UErrorCode &)123 UTF8CollationIterator::backwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
124 U8_BACK_N(u8, 0, pos, num);
125 }
126
127 // FCDUTF8CollationIterator ------------------------------------------------ ***
128
~FCDUTF8CollationIterator()129 FCDUTF8CollationIterator::~FCDUTF8CollationIterator() {}
130
131 void
resetToOffset(int32_t newOffset)132 FCDUTF8CollationIterator::resetToOffset(int32_t newOffset) {
133 reset();
134 start = pos = newOffset;
135 state = CHECK_FWD;
136 }
137
138 int32_t
getOffset() const139 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
handleNextCE32(UChar32 & c,UErrorCode & errorCode)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
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(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
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(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
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((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
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