Line data Source code
1 : // © 2016 and later: Unicode, Inc. and others.
2 : // License & terms of use: http://www.unicode.org/copyright.html
3 : /*
4 : *******************************************************************************
5 : * Copyright (C) 2013-2014, International Business Machines
6 : * Corporation and others. All Rights Reserved.
7 : *******************************************************************************
8 : * collationbuilder.h
9 : *
10 : * created on: 2013may06
11 : * created by: Markus W. Scherer
12 : */
13 :
14 : #ifndef __COLLATIONBUILDER_H__
15 : #define __COLLATIONBUILDER_H__
16 :
17 : #include "unicode/utypes.h"
18 :
19 : #if !UCONFIG_NO_COLLATION
20 :
21 : #include "unicode/uniset.h"
22 : #include "unicode/unistr.h"
23 : #include "collationrootelements.h"
24 : #include "collationruleparser.h"
25 : #include "uvectr32.h"
26 : #include "uvectr64.h"
27 :
28 : struct UParseError;
29 :
30 : U_NAMESPACE_BEGIN
31 :
32 : struct CollationData;
33 : struct CollationTailoring;
34 :
35 : class CEFinalizer;
36 : class CollationDataBuilder;
37 : class Normalizer2;
38 : class Normalizer2Impl;
39 :
40 : class U_I18N_API CollationBuilder : public CollationRuleParser::Sink {
41 : public:
42 : CollationBuilder(const CollationTailoring *base, UErrorCode &errorCode);
43 : virtual ~CollationBuilder();
44 :
45 : void disableFastLatin() { fastLatinEnabled = FALSE; }
46 :
47 : CollationTailoring *parseAndBuild(const UnicodeString &ruleString,
48 : const UVersionInfo rulesVersion,
49 : CollationRuleParser::Importer *importer,
50 : UParseError *outParseError,
51 : UErrorCode &errorCode);
52 :
53 0 : const char *getErrorReason() const { return errorReason; }
54 :
55 : private:
56 : friend class CEFinalizer;
57 :
58 : /** Implements CollationRuleParser::Sink. */
59 : virtual void addReset(int32_t strength, const UnicodeString &str,
60 : const char *&errorReason, UErrorCode &errorCode);
61 : /**
62 : * Returns the secondary or tertiary weight preceding the current node's weight.
63 : * node=nodes[index].
64 : */
65 : uint32_t getWeight16Before(int32_t index, int64_t node, int32_t level);
66 :
67 : int64_t getSpecialResetPosition(const UnicodeString &str,
68 : const char *&parserErrorReason, UErrorCode &errorCode);
69 :
70 : /** Implements CollationRuleParser::Sink. */
71 : virtual void addRelation(int32_t strength, const UnicodeString &prefix,
72 : const UnicodeString &str, const UnicodeString &extension,
73 : const char *&errorReason, UErrorCode &errorCode);
74 :
75 : /**
76 : * Picks one of the current CEs and finds or inserts a node in the graph
77 : * for the CE + strength.
78 : */
79 : int32_t findOrInsertNodeForCEs(int32_t strength, const char *&parserErrorReason,
80 : UErrorCode &errorCode);
81 : int32_t findOrInsertNodeForRootCE(int64_t ce, int32_t strength, UErrorCode &errorCode);
82 : /** Finds or inserts the node for a root CE's primary weight. */
83 : int32_t findOrInsertNodeForPrimary(uint32_t p, UErrorCode &errorCode);
84 : /** Finds or inserts the node for a secondary or tertiary weight. */
85 : int32_t findOrInsertWeakNode(int32_t index, uint32_t weight16, int32_t level,
86 : UErrorCode &errorCode);
87 :
88 : /**
89 : * Makes and inserts a new tailored node into the list, after the one at index.
90 : * Skips over nodes of weaker strength to maintain collation order
91 : * ("postpone insertion").
92 : * @return the new node's index
93 : */
94 : int32_t insertTailoredNodeAfter(int32_t index, int32_t strength, UErrorCode &errorCode);
95 :
96 : /**
97 : * Inserts a new node into the list, between list-adjacent items.
98 : * The node's previous and next indexes must not be set yet.
99 : * @return the new node's index
100 : */
101 : int32_t insertNodeBetween(int32_t index, int32_t nextIndex, int64_t node,
102 : UErrorCode &errorCode);
103 :
104 : /**
105 : * Finds the node which implies or contains a common=05 weight of the given strength
106 : * (secondary or tertiary), if the current node is stronger.
107 : * Skips weaker nodes and tailored nodes if the current node is stronger
108 : * and is followed by an explicit-common-weight node.
109 : * Always returns the input index if that node is no stronger than the given strength.
110 : */
111 : int32_t findCommonNode(int32_t index, int32_t strength) const;
112 :
113 : void setCaseBits(const UnicodeString &nfdString,
114 : const char *&parserErrorReason, UErrorCode &errorCode);
115 :
116 : /** Implements CollationRuleParser::Sink. */
117 : virtual void suppressContractions(const UnicodeSet &set, const char *&parserErrorReason,
118 : UErrorCode &errorCode);
119 :
120 : /** Implements CollationRuleParser::Sink. */
121 : virtual void optimize(const UnicodeSet &set, const char *&parserErrorReason,
122 : UErrorCode &errorCode);
123 :
124 : /**
125 : * Adds the mapping and its canonical closure.
126 : * Takes ce32=dataBuilder->encodeCEs(...) so that the data builder
127 : * need not re-encode the CEs multiple times.
128 : */
129 : uint32_t addWithClosure(const UnicodeString &nfdPrefix, const UnicodeString &nfdString,
130 : const int64_t newCEs[], int32_t newCEsLength, uint32_t ce32,
131 : UErrorCode &errorCode);
132 : uint32_t addOnlyClosure(const UnicodeString &nfdPrefix, const UnicodeString &nfdString,
133 : const int64_t newCEs[], int32_t newCEsLength, uint32_t ce32,
134 : UErrorCode &errorCode);
135 : void addTailComposites(const UnicodeString &nfdPrefix, const UnicodeString &nfdString,
136 : UErrorCode &errorCode);
137 : UBool mergeCompositeIntoString(const UnicodeString &nfdString, int32_t indexAfterLastStarter,
138 : UChar32 composite, const UnicodeString &decomp,
139 : UnicodeString &newNFDString, UnicodeString &newString,
140 : UErrorCode &errorCode) const;
141 :
142 : UBool ignorePrefix(const UnicodeString &s, UErrorCode &errorCode) const;
143 : UBool ignoreString(const UnicodeString &s, UErrorCode &errorCode) const;
144 : UBool isFCD(const UnicodeString &s, UErrorCode &errorCode) const;
145 :
146 : void closeOverComposites(UErrorCode &errorCode);
147 :
148 : uint32_t addIfDifferent(const UnicodeString &prefix, const UnicodeString &str,
149 : const int64_t newCEs[], int32_t newCEsLength, uint32_t ce32,
150 : UErrorCode &errorCode);
151 : static UBool sameCEs(const int64_t ces1[], int32_t ces1Length,
152 : const int64_t ces2[], int32_t ces2Length);
153 :
154 : /**
155 : * Walks the tailoring graph and overwrites tailored nodes with new CEs.
156 : * After this, the graph is destroyed.
157 : * The nodes array can then be used only as a source of tailored CEs.
158 : */
159 : void makeTailoredCEs(UErrorCode &errorCode);
160 : /**
161 : * Counts the tailored nodes of the given strength up to the next node
162 : * which is either stronger or has an explicit weight of this strength.
163 : */
164 : static int32_t countTailoredNodes(const int64_t *nodesArray, int32_t i, int32_t strength);
165 :
166 : /** Replaces temporary CEs with the final CEs they point to. */
167 : void finalizeCEs(UErrorCode &errorCode);
168 :
169 : /**
170 : * Encodes "temporary CE" data into a CE that fits into the CE32 data structure,
171 : * with 2-byte primary, 1-byte secondary and 6-bit tertiary,
172 : * with valid CE byte values.
173 : *
174 : * The index must not exceed 20 bits (0xfffff).
175 : * The strength must fit into 2 bits (UCOL_PRIMARY..UCOL_QUATERNARY).
176 : *
177 : * Temporary CEs are distinguished from real CEs by their use of
178 : * secondary weights 06..45 which are otherwise reserved for compressed sort keys.
179 : *
180 : * The case bits are unused and available.
181 : */
182 0 : static inline int64_t tempCEFromIndexAndStrength(int32_t index, int32_t strength) {
183 : return
184 : // CE byte offsets, to ensure valid CE bytes, and case bits 11
185 0 : INT64_C(0x4040000006002000) +
186 : // index bits 19..13 -> primary byte 1 = CE bits 63..56 (byte values 40..BF)
187 0 : ((int64_t)(index & 0xfe000) << 43) +
188 : // index bits 12..6 -> primary byte 2 = CE bits 55..48 (byte values 40..BF)
189 0 : ((int64_t)(index & 0x1fc0) << 42) +
190 : // index bits 5..0 -> secondary byte 1 = CE bits 31..24 (byte values 06..45)
191 0 : ((index & 0x3f) << 24) +
192 : // strength bits 1..0 -> tertiary byte 1 = CE bits 13..8 (byte values 20..23)
193 0 : (strength << 8);
194 : }
195 0 : static inline int32_t indexFromTempCE(int64_t tempCE) {
196 0 : tempCE -= INT64_C(0x4040000006002000);
197 : return
198 0 : ((int32_t)(tempCE >> 43) & 0xfe000) |
199 0 : ((int32_t)(tempCE >> 42) & 0x1fc0) |
200 0 : ((int32_t)(tempCE >> 24) & 0x3f);
201 : }
202 0 : static inline int32_t strengthFromTempCE(int64_t tempCE) {
203 0 : return ((int32_t)tempCE >> 8) & 3;
204 : }
205 0 : static inline UBool isTempCE(int64_t ce) {
206 0 : uint32_t sec = (uint32_t)ce >> 24;
207 0 : return 6 <= sec && sec <= 0x45;
208 : }
209 :
210 0 : static inline int32_t indexFromTempCE32(uint32_t tempCE32) {
211 0 : tempCE32 -= 0x40400620;
212 : return
213 0 : ((int32_t)(tempCE32 >> 11) & 0xfe000) |
214 0 : ((int32_t)(tempCE32 >> 10) & 0x1fc0) |
215 0 : ((int32_t)(tempCE32 >> 8) & 0x3f);
216 : }
217 0 : static inline UBool isTempCE32(uint32_t ce32) {
218 : return
219 0 : (ce32 & 0xff) >= 2 && // not a long-primary/long-secondary CE32
220 0 : 6 <= ((ce32 >> 8) & 0xff) && ((ce32 >> 8) & 0xff) <= 0x45;
221 : }
222 :
223 : static int32_t ceStrength(int64_t ce);
224 :
225 : /** At most 1M nodes, limited by the 20 bits in node bit fields. */
226 : static const int32_t MAX_INDEX = 0xfffff;
227 : /**
228 : * Node bit 6 is set on a primary node if there are nodes
229 : * with secondary values below the common secondary weight (05).
230 : */
231 : static const int32_t HAS_BEFORE2 = 0x40;
232 : /**
233 : * Node bit 5 is set on a primary or secondary node if there are nodes
234 : * with tertiary values below the common tertiary weight (05).
235 : */
236 : static const int32_t HAS_BEFORE3 = 0x20;
237 : /**
238 : * Node bit 3 distinguishes a tailored node, which has no weight value,
239 : * from a node with an explicit (root or default) weight.
240 : */
241 : static const int32_t IS_TAILORED = 8;
242 :
243 0 : static inline int64_t nodeFromWeight32(uint32_t weight32) {
244 0 : return (int64_t)weight32 << 32;
245 : }
246 0 : static inline int64_t nodeFromWeight16(uint32_t weight16) {
247 0 : return (int64_t)weight16 << 48;
248 : }
249 0 : static inline int64_t nodeFromPreviousIndex(int32_t previous) {
250 0 : return (int64_t)previous << 28;
251 : }
252 0 : static inline int64_t nodeFromNextIndex(int32_t next) {
253 0 : return next << 8;
254 : }
255 0 : static inline int64_t nodeFromStrength(int32_t strength) {
256 0 : return strength;
257 : }
258 :
259 0 : static inline uint32_t weight32FromNode(int64_t node) {
260 0 : return (uint32_t)(node >> 32);
261 : }
262 0 : static inline uint32_t weight16FromNode(int64_t node) {
263 0 : return (uint32_t)(node >> 48) & 0xffff;
264 : }
265 0 : static inline int32_t previousIndexFromNode(int64_t node) {
266 0 : return (int32_t)(node >> 28) & MAX_INDEX;
267 : }
268 0 : static inline int32_t nextIndexFromNode(int64_t node) {
269 0 : return ((int32_t)node >> 8) & MAX_INDEX;
270 : }
271 0 : static inline int32_t strengthFromNode(int64_t node) {
272 0 : return (int32_t)node & 3;
273 : }
274 :
275 0 : static inline UBool nodeHasBefore2(int64_t node) {
276 0 : return (node & HAS_BEFORE2) != 0;
277 : }
278 0 : static inline UBool nodeHasBefore3(int64_t node) {
279 0 : return (node & HAS_BEFORE3) != 0;
280 : }
281 0 : static inline UBool nodeHasAnyBefore(int64_t node) {
282 0 : return (node & (HAS_BEFORE2 | HAS_BEFORE3)) != 0;
283 : }
284 0 : static inline UBool isTailoredNode(int64_t node) {
285 0 : return (node & IS_TAILORED) != 0;
286 : }
287 :
288 0 : static inline int64_t changeNodePreviousIndex(int64_t node, int32_t previous) {
289 0 : return (node & INT64_C(0xffff00000fffffff)) | nodeFromPreviousIndex(previous);
290 : }
291 0 : static inline int64_t changeNodeNextIndex(int64_t node, int32_t next) {
292 0 : return (node & INT64_C(0xfffffffff00000ff)) | nodeFromNextIndex(next);
293 : }
294 :
295 : const Normalizer2 &nfd, &fcd;
296 : const Normalizer2Impl &nfcImpl;
297 :
298 : const CollationTailoring *base;
299 : const CollationData *baseData;
300 : const CollationRootElements rootElements;
301 : uint32_t variableTop;
302 :
303 : CollationDataBuilder *dataBuilder;
304 : UBool fastLatinEnabled;
305 : UnicodeSet optimizeSet;
306 : const char *errorReason;
307 :
308 : int64_t ces[Collation::MAX_EXPANSION_LENGTH];
309 : int32_t cesLength;
310 :
311 : /**
312 : * Indexes of nodes with root primary weights, sorted by primary.
313 : * Compact form of a TreeMap from root primary to node index.
314 : *
315 : * This is a performance optimization for finding reset positions.
316 : * Without this, we would have to search through the entire nodes list.
317 : * It also allows storing root primary weights in list head nodes,
318 : * without previous index, leaving room in root primary nodes for 32-bit primary weights.
319 : */
320 : UVector32 rootPrimaryIndexes;
321 : /**
322 : * Data structure for assigning tailored weights and CEs.
323 : * Doubly-linked lists of nodes in mostly collation order.
324 : * Each list starts with a root primary node and ends with a nextIndex of 0.
325 : *
326 : * When there are any nodes in the list, then there is always a root primary node at index 0.
327 : * This allows some code not to have to check explicitly for nextIndex==0.
328 : *
329 : * Root primary nodes have 32-bit weights but do not have previous indexes.
330 : * All other nodes have at most 16-bit weights and do have previous indexes.
331 : *
332 : * Nodes with explicit weights store root collator weights,
333 : * or default weak weights (e.g., secondary 05) for stronger nodes.
334 : * "Tailored" nodes, with the IS_TAILORED bit set,
335 : * do not store explicit weights but rather
336 : * create a difference of a certain strength from the preceding node.
337 : *
338 : * A root node is followed by either
339 : * - a root/default node of the same strength, or
340 : * - a root/default node of the next-weaker strength, or
341 : * - a tailored node of the same strength.
342 : *
343 : * A node of a given strength normally implies "common" weights on weaker levels.
344 : *
345 : * A node with HAS_BEFORE2 must be immediately followed by
346 : * a secondary node with an explicit below-common weight, then a secondary tailored node,
347 : * and later an explicit common-secondary node.
348 : * The below-common weight can be a root weight,
349 : * or it can be BEFORE_WEIGHT16 for tailoring before an implied common weight
350 : * or before the lowest root weight.
351 : * (&[before 2] resets to an explicit secondary node so that
352 : * the following addRelation(secondary) tailors right after that.
353 : * If we did not have this node and instead were to reset on the primary node,
354 : * then addRelation(secondary) would skip forward to the the COMMON_WEIGHT16 node.)
355 : *
356 : * If the flag is not set, then there are no explicit secondary nodes
357 : * with the common or lower weights.
358 : *
359 : * Same for HAS_BEFORE3 for tertiary nodes and weights.
360 : * A node must not have both flags set.
361 : *
362 : * Tailored CEs are initially represented in a CollationDataBuilder as temporary CEs
363 : * which point to stable indexes in this list,
364 : * and temporary CEs stored in a CollationDataBuilder only point to tailored nodes.
365 : *
366 : * A temporary CE in the ces[] array may point to a non-tailored reset-before-position node,
367 : * until the next relation is added.
368 : *
369 : * At the end, the tailored weights are allocated as necessary,
370 : * then the tailored nodes are replaced with final CEs,
371 : * and the CollationData is rewritten by replacing temporary CEs with final ones.
372 : *
373 : * We cannot simply insert new nodes in the middle of the array
374 : * because that would invalidate the indexes stored in existing temporary CEs.
375 : * We need to use a linked graph with stable indexes to existing nodes.
376 : * A doubly-linked list seems easiest to maintain.
377 : *
378 : * Each node is stored as an int64_t, with its fields stored as bit fields.
379 : *
380 : * Root primary node:
381 : * - primary weight: 32 bits 63..32
382 : * - reserved/unused/zero: 4 bits 31..28
383 : *
384 : * Weaker root nodes & tailored nodes:
385 : * - a weight: 16 bits 63..48
386 : * + a root or default weight for a non-tailored node
387 : * + unused/zero for a tailored node
388 : * - index to the previous node: 20 bits 47..28
389 : *
390 : * All types of nodes:
391 : * - index to the next node: 20 bits 27..8
392 : * + nextIndex=0 in last node per root-primary list
393 : * - reserved/unused/zero bits: bits 7, 4, 2
394 : * - HAS_BEFORE2: bit 6
395 : * - HAS_BEFORE3: bit 5
396 : * - IS_TAILORED: bit 3
397 : * - the difference strength (primary/secondary/tertiary/quaternary): 2 bits 1..0
398 : *
399 : * We could allocate structs with pointers, but we would have to store them
400 : * in a pointer list so that they can be indexed from temporary CEs,
401 : * and they would require more memory allocations.
402 : */
403 : UVector64 nodes;
404 : };
405 :
406 : U_NAMESPACE_END
407 :
408 : #endif // !UCONFIG_NO_COLLATION
409 : #endif // __COLLATIONBUILDER_H__
|
