icuSources/i18n/collationbuilder.cpp

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