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