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 26 struct UParseError; 27 28 U_NAMESPACE_BEGIN 29 30 struct CollationData; 31 struct CollationTailoring; 32 33 class CEFinalizer; 34 class CollationDataBuilder; 35 class Normalizer2; 36 class Normalizer2Impl; 37 38 class U_I18N_API CollationBuilder : public CollationRuleParser::Sink { 39 public: 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 53 private: 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 403 U_NAMESPACE_END 404 405 #endif // !UCONFIG_NO_COLLATION 406 #endif // __COLLATIONBUILDER_H__ 407
