| /* | |
| ********************************************************************** | |
| * Copyright (c) 2002-2009, International Business Machines | |
| * Corporation and others. All Rights Reserved. | |
| ********************************************************************** | |
| */ | |
| // | |
| // rbbitblb.cpp | |
| // | |
| #include "unicode/utypes.h" | |
| #if !UCONFIG_NO_BREAK_ITERATION | |
| #include "starboard/client_porting/poem/assert_poem.h" | |
| #include "starboard/client_porting/poem/string_poem.h" | |
| #include "unicode/unistr.h" | |
| #include "rbbitblb.h" | |
| #include "rbbirb.h" | |
| #include "rbbisetb.h" | |
| #include "rbbidata.h" | |
| #include "cstring.h" | |
| #include "uassert.h" | |
| #include "cmemory.h" | |
| U_NAMESPACE_BEGIN | |
| RBBITableBuilder::RBBITableBuilder(RBBIRuleBuilder *rb, RBBINode **rootNode) : | |
| fTree(*rootNode) { | |
| fRB = rb; | |
| fStatus = fRB->fStatus; | |
| UErrorCode status = U_ZERO_ERROR; | |
| fDStates = new UVector(status); | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| if (U_FAILURE(status)) { | |
| *fStatus = status; | |
| return; | |
| } | |
| if (fDStates == NULL) { | |
| *fStatus = U_MEMORY_ALLOCATION_ERROR;; | |
| } | |
| } | |
| RBBITableBuilder::~RBBITableBuilder() { | |
| int i; | |
| for (i=0; i<fDStates->size(); i++) { | |
| delete (RBBIStateDescriptor *)fDStates->elementAt(i); | |
| } | |
| delete fDStates; | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // RBBITableBuilder::build - This is the main function for building the DFA state transtion | |
| // table from the RBBI rules parse tree. | |
| // | |
| //----------------------------------------------------------------------------- | |
| void RBBITableBuilder::build() { | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| // If there were no rules, just return. This situation can easily arise | |
| // for the reverse rules. | |
| if (fTree==NULL) { | |
| return; | |
| } | |
| // | |
| // Walk through the tree, replacing any references to $variables with a copy of the | |
| // parse tree for the substition expression. | |
| // | |
| fTree = fTree->flattenVariables(); | |
| #ifdef RBBI_DEBUG | |
| if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "ftree")) { | |
| RBBIDebugPuts("Parse tree after flattening variable references."); | |
| fTree->printTree(TRUE); | |
| } | |
| #endif | |
| // | |
| // If the rules contained any references to {bof} | |
| // add a {bof} <cat> <former root of tree> to the | |
| // tree. Means that all matches must start out with the | |
| // {bof} fake character. | |
| // | |
| if (fRB->fSetBuilder->sawBOF()) { | |
| RBBINode *bofTop = new RBBINode(RBBINode::opCat); | |
| RBBINode *bofLeaf = new RBBINode(RBBINode::leafChar); | |
| // Delete and exit if memory allocation failed. | |
| if (bofTop == NULL || bofLeaf == NULL) { | |
| *fStatus = U_MEMORY_ALLOCATION_ERROR; | |
| delete bofTop; | |
| delete bofLeaf; | |
| return; | |
| } | |
| bofTop->fLeftChild = bofLeaf; | |
| bofTop->fRightChild = fTree; | |
| bofLeaf->fParent = bofTop; | |
| bofLeaf->fVal = 2; // Reserved value for {bof}. | |
| fTree = bofTop; | |
| } | |
| // | |
| // Add a unique right-end marker to the expression. | |
| // Appears as a cat-node, left child being the original tree, | |
| // right child being the end marker. | |
| // | |
| RBBINode *cn = new RBBINode(RBBINode::opCat); | |
| // Exit if memory allocation failed. | |
| if (cn == NULL) { | |
| *fStatus = U_MEMORY_ALLOCATION_ERROR; | |
| return; | |
| } | |
| cn->fLeftChild = fTree; | |
| fTree->fParent = cn; | |
| cn->fRightChild = new RBBINode(RBBINode::endMark); | |
| // Delete and exit if memory allocation failed. | |
| if (cn->fRightChild == NULL) { | |
| *fStatus = U_MEMORY_ALLOCATION_ERROR; | |
| delete cn; | |
| return; | |
| } | |
| cn->fRightChild->fParent = cn; | |
| fTree = cn; | |
| // | |
| // Replace all references to UnicodeSets with the tree for the equivalent | |
| // expression. | |
| // | |
| fTree->flattenSets(); | |
| #ifdef RBBI_DEBUG | |
| if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "stree")) { | |
| RBBIDebugPuts("Parse tree after flattening Unicode Set references."); | |
| fTree->printTree(TRUE); | |
| } | |
| #endif | |
| // | |
| // calculate the functions nullable, firstpos, lastpos and followpos on | |
| // nodes in the parse tree. | |
| // See the alogrithm description in Aho. | |
| // Understanding how this works by looking at the code alone will be | |
| // nearly impossible. | |
| // | |
| calcNullable(fTree); | |
| calcFirstPos(fTree); | |
| calcLastPos(fTree); | |
| calcFollowPos(fTree); | |
| if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "pos")) { | |
| RBBIDebugPuts("\n"); | |
| printPosSets(fTree); | |
| } | |
| // | |
| // For "chained" rules, modify the followPos sets | |
| // | |
| if (fRB->fChainRules) { | |
| calcChainedFollowPos(fTree); | |
| } | |
| // | |
| // BOF (start of input) test fixup. | |
| // | |
| if (fRB->fSetBuilder->sawBOF()) { | |
| bofFixup(); | |
| } | |
| // | |
| // Build the DFA state transition tables. | |
| // | |
| buildStateTable(); | |
| flagAcceptingStates(); | |
| flagLookAheadStates(); | |
| flagTaggedStates(); | |
| // | |
| // Update the global table of rule status {tag} values | |
| // The rule builder has a global vector of status values that are common | |
| // for all tables. Merge the ones from this table into the global set. | |
| // | |
| mergeRuleStatusVals(); | |
| if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "states")) {printStates();}; | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // calcNullable. Impossible to explain succinctly. See Aho, section 3.9 | |
| // | |
| //----------------------------------------------------------------------------- | |
| void RBBITableBuilder::calcNullable(RBBINode *n) { | |
| if (n == NULL) { | |
| return; | |
| } | |
| if (n->fType == RBBINode::setRef || | |
| n->fType == RBBINode::endMark ) { | |
| // These are non-empty leaf node types. | |
| n->fNullable = FALSE; | |
| return; | |
| } | |
| if (n->fType == RBBINode::lookAhead || n->fType == RBBINode::tag) { | |
| // Lookahead marker node. It's a leaf, so no recursion on children. | |
| // It's nullable because it does not match any literal text from the input stream. | |
| n->fNullable = TRUE; | |
| return; | |
| } | |
| // The node is not a leaf. | |
| // Calculate nullable on its children. | |
| calcNullable(n->fLeftChild); | |
| calcNullable(n->fRightChild); | |
| // Apply functions from table 3.40 in Aho | |
| if (n->fType == RBBINode::opOr) { | |
| n->fNullable = n->fLeftChild->fNullable || n->fRightChild->fNullable; | |
| } | |
| else if (n->fType == RBBINode::opCat) { | |
| n->fNullable = n->fLeftChild->fNullable && n->fRightChild->fNullable; | |
| } | |
| else if (n->fType == RBBINode::opStar || n->fType == RBBINode::opQuestion) { | |
| n->fNullable = TRUE; | |
| } | |
| else { | |
| n->fNullable = FALSE; | |
| } | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // calcFirstPos. Impossible to explain succinctly. See Aho, section 3.9 | |
| // | |
| //----------------------------------------------------------------------------- | |
| void RBBITableBuilder::calcFirstPos(RBBINode *n) { | |
| if (n == NULL) { | |
| return; | |
| } | |
| if (n->fType == RBBINode::leafChar || | |
| n->fType == RBBINode::endMark || | |
| n->fType == RBBINode::lookAhead || | |
| n->fType == RBBINode::tag) { | |
| // These are non-empty leaf node types. | |
| // Note: In order to maintain the sort invariant on the set, | |
| // this function should only be called on a node whose set is | |
| // empty to start with. | |
| n->fFirstPosSet->addElement(n, *fStatus); | |
| return; | |
| } | |
| // The node is not a leaf. | |
| // Calculate firstPos on its children. | |
| calcFirstPos(n->fLeftChild); | |
| calcFirstPos(n->fRightChild); | |
| // Apply functions from table 3.40 in Aho | |
| if (n->fType == RBBINode::opOr) { | |
| setAdd(n->fFirstPosSet, n->fLeftChild->fFirstPosSet); | |
| setAdd(n->fFirstPosSet, n->fRightChild->fFirstPosSet); | |
| } | |
| else if (n->fType == RBBINode::opCat) { | |
| setAdd(n->fFirstPosSet, n->fLeftChild->fFirstPosSet); | |
| if (n->fLeftChild->fNullable) { | |
| setAdd(n->fFirstPosSet, n->fRightChild->fFirstPosSet); | |
| } | |
| } | |
| else if (n->fType == RBBINode::opStar || | |
| n->fType == RBBINode::opQuestion || | |
| n->fType == RBBINode::opPlus) { | |
| setAdd(n->fFirstPosSet, n->fLeftChild->fFirstPosSet); | |
| } | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // calcLastPos. Impossible to explain succinctly. See Aho, section 3.9 | |
| // | |
| //----------------------------------------------------------------------------- | |
| void RBBITableBuilder::calcLastPos(RBBINode *n) { | |
| if (n == NULL) { | |
| return; | |
| } | |
| if (n->fType == RBBINode::leafChar || | |
| n->fType == RBBINode::endMark || | |
| n->fType == RBBINode::lookAhead || | |
| n->fType == RBBINode::tag) { | |
| // These are non-empty leaf node types. | |
| // Note: In order to maintain the sort invariant on the set, | |
| // this function should only be called on a node whose set is | |
| // empty to start with. | |
| n->fLastPosSet->addElement(n, *fStatus); | |
| return; | |
| } | |
| // The node is not a leaf. | |
| // Calculate lastPos on its children. | |
| calcLastPos(n->fLeftChild); | |
| calcLastPos(n->fRightChild); | |
| // Apply functions from table 3.40 in Aho | |
| if (n->fType == RBBINode::opOr) { | |
| setAdd(n->fLastPosSet, n->fLeftChild->fLastPosSet); | |
| setAdd(n->fLastPosSet, n->fRightChild->fLastPosSet); | |
| } | |
| else if (n->fType == RBBINode::opCat) { | |
| setAdd(n->fLastPosSet, n->fRightChild->fLastPosSet); | |
| if (n->fRightChild->fNullable) { | |
| setAdd(n->fLastPosSet, n->fLeftChild->fLastPosSet); | |
| } | |
| } | |
| else if (n->fType == RBBINode::opStar || | |
| n->fType == RBBINode::opQuestion || | |
| n->fType == RBBINode::opPlus) { | |
| setAdd(n->fLastPosSet, n->fLeftChild->fLastPosSet); | |
| } | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // calcFollowPos. Impossible to explain succinctly. See Aho, section 3.9 | |
| // | |
| //----------------------------------------------------------------------------- | |
| void RBBITableBuilder::calcFollowPos(RBBINode *n) { | |
| if (n == NULL || | |
| n->fType == RBBINode::leafChar || | |
| n->fType == RBBINode::endMark) { | |
| return; | |
| } | |
| calcFollowPos(n->fLeftChild); | |
| calcFollowPos(n->fRightChild); | |
| // Aho rule #1 | |
| if (n->fType == RBBINode::opCat) { | |
| RBBINode *i; // is 'i' in Aho's description | |
| uint32_t ix; | |
| UVector *LastPosOfLeftChild = n->fLeftChild->fLastPosSet; | |
| for (ix=0; ix<(uint32_t)LastPosOfLeftChild->size(); ix++) { | |
| i = (RBBINode *)LastPosOfLeftChild->elementAt(ix); | |
| setAdd(i->fFollowPos, n->fRightChild->fFirstPosSet); | |
| } | |
| } | |
| // Aho rule #2 | |
| if (n->fType == RBBINode::opStar || | |
| n->fType == RBBINode::opPlus) { | |
| RBBINode *i; // again, n and i are the names from Aho's description. | |
| uint32_t ix; | |
| for (ix=0; ix<(uint32_t)n->fLastPosSet->size(); ix++) { | |
| i = (RBBINode *)n->fLastPosSet->elementAt(ix); | |
| setAdd(i->fFollowPos, n->fFirstPosSet); | |
| } | |
| } | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // calcChainedFollowPos. Modify the previously calculated followPos sets | |
| // to implement rule chaining. NOT described by Aho | |
| // | |
| //----------------------------------------------------------------------------- | |
| void RBBITableBuilder::calcChainedFollowPos(RBBINode *tree) { | |
| UVector endMarkerNodes(*fStatus); | |
| UVector leafNodes(*fStatus); | |
| int32_t i; | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| // get a list of all endmarker nodes. | |
| tree->findNodes(&endMarkerNodes, RBBINode::endMark, *fStatus); | |
| // get a list all leaf nodes | |
| tree->findNodes(&leafNodes, RBBINode::leafChar, *fStatus); | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| // Get all nodes that can be the start a match, which is FirstPosition() | |
| // of the portion of the tree corresponding to user-written rules. | |
| // See the tree description in bofFixup(). | |
| RBBINode *userRuleRoot = tree; | |
| if (fRB->fSetBuilder->sawBOF()) { | |
| userRuleRoot = tree->fLeftChild->fRightChild; | |
| } | |
| U_ASSERT(userRuleRoot != NULL); | |
| UVector *matchStartNodes = userRuleRoot->fFirstPosSet; | |
| // Iteratate over all leaf nodes, | |
| // | |
| int32_t endNodeIx; | |
| int32_t startNodeIx; | |
| for (endNodeIx=0; endNodeIx<leafNodes.size(); endNodeIx++) { | |
| RBBINode *tNode = (RBBINode *)leafNodes.elementAt(endNodeIx); | |
| RBBINode *endNode = NULL; | |
| // Identify leaf nodes that correspond to overall rule match positions. | |
| // These include an endMarkerNode in their followPos sets. | |
| for (i=0; i<endMarkerNodes.size(); i++) { | |
| if (tNode->fFollowPos->contains(endMarkerNodes.elementAt(i))) { | |
| endNode = tNode; | |
| break; | |
| } | |
| } | |
| if (endNode == NULL) { | |
| // node wasn't an end node. Try again with the next. | |
| continue; | |
| } | |
| // We've got a node that can end a match. | |
| // Line Break Specific hack: If this node's val correspond to the $CM char class, | |
| // don't chain from it. | |
| // TODO: Add rule syntax for this behavior, get specifics out of here and | |
| // into the rule file. | |
| if (fRB->fLBCMNoChain) { | |
| UChar32 c = this->fRB->fSetBuilder->getFirstChar(endNode->fVal); | |
| if (c != -1) { | |
| // c == -1 occurs with sets containing only the {eof} marker string. | |
| ULineBreak cLBProp = (ULineBreak)u_getIntPropertyValue(c, UCHAR_LINE_BREAK); | |
| if (cLBProp == U_LB_COMBINING_MARK) { | |
| continue; | |
| } | |
| } | |
| } | |
| // Now iterate over the nodes that can start a match, looking for ones | |
| // with the same char class as our ending node. | |
| RBBINode *startNode; | |
| for (startNodeIx = 0; startNodeIx<matchStartNodes->size(); startNodeIx++) { | |
| startNode = (RBBINode *)matchStartNodes->elementAt(startNodeIx); | |
| if (startNode->fType != RBBINode::leafChar) { | |
| continue; | |
| } | |
| if (endNode->fVal == startNode->fVal) { | |
| // The end val (character class) of one possible match is the | |
| // same as the start of another. | |
| // Add all nodes from the followPos of the start node to the | |
| // followPos set of the end node, which will have the effect of | |
| // letting matches transition from a match state at endNode | |
| // to the second char of a match starting with startNode. | |
| setAdd(endNode->fFollowPos, startNode->fFollowPos); | |
| } | |
| } | |
| } | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // bofFixup. Fixup for state tables that include {bof} beginning of input testing. | |
| // Do an swizzle similar to chaining, modifying the followPos set of | |
| // the bofNode to include the followPos nodes from other {bot} nodes | |
| // scattered through the tree. | |
| // | |
| // This function has much in common with calcChainedFollowPos(). | |
| // | |
| //----------------------------------------------------------------------------- | |
| void RBBITableBuilder::bofFixup() { | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| // The parse tree looks like this ... | |
| // fTree root ---> <cat> | |
| // / \ . | |
| // <cat> <#end node> | |
| // / \ . | |
| // <bofNode> rest | |
| // of tree | |
| // | |
| // We will be adding things to the followPos set of the <bofNode> | |
| // | |
| RBBINode *bofNode = fTree->fLeftChild->fLeftChild; | |
| U_ASSERT(bofNode->fType == RBBINode::leafChar); | |
| U_ASSERT(bofNode->fVal == 2); | |
| // Get all nodes that can be the start a match of the user-written rules | |
| // (excluding the fake bofNode) | |
| // We want the nodes that can start a match in the | |
| // part labeled "rest of tree" | |
| // | |
| UVector *matchStartNodes = fTree->fLeftChild->fRightChild->fFirstPosSet; | |
| RBBINode *startNode; | |
| int startNodeIx; | |
| for (startNodeIx = 0; startNodeIx<matchStartNodes->size(); startNodeIx++) { | |
| startNode = (RBBINode *)matchStartNodes->elementAt(startNodeIx); | |
| if (startNode->fType != RBBINode::leafChar) { | |
| continue; | |
| } | |
| if (startNode->fVal == bofNode->fVal) { | |
| // We found a leaf node corresponding to a {bof} that was | |
| // explicitly written into a rule. | |
| // Add everything from the followPos set of this node to the | |
| // followPos set of the fake bofNode at the start of the tree. | |
| // | |
| setAdd(bofNode->fFollowPos, startNode->fFollowPos); | |
| } | |
| } | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // buildStateTable() Determine the set of runtime DFA states and the | |
| // transition tables for these states, by the algorithm | |
| // of fig. 3.44 in Aho. | |
| // | |
| // Most of the comments are quotes of Aho's psuedo-code. | |
| // | |
| //----------------------------------------------------------------------------- | |
| void RBBITableBuilder::buildStateTable() { | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| RBBIStateDescriptor *failState; | |
| // Set it to NULL to avoid uninitialized warning | |
| RBBIStateDescriptor *initialState = NULL; | |
| // | |
| // Add a dummy state 0 - the stop state. Not from Aho. | |
| int lastInputSymbol = fRB->fSetBuilder->getNumCharCategories() - 1; | |
| failState = new RBBIStateDescriptor(lastInputSymbol, fStatus); | |
| if (failState == NULL) { | |
| *fStatus = U_MEMORY_ALLOCATION_ERROR; | |
| goto ExitBuildSTdeleteall; | |
| } | |
| failState->fPositions = new UVector(*fStatus); | |
| if (failState->fPositions == NULL) { | |
| *fStatus = U_MEMORY_ALLOCATION_ERROR; | |
| } | |
| if (failState->fPositions == NULL || U_FAILURE(*fStatus)) { | |
| goto ExitBuildSTdeleteall; | |
| } | |
| fDStates->addElement(failState, *fStatus); | |
| if (U_FAILURE(*fStatus)) { | |
| goto ExitBuildSTdeleteall; | |
| } | |
| // initially, the only unmarked state in Dstates is firstpos(root), | |
| // where toot is the root of the syntax tree for (r)#; | |
| initialState = new RBBIStateDescriptor(lastInputSymbol, fStatus); | |
| if (initialState == NULL) { | |
| *fStatus = U_MEMORY_ALLOCATION_ERROR; | |
| } | |
| if (U_FAILURE(*fStatus)) { | |
| goto ExitBuildSTdeleteall; | |
| } | |
| initialState->fPositions = new UVector(*fStatus); | |
| if (initialState->fPositions == NULL) { | |
| *fStatus = U_MEMORY_ALLOCATION_ERROR; | |
| } | |
| if (U_FAILURE(*fStatus)) { | |
| goto ExitBuildSTdeleteall; | |
| } | |
| setAdd(initialState->fPositions, fTree->fFirstPosSet); | |
| fDStates->addElement(initialState, *fStatus); | |
| if (U_FAILURE(*fStatus)) { | |
| goto ExitBuildSTdeleteall; | |
| } | |
| // while there is an unmarked state T in Dstates do begin | |
| for (;;) { | |
| RBBIStateDescriptor *T = NULL; | |
| int32_t tx; | |
| for (tx=1; tx<fDStates->size(); tx++) { | |
| RBBIStateDescriptor *temp; | |
| temp = (RBBIStateDescriptor *)fDStates->elementAt(tx); | |
| if (temp->fMarked == FALSE) { | |
| T = temp; | |
| break; | |
| } | |
| } | |
| if (T == NULL) { | |
| break; | |
| } | |
| // mark T; | |
| T->fMarked = TRUE; | |
| // for each input symbol a do begin | |
| int32_t a; | |
| for (a = 1; a<=lastInputSymbol; a++) { | |
| // let U be the set of positions that are in followpos(p) | |
| // for some position p in T | |
| // such that the symbol at position p is a; | |
| UVector *U = NULL; | |
| RBBINode *p; | |
| int32_t px; | |
| for (px=0; px<T->fPositions->size(); px++) { | |
| p = (RBBINode *)T->fPositions->elementAt(px); | |
| if ((p->fType == RBBINode::leafChar) && (p->fVal == a)) { | |
| if (U == NULL) { | |
| U = new UVector(*fStatus); | |
| if (U == NULL) { | |
| *fStatus = U_MEMORY_ALLOCATION_ERROR; | |
| goto ExitBuildSTdeleteall; | |
| } | |
| } | |
| setAdd(U, p->fFollowPos); | |
| } | |
| } | |
| // if U is not empty and not in DStates then | |
| int32_t ux = 0; | |
| UBool UinDstates = FALSE; | |
| if (U != NULL) { | |
| U_ASSERT(U->size() > 0); | |
| int ix; | |
| for (ix=0; ix<fDStates->size(); ix++) { | |
| RBBIStateDescriptor *temp2; | |
| temp2 = (RBBIStateDescriptor *)fDStates->elementAt(ix); | |
| if (setEquals(U, temp2->fPositions)) { | |
| delete U; | |
| U = temp2->fPositions; | |
| ux = ix; | |
| UinDstates = TRUE; | |
| break; | |
| } | |
| } | |
| // Add U as an unmarked state to Dstates | |
| if (!UinDstates) | |
| { | |
| RBBIStateDescriptor *newState = new RBBIStateDescriptor(lastInputSymbol, fStatus); | |
| if (newState == NULL) { | |
| *fStatus = U_MEMORY_ALLOCATION_ERROR; | |
| } | |
| if (U_FAILURE(*fStatus)) { | |
| goto ExitBuildSTdeleteall; | |
| } | |
| newState->fPositions = U; | |
| fDStates->addElement(newState, *fStatus); | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| ux = fDStates->size()-1; | |
| } | |
| // Dtran[T, a] := U; | |
| T->fDtran->setElementAt(ux, a); | |
| } | |
| } | |
| } | |
| return; | |
| // delete local pointers only if error occured. | |
| ExitBuildSTdeleteall: | |
| delete initialState; | |
| delete failState; | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // flagAcceptingStates Identify accepting states. | |
| // First get a list of all of the end marker nodes. | |
| // Then, for each state s, | |
| // if s contains one of the end marker nodes in its list of tree positions then | |
| // s is an accepting state. | |
| // | |
| //----------------------------------------------------------------------------- | |
| void RBBITableBuilder::flagAcceptingStates() { | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| UVector endMarkerNodes(*fStatus); | |
| RBBINode *endMarker; | |
| int32_t i; | |
| int32_t n; | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| fTree->findNodes(&endMarkerNodes, RBBINode::endMark, *fStatus); | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| for (i=0; i<endMarkerNodes.size(); i++) { | |
| endMarker = (RBBINode *)endMarkerNodes.elementAt(i); | |
| for (n=0; n<fDStates->size(); n++) { | |
| RBBIStateDescriptor *sd = (RBBIStateDescriptor *)fDStates->elementAt(n); | |
| if (sd->fPositions->indexOf(endMarker) >= 0) { | |
| // Any non-zero value for fAccepting means this is an accepting node. | |
| // The value is what will be returned to the user as the break status. | |
| // If no other value was specified, force it to -1. | |
| if (sd->fAccepting==0) { | |
| // State hasn't been marked as accepting yet. Do it now. | |
| sd->fAccepting = endMarker->fVal; | |
| if (sd->fAccepting == 0) { | |
| sd->fAccepting = -1; | |
| } | |
| } | |
| if (sd->fAccepting==-1 && endMarker->fVal != 0) { | |
| // Both lookahead and non-lookahead accepting for this state. | |
| // Favor the look-ahead. Expedient for line break. | |
| // TODO: need a more elegant resolution for conflicting rules. | |
| sd->fAccepting = endMarker->fVal; | |
| } | |
| // implicit else: | |
| // if sd->fAccepting already had a value other than 0 or -1, leave it be. | |
| // If the end marker node is from a look-ahead rule, set | |
| // the fLookAhead field or this state also. | |
| if (endMarker->fLookAheadEnd) { | |
| // TODO: don't change value if already set? | |
| // TODO: allow for more than one active look-ahead rule in engine. | |
| // Make value here an index to a side array in engine? | |
| sd->fLookAhead = sd->fAccepting; | |
| } | |
| } | |
| } | |
| } | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // flagLookAheadStates Very similar to flagAcceptingStates, above. | |
| // | |
| //----------------------------------------------------------------------------- | |
| void RBBITableBuilder::flagLookAheadStates() { | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| UVector lookAheadNodes(*fStatus); | |
| RBBINode *lookAheadNode; | |
| int32_t i; | |
| int32_t n; | |
| fTree->findNodes(&lookAheadNodes, RBBINode::lookAhead, *fStatus); | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| for (i=0; i<lookAheadNodes.size(); i++) { | |
| lookAheadNode = (RBBINode *)lookAheadNodes.elementAt(i); | |
| for (n=0; n<fDStates->size(); n++) { | |
| RBBIStateDescriptor *sd = (RBBIStateDescriptor *)fDStates->elementAt(n); | |
| if (sd->fPositions->indexOf(lookAheadNode) >= 0) { | |
| sd->fLookAhead = lookAheadNode->fVal; | |
| } | |
| } | |
| } | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // flagTaggedStates | |
| // | |
| //----------------------------------------------------------------------------- | |
| void RBBITableBuilder::flagTaggedStates() { | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| UVector tagNodes(*fStatus); | |
| RBBINode *tagNode; | |
| int32_t i; | |
| int32_t n; | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| fTree->findNodes(&tagNodes, RBBINode::tag, *fStatus); | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| for (i=0; i<tagNodes.size(); i++) { // For each tag node t (all of 'em) | |
| tagNode = (RBBINode *)tagNodes.elementAt(i); | |
| for (n=0; n<fDStates->size(); n++) { // For each state s (row in the state table) | |
| RBBIStateDescriptor *sd = (RBBIStateDescriptor *)fDStates->elementAt(n); | |
| if (sd->fPositions->indexOf(tagNode) >= 0) { // if s include the tag node t | |
| sortedAdd(&sd->fTagVals, tagNode->fVal); | |
| } | |
| } | |
| } | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // mergeRuleStatusVals | |
| // | |
| // Update the global table of rule status {tag} values | |
| // The rule builder has a global vector of status values that are common | |
| // for all tables. Merge the ones from this table into the global set. | |
| // | |
| //----------------------------------------------------------------------------- | |
| void RBBITableBuilder::mergeRuleStatusVals() { | |
| // | |
| // The basic outline of what happens here is this... | |
| // | |
| // for each state in this state table | |
| // if the status tag list for this state is in the global statuses list | |
| // record where and | |
| // continue with the next state | |
| // else | |
| // add the tag list for this state to the global list. | |
| // | |
| int i; | |
| int n; | |
| // Pre-set a single tag of {0} into the table. | |
| // We will need this as a default, for rule sets with no explicit tagging. | |
| if (fRB->fRuleStatusVals->size() == 0) { | |
| fRB->fRuleStatusVals->addElement(1, *fStatus); // Num of statuses in group | |
| fRB->fRuleStatusVals->addElement((int32_t)0, *fStatus); // and our single status of zero | |
| } | |
| // For each state | |
| for (n=0; n<fDStates->size(); n++) { | |
| RBBIStateDescriptor *sd = (RBBIStateDescriptor *)fDStates->elementAt(n); | |
| UVector *thisStatesTagValues = sd->fTagVals; | |
| if (thisStatesTagValues == NULL) { | |
| // No tag values are explicitly associated with this state. | |
| // Set the default tag value. | |
| sd->fTagsIdx = 0; | |
| continue; | |
| } | |
| // There are tag(s) associated with this state. | |
| // fTagsIdx will be the index into the global tag list for this state's tag values. | |
| // Initial value of -1 flags that we haven't got it set yet. | |
| sd->fTagsIdx = -1; | |
| int32_t thisTagGroupStart = 0; // indexes into the global rule status vals list | |
| int32_t nextTagGroupStart = 0; | |
| // Loop runs once per group of tags in the global list | |
| while (nextTagGroupStart < fRB->fRuleStatusVals->size()) { | |
| thisTagGroupStart = nextTagGroupStart; | |
| nextTagGroupStart += fRB->fRuleStatusVals->elementAti(thisTagGroupStart) + 1; | |
| if (thisStatesTagValues->size() != fRB->fRuleStatusVals->elementAti(thisTagGroupStart)) { | |
| // The number of tags for this state is different from | |
| // the number of tags in this group from the global list. | |
| // Continue with the next group from the global list. | |
| continue; | |
| } | |
| // The lengths match, go ahead and compare the actual tag values | |
| // between this state and the group from the global list. | |
| for (i=0; i<thisStatesTagValues->size(); i++) { | |
| if (thisStatesTagValues->elementAti(i) != | |
| fRB->fRuleStatusVals->elementAti(thisTagGroupStart + 1 + i) ) { | |
| // Mismatch. | |
| break; | |
| } | |
| } | |
| if (i == thisStatesTagValues->size()) { | |
| // We found a set of tag values in the global list that match | |
| // those for this state. Use them. | |
| sd->fTagsIdx = thisTagGroupStart; | |
| break; | |
| } | |
| } | |
| if (sd->fTagsIdx == -1) { | |
| // No suitable entry in the global tag list already. Add one | |
| sd->fTagsIdx = fRB->fRuleStatusVals->size(); | |
| fRB->fRuleStatusVals->addElement(thisStatesTagValues->size(), *fStatus); | |
| for (i=0; i<thisStatesTagValues->size(); i++) { | |
| fRB->fRuleStatusVals->addElement(thisStatesTagValues->elementAti(i), *fStatus); | |
| } | |
| } | |
| } | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // sortedAdd Add a value to a vector of sorted values (ints). | |
| // Do not replicate entries; if the value is already there, do not | |
| // add a second one. | |
| // Lazily create the vector if it does not already exist. | |
| // | |
| //----------------------------------------------------------------------------- | |
| void RBBITableBuilder::sortedAdd(UVector **vector, int32_t val) { | |
| int32_t i; | |
| if (*vector == NULL) { | |
| *vector = new UVector(*fStatus); | |
| } | |
| if (*vector == NULL || U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| UVector *vec = *vector; | |
| int32_t vSize = vec->size(); | |
| for (i=0; i<vSize; i++) { | |
| int32_t valAtI = vec->elementAti(i); | |
| if (valAtI == val) { | |
| // The value is already in the vector. Don't add it again. | |
| return; | |
| } | |
| if (valAtI > val) { | |
| break; | |
| } | |
| } | |
| vec->insertElementAt(val, i, *fStatus); | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // setAdd Set operation on UVector | |
| // dest = dest union source | |
| // Elements may only appear once and must be sorted. | |
| // | |
| //----------------------------------------------------------------------------- | |
| void RBBITableBuilder::setAdd(UVector *dest, UVector *source) { | |
| int32_t destOriginalSize = dest->size(); | |
| int32_t sourceSize = source->size(); | |
| int32_t di = 0; | |
| MaybeStackArray<void *, 16> destArray, sourceArray; // Handle small cases without malloc | |
| void **destPtr, **sourcePtr; | |
| void **destLim, **sourceLim; | |
| if (destOriginalSize > destArray.getCapacity()) { | |
| if (destArray.resize(destOriginalSize) == NULL) { | |
| return; | |
| } | |
| } | |
| destPtr = destArray.getAlias(); | |
| destLim = destPtr + destOriginalSize; // destArray.getArrayLimit()? | |
| if (sourceSize > sourceArray.getCapacity()) { | |
| if (sourceArray.resize(sourceSize) == NULL) { | |
| return; | |
| } | |
| } | |
| sourcePtr = sourceArray.getAlias(); | |
| sourceLim = sourcePtr + sourceSize; // sourceArray.getArrayLimit()? | |
| // Avoid multiple "get element" calls by getting the contents into arrays | |
| (void) dest->toArray(destPtr); | |
| (void) source->toArray(sourcePtr); | |
| dest->setSize(sourceSize+destOriginalSize, *fStatus); | |
| while (sourcePtr < sourceLim && destPtr < destLim) { | |
| if (*destPtr == *sourcePtr) { | |
| dest->setElementAt(*sourcePtr++, di++); | |
| destPtr++; | |
| } | |
| // This check is required for machines with segmented memory, like i5/OS. | |
| // Direct pointer comparison is not recommended. | |
| else if (uprv_memcmp(destPtr, sourcePtr, sizeof(void *)) < 0) { | |
| dest->setElementAt(*destPtr++, di++); | |
| } | |
| else { /* *sourcePtr < *destPtr */ | |
| dest->setElementAt(*sourcePtr++, di++); | |
| } | |
| } | |
| // At most one of these two cleanup loops will execute | |
| while (destPtr < destLim) { | |
| dest->setElementAt(*destPtr++, di++); | |
| } | |
| while (sourcePtr < sourceLim) { | |
| dest->setElementAt(*sourcePtr++, di++); | |
| } | |
| dest->setSize(di, *fStatus); | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // setEqual Set operation on UVector. | |
| // Compare for equality. | |
| // Elements must be sorted. | |
| // | |
| //----------------------------------------------------------------------------- | |
| UBool RBBITableBuilder::setEquals(UVector *a, UVector *b) { | |
| return a->equals(*b); | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // printPosSets Debug function. Dump Nullable, firstpos, lastpos and followpos | |
| // for each node in the tree. | |
| // | |
| //----------------------------------------------------------------------------- | |
| #ifdef RBBI_DEBUG | |
| void RBBITableBuilder::printPosSets(RBBINode *n) { | |
| if (n==NULL) { | |
| return; | |
| } | |
| n->printNode(); | |
| RBBIDebugPrintf(" Nullable: %s\n", n->fNullable?"TRUE":"FALSE"); | |
| RBBIDebugPrintf(" firstpos: "); | |
| printSet(n->fFirstPosSet); | |
| RBBIDebugPrintf(" lastpos: "); | |
| printSet(n->fLastPosSet); | |
| RBBIDebugPrintf(" followpos: "); | |
| printSet(n->fFollowPos); | |
| printPosSets(n->fLeftChild); | |
| printPosSets(n->fRightChild); | |
| } | |
| #endif | |
| //----------------------------------------------------------------------------- | |
| // | |
| // getTableSize() Calculate the size of the runtime form of this | |
| // state transition table. | |
| // | |
| //----------------------------------------------------------------------------- | |
| int32_t RBBITableBuilder::getTableSize() const { | |
| int32_t size = 0; | |
| int32_t numRows; | |
| int32_t numCols; | |
| int32_t rowSize; | |
| if (fTree == NULL) { | |
| return 0; | |
| } | |
| size = sizeof(RBBIStateTable) - 4; // The header, with no rows to the table. | |
| numRows = fDStates->size(); | |
| numCols = fRB->fSetBuilder->getNumCharCategories(); | |
| // Note The declaration of RBBIStateTableRow is for a table of two columns. | |
| // Therefore we subtract two from numCols when determining | |
| // how much storage to add to a row for the total columns. | |
| rowSize = sizeof(RBBIStateTableRow) + sizeof(uint16_t)*(numCols-2); | |
| size += numRows * rowSize; | |
| return size; | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // exportTable() export the state transition table in the format required | |
| // by the runtime engine. getTableSize() bytes of memory | |
| // must be available at the output address "where". | |
| // | |
| //----------------------------------------------------------------------------- | |
| void RBBITableBuilder::exportTable(void *where) { | |
| RBBIStateTable *table = (RBBIStateTable *)where; | |
| uint32_t state; | |
| int col; | |
| if (U_FAILURE(*fStatus) || fTree == NULL) { | |
| return; | |
| } | |
| if (fRB->fSetBuilder->getNumCharCategories() > 0x7fff || | |
| fDStates->size() > 0x7fff) { | |
| *fStatus = U_BRK_INTERNAL_ERROR; | |
| return; | |
| } | |
| table->fRowLen = sizeof(RBBIStateTableRow) + | |
| sizeof(uint16_t) * (fRB->fSetBuilder->getNumCharCategories() - 2); | |
| table->fNumStates = fDStates->size(); | |
| table->fFlags = 0; | |
| if (fRB->fLookAheadHardBreak) { | |
| table->fFlags |= RBBI_LOOKAHEAD_HARD_BREAK; | |
| } | |
| if (fRB->fSetBuilder->sawBOF()) { | |
| table->fFlags |= RBBI_BOF_REQUIRED; | |
| } | |
| table->fReserved = 0; | |
| for (state=0; state<table->fNumStates; state++) { | |
| RBBIStateDescriptor *sd = (RBBIStateDescriptor *)fDStates->elementAt(state); | |
| RBBIStateTableRow *row = (RBBIStateTableRow *)(table->fTableData + state*table->fRowLen); | |
| U_ASSERT (-32768 < sd->fAccepting && sd->fAccepting <= 32767); | |
| U_ASSERT (-32768 < sd->fLookAhead && sd->fLookAhead <= 32767); | |
| row->fAccepting = (int16_t)sd->fAccepting; | |
| row->fLookAhead = (int16_t)sd->fLookAhead; | |
| row->fTagIdx = (int16_t)sd->fTagsIdx; | |
| for (col=0; col<fRB->fSetBuilder->getNumCharCategories(); col++) { | |
| row->fNextState[col] = (uint16_t)sd->fDtran->elementAti(col); | |
| } | |
| } | |
| } | |
| //----------------------------------------------------------------------------- | |
| // | |
| // printSet Debug function. Print the contents of a UVector | |
| // | |
| //----------------------------------------------------------------------------- | |
| #ifdef RBBI_DEBUG | |
| void RBBITableBuilder::printSet(UVector *s) { | |
| int32_t i; | |
| for (i=0; i<s->size(); i++) { | |
| void *v = s->elementAt(i); | |
| RBBIDebugPrintf("%10p", v); | |
| } | |
| RBBIDebugPrintf("\n"); | |
| } | |
| #endif | |
| //----------------------------------------------------------------------------- | |
| // | |
| // printStates Debug Function. Dump the fully constructed state transition table. | |
| // | |
| //----------------------------------------------------------------------------- | |
| #ifdef RBBI_DEBUG | |
| void RBBITableBuilder::printStates() { | |
| int c; // input "character" | |
| int n; // state number | |
| RBBIDebugPrintf("state | i n p u t s y m b o l s \n"); | |
| RBBIDebugPrintf(" | Acc LA Tag"); | |
| for (c=0; c<fRB->fSetBuilder->getNumCharCategories(); c++) { | |
| RBBIDebugPrintf(" %2d", c); | |
| } | |
| RBBIDebugPrintf("\n"); | |
| RBBIDebugPrintf(" |---------------"); | |
| for (c=0; c<fRB->fSetBuilder->getNumCharCategories(); c++) { | |
| RBBIDebugPrintf("---"); | |
| } | |
| RBBIDebugPrintf("\n"); | |
| for (n=0; n<fDStates->size(); n++) { | |
| RBBIStateDescriptor *sd = (RBBIStateDescriptor *)fDStates->elementAt(n); | |
| RBBIDebugPrintf(" %3d | " , n); | |
| RBBIDebugPrintf("%3d %3d %5d ", sd->fAccepting, sd->fLookAhead, sd->fTagsIdx); | |
| for (c=0; c<fRB->fSetBuilder->getNumCharCategories(); c++) { | |
| RBBIDebugPrintf(" %2d", sd->fDtran->elementAti(c)); | |
| } | |
| RBBIDebugPrintf("\n"); | |
| } | |
| RBBIDebugPrintf("\n\n"); | |
| } | |
| #endif | |
| //----------------------------------------------------------------------------- | |
| // | |
| // printRuleStatusTable Debug Function. Dump the common rule status table | |
| // | |
| //----------------------------------------------------------------------------- | |
| #ifdef RBBI_DEBUG | |
| void RBBITableBuilder::printRuleStatusTable() { | |
| int32_t thisRecord = 0; | |
| int32_t nextRecord = 0; | |
| int i; | |
| UVector *tbl = fRB->fRuleStatusVals; | |
| RBBIDebugPrintf("index | tags \n"); | |
| RBBIDebugPrintf("-------------------\n"); | |
| while (nextRecord < tbl->size()) { | |
| thisRecord = nextRecord; | |
| nextRecord = thisRecord + tbl->elementAti(thisRecord) + 1; | |
| RBBIDebugPrintf("%4d ", thisRecord); | |
| for (i=thisRecord+1; i<nextRecord; i++) { | |
| RBBIDebugPrintf(" %5d", tbl->elementAti(i)); | |
| } | |
| RBBIDebugPrintf("\n"); | |
| } | |
| RBBIDebugPrintf("\n\n"); | |
| } | |
| #endif | |
| //----------------------------------------------------------------------------- | |
| // | |
| // RBBIStateDescriptor Methods. This is a very struct-like class | |
| // Most access is directly to the fields. | |
| // | |
| //----------------------------------------------------------------------------- | |
| RBBIStateDescriptor::RBBIStateDescriptor(int lastInputSymbol, UErrorCode *fStatus) { | |
| fMarked = FALSE; | |
| fAccepting = 0; | |
| fLookAhead = 0; | |
| fTagsIdx = 0; | |
| fTagVals = NULL; | |
| fPositions = NULL; | |
| fDtran = NULL; | |
| fDtran = new UVector(lastInputSymbol+1, *fStatus); | |
| if (U_FAILURE(*fStatus)) { | |
| return; | |
| } | |
| if (fDtran == NULL) { | |
| *fStatus = U_MEMORY_ALLOCATION_ERROR; | |
| return; | |
| } | |
| fDtran->setSize(lastInputSymbol+1, *fStatus); // fDtran needs to be pre-sized. | |
| // It is indexed by input symbols, and will | |
| // hold the next state number for each | |
| // symbol. | |
| } | |
| RBBIStateDescriptor::~RBBIStateDescriptor() { | |
| delete fPositions; | |
| delete fDtran; | |
| delete fTagVals; | |
| fPositions = NULL; | |
| fDtran = NULL; | |
| fTagVals = NULL; | |
| } | |
| U_NAMESPACE_END | |
| #endif /* #if !UCONFIG_NO_BREAK_ITERATION */ |