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