// © 2016 and later: Unicode, Inc. and others.

// License & terms of use: http://www.unicode.org/copyright.html

/*

*******************************************************************************

* Copyright (C) 2013-2014, International Business Machines

* Corporation and others.  All Rights Reserved.

*******************************************************************************

* collationbuilder.cpp

*

* (replaced the former ucol_bld.cpp)

*

* created on: 2013may06

* created by: Markus W. Scherer

*/

#ifdef DEBUG_COLLATION_BUILDER

#include <stdio.h>

#endif

#include "unicode/utypes.h"

#if !UCONFIG_NO_COLLATION

#include "unicode/caniter.h"

#include "unicode/normalizer2.h"

#include "unicode/tblcoll.h"

#include "unicode/parseerr.h"

#include "unicode/uchar.h"

#include "unicode/ucol.h"

#include "unicode/unistr.h"

#include "unicode/usetiter.h"

#include "unicode/utf16.h"

#include "unicode/uversion.h"

#include "cmemory.h"

#include "collation.h"

#include "collationbuilder.h"

#include "collationdata.h"

#include "collationdatabuilder.h"

#include "collationfastlatin.h"

#include "collationroot.h"

#include "collationrootelements.h"

#include "collationruleparser.h"

#include "collationsettings.h"

#include "collationtailoring.h"

#include "collationweights.h"

#include "normalizer2impl.h"

#include "uassert.h"

#include "ucol_imp.h"

#include "utf16collationiterator.h"

U_NAMESPACE_BEGIN

namespace {

class BundleImporter : public CollationRuleParser::Importer {

public:

    BundleImporter() {}

    virtual ~BundleImporter();

    virtual void getRules(

            const char *localeID, const char *collationType,

            UnicodeString &rules,

            const char *&errorReason, UErrorCode &errorCode);

};

BundleImporter::~BundleImporter() {}

void

BundleImporter::getRules(

        const char *localeID, const char *collationType,

        UnicodeString &rules,

        const char *& /*errorReason*/, UErrorCode &errorCode) {

    CollationLoader::loadRules(localeID, collationType, rules, errorCode);

}

}  // namespace

// RuleBasedCollator implementation ---------------------------------------- ***

// These methods are here, rather than in rulebasedcollator.cpp,

// for modularization:

// Most code using Collator does not need to build a Collator from rules.

// By moving these constructors and helper methods to a separate file,

// most code will not have a static dependency on the builder code.

RuleBasedCollator::RuleBasedCollator()

        : data(NULL),

          settings(NULL),

          tailoring(NULL),

          cacheEntry(NULL),

          validLocale(""),

          explicitlySetAttributes(0),

          actualLocaleIsSameAsValid(FALSE) {

}

RuleBasedCollator::RuleBasedCollator(const UnicodeString &rules, UErrorCode &errorCode)

        : data(NULL),

          settings(NULL),

          tailoring(NULL),

          cacheEntry(NULL),

          validLocale(""),

          explicitlySetAttributes(0),

          actualLocaleIsSameAsValid(FALSE) {

    internalBuildTailoring(rules, UCOL_DEFAULT, UCOL_DEFAULT, NULL, NULL, errorCode);

}

RuleBasedCollator::RuleBasedCollator(const UnicodeString &rules, ECollationStrength strength,

                                     UErrorCode &errorCode)

        : data(NULL),

          settings(NULL),

          tailoring(NULL),

          cacheEntry(NULL),

          validLocale(""),

          explicitlySetAttributes(0),

          actualLocaleIsSameAsValid(FALSE) {

    internalBuildTailoring(rules, strength, UCOL_DEFAULT, NULL, NULL, errorCode);

}

RuleBasedCollator::RuleBasedCollator(const UnicodeString &rules,

                                     UColAttributeValue decompositionMode,

                                     UErrorCode &errorCode)

        : data(NULL),

          settings(NULL),

          tailoring(NULL),

          cacheEntry(NULL),

          validLocale(""),

          explicitlySetAttributes(0),

          actualLocaleIsSameAsValid(FALSE) {

    internalBuildTailoring(rules, UCOL_DEFAULT, decompositionMode, NULL, NULL, errorCode);

}

RuleBasedCollator::RuleBasedCollator(const UnicodeString &rules,

                                     ECollationStrength strength,

                                     UColAttributeValue decompositionMode,

                                     UErrorCode &errorCode)

        : data(NULL),

          settings(NULL),

          tailoring(NULL),

          cacheEntry(NULL),

          validLocale(""),

          explicitlySetAttributes(0),

          actualLocaleIsSameAsValid(FALSE) {

    internalBuildTailoring(rules, strength, decompositionMode, NULL, NULL, errorCode);

}

RuleBasedCollator::RuleBasedCollator(const UnicodeString &rules,

                                     UParseError &parseError, UnicodeString &reason,

                                     UErrorCode &errorCode)

        : data(NULL),

          settings(NULL),

          tailoring(NULL),

          cacheEntry(NULL),

          validLocale(""),

          explicitlySetAttributes(0),

          actualLocaleIsSameAsValid(FALSE) {

    internalBuildTailoring(rules, UCOL_DEFAULT, UCOL_DEFAULT, &parseError, &reason, errorCode);

}

void

RuleBasedCollator::internalBuildTailoring(const UnicodeString &rules,

                                          int32_t strength,

                                          UColAttributeValue decompositionMode,

                                          UParseError *outParseError, UnicodeString *outReason,

                                          UErrorCode &errorCode) {

    const CollationTailoring *base = CollationRoot::getRoot(errorCode);

    if(U_FAILURE(errorCode)) { return; }

    if(outReason != NULL) { outReason->remove(); }

    CollationBuilder builder(base, errorCode);

    UVersionInfo noVersion = { 0, 0, 0, 0 };

    BundleImporter importer;

    LocalPointer<CollationTailoring> t(builder.parseAndBuild(rules, noVersion,

                                                             &importer,

                                                             outParseError, errorCode));

    if(U_FAILURE(errorCode)) {

        const char *reason = builder.getErrorReason();

        if(reason != NULL && outReason != NULL) {

            *outReason = UnicodeString(reason, -1, US_INV);

        }

        return;

    }

    t->actualLocale.setToBogus();

    adoptTailoring(t.orphan(), errorCode);

    // Set attributes after building the collator,

    // to keep the default settings consistent with the rule string.

    if(strength != UCOL_DEFAULT) {

        setAttribute(UCOL_STRENGTH, (UColAttributeValue)strength, errorCode);

    }

    if(decompositionMode != UCOL_DEFAULT) {

        setAttribute(UCOL_NORMALIZATION_MODE, decompositionMode, errorCode);

    }

}

// CollationBuilder implementation ----------------------------------------- ***

// Some compilers don't care if constants are defined in the .cpp file.

// MS Visual C++ does not like it, but gcc requires it. clang does not care.

#ifndef _MSC_VER

const int32_t CollationBuilder::HAS_BEFORE2;

const int32_t CollationBuilder::HAS_BEFORE3;

#endif

CollationBuilder::CollationBuilder(const CollationTailoring *b, UErrorCode &errorCode)

        : nfd(*Normalizer2::getNFDInstance(errorCode)),

          fcd(*Normalizer2Factory::getFCDInstance(errorCode)),

          nfcImpl(*Normalizer2Factory::getNFCImpl(errorCode)),

          base(b),

          baseData(b->data),

          rootElements(b->data->rootElements, b->data->rootElementsLength),

          variableTop(0),

          dataBuilder(new CollationDataBuilder(errorCode)), fastLatinEnabled(TRUE),

          errorReason(NULL),

          cesLength(0),

          rootPrimaryIndexes(errorCode), nodes(errorCode) {

    nfcImpl.ensureCanonIterData(errorCode);

    if(U_FAILURE(errorCode)) {

        errorReason = "CollationBuilder fields initialization failed";

        return;

    }

    if(dataBuilder == NULL) {

        errorCode = U_MEMORY_ALLOCATION_ERROR;

        return;

    }

    dataBuilder->initForTailoring(baseData, errorCode);

    if(U_FAILURE(errorCode)) {

        errorReason = "CollationBuilder initialization failed";

    }

}

CollationBuilder::~CollationBuilder() {

    delete dataBuilder;

}

CollationTailoring *

CollationBuilder::parseAndBuild(const UnicodeString &ruleString,

                                const UVersionInfo rulesVersion,

                                CollationRuleParser::Importer *importer,

                                UParseError *outParseError,

                                UErrorCode &errorCode) {

    if(U_FAILURE(errorCode)) { return NULL; }

    if(baseData->rootElements == NULL) {

        errorCode = U_MISSING_RESOURCE_ERROR;

        errorReason = "missing root elements data, tailoring not supported";

        return NULL;

    }

    LocalPointer<CollationTailoring> tailoring(new CollationTailoring(base->settings));

    if(tailoring.isNull() || tailoring->isBogus()) {

        errorCode = U_MEMORY_ALLOCATION_ERROR;

        return NULL;

    }

    CollationRuleParser parser(baseData, errorCode);

    if(U_FAILURE(errorCode)) { return NULL; }

    // Note: This always bases &[last variable] and &[first regular]

    // on the root collator's maxVariable/variableTop.

    // If we wanted this to change after [maxVariable x], then we would keep

    // the tailoring.settings pointer here and read its variableTop when we need it.

    // See http://unicode.org/cldr/trac/ticket/6070

    variableTop = base->settings->variableTop;

    parser.setSink(this);

    parser.setImporter(importer);

    CollationSettings &ownedSettings = *SharedObject::copyOnWrite(tailoring->settings);

    parser.parse(ruleString, ownedSettings, outParseError, errorCode);

    errorReason = parser.getErrorReason();

    if(U_FAILURE(errorCode)) { return NULL; }

    if(dataBuilder->hasMappings()) {

        makeTailoredCEs(errorCode);

        closeOverComposites(errorCode);

        finalizeCEs(errorCode);

        // Copy all of ASCII, and Latin-1 letters, into each tailoring.

        optimizeSet.add(0, 0x7f);

        optimizeSet.add(0xc0, 0xff);

        // Hangul is decomposed on the fly during collation,

        // and the tailoring data is always built with HANGUL_TAG specials.

        optimizeSet.remove(Hangul::HANGUL_BASE, Hangul::HANGUL_END);

        dataBuilder->optimize(optimizeSet, errorCode);

        tailoring->ensureOwnedData(errorCode);

        if(U_FAILURE(errorCode)) { return NULL; }

        if(fastLatinEnabled) { dataBuilder->enableFastLatin(); }

        dataBuilder->build(*tailoring->ownedData, errorCode);

        tailoring->builder = dataBuilder;

        dataBuilder = NULL;

    } else {

        tailoring->data = baseData;

    }

    if(U_FAILURE(errorCode)) { return NULL; }

    ownedSettings.fastLatinOptions = CollationFastLatin::getOptions(

        tailoring->data, ownedSettings,

        ownedSettings.fastLatinPrimaries, UPRV_LENGTHOF(ownedSettings.fastLatinPrimaries));

    tailoring->rules = ruleString;

    tailoring->rules.getTerminatedBuffer();  // ensure NUL-termination

    tailoring->setVersion(base->version, rulesVersion);

    return tailoring.orphan();

}

void

CollationBuilder::addReset(int32_t strength, const UnicodeString &str,

                           const char *&parserErrorReason, UErrorCode &errorCode) {

    if(U_FAILURE(errorCode)) { return; }

    U_ASSERT(!str.isEmpty());

    if(str.charAt(0) == CollationRuleParser::POS_LEAD) {

        ces[0] = getSpecialResetPosition(str, parserErrorReason, errorCode);

        cesLength = 1;

        if(U_FAILURE(errorCode)) { return; }

        U_ASSERT((ces[0] & Collation::CASE_AND_QUATERNARY_MASK) == 0);

    } else {

        // normal reset to a character or string

        UnicodeString nfdString = nfd.normalize(str, errorCode);

        if(U_FAILURE(errorCode)) {

            parserErrorReason = "normalizing the reset position";

            return;

        }

        cesLength = dataBuilder->getCEs(nfdString, ces, 0);

        if(cesLength > Collation::MAX_EXPANSION_LENGTH) {

            errorCode = U_ILLEGAL_ARGUMENT_ERROR;

            parserErrorReason = "reset position maps to too many collation elements (more than 31)";

            return;

        }

    }

    if(strength == UCOL_IDENTICAL) { return; }  // simple reset-at-position

    // &[before strength]position

    U_ASSERT(UCOL_PRIMARY <= strength && strength <= UCOL_TERTIARY);

    int32_t index = findOrInsertNodeForCEs(strength, parserErrorReason, errorCode);

    if(U_FAILURE(errorCode)) { return; }

    int64_t node = nodes.elementAti(index);

    // If the index is for a "weaker" node,

    // then skip backwards over this and further "weaker" nodes.

    while(strengthFromNode(node) > strength) {

        index = previousIndexFromNode(node);

        node = nodes.elementAti(index);

    }

    // Find or insert a node whose index we will put into a temporary CE.

    if(strengthFromNode(node) == strength && isTailoredNode(node)) {

        // Reset to just before this same-strength tailored node.

        index = previousIndexFromNode(node);

    } else if(strength == UCOL_PRIMARY) {

        // root primary node (has no previous index)

        uint32_t p = weight32FromNode(node);

        if(p == 0) {

            errorCode = U_UNSUPPORTED_ERROR;

            parserErrorReason = "reset primary-before ignorable not possible";

            return;

        }

        if(p <= rootElements.getFirstPrimary()) {

            // There is no primary gap between ignorables and the space-first-primary.

            errorCode = U_UNSUPPORTED_ERROR;

            parserErrorReason = "reset primary-before first non-ignorable not supported";

            return;

        }

        if(p == Collation::FIRST_TRAILING_PRIMARY) {

            // We do not support tailoring to an unassigned-implicit CE.

            errorCode = U_UNSUPPORTED_ERROR;

            parserErrorReason = "reset primary-before [first trailing] not supported";

            return;

        }

        p = rootElements.getPrimaryBefore(p, baseData->isCompressiblePrimary(p));

        index = findOrInsertNodeForPrimary(p, errorCode);

        // Go to the last node in this list:

        // Tailor after the last node between adjacent root nodes.

        for(;;) {

            node = nodes.elementAti(index);

            int32_t nextIndex = nextIndexFromNode(node);

            if(nextIndex == 0) { break; }

            index = nextIndex;

        }

    } else {

        // &[before 2] or &[before 3]

        index = findCommonNode(index, UCOL_SECONDARY);

        if(strength >= UCOL_TERTIARY) {

            index = findCommonNode(index, UCOL_TERTIARY);

        }

        // findCommonNode() stayed on the stronger node or moved to

        // an explicit common-weight node of the reset-before strength.

        node = nodes.elementAti(index);

        if(strengthFromNode(node) == strength) {

            // Found a same-strength node with an explicit weight.

            uint32_t weight16 = weight16FromNode(node);

            if(weight16 == 0) {

                errorCode = U_UNSUPPORTED_ERROR;

                if(strength == UCOL_SECONDARY) {

                    parserErrorReason = "reset secondary-before secondary ignorable not possible";

                } else {

                    parserErrorReason = "reset tertiary-before completely ignorable not possible";

                }

                return;

            }

            U_ASSERT(weight16 > Collation::BEFORE_WEIGHT16);

            // Reset to just before this node.

            // Insert the preceding same-level explicit weight if it is not there already.

            // Which explicit weight immediately precedes this one?

            weight16 = getWeight16Before(index, node, strength);

            // Does this preceding weight have a node?

            uint32_t previousWeight16;

            int32_t previousIndex = previousIndexFromNode(node);

            for(int32_t i = previousIndex;; i = previousIndexFromNode(node)) {

                node = nodes.elementAti(i);

                int32_t previousStrength = strengthFromNode(node);

                if(previousStrength < strength) {

                    U_ASSERT(weight16 >= Collation::COMMON_WEIGHT16 || i == previousIndex);

                    // Either the reset element has an above-common weight and

                    // the parent node provides the implied common weight,

                    // or the reset element has a weight<=common in the node

                    // right after the parent, and we need to insert the preceding weight.

                    previousWeight16 = Collation::COMMON_WEIGHT16;

                    break;

                } else if(previousStrength == strength && !isTailoredNode(node)) {

                    previousWeight16 = weight16FromNode(node);

                    break;

                }

                // Skip weaker nodes and same-level tailored nodes.

            }

            if(previousWeight16 == weight16) {

                // The preceding weight has a node,

                // maybe with following weaker or tailored nodes.

                // Reset to the last of them.

                index = previousIndex;

            } else {

                // Insert a node with the preceding weight, reset to that.

                node = nodeFromWeight16(weight16) | nodeFromStrength(strength);

                index = insertNodeBetween(previousIndex, index, node, errorCode);

            }

        } else {

            // Found a stronger node with implied strength-common weight.

            uint32_t weight16 = getWeight16Before(index, node, strength);

            index = findOrInsertWeakNode(index, weight16, strength, errorCode);

        }

        // Strength of the temporary CE = strength of its reset position.

        // Code above raises an error if the before-strength is stronger.

        strength = ceStrength(ces[cesLength - 1]);

    }

    if(U_FAILURE(errorCode)) {

        parserErrorReason = "inserting reset position for &[before n]";

        return;

    }

    ces[cesLength - 1] = tempCEFromIndexAndStrength(index, strength);

}

uint32_t

CollationBuilder::getWeight16Before(int32_t index, int64_t node, int32_t level) {

    U_ASSERT(strengthFromNode(node) < level || !isTailoredNode(node));

    // Collect the root CE weights if this node is for a root CE.

    // If it is not, then return the low non-primary boundary for a tailored CE.

    uint32_t t;

    if(strengthFromNode(node) == UCOL_TERTIARY) {

        t = weight16FromNode(node);

    } else {

        t = Collation::COMMON_WEIGHT16;  // Stronger node with implied common weight.

    }

    while(strengthFromNode(node) > UCOL_SECONDARY) {

        index = previousIndexFromNode(node);

        node = nodes.elementAti(index);

    }

    if(isTailoredNode(node)) {

        return Collation::BEFORE_WEIGHT16;

    }

    uint32_t s;

    if(strengthFromNode(node) == UCOL_SECONDARY) {

        s = weight16FromNode(node);

    } else {

        s = Collation::COMMON_WEIGHT16;  // Stronger node with implied common weight.

    }

    while(strengthFromNode(node) > UCOL_PRIMARY) {

        index = previousIndexFromNode(node);

        node = nodes.elementAti(index);

    }

    if(isTailoredNode(node)) {

        return Collation::BEFORE_WEIGHT16;

    }

    // [p, s, t] is a root CE. Return the preceding weight for the requested level.

    uint32_t p = weight32FromNode(node);

    uint32_t weight16;

    if(level == UCOL_SECONDARY) {

        weight16 = rootElements.getSecondaryBefore(p, s);

    } else {

        weight16 = rootElements.getTertiaryBefore(p, s, t);

        U_ASSERT((weight16 & ~Collation::ONLY_TERTIARY_MASK) == 0);

    }

    return weight16;

}

int64_t

CollationBuilder::getSpecialResetPosition(const UnicodeString &str,

                                          const char *&parserErrorReason, UErrorCode &errorCode) {

    U_ASSERT(str.length() == 2);

    int64_t ce;

    int32_t strength = UCOL_PRIMARY;

    UBool isBoundary = FALSE;

    UChar32 pos = str.charAt(1) - CollationRuleParser::POS_BASE;

    U_ASSERT(0 <= pos && pos <= CollationRuleParser::LAST_TRAILING);

    switch(pos) {

    case CollationRuleParser::FIRST_TERTIARY_IGNORABLE:

        // Quaternary CEs are not supported.

        // Non-zero quaternary weights are possible only on tertiary or stronger CEs.

        return 0;

    case CollationRuleParser::LAST_TERTIARY_IGNORABLE:

        return 0;

    case CollationRuleParser::FIRST_SECONDARY_IGNORABLE: {

        // Look for a tailored tertiary node after [0, 0, 0].

        int32_t index = findOrInsertNodeForRootCE(0, UCOL_TERTIARY, errorCode);

        if(U_FAILURE(errorCode)) { return 0; }

        int64_t node = nodes.elementAti(index);

        if((index = nextIndexFromNode(node)) != 0) {

            node = nodes.elementAti(index);

            U_ASSERT(strengthFromNode(node) <= UCOL_TERTIARY);

            if(isTailoredNode(node) && strengthFromNode(node) == UCOL_TERTIARY) {

                return tempCEFromIndexAndStrength(index, UCOL_TERTIARY);

            }

        }

        return rootElements.getFirstTertiaryCE();

        // No need to look for nodeHasAnyBefore() on a tertiary node.

    }

    case CollationRuleParser::LAST_SECONDARY_IGNORABLE:

        ce = rootElements.getLastTertiaryCE();

        strength = UCOL_TERTIARY;

        break;

    case CollationRuleParser::FIRST_PRIMARY_IGNORABLE: {

        // Look for a tailored secondary node after [0, 0, *].

        int32_t index = findOrInsertNodeForRootCE(0, UCOL_SECONDARY, errorCode);

        if(U_FAILURE(errorCode)) { return 0; }

        int64_t node = nodes.elementAti(index);

        while((index = nextIndexFromNode(node)) != 0) {

            node = nodes.elementAti(index);

            strength = strengthFromNode(node);

            if(strength < UCOL_SECONDARY) { break; }

            if(strength == UCOL_SECONDARY) {

                if(isTailoredNode(node)) {

                    if(nodeHasBefore3(node)) {

                        index = nextIndexFromNode(nodes.elementAti(nextIndexFromNode(node)));

                        U_ASSERT(isTailoredNode(nodes.elementAti(index)));

                    }

                    return tempCEFromIndexAndStrength(index, UCOL_SECONDARY);

                } else {

                    break;

                }

            }

        }

        ce = rootElements.getFirstSecondaryCE();

        strength = UCOL_SECONDARY;

        break;

    }

    case CollationRuleParser::LAST_PRIMARY_IGNORABLE:

        ce = rootElements.getLastSecondaryCE();

        strength = UCOL_SECONDARY;

        break;

    case CollationRuleParser::FIRST_VARIABLE:

        ce = rootElements.getFirstPrimaryCE();

        isBoundary = TRUE;  // FractionalUCA.txt: FDD1 00A0, SPACE first primary

        break;

    case CollationRuleParser::LAST_VARIABLE:

        ce = rootElements.lastCEWithPrimaryBefore(variableTop + 1);

        break;

    case CollationRuleParser::FIRST_REGULAR:

        ce = rootElements.firstCEWithPrimaryAtLeast(variableTop + 1);

        isBoundary = TRUE;  // FractionalUCA.txt: FDD1 263A, SYMBOL first primary

        break;

    case CollationRuleParser::LAST_REGULAR:

        // Use the Hani-first-primary rather than the actual last "regular" CE before it,

        // for backward compatibility with behavior before the introduction of

        // script-first-primary CEs in the root collator.

        ce = rootElements.firstCEWithPrimaryAtLeast(

            baseData->getFirstPrimaryForGroup(USCRIPT_HAN));

        break;

    case CollationRuleParser::FIRST_IMPLICIT:

        ce = baseData->getSingleCE(0x4e00, errorCode);

        break;

    case CollationRuleParser::LAST_IMPLICIT:

        // We do not support tailoring to an unassigned-implicit CE.

        errorCode = U_UNSUPPORTED_ERROR;

        parserErrorReason = "reset to [last implicit] not supported";

        return 0;

    case CollationRuleParser::FIRST_TRAILING:

        ce = Collation::makeCE(Collation::FIRST_TRAILING_PRIMARY);

        isBoundary = TRUE;  // trailing first primary (there is no mapping for it)

        break;

    case CollationRuleParser::LAST_TRAILING:

        errorCode = U_ILLEGAL_ARGUMENT_ERROR;

        parserErrorReason = "LDML forbids tailoring to U+FFFF";

        return 0;

    default:

        UPRV_UNREACHABLE;

    }

    int32_t index = findOrInsertNodeForRootCE(ce, strength, errorCode);

    if(U_FAILURE(errorCode)) { return 0; }

    int64_t node = nodes.elementAti(index);

    if((pos & 1) == 0) {

        // even pos = [first xyz]

        if(!nodeHasAnyBefore(node) && isBoundary) {

            // A <group> first primary boundary is artificially added to FractionalUCA.txt.

            // It is reachable via its special contraction, but is not normally used.

            // Find the first character tailored after the boundary CE,

            // or the first real root CE after it.

            if((index = nextIndexFromNode(node)) != 0) {

                // If there is a following node, then it must be tailored

                // because there are no root CEs with a boundary primary

                // and non-common secondary/tertiary weights.

                node = nodes.elementAti(index);

                U_ASSERT(isTailoredNode(node));

                ce = tempCEFromIndexAndStrength(index, strength);

            } else {

                U_ASSERT(strength == UCOL_PRIMARY);

                uint32_t p = (uint32_t)(ce >> 32);

                int32_t pIndex = rootElements.findPrimary(p);

                UBool isCompressible = baseData->isCompressiblePrimary(p);

                p = rootElements.getPrimaryAfter(p, pIndex, isCompressible);

                ce = Collation::makeCE(p);

                index = findOrInsertNodeForRootCE(ce, UCOL_PRIMARY, errorCode);

                if(U_FAILURE(errorCode)) { return 0; }

                node = nodes.elementAti(index);

            }

        }

        if(nodeHasAnyBefore(node)) {

            // Get the first node that was tailored before this one at a weaker strength.

            if(nodeHasBefore2(node)) {

                index = nextIndexFromNode(nodes.elementAti(nextIndexFromNode(node)));

                node = nodes.elementAti(index);

            }

            if(nodeHasBefore3(node)) {

                index = nextIndexFromNode(nodes.elementAti(nextIndexFromNode(node)));

            }

            U_ASSERT(isTailoredNode(nodes.elementAti(index)));

            ce = tempCEFromIndexAndStrength(index, strength);

        }

    } else {

        // odd pos = [last xyz]

        // Find the last node that was tailored after the [last xyz]

        // at a strength no greater than the position's strength.

        for(;;) {

            int32_t nextIndex = nextIndexFromNode(node);

            if(nextIndex == 0) { break; }

            int64_t nextNode = nodes.elementAti(nextIndex);

            if(strengthFromNode(nextNode) < strength) { break; }

            index = nextIndex;

            node = nextNode;

        }

        // Do not make a temporary CE for a root node.

        // This last node might be the node for the root CE itself,

        // or a node with a common secondary or tertiary weight.

        if(isTailoredNode(node)) {

            ce = tempCEFromIndexAndStrength(index, strength);

        }

    }

    return ce;

}

void

CollationBuilder::addRelation(int32_t strength, const UnicodeString &prefix,

                              const UnicodeString &str, const UnicodeString &extension,

                              const char *&parserErrorReason, UErrorCode &errorCode) {

    if(U_FAILURE(errorCode)) { return; }

    UnicodeString nfdPrefix;

    if(!prefix.isEmpty()) {

        nfd.normalize(prefix, nfdPrefix, errorCode);

        if(U_FAILURE(errorCode)) {

            parserErrorReason = "normalizing the relation prefix";

            return;

        }

    }

    UnicodeString nfdString = nfd.normalize(str, errorCode);

    if(U_FAILURE(errorCode)) {

        parserErrorReason = "normalizing the relation string";

        return;

    }

    // The runtime code decomposes Hangul syllables on the fly,

    // with recursive processing but without making the Jamo pieces visible for matching.

    // It does not work with certain types of contextual mappings.

    int32_t nfdLength = nfdString.length();

    if(nfdLength >= 2) {

        UChar c = nfdString.charAt(0);

        if(Hangul::isJamoL(c) || Hangul::isJamoV(c)) {

            // While handling a Hangul syllable, contractions starting with Jamo L or V

            // would not see the following Jamo of that syllable.

            errorCode = U_UNSUPPORTED_ERROR;

            parserErrorReason = "contractions starting with conjoining Jamo L or V not supported";

            return;

        }

        c = nfdString.charAt(nfdLength - 1);

        if(Hangul::isJamoL(c) ||

                (Hangul::isJamoV(c) && Hangul::isJamoL(nfdString.charAt(nfdLength - 2)))) {

            // A contraction ending with Jamo L or L+V would require

            // generating Hangul syllables in addTailComposites() (588 for a Jamo L),

            // or decomposing a following Hangul syllable on the fly, during contraction matching.

            errorCode = U_UNSUPPORTED_ERROR;

            parserErrorReason = "contractions ending with conjoining Jamo L or L+V not supported";

            return;

        }

        // A Hangul syllable completely inside a contraction is ok.

    }

    // Note: If there is a prefix, then the parser checked that

    // both the prefix and the string begin with NFC boundaries (not Jamo V or T).

    // Therefore: prefix.isEmpty() || !isJamoVOrT(nfdString.charAt(0))

    // (While handling a Hangul syllable, prefixes on Jamo V or T

    // would not see the previous Jamo of that syllable.)

    if(strength != UCOL_IDENTICAL) {

        // Find the node index after which we insert the new tailored node.

        int32_t index = findOrInsertNodeForCEs(strength, parserErrorReason, errorCode);

        U_ASSERT(cesLength > 0);

        int64_t ce = ces[cesLength - 1];

        if(strength == UCOL_PRIMARY && !isTempCE(ce) && (uint32_t)(ce >> 32) == 0) {

            // There is no primary gap between ignorables and the space-first-primary.

            errorCode = U_UNSUPPORTED_ERROR;

            parserErrorReason = "tailoring primary after ignorables not supported";

            return;

        }

        if(strength == UCOL_QUATERNARY && ce == 0) {

            // The CE data structure does not support non-zero quaternary weights

            // on tertiary ignorables.

            errorCode = U_UNSUPPORTED_ERROR;

            parserErrorReason = "tailoring quaternary after tertiary ignorables not supported";

            return;

        }

        // Insert the new tailored node.

        index = insertTailoredNodeAfter(index, strength, errorCode);

        if(U_FAILURE(errorCode)) {

            parserErrorReason = "modifying collation elements";

            return;

        }

        // Strength of the temporary CE:

        // The new relation may yield a stronger CE but not a weaker one.

        int32_t tempStrength = ceStrength(ce);

        if(strength < tempStrength) { tempStrength = strength; }

        ces[cesLength - 1] = tempCEFromIndexAndStrength(index, tempStrength);

    }

    setCaseBits(nfdString, parserErrorReason, errorCode);

    if(U_FAILURE(errorCode)) { return; }

    int32_t cesLengthBeforeExtension = cesLength;

    if(!extension.isEmpty()) {

        UnicodeString nfdExtension = nfd.normalize(extension, errorCode);

        if(U_FAILURE(errorCode)) {

            parserErrorReason = "normalizing the relation extension";

            return;

        }

        cesLength = dataBuilder->getCEs(nfdExtension, ces, cesLength);

        if(cesLength > Collation::MAX_EXPANSION_LENGTH) {

            errorCode = U_ILLEGAL_ARGUMENT_ERROR;

            parserErrorReason =

                "extension string adds too many collation elements (more than 31 total)";

            return;

        }

    }

    uint32_t ce32 = Collation::UNASSIGNED_CE32;

    if((prefix != nfdPrefix || str != nfdString) &&

            !ignorePrefix(prefix, errorCode) && !ignoreString(str, errorCode)) {

        // Map from the original input to the CEs.

        // We do this in case the canonical closure is incomplete,

        // so that it is possible to explicitly provide the missing mappings.

        ce32 = addIfDifferent(prefix, str, ces, cesLength, ce32, errorCode);

    }

    addWithClosure(nfdPrefix, nfdString, ces, cesLength, ce32, errorCode);

    if(U_FAILURE(errorCode)) {

        parserErrorReason = "writing collation elements";

        return;

    }

    cesLength = cesLengthBeforeExtension;

}

int32_t

CollationBuilder::findOrInsertNodeForCEs(int32_t strength, const char *&parserErrorReason,

                                         UErrorCode &errorCode) {

    if(U_FAILURE(errorCode)) { return 0; }

    U_ASSERT(UCOL_PRIMARY <= strength && strength <= UCOL_QUATERNARY);

    // Find the last CE that is at least as "strong" as the requested difference.

    // Note: Stronger is smaller (UCOL_PRIMARY=0).

    int64_t ce;

    for(;; --cesLength) {

        if(cesLength == 0) {

            ce = ces[0] = 0;

            cesLength = 1;

            break;

        } else {

            ce = ces[cesLength - 1];

        }

        if(ceStrength(ce) <= strength) { break; }

    }

    if(isTempCE(ce)) {

        // No need to findCommonNode() here for lower levels

        // because insertTailoredNodeAfter() will do that anyway.

        return indexFromTempCE(ce);

    }

    // root CE

    if((uint8_t)(ce >> 56) == Collation::UNASSIGNED_IMPLICIT_BYTE) {

        errorCode = U_UNSUPPORTED_ERROR;

        parserErrorReason = "tailoring relative to an unassigned code point not supported";

        return 0;

    }

    return findOrInsertNodeForRootCE(ce, strength, errorCode);

}

int32_t

CollationBuilder::findOrInsertNodeForRootCE(int64_t ce, int32_t strength, UErrorCode &errorCode) {

    if(U_FAILURE(errorCode)) { return 0; }

    U_ASSERT((uint8_t)(ce >> 56) != Collation::UNASSIGNED_IMPLICIT_BYTE);

    // Find or insert the node for each of the root CE's weights,

    // down to the requested level/strength.

    // Root CEs must have common=zero quaternary weights (for which we never insert any nodes).

    U_ASSERT((ce & 0xc0) == 0);

    int32_t index = findOrInsertNodeForPrimary((uint32_t)(ce >> 32), errorCode);

    if(strength >= UCOL_SECONDARY) {

        uint32_t lower32 = (uint32_t)ce;

        index = findOrInsertWeakNode(index, lower32 >> 16, UCOL_SECONDARY, errorCode);

        if(strength >= UCOL_TERTIARY) {

            index = findOrInsertWeakNode(index, lower32 & Collation::ONLY_TERTIARY_MASK,

                                         UCOL_TERTIARY, errorCode);

        }

    }

    return index;

}

namespace {

/**

 * Like Java Collections.binarySearch(List, key, Comparator).

 *

 * @return the index>=0 where the item was found,

 *         or the index<0 for inserting the string at ~index in sorted order

 *         (index into rootPrimaryIndexes)

 */

int32_t

binarySearchForRootPrimaryNode(const int32_t *rootPrimaryIndexes, int32_t length,

                               const int64_t *nodes, uint32_t p) {

    if(length == 0) { return ~0; }

    int32_t start = 0;

    int32_t limit = length;

    for (;;) {

        int32_t i = (start + limit) / 2;

        int64_t node = nodes[rootPrimaryIndexes[i]];

        uint32_t nodePrimary = (uint32_t)(node >> 32);  // weight32FromNode(node)

        if (p == nodePrimary) {

            return i;

        } else if (p < nodePrimary) {

            if (i == start) {

                return ~start;  // insert s before i

            }

            limit = i;

        } else {

            if (i == start) {

                return ~(start + 1);  // insert s after i

            }

            start = i;

        }

    }

}

}  // namespace

int32_t

CollationBuilder::findOrInsertNodeForPrimary(uint32_t p, UErrorCode &errorCode) {

    if(U_FAILURE(errorCode)) { return 0; }

    int32_t rootIndex = binarySearchForRootPrimaryNode(

        rootPrimaryIndexes.getBuffer(), rootPrimaryIndexes.size(), nodes.getBuffer(), p);

    if(rootIndex >= 0) {

        return rootPrimaryIndexes.elementAti(rootIndex);

    } else {

        // Start a new list of nodes with this primary.

        int32_t index = nodes.size();

        nodes.addElement(nodeFromWeight32(p), errorCode);

        rootPrimaryIndexes.insertElementAt(index, ~rootIndex, errorCode);

        return index;

    }

}

int32_t

CollationBuilder::findOrInsertWeakNode(int32_t index, uint32_t weight16, int32_t level, UErrorCode &errorCode) {

    if(U_FAILURE(errorCode)) { return 0; }

    U_ASSERT(0 <= index && index < nodes.size());

    U_ASSERT(UCOL_SECONDARY <= level && level <= UCOL_TERTIARY);

    if(weight16 == Collation::COMMON_WEIGHT16) {

        return findCommonNode(index, level);

    }

    // If this will be the first below-common weight for the parent node,

    // then we will also need to insert a common weight after it.

    int64_t node = nodes.elementAti(index);

    U_ASSERT(strengthFromNode(node) < level);  // parent node is stronger

    if(weight16 != 0 && weight16 < Collation::COMMON_WEIGHT16) {

        int32_t hasThisLevelBefore = level == UCOL_SECONDARY ? HAS_BEFORE2 : HAS_BEFORE3;

        if((node & hasThisLevelBefore) == 0) {