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