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-2015, International Business Machines
6 * Corporation and others.  All Rights Reserved.
7 *******************************************************************************
8 * collationdatabuilder.cpp
9 *
10 * (replaced the former ucol_elm.cpp)
11 *
12 * created on: 2012apr01
13 * created by: Markus W. Scherer
14 */
15 
16 #include "unicode/utypes.h"
17 
18 #if !UCONFIG_NO_COLLATION
19 
20 #include "unicode/localpointer.h"
21 #include "unicode/uchar.h"
22 #include "unicode/ucharstrie.h"
23 #include "unicode/ucharstriebuilder.h"
24 #include "unicode/uniset.h"
25 #include "unicode/unistr.h"
26 #include "unicode/usetiter.h"
27 #include "unicode/utf16.h"
28 #include "cmemory.h"
29 #include "collation.h"
30 #include "collationdata.h"
31 #include "collationdatabuilder.h"
32 #include "collationfastlatinbuilder.h"
33 #include "collationiterator.h"
34 #include "normalizer2impl.h"
35 #include "utrie2.h"
36 #include "uvectr32.h"
37 #include "uvectr64.h"
38 #include "uvector.h"
39 
40 U_NAMESPACE_BEGIN
41 
~CEModifier()42 CollationDataBuilder::CEModifier::~CEModifier() {}
43 
44 /**
45  * Build-time context and CE32 for a code point.
46  * If a code point has contextual mappings, then the default (no-context) mapping
47  * and all conditional mappings are stored in a singly-linked list
48  * of ConditionalCE32, sorted by context strings.
49  *
50  * Context strings sort by prefix length, then by prefix, then by contraction suffix.
51  * Context strings must be unique and in ascending order.
52  */
53 struct ConditionalCE32 : public UMemory {
ConditionalCE32ConditionalCE3254     ConditionalCE32()
55             : context(),
56               ce32(0), defaultCE32(Collation::NO_CE32), builtCE32(Collation::NO_CE32),
57               next(-1) {}
ConditionalCE32ConditionalCE3258     ConditionalCE32(const UnicodeString &ct, uint32_t ce)
59             : context(ct),
60               ce32(ce), defaultCE32(Collation::NO_CE32), builtCE32(Collation::NO_CE32),
61               next(-1) {}
62 
hasContextConditionalCE3263     inline UBool hasContext() const { return context.length() > 1; }
prefixLengthConditionalCE3264     inline int32_t prefixLength() const { return context.charAt(0); }
65 
66     /**
67      * "\0" for the first entry for any code point, with its default CE32.
68      *
69      * Otherwise one unit with the length of the prefix string,
70      * then the prefix string, then the contraction suffix.
71      */
72     UnicodeString context;
73     /**
74      * CE32 for the code point and its context.
75      * Can be special (e.g., for an expansion) but not contextual (prefix or contraction tag).
76      */
77     uint32_t ce32;
78     /**
79      * Default CE32 for all contexts with this same prefix.
80      * Initially NO_CE32. Set only while building runtime data structures,
81      * and only on one of the nodes of a sub-list with the same prefix.
82      */
83     uint32_t defaultCE32;
84     /**
85      * CE32 for the built contexts.
86      * When fetching CEs from the builder, the contexts are built into their runtime form
87      * so that the normal collation implementation can process them.
88      * The result is cached in the list head. It is reset when the contexts are modified.
89      */
90     uint32_t builtCE32;
91     /**
92      * Index of the next ConditionalCE32.
93      * Negative for the end of the list.
94      */
95     int32_t next;
96 };
97 
98 U_CDECL_BEGIN
99 
100 U_CAPI void U_CALLCONV
uprv_deleteConditionalCE32(void * obj)101 uprv_deleteConditionalCE32(void *obj) {
102     delete static_cast<ConditionalCE32 *>(obj);
103 }
104 
105 U_CDECL_END
106 
107 /**
108  * Build-time collation element and character iterator.
109  * Uses the runtime CollationIterator for fetching CEs for a string
110  * but reads from the builder's unfinished data structures.
111  * In particular, this class reads from the unfinished trie
112  * and has to avoid CollationIterator::nextCE() and redirect other
113  * calls to data->getCE32() and data->getCE32FromSupplementary().
114  *
115  * We do this so that we need not implement the collation algorithm
116  * again for the builder and make it behave exactly like the runtime code.
117  * That would be more difficult to test and maintain than this indirection.
118  *
119  * Some CE32 tags (for example, the DIGIT_TAG) do not occur in the builder data,
120  * so the data accesses from those code paths need not be modified.
121  *
122  * This class iterates directly over whole code points
123  * so that the CollationIterator does not need the finished trie
124  * for handling the LEAD_SURROGATE_TAG.
125  */
126 class DataBuilderCollationIterator : public CollationIterator {
127 public:
128     DataBuilderCollationIterator(CollationDataBuilder &b);
129 
130     virtual ~DataBuilderCollationIterator();
131 
132     int32_t fetchCEs(const UnicodeString &str, int32_t start, int64_t ces[], int32_t cesLength);
133 
134     virtual void resetToOffset(int32_t newOffset);
135     virtual int32_t getOffset() const;
136 
137     virtual UChar32 nextCodePoint(UErrorCode &errorCode);
138     virtual UChar32 previousCodePoint(UErrorCode &errorCode);
139 
140 protected:
141     virtual void forwardNumCodePoints(int32_t num, UErrorCode &errorCode);
142     virtual void backwardNumCodePoints(int32_t num, UErrorCode &errorCode);
143 
144     virtual uint32_t getDataCE32(UChar32 c) const;
145     virtual uint32_t getCE32FromBuilderData(uint32_t ce32, UErrorCode &errorCode);
146 
147     CollationDataBuilder &builder;
148     CollationData builderData;
149     uint32_t jamoCE32s[CollationData::JAMO_CE32S_LENGTH];
150     const UnicodeString *s;
151     int32_t pos;
152 };
153 
DataBuilderCollationIterator(CollationDataBuilder & b)154 DataBuilderCollationIterator::DataBuilderCollationIterator(CollationDataBuilder &b)
155         : CollationIterator(&builderData, /*numeric=*/ FALSE),
156           builder(b), builderData(b.nfcImpl),
157           s(NULL), pos(0) {
158     builderData.base = builder.base;
159     // Set all of the jamoCE32s[] to indirection CE32s.
160     for(int32_t j = 0; j < CollationData::JAMO_CE32S_LENGTH; ++j) {  // Count across Jamo types.
161         UChar32 jamo = CollationDataBuilder::jamoCpFromIndex(j);
162         jamoCE32s[j] = Collation::makeCE32FromTagAndIndex(Collation::BUILDER_DATA_TAG, jamo) |
163                 CollationDataBuilder::IS_BUILDER_JAMO_CE32;
164     }
165     builderData.jamoCE32s = jamoCE32s;
166 }
167 
~DataBuilderCollationIterator()168 DataBuilderCollationIterator::~DataBuilderCollationIterator() {}
169 
170 int32_t
fetchCEs(const UnicodeString & str,int32_t start,int64_t ces[],int32_t cesLength)171 DataBuilderCollationIterator::fetchCEs(const UnicodeString &str, int32_t start,
172                                        int64_t ces[], int32_t cesLength) {
173     // Set the pointers each time, in case they changed due to reallocation.
174     builderData.ce32s = reinterpret_cast<const uint32_t *>(builder.ce32s.getBuffer());
175     builderData.ces = builder.ce64s.getBuffer();
176     builderData.contexts = builder.contexts.getBuffer();
177     // Modified copy of CollationIterator::nextCE() and CollationIterator::nextCEFromCE32().
178     reset();
179     s = &str;
180     pos = start;
181     UErrorCode errorCode = U_ZERO_ERROR;
182     while(U_SUCCESS(errorCode) && pos < s->length()) {
183         // No need to keep all CEs in the iterator buffer.
184         clearCEs();
185         UChar32 c = s->char32At(pos);
186         pos += U16_LENGTH(c);
187         uint32_t ce32 = utrie2_get32(builder.trie, c);
188         const CollationData *d;
189         if(ce32 == Collation::FALLBACK_CE32) {
190             d = builder.base;
191             ce32 = builder.base->getCE32(c);
192         } else {
193             d = &builderData;
194         }
195         appendCEsFromCE32(d, c, ce32, /*forward=*/ TRUE, errorCode);
196         U_ASSERT(U_SUCCESS(errorCode));
197         for(int32_t i = 0; i < getCEsLength(); ++i) {
198             int64_t ce = getCE(i);
199             if(ce != 0) {
200                 if(cesLength < Collation::MAX_EXPANSION_LENGTH) {
201                     ces[cesLength] = ce;
202                 }
203                 ++cesLength;
204             }
205         }
206     }
207     return cesLength;
208 }
209 
210 void
resetToOffset(int32_t newOffset)211 DataBuilderCollationIterator::resetToOffset(int32_t newOffset) {
212     reset();
213     pos = newOffset;
214 }
215 
216 int32_t
getOffset() const217 DataBuilderCollationIterator::getOffset() const {
218     return pos;
219 }
220 
221 UChar32
nextCodePoint(UErrorCode &)222 DataBuilderCollationIterator::nextCodePoint(UErrorCode & /*errorCode*/) {
223     if(pos == s->length()) {
224         return U_SENTINEL;
225     }
226     UChar32 c = s->char32At(pos);
227     pos += U16_LENGTH(c);
228     return c;
229 }
230 
231 UChar32
previousCodePoint(UErrorCode &)232 DataBuilderCollationIterator::previousCodePoint(UErrorCode & /*errorCode*/) {
233     if(pos == 0) {
234         return U_SENTINEL;
235     }
236     UChar32 c = s->char32At(pos - 1);
237     pos -= U16_LENGTH(c);
238     return c;
239 }
240 
241 void
forwardNumCodePoints(int32_t num,UErrorCode &)242 DataBuilderCollationIterator::forwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
243     pos = s->moveIndex32(pos, num);
244 }
245 
246 void
backwardNumCodePoints(int32_t num,UErrorCode &)247 DataBuilderCollationIterator::backwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
248     pos = s->moveIndex32(pos, -num);
249 }
250 
251 uint32_t
getDataCE32(UChar32 c) const252 DataBuilderCollationIterator::getDataCE32(UChar32 c) const {
253     return utrie2_get32(builder.trie, c);
254 }
255 
256 uint32_t
getCE32FromBuilderData(uint32_t ce32,UErrorCode & errorCode)257 DataBuilderCollationIterator::getCE32FromBuilderData(uint32_t ce32, UErrorCode &errorCode) {
258     if (U_FAILURE(errorCode)) { return 0; }
259     U_ASSERT(Collation::hasCE32Tag(ce32, Collation::BUILDER_DATA_TAG));
260     if((ce32 & CollationDataBuilder::IS_BUILDER_JAMO_CE32) != 0) {
261         UChar32 jamo = Collation::indexFromCE32(ce32);
262         return utrie2_get32(builder.trie, jamo);
263     } else {
264         ConditionalCE32 *cond = builder.getConditionalCE32ForCE32(ce32);
265         if (cond == nullptr) {
266             errorCode = U_INTERNAL_PROGRAM_ERROR;
267             // TODO: ICU-21531 figure out why this happens.
268             return 0;
269         }
270         if(cond->builtCE32 == Collation::NO_CE32) {
271             // Build the context-sensitive mappings into their runtime form and cache the result.
272             cond->builtCE32 = builder.buildContext(cond, errorCode);
273             if(errorCode == U_BUFFER_OVERFLOW_ERROR) {
274                 errorCode = U_ZERO_ERROR;
275                 builder.clearContexts();
276                 cond->builtCE32 = builder.buildContext(cond, errorCode);
277             }
278             builderData.contexts = builder.contexts.getBuffer();
279         }
280         return cond->builtCE32;
281     }
282 }
283 
284 // ------------------------------------------------------------------------- ***
285 
CollationDataBuilder(UErrorCode & errorCode)286 CollationDataBuilder::CollationDataBuilder(UErrorCode &errorCode)
287         : nfcImpl(*Normalizer2Factory::getNFCImpl(errorCode)),
288           base(NULL), baseSettings(NULL),
289           trie(NULL),
290           ce32s(errorCode), ce64s(errorCode), conditionalCE32s(errorCode),
291           modified(FALSE),
292           fastLatinEnabled(FALSE), fastLatinBuilder(NULL),
293           collIter(NULL) {
294     // Reserve the first CE32 for U+0000.
295     ce32s.addElement(0, errorCode);
296     conditionalCE32s.setDeleter(uprv_deleteConditionalCE32);
297 }
298 
~CollationDataBuilder()299 CollationDataBuilder::~CollationDataBuilder() {
300     utrie2_close(trie);
301     delete fastLatinBuilder;
302     delete collIter;
303 }
304 
305 void
initForTailoring(const CollationData * b,UErrorCode & errorCode)306 CollationDataBuilder::initForTailoring(const CollationData *b, UErrorCode &errorCode) {
307     if(U_FAILURE(errorCode)) { return; }
308     if(trie != NULL) {
309         errorCode = U_INVALID_STATE_ERROR;
310         return;
311     }
312     if(b == NULL) {
313         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
314         return;
315     }
316     base = b;
317 
318     // For a tailoring, the default is to fall back to the base.
319     trie = utrie2_open(Collation::FALLBACK_CE32, Collation::FFFD_CE32, &errorCode);
320 
321     // Set the Latin-1 letters block so that it is allocated first in the data array,
322     // to try to improve locality of reference when sorting Latin-1 text.
323     // Do not use utrie2_setRange32() since that will not actually allocate blocks
324     // that are filled with the default value.
325     // ASCII (0..7F) is already preallocated anyway.
326     for(UChar32 c = 0xc0; c <= 0xff; ++c) {
327         utrie2_set32(trie, c, Collation::FALLBACK_CE32, &errorCode);
328     }
329 
330     // Hangul syllables are not tailorable (except via tailoring Jamos).
331     // Always set the Hangul tag to help performance.
332     // Do this here, rather than in buildMappings(),
333     // so that we see the HANGUL_TAG in various assertions.
334     uint32_t hangulCE32 = Collation::makeCE32FromTagAndIndex(Collation::HANGUL_TAG, 0);
335     utrie2_setRange32(trie, Hangul::HANGUL_BASE, Hangul::HANGUL_END, hangulCE32, TRUE, &errorCode);
336 
337     // Copy the set contents but don't copy/clone the set as a whole because
338     // that would copy the isFrozen state too.
339     unsafeBackwardSet.addAll(*b->unsafeBackwardSet);
340 
341     if(U_FAILURE(errorCode)) { return; }
342 }
343 
344 UBool
maybeSetPrimaryRange(UChar32 start,UChar32 end,uint32_t primary,int32_t step,UErrorCode & errorCode)345 CollationDataBuilder::maybeSetPrimaryRange(UChar32 start, UChar32 end,
346                                            uint32_t primary, int32_t step,
347                                            UErrorCode &errorCode) {
348     if(U_FAILURE(errorCode)) { return FALSE; }
349     U_ASSERT(start <= end);
350     // TODO: Do we need to check what values are currently set for start..end?
351     // An offset range is worth it only if we can achieve an overlap between
352     // adjacent UTrie2 blocks of 32 code points each.
353     // An offset CE is also a little more expensive to look up and compute
354     // than a simple CE.
355     // If the range spans at least three UTrie2 block boundaries (> 64 code points),
356     // then we take it.
357     // If the range spans one or two block boundaries and there are
358     // at least 4 code points on either side, then we take it.
359     // (We could additionally require a minimum range length of, say, 16.)
360     int32_t blockDelta = (end >> 5) - (start >> 5);
361     if(2 <= step && step <= 0x7f &&
362             (blockDelta >= 3 ||
363             (blockDelta > 0 && (start & 0x1f) <= 0x1c && (end & 0x1f) >= 3))) {
364         int64_t dataCE = ((int64_t)primary << 32) | (start << 8) | step;
365         if(isCompressiblePrimary(primary)) { dataCE |= 0x80; }
366         int32_t index = addCE(dataCE, errorCode);
367         if(U_FAILURE(errorCode)) { return 0; }
368         if(index > Collation::MAX_INDEX) {
369             errorCode = U_BUFFER_OVERFLOW_ERROR;
370             return 0;
371         }
372         uint32_t offsetCE32 = Collation::makeCE32FromTagAndIndex(Collation::OFFSET_TAG, index);
373         utrie2_setRange32(trie, start, end, offsetCE32, TRUE, &errorCode);
374         modified = TRUE;
375         return TRUE;
376     } else {
377         return FALSE;
378     }
379 }
380 
381 uint32_t
setPrimaryRangeAndReturnNext(UChar32 start,UChar32 end,uint32_t primary,int32_t step,UErrorCode & errorCode)382 CollationDataBuilder::setPrimaryRangeAndReturnNext(UChar32 start, UChar32 end,
383                                                    uint32_t primary, int32_t step,
384                                                    UErrorCode &errorCode) {
385     if(U_FAILURE(errorCode)) { return 0; }
386     UBool isCompressible = isCompressiblePrimary(primary);
387     if(maybeSetPrimaryRange(start, end, primary, step, errorCode)) {
388         return Collation::incThreeBytePrimaryByOffset(primary, isCompressible,
389                                                       (end - start + 1) * step);
390     } else {
391         // Short range: Set individual CE32s.
392         for(;;) {
393             utrie2_set32(trie, start, Collation::makeLongPrimaryCE32(primary), &errorCode);
394             ++start;
395             primary = Collation::incThreeBytePrimaryByOffset(primary, isCompressible, step);
396             if(start > end) { return primary; }
397         }
398         modified = TRUE;
399     }
400 }
401 
402 uint32_t
getCE32FromOffsetCE32(UBool fromBase,UChar32 c,uint32_t ce32) const403 CollationDataBuilder::getCE32FromOffsetCE32(UBool fromBase, UChar32 c, uint32_t ce32) const {
404     int32_t i = Collation::indexFromCE32(ce32);
405     int64_t dataCE = fromBase ? base->ces[i] : ce64s.elementAti(i);
406     uint32_t p = Collation::getThreeBytePrimaryForOffsetData(c, dataCE);
407     return Collation::makeLongPrimaryCE32(p);
408 }
409 
410 UBool
isCompressibleLeadByte(uint32_t b) const411 CollationDataBuilder::isCompressibleLeadByte(uint32_t b) const {
412     return base->isCompressibleLeadByte(b);
413 }
414 
415 UBool
isAssigned(UChar32 c) const416 CollationDataBuilder::isAssigned(UChar32 c) const {
417     return Collation::isAssignedCE32(utrie2_get32(trie, c));
418 }
419 
420 uint32_t
getLongPrimaryIfSingleCE(UChar32 c) const421 CollationDataBuilder::getLongPrimaryIfSingleCE(UChar32 c) const {
422     uint32_t ce32 = utrie2_get32(trie, c);
423     if(Collation::isLongPrimaryCE32(ce32)) {
424         return Collation::primaryFromLongPrimaryCE32(ce32);
425     } else {
426         return 0;
427     }
428 }
429 
430 int64_t
getSingleCE(UChar32 c,UErrorCode & errorCode) const431 CollationDataBuilder::getSingleCE(UChar32 c, UErrorCode &errorCode) const {
432     if(U_FAILURE(errorCode)) { return 0; }
433     // Keep parallel with CollationData::getSingleCE().
434     UBool fromBase = FALSE;
435     uint32_t ce32 = utrie2_get32(trie, c);
436     if(ce32 == Collation::FALLBACK_CE32) {
437         fromBase = TRUE;
438         ce32 = base->getCE32(c);
439     }
440     while(Collation::isSpecialCE32(ce32)) {
441         switch(Collation::tagFromCE32(ce32)) {
442         case Collation::LATIN_EXPANSION_TAG:
443         case Collation::BUILDER_DATA_TAG:
444         case Collation::PREFIX_TAG:
445         case Collation::CONTRACTION_TAG:
446         case Collation::HANGUL_TAG:
447         case Collation::LEAD_SURROGATE_TAG:
448             errorCode = U_UNSUPPORTED_ERROR;
449             return 0;
450         case Collation::FALLBACK_TAG:
451         case Collation::RESERVED_TAG_3:
452             errorCode = U_INTERNAL_PROGRAM_ERROR;
453             return 0;
454         case Collation::LONG_PRIMARY_TAG:
455             return Collation::ceFromLongPrimaryCE32(ce32);
456         case Collation::LONG_SECONDARY_TAG:
457             return Collation::ceFromLongSecondaryCE32(ce32);
458         case Collation::EXPANSION32_TAG:
459             if(Collation::lengthFromCE32(ce32) == 1) {
460                 int32_t i = Collation::indexFromCE32(ce32);
461                 ce32 = fromBase ? base->ce32s[i] : ce32s.elementAti(i);
462                 break;
463             } else {
464                 errorCode = U_UNSUPPORTED_ERROR;
465                 return 0;
466             }
467         case Collation::EXPANSION_TAG: {
468             if(Collation::lengthFromCE32(ce32) == 1) {
469                 int32_t i = Collation::indexFromCE32(ce32);
470                 return fromBase ? base->ces[i] : ce64s.elementAti(i);
471             } else {
472                 errorCode = U_UNSUPPORTED_ERROR;
473                 return 0;
474             }
475         }
476         case Collation::DIGIT_TAG:
477             // Fetch the non-numeric-collation CE32 and continue.
478             ce32 = ce32s.elementAti(Collation::indexFromCE32(ce32));
479             break;
480         case Collation::U0000_TAG:
481             U_ASSERT(c == 0);
482             // Fetch the normal ce32 for U+0000 and continue.
483             ce32 = fromBase ? base->ce32s[0] : ce32s.elementAti(0);
484             break;
485         case Collation::OFFSET_TAG:
486             ce32 = getCE32FromOffsetCE32(fromBase, c, ce32);
487             break;
488         case Collation::IMPLICIT_TAG:
489             return Collation::unassignedCEFromCodePoint(c);
490         }
491     }
492     return Collation::ceFromSimpleCE32(ce32);
493 }
494 
495 int32_t
addCE(int64_t ce,UErrorCode & errorCode)496 CollationDataBuilder::addCE(int64_t ce, UErrorCode &errorCode) {
497     int32_t length = ce64s.size();
498     for(int32_t i = 0; i < length; ++i) {
499         if(ce == ce64s.elementAti(i)) { return i; }
500     }
501     ce64s.addElement(ce, errorCode);
502     return length;
503 }
504 
505 int32_t
addCE32(uint32_t ce32,UErrorCode & errorCode)506 CollationDataBuilder::addCE32(uint32_t ce32, UErrorCode &errorCode) {
507     int32_t length = ce32s.size();
508     for(int32_t i = 0; i < length; ++i) {
509         if(ce32 == (uint32_t)ce32s.elementAti(i)) { return i; }
510     }
511     ce32s.addElement((int32_t)ce32, errorCode);
512     return length;
513 }
514 
515 int32_t
addConditionalCE32(const UnicodeString & context,uint32_t ce32,UErrorCode & errorCode)516 CollationDataBuilder::addConditionalCE32(const UnicodeString &context, uint32_t ce32,
517                                          UErrorCode &errorCode) {
518     if(U_FAILURE(errorCode)) { return -1; }
519     U_ASSERT(!context.isEmpty());
520     int32_t index = conditionalCE32s.size();
521     if(index > Collation::MAX_INDEX) {
522         errorCode = U_BUFFER_OVERFLOW_ERROR;
523         return -1;
524     }
525     ConditionalCE32 *cond = new ConditionalCE32(context, ce32);
526     if(cond == NULL) {
527         errorCode = U_MEMORY_ALLOCATION_ERROR;
528         return -1;
529     }
530     conditionalCE32s.addElement(cond, errorCode);
531     return index;
532 }
533 
534 void
add(const UnicodeString & prefix,const UnicodeString & s,const int64_t ces[],int32_t cesLength,UErrorCode & errorCode)535 CollationDataBuilder::add(const UnicodeString &prefix, const UnicodeString &s,
536                           const int64_t ces[], int32_t cesLength,
537                           UErrorCode &errorCode) {
538     uint32_t ce32 = encodeCEs(ces, cesLength, errorCode);
539     addCE32(prefix, s, ce32, errorCode);
540 }
541 
542 void
addCE32(const UnicodeString & prefix,const UnicodeString & s,uint32_t ce32,UErrorCode & errorCode)543 CollationDataBuilder::addCE32(const UnicodeString &prefix, const UnicodeString &s,
544                               uint32_t ce32, UErrorCode &errorCode) {
545     if(U_FAILURE(errorCode)) { return; }
546     if(s.isEmpty()) {
547         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
548         return;
549     }
550     if(trie == NULL || utrie2_isFrozen(trie)) {
551         errorCode = U_INVALID_STATE_ERROR;
552         return;
553     }
554     UChar32 c = s.char32At(0);
555     int32_t cLength = U16_LENGTH(c);
556     uint32_t oldCE32 = utrie2_get32(trie, c);
557     UBool hasContext = !prefix.isEmpty() || s.length() > cLength;
558     if(oldCE32 == Collation::FALLBACK_CE32) {
559         // First tailoring for c.
560         // If c has contextual base mappings or if we add a contextual mapping,
561         // then copy the base mappings.
562         // Otherwise we just override the base mapping.
563         uint32_t baseCE32 = base->getFinalCE32(base->getCE32(c));
564         if(hasContext || Collation::ce32HasContext(baseCE32)) {
565             oldCE32 = copyFromBaseCE32(c, baseCE32, TRUE, errorCode);
566             utrie2_set32(trie, c, oldCE32, &errorCode);
567             if(U_FAILURE(errorCode)) { return; }
568         }
569     }
570     if(!hasContext) {
571         // No prefix, no contraction.
572         if(!isBuilderContextCE32(oldCE32)) {
573             utrie2_set32(trie, c, ce32, &errorCode);
574         } else {
575             ConditionalCE32 *cond = getConditionalCE32ForCE32(oldCE32);
576             cond->builtCE32 = Collation::NO_CE32;
577             cond->ce32 = ce32;
578         }
579     } else {
580         ConditionalCE32 *cond;
581         if(!isBuilderContextCE32(oldCE32)) {
582             // Replace the simple oldCE32 with a builder context CE32
583             // pointing to a new ConditionalCE32 list head.
584             int32_t index = addConditionalCE32(UnicodeString((UChar)0), oldCE32, errorCode);
585             if(U_FAILURE(errorCode)) { return; }
586             uint32_t contextCE32 = makeBuilderContextCE32(index);
587             utrie2_set32(trie, c, contextCE32, &errorCode);
588             contextChars.add(c);
589             cond = getConditionalCE32(index);
590         } else {
591             cond = getConditionalCE32ForCE32(oldCE32);
592             cond->builtCE32 = Collation::NO_CE32;
593         }
594         UnicodeString suffix(s, cLength);
595         UnicodeString context((UChar)prefix.length());
596         context.append(prefix).append(suffix);
597         unsafeBackwardSet.addAll(suffix);
598         for(;;) {
599             // invariant: context > cond->context
600             int32_t next = cond->next;
601             if(next < 0) {
602                 // Append a new ConditionalCE32 after cond.
603                 int32_t index = addConditionalCE32(context, ce32, errorCode);
604                 if(U_FAILURE(errorCode)) { return; }
605                 cond->next = index;
606                 break;
607             }
608             ConditionalCE32 *nextCond = getConditionalCE32(next);
609             int8_t cmp = context.compare(nextCond->context);
610             if(cmp < 0) {
611                 // Insert a new ConditionalCE32 between cond and nextCond.
612                 int32_t index = addConditionalCE32(context, ce32, errorCode);
613                 if(U_FAILURE(errorCode)) { return; }
614                 cond->next = index;
615                 getConditionalCE32(index)->next = next;
616                 break;
617             } else if(cmp == 0) {
618                 // Same context as before, overwrite its ce32.
619                 nextCond->ce32 = ce32;
620                 break;
621             }
622             cond = nextCond;
623         }
624     }
625     modified = TRUE;
626 }
627 
628 uint32_t
encodeOneCEAsCE32(int64_t ce)629 CollationDataBuilder::encodeOneCEAsCE32(int64_t ce) {
630     uint32_t p = (uint32_t)(ce >> 32);
631     uint32_t lower32 = (uint32_t)ce;
632     uint32_t t = (uint32_t)(ce & 0xffff);
633     U_ASSERT((t & 0xc000) != 0xc000);  // Impossible case bits 11 mark special CE32s.
634     if((ce & INT64_C(0xffff00ff00ff)) == 0) {
635         // normal form ppppsstt
636         return p | (lower32 >> 16) | (t >> 8);
637     } else if((ce & INT64_C(0xffffffffff)) == Collation::COMMON_SEC_AND_TER_CE) {
638         // long-primary form ppppppC1
639         return Collation::makeLongPrimaryCE32(p);
640     } else if(p == 0 && (t & 0xff) == 0) {
641         // long-secondary form ssssttC2
642         return Collation::makeLongSecondaryCE32(lower32);
643     }
644     return Collation::NO_CE32;
645 }
646 
647 uint32_t
encodeOneCE(int64_t ce,UErrorCode & errorCode)648 CollationDataBuilder::encodeOneCE(int64_t ce, UErrorCode &errorCode) {
649     // Try to encode one CE as one CE32.
650     uint32_t ce32 = encodeOneCEAsCE32(ce);
651     if(ce32 != Collation::NO_CE32) { return ce32; }
652     int32_t index = addCE(ce, errorCode);
653     if(U_FAILURE(errorCode)) { return 0; }
654     if(index > Collation::MAX_INDEX) {
655         errorCode = U_BUFFER_OVERFLOW_ERROR;
656         return 0;
657     }
658     return Collation::makeCE32FromTagIndexAndLength(Collation::EXPANSION_TAG, index, 1);
659 }
660 
661 uint32_t
encodeCEs(const int64_t ces[],int32_t cesLength,UErrorCode & errorCode)662 CollationDataBuilder::encodeCEs(const int64_t ces[], int32_t cesLength,
663                                 UErrorCode &errorCode) {
664     if(U_FAILURE(errorCode)) { return 0; }
665     if(cesLength < 0 || cesLength > Collation::MAX_EXPANSION_LENGTH) {
666         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
667         return 0;
668     }
669     if(trie == NULL || utrie2_isFrozen(trie)) {
670         errorCode = U_INVALID_STATE_ERROR;
671         return 0;
672     }
673     if(cesLength == 0) {
674         // Convenience: We cannot map to nothing, but we can map to a completely ignorable CE.
675         // Do this here so that callers need not do it.
676         return encodeOneCEAsCE32(0);
677     } else if(cesLength == 1) {
678         return encodeOneCE(ces[0], errorCode);
679     } else if(cesLength == 2) {
680         // Try to encode two CEs as one CE32.
681         int64_t ce0 = ces[0];
682         int64_t ce1 = ces[1];
683         uint32_t p0 = (uint32_t)(ce0 >> 32);
684         if((ce0 & INT64_C(0xffffffffff00ff)) == Collation::COMMON_SECONDARY_CE &&
685                 (ce1 & INT64_C(0xffffffff00ffffff)) == Collation::COMMON_TERTIARY_CE &&
686                 p0 != 0) {
687             // Latin mini expansion
688             return
689                 p0 |
690                 (((uint32_t)ce0 & 0xff00u) << 8) |
691                 (uint32_t)(ce1 >> 16) |
692                 Collation::SPECIAL_CE32_LOW_BYTE |
693                 Collation::LATIN_EXPANSION_TAG;
694         }
695     }
696     // Try to encode two or more CEs as CE32s.
697     int32_t newCE32s[Collation::MAX_EXPANSION_LENGTH];
698     for(int32_t i = 0;; ++i) {
699         if(i == cesLength) {
700             return encodeExpansion32(newCE32s, cesLength, errorCode);
701         }
702         uint32_t ce32 = encodeOneCEAsCE32(ces[i]);
703         if(ce32 == Collation::NO_CE32) { break; }
704         newCE32s[i] = (int32_t)ce32;
705     }
706     return encodeExpansion(ces, cesLength, errorCode);
707 }
708 
709 uint32_t
encodeExpansion(const int64_t ces[],int32_t length,UErrorCode & errorCode)710 CollationDataBuilder::encodeExpansion(const int64_t ces[], int32_t length, UErrorCode &errorCode) {
711     if(U_FAILURE(errorCode)) { return 0; }
712     // See if this sequence of CEs has already been stored.
713     int64_t first = ces[0];
714     int32_t ce64sMax = ce64s.size() - length;
715     for(int32_t i = 0; i <= ce64sMax; ++i) {
716         if(first == ce64s.elementAti(i)) {
717             if(i > Collation::MAX_INDEX) {
718                 errorCode = U_BUFFER_OVERFLOW_ERROR;
719                 return 0;
720             }
721             for(int32_t j = 1;; ++j) {
722                 if(j == length) {
723                     return Collation::makeCE32FromTagIndexAndLength(
724                             Collation::EXPANSION_TAG, i, length);
725                 }
726                 if(ce64s.elementAti(i + j) != ces[j]) { break; }
727             }
728         }
729     }
730     // Store the new sequence.
731     int32_t i = ce64s.size();
732     if(i > Collation::MAX_INDEX) {
733         errorCode = U_BUFFER_OVERFLOW_ERROR;
734         return 0;
735     }
736     for(int32_t j = 0; j < length; ++j) {
737         ce64s.addElement(ces[j], errorCode);
738     }
739     return Collation::makeCE32FromTagIndexAndLength(Collation::EXPANSION_TAG, i, length);
740 }
741 
742 uint32_t
encodeExpansion32(const int32_t newCE32s[],int32_t length,UErrorCode & errorCode)743 CollationDataBuilder::encodeExpansion32(const int32_t newCE32s[], int32_t length,
744                                         UErrorCode &errorCode) {
745     if(U_FAILURE(errorCode)) { return 0; }
746     // See if this sequence of CE32s has already been stored.
747     int32_t first = newCE32s[0];
748     int32_t ce32sMax = ce32s.size() - length;
749     for(int32_t i = 0; i <= ce32sMax; ++i) {
750         if(first == ce32s.elementAti(i)) {
751             if(i > Collation::MAX_INDEX) {
752                 errorCode = U_BUFFER_OVERFLOW_ERROR;
753                 return 0;
754             }
755             for(int32_t j = 1;; ++j) {
756                 if(j == length) {
757                     return Collation::makeCE32FromTagIndexAndLength(
758                             Collation::EXPANSION32_TAG, i, length);
759                 }
760                 if(ce32s.elementAti(i + j) != newCE32s[j]) { break; }
761             }
762         }
763     }
764     // Store the new sequence.
765     int32_t i = ce32s.size();
766     if(i > Collation::MAX_INDEX) {
767         errorCode = U_BUFFER_OVERFLOW_ERROR;
768         return 0;
769     }
770     for(int32_t j = 0; j < length; ++j) {
771         ce32s.addElement(newCE32s[j], errorCode);
772     }
773     return Collation::makeCE32FromTagIndexAndLength(Collation::EXPANSION32_TAG, i, length);
774 }
775 
776 uint32_t
copyFromBaseCE32(UChar32 c,uint32_t ce32,UBool withContext,UErrorCode & errorCode)777 CollationDataBuilder::copyFromBaseCE32(UChar32 c, uint32_t ce32, UBool withContext,
778                                        UErrorCode &errorCode) {
779     if(U_FAILURE(errorCode)) { return 0; }
780     if(!Collation::isSpecialCE32(ce32)) { return ce32; }
781     switch(Collation::tagFromCE32(ce32)) {
782     case Collation::LONG_PRIMARY_TAG:
783     case Collation::LONG_SECONDARY_TAG:
784     case Collation::LATIN_EXPANSION_TAG:
785         // copy as is
786         break;
787     case Collation::EXPANSION32_TAG: {
788         const uint32_t *baseCE32s = base->ce32s + Collation::indexFromCE32(ce32);
789         int32_t length = Collation::lengthFromCE32(ce32);
790         ce32 = encodeExpansion32(
791             reinterpret_cast<const int32_t *>(baseCE32s), length, errorCode);
792         break;
793     }
794     case Collation::EXPANSION_TAG: {
795         const int64_t *baseCEs = base->ces + Collation::indexFromCE32(ce32);
796         int32_t length = Collation::lengthFromCE32(ce32);
797         ce32 = encodeExpansion(baseCEs, length, errorCode);
798         break;
799     }
800     case Collation::PREFIX_TAG: {
801         // Flatten prefixes and nested suffixes (contractions)
802         // into a linear list of ConditionalCE32.
803         const UChar *p = base->contexts + Collation::indexFromCE32(ce32);
804         ce32 = CollationData::readCE32(p);  // Default if no prefix match.
805         if(!withContext) {
806             return copyFromBaseCE32(c, ce32, FALSE, errorCode);
807         }
808         ConditionalCE32 head;
809         UnicodeString context((UChar)0);
810         int32_t index;
811         if(Collation::isContractionCE32(ce32)) {
812             index = copyContractionsFromBaseCE32(context, c, ce32, &head, errorCode);
813         } else {
814             ce32 = copyFromBaseCE32(c, ce32, TRUE, errorCode);
815             head.next = index = addConditionalCE32(context, ce32, errorCode);
816         }
817         if(U_FAILURE(errorCode)) { return 0; }
818         ConditionalCE32 *cond = getConditionalCE32(index);  // the last ConditionalCE32 so far
819         UCharsTrie::Iterator prefixes(p + 2, 0, errorCode);
820         while(prefixes.next(errorCode)) {
821             context = prefixes.getString();
822             context.reverse();
823             context.insert(0, (UChar)context.length());
824             ce32 = (uint32_t)prefixes.getValue();
825             if(Collation::isContractionCE32(ce32)) {
826                 index = copyContractionsFromBaseCE32(context, c, ce32, cond, errorCode);
827             } else {
828                 ce32 = copyFromBaseCE32(c, ce32, TRUE, errorCode);
829                 cond->next = index = addConditionalCE32(context, ce32, errorCode);
830             }
831             if(U_FAILURE(errorCode)) { return 0; }
832             cond = getConditionalCE32(index);
833         }
834         ce32 = makeBuilderContextCE32(head.next);
835         contextChars.add(c);
836         break;
837     }
838     case Collation::CONTRACTION_TAG: {
839         if(!withContext) {
840             const UChar *p = base->contexts + Collation::indexFromCE32(ce32);
841             ce32 = CollationData::readCE32(p);  // Default if no suffix match.
842             return copyFromBaseCE32(c, ce32, FALSE, errorCode);
843         }
844         ConditionalCE32 head;
845         UnicodeString context((UChar)0);
846         copyContractionsFromBaseCE32(context, c, ce32, &head, errorCode);
847         ce32 = makeBuilderContextCE32(head.next);
848         contextChars.add(c);
849         break;
850     }
851     case Collation::HANGUL_TAG:
852         errorCode = U_UNSUPPORTED_ERROR;  // We forbid tailoring of Hangul syllables.
853         break;
854     case Collation::OFFSET_TAG:
855         ce32 = getCE32FromOffsetCE32(TRUE, c, ce32);
856         break;
857     case Collation::IMPLICIT_TAG:
858         ce32 = encodeOneCE(Collation::unassignedCEFromCodePoint(c), errorCode);
859         break;
860     default:
861         UPRV_UNREACHABLE;  // require ce32 == base->getFinalCE32(ce32)
862     }
863     return ce32;
864 }
865 
866 int32_t
copyContractionsFromBaseCE32(UnicodeString & context,UChar32 c,uint32_t ce32,ConditionalCE32 * cond,UErrorCode & errorCode)867 CollationDataBuilder::copyContractionsFromBaseCE32(UnicodeString &context, UChar32 c, uint32_t ce32,
868                                                    ConditionalCE32 *cond, UErrorCode &errorCode) {
869     if(U_FAILURE(errorCode)) { return 0; }
870     const UChar *p = base->contexts + Collation::indexFromCE32(ce32);
871     int32_t index;
872     if((ce32 & Collation::CONTRACT_SINGLE_CP_NO_MATCH) != 0) {
873         // No match on the single code point.
874         // We are underneath a prefix, and the default mapping is just
875         // a fallback to the mappings for a shorter prefix.
876         U_ASSERT(context.length() > 1);
877         index = -1;
878     } else {
879         ce32 = CollationData::readCE32(p);  // Default if no suffix match.
880         U_ASSERT(!Collation::isContractionCE32(ce32));
881         ce32 = copyFromBaseCE32(c, ce32, TRUE, errorCode);
882         cond->next = index = addConditionalCE32(context, ce32, errorCode);
883         if(U_FAILURE(errorCode)) { return 0; }
884         cond = getConditionalCE32(index);
885     }
886 
887     int32_t suffixStart = context.length();
888     UCharsTrie::Iterator suffixes(p + 2, 0, errorCode);
889     while(suffixes.next(errorCode)) {
890         context.append(suffixes.getString());
891         ce32 = copyFromBaseCE32(c, (uint32_t)suffixes.getValue(), TRUE, errorCode);
892         cond->next = index = addConditionalCE32(context, ce32, errorCode);
893         if(U_FAILURE(errorCode)) { return 0; }
894         // No need to update the unsafeBackwardSet because the tailoring set
895         // is already a copy of the base set.
896         cond = getConditionalCE32(index);
897         context.truncate(suffixStart);
898     }
899     U_ASSERT(index >= 0);
900     return index;
901 }
902 
903 class CopyHelper {
904 public:
CopyHelper(const CollationDataBuilder & s,CollationDataBuilder & d,const CollationDataBuilder::CEModifier & m,UErrorCode & initialErrorCode)905     CopyHelper(const CollationDataBuilder &s, CollationDataBuilder &d,
906                const CollationDataBuilder::CEModifier &m, UErrorCode &initialErrorCode)
907             : src(s), dest(d), modifier(m),
908               errorCode(initialErrorCode) {}
909 
copyRangeCE32(UChar32 start,UChar32 end,uint32_t ce32)910     UBool copyRangeCE32(UChar32 start, UChar32 end, uint32_t ce32) {
911         ce32 = copyCE32(ce32);
912         utrie2_setRange32(dest.trie, start, end, ce32, TRUE, &errorCode);
913         if(CollationDataBuilder::isBuilderContextCE32(ce32)) {
914             dest.contextChars.add(start, end);
915         }
916         return U_SUCCESS(errorCode);
917     }
918 
copyCE32(uint32_t ce32)919     uint32_t copyCE32(uint32_t ce32) {
920         if(!Collation::isSpecialCE32(ce32)) {
921             int64_t ce = modifier.modifyCE32(ce32);
922             if(ce != Collation::NO_CE) {
923                 ce32 = dest.encodeOneCE(ce, errorCode);
924             }
925         } else {
926             int32_t tag = Collation::tagFromCE32(ce32);
927             if(tag == Collation::EXPANSION32_TAG) {
928                 const uint32_t *srcCE32s = reinterpret_cast<uint32_t *>(src.ce32s.getBuffer());
929                 srcCE32s += Collation::indexFromCE32(ce32);
930                 int32_t length = Collation::lengthFromCE32(ce32);
931                 // Inspect the source CE32s. Just copy them if none are modified.
932                 // Otherwise copy to modifiedCEs, with modifications.
933                 UBool isModified = FALSE;
934                 for(int32_t i = 0; i < length; ++i) {
935                     ce32 = srcCE32s[i];
936                     int64_t ce;
937                     if(Collation::isSpecialCE32(ce32) ||
938                             (ce = modifier.modifyCE32(ce32)) == Collation::NO_CE) {
939                         if(isModified) {
940                             modifiedCEs[i] = Collation::ceFromCE32(ce32);
941                         }
942                     } else {
943                         if(!isModified) {
944                             for(int32_t j = 0; j < i; ++j) {
945                                 modifiedCEs[j] = Collation::ceFromCE32(srcCE32s[j]);
946                             }
947                             isModified = TRUE;
948                         }
949                         modifiedCEs[i] = ce;
950                     }
951                 }
952                 if(isModified) {
953                     ce32 = dest.encodeCEs(modifiedCEs, length, errorCode);
954                 } else {
955                     ce32 = dest.encodeExpansion32(
956                         reinterpret_cast<const int32_t *>(srcCE32s), length, errorCode);
957                 }
958             } else if(tag == Collation::EXPANSION_TAG) {
959                 const int64_t *srcCEs = src.ce64s.getBuffer();
960                 srcCEs += Collation::indexFromCE32(ce32);
961                 int32_t length = Collation::lengthFromCE32(ce32);
962                 // Inspect the source CEs. Just copy them if none are modified.
963                 // Otherwise copy to modifiedCEs, with modifications.
964                 UBool isModified = FALSE;
965                 for(int32_t i = 0; i < length; ++i) {
966                     int64_t srcCE = srcCEs[i];
967                     int64_t ce = modifier.modifyCE(srcCE);
968                     if(ce == Collation::NO_CE) {
969                         if(isModified) {
970                             modifiedCEs[i] = srcCE;
971                         }
972                     } else {
973                         if(!isModified) {
974                             for(int32_t j = 0; j < i; ++j) {
975                                 modifiedCEs[j] = srcCEs[j];
976                             }
977                             isModified = TRUE;
978                         }
979                         modifiedCEs[i] = ce;
980                     }
981                 }
982                 if(isModified) {
983                     ce32 = dest.encodeCEs(modifiedCEs, length, errorCode);
984                 } else {
985                     ce32 = dest.encodeExpansion(srcCEs, length, errorCode);
986                 }
987             } else if(tag == Collation::BUILDER_DATA_TAG) {
988                 // Copy the list of ConditionalCE32.
989                 ConditionalCE32 *cond = src.getConditionalCE32ForCE32(ce32);
990                 U_ASSERT(!cond->hasContext());
991                 int32_t destIndex = dest.addConditionalCE32(
992                         cond->context, copyCE32(cond->ce32), errorCode);
993                 ce32 = CollationDataBuilder::makeBuilderContextCE32(destIndex);
994                 while(cond->next >= 0) {
995                     cond = src.getConditionalCE32(cond->next);
996                     ConditionalCE32 *prevDestCond = dest.getConditionalCE32(destIndex);
997                     destIndex = dest.addConditionalCE32(
998                             cond->context, copyCE32(cond->ce32), errorCode);
999                     int32_t suffixStart = cond->prefixLength() + 1;
1000                     dest.unsafeBackwardSet.addAll(cond->context.tempSubString(suffixStart));
1001                     prevDestCond->next = destIndex;
1002                 }
1003             } else {
1004                 // Just copy long CEs and Latin mini expansions (and other expected values) as is,
1005                 // assuming that the modifier would not modify them.
1006                 U_ASSERT(tag == Collation::LONG_PRIMARY_TAG ||
1007                         tag == Collation::LONG_SECONDARY_TAG ||
1008                         tag == Collation::LATIN_EXPANSION_TAG ||
1009                         tag == Collation::HANGUL_TAG);
1010             }
1011         }
1012         return ce32;
1013     }
1014 
1015     const CollationDataBuilder &src;
1016     CollationDataBuilder &dest;
1017     const CollationDataBuilder::CEModifier &modifier;
1018     int64_t modifiedCEs[Collation::MAX_EXPANSION_LENGTH];
1019     UErrorCode errorCode;
1020 };
1021 
1022 U_CDECL_BEGIN
1023 
1024 static UBool U_CALLCONV
enumRangeForCopy(const void * context,UChar32 start,UChar32 end,uint32_t value)1025 enumRangeForCopy(const void *context, UChar32 start, UChar32 end, uint32_t value) {
1026     return
1027         value == Collation::UNASSIGNED_CE32 || value == Collation::FALLBACK_CE32 ||
1028         ((CopyHelper *)context)->copyRangeCE32(start, end, value);
1029 }
1030 
1031 U_CDECL_END
1032 
1033 void
copyFrom(const CollationDataBuilder & src,const CEModifier & modifier,UErrorCode & errorCode)1034 CollationDataBuilder::copyFrom(const CollationDataBuilder &src, const CEModifier &modifier,
1035                                UErrorCode &errorCode) {
1036     if(U_FAILURE(errorCode)) { return; }
1037     if(trie == NULL || utrie2_isFrozen(trie)) {
1038         errorCode = U_INVALID_STATE_ERROR;
1039         return;
1040     }
1041     CopyHelper helper(src, *this, modifier, errorCode);
1042     utrie2_enum(src.trie, NULL, enumRangeForCopy, &helper);
1043     errorCode = helper.errorCode;
1044     // Update the contextChars and the unsafeBackwardSet while copying,
1045     // in case a character had conditional mappings in the source builder
1046     // and they were removed later.
1047     modified |= src.modified;
1048 }
1049 
1050 void
optimize(const UnicodeSet & set,UErrorCode & errorCode)1051 CollationDataBuilder::optimize(const UnicodeSet &set, UErrorCode &errorCode) {
1052     if(U_FAILURE(errorCode) || set.isEmpty()) { return; }
1053     UnicodeSetIterator iter(set);
1054     while(iter.next() && !iter.isString()) {
1055         UChar32 c = iter.getCodepoint();
1056         uint32_t ce32 = utrie2_get32(trie, c);
1057         if(ce32 == Collation::FALLBACK_CE32) {
1058             ce32 = base->getFinalCE32(base->getCE32(c));
1059             ce32 = copyFromBaseCE32(c, ce32, TRUE, errorCode);
1060             utrie2_set32(trie, c, ce32, &errorCode);
1061         }
1062     }
1063     modified = TRUE;
1064 }
1065 
1066 void
suppressContractions(const UnicodeSet & set,UErrorCode & errorCode)1067 CollationDataBuilder::suppressContractions(const UnicodeSet &set, UErrorCode &errorCode) {
1068     if(U_FAILURE(errorCode) || set.isEmpty()) { return; }
1069     UnicodeSetIterator iter(set);
1070     while(iter.next() && !iter.isString()) {
1071         UChar32 c = iter.getCodepoint();
1072         uint32_t ce32 = utrie2_get32(trie, c);
1073         if(ce32 == Collation::FALLBACK_CE32) {
1074             ce32 = base->getFinalCE32(base->getCE32(c));
1075             if(Collation::ce32HasContext(ce32)) {
1076                 ce32 = copyFromBaseCE32(c, ce32, FALSE /* without context */, errorCode);
1077                 utrie2_set32(trie, c, ce32, &errorCode);
1078             }
1079         } else if(isBuilderContextCE32(ce32)) {
1080             ce32 = getConditionalCE32ForCE32(ce32)->ce32;
1081             // Simply abandon the list of ConditionalCE32.
1082             // The caller will copy this builder in the end,
1083             // eliminating unreachable data.
1084             utrie2_set32(trie, c, ce32, &errorCode);
1085             contextChars.remove(c);
1086         }
1087     }
1088     modified = TRUE;
1089 }
1090 
1091 UBool
getJamoCE32s(uint32_t jamoCE32s[],UErrorCode & errorCode)1092 CollationDataBuilder::getJamoCE32s(uint32_t jamoCE32s[], UErrorCode &errorCode) {
1093     if(U_FAILURE(errorCode)) { return FALSE; }
1094     UBool anyJamoAssigned = base == NULL;  // always set jamoCE32s in the base data
1095     UBool needToCopyFromBase = FALSE;
1096     for(int32_t j = 0; j < CollationData::JAMO_CE32S_LENGTH; ++j) {  // Count across Jamo types.
1097         UChar32 jamo = jamoCpFromIndex(j);
1098         UBool fromBase = FALSE;
1099         uint32_t ce32 = utrie2_get32(trie, jamo);
1100         anyJamoAssigned |= Collation::isAssignedCE32(ce32);
1101         // TODO: Try to prevent [optimize [Jamo]] from counting as anyJamoAssigned.
1102         // (As of CLDR 24 [2013] the Korean tailoring does not optimize conjoining Jamo.)
1103         if(ce32 == Collation::FALLBACK_CE32) {
1104             fromBase = TRUE;
1105             ce32 = base->getCE32(jamo);
1106         }
1107         if(Collation::isSpecialCE32(ce32)) {
1108             switch(Collation::tagFromCE32(ce32)) {
1109             case Collation::LONG_PRIMARY_TAG:
1110             case Collation::LONG_SECONDARY_TAG:
1111             case Collation::LATIN_EXPANSION_TAG:
1112                 // Copy the ce32 as-is.
1113                 break;
1114             case Collation::EXPANSION32_TAG:
1115             case Collation::EXPANSION_TAG:
1116             case Collation::PREFIX_TAG:
1117             case Collation::CONTRACTION_TAG:
1118                 if(fromBase) {
1119                     // Defer copying until we know if anyJamoAssigned.
1120                     ce32 = Collation::FALLBACK_CE32;
1121                     needToCopyFromBase = TRUE;
1122                 }
1123                 break;
1124             case Collation::IMPLICIT_TAG:
1125                 // An unassigned Jamo should only occur in tests with incomplete bases.
1126                 U_ASSERT(fromBase);
1127                 ce32 = Collation::FALLBACK_CE32;
1128                 needToCopyFromBase = TRUE;
1129                 break;
1130             case Collation::OFFSET_TAG:
1131                 ce32 = getCE32FromOffsetCE32(fromBase, jamo, ce32);
1132                 break;
1133             case Collation::FALLBACK_TAG:
1134             case Collation::RESERVED_TAG_3:
1135             case Collation::BUILDER_DATA_TAG:
1136             case Collation::DIGIT_TAG:
1137             case Collation::U0000_TAG:
1138             case Collation::HANGUL_TAG:
1139             case Collation::LEAD_SURROGATE_TAG:
1140                 errorCode = U_INTERNAL_PROGRAM_ERROR;
1141                 return FALSE;
1142             }
1143         }
1144         jamoCE32s[j] = ce32;
1145     }
1146     if(anyJamoAssigned && needToCopyFromBase) {
1147         for(int32_t j = 0; j < CollationData::JAMO_CE32S_LENGTH; ++j) {
1148             if(jamoCE32s[j] == Collation::FALLBACK_CE32) {
1149                 UChar32 jamo = jamoCpFromIndex(j);
1150                 jamoCE32s[j] = copyFromBaseCE32(jamo, base->getCE32(jamo),
1151                                                 /*withContext=*/ TRUE, errorCode);
1152             }
1153         }
1154     }
1155     return anyJamoAssigned && U_SUCCESS(errorCode);
1156 }
1157 
1158 void
setDigitTags(UErrorCode & errorCode)1159 CollationDataBuilder::setDigitTags(UErrorCode &errorCode) {
1160     UnicodeSet digits(UNICODE_STRING_SIMPLE("[:Nd:]"), errorCode);
1161     if(U_FAILURE(errorCode)) { return; }
1162     UnicodeSetIterator iter(digits);
1163     while(iter.next()) {
1164         U_ASSERT(!iter.isString());
1165         UChar32 c = iter.getCodepoint();
1166         uint32_t ce32 = utrie2_get32(trie, c);
1167         if(ce32 != Collation::FALLBACK_CE32 && ce32 != Collation::UNASSIGNED_CE32) {
1168             int32_t index = addCE32(ce32, errorCode);
1169             if(U_FAILURE(errorCode)) { return; }
1170             if(index > Collation::MAX_INDEX) {
1171                 errorCode = U_BUFFER_OVERFLOW_ERROR;
1172                 return;
1173             }
1174             ce32 = Collation::makeCE32FromTagIndexAndLength(
1175                     Collation::DIGIT_TAG, index, u_charDigitValue(c));
1176             utrie2_set32(trie, c, ce32, &errorCode);
1177         }
1178     }
1179 }
1180 
1181 U_CDECL_BEGIN
1182 
1183 static UBool U_CALLCONV
enumRangeLeadValue(const void * context,UChar32,UChar32,uint32_t value)1184 enumRangeLeadValue(const void *context, UChar32 /*start*/, UChar32 /*end*/, uint32_t value) {
1185     int32_t *pValue = (int32_t *)context;
1186     if(value == Collation::UNASSIGNED_CE32) {
1187         value = Collation::LEAD_ALL_UNASSIGNED;
1188     } else if(value == Collation::FALLBACK_CE32) {
1189         value = Collation::LEAD_ALL_FALLBACK;
1190     } else {
1191         *pValue = Collation::LEAD_MIXED;
1192         return FALSE;
1193     }
1194     if(*pValue < 0) {
1195         *pValue = (int32_t)value;
1196     } else if(*pValue != (int32_t)value) {
1197         *pValue = Collation::LEAD_MIXED;
1198         return FALSE;
1199     }
1200     return TRUE;
1201 }
1202 
1203 U_CDECL_END
1204 
1205 void
setLeadSurrogates(UErrorCode & errorCode)1206 CollationDataBuilder::setLeadSurrogates(UErrorCode &errorCode) {
1207     for(UChar lead = 0xd800; lead < 0xdc00; ++lead) {
1208         int32_t value = -1;
1209         utrie2_enumForLeadSurrogate(trie, lead, NULL, enumRangeLeadValue, &value);
1210         utrie2_set32ForLeadSurrogateCodeUnit(
1211             trie, lead,
1212             Collation::makeCE32FromTagAndIndex(Collation::LEAD_SURROGATE_TAG, 0) | (uint32_t)value,
1213             &errorCode);
1214     }
1215 }
1216 
1217 void
build(CollationData & data,UErrorCode & errorCode)1218 CollationDataBuilder::build(CollationData &data, UErrorCode &errorCode) {
1219     buildMappings(data, errorCode);
1220     if(base != NULL) {
1221         data.numericPrimary = base->numericPrimary;
1222         data.compressibleBytes = base->compressibleBytes;
1223         data.numScripts = base->numScripts;
1224         data.scriptsIndex = base->scriptsIndex;
1225         data.scriptStarts = base->scriptStarts;
1226         data.scriptStartsLength = base->scriptStartsLength;
1227     }
1228     buildFastLatinTable(data, errorCode);
1229 }
1230 
1231 void
buildMappings(CollationData & data,UErrorCode & errorCode)1232 CollationDataBuilder::buildMappings(CollationData &data, UErrorCode &errorCode) {
1233     if(U_FAILURE(errorCode)) { return; }
1234     if(trie == NULL || utrie2_isFrozen(trie)) {
1235         errorCode = U_INVALID_STATE_ERROR;
1236         return;
1237     }
1238 
1239     buildContexts(errorCode);
1240 
1241     uint32_t jamoCE32s[CollationData::JAMO_CE32S_LENGTH];
1242     int32_t jamoIndex = -1;
1243     if(getJamoCE32s(jamoCE32s, errorCode)) {
1244         jamoIndex = ce32s.size();
1245         for(int32_t i = 0; i < CollationData::JAMO_CE32S_LENGTH; ++i) {
1246             ce32s.addElement((int32_t)jamoCE32s[i], errorCode);
1247         }
1248         // Small optimization: Use a bit in the Hangul ce32
1249         // to indicate that none of the Jamo CE32s are isSpecialCE32()
1250         // (as it should be in the root collator).
1251         // It allows CollationIterator to avoid recursive function calls and per-Jamo tests.
1252         // In order to still have good trie compression and keep this code simple,
1253         // we only set this flag if a whole block of 588 Hangul syllables starting with
1254         // a common leading consonant (Jamo L) has this property.
1255         UBool isAnyJamoVTSpecial = FALSE;
1256         for(int32_t i = Hangul::JAMO_L_COUNT; i < CollationData::JAMO_CE32S_LENGTH; ++i) {
1257             if(Collation::isSpecialCE32(jamoCE32s[i])) {
1258                 isAnyJamoVTSpecial = TRUE;
1259                 break;
1260             }
1261         }
1262         uint32_t hangulCE32 = Collation::makeCE32FromTagAndIndex(Collation::HANGUL_TAG, 0);
1263         UChar32 c = Hangul::HANGUL_BASE;
1264         for(int32_t i = 0; i < Hangul::JAMO_L_COUNT; ++i) {  // iterate over the Jamo L
1265             uint32_t ce32 = hangulCE32;
1266             if(!isAnyJamoVTSpecial && !Collation::isSpecialCE32(jamoCE32s[i])) {
1267                 ce32 |= Collation::HANGUL_NO_SPECIAL_JAMO;
1268             }
1269             UChar32 limit = c + Hangul::JAMO_VT_COUNT;
1270             utrie2_setRange32(trie, c, limit - 1, ce32, TRUE, &errorCode);
1271             c = limit;
1272         }
1273     } else {
1274         // Copy the Hangul CE32s from the base in blocks per Jamo L,
1275         // assuming that HANGUL_NO_SPECIAL_JAMO is set or not set for whole blocks.
1276         for(UChar32 c = Hangul::HANGUL_BASE; c < Hangul::HANGUL_LIMIT;) {
1277             uint32_t ce32 = base->getCE32(c);
1278             U_ASSERT(Collation::hasCE32Tag(ce32, Collation::HANGUL_TAG));
1279             UChar32 limit = c + Hangul::JAMO_VT_COUNT;
1280             utrie2_setRange32(trie, c, limit - 1, ce32, TRUE, &errorCode);
1281             c = limit;
1282         }
1283     }
1284 
1285     setDigitTags(errorCode);
1286     setLeadSurrogates(errorCode);
1287 
1288     // For U+0000, move its normal ce32 into CE32s[0] and set U0000_TAG.
1289     ce32s.setElementAt((int32_t)utrie2_get32(trie, 0), 0);
1290     utrie2_set32(trie, 0, Collation::makeCE32FromTagAndIndex(Collation::U0000_TAG, 0), &errorCode);
1291 
1292     utrie2_freeze(trie, UTRIE2_32_VALUE_BITS, &errorCode);
1293     if(U_FAILURE(errorCode)) { return; }
1294 
1295     // Mark each lead surrogate as "unsafe"
1296     // if any of its 1024 associated supplementary code points is "unsafe".
1297     UChar32 c = 0x10000;
1298     for(UChar lead = 0xd800; lead < 0xdc00; ++lead, c += 0x400) {
1299         if(unsafeBackwardSet.containsSome(c, c + 0x3ff)) {
1300             unsafeBackwardSet.add(lead);
1301         }
1302     }
1303     unsafeBackwardSet.freeze();
1304 
1305     data.trie = trie;
1306     data.ce32s = reinterpret_cast<const uint32_t *>(ce32s.getBuffer());
1307     data.ces = ce64s.getBuffer();
1308     data.contexts = contexts.getBuffer();
1309 
1310     data.ce32sLength = ce32s.size();
1311     data.cesLength = ce64s.size();
1312     data.contextsLength = contexts.length();
1313 
1314     data.base = base;
1315     if(jamoIndex >= 0) {
1316         data.jamoCE32s = data.ce32s + jamoIndex;
1317     } else {
1318         data.jamoCE32s = base->jamoCE32s;
1319     }
1320     data.unsafeBackwardSet = &unsafeBackwardSet;
1321 }
1322 
1323 void
clearContexts()1324 CollationDataBuilder::clearContexts() {
1325     contexts.remove();
1326     UnicodeSetIterator iter(contextChars);
1327     while(iter.next()) {
1328         U_ASSERT(!iter.isString());
1329         uint32_t ce32 = utrie2_get32(trie, iter.getCodepoint());
1330         U_ASSERT(isBuilderContextCE32(ce32));
1331         getConditionalCE32ForCE32(ce32)->builtCE32 = Collation::NO_CE32;
1332     }
1333 }
1334 
1335 void
buildContexts(UErrorCode & errorCode)1336 CollationDataBuilder::buildContexts(UErrorCode &errorCode) {
1337     if(U_FAILURE(errorCode)) { return; }
1338     // Ignore abandoned lists and the cached builtCE32,
1339     // and build all contexts from scratch.
1340     contexts.remove();
1341     UnicodeSetIterator iter(contextChars);
1342     while(U_SUCCESS(errorCode) && iter.next()) {
1343         U_ASSERT(!iter.isString());
1344         UChar32 c = iter.getCodepoint();
1345         uint32_t ce32 = utrie2_get32(trie, c);
1346         if(!isBuilderContextCE32(ce32)) {
1347             // Impossible: No context data for c in contextChars.
1348             errorCode = U_INTERNAL_PROGRAM_ERROR;
1349             return;
1350         }
1351         ConditionalCE32 *cond = getConditionalCE32ForCE32(ce32);
1352         ce32 = buildContext(cond, errorCode);
1353         utrie2_set32(trie, c, ce32, &errorCode);
1354     }
1355 }
1356 
1357 uint32_t
buildContext(ConditionalCE32 * head,UErrorCode & errorCode)1358 CollationDataBuilder::buildContext(ConditionalCE32 *head, UErrorCode &errorCode) {
1359     if(U_FAILURE(errorCode)) { return 0; }
1360     // The list head must have no context.
1361     U_ASSERT(!head->hasContext());
1362     // The list head must be followed by one or more nodes that all do have context.
1363     U_ASSERT(head->next >= 0);
1364     UCharsTrieBuilder prefixBuilder(errorCode);
1365     UCharsTrieBuilder contractionBuilder(errorCode);
1366     for(ConditionalCE32 *cond = head;; cond = getConditionalCE32(cond->next)) {
1367         // After the list head, the prefix or suffix can be empty, but not both.
1368         U_ASSERT(cond == head || cond->hasContext());
1369         int32_t prefixLength = cond->prefixLength();
1370         UnicodeString prefix(cond->context, 0, prefixLength + 1);
1371         // Collect all contraction suffixes for one prefix.
1372         ConditionalCE32 *firstCond = cond;
1373         ConditionalCE32 *lastCond = cond;
1374         while(cond->next >= 0 &&
1375                 (cond = getConditionalCE32(cond->next))->context.startsWith(prefix)) {
1376             lastCond = cond;
1377         }
1378         uint32_t ce32;
1379         int32_t suffixStart = prefixLength + 1;  // == prefix.length()
1380         if(lastCond->context.length() == suffixStart) {
1381             // One prefix without contraction suffix.
1382             U_ASSERT(firstCond == lastCond);
1383             ce32 = lastCond->ce32;
1384             cond = lastCond;
1385         } else {
1386             // Build the contractions trie.
1387             contractionBuilder.clear();
1388             // Entry for an empty suffix, to be stored before the trie.
1389             uint32_t emptySuffixCE32 = 0;
1390             uint32_t flags = 0;
1391             if(firstCond->context.length() == suffixStart) {
1392                 // There is a mapping for the prefix and the single character c. (p|c)
1393                 // If no other suffix matches, then we return this value.
1394                 emptySuffixCE32 = firstCond->ce32;
1395                 cond = getConditionalCE32(firstCond->next);
1396             } else {
1397                 // There is no mapping for the prefix and just the single character.
1398                 // (There is no p|c, only p|cd, p|ce etc.)
1399                 flags |= Collation::CONTRACT_SINGLE_CP_NO_MATCH;
1400                 // When the prefix matches but none of the prefix-specific suffixes,
1401                 // then we fall back to the mappings with the next-longest prefix,
1402                 // and ultimately to mappings with no prefix.
1403                 // Each fallback might be another set of contractions.
1404                 // For example, if there are mappings for ch, p|cd, p|ce, but not for p|c,
1405                 // then in text "pch" we find the ch contraction.
1406                 for(cond = head;; cond = getConditionalCE32(cond->next)) {
1407                     int32_t length = cond->prefixLength();
1408                     if(length == prefixLength) { break; }
1409                     if(cond->defaultCE32 != Collation::NO_CE32 &&
1410                             (length==0 || prefix.endsWith(cond->context, 1, length))) {
1411                         emptySuffixCE32 = cond->defaultCE32;
1412                     }
1413                 }
1414                 cond = firstCond;
1415             }
1416             // Optimization: Set a flag when
1417             // the first character of every contraction suffix has lccc!=0.
1418             // Short-circuits contraction matching when a normal letter follows.
1419             flags |= Collation::CONTRACT_NEXT_CCC;
1420             // Add all of the non-empty suffixes into the contraction trie.
1421             for(;;) {
1422                 UnicodeString suffix(cond->context, suffixStart);
1423                 uint16_t fcd16 = nfcImpl.getFCD16(suffix.char32At(0));
1424                 if(fcd16 <= 0xff) {
1425                     flags &= ~Collation::CONTRACT_NEXT_CCC;
1426                 }
1427                 fcd16 = nfcImpl.getFCD16(suffix.char32At(suffix.length() - 1));
1428                 if(fcd16 > 0xff) {
1429                     // The last suffix character has lccc!=0, allowing for discontiguous contractions.
1430                     flags |= Collation::CONTRACT_TRAILING_CCC;
1431                 }
1432                 contractionBuilder.add(suffix, (int32_t)cond->ce32, errorCode);
1433                 if(cond == lastCond) { break; }
1434                 cond = getConditionalCE32(cond->next);
1435             }
1436             int32_t index = addContextTrie(emptySuffixCE32, contractionBuilder, errorCode);
1437             if(U_FAILURE(errorCode)) { return 0; }
1438             if(index > Collation::MAX_INDEX) {
1439                 errorCode = U_BUFFER_OVERFLOW_ERROR;
1440                 return 0;
1441             }
1442             ce32 = Collation::makeCE32FromTagAndIndex(Collation::CONTRACTION_TAG, index) | flags;
1443         }
1444         U_ASSERT(cond == lastCond);
1445         firstCond->defaultCE32 = ce32;
1446         if(prefixLength == 0) {
1447             if(cond->next < 0) {
1448                 // No non-empty prefixes, only contractions.
1449                 return ce32;
1450             }
1451         } else {
1452             prefix.remove(0, 1);  // Remove the length unit.
1453             prefix.reverse();
1454             prefixBuilder.add(prefix, (int32_t)ce32, errorCode);
1455             if(cond->next < 0) { break; }
1456         }
1457     }
1458     U_ASSERT(head->defaultCE32 != Collation::NO_CE32);
1459     int32_t index = addContextTrie(head->defaultCE32, prefixBuilder, errorCode);
1460     if(U_FAILURE(errorCode)) { return 0; }
1461     if(index > Collation::MAX_INDEX) {
1462         errorCode = U_BUFFER_OVERFLOW_ERROR;
1463         return 0;
1464     }
1465     return Collation::makeCE32FromTagAndIndex(Collation::PREFIX_TAG, index);
1466 }
1467 
1468 int32_t
addContextTrie(uint32_t defaultCE32,UCharsTrieBuilder & trieBuilder,UErrorCode & errorCode)1469 CollationDataBuilder::addContextTrie(uint32_t defaultCE32, UCharsTrieBuilder &trieBuilder,
1470                                      UErrorCode &errorCode) {
1471     UnicodeString context;
1472     context.append((UChar)(defaultCE32 >> 16)).append((UChar)defaultCE32);
1473     UnicodeString trieString;
1474     context.append(trieBuilder.buildUnicodeString(USTRINGTRIE_BUILD_SMALL, trieString, errorCode));
1475     if(U_FAILURE(errorCode)) { return -1; }
1476     int32_t index = contexts.indexOf(context);
1477     if(index < 0) {
1478         index = contexts.length();
1479         contexts.append(context);
1480     }
1481     return index;
1482 }
1483 
1484 void
buildFastLatinTable(CollationData & data,UErrorCode & errorCode)1485 CollationDataBuilder::buildFastLatinTable(CollationData &data, UErrorCode &errorCode) {
1486     if(U_FAILURE(errorCode) || !fastLatinEnabled) { return; }
1487 
1488     delete fastLatinBuilder;
1489     fastLatinBuilder = new CollationFastLatinBuilder(errorCode);
1490     if(fastLatinBuilder == NULL) {
1491         errorCode = U_MEMORY_ALLOCATION_ERROR;
1492         return;
1493     }
1494     if(fastLatinBuilder->forData(data, errorCode)) {
1495         const uint16_t *table = fastLatinBuilder->getTable();
1496         int32_t length = fastLatinBuilder->lengthOfTable();
1497         if(base != NULL && length == base->fastLatinTableLength &&
1498                 uprv_memcmp(table, base->fastLatinTable, length * 2) == 0) {
1499             // Same fast Latin table as in the base, use that one instead.
1500             delete fastLatinBuilder;
1501             fastLatinBuilder = NULL;
1502             table = base->fastLatinTable;
1503         }
1504         data.fastLatinTable = table;
1505         data.fastLatinTableLength = length;
1506     } else {
1507         delete fastLatinBuilder;
1508         fastLatinBuilder = NULL;
1509     }
1510 }
1511 
1512 int32_t
getCEs(const UnicodeString & s,int64_t ces[],int32_t cesLength)1513 CollationDataBuilder::getCEs(const UnicodeString &s, int64_t ces[], int32_t cesLength) {
1514     return getCEs(s, 0, ces, cesLength);
1515 }
1516 
1517 int32_t
getCEs(const UnicodeString & prefix,const UnicodeString & s,int64_t ces[],int32_t cesLength)1518 CollationDataBuilder::getCEs(const UnicodeString &prefix, const UnicodeString &s,
1519                              int64_t ces[], int32_t cesLength) {
1520     int32_t prefixLength = prefix.length();
1521     if(prefixLength == 0) {
1522         return getCEs(s, 0, ces, cesLength);
1523     } else {
1524         return getCEs(prefix + s, prefixLength, ces, cesLength);
1525     }
1526 }
1527 
1528 int32_t
getCEs(const UnicodeString & s,int32_t start,int64_t ces[],int32_t cesLength)1529 CollationDataBuilder::getCEs(const UnicodeString &s, int32_t start,
1530                              int64_t ces[], int32_t cesLength) {
1531     if(collIter == NULL) {
1532         collIter = new DataBuilderCollationIterator(*this);
1533         if(collIter == NULL) { return 0; }
1534     }
1535     return collIter->fetchCEs(s, start, ces, cesLength);
1536 }
1537 
1538 U_NAMESPACE_END
1539 
1540 #endif  // !UCONFIG_NO_COLLATION
1541