icuSources/i18n/rulebasedcollator.cpp

   1 /*
   2 *******************************************************************************
   3 * Copyright (C) 1996-2015, International Business Machines
   4 * Corporation and others.  All Rights Reserved.
   5 *******************************************************************************
   6 * rulebasedcollator.cpp
   7 *
   8 * (replaced the former tblcoll.cpp)
   9 *
  10 * created on: 2012feb14 with new and old collation code
  11 * created by: Markus W. Scherer
  12 */
  13
  14 #include "unicode/utypes.h"
  15
  16 #if !UCONFIG_NO_COLLATION
  17
  18 #include "unicode/coll.h"
  19 #include "unicode/coleitr.h"
  20 #include "unicode/localpointer.h"
  21 #include "unicode/locid.h"
  22 #include "unicode/sortkey.h"
  23 #include "unicode/tblcoll.h"
  24 #include "unicode/ucol.h"
  25 #include "unicode/uiter.h"
  26 #include "unicode/uloc.h"
  27 #include "unicode/uniset.h"
  28 #include "unicode/unistr.h"
  29 #include "unicode/usetiter.h"
  30 #include "unicode/utf8.h"
  31 #include "unicode/uversion.h"
  32 #include "bocsu.h"
  33 #include "charstr.h"
  34 #include "cmemory.h"
  35 #include "collation.h"
  36 #include "collationcompare.h"
  37 #include "collationdata.h"
  38 #include "collationdatareader.h"
  39 #include "collationfastlatin.h"
  40 #include "collationiterator.h"
  41 #include "collationkeys.h"
  42 #include "collationroot.h"
  43 #include "collationsets.h"
  44 #include "collationsettings.h"
  45 #include "collationtailoring.h"
  46 #include "cstring.h"
  47 #include "uassert.h"
  48 #include "ucol_imp.h"
  49 #include "uhash.h"
  50 #include "uitercollationiterator.h"
  51 #include "ustr_imp.h"
  52 #include "utf16collationiterator.h"
  53 #include "utf8collationiterator.h"
  54 #include "uvectr64.h"
  55
  56 U_NAMESPACE_BEGIN
  57
  58 namespace {
  59
  60 class FixedSortKeyByteSink : public SortKeyByteSink {
  61 public:
  62     FixedSortKeyByteSink(char *dest, int32_t destCapacity)
  63             : SortKeyByteSink(dest, destCapacity) {}
  64     virtual ~FixedSortKeyByteSink();
  65
  66 private:
  67     virtual void AppendBeyondCapacity(const char *bytes, int32_t n, int32_t length);
  68     virtual UBool Resize(int32_t appendCapacity, int32_t length);
  69 };
  70
  71 FixedSortKeyByteSink::~FixedSortKeyByteSink() {}
  72
  73 void
  74 FixedSortKeyByteSink::AppendBeyondCapacity(const char *bytes, int32_t /*n*/, int32_t length) {
  75     // buffer_ != NULL && bytes != NULL && n > 0 && appended_ > capacity_
  76     // Fill the buffer completely.
  77     int32_t available = capacity_ - length;
  78     if (available > 0) {
  79         uprv_memcpy(buffer_ + length, bytes, available);
  80     }
  81 }
  82
  83 UBool
  84 FixedSortKeyByteSink::Resize(int32_t /*appendCapacity*/, int32_t /*length*/) {
  85     return FALSE;
  86 }
  87
  88 }  // namespace
  89
  90 // Not in an anonymous namespace, so that it can be a friend of CollationKey.
  91 class CollationKeyByteSink : public SortKeyByteSink {
  92 public:
  93     CollationKeyByteSink(CollationKey &key)
  94             : SortKeyByteSink(reinterpret_cast<char *>(key.getBytes()), key.getCapacity()),
  95               key_(key) {}
  96     virtual ~CollationKeyByteSink();
  97
  98 private:
  99     virtual void AppendBeyondCapacity(const char *bytes, int32_t n, int32_t length);
 100     virtual UBool Resize(int32_t appendCapacity, int32_t length);
 101
 102     CollationKey &key_;
 103 };
 104
 105 CollationKeyByteSink::~CollationKeyByteSink() {}
 106
 107 void
 108 CollationKeyByteSink::AppendBeyondCapacity(const char *bytes, int32_t n, int32_t length) {
 109     // buffer_ != NULL && bytes != NULL && n > 0 && appended_ > capacity_
 110     if (Resize(n, length)) {
 111         uprv_memcpy(buffer_ + length, bytes, n);
 112     }
 113 }
 114
 115 UBool
 116 CollationKeyByteSink::Resize(int32_t appendCapacity, int32_t length) {
 117     if (buffer_ == NULL) {
 118         return FALSE;  // allocation failed before already
 119     }
 120     int32_t newCapacity = 2 * capacity_;
 121     int32_t altCapacity = length + 2 * appendCapacity;
 122     if (newCapacity < altCapacity) {
 123         newCapacity = altCapacity;
 124     }
 125     if (newCapacity < 200) {
 126         newCapacity = 200;
 127     }
 128     uint8_t *newBuffer = key_.reallocate(newCapacity, length);
 129     if (newBuffer == NULL) {
 130         SetNotOk();
 131         return FALSE;
 132     }
 133     buffer_ = reinterpret_cast<char *>(newBuffer);
 134     capacity_ = newCapacity;
 135     return TRUE;
 136 }
 137
 138 RuleBasedCollator::RuleBasedCollator(const RuleBasedCollator &other)
 139         : Collator(other),
 140           data(other.data),
 141           settings(other.settings),
 142           tailoring(other.tailoring),
 143           cacheEntry(other.cacheEntry),
 144           validLocale(other.validLocale),
 145           explicitlySetAttributes(other.explicitlySetAttributes),
 146           actualLocaleIsSameAsValid(other.actualLocaleIsSameAsValid) {
 147     settings->addRef();
 148     cacheEntry->addRef();
 149 }
 150
 151 RuleBasedCollator::RuleBasedCollator(const uint8_t *bin, int32_t length,
 152                                      const RuleBasedCollator *base, UErrorCode &errorCode)
 153         : data(NULL),
 154           settings(NULL),
 155           tailoring(NULL),
 156           cacheEntry(NULL),
 157           validLocale(""),
 158           explicitlySetAttributes(0),
 159           actualLocaleIsSameAsValid(FALSE) {
 160     if(U_FAILURE(errorCode)) { return; }
 161     if(bin == NULL || length == 0 || base == NULL) {
 162         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 163         return;
 164     }
 165     const CollationTailoring *root = CollationRoot::getRoot(errorCode);
 166     if(U_FAILURE(errorCode)) { return; }
 167     if(base->tailoring != root) {
 168         errorCode = U_UNSUPPORTED_ERROR;
 169         return;
 170     }
 171     LocalPointer<CollationTailoring> t(new CollationTailoring(base->tailoring->settings));
 172     if(t.isNull() || t->isBogus()) {
 173         errorCode = U_MEMORY_ALLOCATION_ERROR;
 174         return;
 175     }
 176     CollationDataReader::read(base->tailoring, bin, length, *t, errorCode);
 177     if(U_FAILURE(errorCode)) { return; }
 178     t->actualLocale.setToBogus();
 179     adoptTailoring(t.orphan(), errorCode);
 180 }
 181
 182 RuleBasedCollator::RuleBasedCollator(const CollationCacheEntry *entry)
 183         : data(entry->tailoring->data),
 184           settings(entry->tailoring->settings),
 185           tailoring(entry->tailoring),
 186           cacheEntry(entry),
 187           validLocale(entry->validLocale),
 188           explicitlySetAttributes(0),
 189           actualLocaleIsSameAsValid(FALSE) {
 190     settings->addRef();
 191     cacheEntry->addRef();
 192 }
 193
 194 RuleBasedCollator::~RuleBasedCollator() {
 195     SharedObject::clearPtr(settings);
 196     SharedObject::clearPtr(cacheEntry);
 197 }
 198
 199 void
 200 RuleBasedCollator::adoptTailoring(CollationTailoring *t, UErrorCode &errorCode) {
 201     if(U_FAILURE(errorCode)) {
 202         t->deleteIfZeroRefCount();
 203         return;
 204     }
 205     U_ASSERT(settings == NULL && data == NULL && tailoring == NULL && cacheEntry == NULL);
 206     cacheEntry = new CollationCacheEntry(t->actualLocale, t);
 207     if(cacheEntry == NULL) {
 208         errorCode = U_MEMORY_ALLOCATION_ERROR;
 209         t->deleteIfZeroRefCount();
 210         return;
 211     }
 212     data = t->data;
 213     settings = t->settings;
 214     settings->addRef();
 215     tailoring = t;
 216     cacheEntry->addRef();
 217     validLocale = t->actualLocale;
 218     actualLocaleIsSameAsValid = FALSE;
 219 }
 220
 221 Collator *
 222 RuleBasedCollator::clone() const {
 223     return new RuleBasedCollator(*this);
 224 }
 225
 226 RuleBasedCollator &RuleBasedCollator::operator=(const RuleBasedCollator &other) {
 227     if(this == &other) { return *this; }
 228     SharedObject::copyPtr(other.settings, settings);
 229     tailoring = other.tailoring;
 230     SharedObject::copyPtr(other.cacheEntry, cacheEntry);
 231     data = tailoring->data;
 232     validLocale = other.validLocale;
 233     explicitlySetAttributes = other.explicitlySetAttributes;
 234     actualLocaleIsSameAsValid = other.actualLocaleIsSameAsValid;
 235     return *this;
 236 }
 237
 238 UOBJECT_DEFINE_RTTI_IMPLEMENTATION(RuleBasedCollator)
 239
 240 UBool
 241 RuleBasedCollator::operator==(const Collator& other) const {
 242     if(this == &other) { return TRUE; }
 243     if(!Collator::operator==(other)) { return FALSE; }
 244     const RuleBasedCollator &o = static_cast<const RuleBasedCollator &>(other);
 245     if(*settings != *o.settings) { return FALSE; }
 246     if(data == o.data) { return TRUE; }
 247     UBool thisIsRoot = data->base == NULL;
 248     UBool otherIsRoot = o.data->base == NULL;
 249     U_ASSERT(!thisIsRoot || !otherIsRoot);  // otherwise their data pointers should be ==
 250     if(thisIsRoot != otherIsRoot) { return FALSE; }
 251     if((thisIsRoot || !tailoring->rules.isEmpty()) &&
 252             (otherIsRoot || !o.tailoring->rules.isEmpty())) {
 253         // Shortcut: If both collators have valid rule strings, then compare those.
 254         if(tailoring->rules == o.tailoring->rules) { return TRUE; }
 255     }
 256     // Different rule strings can result in the same or equivalent tailoring.
 257     // The rule strings are optional in ICU resource bundles, although included by default.
 258     // cloneBinary() drops the rule string.
 259     UErrorCode errorCode = U_ZERO_ERROR;
 260     LocalPointer<UnicodeSet> thisTailored(getTailoredSet(errorCode));
 261     LocalPointer<UnicodeSet> otherTailored(o.getTailoredSet(errorCode));
 262     if(U_FAILURE(errorCode)) { return FALSE; }
 263     if(*thisTailored != *otherTailored) { return FALSE; }
 264     // For completeness, we should compare all of the mappings;
 265     // or we should create a list of strings, sort it with one collator,
 266     // and check if both collators compare adjacent strings the same
 267     // (order & strength, down to quaternary); or similar.
 268     // Testing equality of collators seems unusual.
 269     return TRUE;
 270 }
 271
 272 int32_t
 273 RuleBasedCollator::hashCode() const {
 274     int32_t h = settings->hashCode();
 275     if(data->base == NULL) { return h; }  // root collator
 276     // Do not rely on the rule string, see comments in operator==().
 277     UErrorCode errorCode = U_ZERO_ERROR;
 278     LocalPointer<UnicodeSet> set(getTailoredSet(errorCode));
 279     if(U_FAILURE(errorCode)) { return 0; }
 280     UnicodeSetIterator iter(*set);
 281     while(iter.next() && !iter.isString()) {
 282         h ^= data->getCE32(iter.getCodepoint());
 283     }
 284     return h;
 285 }
 286
 287 void
 288 RuleBasedCollator::setLocales(const Locale &requested, const Locale &valid,
 289                               const Locale &actual) {
 290     if(actual == tailoring->actualLocale) {
 291         actualLocaleIsSameAsValid = FALSE;
 292     } else {
 293         U_ASSERT(actual == valid);
 294         actualLocaleIsSameAsValid = TRUE;
 295     }
 296     // Do not modify tailoring.actualLocale:
 297     // We cannot be sure that that would be thread-safe.
 298     validLocale = valid;
 299     (void)requested;  // Ignore, see also ticket #10477.
 300 }
 301
 302 Locale
 303 RuleBasedCollator::getLocale(ULocDataLocaleType type, UErrorCode& errorCode) const {
 304     if(U_FAILURE(errorCode)) {
 305         return Locale::getRoot();
 306     }
 307     switch(type) {
 308     case ULOC_ACTUAL_LOCALE:
 309         return actualLocaleIsSameAsValid ? validLocale : tailoring->actualLocale;
 310     case ULOC_VALID_LOCALE:
 311     case ULOC_REQUESTED_LOCALE: // Apple: keep treating as ULOC_VALID_LOCALE, apps depend on it <rdar://problem/19546211>
 312         return validLocale;
 313     default:
 314         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 315         return Locale::getRoot();
 316     }
 317 }
 318
 319 const char *
 320 RuleBasedCollator::internalGetLocaleID(ULocDataLocaleType type, UErrorCode &errorCode) const {
 321     if(U_FAILURE(errorCode)) {
 322         return NULL;
 323     }
 324     const Locale *result;
 325     switch(type) {
 326     case ULOC_ACTUAL_LOCALE:
 327         result = actualLocaleIsSameAsValid ? &validLocale : &tailoring->actualLocale;
 328         break;
 329     case ULOC_VALID_LOCALE:
 330     case ULOC_REQUESTED_LOCALE: // Apple: keep treating as ULOC_VALID_LOCALE, apps depend on it <rdar://problem/19546211>
 331         result = &validLocale;
 332         break;
 333     default:
 334         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 335         return NULL;
 336     }
 337     if(result->isBogus()) { return NULL; }
 338     const char *id = result->getName();
 339     return id[0] == 0 ? "root" : id;
 340 }
 341
 342 const UnicodeString&
 343 RuleBasedCollator::getRules() const {
 344     return tailoring->rules;
 345 }
 346
 347 void
 348 RuleBasedCollator::getRules(UColRuleOption delta, UnicodeString &buffer) const {
 349     if(delta == UCOL_TAILORING_ONLY) {
 350         buffer = tailoring->rules;
 351         return;
 352     }
 353     // UCOL_FULL_RULES
 354     buffer.remove();
 355     CollationLoader::appendRootRules(buffer);
 356     buffer.append(tailoring->rules).getTerminatedBuffer();
 357 }
 358
 359 void
 360 RuleBasedCollator::getVersion(UVersionInfo version) const {
 361     uprv_memcpy(version, tailoring->version, U_MAX_VERSION_LENGTH);
 362     version[0] += (UCOL_RUNTIME_VERSION << 4) + (UCOL_RUNTIME_VERSION >> 4);
 363 }
 364
 365 UnicodeSet *
 366 RuleBasedCollator::getTailoredSet(UErrorCode &errorCode) const {
 367     if(U_FAILURE(errorCode)) { return NULL; }
 368     UnicodeSet *tailored = new UnicodeSet();
 369     if(tailored == NULL) {
 370         errorCode = U_MEMORY_ALLOCATION_ERROR;
 371         return NULL;
 372     }
 373     if(data->base != NULL) {
 374         TailoredSet(tailored).forData(data, errorCode);
 375         if(U_FAILURE(errorCode)) {
 376             delete tailored;
 377             return NULL;
 378         }
 379     }
 380     return tailored;
 381 }
 382
 383 void
 384 RuleBasedCollator::internalGetContractionsAndExpansions(
 385         UnicodeSet *contractions, UnicodeSet *expansions,
 386         UBool addPrefixes, UErrorCode &errorCode) const {
 387     if(U_FAILURE(errorCode)) { return; }
 388     if(contractions != NULL) {
 389         contractions->clear();
 390     }
 391     if(expansions != NULL) {
 392         expansions->clear();
 393     }
 394     ContractionsAndExpansions(contractions, expansions, NULL, addPrefixes).forData(data, errorCode);
 395 }
 396
 397 void
 398 RuleBasedCollator::internalAddContractions(UChar32 c, UnicodeSet &set, UErrorCode &errorCode) const {
 399     if(U_FAILURE(errorCode)) { return; }
 400     ContractionsAndExpansions(&set, NULL, NULL, FALSE).forCodePoint(data, c, errorCode);
 401 }
 402
 403 const CollationSettings &
 404 RuleBasedCollator::getDefaultSettings() const {
 405     return *tailoring->settings;
 406 }
 407
 408 UColAttributeValue
 409 RuleBasedCollator::getAttribute(UColAttribute attr, UErrorCode &errorCode) const {
 410     if(U_FAILURE(errorCode)) { return UCOL_DEFAULT; }
 411     int32_t option;
 412     switch(attr) {
 413     case UCOL_FRENCH_COLLATION:
 414         option = CollationSettings::BACKWARD_SECONDARY;
 415         break;
 416     case UCOL_ALTERNATE_HANDLING:
 417         return settings->getAlternateHandling();
 418     case UCOL_CASE_FIRST:
 419         return settings->getCaseFirst();
 420     case UCOL_CASE_LEVEL:
 421         option = CollationSettings::CASE_LEVEL;
 422         break;
 423     case UCOL_NORMALIZATION_MODE:
 424         option = CollationSettings::CHECK_FCD;
 425         break;
 426     case UCOL_STRENGTH:
 427         return (UColAttributeValue)settings->getStrength();
 428     case UCOL_HIRAGANA_QUATERNARY_MODE:
 429         // Deprecated attribute, unsettable.
 430         return UCOL_OFF;
 431     case UCOL_NUMERIC_COLLATION:
 432         option = CollationSettings::NUMERIC;
 433         break;
 434     default:
 435         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 436         return UCOL_DEFAULT;
 437     }
 438     return ((settings->options & option) == 0) ? UCOL_OFF : UCOL_ON;
 439 }
 440
 441 void
 442 RuleBasedCollator::setAttribute(UColAttribute attr, UColAttributeValue value,
 443                                 UErrorCode &errorCode) {
 444     UColAttributeValue oldValue = getAttribute(attr, errorCode);
 445     if(U_FAILURE(errorCode)) { return; }
 446     if(value == oldValue) {
 447         setAttributeExplicitly(attr);
 448         return;
 449     }
 450     const CollationSettings &defaultSettings = getDefaultSettings();
 451     if(settings == &defaultSettings) {
 452         if(value == UCOL_DEFAULT) {
 453             setAttributeDefault(attr);
 454             return;
 455         }
 456     }
 457     CollationSettings *ownedSettings = SharedObject::copyOnWrite(settings);
 458     if(ownedSettings == NULL) {
 459         errorCode = U_MEMORY_ALLOCATION_ERROR;
 460         return;
 461     }
 462
 463     switch(attr) {
 464     case UCOL_FRENCH_COLLATION:
 465         ownedSettings->setFlag(CollationSettings::BACKWARD_SECONDARY, value,
 466                                defaultSettings.options, errorCode);
 467         break;
 468     case UCOL_ALTERNATE_HANDLING:
 469         ownedSettings->setAlternateHandling(value, defaultSettings.options, errorCode);
 470         break;
 471     case UCOL_CASE_FIRST:
 472         ownedSettings->setCaseFirst(value, defaultSettings.options, errorCode);
 473         break;
 474     case UCOL_CASE_LEVEL:
 475         ownedSettings->setFlag(CollationSettings::CASE_LEVEL, value,
 476                                defaultSettings.options, errorCode);
 477         break;
 478     case UCOL_NORMALIZATION_MODE:
 479         ownedSettings->setFlag(CollationSettings::CHECK_FCD, value,
 480                                defaultSettings.options, errorCode);
 481         break;
 482     case UCOL_STRENGTH:
 483         ownedSettings->setStrength(value, defaultSettings.options, errorCode);
 484         break;
 485     case UCOL_HIRAGANA_QUATERNARY_MODE:
 486         // Deprecated attribute. Check for valid values but do not change anything.
 487         if(value != UCOL_OFF && value != UCOL_ON && value != UCOL_DEFAULT) {
 488             errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 489         }
 490         break;
 491     case UCOL_NUMERIC_COLLATION:
 492         ownedSettings->setFlag(CollationSettings::NUMERIC, value, defaultSettings.options, errorCode);
 493         break;
 494     default:
 495         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 496         break;
 497     }
 498     if(U_FAILURE(errorCode)) { return; }
 499     setFastLatinOptions(*ownedSettings);
 500     if(value == UCOL_DEFAULT) {
 501         setAttributeDefault(attr);
 502     } else {
 503         setAttributeExplicitly(attr);
 504     }
 505 }
 506
 507 Collator &
 508 RuleBasedCollator::setMaxVariable(UColReorderCode group, UErrorCode &errorCode) {
 509     if(U_FAILURE(errorCode)) { return *this; }
 510     // Convert the reorder code into a MaxVariable number, or UCOL_DEFAULT=-1.
 511     int32_t value;
 512     if(group == UCOL_REORDER_CODE_DEFAULT) {
 513         value = UCOL_DEFAULT;
 514     } else if(UCOL_REORDER_CODE_FIRST <= group && group <= UCOL_REORDER_CODE_CURRENCY) {
 515         value = group - UCOL_REORDER_CODE_FIRST;
 516     } else {
 517         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 518         return *this;
 519     }
 520     CollationSettings::MaxVariable oldValue = settings->getMaxVariable();
 521     if(value == oldValue) {
 522         setAttributeExplicitly(ATTR_VARIABLE_TOP);
 523         return *this;
 524     }
 525     const CollationSettings &defaultSettings = getDefaultSettings();
 526     if(settings == &defaultSettings) {
 527         if(value == UCOL_DEFAULT) {
 528             setAttributeDefault(ATTR_VARIABLE_TOP);
 529             return *this;
 530         }
 531     }
 532     CollationSettings *ownedSettings = SharedObject::copyOnWrite(settings);
 533     if(ownedSettings == NULL) {
 534         errorCode = U_MEMORY_ALLOCATION_ERROR;
 535         return *this;
 536     }
 537
 538     if(group == UCOL_REORDER_CODE_DEFAULT) {
 539         group = (UColReorderCode)(UCOL_REORDER_CODE_FIRST + defaultSettings.getMaxVariable());
 540     }
 541     uint32_t varTop = data->getLastPrimaryForGroup(group);
 542     U_ASSERT(varTop != 0);
 543     ownedSettings->setMaxVariable(value, defaultSettings.options, errorCode);
 544     if(U_FAILURE(errorCode)) { return *this; }
 545     ownedSettings->variableTop = varTop;
 546     setFastLatinOptions(*ownedSettings);
 547     if(value == UCOL_DEFAULT) {
 548         setAttributeDefault(ATTR_VARIABLE_TOP);
 549     } else {
 550         setAttributeExplicitly(ATTR_VARIABLE_TOP);
 551     }
 552     return *this;
 553 }
 554
 555 UColReorderCode
 556 RuleBasedCollator::getMaxVariable() const {
 557     return (UColReorderCode)(UCOL_REORDER_CODE_FIRST + settings->getMaxVariable());
 558 }
 559
 560 uint32_t
 561 RuleBasedCollator::getVariableTop(UErrorCode & /*errorCode*/) const {
 562     return settings->variableTop;
 563 }
 564
 565 uint32_t
 566 RuleBasedCollator::setVariableTop(const UChar *varTop, int32_t len, UErrorCode &errorCode) {
 567     if(U_FAILURE(errorCode)) { return 0; }
 568     if(varTop == NULL && len !=0) {
 569         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 570         return 0;
 571     }
 572     if(len < 0) { len = u_strlen(varTop); }
 573     if(len == 0) {
 574         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 575         return 0;
 576     }
 577     UBool numeric = settings->isNumeric();
 578     int64_t ce1, ce2;
 579     if(settings->dontCheckFCD()) {
 580         UTF16CollationIterator ci(data, numeric, varTop, varTop, varTop + len);
 581         ce1 = ci.nextCE(errorCode);
 582         ce2 = ci.nextCE(errorCode);
 583     } else {
 584         FCDUTF16CollationIterator ci(data, numeric, varTop, varTop, varTop + len);
 585         ce1 = ci.nextCE(errorCode);
 586         ce2 = ci.nextCE(errorCode);
 587     }
 588     if(ce1 == Collation::NO_CE || ce2 != Collation::NO_CE) {
 589         errorCode = U_CE_NOT_FOUND_ERROR;
 590         return 0;
 591     }
 592     setVariableTop((uint32_t)(ce1 >> 32), errorCode);
 593     return settings->variableTop;
 594 }
 595
 596 uint32_t
 597 RuleBasedCollator::setVariableTop(const UnicodeString &varTop, UErrorCode &errorCode) {
 598     return setVariableTop(varTop.getBuffer(), varTop.length(), errorCode);
 599 }
 600
 601 void
 602 RuleBasedCollator::setVariableTop(uint32_t varTop, UErrorCode &errorCode) {
 603     if(U_FAILURE(errorCode)) { return; }
 604     if(varTop != settings->variableTop) {
 605         // Pin the variable top to the end of the reordering group which contains it.
 606         // Only a few special groups are supported.
 607         int32_t group = data->getGroupForPrimary(varTop);
 608         if(group < UCOL_REORDER_CODE_FIRST || UCOL_REORDER_CODE_CURRENCY < group) {
 609             errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 610             return;
 611         }
 612         uint32_t v = data->getLastPrimaryForGroup(group);
 613         U_ASSERT(v != 0 && v >= varTop);
 614         varTop = v;
 615         if(varTop != settings->variableTop) {
 616             CollationSettings *ownedSettings = SharedObject::copyOnWrite(settings);
 617             if(ownedSettings == NULL) {
 618                 errorCode = U_MEMORY_ALLOCATION_ERROR;
 619                 return;
 620             }
 621             ownedSettings->setMaxVariable(group - UCOL_REORDER_CODE_FIRST,
 622                                           getDefaultSettings().options, errorCode);
 623             if(U_FAILURE(errorCode)) { return; }
 624             ownedSettings->variableTop = varTop;
 625             setFastLatinOptions(*ownedSettings);
 626         }
 627     }
 628     if(varTop == getDefaultSettings().variableTop) {
 629         setAttributeDefault(ATTR_VARIABLE_TOP);
 630     } else {
 631         setAttributeExplicitly(ATTR_VARIABLE_TOP);
 632     }
 633 }
 634
 635 int32_t
 636 RuleBasedCollator::getReorderCodes(int32_t *dest, int32_t capacity,
 637                                    UErrorCode &errorCode) const {
 638     if(U_FAILURE(errorCode)) { return 0; }
 639     if(capacity < 0 || (dest == NULL && capacity > 0)) {
 640         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 641         return 0;
 642     }
 643     int32_t length = settings->reorderCodesLength;
 644     if(length == 0) { return 0; }
 645     if(length > capacity) {
 646         errorCode = U_BUFFER_OVERFLOW_ERROR;
 647         return length;
 648     }
 649     uprv_memcpy(dest, settings->reorderCodes, length * 4);
 650     return length;
 651 }
 652
 653 void
 654 RuleBasedCollator::setReorderCodes(const int32_t *reorderCodes, int32_t length,
 655                                    UErrorCode &errorCode) {
 656     if(U_FAILURE(errorCode)) { return; }
 657     if(length < 0 || (reorderCodes == NULL && length > 0)) {
 658         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 659         return;
 660     }
 661     if(length == 1 && reorderCodes[0] == UCOL_REORDER_CODE_NONE) {
 662         length = 0;
 663     }
 664     if(length == settings->reorderCodesLength &&
 665             uprv_memcmp(reorderCodes, settings->reorderCodes, length * 4) == 0) {
 666         return;
 667     }
 668     const CollationSettings &defaultSettings = getDefaultSettings();
 669     if(length == 1 && reorderCodes[0] == UCOL_REORDER_CODE_DEFAULT) {
 670         if(settings != &defaultSettings) {
 671             CollationSettings *ownedSettings = SharedObject::copyOnWrite(settings);
 672             if(ownedSettings == NULL) {
 673                 errorCode = U_MEMORY_ALLOCATION_ERROR;
 674                 return;
 675             }
 676             ownedSettings->copyReorderingFrom(defaultSettings, errorCode);
 677             setFastLatinOptions(*ownedSettings);
 678         }
 679         return;
 680     }
 681     CollationSettings *ownedSettings = SharedObject::copyOnWrite(settings);
 682     if(ownedSettings == NULL) {
 683         errorCode = U_MEMORY_ALLOCATION_ERROR;
 684         return;
 685     }
 686     ownedSettings->setReordering(*data, reorderCodes, length, errorCode);
 687     setFastLatinOptions(*ownedSettings);
 688 }
 689
 690 void
 691 RuleBasedCollator::setFastLatinOptions(CollationSettings &ownedSettings) const {
 692     ownedSettings.fastLatinOptions = CollationFastLatin::getOptions(
 693             data, ownedSettings,
 694             ownedSettings.fastLatinPrimaries, UPRV_LENGTHOF(ownedSettings.fastLatinPrimaries));
 695 }
 696
 697 UCollationResult
 698 RuleBasedCollator::compare(const UnicodeString &left, const UnicodeString &right,
 699                            UErrorCode &errorCode) const {
 700     if(U_FAILURE(errorCode)) { return UCOL_EQUAL; }
 701     return doCompare(left.getBuffer(), left.length(),
 702                      right.getBuffer(), right.length(), errorCode);
 703 }
 704
 705 UCollationResult
 706 RuleBasedCollator::compare(const UnicodeString &left, const UnicodeString &right,
 707                            int32_t length, UErrorCode &errorCode) const {
 708     if(U_FAILURE(errorCode) || length == 0) { return UCOL_EQUAL; }
 709     if(length < 0) {
 710         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 711         return UCOL_EQUAL;
 712     }
 713     int32_t leftLength = left.length();
 714     int32_t rightLength = right.length();
 715     if(leftLength > length) { leftLength = length; }
 716     if(rightLength > length) { rightLength = length; }
 717     return doCompare(left.getBuffer(), leftLength,
 718                      right.getBuffer(), rightLength, errorCode);
 719 }
 720
 721 UCollationResult
 722 RuleBasedCollator::compare(const UChar *left, int32_t leftLength,
 723                            const UChar *right, int32_t rightLength,
 724                            UErrorCode &errorCode) const {
 725     if(U_FAILURE(errorCode)) { return UCOL_EQUAL; }
 726     if((left == NULL && leftLength != 0) || (right == NULL && rightLength != 0)) {
 727         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 728         return UCOL_EQUAL;
 729     }
 730     // Make sure both or neither strings have a known length.
 731     // We do not optimize for mixed length/termination.
 732     if(leftLength >= 0) {
 733         if(rightLength < 0) { rightLength = u_strlen(right); }
 734     } else {
 735         if(rightLength >= 0) { leftLength = u_strlen(left); }
 736     }
 737     return doCompare(left, leftLength, right, rightLength, errorCode);
 738 }
 739
 740 UCollationResult
 741 RuleBasedCollator::compareUTF8(const StringPiece &left, const StringPiece &right,
 742                                UErrorCode &errorCode) const {
 743     if(U_FAILURE(errorCode)) { return UCOL_EQUAL; }
 744     const uint8_t *leftBytes = reinterpret_cast<const uint8_t *>(left.data());
 745     const uint8_t *rightBytes = reinterpret_cast<const uint8_t *>(right.data());
 746     if((leftBytes == NULL && !left.empty()) || (rightBytes == NULL && !right.empty())) {
 747         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 748         return UCOL_EQUAL;
 749     }
 750     return doCompare(leftBytes, left.length(), rightBytes, right.length(), errorCode);
 751 }
 752
 753 UCollationResult
 754 RuleBasedCollator::internalCompareUTF8(const char *left, int32_t leftLength,
 755                                        const char *right, int32_t rightLength,
 756                                        UErrorCode &errorCode) const {
 757     if(U_FAILURE(errorCode)) { return UCOL_EQUAL; }
 758     if((left == NULL && leftLength != 0) || (right == NULL && rightLength != 0)) {
 759         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 760         return UCOL_EQUAL;
 761     }
 762     // Make sure both or neither strings have a known length.
 763     // We do not optimize for mixed length/termination.
 764     if(leftLength >= 0) {
 765         if(rightLength < 0) { rightLength = uprv_strlen(right); }
 766     } else {
 767         if(rightLength >= 0) { leftLength = uprv_strlen(left); }
 768     }
 769     return doCompare(reinterpret_cast<const uint8_t *>(left), leftLength,
 770                      reinterpret_cast<const uint8_t *>(right), rightLength, errorCode);
 771 }
 772
 773 namespace {
 774
 775 /**
 776  * Abstract iterator for identical-level string comparisons.
 777  * Returns FCD code points and handles temporary switching to NFD.
 778  */
 779 class NFDIterator : public UObject {
 780 public:
 781     NFDIterator() : index(-1), length(0) {}
 782     virtual ~NFDIterator() {}
 783     /**
 784      * Returns the next code point from the internal normalization buffer,
 785      * or else the next text code point.
 786      * Returns -1 at the end of the text.
 787      */
 788     UChar32 nextCodePoint() {
 789         if(index >= 0) {
 790             if(index == length) {
 791                 index = -1;
 792             } else {
 793                 UChar32 c;
 794                 U16_NEXT_UNSAFE(decomp, index, c);
 795                 return c;
 796             }
 797         }
 798         return nextRawCodePoint();
 799     }
 800     /**
 801      * @param nfcImpl
 802      * @param c the last code point returned by nextCodePoint() or nextDecomposedCodePoint()
 803      * @return the first code point in c's decomposition,
 804      *         or c itself if it was decomposed already or if it does not decompose
 805      */
 806     UChar32 nextDecomposedCodePoint(const Normalizer2Impl &nfcImpl, UChar32 c) {
 807         if(index >= 0) { return c; }
 808         decomp = nfcImpl.getDecomposition(c, buffer, length);
 809         if(decomp == NULL) { return c; }
 810         index = 0;
 811         U16_NEXT_UNSAFE(decomp, index, c);
 812         return c;
 813     }
 814 protected:
 815     /**
 816      * Returns the next text code point in FCD order.
 817      * Returns -1 at the end of the text.
 818      */
 819     virtual UChar32 nextRawCodePoint() = 0;
 820 private:
 821     const UChar *decomp;
 822     UChar buffer[4];
 823     int32_t index;
 824     int32_t length;
 825 };
 826
 827 class UTF16NFDIterator : public NFDIterator {
 828 public:
 829     UTF16NFDIterator(const UChar *text, const UChar *textLimit) : s(text), limit(textLimit) {}
 830 protected:
 831     virtual UChar32 nextRawCodePoint() {
 832         if(s == limit) { return U_SENTINEL; }
 833         UChar32 c = *s++;
 834         if(limit == NULL && c == 0) {
 835             s = NULL;
 836             return U_SENTINEL;
 837         }
 838         UChar trail;
 839         if(U16_IS_LEAD(c) && s != limit && U16_IS_TRAIL(trail = *s)) {
 840             ++s;
 841             c = U16_GET_SUPPLEMENTARY(c, trail);
 842         }
 843         return c;
 844     }
 845
 846     const UChar *s;
 847     const UChar *limit;
 848 };
 849
 850 class FCDUTF16NFDIterator : public UTF16NFDIterator {
 851 public:
 852     FCDUTF16NFDIterator(const Normalizer2Impl &nfcImpl, const UChar *text, const UChar *textLimit)
 853             : UTF16NFDIterator(NULL, NULL) {
 854         UErrorCode errorCode = U_ZERO_ERROR;
 855         const UChar *spanLimit = nfcImpl.makeFCD(text, textLimit, NULL, errorCode);
 856         if(U_FAILURE(errorCode)) { return; }
 857         if(spanLimit == textLimit || (textLimit == NULL && *spanLimit == 0)) {
 858             s = text;
 859             limit = spanLimit;
 860         } else {
 861             str.setTo(text, (int32_t)(spanLimit - text));
 862             {
 863                 ReorderingBuffer buffer(nfcImpl, str);
 864                 if(buffer.init(str.length(), errorCode)) {
 865                     nfcImpl.makeFCD(spanLimit, textLimit, &buffer, errorCode);
 866                 }
 867             }
 868             if(U_SUCCESS(errorCode)) {
 869                 s = str.getBuffer();
 870                 limit = s + str.length();
 871             }
 872         }
 873     }
 874 private:
 875     UnicodeString str;
 876 };
 877
 878 class UTF8NFDIterator : public NFDIterator {
 879 public:
 880     UTF8NFDIterator(const uint8_t *text, int32_t textLength)
 881         : s(text), pos(0), length(textLength) {}
 882 protected:
 883     virtual UChar32 nextRawCodePoint() {
 884         if(pos == length || (s[pos] == 0 && length < 0)) { return U_SENTINEL; }
 885         UChar32 c;
 886         U8_NEXT_OR_FFFD(s, pos, length, c);
 887         return c;
 888     }
 889
 890     const uint8_t *s;
 891     int32_t pos;
 892     int32_t length;
 893 };
 894
 895 class FCDUTF8NFDIterator : public NFDIterator {
 896 public:
 897     FCDUTF8NFDIterator(const CollationData *data, const uint8_t *text, int32_t textLength)
 898             : u8ci(data, FALSE, text, 0, textLength) {}
 899 protected:
 900     virtual UChar32 nextRawCodePoint() {
 901         UErrorCode errorCode = U_ZERO_ERROR;
 902         return u8ci.nextCodePoint(errorCode);
 903     }
 904 private:
 905     FCDUTF8CollationIterator u8ci;
 906 };
 907
 908 class UIterNFDIterator : public NFDIterator {
 909 public:
 910     UIterNFDIterator(UCharIterator &it) : iter(it) {}
 911 protected:
 912     virtual UChar32 nextRawCodePoint() {
 913         return uiter_next32(&iter);
 914     }
 915 private:
 916     UCharIterator &iter;
 917 };
 918
 919 class FCDUIterNFDIterator : public NFDIterator {
 920 public:
 921     FCDUIterNFDIterator(const CollationData *data, UCharIterator &it, int32_t startIndex)
 922             : uici(data, FALSE, it, startIndex) {}
 923 protected:
 924     virtual UChar32 nextRawCodePoint() {
 925         UErrorCode errorCode = U_ZERO_ERROR;
 926         return uici.nextCodePoint(errorCode);
 927     }
 928 private:
 929     FCDUIterCollationIterator uici;
 930 };
 931
 932 UCollationResult compareNFDIter(const Normalizer2Impl &nfcImpl,
 933                                 NFDIterator &left, NFDIterator &right) {
 934     for(;;) {
 935         // Fetch the next FCD code point from each string.
 936         UChar32 leftCp = left.nextCodePoint();
 937         UChar32 rightCp = right.nextCodePoint();
 938         if(leftCp == rightCp) {
 939             if(leftCp < 0) { break; }
 940             continue;
 941         }
 942         // If they are different, then decompose each and compare again.
 943         if(leftCp < 0) {
 944             leftCp = -2;  // end of string
 945         } else if(leftCp == 0xfffe) {
 946             leftCp = -1;  // U+FFFE: merge separator
 947         } else {
 948             leftCp = left.nextDecomposedCodePoint(nfcImpl, leftCp);
 949         }
 950         if(rightCp < 0) {
 951             rightCp = -2;  // end of string
 952         } else if(rightCp == 0xfffe) {
 953             rightCp = -1;  // U+FFFE: merge separator
 954         } else {
 955             rightCp = right.nextDecomposedCodePoint(nfcImpl, rightCp);
 956         }
 957         if(leftCp < rightCp) { return UCOL_LESS; }
 958         if(leftCp > rightCp) { return UCOL_GREATER; }
 959     }
 960     return UCOL_EQUAL;
 961 }
 962
 963 }  // namespace
 964
 965 UCollationResult
 966 RuleBasedCollator::doCompare(const UChar *left, int32_t leftLength,
 967                              const UChar *right, int32_t rightLength,
 968                              UErrorCode &errorCode) const {
 969     // U_FAILURE(errorCode) checked by caller.
 970     if(left == right && leftLength == rightLength) {
 971         return UCOL_EQUAL;
 972     }
 973
 974     // Identical-prefix test.
 975     const UChar *leftLimit;
 976     const UChar *rightLimit;
 977     int32_t equalPrefixLength = 0;
 978     if(leftLength < 0) {
 979         leftLimit = NULL;
 980         rightLimit = NULL;
 981         UChar c;
 982         while((c = left[equalPrefixLength]) == right[equalPrefixLength]) {
 983             if(c == 0) { return UCOL_EQUAL; }
 984             ++equalPrefixLength;
 985         }
 986     } else {
 987         leftLimit = left + leftLength;
 988         rightLimit = right + rightLength;
 989         for(;;) {
 990             if(equalPrefixLength == leftLength) {
 991                 if(equalPrefixLength == rightLength) { return UCOL_EQUAL; }
 992                 break;
 993             } else if(equalPrefixLength == rightLength ||
 994                       left[equalPrefixLength] != right[equalPrefixLength]) {
 995                 break;
 996             }
 997             ++equalPrefixLength;
 998         }
 999     }
1000
1001     UBool numeric = settings->isNumeric();
1002     if(equalPrefixLength > 0) {
1003         if((equalPrefixLength != leftLength &&
1004                     data->isUnsafeBackward(left[equalPrefixLength], numeric)) ||
1005                 (equalPrefixLength != rightLength &&
1006                     data->isUnsafeBackward(right[equalPrefixLength], numeric))) {
1007             // Identical prefix: Back up to the start of a contraction or reordering sequence.
1008             while(--equalPrefixLength > 0 &&
1009                     data->isUnsafeBackward(left[equalPrefixLength], numeric)) {}
1010         }
1011         // Notes:
1012         // - A longer string can compare equal to a prefix of it if only ignorables follow.
1013         // - With a backward level, a longer string can compare less-than a prefix of it.
1014
1015         // Pass the actual start of each string into the CollationIterators,
1016         // plus the equalPrefixLength position,
1017         // so that prefix matches back into the equal prefix work.
1018     }
1019
1020     int32_t result;
1021     int32_t fastLatinOptions = settings->fastLatinOptions;
1022     if(fastLatinOptions >= 0 &&
1023             (equalPrefixLength == leftLength ||
1024                 left[equalPrefixLength] <= CollationFastLatin::LATIN_MAX) &&
1025             (equalPrefixLength == rightLength ||
1026                 right[equalPrefixLength] <= CollationFastLatin::LATIN_MAX)) {
1027         if(leftLength >= 0) {
1028             result = CollationFastLatin::compareUTF16(data->fastLatinTable,
1029                                                       settings->fastLatinPrimaries,
1030                                                       fastLatinOptions,
1031                                                       left + equalPrefixLength,
1032                                                       leftLength - equalPrefixLength,
1033                                                       right + equalPrefixLength,
1034                                                       rightLength - equalPrefixLength);
1035         } else {
1036             result = CollationFastLatin::compareUTF16(data->fastLatinTable,
1037                                                       settings->fastLatinPrimaries,
1038                                                       fastLatinOptions,
1039                                                       left + equalPrefixLength, -1,
1040                                                       right + equalPrefixLength, -1);
1041         }
1042     } else {
1043         result = CollationFastLatin::BAIL_OUT_RESULT;
1044     }
1045
1046     if(result == CollationFastLatin::BAIL_OUT_RESULT) {
1047         if(settings->dontCheckFCD()) {
1048             UTF16CollationIterator leftIter(data, numeric,
1049                                             left, left + equalPrefixLength, leftLimit);
1050             UTF16CollationIterator rightIter(data, numeric,
1051                                             right, right + equalPrefixLength, rightLimit);
1052             result = CollationCompare::compareUpToQuaternary(leftIter, rightIter, *settings, errorCode);
1053         } else {
1054             FCDUTF16CollationIterator leftIter(data, numeric,
1055                                               left, left + equalPrefixLength, leftLimit);
1056             FCDUTF16CollationIterator rightIter(data, numeric,
1057                                                 right, right + equalPrefixLength, rightLimit);
1058             result = CollationCompare::compareUpToQuaternary(leftIter, rightIter, *settings, errorCode);
1059         }
1060     }
1061     if(result != UCOL_EQUAL || settings->getStrength() < UCOL_IDENTICAL || U_FAILURE(errorCode)) {
1062         return (UCollationResult)result;
1063     }
1064
1065     // Note: If NUL-terminated, we could get the actual limits from the iterators now.
1066     // That would complicate the iterators a bit, NUL-terminated strings are only a C convenience,
1067     // and the benefit seems unlikely to be measurable.
1068
1069     // Compare identical level.
1070     const Normalizer2Impl &nfcImpl = data->nfcImpl;
1071     left += equalPrefixLength;
1072     right += equalPrefixLength;
1073     if(settings->dontCheckFCD()) {
1074         UTF16NFDIterator leftIter(left, leftLimit);
1075         UTF16NFDIterator rightIter(right, rightLimit);
1076         return compareNFDIter(nfcImpl, leftIter, rightIter);
1077     } else {
1078         FCDUTF16NFDIterator leftIter(nfcImpl, left, leftLimit);
1079         FCDUTF16NFDIterator rightIter(nfcImpl, right, rightLimit);
1080         return compareNFDIter(nfcImpl, leftIter, rightIter);
1081     }
1082 }
1083
1084 UCollationResult
1085 RuleBasedCollator::doCompare(const uint8_t *left, int32_t leftLength,
1086                              const uint8_t *right, int32_t rightLength,
1087                              UErrorCode &errorCode) const {
1088     // U_FAILURE(errorCode) checked by caller.
1089     if(left == right && leftLength == rightLength) {
1090         return UCOL_EQUAL;
1091     }
1092
1093     // Identical-prefix test.
1094     int32_t equalPrefixLength = 0;
1095     if(leftLength < 0) {
1096         uint8_t c;
1097         while((c = left[equalPrefixLength]) == right[equalPrefixLength]) {
1098             if(c == 0) { return UCOL_EQUAL; }
1099             ++equalPrefixLength;
1100         }
1101     } else {
1102         for(;;) {
1103             if(equalPrefixLength == leftLength) {
1104                 if(equalPrefixLength == rightLength) { return UCOL_EQUAL; }
1105                 break;
1106             } else if(equalPrefixLength == rightLength ||
1107                       left[equalPrefixLength] != right[equalPrefixLength]) {
1108                 break;
1109             }
1110             ++equalPrefixLength;
1111         }
1112     }
1113     // Back up to the start of a partially-equal code point.
1114     if(equalPrefixLength > 0 &&
1115             ((equalPrefixLength != leftLength && U8_IS_TRAIL(left[equalPrefixLength])) ||
1116             (equalPrefixLength != rightLength && U8_IS_TRAIL(right[equalPrefixLength])))) {
1117         while(--equalPrefixLength > 0 && U8_IS_TRAIL(left[equalPrefixLength])) {}
1118     }
1119
1120     UBool numeric = settings->isNumeric();
1121     if(equalPrefixLength > 0) {
1122         UBool unsafe = FALSE;
1123         if(equalPrefixLength != leftLength) {
1124             int32_t i = equalPrefixLength;
1125             UChar32 c;
1126             U8_NEXT_OR_FFFD(left, i, leftLength, c);
1127             unsafe = data->isUnsafeBackward(c, numeric);
1128         }
1129         if(!unsafe && equalPrefixLength != rightLength) {
1130             int32_t i = equalPrefixLength;
1131             UChar32 c;
1132             U8_NEXT_OR_FFFD(right, i, rightLength, c);
1133             unsafe = data->isUnsafeBackward(c, numeric);
1134         }
1135         if(unsafe) {
1136             // Identical prefix: Back up to the start of a contraction or reordering sequence.
1137             UChar32 c;
1138             do {
1139                 U8_PREV_OR_FFFD(left, 0, equalPrefixLength, c);
1140             } while(equalPrefixLength > 0 && data->isUnsafeBackward(c, numeric));
1141         }
1142         // See the notes in the UTF-16 version.
1143
1144         // Pass the actual start of each string into the CollationIterators,
1145         // plus the equalPrefixLength position,
1146         // so that prefix matches back into the equal prefix work.
1147     }
1148
1149     int32_t result;
1150     int32_t fastLatinOptions = settings->fastLatinOptions;
1151     if(fastLatinOptions >= 0 &&
1152             (equalPrefixLength == leftLength ||
1153                 left[equalPrefixLength] <= CollationFastLatin::LATIN_MAX_UTF8_LEAD) &&
1154             (equalPrefixLength == rightLength ||
1155                 right[equalPrefixLength] <= CollationFastLatin::LATIN_MAX_UTF8_LEAD)) {
1156         if(leftLength >= 0) {
1157             result = CollationFastLatin::compareUTF8(data->fastLatinTable,
1158                                                      settings->fastLatinPrimaries,
1159                                                      fastLatinOptions,
1160                                                      left + equalPrefixLength,
1161                                                      leftLength - equalPrefixLength,
1162                                                      right + equalPrefixLength,
1163                                                      rightLength - equalPrefixLength);
1164         } else {
1165             result = CollationFastLatin::compareUTF8(data->fastLatinTable,
1166                                                      settings->fastLatinPrimaries,
1167                                                      fastLatinOptions,
1168                                                      left + equalPrefixLength, -1,
1169                                                      right + equalPrefixLength, -1);
1170         }
1171     } else {
1172         result = CollationFastLatin::BAIL_OUT_RESULT;
1173     }
1174
1175     if(result == CollationFastLatin::BAIL_OUT_RESULT) {
1176         if(settings->dontCheckFCD()) {
1177             UTF8CollationIterator leftIter(data, numeric, left, equalPrefixLength, leftLength);
1178             UTF8CollationIterator rightIter(data, numeric, right, equalPrefixLength, rightLength);
1179             result = CollationCompare::compareUpToQuaternary(leftIter, rightIter, *settings, errorCode);
1180         } else {
1181             FCDUTF8CollationIterator leftIter(data, numeric, left, equalPrefixLength, leftLength);
1182             FCDUTF8CollationIterator rightIter(data, numeric, right, equalPrefixLength, rightLength);
1183             result = CollationCompare::compareUpToQuaternary(leftIter, rightIter, *settings, errorCode);
1184         }
1185     }
1186     if(result != UCOL_EQUAL || settings->getStrength() < UCOL_IDENTICAL || U_FAILURE(errorCode)) {
1187         return (UCollationResult)result;
1188     }
1189
1190     // Note: If NUL-terminated, we could get the actual limits from the iterators now.
1191     // That would complicate the iterators a bit, NUL-terminated strings are only a C convenience,
1192     // and the benefit seems unlikely to be measurable.
1193
1194     // Compare identical level.
1195     const Normalizer2Impl &nfcImpl = data->nfcImpl;
1196     left += equalPrefixLength;
1197     right += equalPrefixLength;
1198     if(leftLength > 0) {
1199         leftLength -= equalPrefixLength;
1200         rightLength -= equalPrefixLength;
1201     }
1202     if(settings->dontCheckFCD()) {
1203         UTF8NFDIterator leftIter(left, leftLength);
1204         UTF8NFDIterator rightIter(right, rightLength);
1205         return compareNFDIter(nfcImpl, leftIter, rightIter);
1206     } else {
1207         FCDUTF8NFDIterator leftIter(data, left, leftLength);
1208         FCDUTF8NFDIterator rightIter(data, right, rightLength);
1209         return compareNFDIter(nfcImpl, leftIter, rightIter);
1210     }
1211 }
1212
1213 UCollationResult
1214 RuleBasedCollator::compare(UCharIterator &left, UCharIterator &right,
1215                            UErrorCode &errorCode) const {
1216     if(U_FAILURE(errorCode) || &left == &right) { return UCOL_EQUAL; }
1217     UBool numeric = settings->isNumeric();
1218
1219     // Identical-prefix test.
1220     int32_t equalPrefixLength = 0;
1221     {
1222         UChar32 leftUnit;
1223         UChar32 rightUnit;
1224         while((leftUnit = left.next(&left)) == (rightUnit = right.next(&right))) {
1225             if(leftUnit < 0) { return UCOL_EQUAL; }
1226             ++equalPrefixLength;
1227         }
1228
1229         // Back out the code units that differed, for the real collation comparison.
1230         if(leftUnit >= 0) { left.previous(&left); }
1231         if(rightUnit >= 0) { right.previous(&right); }
1232
1233         if(equalPrefixLength > 0) {
1234             if((leftUnit >= 0 && data->isUnsafeBackward(leftUnit, numeric)) ||
1235                     (rightUnit >= 0 && data->isUnsafeBackward(rightUnit, numeric))) {
1236                 // Identical prefix: Back up to the start of a contraction or reordering sequence.
1237                 do {
1238                     --equalPrefixLength;
1239                     leftUnit = left.previous(&left);
1240                     right.previous(&right);
1241                 } while(equalPrefixLength > 0 && data->isUnsafeBackward(leftUnit, numeric));
1242             }
1243             // See the notes in the UTF-16 version.
1244         }
1245     }
1246
1247     UCollationResult result;
1248     if(settings->dontCheckFCD()) {
1249         UIterCollationIterator leftIter(data, numeric, left);
1250         UIterCollationIterator rightIter(data, numeric, right);
1251         result = CollationCompare::compareUpToQuaternary(leftIter, rightIter, *settings, errorCode);
1252     } else {
1253         FCDUIterCollationIterator leftIter(data, numeric, left, equalPrefixLength);
1254         FCDUIterCollationIterator rightIter(data, numeric, right, equalPrefixLength);
1255         result = CollationCompare::compareUpToQuaternary(leftIter, rightIter, *settings, errorCode);
1256     }
1257     if(result != UCOL_EQUAL || settings->getStrength() < UCOL_IDENTICAL || U_FAILURE(errorCode)) {
1258         return result;
1259     }
1260
1261     // Compare identical level.
1262     left.move(&left, equalPrefixLength, UITER_ZERO);
1263     right.move(&right, equalPrefixLength, UITER_ZERO);
1264     const Normalizer2Impl &nfcImpl = data->nfcImpl;
1265     if(settings->dontCheckFCD()) {
1266         UIterNFDIterator leftIter(left);
1267         UIterNFDIterator rightIter(right);
1268         return compareNFDIter(nfcImpl, leftIter, rightIter);
1269     } else {
1270         FCDUIterNFDIterator leftIter(data, left, equalPrefixLength);
1271         FCDUIterNFDIterator rightIter(data, right, equalPrefixLength);
1272         return compareNFDIter(nfcImpl, leftIter, rightIter);
1273     }
1274 }
1275
1276 CollationKey &
1277 RuleBasedCollator::getCollationKey(const UnicodeString &s, CollationKey &key,
1278                                    UErrorCode &errorCode) const {
1279     return getCollationKey(s.getBuffer(), s.length(), key, errorCode);
1280 }
1281
1282 CollationKey &
1283 RuleBasedCollator::getCollationKey(const UChar *s, int32_t length, CollationKey& key,
1284                                    UErrorCode &errorCode) const {
1285     if(U_FAILURE(errorCode)) {
1286         return key.setToBogus();
1287     }
1288     if(s == NULL && length != 0) {
1289         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
1290         return key.setToBogus();
1291     }
1292     key.reset();  // resets the "bogus" state
1293     CollationKeyByteSink sink(key);
1294     writeSortKey(s, length, sink, errorCode);
1295     if(U_FAILURE(errorCode)) {
1296         key.setToBogus();
1297     } else if(key.isBogus()) {
1298         errorCode = U_MEMORY_ALLOCATION_ERROR;
1299     } else {
1300         key.setLength(sink.NumberOfBytesAppended());
1301     }
1302     return key;
1303 }
1304
1305 int32_t
1306 RuleBasedCollator::getSortKey(const UnicodeString &s,
1307                               uint8_t *dest, int32_t capacity) const {
1308     return getSortKey(s.getBuffer(), s.length(), dest, capacity);
1309 }
1310
1311 int32_t
1312 RuleBasedCollator::getSortKey(const UChar *s, int32_t length,
1313                               uint8_t *dest, int32_t capacity) const {
1314     if((s == NULL && length != 0) || capacity < 0 || (dest == NULL && capacity > 0)) {
1315         return 0;
1316     }
1317     uint8_t noDest[1] = { 0 };
1318     if(dest == NULL) {
1319         // Distinguish pure preflighting from an allocation error.
1320         dest = noDest;
1321         capacity = 0;
1322     }
1323     FixedSortKeyByteSink sink(reinterpret_cast<char *>(dest), capacity);
1324     UErrorCode errorCode = U_ZERO_ERROR;
1325     writeSortKey(s, length, sink, errorCode);
1326     return U_SUCCESS(errorCode) ? sink.NumberOfBytesAppended() : 0;
1327 }
1328
1329 void
1330 RuleBasedCollator::writeSortKey(const UChar *s, int32_t length,
1331                                 SortKeyByteSink &sink, UErrorCode &errorCode) const {
1332     if(U_FAILURE(errorCode)) { return; }
1333     const UChar *limit = (length >= 0) ? s + length : NULL;
1334     UBool numeric = settings->isNumeric();
1335     CollationKeys::LevelCallback callback;
1336     if(settings->dontCheckFCD()) {
1337         UTF16CollationIterator iter(data, numeric, s, s, limit);
1338         CollationKeys::writeSortKeyUpToQuaternary(iter, data->compressibleBytes, *settings,
1339                                                   sink, Collation::PRIMARY_LEVEL,
1340                                                   callback, TRUE, errorCode);
1341     } else {
1342         FCDUTF16CollationIterator iter(data, numeric, s, s, limit);
1343         CollationKeys::writeSortKeyUpToQuaternary(iter, data->compressibleBytes, *settings,
1344                                                   sink, Collation::PRIMARY_LEVEL,
1345                                                   callback, TRUE, errorCode);
1346     }
1347     if(settings->getStrength() == UCOL_IDENTICAL) {
1348         writeIdenticalLevel(s, limit, sink, errorCode);
1349     }
1350     static const char terminator = 0;  // TERMINATOR_BYTE
1351     sink.Append(&terminator, 1);
1352 }
1353
1354 void
1355 RuleBasedCollator::writeIdenticalLevel(const UChar *s, const UChar *limit,
1356                                        SortKeyByteSink &sink, UErrorCode &errorCode) const {
1357     // NFD quick check
1358     const UChar *nfdQCYesLimit = data->nfcImpl.decompose(s, limit, NULL, errorCode);
1359     if(U_FAILURE(errorCode)) { return; }
1360     sink.Append(Collation::LEVEL_SEPARATOR_BYTE);
1361     UChar32 prev = 0;
1362     if(nfdQCYesLimit != s) {
1363         prev = u_writeIdenticalLevelRun(prev, s, (int32_t)(nfdQCYesLimit - s), sink);
1364     }
1365     // Is there non-NFD text?
1366     int32_t destLengthEstimate;
1367     if(limit != NULL) {
1368         if(nfdQCYesLimit == limit) { return; }
1369         destLengthEstimate = (int32_t)(limit - nfdQCYesLimit);
1370     } else {
1371         // s is NUL-terminated
1372         if(*nfdQCYesLimit == 0) { return; }
1373         destLengthEstimate = -1;
1374     }
1375     UnicodeString nfd;
1376     data->nfcImpl.decompose(nfdQCYesLimit, limit, nfd, destLengthEstimate, errorCode);
1377     u_writeIdenticalLevelRun(prev, nfd.getBuffer(), nfd.length(), sink);
1378 }
1379
1380 namespace {
1381
1382 /**
1383  * internalNextSortKeyPart() calls CollationKeys::writeSortKeyUpToQuaternary()
1384  * with an instance of this callback class.
1385  * When another level is about to be written, the callback
1386  * records the level and the number of bytes that will be written until
1387  * the sink (which is actually a FixedSortKeyByteSink) fills up.
1388  *
1389  * When internalNextSortKeyPart() is called again, it restarts with the last level
1390  * and ignores as many bytes as were written previously for that level.
1391  */
1392 class PartLevelCallback : public CollationKeys::LevelCallback {
1393 public:
1394     PartLevelCallback(const SortKeyByteSink &s)
1395             : sink(s), level(Collation::PRIMARY_LEVEL) {
1396         levelCapacity = sink.GetRemainingCapacity();
1397     }
1398     virtual ~PartLevelCallback() {}
1399     virtual UBool needToWrite(Collation::Level l) {
1400         if(!sink.Overflowed()) {
1401             // Remember a level that will be at least partially written.
1402             level = l;
1403             levelCapacity = sink.GetRemainingCapacity();
1404             return TRUE;
1405         } else {
1406             return FALSE;
1407         }
1408     }
1409     Collation::Level getLevel() const { return level; }
1410     int32_t getLevelCapacity() const { return levelCapacity; }
1411
1412 private:
1413     const SortKeyByteSink &sink;
1414     Collation::Level level;
1415     int32_t levelCapacity;
1416 };
1417
1418 }  // namespace
1419
1420 int32_t
1421 RuleBasedCollator::internalNextSortKeyPart(UCharIterator *iter, uint32_t state[2],
1422                                            uint8_t *dest, int32_t count, UErrorCode &errorCode) const {
1423     if(U_FAILURE(errorCode)) { return 0; }
1424     if(iter == NULL || state == NULL || count < 0 || (count > 0 && dest == NULL)) {
1425         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
1426         return 0;
1427     }
1428     if(count == 0) { return 0; }
1429
1430     FixedSortKeyByteSink sink(reinterpret_cast<char *>(dest), count);
1431     sink.IgnoreBytes((int32_t)state[1]);
1432     iter->move(iter, 0, UITER_START);
1433
1434     Collation::Level level = (Collation::Level)state[0];
1435     if(level <= Collation::QUATERNARY_LEVEL) {
1436         UBool numeric = settings->isNumeric();
1437         PartLevelCallback callback(sink);
1438         if(settings->dontCheckFCD()) {
1439             UIterCollationIterator ci(data, numeric, *iter);
1440             CollationKeys::writeSortKeyUpToQuaternary(ci, data->compressibleBytes, *settings,
1441                                                       sink, level, callback, FALSE, errorCode);
1442         } else {
1443             FCDUIterCollationIterator ci(data, numeric, *iter, 0);
1444             CollationKeys::writeSortKeyUpToQuaternary(ci, data->compressibleBytes, *settings,
1445                                                       sink, level, callback, FALSE, errorCode);
1446         }
1447         if(U_FAILURE(errorCode)) { return 0; }
1448         if(sink.NumberOfBytesAppended() > count) {
1449             state[0] = (uint32_t)callback.getLevel();
1450             state[1] = (uint32_t)callback.getLevelCapacity();
1451             return count;
1452         }
1453         // All of the normal levels are done.
1454         if(settings->getStrength() == UCOL_IDENTICAL) {
1455             level = Collation::IDENTICAL_LEVEL;
1456             iter->move(iter, 0, UITER_START);
1457         }
1458         // else fall through to setting ZERO_LEVEL
1459     }
1460
1461     if(level == Collation::IDENTICAL_LEVEL) {
1462         int32_t levelCapacity = sink.GetRemainingCapacity();
1463         UnicodeString s;
1464         for(;;) {
1465             UChar32 c = iter->next(iter);
1466             if(c < 0) { break; }
1467             s.append((UChar)c);
1468         }
1469         const UChar *sArray = s.getBuffer();
1470         writeIdenticalLevel(sArray, sArray + s.length(), sink, errorCode);
1471         if(U_FAILURE(errorCode)) { return 0; }
1472         if(sink.NumberOfBytesAppended() > count) {
1473             state[0] = (uint32_t)level;
1474             state[1] = (uint32_t)levelCapacity;
1475             return count;
1476         }
1477     }
1478
1479     // ZERO_LEVEL: Fill the remainder of dest with 00 bytes.
1480     state[0] = (uint32_t)Collation::ZERO_LEVEL;
1481     state[1] = 0;
1482     int32_t length = sink.NumberOfBytesAppended();
1483     int32_t i = length;
1484     while(i < count) { dest[i++] = 0; }
1485     return length;
1486 }
1487
1488 void
1489 RuleBasedCollator::internalGetCEs(const UnicodeString &str, UVector64 &ces,
1490                                   UErrorCode &errorCode) const {
1491     if(U_FAILURE(errorCode)) { return; }
1492     const UChar *s = str.getBuffer();
1493     const UChar *limit = s + str.length();
1494     UBool numeric = settings->isNumeric();
1495     if(settings->dontCheckFCD()) {
1496         UTF16CollationIterator iter(data, numeric, s, s, limit);
1497         int64_t ce;
1498         while((ce = iter.nextCE(errorCode)) != Collation::NO_CE) {
1499             ces.addElement(ce, errorCode);
1500         }
1501     } else {
1502         FCDUTF16CollationIterator iter(data, numeric, s, s, limit);
1503         int64_t ce;
1504         while((ce = iter.nextCE(errorCode)) != Collation::NO_CE) {
1505             ces.addElement(ce, errorCode);
1506         }
1507     }
1508 }
1509
1510 namespace {
1511
1512 void appendSubtag(CharString &s, char letter, const char *subtag, int32_t length,
1513                   UErrorCode &errorCode) {
1514     if(U_FAILURE(errorCode) || length == 0) { return; }
1515     if(!s.isEmpty()) {
1516         s.append('_', errorCode);
1517     }
1518     s.append(letter, errorCode);
1519     for(int32_t i = 0; i < length; ++i) {
1520         s.append(uprv_toupper(subtag[i]), errorCode);
1521     }
1522 }
1523
1524 void appendAttribute(CharString &s, char letter, UColAttributeValue value,
1525                      UErrorCode &errorCode) {
1526     if(U_FAILURE(errorCode)) { return; }
1527     if(!s.isEmpty()) {
1528         s.append('_', errorCode);
1529     }
1530     static const char *valueChars = "1234...........IXO..SN..LU......";
1531     s.append(letter, errorCode);
1532     s.append(valueChars[value], errorCode);
1533 }
1534
1535 }  // namespace
1536
1537 int32_t
1538 RuleBasedCollator::internalGetShortDefinitionString(const char *locale,
1539                                                     char *buffer, int32_t capacity,
1540                                                     UErrorCode &errorCode) const {
1541     if(U_FAILURE(errorCode)) { return 0; }
1542     if(buffer == NULL ? capacity != 0 : capacity < 0) {
1543         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
1544         return 0;
1545     }
1546     if(locale == NULL) {
1547         locale = internalGetLocaleID(ULOC_VALID_LOCALE, errorCode);
1548     }
1549
1550     char resultLocale[ULOC_FULLNAME_CAPACITY + 1];
1551     int32_t length = ucol_getFunctionalEquivalent(resultLocale, ULOC_FULLNAME_CAPACITY,
1552                                                   "collation", locale,
1553                                                   NULL, &errorCode);
1554     if(U_FAILURE(errorCode)) { return 0; }
1555     if(length == 0) {
1556         uprv_strcpy(resultLocale, "root");
1557     } else {
1558         resultLocale[length] = 0;
1559     }
1560
1561     // Append items in alphabetic order of their short definition letters.
1562     CharString result;
1563     char subtag[ULOC_KEYWORD_AND_VALUES_CAPACITY];
1564
1565     if(attributeHasBeenSetExplicitly(UCOL_ALTERNATE_HANDLING)) {
1566         appendAttribute(result, 'A', getAttribute(UCOL_ALTERNATE_HANDLING, errorCode), errorCode);
1567     }
1568     // ATTR_VARIABLE_TOP not supported because 'B' was broken.
1569     // See ICU tickets #10372 and #10386.
1570     if(attributeHasBeenSetExplicitly(UCOL_CASE_FIRST)) {
1571         appendAttribute(result, 'C', getAttribute(UCOL_CASE_FIRST, errorCode), errorCode);
1572     }
1573     if(attributeHasBeenSetExplicitly(UCOL_NUMERIC_COLLATION)) {
1574         appendAttribute(result, 'D', getAttribute(UCOL_NUMERIC_COLLATION, errorCode), errorCode);
1575     }
1576     if(attributeHasBeenSetExplicitly(UCOL_CASE_LEVEL)) {
1577         appendAttribute(result, 'E', getAttribute(UCOL_CASE_LEVEL, errorCode), errorCode);
1578     }
1579     if(attributeHasBeenSetExplicitly(UCOL_FRENCH_COLLATION)) {
1580         appendAttribute(result, 'F', getAttribute(UCOL_FRENCH_COLLATION, errorCode), errorCode);
1581     }
1582     // Note: UCOL_HIRAGANA_QUATERNARY_MODE is deprecated and never changes away from default.
1583     length = uloc_getKeywordValue(resultLocale, "collation", subtag, UPRV_LENGTHOF(subtag), &errorCode);
1584     appendSubtag(result, 'K', subtag, length, errorCode);
1585     length = uloc_getLanguage(resultLocale, subtag, UPRV_LENGTHOF(subtag), &errorCode);
1586     appendSubtag(result, 'L', subtag, length, errorCode);
1587     if(attributeHasBeenSetExplicitly(UCOL_NORMALIZATION_MODE)) {
1588         appendAttribute(result, 'N', getAttribute(UCOL_NORMALIZATION_MODE, errorCode), errorCode);
1589     }
1590     length = uloc_getCountry(resultLocale, subtag, UPRV_LENGTHOF(subtag), &errorCode);
1591     appendSubtag(result, 'R', subtag, length, errorCode);
1592     if(attributeHasBeenSetExplicitly(UCOL_STRENGTH)) {
1593         appendAttribute(result, 'S', getAttribute(UCOL_STRENGTH, errorCode), errorCode);
1594     }
1595     length = uloc_getVariant(resultLocale, subtag, UPRV_LENGTHOF(subtag), &errorCode);
1596     appendSubtag(result, 'V', subtag, length, errorCode);
1597     length = uloc_getScript(resultLocale, subtag, UPRV_LENGTHOF(subtag), &errorCode);
1598     appendSubtag(result, 'Z', subtag, length, errorCode);
1599
1600     if(U_FAILURE(errorCode)) { return 0; }
1601     if(result.length() <= capacity) {
1602         uprv_memcpy(buffer, result.data(), result.length());
1603     }
1604     return u_terminateChars(buffer, capacity, result.length(), &errorCode);
1605 }
1606
1607 UBool
1608 RuleBasedCollator::isUnsafe(UChar32 c) const {
1609     return data->isUnsafeBackward(c, settings->isNumeric());
1610 }
1611
1612 void
1613 RuleBasedCollator::computeMaxExpansions(const CollationTailoring *t, UErrorCode &errorCode) {
1614     t->maxExpansions = CollationElementIterator::computeMaxExpansions(t->data, errorCode);
1615 }
1616
1617 UBool
1618 RuleBasedCollator::initMaxExpansions(UErrorCode &errorCode) const {
1619     umtx_initOnce(tailoring->maxExpansionsInitOnce, computeMaxExpansions, tailoring, errorCode);
1620     return U_SUCCESS(errorCode);
1621 }
1622
1623 CollationElementIterator *
1624 RuleBasedCollator::createCollationElementIterator(const UnicodeString& source) const {
1625     UErrorCode errorCode = U_ZERO_ERROR;
1626     if(!initMaxExpansions(errorCode)) { return NULL; }
1627     CollationElementIterator *cei = new CollationElementIterator(source, this, errorCode);
1628     if(U_FAILURE(errorCode)) {
1629         delete cei;
1630         return NULL;
1631     }
1632     return cei;
1633 }
1634
1635 CollationElementIterator *
1636 RuleBasedCollator::createCollationElementIterator(const CharacterIterator& source) const {
1637     UErrorCode errorCode = U_ZERO_ERROR;
1638     if(!initMaxExpansions(errorCode)) { return NULL; }
1639     CollationElementIterator *cei = new CollationElementIterator(source, this, errorCode);
1640     if(U_FAILURE(errorCode)) {
1641         delete cei;
1642         return NULL;
1643     }
1644     return cei;
1645 }
1646
1647 int32_t
1648 RuleBasedCollator::getMaxExpansion(int32_t order) const {
1649     UErrorCode errorCode = U_ZERO_ERROR;
1650     (void)initMaxExpansions(errorCode);
1651     return CollationElementIterator::getMaxExpansion(tailoring->maxExpansions, order);
1652 }
1653
1654 U_NAMESPACE_END
1655
1656 #endif  // !UCONFIG_NO_COLLATION