Bug Summary

File:out/../deps/icu-small/source/i18n/collation.h
Warning:line 333, column 23
The result of the left shift is undefined because the left operand is negative

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name collationdatabuilder.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/home/maurizio/node-v18.6.0/out -resource-dir /usr/local/lib/clang/16.0.0 -D V8_DEPRECATION_WARNINGS -D V8_IMMINENT_DEPRECATION_WARNINGS -D _GLIBCXX_USE_CXX11_ABI=1 -D NODE_OPENSSL_CONF_NAME=nodejs_conf -D NODE_OPENSSL_HAS_QUIC -D __STDC_FORMAT_MACROS -D OPENSSL_NO_PINSHARED -D OPENSSL_THREADS -D U_COMMON_IMPLEMENTATION=1 -D U_I18N_IMPLEMENTATION=1 -D U_IO_IMPLEMENTATION=1 -D U_TOOLUTIL_IMPLEMENTATION=1 -D U_ATTRIBUTE_DEPRECATED= -D _CRT_SECURE_NO_DEPRECATE= -D U_STATIC_IMPLEMENTATION=1 -D UCONFIG_NO_SERVICE=1 -D U_ENABLE_DYLOAD=0 -D U_HAVE_STD_STRING=1 -D UCONFIG_NO_BREAK_ITERATION=0 -I ../deps/icu-small/source/common -I ../deps/icu-small/source/i18n -I ../deps/icu-small/source/tools/toolutil -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../include/c++/8/x86_64-redhat-linux -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../include/c++/8/backward -internal-isystem /usr/local/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../x86_64-redhat-linux/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -Wno-unused-parameter -Wno-deprecated-declarations -Wno-strict-aliasing -std=gnu++17 -fdeprecated-macro -fdebug-compilation-dir=/home/maurizio/node-v18.6.0/out -ferror-limit 19 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-08-22-142216-507842-1 -x c++ ../deps/icu-small/source/i18n/collationdatabuilder.cpp

../deps/icu-small/source/i18n/collationdatabuilder.cpp

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

../deps/icu-small/source/i18n/collationdatabuilder.h

→
1// © 2016 and later: Unicode, Inc. and others.
2// License & terms of use: http://www.unicode.org/copyright.html
3/*
4*******************************************************************************
5* Copyright (C) 2012-2014, International Business Machines
6* Corporation and others. All Rights Reserved.
7*******************************************************************************
8* collationdatabuilder.h
9*
10* created on: 2012apr01
11* created by: Markus W. Scherer
12*/
13
14#ifndef __COLLATIONDATABUILDER_H__
15#define __COLLATIONDATABUILDER_H__
16
17#include "unicode/utypes.h"
18
19#if !UCONFIG_NO_COLLATION0
20
21#include "unicode/uniset.h"
22#include "unicode/unistr.h"
23#include "unicode/uversion.h"
24#include "collation.h"
25#include "collationdata.h"
26#include "collationsettings.h"
27#include "normalizer2impl.h"
28#include "utrie2.h"
29#include "uvectr32.h"
30#include "uvectr64.h"
31#include "uvector.h"
32
33U_NAMESPACE_BEGINnamespace icu_71 {
34
35struct ConditionalCE32;
36
37class CollationFastLatinBuilder;
38class CopyHelper;
39class DataBuilderCollationIterator;
40class UCharsTrieBuilder;
41
42/**
43 * Low-level CollationData builder.
44 * Takes (character, CE) pairs and builds them into runtime data structures.
45 * Supports characters with context prefixes and contraction suffixes.
46 */
47class U_I18N_API CollationDataBuilder : public UObject {
48public:
49 /**
50 * Collation element modifier. Interface class for a modifier
51 * that changes a tailoring builder's temporary CEs to final CEs.
52 * Called for every non-special CE32 and every expansion CE.
53 */
54 class CEModifier : public UObject {
55 public:
56 virtual ~CEModifier();
57 /** Returns a new CE to replace the non-special input CE32, or else Collation::NO_CE. */
58 virtual int64_t modifyCE32(uint32_t ce32) const = 0;
59 /** Returns a new CE to replace the input CE, or else Collation::NO_CE. */
60 virtual int64_t modifyCE(int64_t ce) const = 0;
61 };
62
63 CollationDataBuilder(UErrorCode &errorCode);
64
65 virtual ~CollationDataBuilder();
66
67 void initForTailoring(const CollationData *b, UErrorCode &errorCode);
68
69 virtual UBool isCompressibleLeadByte(uint32_t b) const;
70
71 inline UBool isCompressiblePrimary(uint32_t p) const {
72 return isCompressibleLeadByte(p >> 24);
73 }
74
75 /**
76 * @return true if this builder has mappings (e.g., add() has been called)
77 */
78 UBool hasMappings() const { return modified; }
79
80 /**
81 * @return true if c has CEs in this builder
82 */
83 UBool isAssigned(UChar32 c) const;
84
85 /**
86 * @return the three-byte primary if c maps to a single such CE and has no context data,
87 * otherwise returns 0.
88 */
89 uint32_t getLongPrimaryIfSingleCE(UChar32 c) const;
90
91 /**
92 * @return the single CE for c.
93 * Sets an error code if c does not have a single CE.
94 */
95 int64_t getSingleCE(UChar32 c, UErrorCode &errorCode) const;
96
97 void add(const UnicodeString &prefix, const UnicodeString &s,
98 const int64_t ces[], int32_t cesLength,
99 UErrorCode &errorCode);
100
101 /**
102 * Encodes the ces as either the returned ce32 by itself,
103 * or by storing an expansion, with the returned ce32 referring to that.
104 *
105 * add(p, s, ces, cesLength) = addCE32(p, s, encodeCEs(ces, cesLength))
106 */
107 virtual uint32_t encodeCEs(const int64_t ces[], int32_t cesLength, UErrorCode &errorCode);
108 void addCE32(const UnicodeString &prefix, const UnicodeString &s,
109 uint32_t ce32, UErrorCode &errorCode);
110
111 /**
112 * Sets three-byte-primary CEs for a range of code points in code point order,
113 * if it is worth doing; otherwise no change is made.
114 * None of the code points in the range should have complex mappings so far
115 * (expansions/contractions/prefixes).
116 * @param start first code point
117 * @param end last code point (inclusive)
118 * @param primary primary weight for 'start'
119 * @param step per-code point primary-weight increment
120 * @param errorCode ICU in/out error code
121 * @return true if an OFFSET_TAG range was used for start..end
122 */
123 UBool maybeSetPrimaryRange(UChar32 start, UChar32 end,
124 uint32_t primary, int32_t step,
125 UErrorCode &errorCode);
126
127 /**
128 * Sets three-byte-primary CEs for a range of code points in code point order.
129 * Sets range values if that is worth doing, or else individual values.
130 * None of the code points in the range should have complex mappings so far
131 * (expansions/contractions/prefixes).
132 * @param start first code point
133 * @param end last code point (inclusive)
134 * @param primary primary weight for 'start'
135 * @param step per-code point primary-weight increment
136 * @param errorCode ICU in/out error code
137 * @return the next primary after 'end': start primary incremented by ((end-start)+1)*step
138 */
139 uint32_t setPrimaryRangeAndReturnNext(UChar32 start, UChar32 end,
140 uint32_t primary, int32_t step,
141 UErrorCode &errorCode);
142
143 /**
144 * Copies all mappings from the src builder, with modifications.
145 * This builder here must not be built yet, and should be empty.
146 */
147 void copyFrom(const CollationDataBuilder &src, const CEModifier &modifier,
148 UErrorCode &errorCode);
149
150 void optimize(const UnicodeSet &set, UErrorCode &errorCode);
151 void suppressContractions(const UnicodeSet &set, UErrorCode &errorCode);
152
153 void enableFastLatin() { fastLatinEnabled = true; }
154 virtual void build(CollationData &data, UErrorCode &errorCode);
155
156 /**
157 * Looks up CEs for s and appends them to the ces array.
158 * Does not handle normalization: s should be in FCD form.
159 *
160 * Does not write completely ignorable CEs.
161 * Does not write beyond Collation::MAX_EXPANSION_LENGTH.
162 *
163 * @return incremented cesLength
164 */
165 int32_t getCEs(const UnicodeString &s, int64_t ces[], int32_t cesLength);
166 int32_t getCEs(const UnicodeString &prefix, const UnicodeString &s,
167 int64_t ces[], int32_t cesLength);
168
169protected:
170 friend class CopyHelper;
171 friend class DataBuilderCollationIterator;
172
173 uint32_t getCE32FromOffsetCE32(UBool fromBase, UChar32 c, uint32_t ce32) const;
174
175 int32_t addCE(int64_t ce, UErrorCode &errorCode);
176 int32_t addCE32(uint32_t ce32, UErrorCode &errorCode);
177 int32_t addConditionalCE32(const UnicodeString &context, uint32_t ce32, UErrorCode &errorCode);
178
179 inline ConditionalCE32 *getConditionalCE32(int32_t index) const {
180 return static_cast<ConditionalCE32 *>(conditionalCE32s[index]);
181 }
182 inline ConditionalCE32 *getConditionalCE32ForCE32(uint32_t ce32) const {
183 return getConditionalCE32(Collation::indexFromCE32(ce32));
184 }
185
186 static uint32_t makeBuilderContextCE32(int32_t index) {
187 return Collation::makeCE32FromTagAndIndex(Collation::BUILDER_DATA_TAG, index);
19
←
Passing the value -1 via 2nd parameter 'index'
→
20
←
Calling 'Collation::makeCE32FromTagAndIndex'
→
188 }
189 static inline UBool isBuilderContextCE32(uint32_t ce32) {
190 return Collation::hasCE32Tag(ce32, Collation::BUILDER_DATA_TAG);
191 }
192
193 static uint32_t encodeOneCEAsCE32(int64_t ce);
194 uint32_t encodeOneCE(int64_t ce, UErrorCode &errorCode);
195 uint32_t encodeExpansion(const int64_t ces[], int32_t length, UErrorCode &errorCode);
196 uint32_t encodeExpansion32(const int32_t newCE32s[], int32_t length, UErrorCode &errorCode);
197
198 uint32_t copyFromBaseCE32(UChar32 c, uint32_t ce32, UBool withContext, UErrorCode &errorCode);
199 /**
200 * Copies base contractions to a list of ConditionalCE32.
201 * Sets cond->next to the index of the first new item
202 * and returns the index of the last new item.
203 */
204 int32_t copyContractionsFromBaseCE32(UnicodeString &context, UChar32 c, uint32_t ce32,
205 ConditionalCE32 *cond, UErrorCode &errorCode);
206
207 UBool getJamoCE32s(uint32_t jamoCE32s[], UErrorCode &errorCode);
208 void setDigitTags(UErrorCode &errorCode);
209 void setLeadSurrogates(UErrorCode &errorCode);
210
211 void buildMappings(CollationData &data, UErrorCode &errorCode);
212
213 void clearContexts();
214 void buildContexts(UErrorCode &errorCode);
215 uint32_t buildContext(ConditionalCE32 *head, UErrorCode &errorCode);
216 int32_t addContextTrie(uint32_t defaultCE32, UCharsTrieBuilder &trieBuilder,
217 UErrorCode &errorCode);
218
219 void buildFastLatinTable(CollationData &data, UErrorCode &errorCode);
220
221 int32_t getCEs(const UnicodeString &s, int32_t start, int64_t ces[], int32_t cesLength);
222
223 static UChar32 jamoCpFromIndex(int32_t i) {
224 // 0 <= i < CollationData::JAMO_CE32S_LENGTH = 19 + 21 + 27
225 if(i < Hangul::JAMO_L_COUNT) { return Hangul::JAMO_L_BASE + i; }
226 i -= Hangul::JAMO_L_COUNT;
227 if(i < Hangul::JAMO_V_COUNT) { return Hangul::JAMO_V_BASE + i; }
228 i -= Hangul::JAMO_V_COUNT;
229 // i < 27
230 return Hangul::JAMO_T_BASE + 1 + i;
231 }
232
233 /** @see Collation::BUILDER_DATA_TAG */
234 static const uint32_t IS_BUILDER_JAMO_CE32 = 0x100;
235
236 const Normalizer2Impl &nfcImpl;
237 const CollationData *base;
238 const CollationSettings *baseSettings;
239 UTrie2 *trie;
240 UVector32 ce32s;
241 UVector64 ce64s;
242 UVector conditionalCE32s; // vector of ConditionalCE32
243 // Characters that have context (prefixes or contraction suffixes).
244 UnicodeSet contextChars;
245 // Serialized UCharsTrie structures for finalized contexts.
246 UnicodeString contexts;
247 UnicodeSet unsafeBackwardSet;
248 UBool modified;
249
250 UBool fastLatinEnabled;
251 CollationFastLatinBuilder *fastLatinBuilder;
252
253 DataBuilderCollationIterator *collIter;
254};
255
256U_NAMESPACE_END}
257
258#endif // !UCONFIG_NO_COLLATION
259#endif // __COLLATIONDATABUILDER_H__
←

../deps/icu-small/source/i18n/collation.h

1// © 2016 and later: Unicode, Inc. and others.
2// License & terms of use: http://www.unicode.org/copyright.html
3/*
4*******************************************************************************
5* Copyright (C) 2010-2015, International Business Machines
6* Corporation and others. All Rights Reserved.
7*******************************************************************************
8* collation.h
9*
10* created on: 2010oct27
11* created by: Markus W. Scherer
12*/
13
14#ifndef __COLLATION_H__
15#define __COLLATION_H__
16
17#include "unicode/utypes.h"
18
19#if !UCONFIG_NO_COLLATION0
20
21U_NAMESPACE_BEGINnamespace icu_71 {
22
23/**
24 * Collation v2 basic definitions and static helper functions.
25 *
26 * Data structures except for expansion tables store 32-bit CEs which are
27 * either specials (see tags below) or are compact forms of 64-bit CEs.
28 */
29class U_I18N_API Collation {
30public:
31 // Special sort key bytes for all levels.
32 static const uint8_t TERMINATOR_BYTE = 0;
33 static const uint8_t LEVEL_SEPARATOR_BYTE = 1;
34
35 /** The secondary/tertiary lower limit for tailoring before any root elements. */
36 static const uint32_t BEFORE_WEIGHT16 = 0x0100;
37
38 /**
39 * Merge-sort-key separator.
40 * Same as the unique primary and identical-level weights of U+FFFE.
41 * Must not be used as primary compression low terminator.
42 * Otherwise usable.
43 */
44 static const uint8_t MERGE_SEPARATOR_BYTE = 2;
45 static const uint32_t MERGE_SEPARATOR_PRIMARY = 0x02000000; // U+FFFE
46 static const uint32_t MERGE_SEPARATOR_CE32 = 0x02000505; // U+FFFE
47
48 /**
49 * Primary compression low terminator, must be greater than MERGE_SEPARATOR_BYTE.
50 * Reserved value in primary second byte if the lead byte is compressible.
51 * Otherwise usable in all CE weight bytes.
52 */
53 static const uint8_t PRIMARY_COMPRESSION_LOW_BYTE = 3;
54 /**
55 * Primary compression high terminator.
56 * Reserved value in primary second byte if the lead byte is compressible.
57 * Otherwise usable in all CE weight bytes.
58 */
59 static const uint8_t PRIMARY_COMPRESSION_HIGH_BYTE = 0xff;
60
61 /** Default secondary/tertiary weight lead byte. */
62 static const uint8_t COMMON_BYTE = 5;
63 static const uint32_t COMMON_WEIGHT16 = 0x0500;
64 /** Middle 16 bits of a CE with a common secondary weight. */
65 static const uint32_t COMMON_SECONDARY_CE = 0x05000000;
66 /** Lower 16 bits of a CE with a common tertiary weight. */
67 static const uint32_t COMMON_TERTIARY_CE = 0x0500;
68 /** Lower 32 bits of a CE with common secondary and tertiary weights. */
69 static const uint32_t COMMON_SEC_AND_TER_CE = 0x05000500;
70
71 static const uint32_t SECONDARY_MASK = 0xffff0000;
72 static const uint32_t CASE_MASK = 0xc000;
73 static const uint32_t SECONDARY_AND_CASE_MASK = SECONDARY_MASK | CASE_MASK;
74 /** Only the 2*6 bits for the pure tertiary weight. */
75 static const uint32_t ONLY_TERTIARY_MASK = 0x3f3f;
76 /** Only the secondary & tertiary bits; no case, no quaternary. */
77 static const uint32_t ONLY_SEC_TER_MASK = SECONDARY_MASK | ONLY_TERTIARY_MASK;
78 /** Case bits and tertiary bits. */
79 static const uint32_t CASE_AND_TERTIARY_MASK = CASE_MASK | ONLY_TERTIARY_MASK;
80 static const uint32_t QUATERNARY_MASK = 0xc0;
81 /** Case bits and quaternary bits. */
82 static const uint32_t CASE_AND_QUATERNARY_MASK = CASE_MASK | QUATERNARY_MASK;
83
84 static const uint8_t UNASSIGNED_IMPLICIT_BYTE = 0xfe; // compressible
85 /**
86 * First unassigned: AlphabeticIndex overflow boundary.
87 * We want a 3-byte primary so that it fits into the root elements table.
88 *
89 * This 3-byte primary will not collide with
90 * any unassigned-implicit 4-byte primaries because
91 * the first few hundred Unicode code points all have real mappings.
92 */
93 static const uint32_t FIRST_UNASSIGNED_PRIMARY = 0xfe040200;
94
95 static const uint8_t TRAIL_WEIGHT_BYTE = 0xff; // not compressible
96 static const uint32_t FIRST_TRAILING_PRIMARY = 0xff020200; // [first trailing]
97 static const uint32_t MAX_PRIMARY = 0xffff0000; // U+FFFF
98 static const uint32_t MAX_REGULAR_CE32 = 0xffff0505; // U+FFFF
99
100 // CE32 value for U+FFFD as well as illegal UTF-8 byte sequences (which behave like U+FFFD).
101 // We use the third-highest primary weight for U+FFFD (as in UCA 6.3+).
102 static const uint32_t FFFD_PRIMARY = MAX_PRIMARY - 0x20000;
103 static const uint32_t FFFD_CE32 = MAX_REGULAR_CE32 - 0x20000;
104
105 /**
106 * A CE32 is special if its low byte is this or greater.
107 * Impossible case bits 11 mark special CE32s.
108 * This value itself is used to indicate a fallback to the base collator.
109 */
110 static const uint8_t SPECIAL_CE32_LOW_BYTE = 0xc0;
111 static const uint32_t FALLBACK_CE32 = SPECIAL_CE32_LOW_BYTE;
112 /**
113 * Low byte of a long-primary special CE32.
114 */
115 static const uint8_t LONG_PRIMARY_CE32_LOW_BYTE = 0xc1; // SPECIAL_CE32_LOW_BYTE | LONG_PRIMARY_TAG
116
117 static const uint32_t UNASSIGNED_CE32 = 0xffffffff; // Compute an unassigned-implicit CE.
118
119 static const uint32_t NO_CE32 = 1;
120
121 /** No CE: End of input. Only used in runtime code, not stored in data. */
122 static const uint32_t NO_CE_PRIMARY = 1; // not a left-adjusted weight
123 static const uint32_t NO_CE_WEIGHT16 = 0x0100; // weight of LEVEL_SEPARATOR_BYTE
124 static const int64_t NO_CE = INT64_C(0x101000100)0x101000100L; // NO_CE_PRIMARY, NO_CE_WEIGHT16, NO_CE_WEIGHT16
125
126 /** Sort key levels. */
127 enum Level {
128 /** Unspecified level. */
129 NO_LEVEL,
130 PRIMARY_LEVEL,
131 SECONDARY_LEVEL,
132 CASE_LEVEL,
133 TERTIARY_LEVEL,
134 QUATERNARY_LEVEL,
135 IDENTICAL_LEVEL,
136 /** Beyond sort key bytes. */
137 ZERO_LEVEL
138 };
139
140 /**
141 * Sort key level flags: xx_FLAG = 1 << xx_LEVEL.
142 * In Java, use enum Level with flag() getters, or use EnumSet rather than hand-made bit sets.
143 */
144 static const uint32_t NO_LEVEL_FLAG = 1;
145 static const uint32_t PRIMARY_LEVEL_FLAG = 2;
146 static const uint32_t SECONDARY_LEVEL_FLAG = 4;
147 static const uint32_t CASE_LEVEL_FLAG = 8;
148 static const uint32_t TERTIARY_LEVEL_FLAG = 0x10;
149 static const uint32_t QUATERNARY_LEVEL_FLAG = 0x20;
150 static const uint32_t IDENTICAL_LEVEL_FLAG = 0x40;
151 static const uint32_t ZERO_LEVEL_FLAG = 0x80;
152
153 /**
154 * Special-CE32 tags, from bits 3..0 of a special 32-bit CE.
155 * Bits 31..8 are available for tag-specific data.
156 * Bits 5..4: Reserved. May be used in the future to indicate lccc!=0 and tccc!=0.
157 */
158 enum {
159 /**
160 * Fall back to the base collator.
161 * This is the tag value in SPECIAL_CE32_LOW_BYTE and FALLBACK_CE32.
162 * Bits 31..8: Unused, 0.
163 */
164 FALLBACK_TAG = 0,
165 /**
166 * Long-primary CE with COMMON_SEC_AND_TER_CE.
167 * Bits 31..8: Three-byte primary.
168 */
169 LONG_PRIMARY_TAG = 1,
170 /**
171 * Long-secondary CE with zero primary.
172 * Bits 31..16: Secondary weight.
173 * Bits 15.. 8: Tertiary weight.
174 */
175 LONG_SECONDARY_TAG = 2,
176 /**
177 * Unused.
178 * May be used in the future for single-byte secondary CEs (SHORT_SECONDARY_TAG),
179 * storing the secondary in bits 31..24, the ccc in bits 23..16,
180 * and the tertiary in bits 15..8.
181 */
182 RESERVED_TAG_3 = 3,
183 /**
184 * Latin mini expansions of two simple CEs [pp, 05, tt] [00, ss, 05].
185 * Bits 31..24: Single-byte primary weight pp of the first CE.
186 * Bits 23..16: Tertiary weight tt of the first CE.
187 * Bits 15.. 8: Secondary weight ss of the second CE.
188 */
189 LATIN_EXPANSION_TAG = 4,
190 /**
191 * Points to one or more simple/long-primary/long-secondary 32-bit CE32s.
192 * Bits 31..13: Index into uint32_t table.
193 * Bits 12.. 8: Length=1..31.
194 */
195 EXPANSION32_TAG = 5,
196 /**
197 * Points to one or more 64-bit CEs.
198 * Bits 31..13: Index into CE table.
199 * Bits 12.. 8: Length=1..31.
200 */
201 EXPANSION_TAG = 6,
202 /**
203 * Builder data, used only in the CollationDataBuilder, not in runtime data.
204 *
205 * If bit 8 is 0: Builder context, points to a list of context-sensitive mappings.
206 * Bits 31..13: Index to the builder's list of ConditionalCE32 for this character.
207 * Bits 12.. 9: Unused, 0.
208 *
209 * If bit 8 is 1 (IS_BUILDER_JAMO_CE32): Builder-only jamoCE32 value.
210 * The builder fetches the Jamo CE32 from the trie.
211 * Bits 31..13: Jamo code point.
212 * Bits 12.. 9: Unused, 0.
213 */
214 BUILDER_DATA_TAG = 7,
215 /**
216 * Points to prefix trie.
217 * Bits 31..13: Index into prefix/contraction data.
218 * Bits 12.. 8: Unused, 0.
219 */
220 PREFIX_TAG = 8,
221 /**
222 * Points to contraction data.
223 * Bits 31..13: Index into prefix/contraction data.
224 * Bits 12..11: Unused, 0.
225 * Bit 10: CONTRACT_TRAILING_CCC flag.
226 * Bit 9: CONTRACT_NEXT_CCC flag.
227 * Bit 8: CONTRACT_SINGLE_CP_NO_MATCH flag.
228 */
229 CONTRACTION_TAG = 9,
230 /**
231 * Decimal digit.
232 * Bits 31..13: Index into uint32_t table for non-numeric-collation CE32.
233 * Bit 12: Unused, 0.
234 * Bits 11.. 8: Digit value 0..9.
235 */
236 DIGIT_TAG = 10,
237 /**
238 * Tag for U+0000, for moving the NUL-termination handling
239 * from the regular fastpath into specials-handling code.
240 * Bits 31..8: Unused, 0.
241 */
242 U0000_TAG = 11,
243 /**
244 * Tag for a Hangul syllable.
245 * Bits 31..9: Unused, 0.
246 * Bit 8: HANGUL_NO_SPECIAL_JAMO flag.
247 */
248 HANGUL_TAG = 12,
249 /**
250 * Tag for a lead surrogate code unit.
251 * Optional optimization for UTF-16 string processing.
252 * Bits 31..10: Unused, 0.
253 * 9.. 8: =0: All associated supplementary code points are unassigned-implicit.
254 * =1: All associated supplementary code points fall back to the base data.
255 * else: (Normally 2) Look up the data for the supplementary code point.
256 */
257 LEAD_SURROGATE_TAG = 13,
258 /**
259 * Tag for CEs with primary weights in code point order.
260 * Bits 31..13: Index into CE table, for one data "CE".
261 * Bits 12.. 8: Unused, 0.
262 *
263 * This data "CE" has the following bit fields:
264 * Bits 63..32: Three-byte primary pppppp00.
265 * 31.. 8: Start/base code point of the in-order range.
266 * 7: Flag isCompressible primary.
267 * 6.. 0: Per-code point primary-weight increment.
268 */
269 OFFSET_TAG = 14,
270 /**
271 * Implicit CE tag. Compute an unassigned-implicit CE.
272 * All bits are set (UNASSIGNED_CE32=0xffffffff).
273 */
274 IMPLICIT_TAG = 15
275 };
276
277 static UBool isAssignedCE32(uint32_t ce32) {
278 return ce32 != FALLBACK_CE32 && ce32 != UNASSIGNED_CE32;
279 }
280
281 /**
282 * We limit the number of CEs in an expansion
283 * so that we can use a small number of length bits in the data structure,
284 * and so that an implementation can copy CEs at runtime without growing a destination buffer.
285 */
286 static const int32_t MAX_EXPANSION_LENGTH = 31;
287 static const int32_t MAX_INDEX = 0x7ffff;
288
289 /**
290 * Set if there is no match for the single (no-suffix) character itself.
291 * This is only possible if there is a prefix.
292 * In this case, discontiguous contraction matching cannot add combining marks
293 * starting from an empty suffix.
294 * The default CE32 is used anyway if there is no suffix match.
295 */
296 static const uint32_t CONTRACT_SINGLE_CP_NO_MATCH = 0x100;
297 /** Set if the first character of every contraction suffix has lccc!=0. */
298 static const uint32_t CONTRACT_NEXT_CCC = 0x200;
299 /** Set if any contraction suffix ends with lccc!=0. */
300 static const uint32_t CONTRACT_TRAILING_CCC = 0x400;
301
302 /** For HANGUL_TAG: None of its Jamo CE32s isSpecialCE32(). */
303 static const uint32_t HANGUL_NO_SPECIAL_JAMO = 0x100;
304
305 static const uint32_t LEAD_ALL_UNASSIGNED = 0;
306 static const uint32_t LEAD_ALL_FALLBACK = 0x100;
307 static const uint32_t LEAD_MIXED = 0x200;
308 static const uint32_t LEAD_TYPE_MASK = 0x300;
309
310 static uint32_t makeLongPrimaryCE32(uint32_t p) { return p | LONG_PRIMARY_CE32_LOW_BYTE; }
311
312 /** Turns the long-primary CE32 into a primary weight pppppp00. */
313 static inline uint32_t primaryFromLongPrimaryCE32(uint32_t ce32) {
314 return ce32 & 0xffffff00;
315 }
316 static inline int64_t ceFromLongPrimaryCE32(uint32_t ce32) {
317 return ((int64_t)(ce32 & 0xffffff00) << 32) | COMMON_SEC_AND_TER_CE;
318 }
319
320 static uint32_t makeLongSecondaryCE32(uint32_t lower32) {
321 return lower32 | SPECIAL_CE32_LOW_BYTE | LONG_SECONDARY_TAG;
322 }
323 static inline int64_t ceFromLongSecondaryCE32(uint32_t ce32) {
324 return ce32 & 0xffffff00;
325 }
326
327 /** Makes a special CE32 with tag, index and length. */
328 static uint32_t makeCE32FromTagIndexAndLength(int32_t tag, int32_t index, int32_t length) {
329 return (index << 13) | (length << 8) | SPECIAL_CE32_LOW_BYTE | tag;
330 }
331 /** Makes a special CE32 with only tag and index. */
332 static uint32_t makeCE32FromTagAndIndex(int32_t tag, int32_t index) {
333 return (index << 13) | SPECIAL_CE32_LOW_BYTE | tag;
21
←
The result of the left shift is undefined because the left operand is negative
334 }
335
336 static inline UBool isSpecialCE32(uint32_t ce32) {
337 return (ce32 & 0xff) >= SPECIAL_CE32_LOW_BYTE;
338 }
339
340 static inline int32_t tagFromCE32(uint32_t ce32) {
341 return (int32_t)(ce32 & 0xf);
342 }
343
344 static inline UBool hasCE32Tag(uint32_t ce32, int32_t tag) {
345 return isSpecialCE32(ce32) && tagFromCE32(ce32) == tag;
346 }
347
348 static inline UBool isLongPrimaryCE32(uint32_t ce32) {
349 return hasCE32Tag(ce32, LONG_PRIMARY_TAG);
350 }
351
352 static UBool isSimpleOrLongCE32(uint32_t ce32) {
353 return !isSpecialCE32(ce32) ||
354 tagFromCE32(ce32) == LONG_PRIMARY_TAG ||
355 tagFromCE32(ce32) == LONG_SECONDARY_TAG;
356 }
357
358 /**
359 * @return true if the ce32 yields one or more CEs without further data lookups
360 */
361 static UBool isSelfContainedCE32(uint32_t ce32) {
362 return !isSpecialCE32(ce32) ||
363 tagFromCE32(ce32) == LONG_PRIMARY_TAG ||
364 tagFromCE32(ce32) == LONG_SECONDARY_TAG ||
365 tagFromCE32(ce32) == LATIN_EXPANSION_TAG;
366 }
367
368 static inline UBool isPrefixCE32(uint32_t ce32) {
369 return hasCE32Tag(ce32, PREFIX_TAG);
370 }
371
372 static inline UBool isContractionCE32(uint32_t ce32) {
373 return hasCE32Tag(ce32, CONTRACTION_TAG);
374 }
375
376 static inline UBool ce32HasContext(uint32_t ce32) {
377 return isSpecialCE32(ce32) &&
378 (tagFromCE32(ce32) == PREFIX_TAG ||
379 tagFromCE32(ce32) == CONTRACTION_TAG);
380 }
381
382 /**
383 * Get the first of the two Latin-expansion CEs encoded in ce32.
384 * @see LATIN_EXPANSION_TAG
385 */
386 static inline int64_t latinCE0FromCE32(uint32_t ce32) {
387 return ((int64_t)(ce32 & 0xff000000) << 32) | COMMON_SECONDARY_CE | ((ce32 & 0xff0000) >> 8);
388 }
389
390 /**
391 * Get the second of the two Latin-expansion CEs encoded in ce32.
392 * @see LATIN_EXPANSION_TAG
393 */
394 static inline int64_t latinCE1FromCE32(uint32_t ce32) {
395 return ((ce32 & 0xff00) << 16) | COMMON_TERTIARY_CE;
396 }
397
398 /**
399 * Returns the data index from a special CE32.
400 */
401 static inline int32_t indexFromCE32(uint32_t ce32) {
402 return (int32_t)(ce32 >> 13);
403 }
404
405 /**
406 * Returns the data length from a ce32.
407 */
408 static inline int32_t lengthFromCE32(uint32_t ce32) {
409 return (ce32 >> 8) & 31;
410 }
411
412 /**
413 * Returns the digit value from a DIGIT_TAG ce32.
414 */
415 static inline char digitFromCE32(uint32_t ce32) {
416 return (char)((ce32 >> 8) & 0xf);
417 }
418
419 /** Returns a 64-bit CE from a simple CE32 (not special). */
420 static inline int64_t ceFromSimpleCE32(uint32_t ce32) {
421 // normal form ppppsstt -> pppp0000ss00tt00
422 // assert (ce32 & 0xff) < SPECIAL_CE32_LOW_BYTE
423 return ((int64_t)(ce32 & 0xffff0000) << 32) | ((ce32 & 0xff00) << 16) | ((ce32 & 0xff) << 8);
424 }
425
426 /** Returns a 64-bit CE from a simple/long-primary/long-secondary CE32. */
427 static inline int64_t ceFromCE32(uint32_t ce32) {
428 uint32_t tertiary = ce32 & 0xff;
429 if(tertiary < SPECIAL_CE32_LOW_BYTE) {
430 // normal form ppppsstt -> pppp0000ss00tt00
431 return ((int64_t)(ce32 & 0xffff0000) << 32) | ((ce32 & 0xff00) << 16) | (tertiary << 8);
432 } else {
433 ce32 -= tertiary;
434 if((tertiary & 0xf) == LONG_PRIMARY_TAG) {
435 // long-primary form ppppppC1 -> pppppp00050000500
436 return ((int64_t)ce32 << 32) | COMMON_SEC_AND_TER_CE;
437 } else {
438 // long-secondary form ssssttC2 -> 00000000sssstt00
439 // assert (tertiary & 0xf) == LONG_SECONDARY_TAG
440 return ce32;
441 }
442 }
443 }
444
445 /** Creates a CE from a primary weight. */
446 static inline int64_t makeCE(uint32_t p) {
447 return ((int64_t)p << 32) | COMMON_SEC_AND_TER_CE;
448 }
449 /**
450 * Creates a CE from a primary weight,
451 * 16-bit secondary/tertiary weights, and a 2-bit quaternary.
452 */
453 static inline int64_t makeCE(uint32_t p, uint32_t s, uint32_t t, uint32_t q) {
454 return ((int64_t)p << 32) | (s << 16) | t | (q << 6);
455 }
456
457 /**
458 * Increments a 2-byte primary by a code point offset.
459 */
460 static uint32_t incTwoBytePrimaryByOffset(uint32_t basePrimary, UBool isCompressible,
461 int32_t offset);
462
463 /**
464 * Increments a 3-byte primary by a code point offset.
465 */
466 static uint32_t incThreeBytePrimaryByOffset(uint32_t basePrimary, UBool isCompressible,
467 int32_t offset);
468
469 /**
470 * Decrements a 2-byte primary by one range step (1..0x7f).
471 */
472 static uint32_t decTwoBytePrimaryByOneStep(uint32_t basePrimary, UBool isCompressible, int32_t step);
473
474 /**
475 * Decrements a 3-byte primary by one range step (1..0x7f).
476 */
477 static uint32_t decThreeBytePrimaryByOneStep(uint32_t basePrimary, UBool isCompressible, int32_t step);
478
479 /**
480 * Computes a 3-byte primary for c's OFFSET_TAG data "CE".
481 */
482 static uint32_t getThreeBytePrimaryForOffsetData(UChar32 c, int64_t dataCE);
483
484 /**
485 * Returns the unassigned-character implicit primary weight for any valid code point c.
486 */
487 static uint32_t unassignedPrimaryFromCodePoint(UChar32 c);
488
489 static inline int64_t unassignedCEFromCodePoint(UChar32 c) {
490 return makeCE(unassignedPrimaryFromCodePoint(c));
491 }
492
493private:
494 Collation(); // No instantiation.
495};
496
497U_NAMESPACE_END}
498
499#endif // !UCONFIG_NO_COLLATION
500#endif // __COLLATION_H__