1// © 2016 and later: Unicode, Inc. and others.
2// License & terms of use: http://www.unicode.org/copyright.html
3/*
4*******************************************************************************
5* Copyright (C) 2010-2014, International Business Machines
6* Corporation and others. All Rights Reserved.
7*******************************************************************************
8* utf16collationiterator.cpp
9*
10* created on: 2010oct27
11* created by: Markus W. Scherer
12*/
13
14#include "unicode/utypes.h"
15
16#if !UCONFIG_NO_COLLATION
17
18#include "charstr.h"
19#include "cmemory.h"
20#include "collation.h"
21#include "collationdata.h"
22#include "collationfcd.h"
23#include "collationiterator.h"
24#include "normalizer2impl.h"
25#include "uassert.h"
26#include "utf16collationiterator.h"
27
28U_NAMESPACE_BEGIN
29
30UTF16CollationIterator::UTF16CollationIterator(const UTF16CollationIterator &other,
31 const UChar *newText)
32 : CollationIterator(other),
33 start(newText),
34 pos(newText + (other.pos - other.start)),
35 limit(other.limit == NULL ? NULL : newText + (other.limit - other.start)) {
36}
37
38UTF16CollationIterator::~UTF16CollationIterator() {}
39
40UBool
41UTF16CollationIterator::operator==(const CollationIterator &other) const {
42 if(!CollationIterator::operator==(other)) { return FALSE; }
43 const UTF16CollationIterator &o = static_cast<const UTF16CollationIterator &>(other);
44 // Compare the iterator state but not the text: Assume that the caller does that.
45 return (pos - start) == (o.pos - o.start);
46}
47
48void
49UTF16CollationIterator::resetToOffset(int32_t newOffset) {
50 reset();
51 pos = start + newOffset;
52}
53
54int32_t
55UTF16CollationIterator::getOffset() const {
56 return (int32_t)(pos - start);
57}
58
59uint32_t
60UTF16CollationIterator::handleNextCE32(UChar32 &c, UErrorCode & /*errorCode*/) {
61 if(pos == limit) {
62 c = U_SENTINEL;
63 return Collation::FALLBACK_CE32;
64 }
65 c = *pos++;
66 return UTRIE2_GET32_FROM_U16_SINGLE_LEAD(trie, c);
67}
68
69UChar
70UTF16CollationIterator::handleGetTrailSurrogate() {
71 if(pos == limit) { return 0; }
72 UChar trail;
73 if(U16_IS_TRAIL(trail = *pos)) { ++pos; }
74 return trail;
75}
76
77UBool
78UTF16CollationIterator::foundNULTerminator() {
79 if(limit == NULL) {
80 limit = --pos;
81 return TRUE;
82 } else {
83 return FALSE;
84 }
85}
86
87UChar32
88UTF16CollationIterator::nextCodePoint(UErrorCode & /*errorCode*/) {
89 if(pos == limit) {
90 return U_SENTINEL;
91 }
92 UChar32 c = *pos;
93 if(c == 0 && limit == NULL) {
94 limit = pos;
95 return U_SENTINEL;
96 }
97 ++pos;
98 UChar trail;
99 if(U16_IS_LEAD(c) && pos != limit && U16_IS_TRAIL(trail = *pos)) {
100 ++pos;
101 return U16_GET_SUPPLEMENTARY(c, trail);
102 } else {
103 return c;
104 }
105}
106
107UChar32
108UTF16CollationIterator::previousCodePoint(UErrorCode & /*errorCode*/) {
109 if(pos == start) {
110 return U_SENTINEL;
111 }
112 UChar32 c = *--pos;
113 UChar lead;
114 if(U16_IS_TRAIL(c) && pos != start && U16_IS_LEAD(lead = *(pos - 1))) {
115 --pos;
116 return U16_GET_SUPPLEMENTARY(lead, c);
117 } else {
118 return c;
119 }
120}
121
122void
123UTF16CollationIterator::forwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
124 while(num > 0 && pos != limit) {
125 UChar32 c = *pos;
126 if(c == 0 && limit == NULL) {
127 limit = pos;
128 break;
129 }
130 ++pos;
131 --num;
132 if(U16_IS_LEAD(c) && pos != limit && U16_IS_TRAIL(*pos)) {
133 ++pos;
134 }
135 }
136}
137
138void
139UTF16CollationIterator::backwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
140 while(num > 0 && pos != start) {
141 UChar32 c = *--pos;
142 --num;
143 if(U16_IS_TRAIL(c) && pos != start && U16_IS_LEAD(*(pos-1))) {
144 --pos;
145 }
146 }
147}
148
149// FCDUTF16CollationIterator ----------------------------------------------- ***
150
151FCDUTF16CollationIterator::FCDUTF16CollationIterator(const FCDUTF16CollationIterator &other,
152 const UChar *newText)
153 : UTF16CollationIterator(other),
154 rawStart(newText),
155 segmentStart(newText + (other.segmentStart - other.rawStart)),
156 segmentLimit(other.segmentLimit == NULL ? NULL : newText + (other.segmentLimit - other.rawStart)),
157 rawLimit(other.rawLimit == NULL ? NULL : newText + (other.rawLimit - other.rawStart)),
158 nfcImpl(other.nfcImpl),
159 normalized(other.normalized),
160 checkDir(other.checkDir) {
161 if(checkDir != 0 || other.start == other.segmentStart) {
162 start = newText + (other.start - other.rawStart);
163 pos = newText + (other.pos - other.rawStart);
164 limit = other.limit == NULL ? NULL : newText + (other.limit - other.rawStart);
165 } else {
166 start = normalized.getBuffer();
167 pos = start + (other.pos - other.start);
168 limit = start + normalized.length();
169 }
170}
171
172FCDUTF16CollationIterator::~FCDUTF16CollationIterator() {}
173
174UBool
175FCDUTF16CollationIterator::operator==(const CollationIterator &other) const {
176 // Skip the UTF16CollationIterator and call its parent.
177 if(!CollationIterator::operator==(other)) { return FALSE; }
178 const FCDUTF16CollationIterator &o = static_cast<const FCDUTF16CollationIterator &>(other);
179 // Compare the iterator state but not the text: Assume that the caller does that.
180 if(checkDir != o.checkDir) { return FALSE; }
181 if(checkDir == 0 && (start == segmentStart) != (o.start == o.segmentStart)) { return FALSE; }
182 if(checkDir != 0 || start == segmentStart) {
183 return (pos - rawStart) == (o.pos - o.rawStart);
184 } else {
185 return (segmentStart - rawStart) == (o.segmentStart - o.rawStart) &&
186 (pos - start) == (o.pos - o.start);
187 }
188}
189
190void
191FCDUTF16CollationIterator::resetToOffset(int32_t newOffset) {
192 reset();
193 start = segmentStart = pos = rawStart + newOffset;
194 limit = rawLimit;
195 checkDir = 1;
196}
197
198int32_t
199FCDUTF16CollationIterator::getOffset() const {
200 if(checkDir != 0 || start == segmentStart) {
201 return (int32_t)(pos - rawStart);
202 } else if(pos == start) {
203 return (int32_t)(segmentStart - rawStart);
204 } else {
205 return (int32_t)(segmentLimit - rawStart);
206 }
207}
208
209uint32_t
210FCDUTF16CollationIterator::handleNextCE32(UChar32 &c, UErrorCode &errorCode) {
211 for(;;) {
212 if(checkDir > 0) {
213 if(pos == limit) {
214 c = U_SENTINEL;
215 return Collation::FALLBACK_CE32;
216 }
217 c = *pos++;
218 if(CollationFCD::hasTccc(c)) {
219 if(CollationFCD::maybeTibetanCompositeVowel(c) ||
220 (pos != limit && CollationFCD::hasLccc(*pos))) {
221 --pos;
222 if(!nextSegment(errorCode)) {
223 c = U_SENTINEL;
224 return Collation::FALLBACK_CE32;
225 }
226 c = *pos++;
227 }
228 }
229 break;
230 } else if(checkDir == 0 && pos != limit) {
231 c = *pos++;
232 break;
233 } else {
234 switchToForward();
235 }
236 }
237 return UTRIE2_GET32_FROM_U16_SINGLE_LEAD(trie, c);
238}
239
240UBool
241FCDUTF16CollationIterator::foundNULTerminator() {
242 if(limit == NULL) {
243 limit = rawLimit = --pos;
244 return TRUE;
245 } else {
246 return FALSE;
247 }
248}
249
250UChar32
251FCDUTF16CollationIterator::nextCodePoint(UErrorCode &errorCode) {
252 UChar32 c;
253 for(;;) {
254 if(checkDir > 0) {
255 if(pos == limit) {
256 return U_SENTINEL;
257 }
258 c = *pos++;
259 if(CollationFCD::hasTccc(c)) {
260 if(CollationFCD::maybeTibetanCompositeVowel(c) ||
261 (pos != limit && CollationFCD::hasLccc(*pos))) {
262 --pos;
263 if(!nextSegment(errorCode)) {
264 return U_SENTINEL;
265 }
266 c = *pos++;
267 }
268 } else if(c == 0 && limit == NULL) {
269 limit = rawLimit = --pos;
270 return U_SENTINEL;
271 }
272 break;
273 } else if(checkDir == 0 && pos != limit) {
274 c = *pos++;
275 break;
276 } else {
277 switchToForward();
278 }
279 }
280 UChar trail;
281 if(U16_IS_LEAD(c) && pos != limit && U16_IS_TRAIL(trail = *pos)) {
282 ++pos;
283 return U16_GET_SUPPLEMENTARY(c, trail);
284 } else {
285 return c;
286 }
287}
288
289UChar32
290FCDUTF16CollationIterator::previousCodePoint(UErrorCode &errorCode) {
291 UChar32 c;
292 for(;;) {
293 if(checkDir < 0) {
294 if(pos == start) {
295 return U_SENTINEL;
296 }
297 c = *--pos;
298 if(CollationFCD::hasLccc(c)) {
299 if(CollationFCD::maybeTibetanCompositeVowel(c) ||
300 (pos != start && CollationFCD::hasTccc(*(pos - 1)))) {
301 ++pos;
302 if(!previousSegment(errorCode)) {
303 return U_SENTINEL;
304 }
305 c = *--pos;
306 }
307 }
308 break;
309 } else if(checkDir == 0 && pos != start) {
310 c = *--pos;
311 break;
312 } else {
313 switchToBackward();
314 }
315 }
316 UChar lead;
317 if(U16_IS_TRAIL(c) && pos != start && U16_IS_LEAD(lead = *(pos - 1))) {
318 --pos;
319 return U16_GET_SUPPLEMENTARY(lead, c);
320 } else {
321 return c;
322 }
323}
324
325void
326FCDUTF16CollationIterator::forwardNumCodePoints(int32_t num, UErrorCode &errorCode) {
327 // Specify the class to avoid a virtual-function indirection.
328 // In Java, we would declare this class final.
329 while(num > 0 && FCDUTF16CollationIterator::nextCodePoint(errorCode) >= 0) {
330 --num;
331 }
332}
333
334void
335FCDUTF16CollationIterator::backwardNumCodePoints(int32_t num, UErrorCode &errorCode) {
336 // Specify the class to avoid a virtual-function indirection.
337 // In Java, we would declare this class final.
338 while(num > 0 && FCDUTF16CollationIterator::previousCodePoint(errorCode) >= 0) {
339 --num;
340 }
341}
342
343void
344FCDUTF16CollationIterator::switchToForward() {
345 U_ASSERT(checkDir < 0 || (checkDir == 0 && pos == limit));
346 if(checkDir < 0) {
347 // Turn around from backward checking.
348 start = segmentStart = pos;
349 if(pos == segmentLimit) {
350 limit = rawLimit;
351 checkDir = 1; // Check forward.
352 } else { // pos < segmentLimit
353 checkDir = 0; // Stay in FCD segment.
354 }
355 } else {
356 // Reached the end of the FCD segment.
357 if(start == segmentStart) {
358 // The input text segment is FCD, extend it forward.
359 } else {
360 // The input text segment needed to be normalized.
361 // Switch to checking forward from it.
362 pos = start = segmentStart = segmentLimit;
363 // Note: If this segment is at the end of the input text,
364 // then it might help to return FALSE to indicate that, so that
365 // we do not have to re-check and normalize when we turn around and go backwards.
366 // However, that would complicate the call sites for an optimization of an unusual case.
367 }
368 limit = rawLimit;
369 checkDir = 1;
370 }
371}
372
373UBool
374FCDUTF16CollationIterator::nextSegment(UErrorCode &errorCode) {
375 if(U_FAILURE(errorCode)) { return FALSE; }
376 U_ASSERT(checkDir > 0 && pos != limit);
377 // The input text [segmentStart..pos[ passes the FCD check.
378 const UChar *p = pos;
379 uint8_t prevCC = 0;
380 for(;;) {
381 // Fetch the next character's fcd16 value.
382 const UChar *q = p;
383 uint16_t fcd16 = nfcImpl.nextFCD16(p, rawLimit);
384 uint8_t leadCC = (uint8_t)(fcd16 >> 8);
385 if(leadCC == 0 && q != pos) {
386 // FCD boundary before the [q, p[ character.
387 limit = segmentLimit = q;
388 break;
389 }
390 if(leadCC != 0 && (prevCC > leadCC || CollationFCD::isFCD16OfTibetanCompositeVowel(fcd16))) {
391 // Fails FCD check. Find the next FCD boundary and normalize.
392 do {
393 q = p;
394 } while(p != rawLimit && nfcImpl.nextFCD16(p, rawLimit) > 0xff);
395 if(!normalize(pos, q, errorCode)) { return FALSE; }
396 pos = start;
397 break;
398 }
399 prevCC = (uint8_t)fcd16;
400 if(p == rawLimit || prevCC == 0) {
401 // FCD boundary after the last character.
402 limit = segmentLimit = p;
403 break;
404 }
405 }
406 U_ASSERT(pos != limit);
407 checkDir = 0;
408 return TRUE;
409}
410
411void
412FCDUTF16CollationIterator::switchToBackward() {
413 U_ASSERT(checkDir > 0 || (checkDir == 0 && pos == start));
414 if(checkDir > 0) {
415 // Turn around from forward checking.
416 limit = segmentLimit = pos;
417 if(pos == segmentStart) {
418 start = rawStart;
419 checkDir = -1; // Check backward.
420 } else { // pos > segmentStart
421 checkDir = 0; // Stay in FCD segment.
422 }
423 } else {
424 // Reached the start of the FCD segment.
425 if(start == segmentStart) {
426 // The input text segment is FCD, extend it backward.
427 } else {
428 // The input text segment needed to be normalized.
429 // Switch to checking backward from it.
430 pos = limit = segmentLimit = segmentStart;
431 }
432 start = rawStart;
433 checkDir = -1;
434 }
435}
436
437UBool
438FCDUTF16CollationIterator::previousSegment(UErrorCode &errorCode) {
439 if(U_FAILURE(errorCode)) { return FALSE; }
440 U_ASSERT(checkDir < 0 && pos != start);
441 // The input text [pos..segmentLimit[ passes the FCD check.
442 const UChar *p = pos;
443 uint8_t nextCC = 0;
444 for(;;) {
445 // Fetch the previous character's fcd16 value.
446 const UChar *q = p;
447 uint16_t fcd16 = nfcImpl.previousFCD16(rawStart, p);
448 uint8_t trailCC = (uint8_t)fcd16;
449 if(trailCC == 0 && q != pos) {
450 // FCD boundary after the [p, q[ character.
451 start = segmentStart = q;
452 break;
453 }
454 if(trailCC != 0 && ((nextCC != 0 && trailCC > nextCC) ||
455 CollationFCD::isFCD16OfTibetanCompositeVowel(fcd16))) {
456 // Fails FCD check. Find the previous FCD boundary and normalize.
457 do {
458 q = p;
459 } while(fcd16 > 0xff && p != rawStart &&
460 (fcd16 = nfcImpl.previousFCD16(rawStart, p)) != 0);
461 if(!normalize(q, pos, errorCode)) { return FALSE; }
462 pos = limit;
463 break;
464 }
465 nextCC = (uint8_t)(fcd16 >> 8);
466 if(p == rawStart || nextCC == 0) {
467 // FCD boundary before the following character.
468 start = segmentStart = p;
469 break;
470 }
471 }
472 U_ASSERT(pos != start);
473 checkDir = 0;
474 return TRUE;
475}
476
477UBool
478FCDUTF16CollationIterator::normalize(const UChar *from, const UChar *to, UErrorCode &errorCode) {
479 // NFD without argument checking.
480 U_ASSERT(U_SUCCESS(errorCode));
481 nfcImpl.decompose(from, to, normalized, (int32_t)(to - from), errorCode);
482 if(U_FAILURE(errorCode)) { return FALSE; }
483 // Switch collation processing into the FCD buffer
484 // with the result of normalizing [segmentStart, segmentLimit[.
485 segmentStart = from;
486 segmentLimit = to;
487 start = normalized.getBuffer();
488 limit = start + normalized.length();
489 return TRUE;
490}
491
492U_NAMESPACE_END
493
494#endif // !UCONFIG_NO_COLLATION
495