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* collationiterator.cpp
9*
10* created on: 2010oct27
11* created by: Markus W. Scherer
12*/
13
14#include "utypeinfo.h" // for 'typeid' to work
15
16#include "unicode/utypes.h"
17
18#if !UCONFIG_NO_COLLATION
19
20#include "unicode/ucharstrie.h"
21#include "unicode/ustringtrie.h"
22#include "charstr.h"
23#include "cmemory.h"
24#include "collation.h"
25#include "collationdata.h"
26#include "collationfcd.h"
27#include "collationiterator.h"
28#include "normalizer2impl.h"
29#include "uassert.h"
30#include "uvectr32.h"
31
32U_NAMESPACE_BEGIN
33
34CollationIterator::CEBuffer::~CEBuffer() {}
35
36UBool
37CollationIterator::CEBuffer::ensureAppendCapacity(int32_t appCap, UErrorCode &errorCode) {
38 int32_t capacity = buffer.getCapacity();
39 if((length + appCap) <= capacity) { return TRUE; }
40 if(U_FAILURE(errorCode)) { return FALSE; }
41 do {
42 if(capacity < 1000) {
43 capacity *= 4;
44 } else {
45 capacity *= 2;
46 }
47 } while(capacity < (length + appCap));
48 int64_t *p = buffer.resize(capacity, length);
49 if(p == NULL) {
50 errorCode = U_MEMORY_ALLOCATION_ERROR;
51 return FALSE;
52 }
53 return TRUE;
54}
55
56// State of combining marks skipped in discontiguous contraction.
57// We create a state object on first use and keep it around deactivated between uses.
58class SkippedState : public UMemory {
59public:
60 // Born active but empty.
61 SkippedState() : pos(0), skipLengthAtMatch(0) {}
62 void clear() {
63 oldBuffer.remove();
64 pos = 0;
65 // The newBuffer is reset by setFirstSkipped().
66 }
67
68 UBool isEmpty() const { return oldBuffer.isEmpty(); }
69
70 UBool hasNext() const { return pos < oldBuffer.length(); }
71
72 // Requires hasNext().
73 UChar32 next() {
74 UChar32 c = oldBuffer.char32At(pos);
75 pos += U16_LENGTH(c);
76 return c;
77 }
78
79 // Accounts for one more input code point read beyond the end of the marks buffer.
80 void incBeyond() {
81 U_ASSERT(!hasNext());
82 ++pos;
83 }
84
85 // Goes backward through the skipped-marks buffer.
86 // Returns the number of code points read beyond the skipped marks
87 // that need to be backtracked through normal input.
88 int32_t backwardNumCodePoints(int32_t n) {
89 int32_t length = oldBuffer.length();
90 int32_t beyond = pos - length;
91 if(beyond > 0) {
92 if(beyond >= n) {
93 // Not back far enough to re-enter the oldBuffer.
94 pos -= n;
95 return n;
96 } else {
97 // Back out all beyond-oldBuffer code points and re-enter the buffer.
98 pos = oldBuffer.moveIndex32(length, beyond - n);
99 return beyond;
100 }
101 } else {
102 // Go backwards from inside the oldBuffer.
103 pos = oldBuffer.moveIndex32(pos, -n);
104 return 0;
105 }
106 }
107
108 void setFirstSkipped(UChar32 c) {
109 skipLengthAtMatch = 0;
110 newBuffer.setTo(c);
111 }
112
113 void skip(UChar32 c) {
114 newBuffer.append(c);
115 }
116
117 void recordMatch() { skipLengthAtMatch = newBuffer.length(); }
118
119 // Replaces the characters we consumed with the newly skipped ones.
120 void replaceMatch() {
121 // Note: UnicodeString.replace() pins pos to at most length().
122 oldBuffer.replace(0, pos, newBuffer, 0, skipLengthAtMatch);
123 pos = 0;
124 }
125
126 void saveTrieState(const UCharsTrie &trie) { trie.saveState(state); }
127 void resetToTrieState(UCharsTrie &trie) const { trie.resetToState(state); }
128
129private:
130 // Combining marks skipped in previous discontiguous-contraction matching.
131 // After that discontiguous contraction was completed, we start reading them from here.
132 UnicodeString oldBuffer;
133 // Combining marks newly skipped in current discontiguous-contraction matching.
134 // These might have been read from the normal text or from the oldBuffer.
135 UnicodeString newBuffer;
136 // Reading index in oldBuffer,
137 // or counter for how many code points have been read beyond oldBuffer (pos-oldBuffer.length()).
138 int32_t pos;
139 // newBuffer.length() at the time of the last matching character.
140 // When a partial match fails, we back out skipped and partial-matching input characters.
141 int32_t skipLengthAtMatch;
142 // We save the trie state before we attempt to match a character,
143 // so that we can skip it and try the next one.
144 UCharsTrie::State state;
145};
146
147CollationIterator::CollationIterator(const CollationIterator &other)
148 : UObject(other),
149 trie(other.trie),
150 data(other.data),
151 cesIndex(other.cesIndex),
152 skipped(NULL),
153 numCpFwd(other.numCpFwd),
154 isNumeric(other.isNumeric) {
155 UErrorCode errorCode = U_ZERO_ERROR;
156 int32_t length = other.ceBuffer.length;
157 if(length > 0 && ceBuffer.ensureAppendCapacity(length, errorCode)) {
158 for(int32_t i = 0; i < length; ++i) {
159 ceBuffer.set(i, other.ceBuffer.get(i));
160 }
161 ceBuffer.length = length;
162 } else {
163 cesIndex = 0;
164 }
165}
166
167CollationIterator::~CollationIterator() {
168 delete skipped;
169}
170
171UBool
172CollationIterator::operator==(const CollationIterator &other) const {
173 // Subclasses: Call this method and then add more specific checks.
174 // Compare the iterator state but not the collation data (trie & data fields):
175 // Assume that the caller compares the data.
176 // Ignore skipped since that should be unused between calls to nextCE().
177 // (It only stays around to avoid another memory allocation.)
178 if(!(typeid(*this) == typeid(other) &&
179 ceBuffer.length == other.ceBuffer.length &&
180 cesIndex == other.cesIndex &&
181 numCpFwd == other.numCpFwd &&
182 isNumeric == other.isNumeric)) {
183 return FALSE;
184 }
185 for(int32_t i = 0; i < ceBuffer.length; ++i) {
186 if(ceBuffer.get(i) != other.ceBuffer.get(i)) { return FALSE; }
187 }
188 return TRUE;
189}
190
191void
192CollationIterator::reset() {
193 cesIndex = ceBuffer.length = 0;
194 if(skipped != NULL) { skipped->clear(); }
195}
196
197int32_t
198CollationIterator::fetchCEs(UErrorCode &errorCode) {
199 while(U_SUCCESS(errorCode) && nextCE(errorCode) != Collation::NO_CE) {
200 // No need to loop for each expansion CE.
201 cesIndex = ceBuffer.length;
202 }
203 return ceBuffer.length;
204}
205
206uint32_t
207CollationIterator::handleNextCE32(UChar32 &c, UErrorCode &errorCode) {
208 c = nextCodePoint(errorCode);
209 return (c < 0) ? Collation::FALLBACK_CE32 : data->getCE32(c);
210}
211
212UChar
213CollationIterator::handleGetTrailSurrogate() {
214 return 0;
215}
216
217UBool
218CollationIterator::foundNULTerminator() {
219 return FALSE;
220}
221
222UBool
223CollationIterator::forbidSurrogateCodePoints() const {
224 return FALSE;
225}
226
227uint32_t
228CollationIterator::getDataCE32(UChar32 c) const {
229 return data->getCE32(c);
230}
231
232uint32_t
233CollationIterator::getCE32FromBuilderData(uint32_t /*ce32*/, UErrorCode &errorCode) {
234 if(U_SUCCESS(errorCode)) { errorCode = U_INTERNAL_PROGRAM_ERROR; }
235 return 0;
236}
237
238int64_t
239CollationIterator::nextCEFromCE32(const CollationData *d, UChar32 c, uint32_t ce32,
240 UErrorCode &errorCode) {
241 --ceBuffer.length; // Undo ceBuffer.incLength().
242 appendCEsFromCE32(d, c, ce32, TRUE, errorCode);
243 if(U_SUCCESS(errorCode)) {
244 return ceBuffer.get(cesIndex++);
245 } else {
246 return Collation::NO_CE_PRIMARY;
247 }
248}
249
250void
251CollationIterator::appendCEsFromCE32(const CollationData *d, UChar32 c, uint32_t ce32,
252 UBool forward, UErrorCode &errorCode) {
253 while(Collation::isSpecialCE32(ce32)) {
254 switch(Collation::tagFromCE32(ce32)) {
255 case Collation::FALLBACK_TAG:
256 case Collation::RESERVED_TAG_3:
257 if(U_SUCCESS(errorCode)) { errorCode = U_INTERNAL_PROGRAM_ERROR; }
258 return;
259 case Collation::LONG_PRIMARY_TAG:
260 ceBuffer.append(Collation::ceFromLongPrimaryCE32(ce32), errorCode);
261 return;
262 case Collation::LONG_SECONDARY_TAG:
263 ceBuffer.append(Collation::ceFromLongSecondaryCE32(ce32), errorCode);
264 return;
265 case Collation::LATIN_EXPANSION_TAG:
266 if(ceBuffer.ensureAppendCapacity(2, errorCode)) {
267 ceBuffer.set(ceBuffer.length, Collation::latinCE0FromCE32(ce32));
268 ceBuffer.set(ceBuffer.length + 1, Collation::latinCE1FromCE32(ce32));
269 ceBuffer.length += 2;
270 }
271 return;
272 case Collation::EXPANSION32_TAG: {
273 const uint32_t *ce32s = d->ce32s + Collation::indexFromCE32(ce32);
274 int32_t length = Collation::lengthFromCE32(ce32);
275 if(ceBuffer.ensureAppendCapacity(length, errorCode)) {
276 do {
277 ceBuffer.appendUnsafe(Collation::ceFromCE32(*ce32s++));
278 } while(--length > 0);
279 }
280 return;
281 }
282 case Collation::EXPANSION_TAG: {
283 const int64_t *ces = d->ces + Collation::indexFromCE32(ce32);
284 int32_t length = Collation::lengthFromCE32(ce32);
285 if(ceBuffer.ensureAppendCapacity(length, errorCode)) {
286 do {
287 ceBuffer.appendUnsafe(*ces++);
288 } while(--length > 0);
289 }
290 return;
291 }
292 case Collation::BUILDER_DATA_TAG:
293 ce32 = getCE32FromBuilderData(ce32, errorCode);
294 if(U_FAILURE(errorCode)) { return; }
295 if(ce32 == Collation::FALLBACK_CE32) {
296 d = data->base;
297 ce32 = d->getCE32(c);
298 }
299 break;
300 case Collation::PREFIX_TAG:
301 if(forward) { backwardNumCodePoints(1, errorCode); }
302 ce32 = getCE32FromPrefix(d, ce32, errorCode);
303 if(forward) { forwardNumCodePoints(1, errorCode); }
304 break;
305 case Collation::CONTRACTION_TAG: {
306 const UChar *p = d->contexts + Collation::indexFromCE32(ce32);
307 uint32_t defaultCE32 = CollationData::readCE32(p); // Default if no suffix match.
308 if(!forward) {
309 // Backward contractions are handled by previousCEUnsafe().
310 // c has contractions but they were not found.
311 ce32 = defaultCE32;
312 break;
313 }
314 UChar32 nextCp;
315 if(skipped == NULL && numCpFwd < 0) {
316 // Some portion of nextCE32FromContraction() pulled out here as an ASCII fast path,
317 // avoiding the function call and the nextSkippedCodePoint() overhead.
318 nextCp = nextCodePoint(errorCode);
319 if(nextCp < 0) {
320 // No more text.
321 ce32 = defaultCE32;
322 break;
323 } else if((ce32 & Collation::CONTRACT_NEXT_CCC) != 0 &&
324 !CollationFCD::mayHaveLccc(nextCp)) {
325 // All contraction suffixes start with characters with lccc!=0
326 // but the next code point has lccc==0.
327 backwardNumCodePoints(1, errorCode);
328 ce32 = defaultCE32;
329 break;
330 }
331 } else {
332 nextCp = nextSkippedCodePoint(errorCode);
333 if(nextCp < 0) {
334 // No more text.
335 ce32 = defaultCE32;
336 break;
337 } else if((ce32 & Collation::CONTRACT_NEXT_CCC) != 0 &&
338 !CollationFCD::mayHaveLccc(nextCp)) {
339 // All contraction suffixes start with characters with lccc!=0
340 // but the next code point has lccc==0.
341 backwardNumSkipped(1, errorCode);
342 ce32 = defaultCE32;
343 break;
344 }
345 }
346 ce32 = nextCE32FromContraction(d, ce32, p + 2, defaultCE32, nextCp, errorCode);
347 if(ce32 == Collation::NO_CE32) {
348 // CEs from a discontiguous contraction plus the skipped combining marks
349 // have been appended already.
350 return;
351 }
352 break;
353 }
354 case Collation::DIGIT_TAG:
355 if(isNumeric) {
356 appendNumericCEs(ce32, forward, errorCode);
357 return;
358 } else {
359 // Fetch the non-numeric-collation CE32 and continue.
360 ce32 = d->ce32s[Collation::indexFromCE32(ce32)];
361 break;
362 }
363 case Collation::U0000_TAG:
364 U_ASSERT(c == 0);
365 if(forward && foundNULTerminator()) {
366 // Handle NUL-termination. (Not needed in Java.)
367 ceBuffer.append(Collation::NO_CE, errorCode);
368 return;
369 } else {
370 // Fetch the normal ce32 for U+0000 and continue.
371 ce32 = d->ce32s[0];
372 break;
373 }
374 case Collation::HANGUL_TAG: {
375 const uint32_t *jamoCE32s = d->jamoCE32s;
376 c -= Hangul::HANGUL_BASE;
377 UChar32 t = c % Hangul::JAMO_T_COUNT;
378 c /= Hangul::JAMO_T_COUNT;
379 UChar32 v = c % Hangul::JAMO_V_COUNT;
380 c /= Hangul::JAMO_V_COUNT;
381 if((ce32 & Collation::HANGUL_NO_SPECIAL_JAMO) != 0) {
382 // None of the Jamo CE32s are isSpecialCE32().
383 // Avoid recursive function calls and per-Jamo tests.
384 if(ceBuffer.ensureAppendCapacity(t == 0 ? 2 : 3, errorCode)) {
385 ceBuffer.set(ceBuffer.length, Collation::ceFromCE32(jamoCE32s[c]));
386 ceBuffer.set(ceBuffer.length + 1, Collation::ceFromCE32(jamoCE32s[19 + v]));
387 ceBuffer.length += 2;
388 if(t != 0) {
389 ceBuffer.appendUnsafe(Collation::ceFromCE32(jamoCE32s[39 + t]));
390 }
391 }
392 return;
393 } else {
394 // We should not need to compute each Jamo code point.
395 // In particular, there should be no offset or implicit ce32.
396 appendCEsFromCE32(d, U_SENTINEL, jamoCE32s[c], forward, errorCode);
397 appendCEsFromCE32(d, U_SENTINEL, jamoCE32s[19 + v], forward, errorCode);
398 if(t == 0) { return; }
399 // offset 39 = 19 + 21 - 1:
400 // 19 = JAMO_L_COUNT
401 // 21 = JAMO_T_COUNT
402 // -1 = omit t==0
403 ce32 = jamoCE32s[39 + t];
404 c = U_SENTINEL;
405 break;
406 }
407 }
408 case Collation::LEAD_SURROGATE_TAG: {
409 U_ASSERT(forward); // Backward iteration should never see lead surrogate code _unit_ data.
410 U_ASSERT(U16_IS_LEAD(c));
411 UChar trail;
412 if(U16_IS_TRAIL(trail = handleGetTrailSurrogate())) {
413 c = U16_GET_SUPPLEMENTARY(c, trail);
414 ce32 &= Collation::LEAD_TYPE_MASK;
415 if(ce32 == Collation::LEAD_ALL_UNASSIGNED) {
416 ce32 = Collation::UNASSIGNED_CE32; // unassigned-implicit
417 } else if(ce32 == Collation::LEAD_ALL_FALLBACK ||
418 (ce32 = d->getCE32FromSupplementary(c)) == Collation::FALLBACK_CE32) {
419 // fall back to the base data
420 d = d->base;
421 ce32 = d->getCE32FromSupplementary(c);
422 }
423 } else {
424 // c is an unpaired surrogate.
425 ce32 = Collation::UNASSIGNED_CE32;
426 }
427 break;
428 }
429 case Collation::OFFSET_TAG:
430 U_ASSERT(c >= 0);
431 ceBuffer.append(d->getCEFromOffsetCE32(c, ce32), errorCode);
432 return;
433 case Collation::IMPLICIT_TAG:
434 U_ASSERT(c >= 0);
435 if(U_IS_SURROGATE(c) && forbidSurrogateCodePoints()) {
436 ce32 = Collation::FFFD_CE32;
437 break;
438 } else {
439 ceBuffer.append(Collation::unassignedCEFromCodePoint(c), errorCode);
440 return;
441 }
442 }
443 }
444 ceBuffer.append(Collation::ceFromSimpleCE32(ce32), errorCode);
445}
446
447uint32_t
448CollationIterator::getCE32FromPrefix(const CollationData *d, uint32_t ce32,
449 UErrorCode &errorCode) {
450 const UChar *p = d->contexts + Collation::indexFromCE32(ce32);
451 ce32 = CollationData::readCE32(p); // Default if no prefix match.
452 p += 2;
453 // Number of code points read before the original code point.
454 int32_t lookBehind = 0;
455 UCharsTrie prefixes(p);
456 for(;;) {
457 UChar32 c = previousCodePoint(errorCode);
458 if(c < 0) { break; }
459 ++lookBehind;
460 UStringTrieResult match = prefixes.nextForCodePoint(c);
461 if(USTRINGTRIE_HAS_VALUE(match)) {
462 ce32 = (uint32_t)prefixes.getValue();
463 }
464 if(!USTRINGTRIE_HAS_NEXT(match)) { break; }
465 }
466 forwardNumCodePoints(lookBehind, errorCode);
467 return ce32;
468}
469
470UChar32
471CollationIterator::nextSkippedCodePoint(UErrorCode &errorCode) {
472 if(skipped != NULL && skipped->hasNext()) { return skipped->next(); }
473 if(numCpFwd == 0) { return U_SENTINEL; }
474 UChar32 c = nextCodePoint(errorCode);
475 if(skipped != NULL && !skipped->isEmpty() && c >= 0) { skipped->incBeyond(); }
476 if(numCpFwd > 0 && c >= 0) { --numCpFwd; }
477 return c;
478}
479
480void
481CollationIterator::backwardNumSkipped(int32_t n, UErrorCode &errorCode) {
482 if(skipped != NULL && !skipped->isEmpty()) {
483 n = skipped->backwardNumCodePoints(n);
484 }
485 backwardNumCodePoints(n, errorCode);
486 if(numCpFwd >= 0) { numCpFwd += n; }
487}
488
489uint32_t
490CollationIterator::nextCE32FromContraction(const CollationData *d, uint32_t contractionCE32,
491 const UChar *p, uint32_t ce32, UChar32 c,
492 UErrorCode &errorCode) {
493 // c: next code point after the original one
494
495 // Number of code points read beyond the original code point.
496 // Needed for discontiguous contraction matching.
497 int32_t lookAhead = 1;
498 // Number of code points read since the last match (initially only c).
499 int32_t sinceMatch = 1;
500 // Normally we only need a contiguous match,
501 // and therefore need not remember the suffixes state from before a mismatch for retrying.
502 // If we are already processing skipped combining marks, then we do track the state.
503 UCharsTrie suffixes(p);
504 if(skipped != NULL && !skipped->isEmpty()) { skipped->saveTrieState(suffixes); }
505 UStringTrieResult match = suffixes.firstForCodePoint(c);
506 for(;;) {
507 UChar32 nextCp;
508 if(USTRINGTRIE_HAS_VALUE(match)) {
509 ce32 = (uint32_t)suffixes.getValue();
510 if(!USTRINGTRIE_HAS_NEXT(match) || (c = nextSkippedCodePoint(errorCode)) < 0) {
511 return ce32;
512 }
513 if(skipped != NULL && !skipped->isEmpty()) { skipped->saveTrieState(suffixes); }
514 sinceMatch = 1;
515 } else if(match == USTRINGTRIE_NO_MATCH || (nextCp = nextSkippedCodePoint(errorCode)) < 0) {
516 // No match for c, or partial match (USTRINGTRIE_NO_VALUE) and no further text.
517 // Back up if necessary, and try a discontiguous contraction.
518 if((contractionCE32 & Collation::CONTRACT_TRAILING_CCC) != 0 &&
519 // Discontiguous contraction matching extends an existing match.
520 // If there is no match yet, then there is nothing to do.
521 ((contractionCE32 & Collation::CONTRACT_SINGLE_CP_NO_MATCH) == 0 ||
522 sinceMatch < lookAhead)) {
523 // The last character of at least one suffix has lccc!=0,
524 // allowing for discontiguous contractions.
525 // UCA S2.1.1 only processes non-starters immediately following
526 // "a match in the table" (sinceMatch=1).
527 if(sinceMatch > 1) {
528 // Return to the state after the last match.
529 // (Return to sinceMatch=0 and re-fetch the first partially-matched character.)
530 backwardNumSkipped(sinceMatch, errorCode);
531 c = nextSkippedCodePoint(errorCode);
532 lookAhead -= sinceMatch - 1;
533 sinceMatch = 1;
534 }
535 if(d->getFCD16(c) > 0xff) {
536 return nextCE32FromDiscontiguousContraction(
537 d, suffixes, ce32, lookAhead, c, errorCode);
538 }
539 }
540 break;
541 } else {
542 // Continue after partial match (USTRINGTRIE_NO_VALUE) for c.
543 // It does not have a result value, therefore it is not itself "a match in the table".
544 // If a partially-matched c has ccc!=0 then
545 // it might be skipped in discontiguous contraction.
546 c = nextCp;
547 ++sinceMatch;
548 }
549 ++lookAhead;
550 match = suffixes.nextForCodePoint(c);
551 }
552 backwardNumSkipped(sinceMatch, errorCode);
553 return ce32;
554}
555
556uint32_t
557CollationIterator::nextCE32FromDiscontiguousContraction(
558 const CollationData *d, UCharsTrie &suffixes, uint32_t ce32,
559 int32_t lookAhead, UChar32 c,
560 UErrorCode &errorCode) {
561 if(U_FAILURE(errorCode)) { return 0; }
562
563 // UCA section 3.3.2 Contractions:
564 // Contractions that end with non-starter characters
565 // are known as discontiguous contractions.
566 // ... discontiguous contractions must be detected in input text
567 // whenever the final sequence of non-starter characters could be rearranged
568 // so as to make a contiguous matching sequence that is canonically equivalent.
569
570 // UCA: http://www.unicode.org/reports/tr10/#S2.1
571 // S2.1 Find the longest initial substring S at each point that has a match in the table.
572 // S2.1.1 If there are any non-starters following S, process each non-starter C.
573 // S2.1.2 If C is not blocked from S, find if S + C has a match in the table.
574 // Note: A non-starter in a string is called blocked
575 // if there is another non-starter of the same canonical combining class or zero
576 // between it and the last character of canonical combining class 0.
577 // S2.1.3 If there is a match, replace S by S + C, and remove C.
578
579 // First: Is a discontiguous contraction even possible?
580 uint16_t fcd16 = d->getFCD16(c);
581 U_ASSERT(fcd16 > 0xff); // The caller checked this already, as a shortcut.
582 UChar32 nextCp = nextSkippedCodePoint(errorCode);
583 if(nextCp < 0) {
584 // No further text.
585 backwardNumSkipped(1, errorCode);
586 return ce32;
587 }
588 ++lookAhead;
589 uint8_t prevCC = (uint8_t)fcd16;
590 fcd16 = d->getFCD16(nextCp);
591 if(fcd16 <= 0xff) {
592 // The next code point after c is a starter (S2.1.1 "process each non-starter").
593 backwardNumSkipped(2, errorCode);
594 return ce32;
595 }
596
597 // We have read and matched (lookAhead-2) code points,
598 // read non-matching c and peeked ahead at nextCp.
599 // Return to the state before the mismatch and continue matching with nextCp.
600 if(skipped == NULL || skipped->isEmpty()) {
601 if(skipped == NULL) {
602 skipped = new SkippedState();
603 if(skipped == NULL) {
604 errorCode = U_MEMORY_ALLOCATION_ERROR;
605 return 0;
606 }
607 }
608 suffixes.reset();
609 if(lookAhead > 2) {
610 // Replay the partial match so far.
611 backwardNumCodePoints(lookAhead, errorCode);
612 suffixes.firstForCodePoint(nextCodePoint(errorCode));
613 for(int32_t i = 3; i < lookAhead; ++i) {
614 suffixes.nextForCodePoint(nextCodePoint(errorCode));
615 }
616 // Skip c (which did not match) and nextCp (which we will try now).
617 forwardNumCodePoints(2, errorCode);
618 }
619 skipped->saveTrieState(suffixes);
620 } else {
621 // Reset to the trie state before the failed match of c.
622 skipped->resetToTrieState(suffixes);
623 }
624
625 skipped->setFirstSkipped(c);
626 // Number of code points read since the last match (at this point: c and nextCp).
627 int32_t sinceMatch = 2;
628 c = nextCp;
629 for(;;) {
630 UStringTrieResult match;
631 // "If C is not blocked from S, find if S + C has a match in the table." (S2.1.2)
632 if(prevCC < (fcd16 >> 8) && USTRINGTRIE_HAS_VALUE(match = suffixes.nextForCodePoint(c))) {
633 // "If there is a match, replace S by S + C, and remove C." (S2.1.3)
634 // Keep prevCC unchanged.
635 ce32 = (uint32_t)suffixes.getValue();
636 sinceMatch = 0;
637 skipped->recordMatch();
638 if(!USTRINGTRIE_HAS_NEXT(match)) { break; }
639 skipped->saveTrieState(suffixes);
640 } else {
641 // No match for "S + C", skip C.
642 skipped->skip(c);
643 skipped->resetToTrieState(suffixes);
644 prevCC = (uint8_t)fcd16;
645 }
646 if((c = nextSkippedCodePoint(errorCode)) < 0) { break; }
647 ++sinceMatch;
648 fcd16 = d->getFCD16(c);
649 if(fcd16 <= 0xff) {
650 // The next code point after c is a starter (S2.1.1 "process each non-starter").
651 break;
652 }
653 }
654 backwardNumSkipped(sinceMatch, errorCode);
655 UBool isTopDiscontiguous = skipped->isEmpty();
656 skipped->replaceMatch();
657 if(isTopDiscontiguous && !skipped->isEmpty()) {
658 // We did get a match after skipping one or more combining marks,
659 // and we are not in a recursive discontiguous contraction.
660 // Append CEs from the contraction ce32
661 // and then from the combining marks that we skipped before the match.
662 c = U_SENTINEL;
663 for(;;) {
664 appendCEsFromCE32(d, c, ce32, TRUE, errorCode);
665 // Fetch CE32s for skipped combining marks from the normal data, with fallback,
666 // rather than from the CollationData where we found the contraction.
667 if(!skipped->hasNext()) { break; }
668 c = skipped->next();
669 ce32 = getDataCE32(c);
670 if(ce32 == Collation::FALLBACK_CE32) {
671 d = data->base;
672 ce32 = d->getCE32(c);
673 } else {
674 d = data;
675 }
676 // Note: A nested discontiguous-contraction match
677 // replaces consumed combining marks with newly skipped ones
678 // and resets the reading position to the beginning.
679 }
680 skipped->clear();
681 ce32 = Collation::NO_CE32; // Signal to the caller that the result is in the ceBuffer.
682 }
683 return ce32;
684}
685
686void
687CollationIterator::appendNumericCEs(uint32_t ce32, UBool forward, UErrorCode &errorCode) {
688 // Collect digits.
689 CharString digits;
690 if(forward) {
691 for(;;) {
692 char digit = Collation::digitFromCE32(ce32);
693 digits.append(digit, errorCode);
694 if(numCpFwd == 0) { break; }
695 UChar32 c = nextCodePoint(errorCode);
696 if(c < 0) { break; }
697 ce32 = data->getCE32(c);
698 if(ce32 == Collation::FALLBACK_CE32) {
699 ce32 = data->base->getCE32(c);
700 }
701 if(!Collation::hasCE32Tag(ce32, Collation::DIGIT_TAG)) {
702 backwardNumCodePoints(1, errorCode);
703 break;
704 }
705 if(numCpFwd > 0) { --numCpFwd; }
706 }
707 } else {
708 for(;;) {
709 char digit = Collation::digitFromCE32(ce32);
710 digits.append(digit, errorCode);
711 UChar32 c = previousCodePoint(errorCode);
712 if(c < 0) { break; }
713 ce32 = data->getCE32(c);
714 if(ce32 == Collation::FALLBACK_CE32) {
715 ce32 = data->base->getCE32(c);
716 }
717 if(!Collation::hasCE32Tag(ce32, Collation::DIGIT_TAG)) {
718 forwardNumCodePoints(1, errorCode);
719 break;
720 }
721 }
722 // Reverse the digit string.
723 char *p = digits.data();
724 char *q = p + digits.length() - 1;
725 while(p < q) {
726 char digit = *p;
727 *p++ = *q;
728 *q-- = digit;
729 }
730 }
731 if(U_FAILURE(errorCode)) { return; }
732 int32_t pos = 0;
733 do {
734 // Skip leading zeros.
735 while(pos < (digits.length() - 1) && digits[pos] == 0) { ++pos; }
736 // Write a sequence of CEs for at most 254 digits at a time.
737 int32_t segmentLength = digits.length() - pos;
738 if(segmentLength > 254) { segmentLength = 254; }
739 appendNumericSegmentCEs(digits.data() + pos, segmentLength, errorCode);
740 pos += segmentLength;
741 } while(U_SUCCESS(errorCode) && pos < digits.length());
742}
743
744void
745CollationIterator::appendNumericSegmentCEs(const char *digits, int32_t length, UErrorCode &errorCode) {
746 U_ASSERT(1 <= length && length <= 254);
747 U_ASSERT(length == 1 || digits[0] != 0);
748 uint32_t numericPrimary = data->numericPrimary;
749 // Note: We use primary byte values 2..255: digits are not compressible.
750 if(length <= 7) {
751 // Very dense encoding for small numbers.
752 int32_t value = digits[0];
753 for(int32_t i = 1; i < length; ++i) {
754 value = value * 10 + digits[i];
755 }
756 // Primary weight second byte values:
757 // 74 byte values 2.. 75 for small numbers in two-byte primary weights.
758 // 40 byte values 76..115 for medium numbers in three-byte primary weights.
759 // 16 byte values 116..131 for large numbers in four-byte primary weights.
760 // 124 byte values 132..255 for very large numbers with 4..127 digit pairs.
761 int32_t firstByte = 2;
762 int32_t numBytes = 74;
763 if(value < numBytes) {
764 // Two-byte primary for 0..73, good for day & month numbers etc.
765 uint32_t primary = numericPrimary | ((firstByte + value) << 16);
766 ceBuffer.append(Collation::makeCE(primary), errorCode);
767 return;
768 }
769 value -= numBytes;
770 firstByte += numBytes;
771 numBytes = 40;
772 if(value < numBytes * 254) {
773 // Three-byte primary for 74..10233=74+40*254-1, good for year numbers and more.
774 uint32_t primary = numericPrimary |
775 ((firstByte + value / 254) << 16) | ((2 + value % 254) << 8);
776 ceBuffer.append(Collation::makeCE(primary), errorCode);
777 return;
778 }
779 value -= numBytes * 254;
780 firstByte += numBytes;
781 numBytes = 16;
782 if(value < numBytes * 254 * 254) {
783 // Four-byte primary for 10234..1042489=10234+16*254*254-1.
784 uint32_t primary = numericPrimary | (2 + value % 254);
785 value /= 254;
786 primary |= (2 + value % 254) << 8;
787 value /= 254;
788 primary |= (firstByte + value % 254) << 16;
789 ceBuffer.append(Collation::makeCE(primary), errorCode);
790 return;
791 }
792 // original value > 1042489
793 }
794 U_ASSERT(length >= 7);
795
796 // The second primary byte value 132..255 indicates the number of digit pairs (4..127),
797 // then we generate primary bytes with those pairs.
798 // Omit trailing 00 pairs.
799 // Decrement the value for the last pair.
800
801 // Set the exponent. 4 pairs->132, 5 pairs->133, ..., 127 pairs->255.
802 int32_t numPairs = (length + 1) / 2;
803 uint32_t primary = numericPrimary | ((132 - 4 + numPairs) << 16);
804 // Find the length without trailing 00 pairs.
805 while(digits[length - 1] == 0 && digits[length - 2] == 0) {
806 length -= 2;
807 }
808 // Read the first pair.
809 uint32_t pair;
810 int32_t pos;
811 if(length & 1) {
812 // Only "half a pair" if we have an odd number of digits.
813 pair = digits[0];
814 pos = 1;
815 } else {
816 pair = digits[0] * 10 + digits[1];
817 pos = 2;
818 }
819 pair = 11 + 2 * pair;
820 // Add the pairs of digits between pos and length.
821 int32_t shift = 8;
822 while(pos < length) {
823 if(shift == 0) {
824 // Every three pairs/bytes we need to store a 4-byte-primary CE
825 // and start with a new CE with the '0' primary lead byte.
826 primary |= pair;
827 ceBuffer.append(Collation::makeCE(primary), errorCode);
828 primary = numericPrimary;
829 shift = 16;
830 } else {
831 primary |= pair << shift;
832 shift -= 8;
833 }
834 pair = 11 + 2 * (digits[pos] * 10 + digits[pos + 1]);
835 pos += 2;
836 }
837 primary |= (pair - 1) << shift;
838 ceBuffer.append(Collation::makeCE(primary), errorCode);
839}
840
841int64_t
842CollationIterator::previousCE(UVector32 &offsets, UErrorCode &errorCode) {
843 if(ceBuffer.length > 0) {
844 // Return the previous buffered CE.
845 return ceBuffer.get(--ceBuffer.length);
846 }
847 offsets.removeAllElements();
848 int32_t limitOffset = getOffset();
849 UChar32 c = previousCodePoint(errorCode);
850 if(c < 0) { return Collation::NO_CE; }
851 if(data->isUnsafeBackward(c, isNumeric)) {
852 return previousCEUnsafe(c, offsets, errorCode);
853 }
854 // Simple, safe-backwards iteration:
855 // Get a CE going backwards, handle prefixes but no contractions.
856 uint32_t ce32 = data->getCE32(c);
857 const CollationData *d;
858 if(ce32 == Collation::FALLBACK_CE32) {
859 d = data->base;
860 ce32 = d->getCE32(c);
861 } else {
862 d = data;
863 }
864 if(Collation::isSimpleOrLongCE32(ce32)) {
865 return Collation::ceFromCE32(ce32);
866 }
867 appendCEsFromCE32(d, c, ce32, FALSE, errorCode);
868 if(U_SUCCESS(errorCode)) {
869 if(ceBuffer.length > 1) {
870 offsets.addElement(getOffset(), errorCode);
871 // For an expansion, the offset of each non-initial CE is the limit offset,
872 // consistent with forward iteration.
873 while(offsets.size() <= ceBuffer.length) {
874 offsets.addElement(limitOffset, errorCode);
875 }
876 }
877 return ceBuffer.get(--ceBuffer.length);
878 } else {
879 return Collation::NO_CE_PRIMARY;
880 }
881}
882
883int64_t
884CollationIterator::previousCEUnsafe(UChar32 c, UVector32 &offsets, UErrorCode &errorCode) {
885 // We just move through the input counting safe and unsafe code points
886 // without collecting the unsafe-backward substring into a buffer and
887 // switching to it.
888 // This is to keep the logic simple. Otherwise we would have to handle
889 // prefix matching going before the backward buffer, switching
890 // to iteration and back, etc.
891 // In the most important case of iterating over a normal string,
892 // reading from the string itself is already maximally fast.
893 // The only drawback there is that after getting the CEs we always
894 // skip backward to the safe character rather than switching out
895 // of a backwardBuffer.
896 // But this should not be the common case for previousCE(),
897 // and correctness and maintainability are more important than
898 // complex optimizations.
899 // Find the first safe character before c.
900 int32_t numBackward = 1;
901 while((c = previousCodePoint(errorCode)) >= 0) {
902 ++numBackward;
903 if(!data->isUnsafeBackward(c, isNumeric)) {
904 break;
905 }
906 }
907 // Set the forward iteration limit.
908 // Note: This counts code points.
909 // We cannot enforce a limit in the middle of a surrogate pair or similar.
910 numCpFwd = numBackward;
911 // Reset the forward iterator.
912 cesIndex = 0;
913 U_ASSERT(ceBuffer.length == 0);
914 // Go forward and collect the CEs.
915 int32_t offset = getOffset();
916 while(numCpFwd > 0) {
917 // nextCE() normally reads one code point.
918 // Contraction matching and digit specials read more and check numCpFwd.
919 --numCpFwd;
920 // Append one or more CEs to the ceBuffer.
921 (void)nextCE(errorCode);
922 U_ASSERT(U_FAILURE(errorCode) || ceBuffer.get(ceBuffer.length - 1) != Collation::NO_CE);
923 // No need to loop for getting each expansion CE from nextCE().
924 cesIndex = ceBuffer.length;
925 // However, we need to write an offset for each CE.
926 // This is for CollationElementIterator::getOffset() to return
927 // intermediate offsets from the unsafe-backwards segment.
928 U_ASSERT(offsets.size() < ceBuffer.length);
929 offsets.addElement(offset, errorCode);
930 // For an expansion, the offset of each non-initial CE is the limit offset,
931 // consistent with forward iteration.
932 offset = getOffset();
933 while(offsets.size() < ceBuffer.length) {
934 offsets.addElement(offset, errorCode);
935 }
936 }
937 U_ASSERT(offsets.size() == ceBuffer.length);
938 // End offset corresponding to just after the unsafe-backwards segment.
939 offsets.addElement(offset, errorCode);
940 // Reset the forward iteration limit
941 // and move backward to before the segment for which we fetched CEs.
942 numCpFwd = -1;
943 backwardNumCodePoints(numBackward, errorCode);
944 // Use the collected CEs and return the last one.
945 cesIndex = 0; // Avoid cesIndex > ceBuffer.length when that gets decremented.
946 if(U_SUCCESS(errorCode)) {
947 return ceBuffer.get(--ceBuffer.length);
948 } else {
949 return Collation::NO_CE_PRIMARY;
950 }
951}
952
953U_NAMESPACE_END
954
955#endif // !UCONFIG_NO_COLLATION
956