jars/icu4j-4_8_1_1/main/classes/core/src/com/ibm/icu/text/RBBINode.java

   1 /********************************************************************
   2  * COPYRIGHT:
   3  * Copyright (c) 2001-2010, International Business Machines Corporation and
   4  * others. All Rights Reserved.
   5  ********************************************************************/
   6
   7 package com.ibm.icu.text;
   8
   9 import java.util.HashSet;
  10 import java.util.List;
  11 import java.util.Set;
  12
  13 import com.ibm.icu.impl.Assert;
  14
  15 /**
  16  *   This class represents a node in the parse tree created by the RBBI Rule compiler.
  17  */
  18 class RBBINode {
  19
  20
  21  //   enum NodeType {
  22      static final int    setRef = 0;
  23      static final int    uset = 1;
  24      static final int    varRef = 2;
  25      static final int    leafChar = 3;
  26      static final int    lookAhead = 4;
  27      static final int    tag = 5;
  28      static final int    endMark = 6;
  29      static final int    opStart = 7;
  30      static final int    opCat = 8;
  31      static final int    opOr = 9;
  32      static final int    opStar = 10;
  33      static final int    opPlus = 11;
  34      static final int    opQuestion = 12;
  35      static final int    opBreak = 13;
  36      static final int    opReverse = 14;
  37      static final int    opLParen = 15;
  38      static final int    nodeTypeLimit = 16;    //  For Assertion checking only.
  39
  40      static final String []  nodeTypeNames = {
  41          "setRef",
  42          "uset",
  43          "varRef",
  44          "leafChar",
  45          "lookAhead",
  46          "tag",
  47          "endMark",
  48          "opStart",
  49          "opCat",
  50          "opOr",
  51          "opStar",
  52          "opPlus",
  53          "opQuestion",
  54          "opBreak",
  55          "opReverse",
  56          "opLParen"
  57      };
  58
  59 //    enum OpPrecedence {
  60     static final int    precZero   = 0;
  61     static final int    precStart  = 1;
  62     static final int    precLParen = 2;
  63     static final int    precOpOr   = 3;
  64     static final int    precOpCat  = 4;
  65
  66     int          fType;   // enum NodeType
  67     RBBINode      fParent;
  68     RBBINode      fLeftChild;
  69     RBBINode      fRightChild;
  70     UnicodeSet    fInputSet;           // For uset nodes only.
  71     int          fPrecedence = precZero;   // enum OpPrecedence, For binary ops only.
  72
  73     String       fText;                 // Text corresponding to this node.
  74                                         //   May be lazily evaluated when (if) needed
  75                                         //   for some node types.
  76     int           fFirstPos;            // Position in the rule source string of the
  77                                         //   first text associated with the node.
  78                                         //   If there's a left child, this will be the same
  79                                         //   as that child's left pos.
  80     int           fLastPos;             //  Last position in the rule source string
  81                                         //    of any text associated with this node.
  82                                         //    If there's a right child, this will be the same
  83                                         //    as that child's last postion.
  84
  85     boolean      fNullable;            //  See Aho DFA table generation algorithm
  86     int           fVal;                 // For leafChar nodes, the value.
  87                                         //   Values are the character category,
  88                                         //   corresponds to columns in the final
  89                                         //   state transition table.
  90
  91     boolean      fLookAheadEnd;        // For endMark nodes, set TRUE if
  92                                         //   marking the end of a look-ahead rule.
  93
  94     Set<RBBINode> fFirstPosSet;         // See Aho DFA table generation algorithm
  95     Set<RBBINode> fLastPosSet;          // See Aho.
  96     Set<RBBINode> fFollowPos;           // See Aho.
  97
  98     int           fSerialNum;           //  Debugging aids.  Each node gets a unique serial number.
  99     static int    gLastSerial;
 100
 101     RBBINode(int t) {
 102         Assert.assrt(t < nodeTypeLimit);
 103         fSerialNum = ++gLastSerial;
 104         fType = t;
 105
 106         fFirstPosSet = new HashSet<RBBINode>();
 107         fLastPosSet = new HashSet<RBBINode>();
 108         fFollowPos = new HashSet<RBBINode>();
 109         if (t == opCat) {
 110             fPrecedence = precOpCat;
 111         } else if (t == opOr) {
 112             fPrecedence = precOpOr;
 113         } else if (t == opStart) {
 114             fPrecedence = precStart;
 115         } else if (t == opLParen) {
 116             fPrecedence = precLParen;
 117         } else {
 118             fPrecedence = precZero;
 119         }
 120     }
 121
 122     RBBINode(RBBINode other) {
 123         fSerialNum = ++gLastSerial;
 124         fType = other.fType;
 125         fInputSet = other.fInputSet;
 126         fPrecedence = other.fPrecedence;
 127         fText = other.fText;
 128         fFirstPos = other.fFirstPos;
 129         fLastPos = other.fLastPos;
 130         fNullable = other.fNullable;
 131         fVal = other.fVal;
 132         fFirstPosSet = new HashSet<RBBINode>(other.fFirstPosSet);
 133         fLastPosSet = new HashSet<RBBINode>(other.fLastPosSet);
 134         fFollowPos = new HashSet<RBBINode>(other.fFollowPos);
 135     }
 136
 137     //-------------------------------------------------------------------------
 138     //
 139     //        cloneTree Make a copy of the subtree rooted at this node.
 140     //                      Discard any variable references encountered along the way,
 141     //                      and replace with copies of the variable's definitions.
 142     //                      Used to replicate the expression underneath variable
 143     //                      references in preparation for generating the DFA tables.
 144     //
 145     //-------------------------------------------------------------------------
 146     RBBINode cloneTree() {
 147         RBBINode n;
 148
 149         if (fType == RBBINode.varRef) {
 150             // If the current node is a variable reference, skip over it
 151             //   and clone the definition of the variable instead.
 152             n = fLeftChild.cloneTree();
 153         } else if (fType == RBBINode.uset) {
 154             n = this;
 155         } else {
 156             n = new RBBINode(this);
 157             if (fLeftChild != null) {
 158                 n.fLeftChild = fLeftChild.cloneTree();
 159                 n.fLeftChild.fParent = n;
 160             }
 161             if (fRightChild != null) {
 162                 n.fRightChild = fRightChild.cloneTree();
 163                 n.fRightChild.fParent = n;
 164             }
 165         }
 166         return n;
 167     }
 168
 169
 170
 171     //-------------------------------------------------------------------------
 172     //
 173     //       flattenVariables Walk a parse tree, replacing any variable
 174     //                          references with a copy of the variable's definition.
 175     //                          Aside from variables, the tree is not changed.
 176     //
 177     //                          Return the root of the tree. If the root was not a variable
 178     //                          reference, it remains unchanged - the root we started with
 179     //                          is the root we return. If, however, the root was a variable
 180     //                          reference, the root of the newly cloned replacement tree will
 181     //                          be returned, and the original tree deleted.
 182     //
 183     //                          This function works by recursively walking the tree
 184     //                          without doing anything until a variable reference is
 185     //                          found, then calling cloneTree() at that point. Any
 186     //                          nested references are handled by cloneTree(), not here.
 187     //
 188     //-------------------------------------------------------------------------
 189     RBBINode flattenVariables() {
 190         if (fType == varRef) {
 191             RBBINode retNode = fLeftChild.cloneTree();
 192             // delete this;
 193             return retNode;
 194         }
 195
 196         if (fLeftChild != null) {
 197             fLeftChild = fLeftChild.flattenVariables();
 198             fLeftChild.fParent = this;
 199         }
 200         if (fRightChild != null) {
 201             fRightChild = fRightChild.flattenVariables();
 202             fRightChild.fParent = this;
 203         }
 204         return this;
 205     }
 206
 207     //-------------------------------------------------------------------------
 208     //
 209     //      flattenSets Walk the parse tree, replacing any nodes of type setRef
 210     //                     with a copy of the expression tree for the set. A set's
 211     //                     equivalent expression tree is precomputed and saved as
 212     //                     the left child of the uset node.
 213     //
 214     //-------------------------------------------------------------------------
 215     void flattenSets() {
 216         Assert.assrt(fType != setRef);
 217
 218         if (fLeftChild != null) {
 219             if (fLeftChild.fType == setRef) {
 220                 RBBINode setRefNode = fLeftChild;
 221                 RBBINode usetNode = setRefNode.fLeftChild;
 222                 RBBINode replTree = usetNode.fLeftChild;
 223                 fLeftChild = replTree.cloneTree();
 224                 fLeftChild.fParent = this;
 225             } else {
 226                 fLeftChild.flattenSets();
 227             }
 228         }
 229
 230         if (fRightChild != null) {
 231             if (fRightChild.fType == setRef) {
 232                 RBBINode setRefNode = fRightChild;
 233                 RBBINode usetNode = setRefNode.fLeftChild;
 234                 RBBINode replTree = usetNode.fLeftChild;
 235                 fRightChild = replTree.cloneTree();
 236                 fRightChild.fParent = this;
 237                 // delete setRefNode;
 238             } else {
 239                 fRightChild.flattenSets();
 240             }
 241         }
 242     }
 243
 244     //-------------------------------------------------------------------------
 245     //
 246     //       findNodes() Locate all the nodes of the specified type, starting
 247     //                       at the specified root.
 248     //
 249     //-------------------------------------------------------------------------
 250     void findNodes(List<RBBINode> dest, int kind) {
 251         if (fType == kind) {
 252             dest.add(this);
 253         }
 254         if (fLeftChild != null) {
 255             fLeftChild.findNodes(dest, kind);
 256         }
 257         if (fRightChild != null) {
 258             fRightChild.findNodes(dest, kind);
 259         }
 260     }
 261
 262
 263
 264     //-------------------------------------------------------------------------
 265     //
 266     //        print. Print out a single node, for debugging.
 267     //
 268     //-------------------------------------------------------------------------
 269     ///CLOVER:OFF
 270     static void printNode(RBBINode n) {
 271
 272         if (n==null) {
 273             System.out.print (" -- null --\n");
 274         } else {
 275             RBBINode.printInt( n.fSerialNum, 10);
 276             RBBINode.printString(nodeTypeNames[n.fType], 11);
 277             RBBINode.printInt(n.fParent==null? 0     : n.fParent.fSerialNum, 11);
 278             RBBINode.printInt(n.fLeftChild==null? 0  : n.fLeftChild.fSerialNum, 11);
 279             RBBINode.printInt(n.fRightChild==null? 0 : n.fRightChild.fSerialNum, 12);
 280             RBBINode.printInt(n.fFirstPos, 12);
 281             RBBINode.printInt(n.fVal, 7);
 282
 283             if (n.fType == varRef) {
 284                 System.out.print(" " + n.fText);
 285             }
 286         }
 287         System.out.println("");
 288     }
 289     ///CLOVER:ON
 290
 291
 292     // Print a String in a fixed field size.
 293     // Debugging function.
 294     ///CLOVER:OFF
 295     static void printString(String s, int minWidth) {
 296         for (int i = minWidth; i < 0; i++) {
 297             // negative width means pad leading spaces, not fixed width.
 298             System.out.print(' ');
 299         }
 300         for (int i = s.length(); i < minWidth; i++) {
 301             System.out.print(' ');
 302         }
 303         System.out.print(s);
 304     }
 305     ///CLOVER:ON
 306
 307     //
 308     //  Print an int in a fixed size field.
 309     //  Debugging function.
 310     //
 311     ///CLOVER:OFF
 312     static void printInt(int i, int minWidth) {
 313         String s = Integer.toString(i);
 314         printString(s, Math.max(minWidth, s.length() + 1));
 315     }
 316     ///CLOVER:ON
 317
 318     ///CLOVER:OFF
 319     static void printHex(int i, int minWidth) {
 320         String s = Integer.toString(i, 16);
 321         String leadingZeroes = "00000"
 322                 .substring(0, Math.max(0, 5 - s.length()));
 323         s = leadingZeroes + s;
 324         printString(s, minWidth);
 325     }
 326     ///CLOVER:ON
 327
 328
 329     // -------------------------------------------------------------------------
 330     //
 331     //        print. Print out the tree of nodes rooted at "this"
 332     //
 333     // -------------------------------------------------------------------------
 334     ///CLOVER:OFF
 335     void printTree(boolean printHeading) {
 336         if (printHeading) {
 337             System.out.println( "-------------------------------------------------------------------");
 338             System.out.println("    Serial       type     Parent  LeftChild  RightChild    position  value");
 339         }
 340         printNode(this);
 341             // Only dump the definition under a variable reference if asked to.
 342             // Unconditinally dump children of all other node types.
 343             if (fType != varRef) {
 344                 if (fLeftChild != null) {
 345                     fLeftChild.printTree(false);
 346                 }
 347
 348                 if (fRightChild != null) {
 349                     fRightChild.printTree(false);
 350                 }
 351             }
 352     }
 353     ///CLOVER:ON
 354
 355 }