Victor Chang | 7322950 | 2020-09-17 13:39:19 +0100 | [diff] [blame] | 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 | |
Victor Chang | ce4bf3c | 2021-01-19 16:34:24 +0000 | [diff] [blame] | 45 | void disableFastLatin() { fastLatinEnabled = false; } |
Victor Chang | 7322950 | 2020-09-17 13:39:19 +0100 | [diff] [blame] | 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__ |