• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 
disableFastLatin()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 
getErrorReason()53     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      */
tempCEFromIndexAndStrength(int32_t index,int32_t strength)182     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             INT64_C(0x4040000006002000) +
186             // index bits 19..13 -> primary byte 1 = CE bits 63..56 (byte values 40..BF)
187             ((int64_t)(index & 0xfe000) << 43) +
188             // index bits 12..6 -> primary byte 2 = CE bits 55..48 (byte values 40..BF)
189             ((int64_t)(index & 0x1fc0) << 42) +
190             // index bits 5..0 -> secondary byte 1 = CE bits 31..24 (byte values 06..45)
191             ((index & 0x3f) << 24) +
192             // strength bits 1..0 -> tertiary byte 1 = CE bits 13..8 (byte values 20..23)
193             (strength << 8);
194     }
indexFromTempCE(int64_t tempCE)195     static inline int32_t indexFromTempCE(int64_t tempCE) {
196         tempCE -= INT64_C(0x4040000006002000);
197         return
198             ((int32_t)(tempCE >> 43) & 0xfe000) |
199             ((int32_t)(tempCE >> 42) & 0x1fc0) |
200             ((int32_t)(tempCE >> 24) & 0x3f);
201     }
strengthFromTempCE(int64_t tempCE)202     static inline int32_t strengthFromTempCE(int64_t tempCE) {
203         return ((int32_t)tempCE >> 8) & 3;
204     }
isTempCE(int64_t ce)205     static inline UBool isTempCE(int64_t ce) {
206         uint32_t sec = (uint32_t)ce >> 24;
207         return 6 <= sec && sec <= 0x45;
208     }
209 
indexFromTempCE32(uint32_t tempCE32)210     static inline int32_t indexFromTempCE32(uint32_t tempCE32) {
211         tempCE32 -= 0x40400620;
212         return
213             ((int32_t)(tempCE32 >> 11) & 0xfe000) |
214             ((int32_t)(tempCE32 >> 10) & 0x1fc0) |
215             ((int32_t)(tempCE32 >> 8) & 0x3f);
216     }
isTempCE32(uint32_t ce32)217     static inline UBool isTempCE32(uint32_t ce32) {
218         return
219             (ce32 & 0xff) >= 2 &&  // not a long-primary/long-secondary CE32
220             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 
nodeFromWeight32(uint32_t weight32)243     static inline int64_t nodeFromWeight32(uint32_t weight32) {
244         return (int64_t)weight32 << 32;
245     }
nodeFromWeight16(uint32_t weight16)246     static inline int64_t nodeFromWeight16(uint32_t weight16) {
247         return (int64_t)weight16 << 48;
248     }
nodeFromPreviousIndex(int32_t previous)249     static inline int64_t nodeFromPreviousIndex(int32_t previous) {
250         return (int64_t)previous << 28;
251     }
nodeFromNextIndex(int32_t next)252     static inline int64_t nodeFromNextIndex(int32_t next) {
253         return next << 8;
254     }
nodeFromStrength(int32_t strength)255     static inline int64_t nodeFromStrength(int32_t strength) {
256         return strength;
257     }
258 
weight32FromNode(int64_t node)259     static inline uint32_t weight32FromNode(int64_t node) {
260         return (uint32_t)(node >> 32);
261     }
weight16FromNode(int64_t node)262     static inline uint32_t weight16FromNode(int64_t node) {
263         return (uint32_t)(node >> 48) & 0xffff;
264     }
previousIndexFromNode(int64_t node)265     static inline int32_t previousIndexFromNode(int64_t node) {
266         return (int32_t)(node >> 28) & MAX_INDEX;
267     }
nextIndexFromNode(int64_t node)268     static inline int32_t nextIndexFromNode(int64_t node) {
269         return ((int32_t)node >> 8) & MAX_INDEX;
270     }
strengthFromNode(int64_t node)271     static inline int32_t strengthFromNode(int64_t node) {
272         return (int32_t)node & 3;
273     }
274 
nodeHasBefore2(int64_t node)275     static inline UBool nodeHasBefore2(int64_t node) {
276         return (node & HAS_BEFORE2) != 0;
277     }
nodeHasBefore3(int64_t node)278     static inline UBool nodeHasBefore3(int64_t node) {
279         return (node & HAS_BEFORE3) != 0;
280     }
nodeHasAnyBefore(int64_t node)281     static inline UBool nodeHasAnyBefore(int64_t node) {
282         return (node & (HAS_BEFORE2 | HAS_BEFORE3)) != 0;
283     }
isTailoredNode(int64_t node)284     static inline UBool isTailoredNode(int64_t node) {
285         return (node & IS_TAILORED) != 0;
286     }
287 
changeNodePreviousIndex(int64_t node,int32_t previous)288     static inline int64_t changeNodePreviousIndex(int64_t node, int32_t previous) {
289         return (node & INT64_C(0xffff00000fffffff)) | nodeFromPreviousIndex(previous);
290     }
changeNodeNextIndex(int64_t node,int32_t next)291     static inline int64_t changeNodeNextIndex(int64_t node, int32_t next) {
292         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__
410