icuSources/i18n/collationbuilder.cpp

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