jars/icu4j-4_2_1-src/src/com/ibm/icu/text/RBBITableBuilder.java

   1 /*\r
   2 **********************************************************************\r
   3 *   Copyright (c) 2002-2007, International Business Machines\r
   4 *   Corporation and others.  All Rights Reserved.\r
   5 **********************************************************************\r
   6 */\r
   7 \r
   8 package com.ibm.icu.text;\r
   9 \r
  10 import java.util.List;\r
  11 import java.util.ArrayList;\r
  12 import java.util.Set;\r
  13 import java.util.HashSet;\r
  14 import java.util.SortedSet;\r
  15 import java.util.TreeSet;\r
  16 import java.util.Iterator;\r
  17 import java.util.Collection;\r
  18 \r
  19 import com.ibm.icu.impl.Assert;\r
  20 import com.ibm.icu.lang.UCharacter;\r
  21 import com.ibm.icu.lang.UProperty;\r
  22 \r
  23 //\r
  24 //  class RBBITableBuilder is part of the RBBI rule compiler.\r
  25 //                         It builds the state transition table used by the RBBI runtime\r
  26 //                         from the expression syntax tree generated by the rule scanner.\r
  27 //\r
  28 //                         This class is part of the RBBI implementation only.\r
  29 //                         There is no user-visible public API here.\r
  30 //\r
  31 class RBBITableBuilder {\r
  32     \r
  33     \r
  34     \r
  35     //\r
  36     //  RBBIStateDescriptor - The DFA is initially constructed as a set of these descriptors,\r
  37     //                        one for each state.\r
  38     static class RBBIStateDescriptor {\r
  39         boolean      fMarked;\r
  40         int          fAccepting;\r
  41         int          fLookAhead;\r
  42         SortedSet    fTagVals;\r
  43         int          fTagsIdx;\r
  44         Set          fPositions;                 // Set of parse tree positions associated\r
  45                                                   //   with this state.  Unordered (it's a set).\r
  46                                                   //   UVector contents are RBBINode *\r
  47 \r
  48         int[]        fDtran;                      // Transitions out of this state.\r
  49                                                    //   indexed by input character\r
  50                                                    //   contents is int index of dest state\r
  51                                                    //   in RBBITableBuilder.fDStates\r
  52 \r
  53         RBBIStateDescriptor(int maxInputSymbol) {\r
  54             fTagVals = new TreeSet();\r
  55             fPositions = new HashSet();\r
  56             fDtran = new int[maxInputSymbol+1];    // fDtran needs to be pre-sized.\r
  57                                                     //   It is indexed by input symbols, and will\r
  58                                                     //   hold  the next state number for each\r
  59                                                     //   symbol.\r
  60         }\r
  61     }\r
  62     \r
  63     \r
  64     private  RBBIRuleBuilder  fRB;\r
  65     private  int             fRootIx;             // The array index into RBBIRuleBuilder.fTreeRoots\r
  66                                                    //   for the parse tree to operate on.\r
  67                                                    //   Too bad Java can't do indirection more easily!\r
  68 \r
  69     private  List             fDStates;       //  D states (Aho's terminology)\r
  70                                                //  Index is state number\r
  71                                                //  Contents are RBBIStateDescriptor pointers.\r
  72 \r
  73     //-----------------------------------------------------------------------------\r
  74     //\r
  75     //  Constructor    for RBBITableBuilder.\r
  76     //\r
  77     //                 rootNode is an index into the array of root nodes that is held by\r
  78     //                          the overall RBBIRuleBuilder.\r
  79     //-----------------------------------------------------------------------------\r
  80     RBBITableBuilder(RBBIRuleBuilder rb,  int rootNodeIx)  {\r
  81            fRootIx     = rootNodeIx;\r
  82            fRB         = rb;\r
  83            fDStates    = new ArrayList();\r
  84         }\r
  85 \r
  86 \r
  87 \r
  88  \r
  89        //-----------------------------------------------------------------------------\r
  90        //\r
  91        //   RBBITableBuilder::build  -  This is the main function for building the DFA state transtion\r
  92        //                               table from the RBBI rules parse tree.\r
  93        //\r
  94        //-----------------------------------------------------------------------------\r
  95        void  build() {\r
  96            // If there were no rules, just return.  This situation can easily arise\r
  97            //   for the reverse rules.\r
  98            if (fRB.fTreeRoots[fRootIx]==null) {\r
  99                return;\r
 100            }\r
 101 \r
 102            //\r
 103            // Walk through the tree, replacing any references to $variables with a copy of the\r
 104            //   parse tree for the substition expression.\r
 105            //\r
 106            fRB.fTreeRoots[fRootIx] = fRB.fTreeRoots[fRootIx].flattenVariables();\r
 107            if (fRB.fDebugEnv!=null && fRB.fDebugEnv.indexOf("ftree")>=0) {\r
 108                System.out.println("Parse tree after flattening variable references.");\r
 109                fRB.fTreeRoots[fRootIx].printTree(true);\r
 110            }\r
 111 \r
 112            //\r
 113            // If the rules contained any references to {bof} \r
 114            //   add a {bof} <cat> <former root of tree> to the\r
 115            //   tree.  Means that all matches must start out with the \r
 116            //   {bof} fake character.\r
 117            // \r
 118            if (fRB.fSetBuilder.sawBOF()) {\r
 119                RBBINode bofTop    = new RBBINode(RBBINode.opCat);\r
 120                RBBINode bofLeaf   = new RBBINode(RBBINode.leafChar);\r
 121                bofTop.fLeftChild  = bofLeaf;\r
 122                bofTop.fRightChild = fRB.fTreeRoots[fRootIx];\r
 123                bofLeaf.fParent    = bofTop;\r
 124                bofLeaf.fVal       = 2;      // Reserved value for {bof}.\r
 125                fRB.fTreeRoots[fRootIx] = bofTop;\r
 126            }\r
 127 \r
 128            //\r
 129            // Add a unique right-end marker to the expression.\r
 130            //   Appears as a cat-node, left child being the original tree,\r
 131            //   right child being the end marker.\r
 132            //\r
 133            RBBINode cn = new RBBINode(RBBINode.opCat);\r
 134            cn.fLeftChild = fRB.fTreeRoots[fRootIx];\r
 135            fRB.fTreeRoots[fRootIx].fParent = cn;\r
 136            cn.fRightChild = new RBBINode(RBBINode.endMark);\r
 137            cn.fRightChild.fParent = cn;\r
 138            fRB.fTreeRoots[fRootIx] = cn;\r
 139 \r
 140            //\r
 141            //  Replace all references to UnicodeSets with the tree for the equivalent\r
 142            //      expression.\r
 143            //\r
 144            fRB.fTreeRoots[fRootIx].flattenSets();\r
 145            if (fRB.fDebugEnv!=null && fRB.fDebugEnv.indexOf("stree")>=0) {\r
 146                System.out.println("Parse tree after flattening Unicode Set references.");\r
 147                fRB.fTreeRoots[fRootIx].printTree(true);\r
 148            }\r
 149 \r
 150 \r
 151            //\r
 152            // calculate the functions nullable, firstpos, lastpos and followpos on\r
 153            // nodes in the parse tree.\r
 154            //    See the alogrithm description in Aho.\r
 155            //    Understanding how this works by looking at the code alone will be\r
 156            //       nearly impossible.\r
 157            //\r
 158            calcNullable(fRB.fTreeRoots[fRootIx]);\r
 159            calcFirstPos(fRB.fTreeRoots[fRootIx]);\r
 160            calcLastPos(fRB.fTreeRoots[fRootIx]);\r
 161            calcFollowPos(fRB.fTreeRoots[fRootIx]);\r
 162            if (fRB.fDebugEnv!=null && fRB.fDebugEnv.indexOf("pos")>=0) {\r
 163                System.out.print("\n");\r
 164                printPosSets(fRB.fTreeRoots[fRootIx]);\r
 165            }\r
 166 \r
 167            //\r
 168            //  For "chained" rules, modify the followPos sets\r
 169            //\r
 170            if (fRB.fChainRules) {\r
 171                calcChainedFollowPos(fRB.fTreeRoots[fRootIx]);\r
 172            }\r
 173 \r
 174            //\r
 175            //  BOF (start of input) test fixup.\r
 176            //\r
 177            if (fRB.fSetBuilder.sawBOF()) {\r
 178                bofFixup();\r
 179            }\r
 180 \r
 181            //\r
 182            // Build the DFA state transition tables.\r
 183            //\r
 184            buildStateTable();\r
 185            flagAcceptingStates();\r
 186            flagLookAheadStates();\r
 187            flagTaggedStates();\r
 188 \r
 189            //\r
 190            // Update the global table of rule status {tag} values\r
 191            // The rule builder has a global vector of status values that are common\r
 192            //    for all tables.  Merge the ones from this table into the global set.\r
 193            //\r
 194            mergeRuleStatusVals();\r
 195 \r
 196            if (fRB.fDebugEnv!=null && fRB.fDebugEnv.indexOf("states")>=0) {printStates();}\r
 197        }\r
 198 \r
 199 \r
 200 \r
 201        //-----------------------------------------------------------------------------\r
 202        //\r
 203        //   calcNullable.    Impossible to explain succinctly.  See Aho, section 3.9\r
 204        //\r
 205        //-----------------------------------------------------------------------------\r
 206        void calcNullable(RBBINode n) {\r
 207            if (n == null) {\r
 208                return;\r
 209            }\r
 210            if (n.fType == RBBINode.setRef ||\r
 211                n.fType == RBBINode.endMark ) {\r
 212                // These are non-empty leaf node types.\r
 213                n.fNullable = false;\r
 214                return;\r
 215            }\r
 216 \r
 217            if (n.fType == RBBINode.lookAhead || n.fType == RBBINode.tag) {\r
 218                // Lookahead marker node.  It's a leaf, so no recursion on children.\r
 219                // It's nullable because it does not match any literal text from the input stream.\r
 220                n.fNullable = true;\r
 221                return;\r
 222            }\r
 223 \r
 224 \r
 225            // The node is not a leaf.\r
 226            //  Calculate nullable on its children.\r
 227            calcNullable(n.fLeftChild);\r
 228            calcNullable(n.fRightChild);\r
 229 \r
 230            // Apply functions from table 3.40 in Aho\r
 231            if (n.fType == RBBINode.opOr) {\r
 232                n.fNullable = n.fLeftChild.fNullable || n.fRightChild.fNullable;\r
 233            }\r
 234            else if (n.fType == RBBINode.opCat) {\r
 235                n.fNullable = n.fLeftChild.fNullable && n.fRightChild.fNullable;\r
 236            }\r
 237            else if (n.fType == RBBINode.opStar || n.fType == RBBINode.opQuestion) {\r
 238                n.fNullable = true;\r
 239            }\r
 240            else {\r
 241                n.fNullable = false;\r
 242            }\r
 243        }\r
 244 \r
 245 \r
 246 \r
 247 \r
 248        //-----------------------------------------------------------------------------\r
 249        //\r
 250        //   calcFirstPos.    Impossible to explain succinctly.  See Aho, section 3.9\r
 251        //\r
 252        //-----------------------------------------------------------------------------\r
 253        void calcFirstPos(RBBINode n) {\r
 254            if (n == null) {\r
 255                return;\r
 256            }\r
 257            if (n.fType == RBBINode.leafChar  ||\r
 258                n.fType == RBBINode.endMark   ||\r
 259                n.fType == RBBINode.lookAhead ||\r
 260                n.fType == RBBINode.tag) {\r
 261                // These are non-empty leaf node types.\r
 262                n.fFirstPosSet.add(n);\r
 263                return;\r
 264            }\r
 265 \r
 266            // The node is not a leaf.\r
 267            //  Calculate firstPos on its children.\r
 268            calcFirstPos(n.fLeftChild);\r
 269            calcFirstPos(n.fRightChild);\r
 270 \r
 271            // Apply functions from table 3.40 in Aho\r
 272            if (n.fType == RBBINode.opOr) {\r
 273                n.fFirstPosSet.addAll(n.fLeftChild.fFirstPosSet);\r
 274                n.fFirstPosSet.addAll(n.fRightChild.fFirstPosSet);\r
 275            }\r
 276            else if (n.fType == RBBINode.opCat) {\r
 277                n.fFirstPosSet.addAll(n.fLeftChild.fFirstPosSet);\r
 278                if (n.fLeftChild.fNullable) {\r
 279                    n.fFirstPosSet.addAll(n.fRightChild.fFirstPosSet);\r
 280                }\r
 281            }\r
 282            else if (n.fType == RBBINode.opStar ||\r
 283                     n.fType == RBBINode.opQuestion ||\r
 284                     n.fType == RBBINode.opPlus) {\r
 285                n.fFirstPosSet.addAll(n.fLeftChild.fFirstPosSet);\r
 286            }\r
 287        }\r
 288 \r
 289 \r
 290 \r
 291        //-----------------------------------------------------------------------------\r
 292        //\r
 293        //   calcLastPos.    Impossible to explain succinctly.  See Aho, section 3.9\r
 294        //\r
 295        //-----------------------------------------------------------------------------\r
 296        void calcLastPos(RBBINode n) {\r
 297            if (n == null) {\r
 298                return;\r
 299            }\r
 300            if (n.fType == RBBINode.leafChar  ||\r
 301                n.fType == RBBINode.endMark   ||\r
 302                n.fType == RBBINode.lookAhead ||\r
 303                n.fType == RBBINode.tag) {\r
 304                // These are non-empty leaf node types.\r
 305                n.fLastPosSet.add(n);\r
 306                return;\r
 307            }\r
 308 \r
 309            // The node is not a leaf.\r
 310            //  Calculate lastPos on its children.\r
 311            calcLastPos(n.fLeftChild);\r
 312            calcLastPos(n.fRightChild);\r
 313 \r
 314            // Apply functions from table 3.40 in Aho\r
 315            if (n.fType == RBBINode.opOr) {\r
 316                n.fLastPosSet.addAll(n.fLeftChild.fLastPosSet);\r
 317                n.fLastPosSet.addAll(n.fRightChild.fLastPosSet);\r
 318            }\r
 319            else if (n.fType == RBBINode.opCat) {\r
 320                n.fLastPosSet.addAll(n.fRightChild.fLastPosSet);\r
 321                if (n.fRightChild.fNullable) {\r
 322                    n.fLastPosSet.addAll(n.fLeftChild.fLastPosSet);\r
 323                }\r
 324            }\r
 325            else if (n.fType == RBBINode.opStar     ||\r
 326                     n.fType == RBBINode.opQuestion ||\r
 327                     n.fType == RBBINode.opPlus) {\r
 328                n.fLastPosSet.addAll(n.fLeftChild.fLastPosSet);\r
 329            }\r
 330        }\r
 331 \r
 332 \r
 333 \r
 334        //-----------------------------------------------------------------------------\r
 335        //\r
 336        //   calcFollowPos.    Impossible to explain succinctly.  See Aho, section 3.9\r
 337        //\r
 338        //-----------------------------------------------------------------------------\r
 339        void calcFollowPos(RBBINode n) {\r
 340            if (n == null ||\r
 341                n.fType == RBBINode.leafChar ||\r
 342                n.fType == RBBINode.endMark) {\r
 343                return;\r
 344            }\r
 345 \r
 346            calcFollowPos(n.fLeftChild);\r
 347            calcFollowPos(n.fRightChild);\r
 348 \r
 349            // Aho rule #1\r
 350            if (n.fType == RBBINode.opCat) {\r
 351                RBBINode i;   // is 'i' in Aho's description\r
 352 \r
 353                Set LastPosOfLeftChild = n.fLeftChild.fLastPosSet;\r
 354 \r
 355                Iterator ix = LastPosOfLeftChild.iterator();\r
 356                while (ix.hasNext()) {\r
 357                    i = (RBBINode )ix.next();\r
 358                    i.fFollowPos.addAll(n.fRightChild.fFirstPosSet);\r
 359                }\r
 360            }\r
 361 \r
 362            // Aho rule #2\r
 363            if (n.fType == RBBINode.opStar ||\r
 364                n.fType == RBBINode.opPlus) {\r
 365                RBBINode   i;  // again, n and i are the names from Aho's description.\r
 366                Iterator   ix = n.fLastPosSet.iterator();\r
 367                while (ix.hasNext()) {\r
 368                    i = (RBBINode) ix.next();\r
 369                    i.fFollowPos.addAll(n.fFirstPosSet);\r
 370                }\r
 371 \r
 372            }\r
 373 \r
 374 \r
 375 \r
 376        }\r
 377 \r
 378 \r
 379        //-----------------------------------------------------------------------------\r
 380        //\r
 381        //   calcChainedFollowPos.    Modify the previously calculated followPos sets\r
 382        //                            to implement rule chaining.  NOT described by Aho\r
 383        //\r
 384        //-----------------------------------------------------------------------------\r
 385        void calcChainedFollowPos(RBBINode tree) {\r
 386 \r
 387            List        endMarkerNodes = new ArrayList();\r
 388            List        leafNodes      = new ArrayList();\r
 389 \r
 390             // get a list of all endmarker nodes.\r
 391            tree.findNodes(endMarkerNodes, RBBINode.endMark);\r
 392 \r
 393            // get a list all leaf nodes\r
 394            tree.findNodes(leafNodes, RBBINode.leafChar);\r
 395 \r
 396            // Get all nodes that can be the start a match, which is FirstPosition()\r
 397            // of the portion of the tree corresponding to user-written rules.\r
 398            // See the tree description in bofFixup().\r
 399            RBBINode userRuleRoot = tree;\r
 400            if (fRB.fSetBuilder.sawBOF()) {\r
 401                userRuleRoot = tree.fLeftChild.fRightChild;\r
 402            }\r
 403            Assert.assrt(userRuleRoot != null);\r
 404            Set matchStartNodes = userRuleRoot.fFirstPosSet;\r
 405 \r
 406 \r
 407            // Iteratate over all leaf nodes,\r
 408            //\r
 409            Iterator  endNodeIx = leafNodes.iterator();\r
 410 \r
 411            while (endNodeIx.hasNext()) {\r
 412                RBBINode tNode   = (RBBINode)endNodeIx.next();\r
 413                RBBINode endNode = null;\r
 414 \r
 415                // Identify leaf nodes that correspond to overall rule match positions.\r
 416                //   These include an endMarkerNode in their followPos sets.\r
 417                Iterator i = endMarkerNodes.iterator();\r
 418                while (i.hasNext()) {\r
 419                    RBBINode endMarkerNode = (RBBINode)i.next();\r
 420                    if (tNode.fFollowPos.contains(endMarkerNode)) {\r
 421                        endNode = tNode;\r
 422                        break;\r
 423                    }\r
 424                }\r
 425                if (endNode == null) {\r
 426                    // node wasn't an end node.  Try again with the next.\r
 427                    continue;\r
 428                }\r
 429 \r
 430                // We've got a node that can end a match.\r
 431 \r
 432                // Line Break Specific hack:  If this node's val correspond to the $CM char class,\r
 433                //                            don't chain from it.\r
 434                // TODO:  Add rule syntax for this behavior, get specifics out of here and\r
 435                //        into the rule file.\r
 436                if (fRB.fLBCMNoChain) {\r
 437                    int c = this.fRB.fSetBuilder.getFirstChar(endNode.fVal);\r
 438                    if (c != -1) {\r
 439                        // c == -1 occurs with sets containing only the {eof} marker string.\r
 440                        int cLBProp = UCharacter.getIntPropertyValue(c, UProperty.LINE_BREAK);\r
 441                        if (cLBProp == UCharacter.LineBreak.COMBINING_MARK) {\r
 442                            continue;\r
 443                        }\r
 444                    }\r
 445                }\r
 446 \r
 447 \r
 448                // Now iterate over the nodes that can start a match, looking for ones\r
 449                //   with the same char class as our ending node.\r
 450                RBBINode startNode;\r
 451                Iterator  startNodeIx = matchStartNodes.iterator();\r
 452                while (startNodeIx.hasNext()) {\r
 453                    startNode = (RBBINode )startNodeIx.next();\r
 454                    if (startNode.fType != RBBINode.leafChar) {\r
 455                        continue;\r
 456                    }\r
 457 \r
 458                    if (endNode.fVal == startNode.fVal) {\r
 459                        // The end val (character class) of one possible match is the\r
 460                        //   same as the start of another.\r
 461 \r
 462                        // Add all nodes from the followPos of the start node to the\r
 463                        //  followPos set of the end node, which will have the effect of\r
 464                        //  letting matches transition from a match state at endNode\r
 465                        //  to the second char of a match starting with startNode.\r
 466                        endNode.fFollowPos.addAll(startNode.fFollowPos);\r
 467                    }\r
 468                }\r
 469            }\r
 470        }\r
 471 \r
 472 \r
 473        //-----------------------------------------------------------------------------\r
 474        //\r
 475        //   bofFixup.    Fixup for state tables that include {bof} beginning of input testing.\r
 476        //                Do an swizzle similar to chaining, modifying the followPos set of\r
 477        //                the bofNode to include the followPos nodes from other {bot} nodes\r
 478        //                scattered through the tree.\r
 479        //\r
 480        //                This function has much in common with calcChainedFollowPos().\r
 481        //\r
 482        //-----------------------------------------------------------------------------\r
 483        void bofFixup() {\r
 484            //\r
 485            //   The parse tree looks like this ...\r
 486            //         fTree root  --.       <cat>\r
 487            //                               /     \   \r
 488            //                            <cat>   <#end node>\r
 489            //                           /     \   \r
 490            //                     <bofNode>   rest\r
 491            //                               of tree\r
 492            //\r
 493            //    We will be adding things to the followPos set of the <bofNode>\r
 494            //\r
 495            RBBINode  bofNode = fRB.fTreeRoots[fRootIx].fLeftChild.fLeftChild;\r
 496            Assert.assrt(bofNode.fType == RBBINode.leafChar);\r
 497            Assert.assrt(bofNode.fVal == 2);\r
 498 \r
 499            // Get all nodes that can be the start a match of the user-written rules\r
 500            //  (excluding the fake bofNode)\r
 501            //  We want the nodes that can start a match in the\r
 502            //     part labeled "rest of tree"\r
 503            // \r
 504            Set matchStartNodes = fRB.fTreeRoots[fRootIx].fLeftChild.fRightChild.fFirstPosSet;\r
 505            Iterator startNodeIt = matchStartNodes.iterator();\r
 506            while (startNodeIt.hasNext()) {\r
 507                RBBINode startNode = (RBBINode)startNodeIt.next();\r
 508                if (startNode.fType != RBBINode.leafChar) {\r
 509                    continue;\r
 510                }\r
 511 \r
 512                if (startNode.fVal == bofNode.fVal) {\r
 513                    //  We found a leaf node corresponding to a {bof} that was\r
 514                    //    explicitly written into a rule.\r
 515                    //  Add everything from the followPos set of this node to the\r
 516                    //    followPos set of the fake bofNode at the start of the tree.\r
 517                    //  \r
 518                    bofNode.fFollowPos.addAll(startNode.fFollowPos);\r
 519                }\r
 520            }\r
 521        }\r
 522 \r
 523        //-----------------------------------------------------------------------------\r
 524        //\r
 525        //   buildStateTable()    Determine the set of runtime DFA states and the\r
 526        //                        transition tables for these states, by the algorithm\r
 527        //                        of fig. 3.44 in Aho.\r
 528        //\r
 529        //                        Most of the comments are quotes of Aho's psuedo-code.\r
 530        //\r
 531        //-----------------------------------------------------------------------------\r
 532        void buildStateTable() {\r
 533            //\r
 534            // Add a dummy state 0 - the stop state.  Not from Aho.\r
 535            int      lastInputSymbol = fRB.fSetBuilder.getNumCharCategories() - 1;\r
 536            RBBIStateDescriptor failState = new RBBIStateDescriptor(lastInputSymbol);\r
 537            fDStates.add(failState);\r
 538 \r
 539            // initially, the only unmarked state in Dstates is firstpos(root),\r
 540            //       where toot is the root of the syntax tree for (r)#;\r
 541            RBBIStateDescriptor initialState = new RBBIStateDescriptor(lastInputSymbol);\r
 542            initialState.fPositions.addAll(fRB.fTreeRoots[fRootIx].fFirstPosSet);\r
 543            fDStates.add(initialState);\r
 544 \r
 545            // while there is an unmarked state T in Dstates do begin\r
 546            for (;;) {\r
 547                RBBIStateDescriptor T = null;\r
 548                int              tx;\r
 549                for (tx=1; tx<fDStates.size(); tx++) {\r
 550                    RBBIStateDescriptor temp  = (RBBIStateDescriptor )fDStates.get(tx);\r
 551                    if (temp.fMarked == false) {\r
 552                        T = temp;\r
 553                        break;\r
 554                    }\r
 555                }\r
 556                if (T == null) {\r
 557                    break;\r
 558                }\r
 559 \r
 560                // mark T;\r
 561                T.fMarked = true;\r
 562 \r
 563                // for each input symbol a do begin\r
 564                int  a;\r
 565                for (a = 1; a<=lastInputSymbol; a++) {\r
 566                    // let U be the set of positions that are in followpos(p)\r
 567                    //    for some position p in T\r
 568                    //    such that the symbol at position p is a;\r
 569                    Set        U = null;\r
 570                    RBBINode   p;\r
 571                    Iterator   pit = T.fPositions.iterator();\r
 572                    while (pit.hasNext()) {\r
 573                        p = (RBBINode )pit.next();\r
 574                        if ((p.fType == RBBINode.leafChar) &&  (p.fVal == a)) {\r
 575                            if (U == null) {\r
 576                                U = new HashSet();\r
 577                            }\r
 578                            U.addAll(p.fFollowPos);\r
 579                        }\r
 580                    }\r
 581 \r
 582                    // if U is not empty and not in DStates then\r
 583                    int  ux = 0;\r
 584                    boolean    UinDstates = false;\r
 585                    if (U != null) {\r
 586                        Assert.assrt(U.size() > 0);\r
 587                        int  ix;\r
 588                        for (ix=0; ix<fDStates.size(); ix++) {\r
 589                            RBBIStateDescriptor temp2;\r
 590                            temp2 = (RBBIStateDescriptor )fDStates.get(ix);\r
 591                            if (U.equals(temp2.fPositions)) {\r
 592                                U  = temp2.fPositions;\r
 593                                ux = ix;\r
 594                                UinDstates = true;\r
 595                                break;\r
 596                            }\r
 597                        }\r
 598 \r
 599                        // Add U as an unmarked state to Dstates\r
 600                        if (!UinDstates)\r
 601                        {\r
 602                            RBBIStateDescriptor newState = new RBBIStateDescriptor(lastInputSymbol);\r
 603                            newState.fPositions = U;\r
 604                            fDStates.add(newState);\r
 605                            ux = fDStates.size()-1;\r
 606                        }\r
 607 \r
 608                        // Dtran[T, a] := U;\r
 609                        T.fDtran[a] = ux;\r
 610                    }\r
 611                }\r
 612            }\r
 613        }\r
 614 \r
 615 \r
 616 \r
 617        //-----------------------------------------------------------------------------\r
 618        //\r
 619        //   flagAcceptingStates    Identify accepting states.\r
 620        //                          First get a list of all of the end marker nodes.\r
 621        //                          Then, for each state s,\r
 622        //                              if s contains one of the end marker nodes in its list of tree positions then\r
 623        //                                  s is an accepting state.\r
 624        //\r
 625        //-----------------------------------------------------------------------------\r
 626        void     flagAcceptingStates() {\r
 627            List        endMarkerNodes = new ArrayList();\r
 628            RBBINode    endMarker;\r
 629            int     i;\r
 630            int     n;\r
 631 \r
 632            fRB.fTreeRoots[fRootIx].findNodes(endMarkerNodes, RBBINode.endMark);\r
 633 \r
 634            for (i=0; i<endMarkerNodes.size(); i++) {\r
 635                endMarker = (RBBINode)endMarkerNodes.get(i);\r
 636                for (n=0; n<fDStates.size(); n++) {\r
 637                    RBBIStateDescriptor sd = (RBBIStateDescriptor )fDStates.get(n);\r
 638                    //if (sd.fPositions.indexOf(endMarker) >= 0) {\r
 639                    if (sd.fPositions.contains(endMarker)) {\r
 640                        // Any non-zero value for fAccepting means this is an accepting node.\r
 641                        // The value is what will be returned to the user as the break status.\r
 642                        // If no other value was specified, force it to -1.\r
 643 \r
 644                        if (sd.fAccepting==0) {\r
 645                         // State hasn't been marked as accepting yet.  Do it now.\r
 646                            sd.fAccepting = endMarker.fVal;\r
 647                            if (sd.fAccepting == 0) {\r
 648                                sd.fAccepting = -1;\r
 649                         }\r
 650                        }\r
 651                        if (sd.fAccepting==-1 && endMarker.fVal != 0) {\r
 652                         // Both lookahead and non-lookahead accepting for this state.\r
 653                         // Favor the look-ahead.  Expedient for line break.\r
 654                         // TODO:  need a more elegant resolution for conflicting rules.\r
 655                         sd.fAccepting = endMarker.fVal;\r
 656                     }\r
 657                         // implicit else:\r
 658                         // if sd.fAccepting already had a value other than 0 or -1, leave it be.\r
 659 \r
 660                        // If the end marker node is from a look-ahead rule, set\r
 661                        //   the fLookAhead field or this state also.\r
 662                        if (endMarker.fLookAheadEnd) {\r
 663                         // TODO:  don't change value if already set?\r
 664                         // TODO:  allow for more than one active look-ahead rule in engine.\r
 665                         //        Make value here an index to a side array in engine?\r
 666                            sd.fLookAhead = sd.fAccepting;\r
 667                        }\r
 668                    }\r
 669                }\r
 670            }\r
 671        }\r
 672 \r
 673 \r
 674        //-----------------------------------------------------------------------------\r
 675        //\r
 676        //    flagLookAheadStates   Very similar to flagAcceptingStates, above.\r
 677        //\r
 678        //-----------------------------------------------------------------------------\r
 679        void     flagLookAheadStates() {\r
 680            List        lookAheadNodes = new ArrayList();\r
 681            RBBINode    lookAheadNode;\r
 682            int     i;\r
 683            int     n;\r
 684 \r
 685            fRB.fTreeRoots[fRootIx].findNodes(lookAheadNodes, RBBINode.lookAhead);\r
 686            for (i=0; i<lookAheadNodes.size(); i++) {\r
 687                lookAheadNode = (RBBINode )lookAheadNodes.get(i);\r
 688 \r
 689                for (n=0; n<fDStates.size(); n++) {\r
 690                    RBBIStateDescriptor sd = (RBBIStateDescriptor )fDStates.get(n);\r
 691                    if (sd.fPositions.contains(lookAheadNode)) {\r
 692                        sd.fLookAhead = lookAheadNode.fVal;\r
 693                    }\r
 694                }\r
 695            }\r
 696        }\r
 697 \r
 698 \r
 699 \r
 700 \r
 701        //-----------------------------------------------------------------------------\r
 702        //\r
 703        //    flagTaggedStates\r
 704        //\r
 705        //-----------------------------------------------------------------------------\r
 706        void     flagTaggedStates() {\r
 707            List        tagNodes = new ArrayList();\r
 708            RBBINode    tagNode;\r
 709            int     i;\r
 710            int     n;\r
 711 \r
 712            fRB.fTreeRoots[fRootIx].findNodes(tagNodes, RBBINode.tag);\r
 713            for (i=0; i<tagNodes.size(); i++) {                   // For each tag node t (all of 'em)\r
 714                tagNode = (RBBINode )tagNodes.get(i);\r
 715 \r
 716                for (n=0; n<fDStates.size(); n++) {              //    For each state  s (row in the state table)\r
 717                    RBBIStateDescriptor sd = (RBBIStateDescriptor )fDStates.get(n);\r
 718                    if (sd.fPositions.contains(tagNode)) {       //       if  s include the tag node t\r
 719                        sd.fTagVals.add(new Integer(tagNode.fVal));\r
 720                    }\r
 721                }\r
 722            }\r
 723        }\r
 724 \r
 725 \r
 726 \r
 727        //-----------------------------------------------------------------------------\r
 728        //\r
 729        //  mergeRuleStatusVals\r
 730        //\r
 731        //      Allocate positions in the  global array of rule status {tag} values\r
 732        //\r
 733        //      The RBBI runtime uses an array of {sets of status values} that can\r
 734        //      be returned for boundaries.  Each accepting state that has non-zero\r
 735        //      status includes an index into this array.  The format of the array\r
 736        //      is \r
 737        //           Num of status values in group 1\r
 738        //              status val\r
 739        //              status val\r
 740        //              ...\r
 741        //           Num of status vals in group 2\r
 742        //              status val\r
 743        //              status val\r
 744        //              ...\r
 745        //           etc.\r
 746        //\r
 747        //\r
 748        //-----------------------------------------------------------------------------\r
 749        \r
 750        void  mergeRuleStatusVals() {\r
 751            //\r
 752            //  The basic outline of what happens here is this...\r
 753            //\r
 754            //    for each state in this state table\r
 755            //       if the status tag list for this state is in the global statuses list\r
 756            //           record where and\r
 757            //           continue with the next state\r
 758            //       else\r
 759            //           add the tag list for this state to the global list.\r
 760            //\r
 761            int n;\r
 762            \r
 763            // Pre-load a single tag of {0} into the table.\r
 764            //   We will need this as a default, for rule sets with no explicit tagging,\r
 765            //   or with explicit tagging of {0}.\r
 766            if (fRB.fRuleStatusVals.size() == 0) {              \r
 767                fRB.fRuleStatusVals.add(new Integer(1));    // Num of statuses in group\r
 768                fRB.fRuleStatusVals.add(new Integer(0));    //   and our single status of zero\r
 769                \r
 770                SortedSet s0 = new TreeSet();\r
 771                Integer izero = new Integer(0);\r
 772                fRB.fStatusSets.put(s0, izero);\r
 773                SortedSet s1 = new TreeSet();\r
 774                s1.add(izero);\r
 775                fRB.fStatusSets.put(s0, izero);\r
 776            }\r
 777 \r
 778            //    For each state, check whether the state's status tag values are\r
 779            //       already entered into the status values array, and add them if not.\r
 780            for (n=0; n<fDStates.size(); n++) {\r
 781                RBBIStateDescriptor sd = (RBBIStateDescriptor )fDStates.get(n);\r
 782                Set statusVals = sd.fTagVals;\r
 783                Integer arrayIndexI = (Integer)fRB.fStatusSets.get(statusVals);\r
 784                if (arrayIndexI == null) {\r
 785                    // This is the first encounter of this set of status values.\r
 786                    //   Add them to the statusSets map, This map associates\r
 787                    //   the set of status values with an index in the runtime status \r
 788                    //   values array.\r
 789                    arrayIndexI = new Integer(fRB.fRuleStatusVals.size());\r
 790                    fRB.fStatusSets.put(statusVals, arrayIndexI);\r
 791                    \r
 792                    // Add the new set of status values to the vector of values that\r
 793                    //   will eventually become the array used by the runtime engine.\r
 794                    fRB.fRuleStatusVals.add(new Integer(statusVals.size()));\r
 795                    Iterator it = statusVals.iterator();\r
 796                    while (it.hasNext()) {\r
 797                        fRB.fRuleStatusVals.add(it.next());\r
 798                    }\r
 799                \r
 800                }\r
 801                \r
 802                // Save the runtime array index back into the state descriptor.\r
 803                sd.fTagsIdx = arrayIndexI.intValue();\r
 804            }          \r
 805        }\r
 806 \r
 807 \r
 808 \r
 809 \r
 810 \r
 811 \r
 812 \r
 813        //-----------------------------------------------------------------------------\r
 814        //\r
 815        //  printPosSets   Debug function.  Dump Nullable, firstpos, lastpos and followpos\r
 816        //                 for each node in the tree.\r
 817        //\r
 818        //-----------------------------------------------------------------------------\r
 819        \r
 820        void printPosSets(RBBINode n) {\r
 821            if (n==null) {\r
 822                return;\r
 823            }\r
 824            RBBINode.printNode(n);\r
 825            System.out.print("         Nullable:  " + n.fNullable);\r
 826 \r
 827            System.out.print("         firstpos:  ");\r
 828            printSet(n.fFirstPosSet);\r
 829 \r
 830            System.out.print("         lastpos:   ");\r
 831            printSet(n.fLastPosSet);\r
 832 \r
 833            System.out.print("         followpos: ");\r
 834            printSet(n.fFollowPos);\r
 835 \r
 836            printPosSets(n.fLeftChild);\r
 837            printPosSets(n.fRightChild);\r
 838        }\r
 839        \r
 840 \r
 841 \r
 842 \r
 843        //-----------------------------------------------------------------------------\r
 844        //\r
 845        //   getTableSize()    Calculate the size in bytes of the runtime form of this\r
 846        //                     state transition table.\r
 847        //\r
 848        //          Note:  Refer to common/rbbidata.h from ICU4C for the declarations\r
 849        //                 of the structures being matched by this calculation.\r
 850        //\r
 851        //-----------------------------------------------------------------------------\r
 852        int  getTableSize()  {\r
 853            int    size = 0;\r
 854            int    numRows;\r
 855            int    numCols;\r
 856            int    rowSize;\r
 857 \r
 858            if (fRB.fTreeRoots[fRootIx] == null) {\r
 859                return 0;\r
 860            }\r
 861 \r
 862            size    = /*sizeof(RBBIStateTable) - 4 */ 16;    // The header, with no rows to the table.\r
 863 \r
 864            numRows = fDStates.size();\r
 865            numCols = fRB.fSetBuilder.getNumCharCategories();\r
 866 \r
 867            //  Note  The declaration of RBBIStateTableRow is for a table of two columns.\r
 868            //        Therefore we subtract two from numCols when determining\r
 869            //        how much storage to add to a row for the total columns.\r
 870            // rowSize = sizeof(RBBIStateTableRow) + sizeof(uint16_t)*(numCols-2);\r
 871            rowSize = 8 + 2*numCols;\r
 872            size   += numRows * rowSize;\r
 873            while (size % 8 > 0) {    // Size must be multiple of 8 bytes in size.\r
 874                size++;\r
 875            }\r
 876 \r
 877            return size;\r
 878        }\r
 879 \r
 880 \r
 881 \r
 882        //-----------------------------------------------------------------------------\r
 883        //\r
 884        //   exportTable()    export the state transition table in the ICU4C format.\r
 885        //\r
 886        //                    Most of the table is 16 bit shorts.  This function exports\r
 887        //                    the whole thing as an array of shorts.\r
 888        //\r
 889        //                    The size of the array must be rounded up to a multiple of\r
 890        //                    8 bytes.\r
 891        //\r
 892        //                    See struct RBBIStateTable in ICU4C, common/rbbidata.h\r
 893        //\r
 894        //-----------------------------------------------------------------------------\r
 895        \r
 896        short [] exportTable() {\r
 897            int                state;\r
 898            int                col;\r
 899 \r
 900            if (fRB.fTreeRoots[fRootIx] == null) {\r
 901                return new short[0];\r
 902            }\r
 903 \r
 904            Assert.assrt(fRB.fSetBuilder.getNumCharCategories() < 0x7fff &&\r
 905                fDStates.size() < 0x7fff); \r
 906 \r
 907            int numStates = fDStates.size();\r
 908     \r
 909            // Size of table size in shorts.\r
 910            //  the "4" is the size of struct RBBIStateTableRow, the row header part only.\r
 911            int rowLen = 4 + fRB.fSetBuilder.getNumCharCategories();\r
 912            int tableSize = getTableSize() / 2;\r
 913 \r
 914            \r
 915            short [] table = new short[tableSize];\r
 916            \r
 917            //\r
 918            // Fill in the header fields.\r
 919            //      Annoying because they really want to be ints, not shorts.\r
 920            //\r
 921            // RBBIStateTable.fNumStates\r
 922            table[RBBIDataWrapper.NUMSTATES]   = (short)(numStates >>> 16);\r
 923            table[RBBIDataWrapper.NUMSTATES+1] = (short)(numStates & 0x0000ffff);\r
 924 \r
 925            // RBBIStateTable.fRowLen\r
 926            table[RBBIDataWrapper.ROWLEN]   = (short)(rowLen >>> 16);\r
 927            table[RBBIDataWrapper.ROWLEN+1] = (short)(rowLen & 0x0000ffff);\r
 928            \r
 929            // RBBIStateTable.fFlags\r
 930            int flags = 0;\r
 931            if (fRB.fLookAheadHardBreak) {\r
 932                flags  |= RBBIDataWrapper.RBBI_LOOKAHEAD_HARD_BREAK;\r
 933            }\r
 934            if (fRB.fSetBuilder.sawBOF()) {\r
 935                flags  |= RBBIDataWrapper.RBBI_BOF_REQUIRED;\r
 936            }\r
 937            table[RBBIDataWrapper.FLAGS]   = (short)(flags >>> 16);\r
 938            table[RBBIDataWrapper.FLAGS+1] = (short)(flags & 0x0000ffff);\r
 939            \r
 940            int numCharCategories = fRB.fSetBuilder.getNumCharCategories();\r
 941            for (state=0; state<numStates; state++) {\r
 942                RBBIStateDescriptor sd = (RBBIStateDescriptor )fDStates.get(state);\r
 943                int                row = 8 + state*rowLen;\r
 944                Assert.assrt (-32768 < sd.fAccepting && sd.fAccepting <= 32767);\r
 945                Assert.assrt (-32768 < sd.fLookAhead && sd.fLookAhead <= 32767);\r
 946                table[row + RBBIDataWrapper.ACCEPTING] = (short)sd.fAccepting;\r
 947                table[row + RBBIDataWrapper.LOOKAHEAD] = (short)sd.fLookAhead;\r
 948                table[row + RBBIDataWrapper.TAGIDX]    = (short)sd.fTagsIdx;\r
 949                for (col=0; col<numCharCategories; col++) {\r
 950                    table[row + RBBIDataWrapper.NEXTSTATES + col] = (short)sd.fDtran[col];\r
 951                }\r
 952            }\r
 953            return table;\r
 954        }\r
 955 \r
 956 \r
 957 \r
 958        //-----------------------------------------------------------------------------\r
 959        //\r
 960        //   printSet    Debug function.   Print the contents of a set of Nodes\r
 961        //\r
 962        //-----------------------------------------------------------------------------\r
 963        \r
 964        void printSet(Collection s) {\r
 965            Iterator it = s.iterator();\r
 966            while (it.hasNext()) {\r
 967                RBBINode n = (RBBINode)it.next();\r
 968                RBBINode.printInt(n.fSerialNum, 8);\r
 969            }\r
 970            System.out.println();\r
 971        }\r
 972        \r
 973 \r
 974 \r
 975        //-----------------------------------------------------------------------------\r
 976        //\r
 977        //   printStates    Debug Function.  Dump the fully constructed state transition table.\r
 978        //\r
 979        //-----------------------------------------------------------------------------\r
 980        \r
 981        void printStates() {\r
 982            int     c;    // input "character"\r
 983            int     n;    // state number\r
 984 \r
 985            System.out.print("state |           i n p u t     s y m b o l s \n");\r
 986            System.out.print("      | Acc  LA    Tag");\r
 987            for (c=0; c<fRB.fSetBuilder.getNumCharCategories(); c++) {\r
 988                RBBINode.printInt((int)c, 3);\r
 989            }\r
 990            System.out.print("\n");\r
 991            System.out.print("      |---------------");\r
 992            for (c=0; c<fRB.fSetBuilder.getNumCharCategories(); c++) {\r
 993                System.out.print("---");\r
 994            }\r
 995            System.out.print("\n");\r
 996 \r
 997            for (n=0; n<fDStates.size(); n++) {\r
 998                RBBIStateDescriptor sd = (RBBIStateDescriptor)fDStates.get(n);\r
 999                RBBINode.printInt(n, 5);\r
1000                System.out.print(" | ");\r
1001                \r
1002                RBBINode.printInt(sd.fAccepting, 3);\r
1003                RBBINode.printInt(sd.fLookAhead, 4);\r
1004                RBBINode.printInt(sd.fTagsIdx, 6);\r
1005                System.out.print(" ");\r
1006                for (c=0; c<fRB.fSetBuilder.getNumCharCategories(); c++) {\r
1007                    RBBINode.printInt(sd.fDtran[c], 3);\r
1008                }\r
1009                System.out.print("\n");\r
1010            }\r
1011            System.out.print("\n\n");\r
1012        }\r
1013        \r
1014 \r
1015 \r
1016 \r
1017        //-----------------------------------------------------------------------------\r
1018        //\r
1019        //   printRuleStatusTable    Debug Function.  Dump the common rule status table\r
1020        //\r
1021        //-----------------------------------------------------------------------------\r
1022        \r
1023        void printRuleStatusTable() {\r
1024            int  thisRecord = 0;\r
1025            int  nextRecord = 0;\r
1026            int      i;\r
1027            List  tbl = fRB.fRuleStatusVals;\r
1028 \r
1029            System.out.print("index |  tags \n");\r
1030            System.out.print("-------------------\n");\r
1031 \r
1032            while (nextRecord < tbl.size()) {\r
1033                thisRecord = nextRecord;\r
1034                nextRecord = thisRecord + ((Integer)tbl.get(thisRecord)).intValue() + 1;\r
1035                RBBINode.printInt(thisRecord, 7);\r
1036                for (i=thisRecord+1; i<nextRecord; i++) {\r
1037                    int val = ((Integer)tbl.get(i)).intValue();\r
1038                    RBBINode.printInt(val, 7);\r
1039                }\r
1040                System.out.print("\n");\r
1041            }\r
1042            System.out.print("\n\n");\r
1043        }\r
1044        \r
1045 \r
1046 \r
1047 }\r