| /* | |
| *************************************************************************** | |
| * Copyright (C) 2002-2008 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 | |
| #include "unicode/unistr.h" | |
| #include "unicode/uniset.h" | |
| #include "unicode/uchar.h" | |
| #include "unicode/parsepos.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; | |
| 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; | |
| 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(); | |
| delete this; | |
| 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 | |
| void RBBINode::printNode() { | |
| static const char * const nodeTypeNames[] = { | |
| "setRef", | |
| "uset", | |
| "varRef", | |
| "leafChar", | |
| "lookAhead", | |
| "tag", | |
| "endMark", | |
| "opStart", | |
| "opCat", | |
| "opOr", | |
| "opStar", | |
| "opPlus", | |
| "opQuestion", | |
| "opBreak", | |
| "opReverse", | |
| "opLParen" | |
| }; | |
| if (this==NULL) { | |
| RBBIDebugPrintf("%10p", (void *)this); | |
| } else { | |
| RBBIDebugPrintf("%10p %12s %10p %10p %10p %4d %6d %d ", | |
| (void *)this, nodeTypeNames[fType], (void *)fParent, (void *)fLeftChild, (void *)fRightChild, | |
| fSerialNum, fFirstPos, fVal); | |
| if (fType == varRef) { | |
| RBBI_DEBUG_printUnicodeString(fText); | |
| } | |
| } | |
| RBBIDebugPrintf("\n"); | |
| } | |
| #endif | |
| #ifdef RBBI_DEBUG | |
| U_CFUNC void RBBI_DEBUG_printUnicodeString(const UnicodeString &s, int minWidth) | |
| { | |
| int i; | |
| for (i=0; i<s.length(); i++) { | |
| RBBIDebugPrintf("%c", s.charAt(i)); | |
| // putc(s.charAt(i), stdout); | |
| } | |
| for (i=s.length(); i<minWidth; i++) { | |
| RBBIDebugPrintf(" "); | |
| } | |
| } | |
| #endif | |
| //------------------------------------------------------------------------- | |
| // | |
| // print. Print out the tree of nodes rooted at "this" | |
| // | |
| //------------------------------------------------------------------------- | |
| #ifdef RBBI_DEBUG | |
| void RBBINode::printTree(UBool printHeading) { | |
| if (printHeading) { | |
| RBBIDebugPrintf( "-------------------------------------------------------------------\n" | |
| " Address type Parent LeftChild RightChild serial position value\n" | |
| ); | |
| } | |
| this->printNode(); | |
| if (this != NULL) { | |
| // Only dump the definition under a variable reference if asked to. | |
| // Unconditinally dump children of all other node types. | |
| if (fType != varRef) { | |
| if (fLeftChild != NULL) { | |
| fLeftChild->printTree(FALSE); | |
| } | |
| if (fRightChild != NULL) { | |
| fRightChild->printTree(FALSE); | |
| } | |
| } | |
| } | |
| } | |
| #endif | |
| U_NAMESPACE_END | |
| #endif /* #if !UCONFIG_NO_BREAK_ITERATION */ |