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