tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

collationbuilder.cpp (74559B)

      1 // © 2016 and later: Unicode, Inc. and others.
      2 // License & terms of use: http://www.unicode.org/copyright.html
      3 /*
      4 *******************************************************************************
      5 * Copyright (C) 2013-2014, International Business Machines
      6 * Corporation and others.  All Rights Reserved.
      7 *******************************************************************************
      8 * collationbuilder.cpp
      9 *
     10 * (replaced the former ucol_bld.cpp)
     11 *
     12 * created on: 2013may06
     13 * created by: Markus W. Scherer
     14 */
     15 
     16 #ifdef DEBUG_COLLATION_BUILDER
     17 #include <stdio.h>
     18 #endif
     19 
     20 #include "unicode/utypes.h"
     21 
     22 #if !UCONFIG_NO_COLLATION
     23 
     24 #include "unicode/caniter.h"
     25 #include "unicode/normalizer2.h"
     26 #include "unicode/tblcoll.h"
     27 #include "unicode/parseerr.h"
     28 #include "unicode/uchar.h"
     29 #include "unicode/ucol.h"
     30 #include "unicode/unistr.h"
     31 #include "unicode/usetiter.h"
     32 #include "unicode/utf16.h"
     33 #include "unicode/uversion.h"
     34 #include "cmemory.h"
     35 #include "collation.h"
     36 #include "collationbuilder.h"
     37 #include "collationdata.h"
     38 #include "collationdatabuilder.h"
     39 #include "collationfastlatin.h"
     40 #include "collationroot.h"
     41 #include "collationrootelements.h"
     42 #include "collationruleparser.h"
     43 #include "collationsettings.h"
     44 #include "collationtailoring.h"
     45 #include "collationweights.h"
     46 #include "normalizer2impl.h"
     47 #include "uassert.h"
     48 #include "ucol_imp.h"
     49 #include "utf16collationiterator.h"
     50 
     51 U_NAMESPACE_BEGIN
     52 
     53 namespace {
     54 
     55 class BundleImporter : public CollationRuleParser::Importer {
     56 public:
     57    BundleImporter() {}
     58    virtual ~BundleImporter();
     59    virtual void getRules(
     60            const char *localeID, const char *collationType,
     61            UnicodeString &rules,
     62            const char *&errorReason, UErrorCode &errorCode) override;
     63 };
     64 
     65 BundleImporter::~BundleImporter() {}
     66 
     67 void
     68 BundleImporter::getRules(
     69        const char *localeID, const char *collationType,
     70        UnicodeString &rules,
     71        const char *& /*errorReason*/, UErrorCode &errorCode) {
     72    CollationLoader::loadRules(localeID, collationType, rules, errorCode);
     73 }
     74 
     75 }  // namespace
     76 
     77 // RuleBasedCollator implementation ---------------------------------------- ***
     78 
     79 // These methods are here, rather than in rulebasedcollator.cpp,
     80 // for modularization:
     81 // Most code using Collator does not need to build a Collator from rules.
     82 // By moving these constructors and helper methods to a separate file,
     83 // most code will not have a static dependency on the builder code.
     84 
     85 RuleBasedCollator::RuleBasedCollator()
     86        : data(nullptr),
     87          settings(nullptr),
     88          tailoring(nullptr),
     89          cacheEntry(nullptr),
     90          validLocale(""),
     91          explicitlySetAttributes(0),
     92          actualLocaleIsSameAsValid(false) {
     93 }
     94 
     95 RuleBasedCollator::RuleBasedCollator(const UnicodeString &rules, UErrorCode &errorCode)
     96        : data(nullptr),
     97          settings(nullptr),
     98          tailoring(nullptr),
     99          cacheEntry(nullptr),
    100          validLocale(""),
    101          explicitlySetAttributes(0),
    102          actualLocaleIsSameAsValid(false) {
    103    internalBuildTailoring(rules, UCOL_DEFAULT, UCOL_DEFAULT, nullptr, nullptr, errorCode);
    104 }
    105 
    106 RuleBasedCollator::RuleBasedCollator(const UnicodeString &rules, ECollationStrength strength,
    107                                     UErrorCode &errorCode)
    108        : data(nullptr),
    109          settings(nullptr),
    110          tailoring(nullptr),
    111          cacheEntry(nullptr),
    112          validLocale(""),
    113          explicitlySetAttributes(0),
    114          actualLocaleIsSameAsValid(false) {
    115    internalBuildTailoring(rules, strength, UCOL_DEFAULT, nullptr, nullptr, errorCode);
    116 }
    117 
    118 RuleBasedCollator::RuleBasedCollator(const UnicodeString &rules,
    119                                     UColAttributeValue decompositionMode,
    120                                     UErrorCode &errorCode)
    121        : data(nullptr),
    122          settings(nullptr),
    123          tailoring(nullptr),
    124          cacheEntry(nullptr),
    125          validLocale(""),
    126          explicitlySetAttributes(0),
    127          actualLocaleIsSameAsValid(false) {
    128    internalBuildTailoring(rules, UCOL_DEFAULT, decompositionMode, nullptr, nullptr, errorCode);
    129 }
    130 
    131 RuleBasedCollator::RuleBasedCollator(const UnicodeString &rules,
    132                                     ECollationStrength strength,
    133                                     UColAttributeValue decompositionMode,
    134                                     UErrorCode &errorCode)
    135        : data(nullptr),
    136          settings(nullptr),
    137          tailoring(nullptr),
    138          cacheEntry(nullptr),
    139          validLocale(""),
    140          explicitlySetAttributes(0),
    141          actualLocaleIsSameAsValid(false) {
    142    internalBuildTailoring(rules, strength, decompositionMode, nullptr, nullptr, errorCode);
    143 }
    144 
    145 RuleBasedCollator::RuleBasedCollator(const UnicodeString &rules,
    146                                     UParseError &parseError, UnicodeString &reason,
    147                                     UErrorCode &errorCode)
    148        : data(nullptr),
    149          settings(nullptr),
    150          tailoring(nullptr),
    151          cacheEntry(nullptr),
    152          validLocale(""),
    153          explicitlySetAttributes(0),
    154          actualLocaleIsSameAsValid(false) {
    155    internalBuildTailoring(rules, UCOL_DEFAULT, UCOL_DEFAULT, &parseError, &reason, errorCode);
    156 }
    157 
    158 void
    159 RuleBasedCollator::internalBuildTailoring(const UnicodeString &rules,
    160                                          int32_t strength,
    161                                          UColAttributeValue decompositionMode,
    162                                          UParseError *outParseError, UnicodeString *outReason,
    163                                          UErrorCode &errorCode) {
    164    const CollationTailoring *base = CollationRoot::getRoot(errorCode);
    165    if(U_FAILURE(errorCode)) { return; }
    166    if(outReason != nullptr) { outReason->remove(); }
    167    CollationBuilder builder(base, errorCode);
    168    UVersionInfo noVersion = { 0, 0, 0, 0 };
    169    BundleImporter importer;
    170    LocalPointer<CollationTailoring> t(builder.parseAndBuild(rules, noVersion,
    171                                                             &importer,
    172                                                             outParseError, errorCode));
    173    if(U_FAILURE(errorCode)) {
    174        const char *reason = builder.getErrorReason();
    175        if(reason != nullptr && outReason != nullptr) {
    176            *outReason = UnicodeString(reason, -1, US_INV);
    177        }
    178        return;
    179    }
    180    t->actualLocale.setToBogus();
    181    adoptTailoring(t.orphan(), errorCode);
    182    // Set attributes after building the collator,
    183    // to keep the default settings consistent with the rule string.
    184    if(strength != UCOL_DEFAULT) {
    185        setAttribute(UCOL_STRENGTH, static_cast<UColAttributeValue>(strength), errorCode);
    186    }
    187    if(decompositionMode != UCOL_DEFAULT) {
    188        setAttribute(UCOL_NORMALIZATION_MODE, decompositionMode, errorCode);
    189    }
    190 }
    191 
    192 // CollationBuilder implementation ----------------------------------------- ***
    193 
    194 CollationBuilder::CollationBuilder(const CollationTailoring *b, UBool icu4xMode, UErrorCode &errorCode)
    195        : nfd(*Normalizer2::getNFDInstance(errorCode)),
    196          fcd(*Normalizer2Factory::getFCDInstance(errorCode)),
    197          nfcImpl(*Normalizer2Factory::getNFCImpl(errorCode)),
    198          base(b),
    199          baseData(b->data),
    200          rootElements(b->data->rootElements, b->data->rootElementsLength),
    201          variableTop(0),
    202          dataBuilder(new CollationDataBuilder(icu4xMode, errorCode)), fastLatinEnabled(true),
    203          icu4xMode(icu4xMode),
    204          errorReason(nullptr),
    205          cesLength(0),
    206          rootPrimaryIndexes(errorCode), nodes(errorCode) {
    207    nfcImpl.ensureCanonIterData(errorCode);
    208    if(U_FAILURE(errorCode)) {
    209        errorReason = "CollationBuilder fields initialization failed";
    210        return;
    211    }
    212    if(dataBuilder == nullptr) {
    213        errorCode = U_MEMORY_ALLOCATION_ERROR;
    214        return;
    215    }
    216    dataBuilder->initForTailoring(baseData, errorCode);
    217    if(U_FAILURE(errorCode)) {
    218        errorReason = "CollationBuilder initialization failed";
    219    }
    220 }
    221 
    222 CollationBuilder::CollationBuilder(const CollationTailoring *b, UErrorCode &errorCode)
    223  : CollationBuilder(b, false, errorCode)
    224 {}
    225 
    226 CollationBuilder::~CollationBuilder() {
    227    delete dataBuilder;
    228 }
    229 
    230 CollationTailoring *
    231 CollationBuilder::parseAndBuild(const UnicodeString &ruleString,
    232                                const UVersionInfo rulesVersion,
    233                                CollationRuleParser::Importer *importer,
    234                                UParseError *outParseError,
    235                                UErrorCode &errorCode) {
    236    if(U_FAILURE(errorCode)) { return nullptr; }
    237    if(baseData->rootElements == nullptr) {
    238        errorCode = U_MISSING_RESOURCE_ERROR;
    239        errorReason = "missing root elements data, tailoring not supported";
    240        return nullptr;
    241    }
    242    LocalPointer<CollationTailoring> tailoring(new CollationTailoring(base->settings));
    243    if(tailoring.isNull() || tailoring->isBogus()) {
    244        errorCode = U_MEMORY_ALLOCATION_ERROR;
    245        return nullptr;
    246    }
    247    CollationRuleParser parser(baseData, errorCode);
    248    if(U_FAILURE(errorCode)) { return nullptr; }
    249    // Note: This always bases &[last variable] and &[first regular]
    250    // on the root collator's maxVariable/variableTop.
    251    // If we wanted this to change after [maxVariable x], then we would keep
    252    // the tailoring.settings pointer here and read its variableTop when we need it.
    253    // See http://unicode.org/cldr/trac/ticket/6070
    254    variableTop = base->settings->variableTop;
    255    parser.setSink(this);
    256    parser.setImporter(importer);
    257    CollationSettings &ownedSettings = *SharedObject::copyOnWrite(tailoring->settings);
    258    parser.parse(ruleString, ownedSettings, outParseError, errorCode);
    259    errorReason = parser.getErrorReason();
    260    if(U_FAILURE(errorCode)) { return nullptr; }
    261    if(dataBuilder->hasMappings()) {
    262        makeTailoredCEs(errorCode);
    263        if (!icu4xMode) {
    264            closeOverComposites(errorCode);
    265        }
    266        finalizeCEs(errorCode);
    267        if (!icu4xMode) {
    268            // Copy all of ASCII, and Latin-1 letters, into each tailoring.
    269            optimizeSet.add(0, 0x7f);
    270            optimizeSet.add(0xc0, 0xff);
    271            // Hangul is decomposed on the fly during collation,
    272            // and the tailoring data is always built with HANGUL_TAG specials.
    273            optimizeSet.remove(Hangul::HANGUL_BASE, Hangul::HANGUL_END);
    274            dataBuilder->optimize(optimizeSet, errorCode);
    275        }
    276        tailoring->ensureOwnedData(errorCode);
    277        if(U_FAILURE(errorCode)) { return nullptr; }
    278        if(fastLatinEnabled) { dataBuilder->enableFastLatin(); }
    279        dataBuilder->build(*tailoring->ownedData, errorCode);
    280        tailoring->builder = dataBuilder;
    281        dataBuilder = nullptr;
    282    } else {
    283        tailoring->data = baseData;
    284    }
    285    if(U_FAILURE(errorCode)) { return nullptr; }
    286    ownedSettings.fastLatinOptions = CollationFastLatin::getOptions(
    287        tailoring->data, ownedSettings,
    288        ownedSettings.fastLatinPrimaries, UPRV_LENGTHOF(ownedSettings.fastLatinPrimaries));
    289    tailoring->rules = ruleString;
    290    tailoring->rules.getTerminatedBuffer();  // ensure NUL-termination
    291    tailoring->setVersion(base->version, rulesVersion);
    292    return tailoring.orphan();
    293 }
    294 
    295 void
    296 CollationBuilder::addReset(int32_t strength, const UnicodeString &str,
    297                           const char *&parserErrorReason, UErrorCode &errorCode) {
    298    if(U_FAILURE(errorCode)) { return; }
    299    U_ASSERT(!str.isEmpty());
    300    if(str.charAt(0) == CollationRuleParser::POS_LEAD) {
    301        ces[0] = getSpecialResetPosition(str, parserErrorReason, errorCode);
    302        cesLength = 1;
    303        if(U_FAILURE(errorCode)) { return; }
    304        U_ASSERT((ces[0] & Collation::CASE_AND_QUATERNARY_MASK) == 0);
    305    } else {
    306        // normal reset to a character or string
    307        UnicodeString nfdString = nfd.normalize(str, errorCode);
    308        if(U_FAILURE(errorCode)) {
    309            parserErrorReason = "normalizing the reset position";
    310            return;
    311        }
    312        cesLength = dataBuilder->getCEs(nfdString, ces, 0);
    313        if(cesLength > Collation::MAX_EXPANSION_LENGTH) {
    314            errorCode = U_ILLEGAL_ARGUMENT_ERROR;
    315            parserErrorReason = "reset position maps to too many collation elements (more than 31)";
    316            return;
    317        }
    318    }
    319    if(strength == UCOL_IDENTICAL) { return; }  // simple reset-at-position
    320 
    321    // &[before strength]position
    322    U_ASSERT(UCOL_PRIMARY <= strength && strength <= UCOL_TERTIARY);
    323    int32_t index = findOrInsertNodeForCEs(strength, parserErrorReason, errorCode);
    324    if(U_FAILURE(errorCode)) { return; }
    325 
    326    int64_t node = nodes.elementAti(index);
    327    // If the index is for a "weaker" node,
    328    // then skip backwards over this and further "weaker" nodes.
    329    while(strengthFromNode(node) > strength) {
    330        index = previousIndexFromNode(node);
    331        node = nodes.elementAti(index);
    332    }
    333 
    334    // Find or insert a node whose index we will put into a temporary CE.
    335    if(strengthFromNode(node) == strength && isTailoredNode(node)) {
    336        // Reset to just before this same-strength tailored node.
    337        index = previousIndexFromNode(node);
    338    } else if(strength == UCOL_PRIMARY) {
    339        // root primary node (has no previous index)
    340        uint32_t p = weight32FromNode(node);
    341        if(p == 0) {
    342            errorCode = U_UNSUPPORTED_ERROR;
    343            parserErrorReason = "reset primary-before ignorable not possible";
    344            return;
    345        }
    346        if(p <= rootElements.getFirstPrimary()) {
    347            // There is no primary gap between ignorables and the space-first-primary.
    348            errorCode = U_UNSUPPORTED_ERROR;
    349            parserErrorReason = "reset primary-before first non-ignorable not supported";
    350            return;
    351        }
    352        if(p == Collation::FIRST_TRAILING_PRIMARY) {
    353            // We do not support tailoring to an unassigned-implicit CE.
    354            errorCode = U_UNSUPPORTED_ERROR;
    355            parserErrorReason = "reset primary-before [first trailing] not supported";
    356            return;
    357        }
    358        p = rootElements.getPrimaryBefore(p, baseData->isCompressiblePrimary(p));
    359        index = findOrInsertNodeForPrimary(p, errorCode);
    360        // Go to the last node in this list:
    361        // Tailor after the last node between adjacent root nodes.
    362        for(;;) {
    363            node = nodes.elementAti(index);
    364            int32_t nextIndex = nextIndexFromNode(node);
    365            if(nextIndex == 0) { break; }
    366            index = nextIndex;
    367        }
    368    } else {
    369        // &[before 2] or &[before 3]
    370        index = findCommonNode(index, UCOL_SECONDARY);
    371        if(strength >= UCOL_TERTIARY) {
    372            index = findCommonNode(index, UCOL_TERTIARY);
    373        }
    374        // findCommonNode() stayed on the stronger node or moved to
    375        // an explicit common-weight node of the reset-before strength.
    376        node = nodes.elementAti(index);
    377        if(strengthFromNode(node) == strength) {
    378            // Found a same-strength node with an explicit weight.
    379            uint32_t weight16 = weight16FromNode(node);
    380            if(weight16 == 0) {
    381                errorCode = U_UNSUPPORTED_ERROR;
    382                if(strength == UCOL_SECONDARY) {
    383                    parserErrorReason = "reset secondary-before secondary ignorable not possible";
    384                } else {
    385                    parserErrorReason = "reset tertiary-before completely ignorable not possible";
    386                }
    387                return;
    388            }
    389            U_ASSERT(weight16 > Collation::BEFORE_WEIGHT16);
    390            // Reset to just before this node.
    391            // Insert the preceding same-level explicit weight if it is not there already.
    392            // Which explicit weight immediately precedes this one?
    393            weight16 = getWeight16Before(index, node, strength);
    394            // Does this preceding weight have a node?
    395            uint32_t previousWeight16;
    396            int32_t previousIndex = previousIndexFromNode(node);
    397            for(int32_t i = previousIndex;; i = previousIndexFromNode(node)) {
    398                node = nodes.elementAti(i);
    399                int32_t previousStrength = strengthFromNode(node);
    400                if(previousStrength < strength) {
    401                    U_ASSERT(weight16 >= Collation::COMMON_WEIGHT16 || i == previousIndex);
    402                    // Either the reset element has an above-common weight and
    403                    // the parent node provides the implied common weight,
    404                    // or the reset element has a weight<=common in the node
    405                    // right after the parent, and we need to insert the preceding weight.
    406                    previousWeight16 = Collation::COMMON_WEIGHT16;
    407                    break;
    408                } else if(previousStrength == strength && !isTailoredNode(node)) {
    409                    previousWeight16 = weight16FromNode(node);
    410                    break;
    411                }
    412                // Skip weaker nodes and same-level tailored nodes.
    413            }
    414            if(previousWeight16 == weight16) {
    415                // The preceding weight has a node,
    416                // maybe with following weaker or tailored nodes.
    417                // Reset to the last of them.
    418                index = previousIndex;
    419            } else {
    420                // Insert a node with the preceding weight, reset to that.
    421                node = nodeFromWeight16(weight16) | nodeFromStrength(strength);
    422                index = insertNodeBetween(previousIndex, index, node, errorCode);
    423            }
    424        } else {
    425            // Found a stronger node with implied strength-common weight.
    426            uint32_t weight16 = getWeight16Before(index, node, strength);
    427            index = findOrInsertWeakNode(index, weight16, strength, errorCode);
    428        }
    429        // Strength of the temporary CE = strength of its reset position.
    430        // Code above raises an error if the before-strength is stronger.
    431        strength = ceStrength(ces[cesLength - 1]);
    432    }
    433    if(U_FAILURE(errorCode)) {
    434        parserErrorReason = "inserting reset position for &[before n]";
    435        return;
    436    }
    437    ces[cesLength - 1] = tempCEFromIndexAndStrength(index, strength);
    438 }
    439 
    440 uint32_t
    441 CollationBuilder::getWeight16Before(int32_t index, int64_t node, int32_t level) {
    442    U_ASSERT(strengthFromNode(node) < level || !isTailoredNode(node));
    443    // Collect the root CE weights if this node is for a root CE.
    444    // If it is not, then return the low non-primary boundary for a tailored CE.
    445    uint32_t t;
    446    if(strengthFromNode(node) == UCOL_TERTIARY) {
    447        t = weight16FromNode(node);
    448    } else {
    449        t = Collation::COMMON_WEIGHT16;  // Stronger node with implied common weight.
    450    }
    451    while(strengthFromNode(node) > UCOL_SECONDARY) {
    452        index = previousIndexFromNode(node);
    453        node = nodes.elementAti(index);
    454    }
    455    if(isTailoredNode(node)) {
    456        return Collation::BEFORE_WEIGHT16;
    457    }
    458    uint32_t s;
    459    if(strengthFromNode(node) == UCOL_SECONDARY) {
    460        s = weight16FromNode(node);
    461    } else {
    462        s = Collation::COMMON_WEIGHT16;  // Stronger node with implied common weight.
    463    }
    464    while(strengthFromNode(node) > UCOL_PRIMARY) {
    465        index = previousIndexFromNode(node);
    466        node = nodes.elementAti(index);
    467    }
    468    if(isTailoredNode(node)) {
    469        return Collation::BEFORE_WEIGHT16;
    470    }
    471    // [p, s, t] is a root CE. Return the preceding weight for the requested level.
    472    uint32_t p = weight32FromNode(node);
    473    uint32_t weight16;
    474    if(level == UCOL_SECONDARY) {
    475        weight16 = rootElements.getSecondaryBefore(p, s);
    476    } else {
    477        weight16 = rootElements.getTertiaryBefore(p, s, t);
    478        U_ASSERT((weight16 & ~Collation::ONLY_TERTIARY_MASK) == 0);
    479    }
    480    return weight16;
    481 }
    482 
    483 int64_t
    484 CollationBuilder::getSpecialResetPosition(const UnicodeString &str,
    485                                          const char *&parserErrorReason, UErrorCode &errorCode) {
    486    U_ASSERT(str.length() == 2);
    487    int64_t ce;
    488    int32_t strength = UCOL_PRIMARY;
    489    UBool isBoundary = false;
    490    UChar32 pos = str.charAt(1) - CollationRuleParser::POS_BASE;
    491    U_ASSERT(0 <= pos && pos <= CollationRuleParser::LAST_TRAILING);
    492    switch(pos) {
    493    case CollationRuleParser::FIRST_TERTIARY_IGNORABLE:
    494        // Quaternary CEs are not supported.
    495        // Non-zero quaternary weights are possible only on tertiary or stronger CEs.
    496        return 0;
    497    case CollationRuleParser::LAST_TERTIARY_IGNORABLE:
    498        return 0;
    499    case CollationRuleParser::FIRST_SECONDARY_IGNORABLE: {
    500        // Look for a tailored tertiary node after [0, 0, 0].
    501        int32_t index = findOrInsertNodeForRootCE(0, UCOL_TERTIARY, errorCode);
    502        if(U_FAILURE(errorCode)) { return 0; }
    503        int64_t node = nodes.elementAti(index);
    504        if((index = nextIndexFromNode(node)) != 0) {
    505            node = nodes.elementAti(index);
    506            U_ASSERT(strengthFromNode(node) <= UCOL_TERTIARY);
    507            if(isTailoredNode(node) && strengthFromNode(node) == UCOL_TERTIARY) {
    508                return tempCEFromIndexAndStrength(index, UCOL_TERTIARY);
    509            }
    510        }
    511        return rootElements.getFirstTertiaryCE();
    512        // No need to look for nodeHasAnyBefore() on a tertiary node.
    513    }
    514    case CollationRuleParser::LAST_SECONDARY_IGNORABLE:
    515        ce = rootElements.getLastTertiaryCE();
    516        strength = UCOL_TERTIARY;
    517        break;
    518    case CollationRuleParser::FIRST_PRIMARY_IGNORABLE: {
    519        // Look for a tailored secondary node after [0, 0, *].
    520        int32_t index = findOrInsertNodeForRootCE(0, UCOL_SECONDARY, errorCode);
    521        if(U_FAILURE(errorCode)) { return 0; }
    522        int64_t node = nodes.elementAti(index);
    523        while((index = nextIndexFromNode(node)) != 0) {
    524            node = nodes.elementAti(index);
    525            strength = strengthFromNode(node);
    526            if(strength < UCOL_SECONDARY) { break; }
    527            if(strength == UCOL_SECONDARY) {
    528                if(isTailoredNode(node)) {
    529                    if(nodeHasBefore3(node)) {
    530                        index = nextIndexFromNode(nodes.elementAti(nextIndexFromNode(node)));
    531                        U_ASSERT(isTailoredNode(nodes.elementAti(index)));
    532                    }
    533                    return tempCEFromIndexAndStrength(index, UCOL_SECONDARY);
    534                } else {
    535                    break;
    536                }
    537            }
    538        }
    539        ce = rootElements.getFirstSecondaryCE();
    540        strength = UCOL_SECONDARY;
    541        break;
    542    }
    543    case CollationRuleParser::LAST_PRIMARY_IGNORABLE:
    544        ce = rootElements.getLastSecondaryCE();
    545        strength = UCOL_SECONDARY;
    546        break;
    547    case CollationRuleParser::FIRST_VARIABLE:
    548        ce = rootElements.getFirstPrimaryCE();
    549        isBoundary = true;  // FractionalUCA.txt: FDD1 00A0, SPACE first primary
    550        break;
    551    case CollationRuleParser::LAST_VARIABLE:
    552        ce = rootElements.lastCEWithPrimaryBefore(variableTop + 1);
    553        break;
    554    case CollationRuleParser::FIRST_REGULAR:
    555        ce = rootElements.firstCEWithPrimaryAtLeast(variableTop + 1);
    556        isBoundary = true;  // FractionalUCA.txt: FDD1 263A, SYMBOL first primary
    557        break;
    558    case CollationRuleParser::LAST_REGULAR:
    559        // Use the Hani-first-primary rather than the actual last "regular" CE before it,
    560        // for backward compatibility with behavior before the introduction of
    561        // script-first-primary CEs in the root collator.
    562        ce = rootElements.firstCEWithPrimaryAtLeast(
    563            baseData->getFirstPrimaryForGroup(USCRIPT_HAN));
    564        break;
    565    case CollationRuleParser::FIRST_IMPLICIT:
    566        ce = baseData->getSingleCE(0x4e00, errorCode);
    567        break;
    568    case CollationRuleParser::LAST_IMPLICIT:
    569        // We do not support tailoring to an unassigned-implicit CE.
    570        errorCode = U_UNSUPPORTED_ERROR;
    571        parserErrorReason = "reset to [last implicit] not supported";
    572        return 0;
    573    case CollationRuleParser::FIRST_TRAILING:
    574        ce = Collation::makeCE(Collation::FIRST_TRAILING_PRIMARY);
    575        isBoundary = true;  // trailing first primary (there is no mapping for it)
    576        break;
    577    case CollationRuleParser::LAST_TRAILING:
    578        errorCode = U_ILLEGAL_ARGUMENT_ERROR;
    579        parserErrorReason = "LDML forbids tailoring to U+FFFF";
    580        return 0;
    581    default:
    582        UPRV_UNREACHABLE_EXIT;
    583    }
    584 
    585    int32_t index = findOrInsertNodeForRootCE(ce, strength, errorCode);
    586    if(U_FAILURE(errorCode)) { return 0; }
    587    int64_t node = nodes.elementAti(index);
    588    if((pos & 1) == 0) {
    589        // even pos = [first xyz]
    590        if(!nodeHasAnyBefore(node) && isBoundary) {
    591            // A <group> first primary boundary is artificially added to FractionalUCA.txt.
    592            // It is reachable via its special contraction, but is not normally used.
    593            // Find the first character tailored after the boundary CE,
    594            // or the first real root CE after it.
    595            if((index = nextIndexFromNode(node)) != 0) {
    596                // If there is a following node, then it must be tailored
    597                // because there are no root CEs with a boundary primary
    598                // and non-common secondary/tertiary weights.
    599                node = nodes.elementAti(index);
    600                U_ASSERT(isTailoredNode(node));
    601                ce = tempCEFromIndexAndStrength(index, strength);
    602            } else {
    603                U_ASSERT(strength == UCOL_PRIMARY);
    604                uint32_t p = static_cast<uint32_t>(ce >> 32);
    605                int32_t pIndex = rootElements.findPrimary(p);
    606                UBool isCompressible = baseData->isCompressiblePrimary(p);
    607                p = rootElements.getPrimaryAfter(p, pIndex, isCompressible);
    608                ce = Collation::makeCE(p);
    609                index = findOrInsertNodeForRootCE(ce, UCOL_PRIMARY, errorCode);
    610                if(U_FAILURE(errorCode)) { return 0; }
    611                node = nodes.elementAti(index);
    612            }
    613        }
    614        if(nodeHasAnyBefore(node)) {
    615            // Get the first node that was tailored before this one at a weaker strength.
    616            if(nodeHasBefore2(node)) {
    617                index = nextIndexFromNode(nodes.elementAti(nextIndexFromNode(node)));
    618                node = nodes.elementAti(index);
    619            }
    620            if(nodeHasBefore3(node)) {
    621                index = nextIndexFromNode(nodes.elementAti(nextIndexFromNode(node)));
    622            }
    623            U_ASSERT(isTailoredNode(nodes.elementAti(index)));
    624            ce = tempCEFromIndexAndStrength(index, strength);
    625        }
    626    } else {
    627        // odd pos = [last xyz]
    628        // Find the last node that was tailored after the [last xyz]
    629        // at a strength no greater than the position's strength.
    630        for(;;) {
    631            int32_t nextIndex = nextIndexFromNode(node);
    632            if(nextIndex == 0) { break; }
    633            int64_t nextNode = nodes.elementAti(nextIndex);
    634            if(strengthFromNode(nextNode) < strength) { break; }
    635            index = nextIndex;
    636            node = nextNode;
    637        }
    638        // Do not make a temporary CE for a root node.
    639        // This last node might be the node for the root CE itself,
    640        // or a node with a common secondary or tertiary weight.
    641        if(isTailoredNode(node)) {
    642            ce = tempCEFromIndexAndStrength(index, strength);
    643        }
    644    }
    645    return ce;
    646 }
    647 
    648 void
    649 CollationBuilder::addRelation(int32_t strength, const UnicodeString &prefix,
    650                              const UnicodeString &str, const UnicodeString &extension,
    651                              const char *&parserErrorReason, UErrorCode &errorCode) {
    652    if(U_FAILURE(errorCode)) { return; }
    653    UnicodeString nfdPrefix;
    654    if(!prefix.isEmpty()) {
    655        nfd.normalize(prefix, nfdPrefix, errorCode);
    656        if(U_FAILURE(errorCode)) {
    657            parserErrorReason = "normalizing the relation prefix";
    658            return;
    659        }
    660    }
    661    UnicodeString nfdString = nfd.normalize(str, errorCode);
    662    if(U_FAILURE(errorCode)) {
    663        parserErrorReason = "normalizing the relation string";
    664        return;
    665    }
    666 
    667    // The runtime code decomposes Hangul syllables on the fly,
    668    // with recursive processing but without making the Jamo pieces visible for matching.
    669    // It does not work with certain types of contextual mappings.
    670    int32_t nfdLength = nfdString.length();
    671    if(nfdLength >= 2) {
    672        char16_t c = nfdString.charAt(0);
    673        if(Hangul::isJamoL(c) || Hangul::isJamoV(c)) {
    674            // While handling a Hangul syllable, contractions starting with Jamo L or V
    675            // would not see the following Jamo of that syllable.
    676            errorCode = U_UNSUPPORTED_ERROR;
    677            parserErrorReason = "contractions starting with conjoining Jamo L or V not supported";
    678            return;
    679        }
    680        c = nfdString.charAt(nfdLength - 1);
    681        if(Hangul::isJamoL(c) ||
    682                (Hangul::isJamoV(c) && Hangul::isJamoL(nfdString.charAt(nfdLength - 2)))) {
    683            // A contraction ending with Jamo L or L+V would require
    684            // generating Hangul syllables in addTailComposites() (588 for a Jamo L),
    685            // or decomposing a following Hangul syllable on the fly, during contraction matching.
    686            errorCode = U_UNSUPPORTED_ERROR;
    687            parserErrorReason = "contractions ending with conjoining Jamo L or L+V not supported";
    688            return;
    689        }
    690        // A Hangul syllable completely inside a contraction is ok.
    691    }
    692    // Note: If there is a prefix, then the parser checked that
    693    // both the prefix and the string begin with NFC boundaries (not Jamo V or T).
    694    // Therefore: prefix.isEmpty() || !isJamoVOrT(nfdString.charAt(0))
    695    // (While handling a Hangul syllable, prefixes on Jamo V or T
    696    // would not see the previous Jamo of that syllable.)
    697 
    698    if(strength != UCOL_IDENTICAL) {
    699        // Find the node index after which we insert the new tailored node.
    700        int32_t index = findOrInsertNodeForCEs(strength, parserErrorReason, errorCode);
    701        U_ASSERT(cesLength > 0);
    702        int64_t ce = ces[cesLength - 1];
    703        if (strength == UCOL_PRIMARY && !isTempCE(ce) && static_cast<uint32_t>(ce >> 32) == 0) {
    704            // There is no primary gap between ignorables and the space-first-primary.
    705            errorCode = U_UNSUPPORTED_ERROR;
    706            parserErrorReason = "tailoring primary after ignorables not supported";
    707            return;
    708        }
    709        if(strength == UCOL_QUATERNARY && ce == 0) {
    710            // The CE data structure does not support non-zero quaternary weights
    711            // on tertiary ignorables.
    712            errorCode = U_UNSUPPORTED_ERROR;
    713            parserErrorReason = "tailoring quaternary after tertiary ignorables not supported";
    714            return;
    715        }
    716        // Insert the new tailored node.
    717        index = insertTailoredNodeAfter(index, strength, errorCode);
    718        if(U_FAILURE(errorCode)) {
    719            parserErrorReason = "modifying collation elements";
    720            return;
    721        }
    722        // Strength of the temporary CE:
    723        // The new relation may yield a stronger CE but not a weaker one.
    724        int32_t tempStrength = ceStrength(ce);
    725        if(strength < tempStrength) { tempStrength = strength; }
    726        ces[cesLength - 1] = tempCEFromIndexAndStrength(index, tempStrength);
    727    }
    728 
    729    setCaseBits(nfdString, parserErrorReason, errorCode);
    730    if(U_FAILURE(errorCode)) { return; }
    731 
    732    int32_t cesLengthBeforeExtension = cesLength;
    733    if(!extension.isEmpty()) {
    734        UnicodeString nfdExtension = nfd.normalize(extension, errorCode);
    735        if(U_FAILURE(errorCode)) {
    736            parserErrorReason = "normalizing the relation extension";
    737            return;
    738        }
    739        cesLength = dataBuilder->getCEs(nfdExtension, ces, cesLength);
    740        if(cesLength > Collation::MAX_EXPANSION_LENGTH) {
    741            errorCode = U_ILLEGAL_ARGUMENT_ERROR;
    742            parserErrorReason =
    743                "extension string adds too many collation elements (more than 31 total)";
    744            return;
    745        }
    746    }
    747    uint32_t ce32 = Collation::UNASSIGNED_CE32;
    748    if(!icu4xMode && (prefix != nfdPrefix || str != nfdString) &&
    749            !ignorePrefix(prefix, errorCode) && !ignoreString(str, errorCode)) {
    750        // Map from the original input to the CEs.
    751        // We do this in case the canonical closure is incomplete,
    752        // so that it is possible to explicitly provide the missing mappings.
    753        ce32 = addIfDifferent(prefix, str, ces, cesLength, ce32, errorCode);
    754    }
    755    if (!icu4xMode) {
    756        addWithClosure(nfdPrefix, nfdString, ces, cesLength, ce32, errorCode);
    757    } else {
    758        addIfDifferent(nfdPrefix, nfdString, ces, cesLength, ce32, errorCode);
    759    }
    760    if(U_FAILURE(errorCode)) {
    761        parserErrorReason = "writing collation elements";
    762        return;
    763    }
    764    cesLength = cesLengthBeforeExtension;
    765 }
    766 
    767 int32_t
    768 CollationBuilder::findOrInsertNodeForCEs(int32_t strength, const char *&parserErrorReason,
    769                                         UErrorCode &errorCode) {
    770    if(U_FAILURE(errorCode)) { return 0; }
    771    U_ASSERT(UCOL_PRIMARY <= strength && strength <= UCOL_QUATERNARY);
    772 
    773    // Find the last CE that is at least as "strong" as the requested difference.
    774    // Note: Stronger is smaller (UCOL_PRIMARY=0).
    775    int64_t ce;
    776    for(;; --cesLength) {
    777        if(cesLength == 0) {
    778            ce = ces[0] = 0;
    779            cesLength = 1;
    780            break;
    781        } else {
    782            ce = ces[cesLength - 1];
    783        }
    784        if(ceStrength(ce) <= strength) { break; }
    785    }
    786 
    787    if(isTempCE(ce)) {
    788        // No need to findCommonNode() here for lower levels
    789        // because insertTailoredNodeAfter() will do that anyway.
    790        return indexFromTempCE(ce);
    791    }
    792 
    793    // root CE
    794    if (static_cast<uint8_t>(ce >> 56) == Collation::UNASSIGNED_IMPLICIT_BYTE) {
    795        errorCode = U_UNSUPPORTED_ERROR;
    796        parserErrorReason = "tailoring relative to an unassigned code point not supported";
    797        return 0;
    798    }
    799    return findOrInsertNodeForRootCE(ce, strength, errorCode);
    800 }
    801 
    802 int32_t
    803 CollationBuilder::findOrInsertNodeForRootCE(int64_t ce, int32_t strength, UErrorCode &errorCode) {
    804    if(U_FAILURE(errorCode)) { return 0; }
    805    U_ASSERT((uint8_t)(ce >> 56) != Collation::UNASSIGNED_IMPLICIT_BYTE);
    806 
    807    // Find or insert the node for each of the root CE's weights,
    808    // down to the requested level/strength.
    809    // Root CEs must have common=zero quaternary weights (for which we never insert any nodes).
    810    U_ASSERT((ce & 0xc0) == 0);
    811    int32_t index = findOrInsertNodeForPrimary(static_cast<uint32_t>(ce >> 32), errorCode);
    812    if(strength >= UCOL_SECONDARY) {
    813        uint32_t lower32 = static_cast<uint32_t>(ce);
    814        index = findOrInsertWeakNode(index, lower32 >> 16, UCOL_SECONDARY, errorCode);
    815        if(strength >= UCOL_TERTIARY) {
    816            index = findOrInsertWeakNode(index, lower32 & Collation::ONLY_TERTIARY_MASK,
    817                                         UCOL_TERTIARY, errorCode);
    818        }
    819    }
    820    return index;
    821 }
    822 
    823 namespace {
    824 
    825 /**
    826 * Like Java Collections.binarySearch(List, key, Comparator).
    827 *
    828 * @return the index>=0 where the item was found,
    829 *         or the index<0 for inserting the string at ~index in sorted order
    830 *         (index into rootPrimaryIndexes)
    831 */
    832 int32_t
    833 binarySearchForRootPrimaryNode(const int32_t *rootPrimaryIndexes, int32_t length,
    834                               const int64_t *nodes, uint32_t p) {
    835    if(length == 0) { return ~0; }
    836    int32_t start = 0;
    837    int32_t limit = length;
    838    for (;;) {
    839        int32_t i = (start + limit) / 2;
    840        int64_t node = nodes[rootPrimaryIndexes[i]];
    841        uint32_t nodePrimary = static_cast<uint32_t>(node >> 32); // weight32FromNode(node)
    842        if (p == nodePrimary) {
    843            return i;
    844        } else if (p < nodePrimary) {
    845            if (i == start) {
    846                return ~start;  // insert s before i
    847            }
    848            limit = i;
    849        } else {
    850            if (i == start) {
    851                return ~(start + 1);  // insert s after i
    852            }
    853            start = i;
    854        }
    855    }
    856 }
    857 
    858 }  // namespace
    859 
    860 int32_t
    861 CollationBuilder::findOrInsertNodeForPrimary(uint32_t p, UErrorCode &errorCode) {
    862    if(U_FAILURE(errorCode)) { return 0; }
    863 
    864    int32_t rootIndex = binarySearchForRootPrimaryNode(
    865        rootPrimaryIndexes.getBuffer(), rootPrimaryIndexes.size(), nodes.getBuffer(), p);
    866    if(rootIndex >= 0) {
    867        return rootPrimaryIndexes.elementAti(rootIndex);
    868    } else {
    869        // Start a new list of nodes with this primary.
    870        int32_t index = nodes.size();
    871        nodes.addElement(nodeFromWeight32(p), errorCode);
    872        rootPrimaryIndexes.insertElementAt(index, ~rootIndex, errorCode);
    873        return index;
    874    }
    875 }
    876 
    877 int32_t
    878 CollationBuilder::findOrInsertWeakNode(int32_t index, uint32_t weight16, int32_t level, UErrorCode &errorCode) {
    879    if(U_FAILURE(errorCode)) { return 0; }
    880    U_ASSERT(0 <= index && index < nodes.size());
    881    U_ASSERT(UCOL_SECONDARY <= level && level <= UCOL_TERTIARY);
    882 
    883    if(weight16 == Collation::COMMON_WEIGHT16) {
    884        return findCommonNode(index, level);
    885    }
    886 
    887    // If this will be the first below-common weight for the parent node,
    888    // then we will also need to insert a common weight after it.
    889    int64_t node = nodes.elementAti(index);
    890    U_ASSERT(strengthFromNode(node) < level);  // parent node is stronger
    891    if(weight16 != 0 && weight16 < Collation::COMMON_WEIGHT16) {
    892        int32_t hasThisLevelBefore = level == UCOL_SECONDARY ? HAS_BEFORE2 : HAS_BEFORE3;
    893        if((node & hasThisLevelBefore) == 0) {
    894            // The parent node has an implied level-common weight.
    895            int64_t commonNode =
    896                nodeFromWeight16(Collation::COMMON_WEIGHT16) | nodeFromStrength(level);
    897            if(level == UCOL_SECONDARY) {
    898                // Move the HAS_BEFORE3 flag from the parent node
    899                // to the new secondary common node.
    900                commonNode |= node & HAS_BEFORE3;
    901                node &= ~static_cast<int64_t>(HAS_BEFORE3);
    902            }
    903            nodes.setElementAt(node | hasThisLevelBefore, index);
    904            // Insert below-common-weight node.
    905            int32_t nextIndex = nextIndexFromNode(node);
    906            node = nodeFromWeight16(weight16) | nodeFromStrength(level);
    907            index = insertNodeBetween(index, nextIndex, node, errorCode);
    908            // Insert common-weight node.
    909            insertNodeBetween(index, nextIndex, commonNode, errorCode);
    910            // Return index of below-common-weight node.
    911            return index;
    912        }
    913    }
    914 
    915    // Find the root CE's weight for this level.
    916    // Postpone insertion if not found:
    917    // Insert the new root node before the next stronger node,
    918    // or before the next root node with the same strength and a larger weight.
    919    int32_t nextIndex;
    920    while((nextIndex = nextIndexFromNode(node)) != 0) {
    921        node = nodes.elementAti(nextIndex);
    922        int32_t nextStrength = strengthFromNode(node);
    923        if(nextStrength <= level) {
    924            // Insert before a stronger node.
    925            if(nextStrength < level) { break; }
    926            // nextStrength == level
    927            if(!isTailoredNode(node)) {
    928                uint32_t nextWeight16 = weight16FromNode(node);
    929                if(nextWeight16 == weight16) {
    930                    // Found the node for the root CE up to this level.
    931                    return nextIndex;
    932                }
    933                // Insert before a node with a larger same-strength weight.
    934                if(nextWeight16 > weight16) { break; }
    935            }
    936        }
    937        // Skip the next node.
    938        index = nextIndex;
    939    }
    940    node = nodeFromWeight16(weight16) | nodeFromStrength(level);
    941    return insertNodeBetween(index, nextIndex, node, errorCode);
    942 }
    943 
    944 int32_t
    945 CollationBuilder::insertTailoredNodeAfter(int32_t index, int32_t strength, UErrorCode &errorCode) {
    946    if(U_FAILURE(errorCode)) { return 0; }
    947    U_ASSERT(0 <= index && index < nodes.size());
    948    if(strength >= UCOL_SECONDARY) {
    949        index = findCommonNode(index, UCOL_SECONDARY);
    950        if(strength >= UCOL_TERTIARY) {
    951            index = findCommonNode(index, UCOL_TERTIARY);
    952        }
    953    }
    954    // Postpone insertion:
    955    // Insert the new node before the next one with a strength at least as strong.
    956    int64_t node = nodes.elementAti(index);
    957    int32_t nextIndex;
    958    while((nextIndex = nextIndexFromNode(node)) != 0) {
    959        node = nodes.elementAti(nextIndex);
    960        if(strengthFromNode(node) <= strength) { break; }
    961        // Skip the next node which has a weaker (larger) strength than the new one.
    962        index = nextIndex;
    963    }
    964    node = IS_TAILORED | nodeFromStrength(strength);
    965    return insertNodeBetween(index, nextIndex, node, errorCode);
    966 }
    967 
    968 int32_t
    969 CollationBuilder::insertNodeBetween(int32_t index, int32_t nextIndex, int64_t node,
    970                                    UErrorCode &errorCode) {
    971    if(U_FAILURE(errorCode)) { return 0; }
    972    U_ASSERT(previousIndexFromNode(node) == 0);
    973    U_ASSERT(nextIndexFromNode(node) == 0);
    974    U_ASSERT(nextIndexFromNode(nodes.elementAti(index)) == nextIndex);
    975    // Append the new node and link it to the existing nodes.
    976    int32_t newIndex = nodes.size();
    977    node |= nodeFromPreviousIndex(index) | nodeFromNextIndex(nextIndex);
    978    nodes.addElement(node, errorCode);
    979    if(U_FAILURE(errorCode)) { return 0; }
    980    // nodes[index].nextIndex = newIndex
    981    node = nodes.elementAti(index);
    982    nodes.setElementAt(changeNodeNextIndex(node, newIndex), index);
    983    // nodes[nextIndex].previousIndex = newIndex
    984    if(nextIndex != 0) {
    985        node = nodes.elementAti(nextIndex);
    986        nodes.setElementAt(changeNodePreviousIndex(node, newIndex), nextIndex);
    987    }
    988    return newIndex;
    989 }
    990 
    991 int32_t
    992 CollationBuilder::findCommonNode(int32_t index, int32_t strength) const {
    993    U_ASSERT(UCOL_SECONDARY <= strength && strength <= UCOL_TERTIARY);
    994    int64_t node = nodes.elementAti(index);
    995    if(strengthFromNode(node) >= strength) {
    996        // The current node is no stronger.
    997        return index;
    998    }
    999    if(strength == UCOL_SECONDARY ? !nodeHasBefore2(node) : !nodeHasBefore3(node)) {
   1000        // The current node implies the strength-common weight.
   1001        return index;
   1002    }
   1003    index = nextIndexFromNode(node);
   1004    node = nodes.elementAti(index);
   1005    U_ASSERT(!isTailoredNode(node) && strengthFromNode(node) == strength &&
   1006            weight16FromNode(node) < Collation::COMMON_WEIGHT16);
   1007    // Skip to the explicit common node.
   1008    do {
   1009        index = nextIndexFromNode(node);
   1010        node = nodes.elementAti(index);
   1011        U_ASSERT(strengthFromNode(node) >= strength);
   1012    } while(isTailoredNode(node) || strengthFromNode(node) > strength ||
   1013            weight16FromNode(node) < Collation::COMMON_WEIGHT16);
   1014    U_ASSERT(weight16FromNode(node) == Collation::COMMON_WEIGHT16);
   1015    return index;
   1016 }
   1017 
   1018 void
   1019 CollationBuilder::setCaseBits(const UnicodeString &nfdString,
   1020                              const char *&parserErrorReason, UErrorCode &errorCode) {
   1021    if(U_FAILURE(errorCode)) { return; }
   1022    int32_t numTailoredPrimaries = 0;
   1023    for(int32_t i = 0; i < cesLength; ++i) {
   1024        if(ceStrength(ces[i]) == UCOL_PRIMARY) { ++numTailoredPrimaries; }
   1025    }
   1026    // We should not be able to get too many case bits because
   1027    // cesLength<=31==MAX_EXPANSION_LENGTH.
   1028    // 31 pairs of case bits fit into an int64_t without setting its sign bit.
   1029    U_ASSERT(numTailoredPrimaries <= 31);
   1030 
   1031    int64_t cases = 0;
   1032    if(numTailoredPrimaries > 0) {
   1033        const char16_t *s = nfdString.getBuffer();
   1034        UTF16CollationIterator baseCEs(baseData, false, s, s, s + nfdString.length());
   1035        int32_t baseCEsLength = baseCEs.fetchCEs(errorCode) - 1;
   1036        if(U_FAILURE(errorCode)) {
   1037            parserErrorReason = "fetching root CEs for tailored string";
   1038            return;
   1039        }
   1040        U_ASSERT(baseCEsLength >= 0 && baseCEs.getCE(baseCEsLength) == Collation::NO_CE);
   1041 
   1042        uint32_t lastCase = 0;
   1043        int32_t numBasePrimaries = 0;
   1044        for(int32_t i = 0; i < baseCEsLength; ++i) {
   1045            int64_t ce = baseCEs.getCE(i);
   1046            if((ce >> 32) != 0) {
   1047                ++numBasePrimaries;
   1048                uint32_t c = (static_cast<uint32_t>(ce) >> 14) & 3;
   1049                U_ASSERT(c == 0 || c == 2);  // lowercase or uppercase, no mixed case in any base CE
   1050                if(numBasePrimaries < numTailoredPrimaries) {
   1051                    cases |= static_cast<int64_t>(c) << ((numBasePrimaries - 1) * 2);
   1052                } else if(numBasePrimaries == numTailoredPrimaries) {
   1053                    lastCase = c;
   1054                } else if(c != lastCase) {
   1055                    // There are more base primary CEs than tailored primaries.
   1056                    // Set mixed case if the case bits of the remainder differ.
   1057                    lastCase = 1;
   1058                    // Nothing more can change.
   1059                    break;
   1060                }
   1061            }
   1062        }
   1063        if(numBasePrimaries >= numTailoredPrimaries) {
   1064            cases |= static_cast<int64_t>(lastCase) << ((numTailoredPrimaries - 1) * 2);
   1065        }
   1066    }
   1067 
   1068    for(int32_t i = 0; i < cesLength; ++i) {
   1069        int64_t ce = ces[i] & INT64_C(0xffffffffffff3fff);  // clear old case bits
   1070        int32_t strength = ceStrength(ce);
   1071        if(strength == UCOL_PRIMARY) {
   1072            ce |= (cases & 3) << 14;
   1073            cases >>= 2;
   1074        } else if(strength == UCOL_TERTIARY) {
   1075            // Tertiary CEs must have uppercase bits.
   1076            // See the LDML spec, and comments in class CollationCompare.
   1077            ce |= 0x8000;
   1078        }
   1079        // Tertiary ignorable CEs must have 0 case bits.
   1080        // We set 0 case bits for secondary CEs too
   1081        // since currently only U+0345 is cased and maps to a secondary CE,
   1082        // and it is lowercase. Other secondaries are uncased.
   1083        // See [[:Cased:]&[:uca1=:]] where uca1 queries the root primary weight.
   1084        ces[i] = ce;
   1085    }
   1086 }
   1087 
   1088 void
   1089 CollationBuilder::suppressContractions(const UnicodeSet &set, const char *&parserErrorReason,
   1090                                       UErrorCode &errorCode) {
   1091    if(U_FAILURE(errorCode)) { return; }
   1092    dataBuilder->suppressContractions(set, errorCode);
   1093    if(U_FAILURE(errorCode)) {
   1094        parserErrorReason = "application of [suppressContractions [set]] failed";
   1095    }
   1096 }
   1097 
   1098 void
   1099 CollationBuilder::optimize(const UnicodeSet &set, const char *& /* parserErrorReason */,
   1100                           UErrorCode &errorCode) {
   1101    if(U_FAILURE(errorCode)) { return; }
   1102    optimizeSet.addAll(set);
   1103 }
   1104 
   1105 uint32_t
   1106 CollationBuilder::addWithClosure(const UnicodeString &nfdPrefix, const UnicodeString &nfdString,
   1107                                 const int64_t newCEs[], int32_t newCEsLength, uint32_t ce32,
   1108                                 UErrorCode &errorCode) {
   1109    // Map from the NFD input to the CEs.
   1110    ce32 = addIfDifferent(nfdPrefix, nfdString, newCEs, newCEsLength, ce32, errorCode);
   1111    ce32 = addOnlyClosure(nfdPrefix, nfdString, newCEs, newCEsLength, ce32, errorCode);
   1112    addTailComposites(nfdPrefix, nfdString, errorCode);
   1113    return ce32;
   1114 }
   1115 
   1116 // ICU-22517
   1117 // This constant defines a limit for the addOnlyClosure to return
   1118 // error, to avoid taking a long time for canonical closure expansion.
   1119 // Please let us know if you have a reasonable use case that needed
   1120 // for a practical Collation rule that needs to increase this limit.
   1121 // This value is needed for compiling a rule with eight Hangul syllables such as
   1122 // "&a=b쫊쫊쫊쫊쫊쫊쫊" without error, which should be more than realistic
   1123 // usage.
   1124 static constexpr int32_t kClosureLoopLimit = 3000;
   1125 
   1126 uint32_t
   1127 CollationBuilder::addOnlyClosure(const UnicodeString &nfdPrefix, const UnicodeString &nfdString,
   1128                                 const int64_t newCEs[], int32_t newCEsLength, uint32_t ce32,
   1129                                 UErrorCode &errorCode) {
   1130    if(U_FAILURE(errorCode)) { return ce32; }
   1131 
   1132    int32_t loop = 0;
   1133    // Map from canonically equivalent input to the CEs. (But not from the all-NFD input.)
   1134    if(nfdPrefix.isEmpty()) {
   1135        CanonicalIterator stringIter(nfdString, errorCode);
   1136        if(U_FAILURE(errorCode)) { return ce32; }
   1137        UnicodeString prefix;
   1138        for(;;) {
   1139            UnicodeString str = stringIter.next();
   1140            if(str.isBogus()) { break; }
   1141            if (loop++ > kClosureLoopLimit) {
   1142                // To avoid hang as in ICU-22517, return with error.
   1143                errorCode = U_INPUT_TOO_LONG_ERROR;
   1144                return ce32;
   1145            }
   1146            if(ignoreString(str, errorCode) || str == nfdString) { continue; }
   1147            ce32 = addIfDifferent(prefix, str, newCEs, newCEsLength, ce32, errorCode);
   1148            if(U_FAILURE(errorCode)) { return ce32; }
   1149        }
   1150    } else {
   1151        CanonicalIterator prefixIter(nfdPrefix, errorCode);
   1152        CanonicalIterator stringIter(nfdString, errorCode);
   1153        if(U_FAILURE(errorCode)) { return ce32; }
   1154        for(;;) {
   1155            UnicodeString prefix = prefixIter.next();
   1156            if(prefix.isBogus()) { break; }
   1157            if(ignorePrefix(prefix, errorCode)) { continue; }
   1158            UBool samePrefix = prefix == nfdPrefix;
   1159            for(;;) {
   1160                UnicodeString str = stringIter.next();
   1161                if(str.isBogus()) { break; }
   1162                if (loop++ > kClosureLoopLimit) {
   1163                    // To avoid hang as in ICU-22517, return with error.
   1164                    errorCode = U_INPUT_TOO_LONG_ERROR;
   1165                    return ce32;
   1166                }
   1167                if(ignoreString(str, errorCode) || (samePrefix && str == nfdString)) { continue; }
   1168                ce32 = addIfDifferent(prefix, str, newCEs, newCEsLength, ce32, errorCode);
   1169                if(U_FAILURE(errorCode)) { return ce32; }
   1170            }
   1171            stringIter.reset();
   1172        }
   1173    }
   1174    return ce32;
   1175 }
   1176 
   1177 void
   1178 CollationBuilder::addTailComposites(const UnicodeString &nfdPrefix, const UnicodeString &nfdString,
   1179                                    UErrorCode &errorCode) {
   1180    if(U_FAILURE(errorCode)) { return; }
   1181 
   1182    // Look for the last starter in the NFD string.
   1183    UChar32 lastStarter;
   1184    int32_t indexAfterLastStarter = nfdString.length();
   1185    for(;;) {
   1186        if(indexAfterLastStarter == 0) { return; }  // no starter at all
   1187        lastStarter = nfdString.char32At(indexAfterLastStarter - 1);
   1188        if(nfd.getCombiningClass(lastStarter) == 0) { break; }
   1189        indexAfterLastStarter -= U16_LENGTH(lastStarter);
   1190    }
   1191    // No closure to Hangul syllables since we decompose them on the fly.
   1192    if(Hangul::isJamoL(lastStarter)) { return; }
   1193 
   1194    // Are there any composites whose decomposition starts with the lastStarter?
   1195    // Note: Normalizer2Impl does not currently return start sets for NFC_QC=Maybe characters.
   1196    // We might find some more equivalent mappings here if it did.
   1197    UnicodeSet composites;
   1198    if(!nfcImpl.getCanonStartSet(lastStarter, composites)) { return; }
   1199 
   1200    UnicodeString decomp;
   1201    UnicodeString newNFDString, newString;
   1202    int64_t newCEs[Collation::MAX_EXPANSION_LENGTH];
   1203    UnicodeSetIterator iter(composites);
   1204    while(iter.next()) {
   1205        U_ASSERT(!iter.isString());
   1206        UChar32 composite = iter.getCodepoint();
   1207        nfd.getDecomposition(composite, decomp);
   1208        if(!mergeCompositeIntoString(nfdString, indexAfterLastStarter, composite, decomp,
   1209                                     newNFDString, newString, errorCode)) {
   1210            continue;
   1211        }
   1212        int32_t newCEsLength = dataBuilder->getCEs(nfdPrefix, newNFDString, newCEs, 0);
   1213        if(newCEsLength > Collation::MAX_EXPANSION_LENGTH) {
   1214            // Ignore mappings that we cannot store.
   1215            continue;
   1216        }
   1217        // Note: It is possible that the newCEs do not make use of the mapping
   1218        // for which we are adding the tail composites, in which case we might be adding
   1219        // unnecessary mappings.
   1220        // For example, when we add tail composites for ae^ (^=combining circumflex),
   1221        // UCA discontiguous-contraction matching does not find any matches
   1222        // for ae_^ (_=any combining diacritic below) *unless* there is also
   1223        // a contraction mapping for ae.
   1224        // Thus, if there is no ae contraction, then the ae^ mapping is ignored
   1225        // while fetching the newCEs for ae_^.
   1226        // TODO: Try to detect this effectively.
   1227        // (Alternatively, print a warning when prefix contractions are missing.)
   1228 
   1229        // We do not need an explicit mapping for the NFD strings.
   1230        // It is fine if the NFD input collates like this via a sequence of mappings.
   1231        // It also saves a little bit of space, and may reduce the set of characters with contractions.
   1232        uint32_t ce32 = addIfDifferent(nfdPrefix, newString,
   1233                                       newCEs, newCEsLength, Collation::UNASSIGNED_CE32, errorCode);
   1234        if(ce32 != Collation::UNASSIGNED_CE32) {
   1235            // was different, was added
   1236            addOnlyClosure(nfdPrefix, newNFDString, newCEs, newCEsLength, ce32, errorCode);
   1237        }
   1238    }
   1239 }
   1240 
   1241 UBool
   1242 CollationBuilder::mergeCompositeIntoString(const UnicodeString &nfdString,
   1243                                           int32_t indexAfterLastStarter,
   1244                                           UChar32 composite, const UnicodeString &decomp,
   1245                                           UnicodeString &newNFDString, UnicodeString &newString,
   1246                                           UErrorCode &errorCode) const {
   1247    if(U_FAILURE(errorCode)) { return false; }
   1248    U_ASSERT(nfdString.char32At(indexAfterLastStarter - 1) == decomp.char32At(0));
   1249    int32_t lastStarterLength = decomp.moveIndex32(0, 1);
   1250    if(lastStarterLength == decomp.length()) {
   1251        // Singleton decompositions should be found by addWithClosure()
   1252        // and the CanonicalIterator, so we can ignore them here.
   1253        return false;
   1254    }
   1255    if(nfdString.compare(indexAfterLastStarter, 0x7fffffff,
   1256                         decomp, lastStarterLength, 0x7fffffff) == 0) {
   1257        // same strings, nothing new to be found here
   1258        return false;
   1259    }
   1260 
   1261    // Make new FCD strings that combine a composite, or its decomposition,
   1262    // into the nfdString's last starter and the combining marks following it.
   1263    // Make an NFD version, and a version with the composite.
   1264    newNFDString.setTo(nfdString, 0, indexAfterLastStarter);
   1265    newString.setTo(nfdString, 0, indexAfterLastStarter - lastStarterLength).append(composite);
   1266 
   1267    // The following is related to discontiguous contraction matching,
   1268    // but builds only FCD strings (or else returns false).
   1269    int32_t sourceIndex = indexAfterLastStarter;
   1270    int32_t decompIndex = lastStarterLength;
   1271    // Small optimization: We keep the source character across loop iterations
   1272    // because we do not always consume it,
   1273    // and then need not fetch it again nor look up its combining class again.
   1274    UChar32 sourceChar = U_SENTINEL;
   1275    // The cc variables need to be declared before the loop so that at the end
   1276    // they are set to the last combining classes seen.
   1277    uint8_t sourceCC = 0;
   1278    uint8_t decompCC = 0;
   1279    for(;;) {
   1280        if(sourceChar < 0) {
   1281            if(sourceIndex >= nfdString.length()) { break; }
   1282            sourceChar = nfdString.char32At(sourceIndex);
   1283            sourceCC = nfd.getCombiningClass(sourceChar);
   1284            U_ASSERT(sourceCC != 0);
   1285        }
   1286        // We consume a decomposition character in each iteration.
   1287        if(decompIndex >= decomp.length()) { break; }
   1288        UChar32 decompChar = decomp.char32At(decompIndex);
   1289        decompCC = nfd.getCombiningClass(decompChar);
   1290        // Compare the two characters and their combining classes.
   1291        if(decompCC == 0) {
   1292            // Unable to merge because the source contains a non-zero combining mark
   1293            // but the composite's decomposition contains another starter.
   1294            // The strings would not be equivalent.
   1295            return false;
   1296        } else if(sourceCC < decompCC) {
   1297            // Composite + sourceChar would not be FCD.
   1298            return false;
   1299        } else if(decompCC < sourceCC) {
   1300            newNFDString.append(decompChar);
   1301            decompIndex += U16_LENGTH(decompChar);
   1302        } else if(decompChar != sourceChar) {
   1303            // Blocked because same combining class.
   1304            return false;
   1305        } else {  // match: decompChar == sourceChar
   1306            newNFDString.append(decompChar);
   1307            decompIndex += U16_LENGTH(decompChar);
   1308            sourceIndex += U16_LENGTH(decompChar);
   1309            sourceChar = U_SENTINEL;
   1310        }
   1311    }
   1312    // We are at the end of at least one of the two inputs.
   1313    if(sourceChar >= 0) {  // more characters from nfdString but not from decomp
   1314        if(sourceCC < decompCC) {
   1315            // Appending the next source character to the composite would not be FCD.
   1316            return false;
   1317        }
   1318        newNFDString.append(nfdString, sourceIndex, 0x7fffffff);
   1319        newString.append(nfdString, sourceIndex, 0x7fffffff);
   1320    } else if(decompIndex < decomp.length()) {  // more characters from decomp, not from nfdString
   1321        newNFDString.append(decomp, decompIndex, 0x7fffffff);
   1322    }
   1323    U_ASSERT(nfd.isNormalized(newNFDString, errorCode));
   1324    U_ASSERT(fcd.isNormalized(newString, errorCode));
   1325    U_ASSERT(nfd.normalize(newString, errorCode) == newNFDString);  // canonically equivalent
   1326    return true;
   1327 }
   1328 
   1329 UBool
   1330 CollationBuilder::ignorePrefix(const UnicodeString &s, UErrorCode &errorCode) const {
   1331    // Do not map non-FCD prefixes.
   1332    return !isFCD(s, errorCode);
   1333 }
   1334 
   1335 UBool
   1336 CollationBuilder::ignoreString(const UnicodeString &s, UErrorCode &errorCode) const {
   1337    // Do not map non-FCD strings.
   1338    // Do not map strings that start with Hangul syllables: We decompose those on the fly.
   1339    return !isFCD(s, errorCode) || Hangul::isHangul(s.charAt(0));
   1340 }
   1341 
   1342 UBool
   1343 CollationBuilder::isFCD(const UnicodeString &s, UErrorCode &errorCode) const {
   1344    return U_SUCCESS(errorCode) && fcd.isNormalized(s, errorCode);
   1345 }
   1346 
   1347 void
   1348 CollationBuilder::closeOverComposites(UErrorCode &errorCode) {
   1349    UnicodeSet composites(UNICODE_STRING_SIMPLE("[:NFD_QC=N:]"), errorCode);  // Java: static final
   1350    if(U_FAILURE(errorCode)) { return; }
   1351    // Hangul is decomposed on the fly during collation.
   1352    composites.remove(Hangul::HANGUL_BASE, Hangul::HANGUL_END);
   1353    UnicodeString prefix;  // empty
   1354    UnicodeString nfdString;
   1355    UnicodeSetIterator iter(composites);
   1356    while(iter.next()) {
   1357        U_ASSERT(!iter.isString());
   1358        nfd.getDecomposition(iter.getCodepoint(), nfdString);
   1359        cesLength = dataBuilder->getCEs(nfdString, ces, 0);
   1360        if(cesLength > Collation::MAX_EXPANSION_LENGTH) {
   1361            // Too many CEs from the decomposition (unusual), ignore this composite.
   1362            // We could add a capacity parameter to getCEs() and reallocate if necessary.
   1363            // However, this can only really happen in contrived cases.
   1364            continue;
   1365        }
   1366        const UnicodeString &composite(iter.getString());
   1367        addIfDifferent(prefix, composite, ces, cesLength, Collation::UNASSIGNED_CE32, errorCode);
   1368    }
   1369 }
   1370 
   1371 uint32_t
   1372 CollationBuilder::addIfDifferent(const UnicodeString &prefix, const UnicodeString &str,
   1373                                 const int64_t newCEs[], int32_t newCEsLength, uint32_t ce32,
   1374                                 UErrorCode &errorCode) {
   1375    if(U_FAILURE(errorCode)) { return ce32; }
   1376    int64_t oldCEs[Collation::MAX_EXPANSION_LENGTH];
   1377    int32_t oldCEsLength = dataBuilder->getCEs(prefix, str, oldCEs, 0);
   1378    if(!sameCEs(newCEs, newCEsLength, oldCEs, oldCEsLength)) {
   1379        if(ce32 == Collation::UNASSIGNED_CE32) {
   1380            ce32 = dataBuilder->encodeCEs(newCEs, newCEsLength, errorCode);
   1381        }
   1382        dataBuilder->addCE32(prefix, str, ce32, errorCode);
   1383    }
   1384    return ce32;
   1385 }
   1386 
   1387 UBool
   1388 CollationBuilder::sameCEs(const int64_t ces1[], int32_t ces1Length,
   1389                          const int64_t ces2[], int32_t ces2Length) {
   1390    if(ces1Length != ces2Length) {
   1391        return false;
   1392    }
   1393    U_ASSERT(ces1Length <= Collation::MAX_EXPANSION_LENGTH);
   1394    for(int32_t i = 0; i < ces1Length; ++i) {
   1395        if(ces1[i] != ces2[i]) { return false; }
   1396    }
   1397    return true;
   1398 }
   1399 
   1400 #ifdef DEBUG_COLLATION_BUILDER
   1401 
   1402 uint32_t
   1403 alignWeightRight(uint32_t w) {
   1404    if(w != 0) {
   1405        while((w & 0xff) == 0) { w >>= 8; }
   1406    }
   1407    return w;
   1408 }
   1409 
   1410 #endif
   1411 
   1412 void
   1413 CollationBuilder::makeTailoredCEs(UErrorCode &errorCode) {
   1414    if(U_FAILURE(errorCode)) { return; }
   1415 
   1416    CollationWeights primaries, secondaries, tertiaries;
   1417    int64_t *nodesArray = nodes.getBuffer();
   1418 #ifdef DEBUG_COLLATION_BUILDER
   1419        puts("\nCollationBuilder::makeTailoredCEs()");
   1420 #endif
   1421 
   1422    for(int32_t rpi = 0; rpi < rootPrimaryIndexes.size(); ++rpi) {
   1423        int32_t i = rootPrimaryIndexes.elementAti(rpi);
   1424        int64_t node = nodesArray[i];
   1425        uint32_t p = weight32FromNode(node);
   1426        uint32_t s = p == 0 ? 0 : Collation::COMMON_WEIGHT16;
   1427        uint32_t t = s;
   1428        uint32_t q = 0;
   1429        UBool pIsTailored = false;
   1430        UBool sIsTailored = false;
   1431        UBool tIsTailored = false;
   1432 #ifdef DEBUG_COLLATION_BUILDER
   1433        printf("\nprimary     %lx\n", (long)alignWeightRight(p));
   1434 #endif
   1435        int32_t pIndex = p == 0 ? 0 : rootElements.findPrimary(p);
   1436        int32_t nextIndex = nextIndexFromNode(node);
   1437        while(nextIndex != 0) {
   1438            i = nextIndex;
   1439            node = nodesArray[i];
   1440            nextIndex = nextIndexFromNode(node);
   1441            int32_t strength = strengthFromNode(node);
   1442            if(strength == UCOL_QUATERNARY) {
   1443                U_ASSERT(isTailoredNode(node));
   1444 #ifdef DEBUG_COLLATION_BUILDER
   1445                printf("      quat+     ");
   1446 #endif
   1447                if(q == 3) {
   1448                    errorCode = U_BUFFER_OVERFLOW_ERROR;
   1449                    errorReason = "quaternary tailoring gap too small";
   1450                    return;
   1451                }
   1452                ++q;
   1453            } else {
   1454                if(strength == UCOL_TERTIARY) {
   1455                    if(isTailoredNode(node)) {
   1456 #ifdef DEBUG_COLLATION_BUILDER
   1457                        printf("    ter+        ");
   1458 #endif
   1459                        if(!tIsTailored) {
   1460                            // First tailored tertiary node for [p, s].
   1461                            int32_t tCount = countTailoredNodes(nodesArray, nextIndex,
   1462                                                                UCOL_TERTIARY) + 1;
   1463                            uint32_t tLimit;
   1464                            if(t == 0) {
   1465                                // Gap at the beginning of the tertiary CE range.
   1466                                t = rootElements.getTertiaryBoundary() - 0x100;
   1467                                tLimit = rootElements.getFirstTertiaryCE() & Collation::ONLY_TERTIARY_MASK;
   1468                            } else if(!pIsTailored && !sIsTailored) {
   1469                                // p and s are root weights.
   1470                                tLimit = rootElements.getTertiaryAfter(pIndex, s, t);
   1471                            } else if(t == Collation::BEFORE_WEIGHT16) {
   1472                                tLimit = Collation::COMMON_WEIGHT16;
   1473                            } else {
   1474                                // [p, s] is tailored.
   1475                                U_ASSERT(t == Collation::COMMON_WEIGHT16);
   1476                                tLimit = rootElements.getTertiaryBoundary();
   1477                            }
   1478                            U_ASSERT(tLimit == 0x4000 || (tLimit & ~Collation::ONLY_TERTIARY_MASK) == 0);
   1479                            tertiaries.initForTertiary();
   1480                            if(!tertiaries.allocWeights(t, tLimit, tCount)) {
   1481                                errorCode = U_BUFFER_OVERFLOW_ERROR;
   1482                                errorReason = "tertiary tailoring gap too small";
   1483                                return;
   1484                            }
   1485                            tIsTailored = true;
   1486                        }
   1487                        t = tertiaries.nextWeight();
   1488                        U_ASSERT(t != 0xffffffff);
   1489                    } else {
   1490                        t = weight16FromNode(node);
   1491                        tIsTailored = false;
   1492 #ifdef DEBUG_COLLATION_BUILDER
   1493                        printf("    ter     %lx\n", (long)alignWeightRight(t));
   1494 #endif
   1495                    }
   1496                } else {
   1497                    if(strength == UCOL_SECONDARY) {
   1498                        if(isTailoredNode(node)) {
   1499 #ifdef DEBUG_COLLATION_BUILDER
   1500                            printf("  sec+          ");
   1501 #endif
   1502                            if(!sIsTailored) {
   1503                                // First tailored secondary node for p.
   1504                                int32_t sCount = countTailoredNodes(nodesArray, nextIndex,
   1505                                                                    UCOL_SECONDARY) + 1;
   1506                                uint32_t sLimit;
   1507                                if(s == 0) {
   1508                                    // Gap at the beginning of the secondary CE range.
   1509                                    s = rootElements.getSecondaryBoundary() - 0x100;
   1510                                    sLimit = rootElements.getFirstSecondaryCE() >> 16;
   1511                                } else if(!pIsTailored) {
   1512                                    // p is a root primary.
   1513                                    sLimit = rootElements.getSecondaryAfter(pIndex, s);
   1514                                } else if(s == Collation::BEFORE_WEIGHT16) {
   1515                                    sLimit = Collation::COMMON_WEIGHT16;
   1516                                } else {
   1517                                    // p is a tailored primary.
   1518                                    U_ASSERT(s == Collation::COMMON_WEIGHT16);
   1519                                    sLimit = rootElements.getSecondaryBoundary();
   1520                                }
   1521                                if(s == Collation::COMMON_WEIGHT16) {
   1522                                    // Do not tailor into the getSortKey() range of
   1523                                    // compressed common secondaries.
   1524                                    s = rootElements.getLastCommonSecondary();
   1525                                }
   1526                                secondaries.initForSecondary();
   1527                                if(!secondaries.allocWeights(s, sLimit, sCount)) {
   1528                                    errorCode = U_BUFFER_OVERFLOW_ERROR;
   1529                                    errorReason = "secondary tailoring gap too small";
   1530 #ifdef DEBUG_COLLATION_BUILDER
   1531                                    printf("!secondaries.allocWeights(%lx, %lx, sCount=%ld)\n",
   1532                                           (long)alignWeightRight(s), (long)alignWeightRight(sLimit),
   1533                                           (long)alignWeightRight(sCount));
   1534 #endif
   1535                                    return;
   1536                                }
   1537                                sIsTailored = true;
   1538                            }
   1539                            s = secondaries.nextWeight();
   1540                            U_ASSERT(s != 0xffffffff);
   1541                        } else {
   1542                            s = weight16FromNode(node);
   1543                            sIsTailored = false;
   1544 #ifdef DEBUG_COLLATION_BUILDER
   1545                            printf("  sec       %lx\n", (long)alignWeightRight(s));
   1546 #endif
   1547                        }
   1548                    } else /* UCOL_PRIMARY */ {
   1549                        U_ASSERT(isTailoredNode(node));
   1550 #ifdef DEBUG_COLLATION_BUILDER
   1551                        printf("pri+            ");
   1552 #endif
   1553                        if(!pIsTailored) {
   1554                            // First tailored primary node in this list.
   1555                            int32_t pCount = countTailoredNodes(nodesArray, nextIndex,
   1556                                                                UCOL_PRIMARY) + 1;
   1557                            UBool isCompressible = baseData->isCompressiblePrimary(p);
   1558                            uint32_t pLimit =
   1559                                rootElements.getPrimaryAfter(p, pIndex, isCompressible);
   1560                            primaries.initForPrimary(isCompressible);
   1561                            if(!primaries.allocWeights(p, pLimit, pCount)) {
   1562                                errorCode = U_BUFFER_OVERFLOW_ERROR;  // TODO: introduce a more specific UErrorCode?
   1563                                errorReason = "primary tailoring gap too small";
   1564                                return;
   1565                            }
   1566                            pIsTailored = true;
   1567                        }
   1568                        p = primaries.nextWeight();
   1569                        U_ASSERT(p != 0xffffffff);
   1570                        s = Collation::COMMON_WEIGHT16;
   1571                        sIsTailored = false;
   1572                    }
   1573                    t = s == 0 ? 0 : Collation::COMMON_WEIGHT16;
   1574                    tIsTailored = false;
   1575                }
   1576                q = 0;
   1577            }
   1578            if(isTailoredNode(node)) {
   1579                nodesArray[i] = Collation::makeCE(p, s, t, q);
   1580 #ifdef DEBUG_COLLATION_BUILDER
   1581                printf("%016llx\n", (long long)nodesArray[i]);
   1582 #endif
   1583            }
   1584        }
   1585    }
   1586 }
   1587 
   1588 int32_t
   1589 CollationBuilder::countTailoredNodes(const int64_t *nodesArray, int32_t i, int32_t strength) {
   1590    int32_t count = 0;
   1591    for(;;) {
   1592        if(i == 0) { break; }
   1593        int64_t node = nodesArray[i];
   1594        if(strengthFromNode(node) < strength) { break; }
   1595        if(strengthFromNode(node) == strength) {
   1596            if(isTailoredNode(node)) {
   1597                ++count;
   1598            } else {
   1599                break;
   1600            }
   1601        }
   1602        i = nextIndexFromNode(node);
   1603    }
   1604    return count;
   1605 }
   1606 
   1607 class CEFinalizer : public CollationDataBuilder::CEModifier {
   1608 public:
   1609    CEFinalizer(const int64_t *ces) : finalCEs(ces) {}
   1610    virtual ~CEFinalizer();
   1611    virtual int64_t modifyCE32(uint32_t ce32) const override {
   1612        U_ASSERT(!Collation::isSpecialCE32(ce32));
   1613        if(CollationBuilder::isTempCE32(ce32)) {
   1614            // retain case bits
   1615            return finalCEs[CollationBuilder::indexFromTempCE32(ce32)] | ((ce32 & 0xc0) << 8);
   1616        } else {
   1617            return Collation::NO_CE;
   1618        }
   1619    }
   1620    virtual int64_t modifyCE(int64_t ce) const override {
   1621        if(CollationBuilder::isTempCE(ce)) {
   1622            // retain case bits
   1623            return finalCEs[CollationBuilder::indexFromTempCE(ce)] | (ce & 0xc000);
   1624        } else {
   1625            return Collation::NO_CE;
   1626        }
   1627    }
   1628 
   1629 private:
   1630    const int64_t *finalCEs;
   1631 };
   1632 
   1633 CEFinalizer::~CEFinalizer() {}
   1634 
   1635 void
   1636 CollationBuilder::finalizeCEs(UErrorCode &errorCode) {
   1637    if(U_FAILURE(errorCode)) { return; }
   1638    LocalPointer<CollationDataBuilder> newBuilder(new CollationDataBuilder(icu4xMode, errorCode), errorCode);
   1639    if(U_FAILURE(errorCode)) {
   1640        return;
   1641    }
   1642    newBuilder->initForTailoring(baseData, errorCode);
   1643    CEFinalizer finalizer(nodes.getBuffer());
   1644    newBuilder->copyFrom(*dataBuilder, finalizer, errorCode);
   1645    if(U_FAILURE(errorCode)) { return; }
   1646    delete dataBuilder;
   1647    dataBuilder = newBuilder.orphan();
   1648 }
   1649 
   1650 int32_t
   1651 CollationBuilder::ceStrength(int64_t ce) {
   1652    return
   1653        isTempCE(ce) ? strengthFromTempCE(ce) :
   1654        (ce & INT64_C(0xff00000000000000)) != 0 ? UCOL_PRIMARY :
   1655        (static_cast<uint32_t>(ce) & 0xff000000) != 0 ? UCOL_SECONDARY :
   1656        ce != 0 ? UCOL_TERTIARY :
   1657        UCOL_IDENTICAL;
   1658 }
   1659 
   1660 U_NAMESPACE_END
   1661 
   1662 U_NAMESPACE_USE
   1663 
   1664 U_CAPI UCollator * U_EXPORT2
   1665 ucol_openRules(const char16_t *rules, int32_t rulesLength,
   1666               UColAttributeValue normalizationMode, UCollationStrength strength,
   1667               UParseError *parseError, UErrorCode *pErrorCode) {
   1668    if(U_FAILURE(*pErrorCode)) { return nullptr; }
   1669    if(rules == nullptr && rulesLength != 0) {
   1670        *pErrorCode = U_ILLEGAL_ARGUMENT_ERROR;
   1671        return nullptr;
   1672    }
   1673    RuleBasedCollator *coll = new RuleBasedCollator();
   1674    if(coll == nullptr) {
   1675        *pErrorCode = U_MEMORY_ALLOCATION_ERROR;
   1676        return nullptr;
   1677    }
   1678    UnicodeString r(rulesLength < 0, rules, rulesLength);
   1679    coll->internalBuildTailoring(r, strength, normalizationMode, parseError, nullptr, *pErrorCode);
   1680    if(U_FAILURE(*pErrorCode)) {
   1681        delete coll;
   1682        return nullptr;
   1683    }
   1684    return coll->toUCollator();
   1685 }
   1686 
   1687 static const int32_t internalBufferSize = 512;
   1688 
   1689 // The @internal ucol_getUnsafeSet() was moved here from ucol_sit.cpp
   1690 // because it calls UnicodeSet "builder" code that depends on all Unicode properties,
   1691 // and the rest of the collation "runtime" code only depends on normalization.
   1692 // This function is not related to the collation builder,
   1693 // but it did not seem worth moving it into its own .cpp file,
   1694 // nor rewriting it to use lower-level UnicodeSet and Normalizer2Impl methods.
   1695 U_CAPI int32_t U_EXPORT2
   1696 ucol_getUnsafeSet( const UCollator *coll,
   1697                  USet *unsafe,
   1698                  UErrorCode *status)
   1699 {
   1700    char16_t buffer[internalBufferSize];
   1701    int32_t len = 0;
   1702 
   1703    uset_clear(unsafe);
   1704 
   1705    // cccpattern = "[[:^tccc=0:][:^lccc=0:]]", unfortunately variant
   1706    static const char16_t cccpattern[25] = { 0x5b, 0x5b, 0x3a, 0x5e, 0x74, 0x63, 0x63, 0x63, 0x3d, 0x30, 0x3a, 0x5d,
   1707                                    0x5b, 0x3a, 0x5e, 0x6c, 0x63, 0x63, 0x63, 0x3d, 0x30, 0x3a, 0x5d, 0x5d, 0x00 };
   1708 
   1709    // add chars that fail the fcd check
   1710    uset_applyPattern(unsafe, cccpattern, 24, USET_IGNORE_SPACE, status);
   1711 
   1712    // add lead/trail surrogates
   1713    // (trail surrogates should need to be unsafe only if the caller tests for UTF-16 code *units*,
   1714    // not when testing code *points*)
   1715    uset_addRange(unsafe, 0xd800, 0xdfff);
   1716 
   1717    USet *contractions = uset_open(0,0);
   1718 
   1719    int32_t i = 0, j = 0;
   1720    ucol_getContractionsAndExpansions(coll, contractions, nullptr, false, status);
   1721    int32_t contsSize = uset_size(contractions);
   1722    UChar32 c = 0;
   1723    // Contraction set consists only of strings
   1724    // to get unsafe code points, we need to
   1725    // break the strings apart and add them to the unsafe set
   1726    for(i = 0; i < contsSize; i++) {
   1727        len = uset_getItem(contractions, i, nullptr, nullptr, buffer, internalBufferSize, status);
   1728        if(len > 0) {
   1729            j = 0;
   1730            while(j < len) {
   1731                U16_NEXT(buffer, j, len, c);
   1732                if(j < len) {
   1733                    uset_add(unsafe, c);
   1734                }
   1735            }
   1736        }
   1737    }
   1738 
   1739    uset_close(contractions);
   1740 
   1741    return uset_size(unsafe);
   1742 }
   1743 
   1744 #endif  // !UCONFIG_NO_COLLATION