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 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 position. 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 RBBINode(int t)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 // flattenVariables Walk a parse tree, replacing any variable 183 // references with a copy of the variable's definition. 184 // Aside from variables, the tree is not changed. 185 // 186 // Return the root of the tree. If the root was not a variable 187 // reference, it remains unchanged - the root we started with 188 // is the root we return. If, however, the root was a variable 189 // reference, the root of the newly cloned replacement tree will 190 // be returned, and the original tree deleted. 191 // 192 // This function works by recursively walking the tree 193 // without doing anything until a variable reference is 194 // found, then calling cloneTree() at that point. Any 195 // nested references are handled by cloneTree(), not here. 196 // 197 //------------------------------------------------------------------------- 198 static final private int kRecursiveDepthLimit = 3500; 199 RBBINode flattenVariables(int depth) { 200 if (depth > kRecursiveDepthLimit) { 201 throw new IllegalArgumentException("The input is too long"); 202 } 203 if (fType == varRef) { 204 RBBINode retNode = fLeftChild.cloneTree(); 205 retNode.fRuleRoot = this.fRuleRoot; 206 retNode.fChainIn = this.fChainIn; 207 return retNode; 208 } 209 210 if (fLeftChild != null) { 211 fLeftChild = fLeftChild.flattenVariables(depth+1); 212 fLeftChild.fParent = this; 213 } 214 if (fRightChild != null) { 215 fRightChild = fRightChild.flattenVariables(depth+1); 216 fRightChild.fParent = this; 217 } 218 return this; 219 } 220 221 //------------------------------------------------------------------------- 222 // 223 // flattenSets Walk the parse tree, replacing any nodes of type setRef 224 // with a copy of the expression tree for the set. A set's 225 // equivalent expression tree is precomputed and saved as 226 // the left child of the uset node. 227 // 228 //------------------------------------------------------------------------- flattenSets()229 void flattenSets() { 230 Assert.assrt(fType != setRef); 231 232 if (fLeftChild != null) { 233 if (fLeftChild.fType == setRef) { 234 RBBINode setRefNode = fLeftChild; 235 RBBINode usetNode = setRefNode.fLeftChild; 236 RBBINode replTree = usetNode.fLeftChild; 237 fLeftChild = replTree.cloneTree(); 238 fLeftChild.fParent = this; 239 } else { 240 fLeftChild.flattenSets(); 241 } 242 } 243 244 if (fRightChild != null) { 245 if (fRightChild.fType == setRef) { 246 RBBINode setRefNode = fRightChild; 247 RBBINode usetNode = setRefNode.fLeftChild; 248 RBBINode replTree = usetNode.fLeftChild; 249 fRightChild = replTree.cloneTree(); 250 fRightChild.fParent = this; 251 // delete setRefNode; 252 } else { 253 fRightChild.flattenSets(); 254 } 255 } 256 } 257 258 //------------------------------------------------------------------------- 259 // 260 // findNodes() Locate all the nodes of the specified type, starting 261 // at the specified root. 262 // 263 //------------------------------------------------------------------------- findNodes(List<RBBINode> dest, int kind)264 void findNodes(List<RBBINode> dest, int kind) { 265 if (fType == kind) { 266 dest.add(this); 267 } 268 if (fLeftChild != null) { 269 fLeftChild.findNodes(dest, kind); 270 } 271 if (fRightChild != null) { 272 fRightChild.findNodes(dest, kind); 273 } 274 } 275 276 277 278 //------------------------------------------------------------------------- 279 // 280 // print. Print out a single node, for debugging. 281 // 282 //------------------------------------------------------------------------- 283 ///CLOVER:OFF printNode(RBBINode n)284 static void printNode(RBBINode n) { 285 286 if (n==null) { 287 System.out.print (" -- null --\n"); 288 } else { 289 RBBINode.printInt( n.fSerialNum, 10); 290 RBBINode.printString(nodeTypeNames[n.fType], 11); 291 RBBINode.printInt(n.fParent==null? 0 : n.fParent.fSerialNum, 11); 292 RBBINode.printInt(n.fLeftChild==null? 0 : n.fLeftChild.fSerialNum, 11); 293 RBBINode.printInt(n.fRightChild==null? 0 : n.fRightChild.fSerialNum, 12); 294 RBBINode.printInt(n.fFirstPos, 12); 295 RBBINode.printInt(n.fVal, 7); 296 297 if (n.fType == varRef) { 298 System.out.print(" " + n.fText); 299 } 300 } 301 System.out.println(""); 302 } 303 ///CLOVER:ON 304 305 306 // Print a String in a fixed field size. 307 // Debugging function. 308 ///CLOVER:OFF printString(String s, int minWidth)309 static void printString(String s, int minWidth) { 310 for (int i = minWidth; i < 0; i++) { 311 // negative width means pad leading spaces, not fixed width. 312 System.out.print(' '); 313 } 314 for (int i = s.length(); i < minWidth; i++) { 315 System.out.print(' '); 316 } 317 System.out.print(s); 318 } 319 ///CLOVER:ON 320 321 // 322 // Print an int in a fixed size field. 323 // Debugging function. 324 // 325 ///CLOVER:OFF printInt(int i, int minWidth)326 static void printInt(int i, int minWidth) { 327 String s = Integer.toString(i); 328 printString(s, Math.max(minWidth, s.length() + 1)); 329 } 330 ///CLOVER:ON 331 332 ///CLOVER:OFF printHex(int i, int minWidth)333 static void printHex(int i, int minWidth) { 334 String s = Integer.toString(i, 16); 335 String leadingZeroes = "00000" 336 .substring(0, Math.max(0, 5 - s.length())); 337 s = leadingZeroes + s; 338 printString(s, minWidth); 339 } 340 ///CLOVER:ON 341 342 343 // ------------------------------------------------------------------------- 344 // 345 // print. Print out the tree of nodes rooted at "this" 346 // 347 // ------------------------------------------------------------------------- 348 ///CLOVER:OFF printTree(boolean printHeading)349 void printTree(boolean printHeading) { 350 if (printHeading) { 351 System.out.println( "-------------------------------------------------------------------"); 352 System.out.println(" Serial type Parent LeftChild RightChild position value"); 353 } 354 printNode(this); 355 // Only dump the definition under a variable reference if asked to. 356 // Unconditionally dump children of all other node types. 357 if (fType != varRef) { 358 if (fLeftChild != null) { 359 fLeftChild.printTree(false); 360 } 361 362 if (fRightChild != null) { 363 fRightChild.printTree(false); 364 } 365 } 366 } 367 ///CLOVER:ON 368 369 } 370