| // © 2016 and later: Unicode, Inc. and others. |
| // License & terms of use: http://www.unicode.org/copyright.html |
| /* |
| *************************************************************************** |
| * Copyright (C) 2002-2016 International Business Machines Corporation * |
| * and others. All rights reserved. * |
| *************************************************************************** |
| */ |
| |
| // |
| // File: rbbinode.cpp |
| // |
| // Implementation of class RBBINode, which represents a node in the |
| // tree generated when parsing the Rules Based Break Iterator rules. |
| // |
| // This "Class" is actually closer to a struct. |
| // Code using it is expected to directly access fields much of the time. |
| // |
| |
| #include "unicode/utypes.h" |
| |
| #if !UCONFIG_NO_BREAK_ITERATION |
| |
| #if defined(STARBOARD) |
| #include "starboard/client_porting/poem/assert_poem.h" |
| #include "starboard/client_porting/poem/string_poem.h" |
| #endif // defined(STARBOARD) |
| #include "unicode/unistr.h" |
| #include "unicode/uniset.h" |
| #include "unicode/uchar.h" |
| #include "unicode/parsepos.h" |
| |
| #include "cstr.h" |
| #include "uvector.h" |
| |
| #include "rbbirb.h" |
| #include "rbbinode.h" |
| |
| #include "uassert.h" |
| |
| |
| U_NAMESPACE_BEGIN |
| |
| #ifdef RBBI_DEBUG |
| static int gLastSerial = 0; |
| #endif |
| |
| |
| //------------------------------------------------------------------------- |
| // |
| // Constructor. Just set the fields to reasonable default values. |
| // |
| //------------------------------------------------------------------------- |
| RBBINode::RBBINode(NodeType t) : UMemory() { |
| #ifdef RBBI_DEBUG |
| fSerialNum = ++gLastSerial; |
| #endif |
| fType = t; |
| fParent = NULL; |
| fLeftChild = NULL; |
| fRightChild = NULL; |
| fInputSet = NULL; |
| fFirstPos = 0; |
| fLastPos = 0; |
| fNullable = FALSE; |
| fLookAheadEnd = FALSE; |
| fRuleRoot = FALSE; |
| fChainIn = FALSE; |
| fVal = 0; |
| fPrecedence = precZero; |
| |
| UErrorCode status = U_ZERO_ERROR; |
| fFirstPosSet = new UVector(status); // TODO - get a real status from somewhere |
| fLastPosSet = new UVector(status); |
| fFollowPos = new UVector(status); |
| if (t==opCat) {fPrecedence = precOpCat;} |
| else if (t==opOr) {fPrecedence = precOpOr;} |
| else if (t==opStart) {fPrecedence = precStart;} |
| else if (t==opLParen) {fPrecedence = precLParen;} |
| |
| } |
| |
| |
| RBBINode::RBBINode(const RBBINode &other) : UMemory(other) { |
| #ifdef RBBI_DEBUG |
| fSerialNum = ++gLastSerial; |
| #endif |
| fType = other.fType; |
| fParent = NULL; |
| fLeftChild = NULL; |
| fRightChild = NULL; |
| fInputSet = other.fInputSet; |
| fPrecedence = other.fPrecedence; |
| fText = other.fText; |
| fFirstPos = other.fFirstPos; |
| fLastPos = other.fLastPos; |
| fNullable = other.fNullable; |
| fVal = other.fVal; |
| fRuleRoot = FALSE; |
| fChainIn = other.fChainIn; |
| UErrorCode status = U_ZERO_ERROR; |
| fFirstPosSet = new UVector(status); // TODO - get a real status from somewhere |
| fLastPosSet = new UVector(status); |
| fFollowPos = new UVector(status); |
| } |
| |
| |
| //------------------------------------------------------------------------- |
| // |
| // Destructor. Deletes both this node AND any child nodes, |
| // except in the case of variable reference nodes. For |
| // these, the l. child points back to the definition, which |
| // is common for all references to the variable, meaning |
| // it can't be deleted here. |
| // |
| //------------------------------------------------------------------------- |
| RBBINode::~RBBINode() { |
| // printf("deleting node %8x serial %4d\n", this, this->fSerialNum); |
| delete fInputSet; |
| fInputSet = NULL; |
| |
| switch (this->fType) { |
| case varRef: |
| case setRef: |
| // for these node types, multiple instances point to the same "children" |
| // Storage ownership of children handled elsewhere. Don't delete here. |
| break; |
| |
| default: |
| delete fLeftChild; |
| fLeftChild = NULL; |
| delete fRightChild; |
| fRightChild = NULL; |
| } |
| |
| |
| delete fFirstPosSet; |
| delete fLastPosSet; |
| delete fFollowPos; |
| |
| } |
| |
| |
| //------------------------------------------------------------------------- |
| // |
| // cloneTree Make a copy of the subtree rooted at this node. |
| // Discard any variable references encountered along the way, |
| // and replace with copies of the variable's definitions. |
| // Used to replicate the expression underneath variable |
| // references in preparation for generating the DFA tables. |
| // |
| //------------------------------------------------------------------------- |
| RBBINode *RBBINode::cloneTree() { |
| RBBINode *n; |
| |
| if (fType == RBBINode::varRef) { |
| // If the current node is a variable reference, skip over it |
| // and clone the definition of the variable instead. |
| n = fLeftChild->cloneTree(); |
| } else if (fType == RBBINode::uset) { |
| n = this; |
| } else { |
| n = new RBBINode(*this); |
| // Check for null pointer. |
| if (n != NULL) { |
| if (fLeftChild != NULL) { |
| n->fLeftChild = fLeftChild->cloneTree(); |
| n->fLeftChild->fParent = n; |
| } |
| if (fRightChild != NULL) { |
| n->fRightChild = fRightChild->cloneTree(); |
| n->fRightChild->fParent = n; |
| } |
| } |
| } |
| return n; |
| } |
| |
| |
| |
| //------------------------------------------------------------------------- |
| // |
| // flattenVariables Walk a parse tree, replacing any variable |
| // references with a copy of the variable's definition. |
| // Aside from variables, the tree is not changed. |
| // |
| // Return the root of the tree. If the root was not a variable |
| // reference, it remains unchanged - the root we started with |
| // is the root we return. If, however, the root was a variable |
| // reference, the root of the newly cloned replacement tree will |
| // be returned, and the original tree deleted. |
| // |
| // This function works by recursively walking the tree |
| // without doing anything until a variable reference is |
| // found, then calling cloneTree() at that point. Any |
| // nested references are handled by cloneTree(), not here. |
| // |
| //------------------------------------------------------------------------- |
| RBBINode *RBBINode::flattenVariables() { |
| if (fType == varRef) { |
| RBBINode *retNode = fLeftChild->cloneTree(); |
| if (retNode != NULL) { |
| retNode->fRuleRoot = this->fRuleRoot; |
| retNode->fChainIn = this->fChainIn; |
| } |
| delete this; // TODO: undefined behavior. Fix. |
| return retNode; |
| } |
| |
| if (fLeftChild != NULL) { |
| fLeftChild = fLeftChild->flattenVariables(); |
| fLeftChild->fParent = this; |
| } |
| if (fRightChild != NULL) { |
| fRightChild = fRightChild->flattenVariables(); |
| fRightChild->fParent = this; |
| } |
| return this; |
| } |
| |
| |
| //------------------------------------------------------------------------- |
| // |
| // flattenSets Walk the parse tree, replacing any nodes of type setRef |
| // with a copy of the expression tree for the set. A set's |
| // equivalent expression tree is precomputed and saved as |
| // the left child of the uset node. |
| // |
| //------------------------------------------------------------------------- |
| void RBBINode::flattenSets() { |
| U_ASSERT(fType != setRef); |
| |
| if (fLeftChild != NULL) { |
| if (fLeftChild->fType==setRef) { |
| RBBINode *setRefNode = fLeftChild; |
| RBBINode *usetNode = setRefNode->fLeftChild; |
| RBBINode *replTree = usetNode->fLeftChild; |
| fLeftChild = replTree->cloneTree(); |
| fLeftChild->fParent = this; |
| delete setRefNode; |
| } else { |
| fLeftChild->flattenSets(); |
| } |
| } |
| |
| if (fRightChild != NULL) { |
| if (fRightChild->fType==setRef) { |
| RBBINode *setRefNode = fRightChild; |
| RBBINode *usetNode = setRefNode->fLeftChild; |
| RBBINode *replTree = usetNode->fLeftChild; |
| fRightChild = replTree->cloneTree(); |
| fRightChild->fParent = this; |
| delete setRefNode; |
| } else { |
| fRightChild->flattenSets(); |
| } |
| } |
| } |
| |
| |
| |
| //------------------------------------------------------------------------- |
| // |
| // findNodes() Locate all the nodes of the specified type, starting |
| // at the specified root. |
| // |
| //------------------------------------------------------------------------- |
| void RBBINode::findNodes(UVector *dest, RBBINode::NodeType kind, UErrorCode &status) { |
| /* test for buffer overflows */ |
| if (U_FAILURE(status)) { |
| return; |
| } |
| if (fType == kind) { |
| dest->addElement(this, status); |
| } |
| if (fLeftChild != NULL) { |
| fLeftChild->findNodes(dest, kind, status); |
| } |
| if (fRightChild != NULL) { |
| fRightChild->findNodes(dest, kind, status); |
| } |
| } |
| |
| |
| //------------------------------------------------------------------------- |
| // |
| // print. Print out a single node, for debugging. |
| // |
| //------------------------------------------------------------------------- |
| #ifdef RBBI_DEBUG |
| |
| static int32_t serial(const RBBINode *node) { |
| return (node == NULL? -1 : node->fSerialNum); |
| } |
| |
| |
| void RBBINode::printNode(const RBBINode *node) { |
| static const char * const nodeTypeNames[] = { |
| "setRef", |
| "uset", |
| "varRef", |
| "leafChar", |
| "lookAhead", |
| "tag", |
| "endMark", |
| "opStart", |
| "opCat", |
| "opOr", |
| "opStar", |
| "opPlus", |
| "opQuestion", |
| "opBreak", |
| "opReverse", |
| "opLParen" |
| }; |
| |
| if (node==NULL) { |
| RBBIDebugPrintf("%10p", (void *)node); |
| } else { |
| RBBIDebugPrintf("%10p %5d %12s %c%c %5d %5d %5d %6d %d ", |
| (void *)node, node->fSerialNum, nodeTypeNames[node->fType], |
| node->fRuleRoot?'R':' ', node->fChainIn?'C':' ', |
| serial(node->fLeftChild), serial(node->fRightChild), serial(node->fParent), |
| node->fFirstPos, node->fVal); |
| if (node->fType == varRef) { |
| RBBI_DEBUG_printUnicodeString(node->fText); |
| } |
| } |
| RBBIDebugPrintf("\n"); |
| } |
| #endif |
| |
| |
| #ifdef RBBI_DEBUG |
| U_CFUNC void RBBI_DEBUG_printUnicodeString(const UnicodeString &s, int minWidth) { |
| RBBIDebugPrintf("%*s", minWidth, CStr(s)()); |
| } |
| #endif |
| |
| |
| //------------------------------------------------------------------------- |
| // |
| // print. Print out the tree of nodes rooted at "this" |
| // |
| //------------------------------------------------------------------------- |
| #ifdef RBBI_DEBUG |
| void RBBINode::printNodeHeader() { |
| RBBIDebugPrintf(" Address serial type LeftChild RightChild Parent position value\n"); |
| } |
| |
| void RBBINode::printTree(const RBBINode *node, UBool printHeading) { |
| if (printHeading) { |
| printNodeHeader(); |
| } |
| printNode(node); |
| if (node != NULL) { |
| // Only dump the definition under a variable reference if asked to. |
| // Unconditinally dump children of all other node types. |
| if (node->fType != varRef) { |
| if (node->fLeftChild != NULL) { |
| printTree(node->fLeftChild, FALSE); |
| } |
| |
| if (node->fRightChild != NULL) { |
| printTree(node->fRightChild, FALSE); |
| } |
| } |
| } |
| } |
| #endif |
| |
| |
| |
| U_NAMESPACE_END |
| |
| #endif /* #if !UCONFIG_NO_BREAK_ITERATION */ |
