icuSources/i18n/collationdatabuilder.cpp

   1 /*
   2 *******************************************************************************
   3 * Copyright (C) 2012-2015, International Business Machines
   4 * Corporation and others.  All Rights Reserved.
   5 *******************************************************************************
   6 * collationdatabuilder.cpp
   7 *
   8 * (replaced the former ucol_elm.cpp)
   9 *
  10 * created on: 2012apr01
  11 * created by: Markus W. Scherer
  12 */
  13
  14 #include "unicode/utypes.h"
  15
  16 #if !UCONFIG_NO_COLLATION
  17
  18 #include "unicode/localpointer.h"
  19 #include "unicode/uchar.h"
  20 #include "unicode/ucharstrie.h"
  21 #include "unicode/ucharstriebuilder.h"
  22 #include "unicode/uniset.h"
  23 #include "unicode/unistr.h"
  24 #include "unicode/usetiter.h"
  25 #include "unicode/utf16.h"
  26 #include "cmemory.h"
  27 #include "collation.h"
  28 #include "collationdata.h"
  29 #include "collationdatabuilder.h"
  30 #include "collationfastlatinbuilder.h"
  31 #include "collationiterator.h"
  32 #include "normalizer2impl.h"
  33 #include "utrie2.h"
  34 #include "uvectr32.h"
  35 #include "uvectr64.h"
  36 #include "uvector.h"
  37
  38 U_NAMESPACE_BEGIN
  39
  40 CollationDataBuilder::CEModifier::~CEModifier() {}
  41
  42 /**
  43  * Build-time context and CE32 for a code point.
  44  * If a code point has contextual mappings, then the default (no-context) mapping
  45  * and all conditional mappings are stored in a singly-linked list
  46  * of ConditionalCE32, sorted by context strings.
  47  *
  48  * Context strings sort by prefix length, then by prefix, then by contraction suffix.
  49  * Context strings must be unique and in ascending order.
  50  */
  51 struct ConditionalCE32 : public UMemory {
  52     ConditionalCE32()
  53             : context(),
  54               ce32(0), defaultCE32(Collation::NO_CE32), builtCE32(Collation::NO_CE32),
  55               next(-1) {}
  56     ConditionalCE32(const UnicodeString &ct, uint32_t ce)
  57             : context(ct),
  58               ce32(ce), defaultCE32(Collation::NO_CE32), builtCE32(Collation::NO_CE32),
  59               next(-1) {}
  60
  61     inline UBool hasContext() const { return context.length() > 1; }
  62     inline int32_t prefixLength() const { return context.charAt(0); }
  63
  64     /**
  65      * "\0" for the first entry for any code point, with its default CE32.
  66      *
  67      * Otherwise one unit with the length of the prefix string,
  68      * then the prefix string, then the contraction suffix.
  69      */
  70     UnicodeString context;
  71     /**
  72      * CE32 for the code point and its context.
  73      * Can be special (e.g., for an expansion) but not contextual (prefix or contraction tag).
  74      */
  75     uint32_t ce32;
  76     /**
  77      * Default CE32 for all contexts with this same prefix.
  78      * Initially NO_CE32. Set only while building runtime data structures,
  79      * and only on one of the nodes of a sub-list with the same prefix.
  80      */
  81     uint32_t defaultCE32;
  82     /**
  83      * CE32 for the built contexts.
  84      * When fetching CEs from the builder, the contexts are built into their runtime form
  85      * so that the normal collation implementation can process them.
  86      * The result is cached in the list head. It is reset when the contexts are modified.
  87      */
  88     uint32_t builtCE32;
  89     /**
  90      * Index of the next ConditionalCE32.
  91      * Negative for the end of the list.
  92      */
  93     int32_t next;
  94 };
  95
  96 U_CDECL_BEGIN
  97
  98 U_CAPI void U_CALLCONV
  99 uprv_deleteConditionalCE32(void *obj) {
 100     delete static_cast<ConditionalCE32 *>(obj);
 101 }
 102
 103 U_CDECL_END
 104
 105 /**
 106  * Build-time collation element and character iterator.
 107  * Uses the runtime CollationIterator for fetching CEs for a string
 108  * but reads from the builder's unfinished data structures.
 109  * In particular, this class reads from the unfinished trie
 110  * and has to avoid CollationIterator::nextCE() and redirect other
 111  * calls to data->getCE32() and data->getCE32FromSupplementary().
 112  *
 113  * We do this so that we need not implement the collation algorithm
 114  * again for the builder and make it behave exactly like the runtime code.
 115  * That would be more difficult to test and maintain than this indirection.
 116  *
 117  * Some CE32 tags (for example, the DIGIT_TAG) do not occur in the builder data,
 118  * so the data accesses from those code paths need not be modified.
 119  *
 120  * This class iterates directly over whole code points
 121  * so that the CollationIterator does not need the finished trie
 122  * for handling the LEAD_SURROGATE_TAG.
 123  */
 124 class DataBuilderCollationIterator : public CollationIterator {
 125 public:
 126     DataBuilderCollationIterator(CollationDataBuilder &b);
 127
 128     virtual ~DataBuilderCollationIterator();
 129
 130     int32_t fetchCEs(const UnicodeString &str, int32_t start, int64_t ces[], int32_t cesLength);
 131
 132     virtual void resetToOffset(int32_t newOffset);
 133     virtual int32_t getOffset() const;
 134
 135     virtual UChar32 nextCodePoint(UErrorCode &errorCode);
 136     virtual UChar32 previousCodePoint(UErrorCode &errorCode);
 137
 138 protected:
 139     virtual void forwardNumCodePoints(int32_t num, UErrorCode &errorCode);
 140     virtual void backwardNumCodePoints(int32_t num, UErrorCode &errorCode);
 141
 142     virtual uint32_t getDataCE32(UChar32 c) const;
 143     virtual uint32_t getCE32FromBuilderData(uint32_t ce32, UErrorCode &errorCode);
 144
 145     CollationDataBuilder &builder;
 146     CollationData builderData;
 147     uint32_t jamoCE32s[CollationData::JAMO_CE32S_LENGTH];
 148     const UnicodeString *s;
 149     int32_t pos;
 150 };
 151
 152 DataBuilderCollationIterator::DataBuilderCollationIterator(CollationDataBuilder &b)
 153         : CollationIterator(&builderData, /*numeric=*/ FALSE),
 154           builder(b), builderData(b.nfcImpl),
 155           s(NULL), pos(0) {
 156     builderData.base = builder.base;
 157     // Set all of the jamoCE32s[] to indirection CE32s.
 158     for(int32_t j = 0; j < CollationData::JAMO_CE32S_LENGTH; ++j) {  // Count across Jamo types.
 159         UChar32 jamo = CollationDataBuilder::jamoCpFromIndex(j);
 160         jamoCE32s[j] = Collation::makeCE32FromTagAndIndex(Collation::BUILDER_DATA_TAG, jamo) |
 161                 CollationDataBuilder::IS_BUILDER_JAMO_CE32;
 162     }
 163     builderData.jamoCE32s = jamoCE32s;
 164 }
 165
 166 DataBuilderCollationIterator::~DataBuilderCollationIterator() {}
 167
 168 int32_t
 169 DataBuilderCollationIterator::fetchCEs(const UnicodeString &str, int32_t start,
 170                                        int64_t ces[], int32_t cesLength) {
 171     // Set the pointers each time, in case they changed due to reallocation.
 172     builderData.ce32s = reinterpret_cast<const uint32_t *>(builder.ce32s.getBuffer());
 173     builderData.ces = builder.ce64s.getBuffer();
 174     builderData.contexts = builder.contexts.getBuffer();
 175     // Modified copy of CollationIterator::nextCE() and CollationIterator::nextCEFromCE32().
 176     reset();
 177     s = &str;
 178     pos = start;
 179     UErrorCode errorCode = U_ZERO_ERROR;
 180     while(U_SUCCESS(errorCode) && pos < s->length()) {
 181         // No need to keep all CEs in the iterator buffer.
 182         clearCEs();
 183         UChar32 c = s->char32At(pos);
 184         pos += U16_LENGTH(c);
 185         uint32_t ce32 = utrie2_get32(builder.trie, c);
 186         const CollationData *d;
 187         if(ce32 == Collation::FALLBACK_CE32) {
 188             d = builder.base;
 189             ce32 = builder.base->getCE32(c);
 190         } else {
 191             d = &builderData;
 192         }
 193         appendCEsFromCE32(d, c, ce32, /*forward=*/ TRUE, errorCode);
 194         U_ASSERT(U_SUCCESS(errorCode));
 195         for(int32_t i = 0; i < getCEsLength(); ++i) {
 196             int64_t ce = getCE(i);
 197             if(ce != 0) {
 198                 if(cesLength < Collation::MAX_EXPANSION_LENGTH) {
 199                     ces[cesLength] = ce;
 200                 }
 201                 ++cesLength;
 202             }
 203         }
 204     }
 205     return cesLength;
 206 }
 207
 208 void
 209 DataBuilderCollationIterator::resetToOffset(int32_t newOffset) {
 210     reset();
 211     pos = newOffset;
 212 }
 213
 214 int32_t
 215 DataBuilderCollationIterator::getOffset() const {
 216     return pos;
 217 }
 218
 219 UChar32
 220 DataBuilderCollationIterator::nextCodePoint(UErrorCode & /*errorCode*/) {
 221     if(pos == s->length()) {
 222         return U_SENTINEL;
 223     }
 224     UChar32 c = s->char32At(pos);
 225     pos += U16_LENGTH(c);
 226     return c;
 227 }
 228
 229 UChar32
 230 DataBuilderCollationIterator::previousCodePoint(UErrorCode & /*errorCode*/) {
 231     if(pos == 0) {
 232         return U_SENTINEL;
 233     }
 234     UChar32 c = s->char32At(pos - 1);
 235     pos -= U16_LENGTH(c);
 236     return c;
 237 }
 238
 239 void
 240 DataBuilderCollationIterator::forwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
 241     pos = s->moveIndex32(pos, num);
 242 }
 243
 244 void
 245 DataBuilderCollationIterator::backwardNumCodePoints(int32_t num, UErrorCode & /*errorCode*/) {
 246     pos = s->moveIndex32(pos, -num);
 247 }
 248
 249 uint32_t
 250 DataBuilderCollationIterator::getDataCE32(UChar32 c) const {
 251     return utrie2_get32(builder.trie, c);
 252 }
 253
 254 uint32_t
 255 DataBuilderCollationIterator::getCE32FromBuilderData(uint32_t ce32, UErrorCode &errorCode) {
 256     U_ASSERT(Collation::hasCE32Tag(ce32, Collation::BUILDER_DATA_TAG));
 257     if((ce32 & CollationDataBuilder::IS_BUILDER_JAMO_CE32) != 0) {
 258         UChar32 jamo = Collation::indexFromCE32(ce32);
 259         return utrie2_get32(builder.trie, jamo);
 260     } else {
 261         ConditionalCE32 *cond = builder.getConditionalCE32ForCE32(ce32);
 262         if(cond->builtCE32 == Collation::NO_CE32) {
 263             // Build the context-sensitive mappings into their runtime form and cache the result.
 264             cond->builtCE32 = builder.buildContext(cond, errorCode);
 265             if(errorCode == U_BUFFER_OVERFLOW_ERROR) {
 266                 errorCode = U_ZERO_ERROR;
 267                 builder.clearContexts();
 268                 cond->builtCE32 = builder.buildContext(cond, errorCode);
 269             }
 270             builderData.contexts = builder.contexts.getBuffer();
 271         }
 272         return cond->builtCE32;
 273     }
 274 }
 275
 276 // ------------------------------------------------------------------------- ***
 277
 278 CollationDataBuilder::CollationDataBuilder(UErrorCode &errorCode)
 279         : nfcImpl(*Normalizer2Factory::getNFCImpl(errorCode)),
 280           base(NULL), baseSettings(NULL),
 281           trie(NULL),
 282           ce32s(errorCode), ce64s(errorCode), conditionalCE32s(errorCode),
 283           modified(FALSE),
 284           fastLatinEnabled(FALSE), fastLatinBuilder(NULL),
 285           collIter(NULL) {
 286     // Reserve the first CE32 for U+0000.
 287     ce32s.addElement(0, errorCode);
 288     conditionalCE32s.setDeleter(uprv_deleteConditionalCE32);
 289 }
 290
 291 CollationDataBuilder::~CollationDataBuilder() {
 292     utrie2_close(trie);
 293     delete fastLatinBuilder;
 294     delete collIter;
 295 }
 296
 297 void
 298 CollationDataBuilder::initForTailoring(const CollationData *b, UErrorCode &errorCode) {
 299     if(U_FAILURE(errorCode)) { return; }
 300     if(trie != NULL) {
 301         errorCode = U_INVALID_STATE_ERROR;
 302         return;
 303     }
 304     if(b == NULL) {
 305         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 306         return;
 307     }
 308     base = b;
 309
 310     // For a tailoring, the default is to fall back to the base.
 311     trie = utrie2_open(Collation::FALLBACK_CE32, Collation::FFFD_CE32, &errorCode);
 312
 313     // Set the Latin-1 letters block so that it is allocated first in the data array,
 314     // to try to improve locality of reference when sorting Latin-1 text.
 315     // Do not use utrie2_setRange32() since that will not actually allocate blocks
 316     // that are filled with the default value.
 317     // ASCII (0..7F) is already preallocated anyway.
 318     for(UChar32 c = 0xc0; c <= 0xff; ++c) {
 319         utrie2_set32(trie, c, Collation::FALLBACK_CE32, &errorCode);
 320     }
 321
 322     // Hangul syllables are not tailorable (except via tailoring Jamos).
 323     // Always set the Hangul tag to help performance.
 324     // Do this here, rather than in buildMappings(),
 325     // so that we see the HANGUL_TAG in various assertions.
 326     uint32_t hangulCE32 = Collation::makeCE32FromTagAndIndex(Collation::HANGUL_TAG, 0);
 327     utrie2_setRange32(trie, Hangul::HANGUL_BASE, Hangul::HANGUL_END, hangulCE32, TRUE, &errorCode);
 328
 329     // Copy the set contents but don't copy/clone the set as a whole because
 330     // that would copy the isFrozen state too.
 331     unsafeBackwardSet.addAll(*b->unsafeBackwardSet);
 332
 333     if(U_FAILURE(errorCode)) { return; }
 334 }
 335
 336 UBool
 337 CollationDataBuilder::maybeSetPrimaryRange(UChar32 start, UChar32 end,
 338                                            uint32_t primary, int32_t step,
 339                                            UErrorCode &errorCode) {
 340     if(U_FAILURE(errorCode)) { return FALSE; }
 341     U_ASSERT(start <= end);
 342     // TODO: Do we need to check what values are currently set for start..end?
 343     // An offset range is worth it only if we can achieve an overlap between
 344     // adjacent UTrie2 blocks of 32 code points each.
 345     // An offset CE is also a little more expensive to look up and compute
 346     // than a simple CE.
 347     // If the range spans at least three UTrie2 block boundaries (> 64 code points),
 348     // then we take it.
 349     // If the range spans one or two block boundaries and there are
 350     // at least 4 code points on either side, then we take it.
 351     // (We could additionally require a minimum range length of, say, 16.)
 352     int32_t blockDelta = (end >> 5) - (start >> 5);
 353     if(2 <= step && step <= 0x7f &&
 354             (blockDelta >= 3 ||
 355             (blockDelta > 0 && (start & 0x1f) <= 0x1c && (end & 0x1f) >= 3))) {
 356         int64_t dataCE = ((int64_t)primary << 32) | (start << 8) | step;
 357         if(isCompressiblePrimary(primary)) { dataCE |= 0x80; }
 358         int32_t index = addCE(dataCE, errorCode);
 359         if(U_FAILURE(errorCode)) { return 0; }
 360         if(index > Collation::MAX_INDEX) {
 361             errorCode = U_BUFFER_OVERFLOW_ERROR;
 362             return 0;
 363         }
 364         uint32_t offsetCE32 = Collation::makeCE32FromTagAndIndex(Collation::OFFSET_TAG, index);
 365         utrie2_setRange32(trie, start, end, offsetCE32, TRUE, &errorCode);
 366         modified = TRUE;
 367         return TRUE;
 368     } else {
 369         return FALSE;
 370     }
 371 }
 372
 373 uint32_t
 374 CollationDataBuilder::setPrimaryRangeAndReturnNext(UChar32 start, UChar32 end,
 375                                                    uint32_t primary, int32_t step,
 376                                                    UErrorCode &errorCode) {
 377     if(U_FAILURE(errorCode)) { return 0; }
 378     UBool isCompressible = isCompressiblePrimary(primary);
 379     if(maybeSetPrimaryRange(start, end, primary, step, errorCode)) {
 380         return Collation::incThreeBytePrimaryByOffset(primary, isCompressible,
 381                                                       (end - start + 1) * step);
 382     } else {
 383         // Short range: Set individual CE32s.
 384         for(;;) {
 385             utrie2_set32(trie, start, Collation::makeLongPrimaryCE32(primary), &errorCode);
 386             ++start;
 387             primary = Collation::incThreeBytePrimaryByOffset(primary, isCompressible, step);
 388             if(start > end) { return primary; }
 389         }
 390         modified = TRUE;
 391     }
 392 }
 393
 394 uint32_t
 395 CollationDataBuilder::getCE32FromOffsetCE32(UBool fromBase, UChar32 c, uint32_t ce32) const {
 396     int32_t i = Collation::indexFromCE32(ce32);
 397     int64_t dataCE = fromBase ? base->ces[i] : ce64s.elementAti(i);
 398     uint32_t p = Collation::getThreeBytePrimaryForOffsetData(c, dataCE);
 399     return Collation::makeLongPrimaryCE32(p);
 400 }
 401
 402 UBool
 403 CollationDataBuilder::isCompressibleLeadByte(uint32_t b) const {
 404     return base->isCompressibleLeadByte(b);
 405 }
 406
 407 UBool
 408 CollationDataBuilder::isAssigned(UChar32 c) const {
 409     return Collation::isAssignedCE32(utrie2_get32(trie, c));
 410 }
 411
 412 uint32_t
 413 CollationDataBuilder::getLongPrimaryIfSingleCE(UChar32 c) const {
 414     uint32_t ce32 = utrie2_get32(trie, c);
 415     if(Collation::isLongPrimaryCE32(ce32)) {
 416         return Collation::primaryFromLongPrimaryCE32(ce32);
 417     } else {
 418         return 0;
 419     }
 420 }
 421
 422 int64_t
 423 CollationDataBuilder::getSingleCE(UChar32 c, UErrorCode &errorCode) const {
 424     if(U_FAILURE(errorCode)) { return 0; }
 425     // Keep parallel with CollationData::getSingleCE().
 426     UBool fromBase = FALSE;
 427     uint32_t ce32 = utrie2_get32(trie, c);
 428     if(ce32 == Collation::FALLBACK_CE32) {
 429         fromBase = TRUE;
 430         ce32 = base->getCE32(c);
 431     }
 432     while(Collation::isSpecialCE32(ce32)) {
 433         switch(Collation::tagFromCE32(ce32)) {
 434         case Collation::LATIN_EXPANSION_TAG:
 435         case Collation::BUILDER_DATA_TAG:
 436         case Collation::PREFIX_TAG:
 437         case Collation::CONTRACTION_TAG:
 438         case Collation::HANGUL_TAG:
 439         case Collation::LEAD_SURROGATE_TAG:
 440             errorCode = U_UNSUPPORTED_ERROR;
 441             return 0;
 442         case Collation::FALLBACK_TAG:
 443         case Collation::RESERVED_TAG_3:
 444             errorCode = U_INTERNAL_PROGRAM_ERROR;
 445             return 0;
 446         case Collation::LONG_PRIMARY_TAG:
 447             return Collation::ceFromLongPrimaryCE32(ce32);
 448         case Collation::LONG_SECONDARY_TAG:
 449             return Collation::ceFromLongSecondaryCE32(ce32);
 450         case Collation::EXPANSION32_TAG:
 451             if(Collation::lengthFromCE32(ce32) == 1) {
 452                 int32_t i = Collation::indexFromCE32(ce32);
 453                 ce32 = fromBase ? base->ce32s[i] : ce32s.elementAti(i);
 454                 break;
 455             } else {
 456                 errorCode = U_UNSUPPORTED_ERROR;
 457                 return 0;
 458             }
 459         case Collation::EXPANSION_TAG: {
 460             if(Collation::lengthFromCE32(ce32) == 1) {
 461                 int32_t i = Collation::indexFromCE32(ce32);
 462                 return fromBase ? base->ces[i] : ce64s.elementAti(i);
 463             } else {
 464                 errorCode = U_UNSUPPORTED_ERROR;
 465                 return 0;
 466             }
 467         }
 468         case Collation::DIGIT_TAG:
 469             // Fetch the non-numeric-collation CE32 and continue.
 470             ce32 = ce32s.elementAti(Collation::indexFromCE32(ce32));
 471             break;
 472         case Collation::U0000_TAG:
 473             U_ASSERT(c == 0);
 474             // Fetch the normal ce32 for U+0000 and continue.
 475             ce32 = fromBase ? base->ce32s[0] : ce32s.elementAti(0);
 476             break;
 477         case Collation::OFFSET_TAG:
 478             ce32 = getCE32FromOffsetCE32(fromBase, c, ce32);
 479             break;
 480         case Collation::IMPLICIT_TAG:
 481             return Collation::unassignedCEFromCodePoint(c);
 482         }
 483     }
 484     return Collation::ceFromSimpleCE32(ce32);
 485 }
 486
 487 int32_t
 488 CollationDataBuilder::addCE(int64_t ce, UErrorCode &errorCode) {
 489     int32_t length = ce64s.size();
 490     for(int32_t i = 0; i < length; ++i) {
 491         if(ce == ce64s.elementAti(i)) { return i; }
 492     }
 493     ce64s.addElement(ce, errorCode);
 494     return length;
 495 }
 496
 497 int32_t
 498 CollationDataBuilder::addCE32(uint32_t ce32, UErrorCode &errorCode) {
 499     int32_t length = ce32s.size();
 500     for(int32_t i = 0; i < length; ++i) {
 501         if(ce32 == (uint32_t)ce32s.elementAti(i)) { return i; }
 502     }
 503     ce32s.addElement((int32_t)ce32, errorCode);
 504     return length;
 505 }
 506
 507 int32_t
 508 CollationDataBuilder::addConditionalCE32(const UnicodeString &context, uint32_t ce32,
 509                                          UErrorCode &errorCode) {
 510     if(U_FAILURE(errorCode)) { return -1; }
 511     U_ASSERT(!context.isEmpty());
 512     int32_t index = conditionalCE32s.size();
 513     if(index > Collation::MAX_INDEX) {
 514         errorCode = U_BUFFER_OVERFLOW_ERROR;
 515         return -1;
 516     }
 517     ConditionalCE32 *cond = new ConditionalCE32(context, ce32);
 518     if(cond == NULL) {
 519         errorCode = U_MEMORY_ALLOCATION_ERROR;
 520         return -1;
 521     }
 522     conditionalCE32s.addElement(cond, errorCode);
 523     return index;
 524 }
 525
 526 void
 527 CollationDataBuilder::add(const UnicodeString &prefix, const UnicodeString &s,
 528                           const int64_t ces[], int32_t cesLength,
 529                           UErrorCode &errorCode) {
 530     uint32_t ce32 = encodeCEs(ces, cesLength, errorCode);
 531     addCE32(prefix, s, ce32, errorCode);
 532 }
 533
 534 void
 535 CollationDataBuilder::addCE32(const UnicodeString &prefix, const UnicodeString &s,
 536                               uint32_t ce32, UErrorCode &errorCode) {
 537     if(U_FAILURE(errorCode)) { return; }
 538     if(s.isEmpty()) {
 539         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 540         return;
 541     }
 542     if(trie == NULL || utrie2_isFrozen(trie)) {
 543         errorCode = U_INVALID_STATE_ERROR;
 544         return;
 545     }
 546     UChar32 c = s.char32At(0);
 547     int32_t cLength = U16_LENGTH(c);
 548     uint32_t oldCE32 = utrie2_get32(trie, c);
 549     UBool hasContext = !prefix.isEmpty() || s.length() > cLength;
 550     if(oldCE32 == Collation::FALLBACK_CE32) {
 551         // First tailoring for c.
 552         // If c has contextual base mappings or if we add a contextual mapping,
 553         // then copy the base mappings.
 554         // Otherwise we just override the base mapping.
 555         uint32_t baseCE32 = base->getFinalCE32(base->getCE32(c));
 556         if(hasContext || Collation::ce32HasContext(baseCE32)) {
 557             oldCE32 = copyFromBaseCE32(c, baseCE32, TRUE, errorCode);
 558             utrie2_set32(trie, c, oldCE32, &errorCode);
 559             if(U_FAILURE(errorCode)) { return; }
 560         }
 561     }
 562     if(!hasContext) {
 563         // No prefix, no contraction.
 564         if(!isBuilderContextCE32(oldCE32)) {
 565             utrie2_set32(trie, c, ce32, &errorCode);
 566         } else {
 567             ConditionalCE32 *cond = getConditionalCE32ForCE32(oldCE32);
 568             cond->builtCE32 = Collation::NO_CE32;
 569             cond->ce32 = ce32;
 570         }
 571     } else {
 572         ConditionalCE32 *cond;
 573         if(!isBuilderContextCE32(oldCE32)) {
 574             // Replace the simple oldCE32 with a builder context CE32
 575             // pointing to a new ConditionalCE32 list head.
 576             int32_t index = addConditionalCE32(UnicodeString((UChar)0), oldCE32, errorCode);
 577             if(U_FAILURE(errorCode)) { return; }
 578             uint32_t contextCE32 = makeBuilderContextCE32(index);
 579             utrie2_set32(trie, c, contextCE32, &errorCode);
 580             contextChars.add(c);
 581             cond = getConditionalCE32(index);
 582         } else {
 583             cond = getConditionalCE32ForCE32(oldCE32);
 584             cond->builtCE32 = Collation::NO_CE32;
 585         }
 586         UnicodeString suffix(s, cLength);
 587         UnicodeString context((UChar)prefix.length());
 588         context.append(prefix).append(suffix);
 589         unsafeBackwardSet.addAll(suffix);
 590         for(;;) {
 591             // invariant: context > cond->context
 592             int32_t next = cond->next;
 593             if(next < 0) {
 594                 // Append a new ConditionalCE32 after cond.
 595                 int32_t index = addConditionalCE32(context, ce32, errorCode);
 596                 if(U_FAILURE(errorCode)) { return; }
 597                 cond->next = index;
 598                 break;
 599             }
 600             ConditionalCE32 *nextCond = getConditionalCE32(next);
 601             int8_t cmp = context.compare(nextCond->context);
 602             if(cmp < 0) {
 603                 // Insert a new ConditionalCE32 between cond and nextCond.
 604                 int32_t index = addConditionalCE32(context, ce32, errorCode);
 605                 if(U_FAILURE(errorCode)) { return; }
 606                 cond->next = index;
 607                 getConditionalCE32(index)->next = next;
 608                 break;
 609             } else if(cmp == 0) {
 610                 // Same context as before, overwrite its ce32.
 611                 nextCond->ce32 = ce32;
 612                 break;
 613             }
 614             cond = nextCond;
 615         }
 616     }
 617     modified = TRUE;
 618 }
 619
 620 uint32_t
 621 CollationDataBuilder::encodeOneCEAsCE32(int64_t ce) {
 622     uint32_t p = (uint32_t)(ce >> 32);
 623     uint32_t lower32 = (uint32_t)ce;
 624     uint32_t t = (uint32_t)(ce & 0xffff);
 625     U_ASSERT((t & 0xc000) != 0xc000);  // Impossible case bits 11 mark special CE32s.
 626     if((ce & INT64_C(0xffff00ff00ff)) == 0) {
 627         // normal form ppppsstt
 628         return p | (lower32 >> 16) | (t >> 8);
 629     } else if((ce & INT64_C(0xffffffffff)) == Collation::COMMON_SEC_AND_TER_CE) {
 630         // long-primary form ppppppC1
 631         return Collation::makeLongPrimaryCE32(p);
 632     } else if(p == 0 && (t & 0xff) == 0) {
 633         // long-secondary form ssssttC2
 634         return Collation::makeLongSecondaryCE32(lower32);
 635     }
 636     return Collation::NO_CE32;
 637 }
 638
 639 uint32_t
 640 CollationDataBuilder::encodeOneCE(int64_t ce, UErrorCode &errorCode) {
 641     // Try to encode one CE as one CE32.
 642     uint32_t ce32 = encodeOneCEAsCE32(ce);
 643     if(ce32 != Collation::NO_CE32) { return ce32; }
 644     int32_t index = addCE(ce, errorCode);
 645     if(U_FAILURE(errorCode)) { return 0; }
 646     if(index > Collation::MAX_INDEX) {
 647         errorCode = U_BUFFER_OVERFLOW_ERROR;
 648         return 0;
 649     }
 650     return Collation::makeCE32FromTagIndexAndLength(Collation::EXPANSION_TAG, index, 1);
 651 }
 652
 653 uint32_t
 654 CollationDataBuilder::encodeCEs(const int64_t ces[], int32_t cesLength,
 655                                 UErrorCode &errorCode) {
 656     if(U_FAILURE(errorCode)) { return 0; }
 657     if(cesLength < 0 || cesLength > Collation::MAX_EXPANSION_LENGTH) {
 658         errorCode = U_ILLEGAL_ARGUMENT_ERROR;
 659         return 0;
 660     }
 661     if(trie == NULL || utrie2_isFrozen(trie)) {
 662         errorCode = U_INVALID_STATE_ERROR;
 663         return 0;
 664     }
 665     if(cesLength == 0) {
 666         // Convenience: We cannot map to nothing, but we can map to a completely ignorable CE.
 667         // Do this here so that callers need not do it.
 668         return encodeOneCEAsCE32(0);
 669     } else if(cesLength == 1) {
 670         return encodeOneCE(ces[0], errorCode);
 671     } else if(cesLength == 2) {
 672         // Try to encode two CEs as one CE32.
 673         int64_t ce0 = ces[0];
 674         int64_t ce1 = ces[1];
 675         uint32_t p0 = (uint32_t)(ce0 >> 32);
 676         if((ce0 & INT64_C(0xffffffffff00ff)) == Collation::COMMON_SECONDARY_CE &&
 677                 (ce1 & INT64_C(0xffffffff00ffffff)) == Collation::COMMON_TERTIARY_CE &&
 678                 p0 != 0) {
 679             // Latin mini expansion
 680             return
 681                 p0 |
 682                 (((uint32_t)ce0 & 0xff00u) << 8) |
 683                 (uint32_t)(ce1 >> 16) |
 684                 Collation::SPECIAL_CE32_LOW_BYTE |
 685                 Collation::LATIN_EXPANSION_TAG;
 686         }
 687     }
 688     // Try to encode two or more CEs as CE32s.
 689     int32_t newCE32s[Collation::MAX_EXPANSION_LENGTH];
 690     for(int32_t i = 0;; ++i) {
 691         if(i == cesLength) {
 692             return encodeExpansion32(newCE32s, cesLength, errorCode);
 693         }
 694         uint32_t ce32 = encodeOneCEAsCE32(ces[i]);
 695         if(ce32 == Collation::NO_CE32) { break; }
 696         newCE32s[i] = (int32_t)ce32;
 697     }
 698     return encodeExpansion(ces, cesLength, errorCode);
 699 }
 700
 701 uint32_t
 702 CollationDataBuilder::encodeExpansion(const int64_t ces[], int32_t length, UErrorCode &errorCode) {
 703     if(U_FAILURE(errorCode)) { return 0; }
 704     // See if this sequence of CEs has already been stored.
 705     int64_t first = ces[0];
 706     int32_t ce64sMax = ce64s.size() - length;
 707     for(int32_t i = 0; i <= ce64sMax; ++i) {
 708         if(first == ce64s.elementAti(i)) {
 709             if(i > Collation::MAX_INDEX) {
 710                 errorCode = U_BUFFER_OVERFLOW_ERROR;
 711                 return 0;
 712             }
 713             for(int32_t j = 1;; ++j) {
 714                 if(j == length) {
 715                     return Collation::makeCE32FromTagIndexAndLength(
 716                             Collation::EXPANSION_TAG, i, length);
 717                 }
 718                 if(ce64s.elementAti(i + j) != ces[j]) { break; }
 719             }
 720         }
 721     }
 722     // Store the new sequence.
 723     int32_t i = ce64s.size();
 724     if(i > Collation::MAX_INDEX) {
 725         errorCode = U_BUFFER_OVERFLOW_ERROR;
 726         return 0;
 727     }
 728     for(int32_t j = 0; j < length; ++j) {
 729         ce64s.addElement(ces[j], errorCode);
 730     }
 731     return Collation::makeCE32FromTagIndexAndLength(Collation::EXPANSION_TAG, i, length);
 732 }
 733
 734 uint32_t
 735 CollationDataBuilder::encodeExpansion32(const int32_t newCE32s[], int32_t length,
 736                                         UErrorCode &errorCode) {
 737     if(U_FAILURE(errorCode)) { return 0; }
 738     // See if this sequence of CE32s has already been stored.
 739     int32_t first = newCE32s[0];
 740     int32_t ce32sMax = ce32s.size() - length;
 741     for(int32_t i = 0; i <= ce32sMax; ++i) {
 742         if(first == ce32s.elementAti(i)) {
 743             if(i > Collation::MAX_INDEX) {
 744                 errorCode = U_BUFFER_OVERFLOW_ERROR;
 745                 return 0;
 746             }
 747             for(int32_t j = 1;; ++j) {
 748                 if(j == length) {
 749                     return Collation::makeCE32FromTagIndexAndLength(
 750                             Collation::EXPANSION32_TAG, i, length);
 751                 }
 752                 if(ce32s.elementAti(i + j) != newCE32s[j]) { break; }
 753             }
 754         }
 755     }
 756     // Store the new sequence.
 757     int32_t i = ce32s.size();
 758     if(i > Collation::MAX_INDEX) {
 759         errorCode = U_BUFFER_OVERFLOW_ERROR;
 760         return 0;
 761     }
 762     for(int32_t j = 0; j < length; ++j) {
 763         ce32s.addElement(newCE32s[j], errorCode);
 764     }
 765     return Collation::makeCE32FromTagIndexAndLength(Collation::EXPANSION32_TAG, i, length);
 766 }
 767
 768 uint32_t
 769 CollationDataBuilder::copyFromBaseCE32(UChar32 c, uint32_t ce32, UBool withContext,
 770                                        UErrorCode &errorCode) {
 771     if(U_FAILURE(errorCode)) { return 0; }
 772     if(!Collation::isSpecialCE32(ce32)) { return ce32; }
 773     switch(Collation::tagFromCE32(ce32)) {
 774     case Collation::LONG_PRIMARY_TAG:
 775     case Collation::LONG_SECONDARY_TAG:
 776     case Collation::LATIN_EXPANSION_TAG:
 777         // copy as is
 778         break;
 779     case Collation::EXPANSION32_TAG: {
 780         const uint32_t *baseCE32s = base->ce32s + Collation::indexFromCE32(ce32);
 781         int32_t length = Collation::lengthFromCE32(ce32);
 782         ce32 = encodeExpansion32(
 783             reinterpret_cast<const int32_t *>(baseCE32s), length, errorCode);
 784         break;
 785     }
 786     case Collation::EXPANSION_TAG: {
 787         const int64_t *baseCEs = base->ces + Collation::indexFromCE32(ce32);
 788         int32_t length = Collation::lengthFromCE32(ce32);
 789         ce32 = encodeExpansion(baseCEs, length, errorCode);
 790         break;
 791     }
 792     case Collation::PREFIX_TAG: {
 793         // Flatten prefixes and nested suffixes (contractions)
 794         // into a linear list of ConditionalCE32.
 795         const UChar *p = base->contexts + Collation::indexFromCE32(ce32);
 796         ce32 = CollationData::readCE32(p);  // Default if no prefix match.
 797         if(!withContext) {
 798             return copyFromBaseCE32(c, ce32, FALSE, errorCode);
 799         }
 800         ConditionalCE32 head;
 801         UnicodeString context((UChar)0);
 802         int32_t index;
 803         if(Collation::isContractionCE32(ce32)) {
 804             index = copyContractionsFromBaseCE32(context, c, ce32, &head, errorCode);
 805         } else {
 806             ce32 = copyFromBaseCE32(c, ce32, TRUE, errorCode);
 807             head.next = index = addConditionalCE32(context, ce32, errorCode);
 808         }
 809         if(U_FAILURE(errorCode)) { return 0; }
 810         ConditionalCE32 *cond = getConditionalCE32(index);  // the last ConditionalCE32 so far
 811         UCharsTrie::Iterator prefixes(p + 2, 0, errorCode);
 812         while(prefixes.next(errorCode)) {
 813             context = prefixes.getString();
 814             context.reverse();
 815             context.insert(0, (UChar)context.length());
 816             ce32 = (uint32_t)prefixes.getValue();
 817             if(Collation::isContractionCE32(ce32)) {
 818                 index = copyContractionsFromBaseCE32(context, c, ce32, cond, errorCode);
 819             } else {
 820                 ce32 = copyFromBaseCE32(c, ce32, TRUE, errorCode);
 821                 cond->next = index = addConditionalCE32(context, ce32, errorCode);
 822             }
 823             if(U_FAILURE(errorCode)) { return 0; }
 824             cond = getConditionalCE32(index);
 825         }
 826         ce32 = makeBuilderContextCE32(head.next);
 827         contextChars.add(c);
 828         break;
 829     }
 830     case Collation::CONTRACTION_TAG: {
 831         if(!withContext) {
 832             const UChar *p = base->contexts + Collation::indexFromCE32(ce32);
 833             ce32 = CollationData::readCE32(p);  // Default if no suffix match.
 834             return copyFromBaseCE32(c, ce32, FALSE, errorCode);
 835         }
 836         ConditionalCE32 head;
 837         UnicodeString context((UChar)0);
 838         copyContractionsFromBaseCE32(context, c, ce32, &head, errorCode);
 839         ce32 = makeBuilderContextCE32(head.next);
 840         contextChars.add(c);
 841         break;
 842     }
 843     case Collation::HANGUL_TAG:
 844         errorCode = U_UNSUPPORTED_ERROR;  // We forbid tailoring of Hangul syllables.
 845         break;
 846     case Collation::OFFSET_TAG:
 847         ce32 = getCE32FromOffsetCE32(TRUE, c, ce32);
 848         break;
 849     case Collation::IMPLICIT_TAG:
 850         ce32 = encodeOneCE(Collation::unassignedCEFromCodePoint(c), errorCode);
 851         break;
 852     default:
 853         U_ASSERT(FALSE);  // require ce32 == base->getFinalCE32(ce32)
 854         break;
 855     }
 856     return ce32;
 857 }
 858
 859 int32_t
 860 CollationDataBuilder::copyContractionsFromBaseCE32(UnicodeString &context, UChar32 c, uint32_t ce32,
 861                                                    ConditionalCE32 *cond, UErrorCode &errorCode) {
 862     if(U_FAILURE(errorCode)) { return 0; }
 863     const UChar *p = base->contexts + Collation::indexFromCE32(ce32);
 864     int32_t index;
 865     if((ce32 & Collation::CONTRACT_SINGLE_CP_NO_MATCH) != 0) {
 866         // No match on the single code point.
 867         // We are underneath a prefix, and the default mapping is just
 868         // a fallback to the mappings for a shorter prefix.
 869         U_ASSERT(context.length() > 1);
 870         index = -1;
 871     } else {
 872         ce32 = CollationData::readCE32(p);  // Default if no suffix match.
 873         U_ASSERT(!Collation::isContractionCE32(ce32));
 874         ce32 = copyFromBaseCE32(c, ce32, TRUE, errorCode);
 875         cond->next = index = addConditionalCE32(context, ce32, errorCode);
 876         if(U_FAILURE(errorCode)) { return 0; }
 877         cond = getConditionalCE32(index);
 878     }
 879
 880     int32_t suffixStart = context.length();
 881     UCharsTrie::Iterator suffixes(p + 2, 0, errorCode);
 882     while(suffixes.next(errorCode)) {
 883         context.append(suffixes.getString());
 884         ce32 = copyFromBaseCE32(c, (uint32_t)suffixes.getValue(), TRUE, errorCode);
 885         cond->next = index = addConditionalCE32(context, ce32, errorCode);
 886         if(U_FAILURE(errorCode)) { return 0; }
 887         // No need to update the unsafeBackwardSet because the tailoring set
 888         // is already a copy of the base set.
 889         cond = getConditionalCE32(index);
 890         context.truncate(suffixStart);
 891     }
 892     U_ASSERT(index >= 0);
 893     return index;
 894 }
 895
 896 class CopyHelper {
 897 public:
 898     CopyHelper(const CollationDataBuilder &s, CollationDataBuilder &d,
 899                const CollationDataBuilder::CEModifier &m, UErrorCode &initialErrorCode)
 900             : src(s), dest(d), modifier(m),
 901               errorCode(initialErrorCode) {}
 902
 903     UBool copyRangeCE32(UChar32 start, UChar32 end, uint32_t ce32) {
 904         ce32 = copyCE32(ce32);
 905         utrie2_setRange32(dest.trie, start, end, ce32, TRUE, &errorCode);
 906         if(CollationDataBuilder::isBuilderContextCE32(ce32)) {
 907             dest.contextChars.add(start, end);
 908         }
 909         return U_SUCCESS(errorCode);
 910     }
 911
 912     uint32_t copyCE32(uint32_t ce32) {
 913         if(!Collation::isSpecialCE32(ce32)) {
 914             int64_t ce = modifier.modifyCE32(ce32);
 915             if(ce != Collation::NO_CE) {
 916                 ce32 = dest.encodeOneCE(ce, errorCode);
 917             }
 918         } else {
 919             int32_t tag = Collation::tagFromCE32(ce32);
 920             if(tag == Collation::EXPANSION32_TAG) {
 921                 const uint32_t *srcCE32s = reinterpret_cast<uint32_t *>(src.ce32s.getBuffer());
 922                 srcCE32s += Collation::indexFromCE32(ce32);
 923                 int32_t length = Collation::lengthFromCE32(ce32);
 924                 // Inspect the source CE32s. Just copy them if none are modified.
 925                 // Otherwise copy to modifiedCEs, with modifications.
 926                 UBool isModified = FALSE;
 927                 for(int32_t i = 0; i < length; ++i) {
 928                     ce32 = srcCE32s[i];
 929                     int64_t ce;
 930                     if(Collation::isSpecialCE32(ce32) ||
 931                             (ce = modifier.modifyCE32(ce32)) == Collation::NO_CE) {
 932                         if(isModified) {
 933                             modifiedCEs[i] = Collation::ceFromCE32(ce32);
 934                         }
 935                     } else {
 936                         if(!isModified) {
 937                             for(int32_t j = 0; j < i; ++j) {
 938                                 modifiedCEs[j] = Collation::ceFromCE32(srcCE32s[j]);
 939                             }
 940                             isModified = TRUE;
 941                         }
 942                         modifiedCEs[i] = ce;
 943                     }
 944                 }
 945                 if(isModified) {
 946                     ce32 = dest.encodeCEs(modifiedCEs, length, errorCode);
 947                 } else {
 948                     ce32 = dest.encodeExpansion32(
 949                         reinterpret_cast<const int32_t *>(srcCE32s), length, errorCode);
 950                 }
 951             } else if(tag == Collation::EXPANSION_TAG) {
 952                 const int64_t *srcCEs = src.ce64s.getBuffer();
 953                 srcCEs += Collation::indexFromCE32(ce32);
 954                 int32_t length = Collation::lengthFromCE32(ce32);
 955                 // Inspect the source CEs. Just copy them if none are modified.
 956                 // Otherwise copy to modifiedCEs, with modifications.
 957                 UBool isModified = FALSE;
 958                 for(int32_t i = 0; i < length; ++i) {
 959                     int64_t srcCE = srcCEs[i];
 960                     int64_t ce = modifier.modifyCE(srcCE);
 961                     if(ce == Collation::NO_CE) {
 962                         if(isModified) {
 963                             modifiedCEs[i] = srcCE;
 964                         }
 965                     } else {
 966                         if(!isModified) {
 967                             for(int32_t j = 0; j < i; ++j) {
 968                                 modifiedCEs[j] = srcCEs[j];
 969                             }
 970                             isModified = TRUE;
 971                         }
 972                         modifiedCEs[i] = ce;
 973                     }
 974                 }
 975                 if(isModified) {
 976                     ce32 = dest.encodeCEs(modifiedCEs, length, errorCode);
 977                 } else {
 978                     ce32 = dest.encodeExpansion(srcCEs, length, errorCode);
 979                 }
 980             } else if(tag == Collation::BUILDER_DATA_TAG) {
 981                 // Copy the list of ConditionalCE32.
 982                 ConditionalCE32 *cond = src.getConditionalCE32ForCE32(ce32);
 983                 U_ASSERT(!cond->hasContext());
 984                 int32_t destIndex = dest.addConditionalCE32(
 985                         cond->context, copyCE32(cond->ce32), errorCode);
 986                 ce32 = CollationDataBuilder::makeBuilderContextCE32(destIndex);
 987                 while(cond->next >= 0) {
 988                     cond = src.getConditionalCE32(cond->next);
 989                     ConditionalCE32 *prevDestCond = dest.getConditionalCE32(destIndex);
 990                     destIndex = dest.addConditionalCE32(
 991                             cond->context, copyCE32(cond->ce32), errorCode);
 992                     int32_t suffixStart = cond->prefixLength() + 1;
 993                     dest.unsafeBackwardSet.addAll(cond->context.tempSubString(suffixStart));
 994                     prevDestCond->next = destIndex;
 995                 }
 996             } else {
 997                 // Just copy long CEs and Latin mini expansions (and other expected values) as is,
 998                 // assuming that the modifier would not modify them.
 999                 U_ASSERT(tag == Collation::LONG_PRIMARY_TAG ||
1000                         tag == Collation::LONG_SECONDARY_TAG ||
1001                         tag == Collation::LATIN_EXPANSION_TAG ||
1002                         tag == Collation::HANGUL_TAG);
1003             }
1004         }
1005         return ce32;
1006     }
1007
1008     const CollationDataBuilder &src;
1009     CollationDataBuilder &dest;
1010     const CollationDataBuilder::CEModifier &modifier;
1011     int64_t modifiedCEs[Collation::MAX_EXPANSION_LENGTH];
1012     UErrorCode errorCode;
1013 };
1014
1015 U_CDECL_BEGIN
1016
1017 static UBool U_CALLCONV
1018 enumRangeForCopy(const void *context, UChar32 start, UChar32 end, uint32_t value) {
1019     return
1020         value == Collation::UNASSIGNED_CE32 || value == Collation::FALLBACK_CE32 ||
1021         ((CopyHelper *)context)->copyRangeCE32(start, end, value);
1022 }
1023
1024 U_CDECL_END
1025
1026 void
1027 CollationDataBuilder::copyFrom(const CollationDataBuilder &src, const CEModifier &modifier,
1028                                UErrorCode &errorCode) {
1029     if(U_FAILURE(errorCode)) { return; }
1030     if(trie == NULL || utrie2_isFrozen(trie)) {
1031         errorCode = U_INVALID_STATE_ERROR;
1032         return;
1033     }
1034     CopyHelper helper(src, *this, modifier, errorCode);
1035     utrie2_enum(src.trie, NULL, enumRangeForCopy, &helper);
1036     errorCode = helper.errorCode;
1037     // Update the contextChars and the unsafeBackwardSet while copying,
1038     // in case a character had conditional mappings in the source builder
1039     // and they were removed later.
1040     modified |= src.modified;
1041 }
1042
1043 void
1044 CollationDataBuilder::optimize(const UnicodeSet &set, UErrorCode &errorCode) {
1045     if(U_FAILURE(errorCode) || set.isEmpty()) { return; }
1046     UnicodeSetIterator iter(set);
1047     while(iter.next() && !iter.isString()) {
1048         UChar32 c = iter.getCodepoint();
1049         uint32_t ce32 = utrie2_get32(trie, c);
1050         if(ce32 == Collation::FALLBACK_CE32) {
1051             ce32 = base->getFinalCE32(base->getCE32(c));
1052             ce32 = copyFromBaseCE32(c, ce32, TRUE, errorCode);
1053             utrie2_set32(trie, c, ce32, &errorCode);
1054         }
1055     }
1056     modified = TRUE;
1057 }
1058
1059 void
1060 CollationDataBuilder::suppressContractions(const UnicodeSet &set, UErrorCode &errorCode) {
1061     if(U_FAILURE(errorCode) || set.isEmpty()) { return; }
1062     UnicodeSetIterator iter(set);
1063     while(iter.next() && !iter.isString()) {
1064         UChar32 c = iter.getCodepoint();
1065         uint32_t ce32 = utrie2_get32(trie, c);
1066         if(ce32 == Collation::FALLBACK_CE32) {
1067             ce32 = base->getFinalCE32(base->getCE32(c));
1068             if(Collation::ce32HasContext(ce32)) {
1069                 ce32 = copyFromBaseCE32(c, ce32, FALSE /* without context */, errorCode);
1070                 utrie2_set32(trie, c, ce32, &errorCode);
1071             }
1072         } else if(isBuilderContextCE32(ce32)) {
1073             ce32 = getConditionalCE32ForCE32(ce32)->ce32;
1074             // Simply abandon the list of ConditionalCE32.
1075             // The caller will copy this builder in the end,
1076             // eliminating unreachable data.
1077             utrie2_set32(trie, c, ce32, &errorCode);
1078             contextChars.remove(c);
1079         }
1080     }
1081     modified = TRUE;
1082 }
1083
1084 UBool
1085 CollationDataBuilder::getJamoCE32s(uint32_t jamoCE32s[], UErrorCode &errorCode) {
1086     if(U_FAILURE(errorCode)) { return FALSE; }
1087     UBool anyJamoAssigned = base == NULL;  // always set jamoCE32s in the base data
1088     UBool needToCopyFromBase = FALSE;
1089     for(int32_t j = 0; j < CollationData::JAMO_CE32S_LENGTH; ++j) {  // Count across Jamo types.
1090         UChar32 jamo = jamoCpFromIndex(j);
1091         UBool fromBase = FALSE;
1092         uint32_t ce32 = utrie2_get32(trie, jamo);
1093         anyJamoAssigned |= Collation::isAssignedCE32(ce32);
1094         // TODO: Try to prevent [optimize [Jamo]] from counting as anyJamoAssigned.
1095         // (As of CLDR 24 [2013] the Korean tailoring does not optimize conjoining Jamo.)
1096         if(ce32 == Collation::FALLBACK_CE32) {
1097             fromBase = TRUE;
1098             ce32 = base->getCE32(jamo);
1099         }
1100         if(Collation::isSpecialCE32(ce32)) {
1101             switch(Collation::tagFromCE32(ce32)) {
1102             case Collation::LONG_PRIMARY_TAG:
1103             case Collation::LONG_SECONDARY_TAG:
1104             case Collation::LATIN_EXPANSION_TAG:
1105                 // Copy the ce32 as-is.
1106                 break;
1107             case Collation::EXPANSION32_TAG:
1108             case Collation::EXPANSION_TAG:
1109             case Collation::PREFIX_TAG:
1110             case Collation::CONTRACTION_TAG:
1111                 if(fromBase) {
1112                     // Defer copying until we know if anyJamoAssigned.
1113                     ce32 = Collation::FALLBACK_CE32;
1114                     needToCopyFromBase = TRUE;
1115                 }
1116                 break;
1117             case Collation::IMPLICIT_TAG:
1118                 // An unassigned Jamo should only occur in tests with incomplete bases.
1119                 U_ASSERT(fromBase);
1120                 ce32 = Collation::FALLBACK_CE32;
1121                 needToCopyFromBase = TRUE;
1122                 break;
1123             case Collation::OFFSET_TAG:
1124                 ce32 = getCE32FromOffsetCE32(fromBase, jamo, ce32);
1125                 break;
1126             case Collation::FALLBACK_TAG:
1127             case Collation::RESERVED_TAG_3:
1128             case Collation::BUILDER_DATA_TAG:
1129             case Collation::DIGIT_TAG:
1130             case Collation::U0000_TAG:
1131             case Collation::HANGUL_TAG:
1132             case Collation::LEAD_SURROGATE_TAG:
1133                 errorCode = U_INTERNAL_PROGRAM_ERROR;
1134                 return FALSE;
1135             }
1136         }
1137         jamoCE32s[j] = ce32;
1138     }
1139     if(anyJamoAssigned && needToCopyFromBase) {
1140         for(int32_t j = 0; j < CollationData::JAMO_CE32S_LENGTH; ++j) {
1141             if(jamoCE32s[j] == Collation::FALLBACK_CE32) {
1142                 UChar32 jamo = jamoCpFromIndex(j);
1143                 jamoCE32s[j] = copyFromBaseCE32(jamo, base->getCE32(jamo),
1144                                                 /*withContext=*/ TRUE, errorCode);
1145             }
1146         }
1147     }
1148     return anyJamoAssigned && U_SUCCESS(errorCode);
1149 }
1150
1151 void
1152 CollationDataBuilder::setDigitTags(UErrorCode &errorCode) {
1153     UnicodeSet digits(UNICODE_STRING_SIMPLE("[:Nd:]"), errorCode);
1154     if(U_FAILURE(errorCode)) { return; }
1155     UnicodeSetIterator iter(digits);
1156     while(iter.next()) {
1157         U_ASSERT(!iter.isString());
1158         UChar32 c = iter.getCodepoint();
1159         uint32_t ce32 = utrie2_get32(trie, c);
1160         if(ce32 != Collation::FALLBACK_CE32 && ce32 != Collation::UNASSIGNED_CE32) {
1161             int32_t index = addCE32(ce32, errorCode);
1162             if(U_FAILURE(errorCode)) { return; }
1163             if(index > Collation::MAX_INDEX) {
1164                 errorCode = U_BUFFER_OVERFLOW_ERROR;
1165                 return;
1166             }
1167             ce32 = Collation::makeCE32FromTagIndexAndLength(
1168                     Collation::DIGIT_TAG, index, u_charDigitValue(c));
1169             utrie2_set32(trie, c, ce32, &errorCode);
1170         }
1171     }
1172 }
1173
1174 U_CDECL_BEGIN
1175
1176 static UBool U_CALLCONV
1177 enumRangeLeadValue(const void *context, UChar32 /*start*/, UChar32 /*end*/, uint32_t value) {
1178     int32_t *pValue = (int32_t *)context;
1179     if(value == Collation::UNASSIGNED_CE32) {
1180         value = Collation::LEAD_ALL_UNASSIGNED;
1181     } else if(value == Collation::FALLBACK_CE32) {
1182         value = Collation::LEAD_ALL_FALLBACK;
1183     } else {
1184         *pValue = Collation::LEAD_MIXED;
1185         return FALSE;
1186     }
1187     if(*pValue < 0) {
1188         *pValue = (int32_t)value;
1189     } else if(*pValue != (int32_t)value) {
1190         *pValue = Collation::LEAD_MIXED;
1191         return FALSE;
1192     }
1193     return TRUE;
1194 }
1195
1196 U_CDECL_END
1197
1198 void
1199 CollationDataBuilder::setLeadSurrogates(UErrorCode &errorCode) {
1200     for(UChar lead = 0xd800; lead < 0xdc00; ++lead) {
1201         int32_t value = -1;
1202         utrie2_enumForLeadSurrogate(trie, lead, NULL, enumRangeLeadValue, &value);
1203         utrie2_set32ForLeadSurrogateCodeUnit(
1204             trie, lead,
1205             Collation::makeCE32FromTagAndIndex(Collation::LEAD_SURROGATE_TAG, 0) | (uint32_t)value,
1206             &errorCode);
1207     }
1208 }
1209
1210 void
1211 CollationDataBuilder::build(CollationData &data, UErrorCode &errorCode) {
1212     buildMappings(data, errorCode);
1213     if(base != NULL) {
1214         data.numericPrimary = base->numericPrimary;
1215         data.compressibleBytes = base->compressibleBytes;
1216         data.numScripts = base->numScripts;
1217         data.scriptsIndex = base->scriptsIndex;
1218         data.scriptStarts = base->scriptStarts;
1219         data.scriptStartsLength = base->scriptStartsLength;
1220     }
1221     buildFastLatinTable(data, errorCode);
1222 }
1223
1224 void
1225 CollationDataBuilder::buildMappings(CollationData &data, UErrorCode &errorCode) {
1226     if(U_FAILURE(errorCode)) { return; }
1227     if(trie == NULL || utrie2_isFrozen(trie)) {
1228         errorCode = U_INVALID_STATE_ERROR;
1229         return;
1230     }
1231
1232     buildContexts(errorCode);
1233
1234     uint32_t jamoCE32s[CollationData::JAMO_CE32S_LENGTH];
1235     int32_t jamoIndex = -1;
1236     if(getJamoCE32s(jamoCE32s, errorCode)) {
1237         jamoIndex = ce32s.size();
1238         for(int32_t i = 0; i < CollationData::JAMO_CE32S_LENGTH; ++i) {
1239             ce32s.addElement((int32_t)jamoCE32s[i], errorCode);
1240         }
1241         // Small optimization: Use a bit in the Hangul ce32
1242         // to indicate that none of the Jamo CE32s are isSpecialCE32()
1243         // (as it should be in the root collator).
1244         // It allows CollationIterator to avoid recursive function calls and per-Jamo tests.
1245         // In order to still have good trie compression and keep this code simple,
1246         // we only set this flag if a whole block of 588 Hangul syllables starting with
1247         // a common leading consonant (Jamo L) has this property.
1248         UBool isAnyJamoVTSpecial = FALSE;
1249         for(int32_t i = Hangul::JAMO_L_COUNT; i < CollationData::JAMO_CE32S_LENGTH; ++i) {
1250             if(Collation::isSpecialCE32(jamoCE32s[i])) {
1251                 isAnyJamoVTSpecial = TRUE;
1252                 break;
1253             }
1254         }
1255         uint32_t hangulCE32 = Collation::makeCE32FromTagAndIndex(Collation::HANGUL_TAG, 0);
1256         UChar32 c = Hangul::HANGUL_BASE;
1257         for(int32_t i = 0; i < Hangul::JAMO_L_COUNT; ++i) {  // iterate over the Jamo L
1258             uint32_t ce32 = hangulCE32;
1259             if(!isAnyJamoVTSpecial && !Collation::isSpecialCE32(jamoCE32s[i])) {
1260                 ce32 |= Collation::HANGUL_NO_SPECIAL_JAMO;
1261             }
1262             UChar32 limit = c + Hangul::JAMO_VT_COUNT;
1263             utrie2_setRange32(trie, c, limit - 1, ce32, TRUE, &errorCode);
1264             c = limit;
1265         }
1266     } else {
1267         // Copy the Hangul CE32s from the base in blocks per Jamo L,
1268         // assuming that HANGUL_NO_SPECIAL_JAMO is set or not set for whole blocks.
1269         for(UChar32 c = Hangul::HANGUL_BASE; c < Hangul::HANGUL_LIMIT;) {
1270             uint32_t ce32 = base->getCE32(c);
1271             U_ASSERT(Collation::hasCE32Tag(ce32, Collation::HANGUL_TAG));
1272             UChar32 limit = c + Hangul::JAMO_VT_COUNT;
1273             utrie2_setRange32(trie, c, limit - 1, ce32, TRUE, &errorCode);
1274             c = limit;
1275         }
1276     }
1277
1278     setDigitTags(errorCode);
1279     setLeadSurrogates(errorCode);
1280
1281     // For U+0000, move its normal ce32 into CE32s[0] and set U0000_TAG.
1282     ce32s.setElementAt((int32_t)utrie2_get32(trie, 0), 0);
1283     utrie2_set32(trie, 0, Collation::makeCE32FromTagAndIndex(Collation::U0000_TAG, 0), &errorCode);
1284
1285     utrie2_freeze(trie, UTRIE2_32_VALUE_BITS, &errorCode);
1286     if(U_FAILURE(errorCode)) { return; }
1287
1288     // Mark each lead surrogate as "unsafe"
1289     // if any of its 1024 associated supplementary code points is "unsafe".
1290     UChar32 c = 0x10000;
1291     for(UChar lead = 0xd800; lead < 0xdc00; ++lead, c += 0x400) {
1292         if(unsafeBackwardSet.containsSome(c, c + 0x3ff)) {
1293             unsafeBackwardSet.add(lead);
1294         }
1295     }
1296     unsafeBackwardSet.freeze();
1297
1298     data.trie = trie;
1299     data.ce32s = reinterpret_cast<const uint32_t *>(ce32s.getBuffer());
1300     data.ces = ce64s.getBuffer();
1301     data.contexts = contexts.getBuffer();
1302
1303     data.ce32sLength = ce32s.size();
1304     data.cesLength = ce64s.size();
1305     data.contextsLength = contexts.length();
1306
1307     data.base = base;
1308     if(jamoIndex >= 0) {
1309         data.jamoCE32s = data.ce32s + jamoIndex;
1310     } else {
1311         data.jamoCE32s = base->jamoCE32s;
1312     }
1313     data.unsafeBackwardSet = &unsafeBackwardSet;
1314 }
1315
1316 void
1317 CollationDataBuilder::clearContexts() {
1318     contexts.remove();
1319     UnicodeSetIterator iter(contextChars);
1320     while(iter.next()) {
1321         U_ASSERT(!iter.isString());
1322         uint32_t ce32 = utrie2_get32(trie, iter.getCodepoint());
1323         U_ASSERT(isBuilderContextCE32(ce32));
1324         getConditionalCE32ForCE32(ce32)->builtCE32 = Collation::NO_CE32;
1325     }
1326 }
1327
1328 void
1329 CollationDataBuilder::buildContexts(UErrorCode &errorCode) {
1330     if(U_FAILURE(errorCode)) { return; }
1331     // Ignore abandoned lists and the cached builtCE32,
1332     // and build all contexts from scratch.
1333     contexts.remove();
1334     UnicodeSetIterator iter(contextChars);
1335     while(U_SUCCESS(errorCode) && iter.next()) {
1336         U_ASSERT(!iter.isString());
1337         UChar32 c = iter.getCodepoint();
1338         uint32_t ce32 = utrie2_get32(trie, c);
1339         if(!isBuilderContextCE32(ce32)) {
1340             // Impossible: No context data for c in contextChars.
1341             errorCode = U_INTERNAL_PROGRAM_ERROR;
1342             return;
1343         }
1344         ConditionalCE32 *cond = getConditionalCE32ForCE32(ce32);
1345         ce32 = buildContext(cond, errorCode);
1346         utrie2_set32(trie, c, ce32, &errorCode);
1347     }
1348 }
1349
1350 uint32_t
1351 CollationDataBuilder::buildContext(ConditionalCE32 *head, UErrorCode &errorCode) {
1352     if(U_FAILURE(errorCode)) { return 0; }
1353     // The list head must have no context.
1354     U_ASSERT(!head->hasContext());
1355     // The list head must be followed by one or more nodes that all do have context.
1356     U_ASSERT(head->next >= 0);
1357     UCharsTrieBuilder prefixBuilder(errorCode);
1358     UCharsTrieBuilder contractionBuilder(errorCode);
1359     for(ConditionalCE32 *cond = head;; cond = getConditionalCE32(cond->next)) {
1360         // After the list head, the prefix or suffix can be empty, but not both.
1361         U_ASSERT(cond == head || cond->hasContext());
1362         int32_t prefixLength = cond->prefixLength();
1363         UnicodeString prefix(cond->context, 0, prefixLength + 1);
1364         // Collect all contraction suffixes for one prefix.
1365         ConditionalCE32 *firstCond = cond;
1366         ConditionalCE32 *lastCond = cond;
1367         while(cond->next >= 0 &&
1368                 (cond = getConditionalCE32(cond->next))->context.startsWith(prefix)) {
1369             lastCond = cond;
1370         }
1371         uint32_t ce32;
1372         int32_t suffixStart = prefixLength + 1;  // == prefix.length()
1373         if(lastCond->context.length() == suffixStart) {
1374             // One prefix without contraction suffix.
1375             U_ASSERT(firstCond == lastCond);
1376             ce32 = lastCond->ce32;
1377             cond = lastCond;
1378         } else {
1379             // Build the contractions trie.
1380             contractionBuilder.clear();
1381             // Entry for an empty suffix, to be stored before the trie.
1382             uint32_t emptySuffixCE32 = 0;
1383             uint32_t flags = 0;
1384             if(firstCond->context.length() == suffixStart) {
1385                 // There is a mapping for the prefix and the single character c. (p|c)
1386                 // If no other suffix matches, then we return this value.
1387                 emptySuffixCE32 = firstCond->ce32;
1388                 cond = getConditionalCE32(firstCond->next);
1389             } else {
1390                 // There is no mapping for the prefix and just the single character.
1391                 // (There is no p|c, only p|cd, p|ce etc.)
1392                 flags |= Collation::CONTRACT_SINGLE_CP_NO_MATCH;
1393                 // When the prefix matches but none of the prefix-specific suffixes,
1394                 // then we fall back to the mappings with the next-longest prefix,
1395                 // and ultimately to mappings with no prefix.
1396                 // Each fallback might be another set of contractions.
1397                 // For example, if there are mappings for ch, p|cd, p|ce, but not for p|c,
1398                 // then in text "pch" we find the ch contraction.
1399                 for(cond = head;; cond = getConditionalCE32(cond->next)) {
1400                     int32_t length = cond->prefixLength();
1401                     if(length == prefixLength) { break; }
1402                     if(cond->defaultCE32 != Collation::NO_CE32 &&
1403                             (length==0 || prefix.endsWith(cond->context, 1, length))) {
1404                         emptySuffixCE32 = cond->defaultCE32;
1405                     }
1406                 }
1407                 cond = firstCond;
1408             }
1409             // Optimization: Set a flag when
1410             // the first character of every contraction suffix has lccc!=0.
1411             // Short-circuits contraction matching when a normal letter follows.
1412             flags |= Collation::CONTRACT_NEXT_CCC;
1413             // Add all of the non-empty suffixes into the contraction trie.
1414             for(;;) {
1415                 UnicodeString suffix(cond->context, suffixStart);
1416                 uint16_t fcd16 = nfcImpl.getFCD16(suffix.char32At(0));
1417                 if(fcd16 <= 0xff) {
1418                     flags &= ~Collation::CONTRACT_NEXT_CCC;
1419                 }
1420                 fcd16 = nfcImpl.getFCD16(suffix.char32At(suffix.length() - 1));
1421                 if(fcd16 > 0xff) {
1422                     // The last suffix character has lccc!=0, allowing for discontiguous contractions.
1423                     flags |= Collation::CONTRACT_TRAILING_CCC;
1424                 }
1425                 contractionBuilder.add(suffix, (int32_t)cond->ce32, errorCode);
1426                 if(cond == lastCond) { break; }
1427                 cond = getConditionalCE32(cond->next);
1428             }
1429             int32_t index = addContextTrie(emptySuffixCE32, contractionBuilder, errorCode);
1430             if(U_FAILURE(errorCode)) { return 0; }
1431             if(index > Collation::MAX_INDEX) {
1432                 errorCode = U_BUFFER_OVERFLOW_ERROR;
1433                 return 0;
1434             }
1435             ce32 = Collation::makeCE32FromTagAndIndex(Collation::CONTRACTION_TAG, index) | flags;
1436         }
1437         U_ASSERT(cond == lastCond);
1438         firstCond->defaultCE32 = ce32;
1439         if(prefixLength == 0) {
1440             if(cond->next < 0) {
1441                 // No non-empty prefixes, only contractions.
1442                 return ce32;
1443             }
1444         } else {
1445             prefix.remove(0, 1);  // Remove the length unit.
1446             prefix.reverse();
1447             prefixBuilder.add(prefix, (int32_t)ce32, errorCode);
1448             if(cond->next < 0) { break; }
1449         }
1450     }
1451     U_ASSERT(head->defaultCE32 != Collation::NO_CE32);
1452     int32_t index = addContextTrie(head->defaultCE32, prefixBuilder, errorCode);
1453     if(U_FAILURE(errorCode)) { return 0; }
1454     if(index > Collation::MAX_INDEX) {
1455         errorCode = U_BUFFER_OVERFLOW_ERROR;
1456         return 0;
1457     }
1458     return Collation::makeCE32FromTagAndIndex(Collation::PREFIX_TAG, index);
1459 }
1460
1461 int32_t
1462 CollationDataBuilder::addContextTrie(uint32_t defaultCE32, UCharsTrieBuilder &trieBuilder,
1463                                      UErrorCode &errorCode) {
1464     UnicodeString context;
1465     context.append((UChar)(defaultCE32 >> 16)).append((UChar)defaultCE32);
1466     UnicodeString trieString;
1467     context.append(trieBuilder.buildUnicodeString(USTRINGTRIE_BUILD_SMALL, trieString, errorCode));
1468     if(U_FAILURE(errorCode)) { return -1; }
1469     int32_t index = contexts.indexOf(context);
1470     if(index < 0) {
1471         index = contexts.length();
1472         contexts.append(context);
1473     }
1474     return index;
1475 }
1476
1477 void
1478 CollationDataBuilder::buildFastLatinTable(CollationData &data, UErrorCode &errorCode) {
1479     if(U_FAILURE(errorCode) || !fastLatinEnabled) { return; }
1480
1481     delete fastLatinBuilder;
1482     fastLatinBuilder = new CollationFastLatinBuilder(errorCode);
1483     if(fastLatinBuilder == NULL) {
1484         errorCode = U_MEMORY_ALLOCATION_ERROR;
1485         return;
1486     }
1487     if(fastLatinBuilder->forData(data, errorCode)) {
1488         const uint16_t *table = fastLatinBuilder->getTable();
1489         int32_t length = fastLatinBuilder->lengthOfTable();
1490         if(base != NULL && length == base->fastLatinTableLength &&
1491                 uprv_memcmp(table, base->fastLatinTable, length * 2) == 0) {
1492             // Same fast Latin table as in the base, use that one instead.
1493             delete fastLatinBuilder;
1494             fastLatinBuilder = NULL;
1495             table = base->fastLatinTable;
1496         }
1497         data.fastLatinTable = table;
1498         data.fastLatinTableLength = length;
1499     } else {
1500         delete fastLatinBuilder;
1501         fastLatinBuilder = NULL;
1502     }
1503 }
1504
1505 int32_t
1506 CollationDataBuilder::getCEs(const UnicodeString &s, int64_t ces[], int32_t cesLength) {
1507     return getCEs(s, 0, ces, cesLength);
1508 }
1509
1510 int32_t
1511 CollationDataBuilder::getCEs(const UnicodeString &prefix, const UnicodeString &s,
1512                              int64_t ces[], int32_t cesLength) {
1513     int32_t prefixLength = prefix.length();
1514     if(prefixLength == 0) {
1515         return getCEs(s, 0, ces, cesLength);
1516     } else {
1517         return getCEs(prefix + s, prefixLength, ces, cesLength);
1518     }
1519 }
1520
1521 int32_t
1522 CollationDataBuilder::getCEs(const UnicodeString &s, int32_t start,
1523                              int64_t ces[], int32_t cesLength) {
1524     if(collIter == NULL) {
1525         collIter = new DataBuilderCollationIterator(*this);
1526         if(collIter == NULL) { return 0; }
1527     }
1528     return collIter->fetchCEs(s, start, ces, cesLength);
1529 }
1530
1531 U_NAMESPACE_END
1532
1533 #endif  // !UCONFIG_NO_COLLATION