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