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 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 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 } 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 } 202 static inline int32_t strengthFromTempCE(int64_t tempCE) { 203 return ((int32_t)tempCE >> 8) & 3; 204 } 205 static inline UBool isTempCE(int64_t ce) { 206 uint32_t sec = (uint32_t)ce >> 24; 207 return 6 <= sec && sec <= 0x45; 208 } 209 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 } 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 243 static inline int64_t nodeFromWeight32(uint32_t weight32) { 244 return (int64_t)weight32 << 32; 245 } 246 static inline int64_t nodeFromWeight16(uint32_t weight16) { 247 return (int64_t)weight16 << 48; 248 } 249 static inline int64_t nodeFromPreviousIndex(int32_t previous) { 250 return (int64_t)previous << 28; 251 } 252 static inline int64_t nodeFromNextIndex(int32_t next) { 253 return next << 8; 254 } 255 static inline int64_t nodeFromStrength(int32_t strength) { 256 return strength; 257 } 258 259 static inline uint32_t weight32FromNode(int64_t node) { 260 return (uint32_t)(node >> 32); 261 } 262 static inline uint32_t weight16FromNode(int64_t node) { 263 return (uint32_t)(node >> 48) & 0xffff; 264 } 265 static inline int32_t previousIndexFromNode(int64_t node) { 266 return (int32_t)(node >> 28) & MAX_INDEX; 267 } 268 static inline int32_t nextIndexFromNode(int64_t node) { 269 return ((int32_t)node >> 8) & MAX_INDEX; 270 } 271 static inline int32_t strengthFromNode(int64_t node) { 272 return (int32_t)node & 3; 273 } 274 275 static inline UBool nodeHasBefore2(int64_t node) { 276 return (node & HAS_BEFORE2) != 0; 277 } 278 static inline UBool nodeHasBefore3(int64_t node) { 279 return (node & HAS_BEFORE3) != 0; 280 } 281 static inline UBool nodeHasAnyBefore(int64_t node) { 282 return (node & (HAS_BEFORE2 | HAS_BEFORE3)) != 0; 283 } 284 static inline UBool isTailoredNode(int64_t node) { 285 return (node & IS_TAILORED) != 0; 286 } 287 288 static inline int64_t changeNodePreviousIndex(int64_t node, int32_t previous) { 289 return (node & INT64_C(0xffff00000fffffff)) | nodeFromPreviousIndex(previous); 290 } 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
