icuSources/i18n/collationbuilder.h

   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      * Returns the secondary or tertiary weight preceding the current node's weight.
  61      * node=nodes[index].
  62      */
  63     uint32_t getWeight16Before(int32_t index, int64_t node, int32_t level);
  64
  65     int64_t getSpecialResetPosition(const UnicodeString &str,
  66                                     const char *&parserErrorReason, UErrorCode &errorCode);
  67
  68     /** Implements CollationRuleParser::Sink. */
  69     virtual void addRelation(int32_t strength, const UnicodeString &prefix,
  70                              const UnicodeString &str, const UnicodeString &extension,
  71                              const char *&errorReason, UErrorCode &errorCode);
  72
  73     /**
  74      * Picks one of the current CEs and finds or inserts a node in the graph
  75      * for the CE + strength.
  76      */
  77     int32_t findOrInsertNodeForCEs(int32_t strength, const char *&parserErrorReason,
  78                                    UErrorCode &errorCode);
  79     int32_t findOrInsertNodeForRootCE(int64_t ce, int32_t strength, UErrorCode &errorCode);
  80     /** Finds or inserts the node for a root CE's primary weight. */
  81     int32_t findOrInsertNodeForPrimary(uint32_t p, UErrorCode &errorCode);
  82     /** Finds or inserts the node for a secondary or tertiary weight. */
  83     int32_t findOrInsertWeakNode(int32_t index, uint32_t weight16, int32_t level,
  84                                  UErrorCode &errorCode);
  85
  86     /**
  87      * Makes and inserts a new tailored node into the list, after the one at index.
  88      * Skips over nodes of weaker strength to maintain collation order
  89      * ("postpone insertion").
  90      * @return the new node's index
  91      */
  92     int32_t insertTailoredNodeAfter(int32_t index, int32_t strength, UErrorCode &errorCode);
  93
  94     /**
  95      * Inserts a new node into the list, between list-adjacent items.
  96      * The node's previous and next indexes must not be set yet.
  97      * @return the new node's index
  98      */
  99     int32_t insertNodeBetween(int32_t index, int32_t nextIndex, int64_t node,
 100                               UErrorCode &errorCode);
 101
 102     /**
 103      * Finds the node which implies or contains a common=05 weight of the given strength
 104      * (secondary or tertiary), if the current node is stronger.
 105      * Skips weaker nodes and tailored nodes if the current node is stronger
 106      * and is followed by an explicit-common-weight node.
 107      * Always returns the input index if that node is no stronger than the given strength.
 108      */
 109     int32_t findCommonNode(int32_t index, int32_t strength) const;
 110
 111     void setCaseBits(const UnicodeString &nfdString,
 112                      const char *&parserErrorReason, UErrorCode &errorCode);
 113
 114     /** Implements CollationRuleParser::Sink. */
 115     virtual void suppressContractions(const UnicodeSet &set, const char *&parserErrorReason,
 116                                       UErrorCode &errorCode);
 117
 118     /** Implements CollationRuleParser::Sink. */
 119     virtual void optimize(const UnicodeSet &set, const char *&parserErrorReason,
 120                           UErrorCode &errorCode);
 121
 122     /**
 123      * Adds the mapping and its canonical closure.
 124      * Takes ce32=dataBuilder->encodeCEs(...) so that the data builder
 125      * need not re-encode the CEs multiple times.
 126      */
 127     uint32_t addWithClosure(const UnicodeString &nfdPrefix, const UnicodeString &nfdString,
 128                             const int64_t newCEs[], int32_t newCEsLength, uint32_t ce32,
 129                             UErrorCode &errorCode);
 130     uint32_t addOnlyClosure(const UnicodeString &nfdPrefix, const UnicodeString &nfdString,
 131                             const int64_t newCEs[], int32_t newCEsLength, uint32_t ce32,
 132                             UErrorCode &errorCode);
 133     void addTailComposites(const UnicodeString &nfdPrefix, const UnicodeString &nfdString,
 134                            UErrorCode &errorCode);
 135     UBool mergeCompositeIntoString(const UnicodeString &nfdString, int32_t indexAfterLastStarter,
 136                                    UChar32 composite, const UnicodeString &decomp,
 137                                    UnicodeString &newNFDString, UnicodeString &newString,
 138                                    UErrorCode &errorCode) const;
 139
 140     UBool ignorePrefix(const UnicodeString &s, UErrorCode &errorCode) const;
 141     UBool ignoreString(const UnicodeString &s, UErrorCode &errorCode) const;
 142     UBool isFCD(const UnicodeString &s, UErrorCode &errorCode) const;
 143
 144     void closeOverComposites(UErrorCode &errorCode);
 145
 146     uint32_t addIfDifferent(const UnicodeString &prefix, const UnicodeString &str,
 147                             const int64_t newCEs[], int32_t newCEsLength, uint32_t ce32,
 148                             UErrorCode &errorCode);
 149     static UBool sameCEs(const int64_t ces1[], int32_t ces1Length,
 150                          const int64_t ces2[], int32_t ces2Length);
 151
 152     /**
 153      * Walks the tailoring graph and overwrites tailored nodes with new CEs.
 154      * After this, the graph is destroyed.
 155      * The nodes array can then be used only as a source of tailored CEs.
 156      */
 157     void makeTailoredCEs(UErrorCode &errorCode);
 158     /**
 159      * Counts the tailored nodes of the given strength up to the next node
 160      * which is either stronger or has an explicit weight of this strength.
 161      */
 162     static int32_t countTailoredNodes(const int64_t *nodesArray, int32_t i, int32_t strength);
 163
 164     /** Replaces temporary CEs with the final CEs they point to. */
 165     void finalizeCEs(UErrorCode &errorCode);
 166
 167     /**
 168      * Encodes "temporary CE" data into a CE that fits into the CE32 data structure,
 169      * with 2-byte primary, 1-byte secondary and 6-bit tertiary,
 170      * with valid CE byte values.
 171      *
 172      * The index must not exceed 20 bits (0xfffff).
 173      * The strength must fit into 2 bits (UCOL_PRIMARY..UCOL_QUATERNARY).
 174      *
 175      * Temporary CEs are distinguished from real CEs by their use of
 176      * secondary weights 06..45 which are otherwise reserved for compressed sort keys.
 177      *
 178      * The case bits are unused and available.
 179      */
 180     static inline int64_t tempCEFromIndexAndStrength(int32_t index, int32_t strength) {
 181         return
 182             // CE byte offsets, to ensure valid CE bytes, and case bits 11
 183             INT64_C(0x4040000006002000) +
 184             // index bits 19..13 -> primary byte 1 = CE bits 63..56 (byte values 40..BF)
 185             ((int64_t)(index & 0xfe000) << 43) +
 186             // index bits 12..6 -> primary byte 2 = CE bits 55..48 (byte values 40..BF)
 187             ((int64_t)(index & 0x1fc0) << 42) +
 188             // index bits 5..0 -> secondary byte 1 = CE bits 31..24 (byte values 06..45)
 189             ((index & 0x3f) << 24) +
 190             // strength bits 1..0 -> tertiary byte 1 = CE bits 13..8 (byte values 20..23)
 191             (strength << 8);
 192     }
 193     static inline int32_t indexFromTempCE(int64_t tempCE) {
 194         tempCE -= INT64_C(0x4040000006002000);
 195         return
 196             ((int32_t)(tempCE >> 43) & 0xfe000) |
 197             ((int32_t)(tempCE >> 42) & 0x1fc0) |
 198             ((int32_t)(tempCE >> 24) & 0x3f);
 199     }
 200     static inline int32_t strengthFromTempCE(int64_t tempCE) {
 201         return ((int32_t)tempCE >> 8) & 3;
 202     }
 203     static inline UBool isTempCE(int64_t ce) {
 204         uint32_t sec = (uint32_t)ce >> 24;
 205         return 6 <= sec && sec <= 0x45;
 206     }
 207
 208     static inline int32_t indexFromTempCE32(uint32_t tempCE32) {
 209         tempCE32 -= 0x40400620;
 210         return
 211             ((int32_t)(tempCE32 >> 11) & 0xfe000) |
 212             ((int32_t)(tempCE32 >> 10) & 0x1fc0) |
 213             ((int32_t)(tempCE32 >> 8) & 0x3f);
 214     }
 215     static inline UBool isTempCE32(uint32_t ce32) {
 216         return
 217             (ce32 & 0xff) >= 2 &&  // not a long-primary/long-secondary CE32
 218             6 <= ((ce32 >> 8) & 0xff) && ((ce32 >> 8) & 0xff) <= 0x45;
 219     }
 220
 221     static int32_t ceStrength(int64_t ce);
 222
 223     /** At most 1M nodes, limited by the 20 bits in node bit fields. */
 224     static const int32_t MAX_INDEX = 0xfffff;
 225     /**
 226      * Node bit 6 is set on a primary node if there are nodes
 227      * with secondary values below the common secondary weight (05).
 228      */
 229     static const int32_t HAS_BEFORE2 = 0x40;
 230     /**
 231      * Node bit 5 is set on a primary or secondary node if there are nodes
 232      * with tertiary values below the common tertiary weight (05).
 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 an explicit below-common weight, then a secondary tailored node,
 345      * and later an explicit common-secondary node.
 346      * The below-common weight can be a root weight,
 347      * or it can be BEFORE_WEIGHT16 for tailoring before an implied common weight
 348      * or before the lowest root weight.
 349      * (&[before 2] resets to an explicit secondary node so that
 350      * the following addRelation(secondary) tailors right after that.
 351      * If we did not have this node and instead were to reset on the primary node,
 352      * then addRelation(secondary) would skip forward to the the COMMON_WEIGHT16 node.)
 353      *
 354      * If the flag is not set, then there are no explicit secondary nodes
 355      * with the common or lower weights.
 356      *
 357      * Same for HAS_BEFORE3 for tertiary nodes and weights.
 358      * A node must not have both flags set.
 359      *
 360      * Tailored CEs are initially represented in a CollationDataBuilder as temporary CEs
 361      * which point to stable indexes in this list,
 362      * and temporary CEs stored in a CollationDataBuilder only point to tailored nodes.
 363      *
 364      * A temporary CE in the ces[] array may point to a non-tailored reset-before-position node,
 365      * until the next relation is added.
 366      *
 367      * At the end, the tailored weights are allocated as necessary,
 368      * then the tailored nodes are replaced with final CEs,
 369      * and the CollationData is rewritten by replacing temporary CEs with final ones.
 370      *
 371      * We cannot simply insert new nodes in the middle of the array
 372      * because that would invalidate the indexes stored in existing temporary CEs.
 373      * We need to use a linked graph with stable indexes to existing nodes.
 374      * A doubly-linked list seems easiest to maintain.
 375      *
 376      * Each node is stored as an int64_t, with its fields stored as bit fields.
 377      *
 378      * Root primary node:
 379      * - primary weight: 32 bits 63..32
 380      * - reserved/unused/zero: 4 bits 31..28
 381      *
 382      * Weaker root nodes & tailored nodes:
 383      * - a weight: 16 bits 63..48
 384      *   + a root or default weight for a non-tailored node
 385      *   + unused/zero for a tailored node
 386      * - index to the previous node: 20 bits 47..28
 387      *
 388      * All types of nodes:
 389      * - index to the next node: 20 bits 27..8
 390      *   + nextIndex=0 in last node per root-primary list
 391      * - reserved/unused/zero bits: bits 7, 4, 2
 392      * - HAS_BEFORE2: bit 6
 393      * - HAS_BEFORE3: bit 5
 394      * - IS_TAILORED: bit 3
 395      * - the difference strength (primary/secondary/tertiary/quaternary): 2 bits 1..0
 396      *
 397      * We could allocate structs with pointers, but we would have to store them
 398      * in a pointer list so that they can be indexed from temporary CEs,
 399      * and they would require more memory allocations.
 400      */
 401     UVector64 nodes;
 402 };
 403
 404 U_NAMESPACE_END
 405
 406 #endif  // !UCONFIG_NO_COLLATION
 407 #endif  // __COLLATIONBUILDER_H__