jars/icu4j-4_4_2-src/main/classes/core/src/com/ibm/icu/text/RBBISetBuilder.java

   1 /*\r
   2 *******************************************************************************\r
   3 * Copyright (C) 2003-2009, International Business Machines Corporation and    *\r
   4 * others. All Rights Reserved.                                                *\r
   5 *******************************************************************************\r
   6 */\r
   7 package com.ibm.icu.text;\r
   8 \r
   9 import java.io.IOException;\r
  10 import java.io.OutputStream;\r
  11 import java.util.ArrayList;\r
  12 import java.util.List;\r
  13 \r
  14 import com.ibm.icu.impl.Assert;\r
  15 import com.ibm.icu.impl.IntTrieBuilder;\r
  16 \r
  17 //\r
  18 //  RBBISetBuilder   Handles processing of Unicode Sets from RBBI rules\r
  19 //                   (part of the rule building process.)\r
  20 //\r
  21 //      Starting with the rules parse tree from the scanner,\r
  22 //\r
  23 //                   -  Enumerate the set of UnicodeSets that are referenced\r
  24 //                      by the RBBI rules.\r
  25 //                   -  compute a set of non-overlapping character ranges\r
  26 //                      with all characters within a range belonging to the same\r
  27 //                      set of input uniocde sets.\r
  28 //                   -  Derive a set of non-overlapping UnicodeSet (like things)\r
  29 //                      that will correspond to columns in the state table for\r
  30 //                      the RBBI execution engine.  All characters within one\r
  31 //                      of these sets belong to the same set of the original\r
  32 //                      UnicodeSets from the user's rules.\r
  33 //                   -  construct the trie table that maps input characters\r
  34 //                      to the index of the matching non-overlapping set of set from\r
  35 //                      the previous step.\r
  36 //\r
  37 class RBBISetBuilder {\r
  38     static class RangeDescriptor  {\r
  39            int                fStartChar;      // Start of range, unicode 32 bit value.\r
  40            int                fEndChar;        // End of range, unicode 32 bit value.\r
  41            int                fNum;            // runtime-mapped input value for this range.\r
  42            List<RBBINode>     fIncludesSets;    // vector of the the original\r
  43                                                  //   Unicode sets that include this range.\r
  44                                                 //    (Contains ptrs to uset nodes)\r
  45             RangeDescriptor   fNext;           // Next RangeDescriptor in the linked list.\r
  46 \r
  47             RangeDescriptor() {\r
  48                 fIncludesSets = new ArrayList<RBBINode>();\r
  49             }\r
  50             \r
  51             RangeDescriptor(RangeDescriptor other) {\r
  52                 fStartChar = other.fStartChar;\r
  53                 fEndChar   = other.fEndChar;\r
  54                 fNum       = other.fNum;\r
  55                 fIncludesSets = new ArrayList<RBBINode>(other.fIncludesSets);\r
  56             }\r
  57  \r
  58             //-------------------------------------------------------------------------------------\r
  59             //\r
  60             //          RangeDesriptor::split()\r
  61             //\r
  62             //-------------------------------------------------------------------------------------\r
  63             void split(int where) {\r
  64                 Assert.assrt(where>fStartChar && where<=fEndChar);\r
  65                 RangeDescriptor nr = new RangeDescriptor(this);\r
  66  \r
  67                 //  RangeDescriptor copy constructor copies all fields.\r
  68                 //  Only need to update those that are different after the split.\r
  69                 nr.fStartChar = where;\r
  70                 this.fEndChar = where-1;\r
  71                 nr.fNext      = this.fNext;\r
  72                 this.fNext    = nr;\r
  73                 \r
  74                 // TODO:  fIncludesSets is not updated.  Check it out.\r
  75                 //         Probably because they haven't been populated yet, \r
  76                 //         but still sloppy.\r
  77             }\r
  78 \r
  79             \r
  80             //-------------------------------------------------------------------------------------\r
  81             //\r
  82             //          RangeDescriptor::setDictionaryFlag\r
  83             //\r
  84             //          Character Category Numbers that include characters from\r
  85             //          the original Unicode Set named "dictionary" have bit 14\r
  86             //          set to 1.  The RBBI runtime engine uses this to trigger\r
  87             //          use of the word dictionary.\r
  88             //\r
  89             //          This function looks through the Unicode Sets that it\r
  90             //          (the range) includes, and sets the bit in fNum when\r
  91             //          "dictionary" is among them.\r
  92             //\r
  93             //          TODO:  a faster way would be to find the set node for\r
  94             //          "dictionary" just once, rather than looking it\r
  95             //          up by name every time.\r
  96             //            \r
  97             // -------------------------------------------------------------------------------------\r
  98             void setDictionaryFlag() {\r
  99                 int i;\r
 100                 \r
 101                 for (i=0; i<this.fIncludesSets.size(); i++) {\r
 102                     RBBINode        usetNode    = fIncludesSets.get(i);\r
 103                     String          setName = "";\r
 104                     RBBINode        setRef = usetNode.fParent;\r
 105                     if (setRef != null) {\r
 106                         RBBINode varRef = setRef.fParent;\r
 107                         if (varRef != null  &&  varRef.fType == RBBINode.varRef) {\r
 108                             setName = varRef.fText;\r
 109                         }\r
 110                     }\r
 111                     if (setName.equals("dictionary")) {\r
 112                         this.fNum |= 0x4000;\r
 113                         break;\r
 114                     }\r
 115                 }\r
 116 \r
 117         }\r
 118     }\r
 119 \r
 120     \r
 121     RBBIRuleBuilder       fRB;             // The RBBI Rule Compiler that owns us.\r
 122     RangeDescriptor       fRangeList;      // Head of the linked list of RangeDescriptors\r
 123 \r
 124     IntTrieBuilder        fTrie;           // The mapping TRIE that is the end result of processing\r
 125     int                  fTrieSize;        //  the Unicode Sets.\r
 126 \r
 127     // Groups correspond to character categories -\r
 128     //       groups of ranges that are in the same original UnicodeSets.\r
 129     //       fGroupCount is the index of the last used group.\r
 130     //       fGroupCount+1 is also the number of columns in the RBBI state table being compiled.\r
 131     //       State table column 0 is not used.  Column 1 is for end-of-input.\r
 132     //       column 2 is for group 0.  Funny counting.\r
 133     int                fGroupCount;\r
 134 \r
 135     boolean             fSawBOF;\r
 136     \r
 137     \r
 138     //------------------------------------------------------------------------\r
 139     //\r
 140     //       RBBISetBuilder Constructor\r
 141     //\r
 142     //------------------------------------------------------------------------\r
 143     RBBISetBuilder(RBBIRuleBuilder rb)\r
 144     {\r
 145         fRB             = rb;\r
 146     }\r
 147 \r
 148 \r
 149     //------------------------------------------------------------------------\r
 150     //\r
 151     //           build          Build the list of non-overlapping character ranges\r
 152     //                          from the Unicode Sets.\r
 153     //\r
 154     //------------------------------------------------------------------------\r
 155     void build() {\r
 156         RangeDescriptor rlRange;\r
 157 \r
 158         if (fRB.fDebugEnv!=null  && fRB.fDebugEnv.indexOf("usets")>=0) {printSets();}\r
 159 \r
 160         //  Initialize the process by creating a single range encompassing all characters\r
 161         //  that is in no sets.\r
 162         //\r
 163         fRangeList               = new RangeDescriptor(); \r
 164         fRangeList.fStartChar    = 0;\r
 165         fRangeList.fEndChar      = 0x10ffff;\r
 166 \r
 167         //\r
 168         //  Find the set of non-overlapping ranges of characters\r
 169         //\r
 170         for (RBBINode usetNode : fRB.fUSetNodes) {\r
 171             UnicodeSet      inputSet             = usetNode.fInputSet;\r
 172             int            inputSetRangeCount   = inputSet.getRangeCount();\r
 173             int            inputSetRangeIndex   = 0;\r
 174             rlRange              = fRangeList;\r
 175 \r
 176             for (;;) {\r
 177                 if (inputSetRangeIndex >= inputSetRangeCount) {\r
 178                     break;\r
 179                 }\r
 180                 int      inputSetRangeBegin  = inputSet.getRangeStart(inputSetRangeIndex);\r
 181                 int      inputSetRangeEnd    = inputSet.getRangeEnd(inputSetRangeIndex);\r
 182 \r
 183                 // skip over ranges from the range list that are completely\r
 184                 //   below the current range from the input unicode set.\r
 185                 while (rlRange.fEndChar < inputSetRangeBegin) {\r
 186                     rlRange = rlRange.fNext;\r
 187                 }\r
 188 \r
 189                 // If the start of the range from the range list is before with\r
 190                 //   the start of the range from the unicode set, split the range list range\r
 191                 //   in two, with one part being before (wholly outside of) the unicode set\r
 192                 //   and the other containing the rest.\r
 193                 //   Then continue the loop; the post-split current range will then be skipped\r
 194                 //     over\r
 195                 if (rlRange.fStartChar < inputSetRangeBegin) {\r
 196                     rlRange.split(inputSetRangeBegin);\r
 197                      continue;\r
 198                 }\r
 199 \r
 200                 // Same thing at the end of the ranges...\r
 201                 // If the end of the range from the range list doesn't coincide with\r
 202                 //   the end of the range from the unicode set, split the range list\r
 203                 //   range in two.  The first part of the split range will be\r
 204                 //   wholly inside the Unicode set.\r
 205                 if (rlRange.fEndChar > inputSetRangeEnd) {\r
 206                     rlRange.split(inputSetRangeEnd+1);\r
 207                  }\r
 208 \r
 209                 // The current rlRange is now entirely within the UnicodeSet range.\r
 210                 // Add this unicode set to the list of sets for this rlRange\r
 211                 if (rlRange.fIncludesSets.indexOf(usetNode) == -1) {\r
 212                     rlRange.fIncludesSets.add(usetNode);\r
 213                 }\r
 214 \r
 215                 // Advance over ranges that we are finished with.\r
 216                 if (inputSetRangeEnd == rlRange.fEndChar) {\r
 217                     inputSetRangeIndex++;\r
 218                 }\r
 219                 rlRange = rlRange.fNext;\r
 220             }\r
 221         }\r
 222 \r
 223         if (fRB.fDebugEnv!=null && fRB.fDebugEnv.indexOf("range")>=0) { printRanges();}\r
 224 \r
 225         //\r
 226         //  Group the above ranges, with each group consisting of one or more\r
 227         //    ranges that are in exactly the same set of original UnicodeSets.\r
 228         //    The groups are numbered, and these group numbers are the set of\r
 229         //    input symbols recognized by the run-time state machine.\r
 230         //\r
 231         //    Numbering: # 0  (state table column 0) is unused.\r
 232         //               # 1  is reserved - table column 1 is for end-of-input\r
 233         //               # 2  is reserved - table column 2 is for beginning-in-input\r
 234         //               # 3  is the first range list.\r
 235         //\r
 236         RangeDescriptor rlSearchRange;\r
 237         for (rlRange = fRangeList; rlRange!=null; rlRange=rlRange.fNext) {\r
 238             for (rlSearchRange=fRangeList; rlSearchRange != rlRange; rlSearchRange=rlSearchRange.fNext) {\r
 239                 if (rlRange.fIncludesSets.equals(rlSearchRange.fIncludesSets)) {\r
 240                     rlRange.fNum = rlSearchRange.fNum;\r
 241                     break;\r
 242                 }\r
 243             }\r
 244             if (rlRange.fNum == 0) {\r
 245                 fGroupCount ++;\r
 246                 rlRange.fNum = fGroupCount+2; \r
 247                 rlRange.setDictionaryFlag();\r
 248                 addValToSets(rlRange.fIncludesSets, fGroupCount+2);\r
 249             }\r
 250         }\r
 251 \r
 252         // Handle input sets that contain the special string {eof}.\r
 253         //   Column 1 of the state table is reserved for EOF on input.\r
 254         //   Column 2 is reserved for before-the-start-input.\r
 255         //            (This column can be optimized away later if there are no rule\r
 256         //             references to {bof}.)\r
 257         //   Add this column value (1 or 2) to the equivalent expression\r
 258         //     subtree for each UnicodeSet that contains the string {eof}\r
 259         //   Because {bof} and {eof} are not a characters in the normal sense,\r
 260         //   they doesn't affect the computation of ranges or TRIE.\r
 261         \r
 262         String eofString = "eof";\r
 263         String bofString = "bof";\r
 264 \r
 265         for (RBBINode usetNode : fRB.fUSetNodes) {\r
 266             UnicodeSet      inputSet = usetNode.fInputSet;\r
 267             if (inputSet.contains(eofString)) {\r
 268                 addValToSet(usetNode, 1);\r
 269             }\r
 270             if (inputSet.contains(bofString)) {\r
 271                 addValToSet(usetNode, 2);\r
 272                 fSawBOF = true;\r
 273             }\r
 274         }\r
 275 \r
 276 \r
 277         if (fRB.fDebugEnv!=null  && fRB.fDebugEnv.indexOf("rgroup")>=0) {printRangeGroups();}\r
 278         if (fRB.fDebugEnv!=null  && fRB.fDebugEnv.indexOf("esets")>=0) {printSets();}\r
 279 \r
 280 \r
 281         //IntTrieBuilder(int aliasdata[], int maxdatalength, \r
 282         //        int initialvalue, int leadunitvalue, \r
 283         //        boolean latin1linear)\r
 284         \r
 285         fTrie = new IntTrieBuilder(null,   //   Data array  (utrie will allocate one)\r
 286                                    100000,  //   Max Data Length\r
 287                                    0,       //   Initial value for all code points\r
 288                                    0,       //   Lead Surrogate unit value,\r
 289                                    true);   //   Keep Latin 1 in separately.\r
 290         \r
 291         for (rlRange = fRangeList; rlRange!=null; rlRange=rlRange.fNext) {\r
 292             fTrie.setRange(rlRange.fStartChar, rlRange.fEndChar+1, rlRange.fNum, true);\r
 293         }\r
 294     }\r
 295 \r
 296 \r
 297 \r
 298     //-----------------------------------------------------------------------------------\r
 299     //\r
 300     //   RBBIDataManipulate  A little internal class needed only to wrap of the \r
 301     //                       getFoldedValue() function needed for Trie table creation.\r
 302     //\r
 303     //-----------------------------------------------------------------------------------\r
 304    class RBBIDataManipulate implements IntTrieBuilder.DataManipulate {\r
 305         public int getFoldedValue(int start, int offset) {\r
 306             int  value;\r
 307             int  limit;\r
 308             boolean [] inBlockZero = new boolean[1];\r
 309             \r
 310             limit = start + 0x400;\r
 311             while(start<limit) {\r
 312                 value = fTrie.getValue(start, inBlockZero);\r
 313                 if (inBlockZero[0]) {\r
 314                     start += IntTrieBuilder.DATA_BLOCK_LENGTH;  \r
 315                 } else if (value != 0) {\r
 316                     return offset | 0x08000;\r
 317                 } else {\r
 318                     ++start;\r
 319                 }\r
 320             }\r
 321             return 0;\r
 322          }\r
 323     }\r
 324     RBBIDataManipulate dm = new RBBIDataManipulate();\r
 325     \r
 326     //-----------------------------------------------------------------------------------\r
 327     //\r
 328     //          getTrieSize()    Return the size that will be required to serialize the Trie.\r
 329     //\r
 330     //-----------------------------------------------------------------------------------\r
 331     int getTrieSize()  {\r
 332         int size = 0;\r
 333         try {\r
 334             // The trie serialize function returns the size of the data written.\r
 335             //    null output stream says give size only, don't actually write anything.\r
 336             size = fTrie.serialize(null, true, dm );\r
 337         } catch (IOException e) {\r
 338             Assert.assrt (false);\r
 339         }\r
 340         return size;\r
 341     }\r
 342 \r
 343 \r
 344     //-----------------------------------------------------------------------------------\r
 345     //\r
 346     //          serializeTrie()   Write the serialized trie to an output stream\r
 347     //\r
 348     //-----------------------------------------------------------------------------------\r
 349     void serializeTrie(OutputStream os) throws IOException {\r
 350         fTrie.serialize(os, true, dm );\r
 351    }\r
 352 \r
 353     //------------------------------------------------------------------------\r
 354     //\r
 355     //      addValToSets     Add a runtime-mapped input value to each uset from a\r
 356     //      list of uset nodes. (val corresponds to a state table column.)\r
 357     //      For each of the original Unicode sets - which correspond\r
 358     //      directly to uset nodes - a logically equivalent expression\r
 359     //      is constructed in terms of the remapped runtime input\r
 360     //      symbol set.  This function adds one runtime input symbol to\r
 361     //      a list of sets.\r
 362     //\r
 363     //      The "logically equivalent expression" is the tree for an\r
 364     //      or-ing together of all of the symbols that go into the set.\r
 365     //\r
 366     //------------------------------------------------------------------------\r
 367     void  addValToSets(List<RBBINode> sets, int val) {\r
 368         for (RBBINode usetNode : sets) {\r
 369             addValToSet(usetNode, val);\r
 370         }\r
 371     }\r
 372 \r
 373     void  addValToSet(RBBINode usetNode, int val) {\r
 374         RBBINode leafNode = new RBBINode(RBBINode.leafChar);\r
 375         leafNode.fVal = val;\r
 376         if (usetNode.fLeftChild == null) {\r
 377             usetNode.fLeftChild = leafNode;\r
 378             leafNode.fParent    = usetNode;\r
 379         } else {\r
 380             // There are already input symbols present for this set.\r
 381             // Set up an OR node, with the previous stuff as the left child\r
 382             //   and the new value as the right child.\r
 383             RBBINode orNode = new RBBINode(RBBINode.opOr);\r
 384             orNode.fLeftChild  = usetNode.fLeftChild;\r
 385             orNode.fRightChild = leafNode;\r
 386             orNode.fLeftChild.fParent  = orNode;\r
 387             orNode.fRightChild.fParent = orNode;\r
 388             usetNode.fLeftChild = orNode;\r
 389             orNode.fParent = usetNode;\r
 390         }\r
 391     }\r
 392 \r
 393 \r
 394     //------------------------------------------------------------------------\r
 395     //\r
 396     //           getNumCharCategories\r
 397     //\r
 398     //------------------------------------------------------------------------\r
 399     int  getNumCharCategories()  {\r
 400         return fGroupCount + 3;\r
 401     }\r
 402 \r
 403 \r
 404     //------------------------------------------------------------------------\r
 405     //\r
 406     //           sawBOF\r
 407     //\r
 408     //------------------------------------------------------------------------\r
 409     boolean  sawBOF()  {\r
 410         return fSawBOF;\r
 411     }\r
 412 \r
 413 \r
 414     //------------------------------------------------------------------------\r
 415     //\r
 416     //           getFirstChar      Given a runtime RBBI character category, find\r
 417     //                             the first UChar32 that is in the set of chars \r
 418     //                             in the category.\r
 419     //------------------------------------------------------------------------\r
 420     int  getFirstChar(int category)  {\r
 421         RangeDescriptor   rlRange;\r
 422         int            retVal = -1;\r
 423         for (rlRange = fRangeList; rlRange!=null; rlRange=rlRange.fNext) {\r
 424             if (rlRange.fNum == category) {\r
 425                 retVal = rlRange.fStartChar;\r
 426                 break;\r
 427             }\r
 428         }\r
 429         return retVal;\r
 430     }\r
 431 \r
 432 \r
 433 \r
 434     //------------------------------------------------------------------------\r
 435     //\r
 436     //           printRanges        A debugging function.\r
 437     //                              dump out all of the range definitions.\r
 438     //\r
 439     //------------------------------------------------------------------------\r
 440     ///CLOVER:OFF\r
 441     void printRanges() {\r
 442         RangeDescriptor       rlRange;\r
 443         int                    i;\r
 444 \r
 445         System.out.print("\n\n Nonoverlapping Ranges ...\n");\r
 446         for (rlRange = fRangeList; rlRange!=null; rlRange=rlRange.fNext) {\r
 447             System.out.print(" " + rlRange.fNum + "   " + rlRange.fStartChar + "-" + rlRange.fEndChar);\r
 448 \r
 449             for (i=0; i<rlRange.fIncludesSets.size(); i++) {\r
 450                 RBBINode       usetNode    = rlRange.fIncludesSets.get(i);\r
 451                 String         setName = "anon";\r
 452                 RBBINode       setRef = usetNode.fParent;\r
 453                 if (setRef != null) {\r
 454                     RBBINode varRef = setRef.fParent;\r
 455                     if (varRef != null  &&  varRef.fType == RBBINode.varRef) {\r
 456                         setName = varRef.fText;\r
 457                     }\r
 458                 }\r
 459                 System.out.print(setName); System.out.print("  ");\r
 460             }\r
 461             System.out.println("");\r
 462         }\r
 463     }\r
 464     ///CLOVER:ON\r
 465 \r
 466 \r
 467     //------------------------------------------------------------------------\r
 468     //\r
 469     //           printRangeGroups     A debugging function.\r
 470     //                                dump out all of the range groups.\r
 471     //\r
 472     //------------------------------------------------------------------------\r
 473     ///CLOVER:OFF\r
 474     void printRangeGroups() {\r
 475         RangeDescriptor       rlRange;\r
 476         RangeDescriptor       tRange;\r
 477         int                    i;\r
 478         int                    lastPrintedGroupNum = 0;\r
 479 \r
 480         System.out.print("\nRanges grouped by Unicode Set Membership...\n");\r
 481         for (rlRange = fRangeList; rlRange!=null; rlRange=rlRange.fNext) {\r
 482             int groupNum = rlRange.fNum & 0xbfff;\r
 483             if (groupNum > lastPrintedGroupNum) {\r
 484                 lastPrintedGroupNum = groupNum;\r
 485                 if (groupNum<10) {System.out.print(" ");}\r
 486                 System.out.print(groupNum + " ");\r
 487 \r
 488                 if ((rlRange.fNum & 0x4000) != 0) { System.out.print(" <DICT> ");}\r
 489 \r
 490                 for (i=0; i<rlRange.fIncludesSets.size(); i++) {\r
 491                     RBBINode       usetNode    = rlRange.fIncludesSets.get(i);\r
 492                     String         setName = "anon";\r
 493                     RBBINode       setRef = usetNode.fParent;\r
 494                     if (setRef != null) {\r
 495                         RBBINode varRef = setRef.fParent;\r
 496                         if (varRef != null  &&  varRef.fType == RBBINode.varRef) {\r
 497                             setName = varRef.fText;\r
 498                         }\r
 499                     }\r
 500                     System.out.print(setName); System.out.print(" ");\r
 501                 }\r
 502 \r
 503                 i = 0;\r
 504                 for (tRange = rlRange; tRange != null; tRange = tRange.fNext) {\r
 505                     if (tRange.fNum == rlRange.fNum) {\r
 506                         if (i++ % 5 == 0) {\r
 507                             System.out.print("\n    ");\r
 508                         }\r
 509                         RBBINode.printHex(tRange.fStartChar, -1);\r
 510                         System.out.print("-");\r
 511                         RBBINode.printHex(tRange.fEndChar, 0);\r
 512                     }\r
 513                 }\r
 514                 System.out.print("\n");\r
 515             }\r
 516         }\r
 517         System.out.print("\n");\r
 518     }\r
 519     ///CLOVER:ON\r
 520 \r
 521 \r
 522     //------------------------------------------------------------------------\r
 523     //\r
 524     //           printSets          A debugging function.\r
 525     //                              dump out all of the set definitions.\r
 526     //\r
 527     //------------------------------------------------------------------------\r
 528     ///CLOVER:OFF\r
 529     void printSets() {\r
 530         int                   i;\r
 531         System.out.print("\n\nUnicode Sets List\n------------------\n");\r
 532         for (i=0; i<fRB.fUSetNodes.size(); i++) {\r
 533             RBBINode        usetNode;\r
 534             RBBINode        setRef;\r
 535             RBBINode        varRef;\r
 536             String          setName;\r
 537 \r
 538             usetNode = fRB.fUSetNodes.get(i);\r
 539 \r
 540             //System.out.print(" " + i + "   ");\r
 541             RBBINode.printInt(2, i);\r
 542             setName = "anonymous";\r
 543             setRef = usetNode.fParent;\r
 544             if (setRef != null) {\r
 545                 varRef = setRef.fParent;\r
 546                 if (varRef != null  &&  varRef.fType == RBBINode.varRef) {\r
 547                     setName = varRef.fText;\r
 548                 }\r
 549             }\r
 550             System.out.print("  " + setName);\r
 551             System.out.print("   ");\r
 552             System.out.print(usetNode.fText);\r
 553             System.out.print("\n");\r
 554             if (usetNode.fLeftChild != null) {\r
 555                 usetNode.fLeftChild.printTree(true);\r
 556             }\r
 557         }\r
 558         System.out.print("\n");\r
 559     }\r
 560     ///CLOVER:ON\r
 561 }\r