Line data Source code
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 :
31 0 : UTF8CollationIterator::~UTF8CollationIterator() {}
32 :
33 : void
34 0 : UTF8CollationIterator::resetToOffset(int32_t newOffset) {
35 0 : reset();
36 0 : pos = newOffset;
37 0 : }
38 :
39 : int32_t
40 0 : UTF8CollationIterator::getOffset() const {
41 0 : return pos;
42 : }
43 :
44 : uint32_t
45 0 : UTF8CollationIterator::handleNextCE32(UChar32 &c, UErrorCode & /*errorCode*/) {
46 0 : if(pos == length) {
47 0 : c = U_SENTINEL;
48 0 : return Collation::FALLBACK_CE32;
49 : }
50 : // Optimized combination of U8_NEXT_OR_FFFD() and UTRIE2_U8_NEXT32().
51 0 : c = u8[pos++];
52 0 : if(c < 0xc0) {
53 : // ASCII 00..7F; trail bytes 80..BF map to error values.
54 0 : return trie->data32[c];
55 : }
56 : uint8_t t1, t2;
57 0 : if(c < 0xe0 && pos != length && (t1 = (u8[pos] - 0x80)) <= 0x3f) {
58 : // U+0080..U+07FF; 00..7F map to error values.
59 0 : uint32_t ce32 = trie->data32[trie->index[(UTRIE2_UTF8_2B_INDEX_2_OFFSET - 0xc0) + c] + t1];
60 0 : c = ((c & 0x1f) << 6) | t1;
61 0 : ++pos;
62 0 : return ce32;
63 0 : } else if(c <= 0xef &&
64 0 : ((pos + 1) < length || length < 0) &&
65 0 : (t1 = (u8[pos] - 0x80)) <= 0x3f && (c != 0xe0 || t1 >= 0x20) &&
66 0 : (t2 = (u8[pos + 1] - 0x80)) <= 0x3f
67 : ) {
68 : // U+0800..U+FFFF; caller maps surrogates to error values.
69 0 : c = (UChar)((c << 12) | (t1 << 6) | t2);
70 0 : pos += 2;
71 0 : return UTRIE2_GET32_FROM_U16_SINGLE_LEAD(trie, c);
72 : } else {
73 : // Function call for supplementary code points and error cases.
74 : // Illegal byte sequences yield U+FFFD.
75 0 : c = utf8_nextCharSafeBody(u8, &pos, length, c, -3);
76 0 : return data->getCE32(c);
77 : }
78 : }
79 :
80 : UBool
81 0 : UTF8CollationIterator::foundNULTerminator() {
82 0 : if(length < 0) {
83 0 : length = --pos;
84 0 : return TRUE;
85 : } else {
86 0 : return FALSE;
87 : }
88 : }
89 :
90 : UBool
91 0 : UTF8CollationIterator::forbidSurrogateCodePoints() const {
92 0 : return TRUE;
93 : }
94 :
95 : UChar32
96 0 : UTF8CollationIterator::nextCodePoint(UErrorCode & /*errorCode*/) {
97 0 : if(pos == length) {
98 0 : return U_SENTINEL;
99 : }
100 0 : if(u8[pos] == 0 && length < 0) {
101 0 : length = pos;
102 0 : return U_SENTINEL;
103 : }
104 : UChar32 c;
105 0 : U8_NEXT_OR_FFFD(u8, pos, length, c);
106 0 : return c;
107 : }
108 :
109 : UChar32
110 0 : UTF8CollationIterator::previousCodePoint(UErrorCode & /*errorCode*/) {
111 0 : if(pos == 0) {
112 0 : return U_SENTINEL;
113 : }
114 : UChar32 c;
115 0 : U8_PREV_OR_FFFD(u8, 0, pos, c);
116 0 : return c;
117 : }
118 :
119 : void
120 0 : UTF8CollationIterator::forwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
121 0 : U8_FWD_N(u8, pos, length, num);
122 0 : }
123 :
124 : void
125 0 : UTF8CollationIterator::backwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
126 0 : U8_BACK_N(u8, 0, pos, num);
127 0 : }
128 :
129 : // FCDUTF8CollationIterator ------------------------------------------------ ***
130 :
131 0 : FCDUTF8CollationIterator::~FCDUTF8CollationIterator() {}
132 :
133 : void
134 0 : FCDUTF8CollationIterator::resetToOffset(int32_t newOffset) {
135 0 : reset();
136 0 : start = pos = newOffset;
137 0 : state = CHECK_FWD;
138 0 : }
139 :
140 : int32_t
141 0 : FCDUTF8CollationIterator::getOffset() const {
142 0 : if(state != IN_NORMALIZED) {
143 0 : return pos;
144 0 : } else if(pos == 0) {
145 0 : return start;
146 : } else {
147 0 : return limit;
148 : }
149 : }
150 :
151 : uint32_t
152 0 : FCDUTF8CollationIterator::handleNextCE32(UChar32 &c, UErrorCode &errorCode) {
153 : for(;;) {
154 0 : if(state == CHECK_FWD) {
155 : // Combination of UTF8CollationIterator::handleNextCE32() with FCD check fastpath.
156 0 : if(pos == length) {
157 0 : c = U_SENTINEL;
158 0 : return Collation::FALLBACK_CE32;
159 : }
160 0 : c = u8[pos++];
161 0 : if(c < 0xc0) {
162 : // ASCII 00..7F; trail bytes 80..BF map to error values.
163 0 : return trie->data32[c];
164 : }
165 : uint8_t t1, t2;
166 0 : if(c < 0xe0 && pos != length && (t1 = (u8[pos] - 0x80)) <= 0x3f) {
167 : // U+0080..U+07FF; 00..7F map to error values.
168 0 : uint32_t ce32 = trie->data32[trie->index[(UTRIE2_UTF8_2B_INDEX_2_OFFSET - 0xc0) + c] + t1];
169 0 : c = ((c & 0x1f) << 6) | t1;
170 0 : ++pos;
171 0 : if(CollationFCD::hasTccc(c) && pos != length && nextHasLccc()) {
172 0 : pos -= 2;
173 : } else {
174 0 : return ce32;
175 : }
176 0 : } else if(c <= 0xef &&
177 0 : ((pos + 1) < length || length < 0) &&
178 0 : (t1 = (u8[pos] - 0x80)) <= 0x3f && (c != 0xe0 || t1 >= 0x20) &&
179 0 : (t2 = (u8[pos + 1] - 0x80)) <= 0x3f
180 : ) {
181 : // U+0800..U+FFFF; caller maps surrogates to error values.
182 0 : c = (UChar)((c << 12) | (t1 << 6) | t2);
183 0 : pos += 2;
184 0 : if(CollationFCD::hasTccc(c) &&
185 0 : (CollationFCD::maybeTibetanCompositeVowel(c) ||
186 0 : (pos != length && nextHasLccc()))) {
187 0 : pos -= 3;
188 : } else {
189 0 : break; // return CE32(BMP)
190 : }
191 : } else {
192 : // Function call for supplementary code points and error cases.
193 : // Illegal byte sequences yield U+FFFD.
194 0 : c = utf8_nextCharSafeBody(u8, &pos, length, c, -3);
195 0 : if(c == 0xfffd) {
196 0 : return Collation::FFFD_CE32;
197 : } else {
198 0 : U_ASSERT(c > 0xffff);
199 0 : if(CollationFCD::hasTccc(U16_LEAD(c)) && pos != length && nextHasLccc()) {
200 0 : pos -= 4;
201 : } else {
202 0 : return data->getCE32FromSupplementary(c);
203 : }
204 : }
205 : }
206 0 : if(!nextSegment(errorCode)) {
207 0 : c = U_SENTINEL;
208 0 : return Collation::FALLBACK_CE32;
209 : }
210 0 : continue;
211 0 : } else if(state == IN_FCD_SEGMENT && pos != limit) {
212 0 : return UTF8CollationIterator::handleNextCE32(c, errorCode);
213 0 : } else if(state == IN_NORMALIZED && pos != normalized.length()) {
214 0 : c = normalized[pos++];
215 0 : break;
216 : } else {
217 0 : switchToForward();
218 : }
219 0 : }
220 0 : return UTRIE2_GET32_FROM_U16_SINGLE_LEAD(trie, c);
221 : }
222 :
223 : UBool
224 0 : FCDUTF8CollationIterator::nextHasLccc() const {
225 0 : U_ASSERT(state == CHECK_FWD && pos != length);
226 : // The lowest code point with ccc!=0 is U+0300 which is CC 80 in UTF-8.
227 : // CJK U+4000..U+DFFF except U+Axxx are also FCD-inert. (Lead bytes E4..ED except EA.)
228 0 : UChar32 c = u8[pos];
229 0 : if(c < 0xcc || (0xe4 <= c && c <= 0xed && c != 0xea)) { return FALSE; }
230 0 : int32_t i = pos;
231 0 : U8_NEXT_OR_FFFD(u8, i, length, c);
232 0 : if(c > 0xffff) { c = U16_LEAD(c); }
233 0 : return CollationFCD::hasLccc(c);
234 : }
235 :
236 : UBool
237 0 : FCDUTF8CollationIterator::previousHasTccc() const {
238 0 : U_ASSERT(state == CHECK_BWD && pos != 0);
239 0 : UChar32 c = u8[pos - 1];
240 0 : if(c < 0x80) { return FALSE; }
241 0 : int32_t i = pos;
242 0 : U8_PREV_OR_FFFD(u8, 0, i, c);
243 0 : if(c > 0xffff) { c = U16_LEAD(c); }
244 0 : return CollationFCD::hasTccc(c);
245 : }
246 :
247 : UChar
248 0 : FCDUTF8CollationIterator::handleGetTrailSurrogate() {
249 0 : if(state != IN_NORMALIZED) { return 0; }
250 0 : U_ASSERT(pos < normalized.length());
251 : UChar trail;
252 0 : if(U16_IS_TRAIL(trail = normalized[pos])) { ++pos; }
253 0 : return trail;
254 : }
255 :
256 : UBool
257 0 : FCDUTF8CollationIterator::foundNULTerminator() {
258 0 : if(state == CHECK_FWD && length < 0) {
259 0 : length = --pos;
260 0 : return TRUE;
261 : } else {
262 0 : return FALSE;
263 : }
264 : }
265 :
266 : UChar32
267 0 : FCDUTF8CollationIterator::nextCodePoint(UErrorCode &errorCode) {
268 : UChar32 c;
269 : for(;;) {
270 0 : if(state == CHECK_FWD) {
271 0 : if(pos == length || ((c = u8[pos]) == 0 && length < 0)) {
272 0 : return U_SENTINEL;
273 : }
274 0 : if(c < 0x80) {
275 0 : ++pos;
276 0 : return c;
277 : }
278 0 : U8_NEXT_OR_FFFD(u8, pos, length, c);
279 0 : if(CollationFCD::hasTccc(c <= 0xffff ? c : U16_LEAD(c)) &&
280 0 : (CollationFCD::maybeTibetanCompositeVowel(c) ||
281 0 : (pos != length && nextHasLccc()))) {
282 : // c is not FCD-inert, therefore it is not U+FFFD and it has a valid byte sequence
283 : // and we can use U8_LENGTH() rather than a previous-position variable.
284 0 : pos -= U8_LENGTH(c);
285 0 : if(!nextSegment(errorCode)) {
286 0 : return U_SENTINEL;
287 : }
288 0 : continue;
289 : }
290 0 : return c;
291 0 : } else if(state == IN_FCD_SEGMENT && pos != limit) {
292 0 : U8_NEXT_OR_FFFD(u8, pos, length, c);
293 0 : return c;
294 0 : } else if(state == IN_NORMALIZED && pos != normalized.length()) {
295 0 : c = normalized.char32At(pos);
296 0 : pos += U16_LENGTH(c);
297 0 : return c;
298 : } else {
299 0 : switchToForward();
300 : }
301 0 : }
302 : }
303 :
304 : UChar32
305 0 : FCDUTF8CollationIterator::previousCodePoint(UErrorCode &errorCode) {
306 : UChar32 c;
307 : for(;;) {
308 0 : if(state == CHECK_BWD) {
309 0 : if(pos == 0) {
310 0 : return U_SENTINEL;
311 : }
312 0 : if((c = u8[pos - 1]) < 0x80) {
313 0 : --pos;
314 0 : return c;
315 : }
316 0 : U8_PREV_OR_FFFD(u8, 0, pos, c);
317 0 : if(CollationFCD::hasLccc(c <= 0xffff ? c : U16_LEAD(c)) &&
318 0 : (CollationFCD::maybeTibetanCompositeVowel(c) ||
319 0 : (pos != 0 && previousHasTccc()))) {
320 : // c is not FCD-inert, therefore it is not U+FFFD and it has a valid byte sequence
321 : // and we can use U8_LENGTH() rather than a previous-position variable.
322 0 : pos += U8_LENGTH(c);
323 0 : if(!previousSegment(errorCode)) {
324 0 : return U_SENTINEL;
325 : }
326 0 : continue;
327 : }
328 0 : return c;
329 0 : } else if(state == IN_FCD_SEGMENT && pos != start) {
330 0 : U8_PREV_OR_FFFD(u8, 0, pos, c);
331 0 : return c;
332 0 : } else if(state >= IN_NORMALIZED && pos != 0) {
333 0 : c = normalized.char32At(pos - 1);
334 0 : pos -= U16_LENGTH(c);
335 0 : return c;
336 : } else {
337 0 : switchToBackward();
338 : }
339 : }
340 : }
341 :
342 : void
343 0 : FCDUTF8CollationIterator::forwardNumCodePoints(int32_t num, UErrorCode &errorCode) {
344 : // Specify the class to avoid a virtual-function indirection.
345 : // In Java, we would declare this class final.
346 0 : while(num > 0 && FCDUTF8CollationIterator::nextCodePoint(errorCode) >= 0) {
347 0 : --num;
348 : }
349 0 : }
350 :
351 : void
352 0 : FCDUTF8CollationIterator::backwardNumCodePoints(int32_t num, UErrorCode &errorCode) {
353 : // Specify the class to avoid a virtual-function indirection.
354 : // In Java, we would declare this class final.
355 0 : while(num > 0 && FCDUTF8CollationIterator::previousCodePoint(errorCode) >= 0) {
356 0 : --num;
357 : }
358 0 : }
359 :
360 : void
361 0 : FCDUTF8CollationIterator::switchToForward() {
362 0 : U_ASSERT(state == CHECK_BWD ||
363 : (state == IN_FCD_SEGMENT && pos == limit) ||
364 : (state == IN_NORMALIZED && pos == normalized.length()));
365 0 : if(state == CHECK_BWD) {
366 : // Turn around from backward checking.
367 0 : start = pos;
368 0 : if(pos == limit) {
369 0 : state = CHECK_FWD; // Check forward.
370 : } else { // pos < limit
371 0 : state = IN_FCD_SEGMENT; // Stay in FCD segment.
372 : }
373 : } else {
374 : // Reached the end of the FCD segment.
375 0 : if(state == IN_FCD_SEGMENT) {
376 : // The input text segment is FCD, extend it forward.
377 : } else {
378 : // The input text segment needed to be normalized.
379 : // Switch to checking forward from it.
380 0 : start = pos = limit;
381 : }
382 0 : state = CHECK_FWD;
383 : }
384 0 : }
385 :
386 : UBool
387 0 : FCDUTF8CollationIterator::nextSegment(UErrorCode &errorCode) {
388 0 : if(U_FAILURE(errorCode)) { return FALSE; }
389 0 : U_ASSERT(state == CHECK_FWD && pos != length);
390 : // The input text [start..pos[ passes the FCD check.
391 0 : int32_t segmentStart = pos;
392 : // Collect the characters being checked, in case they need to be normalized.
393 0 : UnicodeString s;
394 0 : uint8_t prevCC = 0;
395 : for(;;) {
396 : // Fetch the next character and its fcd16 value.
397 0 : int32_t cpStart = pos;
398 : UChar32 c;
399 0 : U8_NEXT_OR_FFFD(u8, pos, length, c);
400 0 : uint16_t fcd16 = nfcImpl.getFCD16(c);
401 0 : uint8_t leadCC = (uint8_t)(fcd16 >> 8);
402 0 : if(leadCC == 0 && cpStart != segmentStart) {
403 : // FCD boundary before this character.
404 0 : pos = cpStart;
405 0 : break;
406 : }
407 0 : s.append(c);
408 0 : if(leadCC != 0 && (prevCC > leadCC || CollationFCD::isFCD16OfTibetanCompositeVowel(fcd16))) {
409 : // Fails FCD check. Find the next FCD boundary and normalize.
410 0 : while(pos != length) {
411 0 : cpStart = pos;
412 0 : U8_NEXT_OR_FFFD(u8, pos, length, c);
413 0 : if(nfcImpl.getFCD16(c) <= 0xff) {
414 0 : pos = cpStart;
415 0 : break;
416 : }
417 0 : s.append(c);
418 : }
419 0 : if(!normalize(s, errorCode)) { return FALSE; }
420 0 : start = segmentStart;
421 0 : limit = pos;
422 0 : state = IN_NORMALIZED;
423 0 : pos = 0;
424 0 : return TRUE;
425 : }
426 0 : prevCC = (uint8_t)fcd16;
427 0 : if(pos == length || prevCC == 0) {
428 : // FCD boundary after the last character.
429 : break;
430 : }
431 0 : }
432 0 : limit = pos;
433 0 : pos = segmentStart;
434 0 : U_ASSERT(pos != limit);
435 0 : state = IN_FCD_SEGMENT;
436 0 : return TRUE;
437 : }
438 :
439 : void
440 0 : FCDUTF8CollationIterator::switchToBackward() {
441 0 : U_ASSERT(state == CHECK_FWD ||
442 : (state == IN_FCD_SEGMENT && pos == start) ||
443 : (state >= IN_NORMALIZED && pos == 0));
444 0 : if(state == CHECK_FWD) {
445 : // Turn around from forward checking.
446 0 : limit = pos;
447 0 : if(pos == start) {
448 0 : state = CHECK_BWD; // Check backward.
449 : } else { // pos > start
450 0 : state = IN_FCD_SEGMENT; // Stay in FCD segment.
451 : }
452 : } else {
453 : // Reached the start of the FCD segment.
454 0 : if(state == IN_FCD_SEGMENT) {
455 : // The input text segment is FCD, extend it backward.
456 : } else {
457 : // The input text segment needed to be normalized.
458 : // Switch to checking backward from it.
459 0 : limit = pos = start;
460 : }
461 0 : state = CHECK_BWD;
462 : }
463 0 : }
464 :
465 : UBool
466 0 : FCDUTF8CollationIterator::previousSegment(UErrorCode &errorCode) {
467 0 : if(U_FAILURE(errorCode)) { return FALSE; }
468 0 : U_ASSERT(state == CHECK_BWD && pos != 0);
469 : // The input text [pos..limit[ passes the FCD check.
470 0 : int32_t segmentLimit = pos;
471 : // Collect the characters being checked, in case they need to be normalized.
472 0 : UnicodeString s;
473 0 : uint8_t nextCC = 0;
474 : for(;;) {
475 : // Fetch the previous character and its fcd16 value.
476 0 : int32_t cpLimit = pos;
477 : UChar32 c;
478 0 : U8_PREV_OR_FFFD(u8, 0, pos, c);
479 0 : uint16_t fcd16 = nfcImpl.getFCD16(c);
480 0 : uint8_t trailCC = (uint8_t)fcd16;
481 0 : if(trailCC == 0 && cpLimit != segmentLimit) {
482 : // FCD boundary after this character.
483 0 : pos = cpLimit;
484 0 : break;
485 : }
486 0 : s.append(c);
487 0 : if(trailCC != 0 && ((nextCC != 0 && trailCC > nextCC) ||
488 0 : CollationFCD::isFCD16OfTibetanCompositeVowel(fcd16))) {
489 : // Fails FCD check. Find the previous FCD boundary and normalize.
490 0 : while(fcd16 > 0xff && pos != 0) {
491 0 : cpLimit = pos;
492 0 : U8_PREV_OR_FFFD(u8, 0, pos, c);
493 0 : fcd16 = nfcImpl.getFCD16(c);
494 0 : if(fcd16 == 0) {
495 0 : pos = cpLimit;
496 0 : break;
497 : }
498 0 : s.append(c);
499 : }
500 0 : s.reverse();
501 0 : if(!normalize(s, errorCode)) { return FALSE; }
502 0 : limit = segmentLimit;
503 0 : start = pos;
504 0 : state = IN_NORMALIZED;
505 0 : pos = normalized.length();
506 0 : return TRUE;
507 : }
508 0 : nextCC = (uint8_t)(fcd16 >> 8);
509 0 : if(pos == 0 || nextCC == 0) {
510 : // FCD boundary before the following character.
511 : break;
512 : }
513 0 : }
514 0 : start = pos;
515 0 : pos = segmentLimit;
516 0 : U_ASSERT(pos != start);
517 0 : state = IN_FCD_SEGMENT;
518 0 : return TRUE;
519 : }
520 :
521 : UBool
522 0 : FCDUTF8CollationIterator::normalize(const UnicodeString &s, UErrorCode &errorCode) {
523 : // NFD without argument checking.
524 0 : U_ASSERT(U_SUCCESS(errorCode));
525 0 : nfcImpl.decompose(s, normalized, errorCode);
526 0 : return U_SUCCESS(errorCode);
527 : }
528 :
529 : U_NAMESPACE_END
530 :
531 : #endif // !UCONFIG_NO_COLLATION
|
