1 // 2016 and later: Unicode, Inc. and others. 2 // License & terms of use: http://www.unicode.org/copyright.html 3 /* 4 *************************************************************************** 5 * Copyright (C) 2002-2016 International Business Machines Corporation * 6 * and others. All rights reserved. * 7 *************************************************************************** 8 */ 9 10 // 11 // File: rbbinode.cpp 12 // 13 // Implementation of class RBBINode, which represents a node in the 14 // tree generated when parsing the Rules Based Break Iterator rules. 15 // 16 // This "Class" is actually closer to a struct. 17 // Code using it is expected to directly access fields much of the time. 18 // 19 20 #include "unicode/utypes.h" 21 22 #if !UCONFIG_NO_BREAK_ITERATION 23 24 #include "unicode/unistr.h" 25 #include "unicode/uniset.h" 26 #include "unicode/uchar.h" 27 #include "unicode/parsepos.h" 28 29 #include "cstr.h" 30 #include "uvector.h" 31 32 #include "rbbirb.h" 33 #include "rbbinode.h" 34 35 #include "uassert.h" 36 37 38 U_NAMESPACE_BEGIN 39 40 #ifdef RBBI_DEBUG 41 static int gLastSerial = 0; 42 #endif 43 44 45 //------------------------------------------------------------------------- 46 // 47 // Constructor. Just set the fields to reasonable default values. 48 // 49 //------------------------------------------------------------------------- 50 RBBINode::RBBINode(NodeType t) : UMemory() { 51 #ifdef RBBI_DEBUG 52 fSerialNum = ++gLastSerial; 53 #endif 54 fType = t; 55 fParent = NULL; 56 fLeftChild = NULL; 57 fRightChild = NULL; 58 fInputSet = NULL; 59 fFirstPos = 0; 60 fLastPos = 0; 61 fNullable = FALSE; 62 fLookAheadEnd = FALSE; 63 fRuleRoot = FALSE; 64 fChainIn = FALSE; 65 fVal = 0; 66 fPrecedence = precZero; 67 68 UErrorCode status = U_ZERO_ERROR; 69 fFirstPosSet = new UVector(status); // TODO - get a real status from somewhere 70 fLastPosSet = new UVector(status); 71 fFollowPos = new UVector(status); 72 if (t==opCat) {fPrecedence = precOpCat;} 73 else if (t==opOr) {fPrecedence = precOpOr;} 74 else if (t==opStart) {fPrecedence = precStart;} 75 else if (t==opLParen) {fPrecedence = precLParen;} 76 77 } 78 79 80 RBBINode::RBBINode(const RBBINode &other) : UMemory(other) { 81 #ifdef RBBI_DEBUG 82 fSerialNum = ++gLastSerial; 83 #endif 84 fType = other.fType; 85 fParent = NULL; 86 fLeftChild = NULL; 87 fRightChild = NULL; 88 fInputSet = other.fInputSet; 89 fPrecedence = other.fPrecedence; 90 fText = other.fText; 91 fFirstPos = other.fFirstPos; 92 fLastPos = other.fLastPos; 93 fNullable = other.fNullable; 94 fVal = other.fVal; 95 fRuleRoot = FALSE; 96 fChainIn = other.fChainIn; 97 UErrorCode status = U_ZERO_ERROR; 98 fFirstPosSet = new UVector(status); // TODO - get a real status from somewhere 99 fLastPosSet = new UVector(status); 100 fFollowPos = new UVector(status); 101 } 102 103 104 //------------------------------------------------------------------------- 105 // 106 // Destructor. Deletes both this node AND any child nodes, 107 // except in the case of variable reference nodes. For 108 // these, the l. child points back to the definition, which 109 // is common for all references to the variable, meaning 110 // it can't be deleted here. 111 // 112 //------------------------------------------------------------------------- 113 RBBINode::~RBBINode() { 114 // printf("deleting node %8x serial %4d\n", this, this->fSerialNum); 115 delete fInputSet; 116 fInputSet = NULL; 117 118 switch (this->fType) { 119 case varRef: 120 case setRef: 121 // for these node types, multiple instances point to the same "children" 122 // Storage ownership of children handled elsewhere. Don't delete here. 123 break; 124 125 default: 126 delete fLeftChild; 127 fLeftChild = NULL; 128 delete fRightChild; 129 fRightChild = NULL; 130 } 131 132 133 delete fFirstPosSet; 134 delete fLastPosSet; 135 delete fFollowPos; 136 137 } 138 139 140 //------------------------------------------------------------------------- 141 // 142 // cloneTree Make a copy of the subtree rooted at this node. 143 // Discard any variable references encountered along the way, 144 // and replace with copies of the variable's definitions. 145 // Used to replicate the expression underneath variable 146 // references in preparation for generating the DFA tables. 147 // 148 //------------------------------------------------------------------------- 149 RBBINode *RBBINode::cloneTree() { 150 RBBINode *n; 151 152 if (fType == RBBINode::varRef) { 153 // If the current node is a variable reference, skip over it 154 // and clone the definition of the variable instead. 155 n = fLeftChild->cloneTree(); 156 } else if (fType == RBBINode::uset) { 157 n = this; 158 } else { 159 n = new RBBINode(*this); 160 // Check for null pointer. 161 if (n != NULL) { 162 if (fLeftChild != NULL) { 163 n->fLeftChild = fLeftChild->cloneTree(); 164 n->fLeftChild->fParent = n; 165 } 166 if (fRightChild != NULL) { 167 n->fRightChild = fRightChild->cloneTree(); 168 n->fRightChild->fParent = n; 169 } 170 } 171 } 172 return n; 173 } 174 175 176 177 //------------------------------------------------------------------------- 178 // 179 // flattenVariables Walk a parse tree, replacing any variable 180 // references with a copy of the variable's definition. 181 // Aside from variables, the tree is not changed. 182 // 183 // Return the root of the tree. If the root was not a variable 184 // reference, it remains unchanged - the root we started with 185 // is the root we return. If, however, the root was a variable 186 // reference, the root of the newly cloned replacement tree will 187 // be returned, and the original tree deleted. 188 // 189 // This function works by recursively walking the tree 190 // without doing anything until a variable reference is 191 // found, then calling cloneTree() at that point. Any 192 // nested references are handled by cloneTree(), not here. 193 // 194 //------------------------------------------------------------------------- 195 RBBINode *RBBINode::flattenVariables() { 196 if (fType == varRef) { 197 RBBINode *retNode = fLeftChild->cloneTree(); 198 if (retNode != NULL) { 199 retNode->fRuleRoot = this->fRuleRoot; 200 retNode->fChainIn = this->fChainIn; 201 } 202 delete this; // TODO: undefined behavior. Fix. 203 return retNode; 204 } 205 206 if (fLeftChild != NULL) { 207 fLeftChild = fLeftChild->flattenVariables(); 208 fLeftChild->fParent = this; 209 } 210 if (fRightChild != NULL) { 211 fRightChild = fRightChild->flattenVariables(); 212 fRightChild->fParent = this; 213 } 214 return this; 215 } 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 RBBINode::flattenSets() { 227 U_ASSERT(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 delete setRefNode; 237 } else { 238 fLeftChild->flattenSets(); 239 } 240 } 241 242 if (fRightChild != NULL) { 243 if (fRightChild->fType==setRef) { 244 RBBINode *setRefNode = fRightChild; 245 RBBINode *usetNode = setRefNode->fLeftChild; 246 RBBINode *replTree = usetNode->fLeftChild; 247 fRightChild = replTree->cloneTree(); 248 fRightChild->fParent = this; 249 delete setRefNode; 250 } else { 251 fRightChild->flattenSets(); 252 } 253 } 254 } 255 256 257 258 //------------------------------------------------------------------------- 259 // 260 // findNodes() Locate all the nodes of the specified type, starting 261 // at the specified root. 262 // 263 //------------------------------------------------------------------------- 264 void RBBINode::findNodes(UVector *dest, RBBINode::NodeType kind, UErrorCode &status) { 265 /* test for buffer overflows */ 266 if (U_FAILURE(status)) { 267 return; 268 } 269 if (fType == kind) { 270 dest->addElement(this, status); 271 } 272 if (fLeftChild != NULL) { 273 fLeftChild->findNodes(dest, kind, status); 274 } 275 if (fRightChild != NULL) { 276 fRightChild->findNodes(dest, kind, status); 277 } 278 } 279 280 281 //------------------------------------------------------------------------- 282 // 283 // print. Print out a single node, for debugging. 284 // 285 //------------------------------------------------------------------------- 286 #ifdef RBBI_DEBUG 287 288 static int32_t serial(const RBBINode *node) { 289 return (node == NULL? -1 : node->fSerialNum); 290 } 291 292 293 void RBBINode::printNode(const RBBINode *node) { 294 static const char * const nodeTypeNames[] = { 295 "setRef", 296 "uset", 297 "varRef", 298 "leafChar", 299 "lookAhead", 300 "tag", 301 "endMark", 302 "opStart", 303 "opCat", 304 "opOr", 305 "opStar", 306 "opPlus", 307 "opQuestion", 308 "opBreak", 309 "opReverse", 310 "opLParen" 311 }; 312 313 if (node==NULL) { 314 RBBIDebugPrintf("%10p", (void *)node); 315 } else { 316 RBBIDebugPrintf("%10p %5d %12s %c%c %5d %5d %5d %6d %d ", 317 (void *)node, node->fSerialNum, nodeTypeNames[node->fType], 318 node->fRuleRoot?'R':' ', node->fChainIn?'C':' ', 319 serial(node->fLeftChild), serial(node->fRightChild), serial(node->fParent), 320 node->fFirstPos, node->fVal); 321 if (node->fType == varRef) { 322 RBBI_DEBUG_printUnicodeString(node->fText); 323 } 324 } 325 RBBIDebugPrintf("\n"); 326 } 327 #endif 328 329 330 #ifdef RBBI_DEBUG 331 U_CFUNC void RBBI_DEBUG_printUnicodeString(const UnicodeString &s, int minWidth) { 332 RBBIDebugPrintf("%*s", minWidth, CStr(s)()); 333 } 334 #endif 335 336 337 //------------------------------------------------------------------------- 338 // 339 // print. Print out the tree of nodes rooted at "this" 340 // 341 //------------------------------------------------------------------------- 342 #ifdef RBBI_DEBUG 343 void RBBINode::printNodeHeader() { 344 RBBIDebugPrintf(" Address serial type LeftChild RightChild Parent position value\n"); 345 } 346 347 void RBBINode::printTree(const RBBINode *node, UBool printHeading) { 348 if (printHeading) { 349 printNodeHeader(); 350 } 351 printNode(node); 352 if (node != NULL) { 353 // Only dump the definition under a variable reference if asked to. 354 // Unconditinally dump children of all other node types. 355 if (node->fType != varRef) { 356 if (node->fLeftChild != NULL) { 357 printTree(node->fLeftChild, FALSE); 358 } 359 360 if (node->fRightChild != NULL) { 361 printTree(node->fRightChild, FALSE); 362 } 363 } 364 } 365 } 366 #endif 367 368 369 370 U_NAMESPACE_END 371 372 #endif /* #if !UCONFIG_NO_BREAK_ITERATION */ 373
