| // © 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. |
| ********************************************************************** |
| */ |
| // |
| // rbbitblb.cpp |
| // |
| |
| |
| #include "unicode/utypes.h" |
| |
| #if !UCONFIG_NO_BREAK_ITERATION |
| |
| #include "unicode/unistr.h" |
| #include "rbbitblb.h" |
| #include "rbbirb.h" |
| #include "rbbiscan.h" |
| #include "rbbisetb.h" |
| #include "rbbidata.h" |
| #include "cstring.h" |
| #include "uassert.h" |
| #include "uvectr32.h" |
| #include "cmemory.h" |
| |
| U_NAMESPACE_BEGIN |
| |
| const int32_t kMaxStateFor8BitsTable = 255; |
| |
| RBBITableBuilder::RBBITableBuilder(RBBIRuleBuilder *rb, RBBINode **rootNode, UErrorCode &status) : |
| fRB(rb), |
| fTree(*rootNode), |
| fStatus(&status), |
| fDStates(nullptr), |
| fSafeTable(nullptr) { |
| if (U_FAILURE(status)) { |
| return; |
| } |
| // fDStates is UVector<RBBIStateDescriptor *> |
| fDStates = new UVector(status); |
| if (U_SUCCESS(status) && fDStates == nullptr ) { |
| status = U_MEMORY_ALLOCATION_ERROR; |
| } |
| } |
| |
| |
| |
| RBBITableBuilder::~RBBITableBuilder() { |
| int i; |
| for (i=0; i<fDStates->size(); i++) { |
| delete (RBBIStateDescriptor *)fDStates->elementAt(i); |
| } |
| delete fDStates; |
| delete fSafeTable; |
| delete fLookAheadRuleMap; |
| } |
| |
| |
| //----------------------------------------------------------------------------- |
| // |
| // RBBITableBuilder::buildForwardTable - This is the main function for building |
| // the DFA state transition table from the RBBI rules parse tree. |
| // |
| //----------------------------------------------------------------------------- |
| void RBBITableBuilder::buildForwardTable() { |
| |
| 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("\nParse tree after flattening variable references."); |
| RBBINode::printTree(fTree, 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; |
| RBBINode *endMarkerNode = 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("\nParse tree after flattening Unicode Set references."); |
| RBBINode::printTree(fTree, 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, endMarkerNode); |
| } |
| |
| // |
| // BOF (start of input) test fixup. |
| // |
| if (fRB->fSetBuilder->sawBOF()) { |
| bofFixup(); |
| } |
| |
| // |
| // Build the DFA state transition tables. |
| // |
| buildStateTable(); |
| mapLookAheadRules(); |
| 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(); |
| } |
| |
| |
| |
| //----------------------------------------------------------------------------- |
| // |
| // 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); |
| } |
| } |
| |
| |
| |
| } |
| |
| //----------------------------------------------------------------------------- |
| // |
| // addRuleRootNodes Recursively walk a parse tree, adding all nodes flagged |
| // as roots of a rule to a destination vector. |
| // |
| //----------------------------------------------------------------------------- |
| void RBBITableBuilder::addRuleRootNodes(UVector *dest, RBBINode *node) { |
| if (node == NULL || U_FAILURE(*fStatus)) { |
| return; |
| } |
| if (node->fRuleRoot) { |
| dest->addElement(node, *fStatus); |
| // Note: rules cannot nest. If we found a rule start node, |
| // no child node can also be a start node. |
| return; |
| } |
| addRuleRootNodes(dest, node->fLeftChild); |
| addRuleRootNodes(dest, node->fRightChild); |
| } |
| |
| //----------------------------------------------------------------------------- |
| // |
| // calcChainedFollowPos. Modify the previously calculated followPos sets |
| // to implement rule chaining. NOT described by Aho |
| // |
| //----------------------------------------------------------------------------- |
| void RBBITableBuilder::calcChainedFollowPos(RBBINode *tree, RBBINode *endMarkNode) { |
| |
| UVector leafNodes(*fStatus); |
| if (U_FAILURE(*fStatus)) { |
| return; |
| } |
| |
| // get a list all leaf nodes |
| tree->findNodes(&leafNodes, RBBINode::leafChar, *fStatus); |
| if (U_FAILURE(*fStatus)) { |
| return; |
| } |
| |
| // Collect all leaf nodes that can start matches for rules |
| // with inbound chaining enabled, which is the union of the |
| // firstPosition sets from each of the rule root nodes. |
| |
| UVector ruleRootNodes(*fStatus); |
| addRuleRootNodes(&ruleRootNodes, tree); |
| |
| UVector matchStartNodes(*fStatus); |
| for (int j=0; j<ruleRootNodes.size(); ++j) { |
| RBBINode *node = static_cast<RBBINode *>(ruleRootNodes.elementAt(j)); |
| if (node->fChainIn) { |
| setAdd(&matchStartNodes, node->fFirstPosSet); |
| } |
| } |
| if (U_FAILURE(*fStatus)) { |
| return; |
| } |
| |
| int32_t endNodeIx; |
| int32_t startNodeIx; |
| |
| for (endNodeIx=0; endNodeIx<leafNodes.size(); endNodeIx++) { |
| RBBINode *endNode = (RBBINode *)leafNodes.elementAt(endNodeIx); |
| |
| // Identify leaf nodes that correspond to overall rule match positions. |
| // These include the endMarkNode in their followPos sets. |
| // |
| // Note: do not consider other end marker nodes, those that are added to |
| // look-ahead rules. These can't chain; a match immediately stops |
| // further matching. This leaves exactly one end marker node, the one |
| // at the end of the complete tree. |
| |
| if (!endNode->fFollowPos->contains(endMarkNode)) { |
| continue; |
| } |
| |
| // We've got a node that can end a match. |
| |
| // !!LBCMNoChain implementation: If this node's val correspond to |
| // the Line Break $CM char class, don't chain from it. |
| // TODO: Remove this. !!LBCMNoChain is deprecated, and is not used |
| // by any of the standard ICU rules. |
| 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; |
| } |
| |
| |
| /** |
| * mapLookAheadRules |
| * |
| */ |
| void RBBITableBuilder::mapLookAheadRules() { |
| fLookAheadRuleMap = new UVector32(fRB->fScanner->numRules() + 1, *fStatus); |
| if (fLookAheadRuleMap == nullptr) { |
| *fStatus = U_MEMORY_ALLOCATION_ERROR; |
| } |
| if (U_FAILURE(*fStatus)) { |
| return; |
| } |
| fLookAheadRuleMap->setSize(fRB->fScanner->numRules() + 1); |
| |
| for (int32_t n=0; n<fDStates->size(); n++) { |
| RBBIStateDescriptor *sd = (RBBIStateDescriptor *)fDStates->elementAt(n); |
| int32_t laSlotForState = 0; |
| |
| // Establish the look-ahead slot for this state, if the state covers |
| // any look-ahead nodes - corresponding to the '/' in look-ahead rules. |
| |
| // If any of the look-ahead nodes already have a slot assigned, use it, |
| // otherwise assign a new one. |
| |
| bool sawLookAheadNode = false; |
| for (int32_t ipos=0; ipos<sd->fPositions->size(); ++ipos) { |
| RBBINode *node = static_cast<RBBINode *>(sd->fPositions->elementAt(ipos)); |
| if (node->fType != RBBINode::NodeType::lookAhead) { |
| continue; |
| } |
| sawLookAheadNode = true; |
| int32_t ruleNum = node->fVal; // Set when rule was originally parsed. |
| U_ASSERT(ruleNum < fLookAheadRuleMap->size()); |
| U_ASSERT(ruleNum > 0); |
| int32_t laSlot = fLookAheadRuleMap->elementAti(ruleNum); |
| if (laSlot != 0) { |
| if (laSlotForState == 0) { |
| laSlotForState = laSlot; |
| } else { |
| // TODO: figure out if this can fail, change to setting an error code if so. |
| U_ASSERT(laSlot == laSlotForState); |
| } |
| } |
| } |
| if (!sawLookAheadNode) { |
| continue; |
| } |
| |
| if (laSlotForState == 0) { |
| laSlotForState = ++fLASlotsInUse; |
| } |
| |
| // For each look ahead node covered by this state, |
| // set the mapping from the node's rule number to the look ahead slot. |
| // There can be multiple nodes/rule numbers going to the same la slot. |
| |
| for (int32_t ipos=0; ipos<sd->fPositions->size(); ++ipos) { |
| RBBINode *node = static_cast<RBBINode *>(sd->fPositions->elementAt(ipos)); |
| if (node->fType != RBBINode::NodeType::lookAhead) { |
| continue; |
| } |
| int32_t ruleNum = node->fVal; // Set when rule was originally parsed. |
| int32_t existingVal = fLookAheadRuleMap->elementAti(ruleNum); |
| (void)existingVal; |
| U_ASSERT(existingVal == 0 || existingVal == laSlotForState); |
| fLookAheadRuleMap->setElementAt(laSlotForState, ruleNum); |
| } |
| } |
| |
| } |
| |
| //----------------------------------------------------------------------------- |
| // |
| // 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 ACCEPTING_UNCONDITIONAL (1). |
| |
| if (sd->fAccepting==0) { |
| // State hasn't been marked as accepting yet. Do it now. |
| sd->fAccepting = fLookAheadRuleMap->elementAti(endMarker->fVal); |
| if (sd->fAccepting == 0) { |
| sd->fAccepting = ACCEPTING_UNCONDITIONAL; |
| } |
| } |
| if (sd->fAccepting==ACCEPTING_UNCONDITIONAL && endMarker->fVal != 0) { |
| // Both lookahead and non-lookahead accepting for this state. |
| // Favor the look-ahead, because a look-ahead match needs to |
| // immediately stop the run-time engine. First match, not longest. |
| sd->fAccepting = fLookAheadRuleMap->elementAti(endMarker->fVal); |
| } |
| // implicit else: |
| // if sd->fAccepting already had a value other than 0 or 1, leave it be. |
| } |
| } |
| } |
| } |
| |
| |
| //----------------------------------------------------------------------------- |
| // |
| // 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); |
| U_ASSERT(lookAheadNode->fType == RBBINode::NodeType::lookAhead); |
| |
| for (n=0; n<fDStates->size(); n++) { |
| RBBIStateDescriptor *sd = (RBBIStateDescriptor *)fDStates->elementAt(n); |
| int32_t positionsIdx = sd->fPositions->indexOf(lookAheadNode); |
| if (positionsIdx >= 0) { |
| U_ASSERT(lookAheadNode == sd->fPositions->elementAt(positionsIdx)); |
| uint32_t lookaheadSlot = fLookAheadRuleMap->elementAti(lookAheadNode->fVal); |
| U_ASSERT(sd->fLookAhead == 0 || sd->fLookAhead == lookaheadSlot); |
| // if (sd->fLookAhead != 0 && sd->fLookAhead != lookaheadSlot) { |
| // printf("%s:%d Bingo. sd->fLookAhead:%d lookaheadSlot:%d\n", |
| // __FILE__, __LINE__, sd->fLookAhead, lookaheadSlot); |
| // } |
| sd->fLookAhead = lookaheadSlot; |
| } |
| } |
| } |
| } |
| |
| |
| |
| |
| //----------------------------------------------------------------------------- |
| // |
| // 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; |
| } |
| printf("\n"); |
| RBBINode::printNodeHeader(); |
| RBBINode::printNode(n); |
| 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 |
| |
| // |
| // findDuplCharClassFrom() |
| // |
| bool RBBITableBuilder::findDuplCharClassFrom(IntPair *categories) { |
| int32_t numStates = fDStates->size(); |
| int32_t numCols = fRB->fSetBuilder->getNumCharCategories(); |
| |
| for (; categories->first < numCols-1; categories->first++) { |
| // Note: dictionary & non-dictionary columns cannot be merged. |
| // The limitSecond value prevents considering mixed pairs. |
| // Dictionary categories are >= DictCategoriesStart. |
| // Non dict categories are < DictCategoriesStart. |
| int limitSecond = categories->first < fRB->fSetBuilder->getDictCategoriesStart() ? |
| fRB->fSetBuilder->getDictCategoriesStart() : numCols; |
| for (categories->second=categories->first+1; categories->second < limitSecond; categories->second++) { |
| // Initialized to different values to prevent returning true if numStates = 0 (implies no duplicates). |
| uint16_t table_base = 0; |
| uint16_t table_dupl = 1; |
| for (int32_t state=0; state<numStates; state++) { |
| RBBIStateDescriptor *sd = (RBBIStateDescriptor *)fDStates->elementAt(state); |
| table_base = (uint16_t)sd->fDtran->elementAti(categories->first); |
| table_dupl = (uint16_t)sd->fDtran->elementAti(categories->second); |
| if (table_base != table_dupl) { |
| break; |
| } |
| } |
| if (table_base == table_dupl) { |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| |
| // |
| // removeColumn() |
| // |
| void RBBITableBuilder::removeColumn(int32_t column) { |
| int32_t numStates = fDStates->size(); |
| for (int32_t state=0; state<numStates; state++) { |
| RBBIStateDescriptor *sd = (RBBIStateDescriptor *)fDStates->elementAt(state); |
| U_ASSERT(column < sd->fDtran->size()); |
| sd->fDtran->removeElementAt(column); |
| } |
| } |
| |
| /* |
| * findDuplicateState |
| */ |
| bool RBBITableBuilder::findDuplicateState(IntPair *states) { |
| int32_t numStates = fDStates->size(); |
| int32_t numCols = fRB->fSetBuilder->getNumCharCategories(); |
| |
| for (; states->first<numStates-1; states->first++) { |
| RBBIStateDescriptor *firstSD = (RBBIStateDescriptor *)fDStates->elementAt(states->first); |
| for (states->second=states->first+1; states->second<numStates; states->second++) { |
| RBBIStateDescriptor *duplSD = (RBBIStateDescriptor *)fDStates->elementAt(states->second); |
| if (firstSD->fAccepting != duplSD->fAccepting || |
| firstSD->fLookAhead != duplSD->fLookAhead || |
| firstSD->fTagsIdx != duplSD->fTagsIdx) { |
| continue; |
| } |
| bool rowsMatch = true; |
| for (int32_t col=0; col < numCols; ++col) { |
| int32_t firstVal = firstSD->fDtran->elementAti(col); |
| int32_t duplVal = duplSD->fDtran->elementAti(col); |
| if (!((firstVal == duplVal) || |
| ((firstVal == states->first || firstVal == states->second) && |
| (duplVal == states->first || duplVal == states->second)))) { |
| rowsMatch = false; |
| break; |
| } |
| } |
| if (rowsMatch) { |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| |
| bool RBBITableBuilder::findDuplicateSafeState(IntPair *states) { |
| int32_t numStates = fSafeTable->size(); |
| |
| for (; states->first<numStates-1; states->first++) { |
| UnicodeString *firstRow = static_cast<UnicodeString *>(fSafeTable->elementAt(states->first)); |
| for (states->second=states->first+1; states->second<numStates; states->second++) { |
| UnicodeString *duplRow = static_cast<UnicodeString *>(fSafeTable->elementAt(states->second)); |
| bool rowsMatch = true; |
| int32_t numCols = firstRow->length(); |
| for (int32_t col=0; col < numCols; ++col) { |
| int32_t firstVal = firstRow->charAt(col); |
| int32_t duplVal = duplRow->charAt(col); |
| if (!((firstVal == duplVal) || |
| ((firstVal == states->first || firstVal == states->second) && |
| (duplVal == states->first || duplVal == states->second)))) { |
| rowsMatch = false; |
| break; |
| } |
| } |
| if (rowsMatch) { |
| return true; |
| } |
| } |
| } |
| return false; |
| } |
| |
| |
| void RBBITableBuilder::removeState(IntPair duplStates) { |
| const int32_t keepState = duplStates.first; |
| const int32_t duplState = duplStates.second; |
| U_ASSERT(keepState < duplState); |
| U_ASSERT(duplState < fDStates->size()); |
| |
| RBBIStateDescriptor *duplSD = (RBBIStateDescriptor *)fDStates->elementAt(duplState); |
| fDStates->removeElementAt(duplState); |
| delete duplSD; |
| |
| int32_t numStates = fDStates->size(); |
| int32_t numCols = fRB->fSetBuilder->getNumCharCategories(); |
| for (int32_t state=0; state<numStates; ++state) { |
| RBBIStateDescriptor *sd = (RBBIStateDescriptor *)fDStates->elementAt(state); |
| for (int32_t col=0; col<numCols; col++) { |
| int32_t existingVal = sd->fDtran->elementAti(col); |
| int32_t newVal = existingVal; |
| if (existingVal == duplState) { |
| newVal = keepState; |
| } else if (existingVal > duplState) { |
| newVal = existingVal - 1; |
| } |
| sd->fDtran->setElementAt(newVal, col); |
| } |
| } |
| } |
| |
| void RBBITableBuilder::removeSafeState(IntPair duplStates) { |
| const int32_t keepState = duplStates.first; |
| const int32_t duplState = duplStates.second; |
| U_ASSERT(keepState < duplState); |
| U_ASSERT(duplState < fSafeTable->size()); |
| |
| fSafeTable->removeElementAt(duplState); // Note that fSafeTable has a deleter function |
| // and will auto-delete the removed element. |
| int32_t numStates = fSafeTable->size(); |
| for (int32_t state=0; state<numStates; ++state) { |
| UnicodeString *sd = (UnicodeString *)fSafeTable->elementAt(state); |
| int32_t numCols = sd->length(); |
| for (int32_t col=0; col<numCols; col++) { |
| int32_t existingVal = sd->charAt(col); |
| int32_t newVal = existingVal; |
| if (existingVal == duplState) { |
| newVal = keepState; |
| } else if (existingVal > duplState) { |
| newVal = existingVal - 1; |
| } |
| sd->setCharAt(col, static_cast<char16_t>(newVal)); |
| } |
| } |
| } |
| |
| |
| /* |
| * RemoveDuplicateStates |
| */ |
| int32_t RBBITableBuilder::removeDuplicateStates() { |
| IntPair dupls = {3, 0}; |
| int32_t numStatesRemoved = 0; |
| |
| while (findDuplicateState(&dupls)) { |
| // printf("Removing duplicate states (%d, %d)\n", dupls.first, dupls.second); |
| removeState(dupls); |
| ++numStatesRemoved; |
| } |
| return numStatesRemoved; |
| } |
| |
| |
| //----------------------------------------------------------------------------- |
| // |
| // 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 = offsetof(RBBIStateTable, fTableData); // The header, with no rows to the table. |
| |
| numRows = fDStates->size(); |
| numCols = fRB->fSetBuilder->getNumCharCategories(); |
| |
| if (use8BitsForTable()) { |
| rowSize = offsetof(RBBIStateTableRow8, fNextState) + sizeof(int8_t)*numCols; |
| } else { |
| rowSize = offsetof(RBBIStateTableRow16, fNextState) + sizeof(int16_t)*numCols; |
| } |
| size += numRows * rowSize; |
| return size; |
| } |
| |
| bool RBBITableBuilder::use8BitsForTable() const { |
| return fDStates->size() <= kMaxStateFor8BitsTable; |
| } |
| |
| //----------------------------------------------------------------------------- |
| // |
| // 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; |
| } |
| |
| int32_t catCount = fRB->fSetBuilder->getNumCharCategories(); |
| if (catCount > 0x7fff || |
| fDStates->size() > 0x7fff) { |
| *fStatus = U_BRK_INTERNAL_ERROR; |
| return; |
| } |
| |
| table->fNumStates = fDStates->size(); |
| table->fDictCategoriesStart = fRB->fSetBuilder->getDictCategoriesStart(); |
| table->fLookAheadResultsSize = fLASlotsInUse == ACCEPTING_UNCONDITIONAL ? 0 : fLASlotsInUse + 1; |
| table->fFlags = 0; |
| if (use8BitsForTable()) { |
| table->fRowLen = offsetof(RBBIStateTableRow8, fNextState) + sizeof(uint8_t) * catCount; |
| table->fFlags |= RBBI_8BITS_ROWS; |
| } else { |
| table->fRowLen = offsetof(RBBIStateTableRow16, fNextState) + sizeof(int16_t) * catCount; |
| } |
| if (fRB->fLookAheadHardBreak) { |
| table->fFlags |= RBBI_LOOKAHEAD_HARD_BREAK; |
| } |
| if (fRB->fSetBuilder->sawBOF()) { |
| table->fFlags |= RBBI_BOF_REQUIRED; |
| } |
| |
| for (state=0; state<table->fNumStates; state++) { |
| RBBIStateDescriptor *sd = (RBBIStateDescriptor *)fDStates->elementAt(state); |
| RBBIStateTableRow *row = (RBBIStateTableRow *)(table->fTableData + state*table->fRowLen); |
| if (use8BitsForTable()) { |
| U_ASSERT (sd->fAccepting <= 255); |
| U_ASSERT (sd->fLookAhead <= 255); |
| U_ASSERT (0 <= sd->fTagsIdx && sd->fTagsIdx <= 255); |
| row->r8.fAccepting = sd->fAccepting; |
| row->r8.fLookAhead = sd->fLookAhead; |
| row->r8.fTagsIdx = sd->fTagsIdx; |
| for (col=0; col<catCount; col++) { |
| U_ASSERT (sd->fDtran->elementAti(col) <= kMaxStateFor8BitsTable); |
| row->r8.fNextState[col] = sd->fDtran->elementAti(col); |
| } |
| } else { |
| U_ASSERT (sd->fAccepting <= 0xffff); |
| U_ASSERT (sd->fLookAhead <= 0xffff); |
| U_ASSERT (0 <= sd->fTagsIdx && sd->fTagsIdx <= 0xffff); |
| row->r16.fAccepting = sd->fAccepting; |
| row->r16.fLookAhead = sd->fLookAhead; |
| row->r16.fTagsIdx = sd->fTagsIdx; |
| for (col=0; col<catCount; col++) { |
| row->r16.fNextState[col] = sd->fDtran->elementAti(col); |
| } |
| } |
| } |
| } |
| |
| |
| /** |
| * Synthesize a safe state table from the main state table. |
| */ |
| void RBBITableBuilder::buildSafeReverseTable(UErrorCode &status) { |
| // The safe table creation has three steps: |
| |
| // 1. Identifiy pairs of character classes that are "safe." Safe means that boundaries |
| // following the pair do not depend on context or state before the pair. To test |
| // whether a pair is safe, run it through the main forward state table, starting |
| // from each state. If the the final state is the same, no matter what the starting state, |
| // the pair is safe. |
| // |
| // 2. Build a state table that recognizes the safe pairs. It's similar to their |
| // forward table, with a column for each input character [class], and a row for |
| // each state. Row 1 is the start state, and row 0 is the stop state. Initially |
| // create an additional state for each input character category; being in |
| // one of these states means that the character has been seen, and is potentially |
| // the first of a pair. In each of these rows, the entry for the second character |
| // of a safe pair is set to the stop state (0), indicating that a match was found. |
| // All other table entries are set to the state corresponding the current input |
| // character, allowing that charcter to be the of a start following pair. |
| // |
| // Because the safe rules are to be run in reverse, moving backwards in the text, |
| // the first and second pair categories are swapped when building the table. |
| // |
| // 3. Compress the table. There are typically many rows (states) that are |
| // equivalent - that have zeroes (match completed) in the same columns - |
| // and can be folded together. |
| |
| // Each safe pair is stored as two UChars in the safePair string. |
| UnicodeString safePairs; |
| |
| int32_t numCharClasses = fRB->fSetBuilder->getNumCharCategories(); |
| int32_t numStates = fDStates->size(); |
| |
| for (int32_t c1=0; c1<numCharClasses; ++c1) { |
| for (int32_t c2=0; c2 < numCharClasses; ++c2) { |
| int32_t wantedEndState = -1; |
| int32_t endState = 0; |
| for (int32_t startState = 1; startState < numStates; ++startState) { |
| RBBIStateDescriptor *startStateD = static_cast<RBBIStateDescriptor *>(fDStates->elementAt(startState)); |
| int32_t s2 = startStateD->fDtran->elementAti(c1); |
| RBBIStateDescriptor *s2StateD = static_cast<RBBIStateDescriptor *>(fDStates->elementAt(s2)); |
| endState = s2StateD->fDtran->elementAti(c2); |
| if (wantedEndState < 0) { |
| wantedEndState = endState; |
| } else { |
| if (wantedEndState != endState) { |
| break; |
| } |
| } |
| } |
| if (wantedEndState == endState) { |
| safePairs.append((char16_t)c1); |
| safePairs.append((char16_t)c2); |
| // printf("(%d, %d) ", c1, c2); |
| } |
| } |
| // printf("\n"); |
| } |
| |
| // Populate the initial safe table. |
| // The table as a whole is UVector<UnicodeString> |
| // Each row is represented by a UnicodeString, being used as a Vector<int16>. |
| // Row 0 is the stop state. |
| // Row 1 is the start sate. |
| // Row 2 and beyond are other states, initially one per char class, but |
| // after initial construction, many of the states will be combined, compacting the table. |
| // The String holds the nextState data only. The four leading fields of a row, fAccepting, |
| // fLookAhead, etc. are not needed for the safe table, and are omitted at this stage of building. |
| |
| U_ASSERT(fSafeTable == nullptr); |
| fSafeTable = new UVector(uprv_deleteUObject, uhash_compareUnicodeString, numCharClasses + 2, status); |
| for (int32_t row=0; row<numCharClasses + 2; ++row) { |
| fSafeTable->addElement(new UnicodeString(numCharClasses, 0, numCharClasses+4), status); |
| } |
| |
| // From the start state, each input char class transitions to the state for that input. |
| UnicodeString &startState = *static_cast<UnicodeString *>(fSafeTable->elementAt(1)); |
| for (int32_t charClass=0; charClass < numCharClasses; ++charClass) { |
| // Note: +2 for the start & stop state. |
| startState.setCharAt(charClass, static_cast<char16_t>(charClass+2)); |
| } |
| |
| // Initially make every other state table row look like the start state row, |
| for (int32_t row=2; row<numCharClasses+2; ++row) { |
| UnicodeString &rowState = *static_cast<UnicodeString *>(fSafeTable->elementAt(row)); |
| rowState = startState; // UnicodeString assignment, copies contents. |
| } |
| |
| // Run through the safe pairs, set the next state to zero when pair has been seen. |
| // Zero being the stop state, meaning we found a safe point. |
| for (int32_t pairIdx=0; pairIdx<safePairs.length(); pairIdx+=2) { |
| int32_t c1 = safePairs.charAt(pairIdx); |
| int32_t c2 = safePairs.charAt(pairIdx + 1); |
| |
| UnicodeString &rowState = *static_cast<UnicodeString *>(fSafeTable->elementAt(c2 + 2)); |
| rowState.setCharAt(c1, 0); |
| } |
| |
| // Remove duplicate or redundant rows from the table. |
| IntPair states = {1, 0}; |
| while (findDuplicateSafeState(&states)) { |
| // printf("Removing duplicate safe states (%d, %d)\n", states.first, states.second); |
| removeSafeState(states); |
| } |
| } |
| |
| |
| //----------------------------------------------------------------------------- |
| // |
| // getSafeTableSize() Calculate the size of the runtime form of this |
| // safe state table. |
| // |
| //----------------------------------------------------------------------------- |
| int32_t RBBITableBuilder::getSafeTableSize() const { |
| int32_t size = 0; |
| int32_t numRows; |
| int32_t numCols; |
| int32_t rowSize; |
| |
| if (fSafeTable == nullptr) { |
| return 0; |
| } |
| |
| size = offsetof(RBBIStateTable, fTableData); // The header, with no rows to the table. |
| |
| numRows = fSafeTable->size(); |
| numCols = fRB->fSetBuilder->getNumCharCategories(); |
| |
| if (use8BitsForSafeTable()) { |
| rowSize = offsetof(RBBIStateTableRow8, fNextState) + sizeof(int8_t)*numCols; |
| } else { |
| rowSize = offsetof(RBBIStateTableRow16, fNextState) + sizeof(int16_t)*numCols; |
| } |
| size += numRows * rowSize; |
| return size; |
| } |
| |
| bool RBBITableBuilder::use8BitsForSafeTable() const { |
| return fSafeTable->size() <= kMaxStateFor8BitsTable; |
| } |
| |
| //----------------------------------------------------------------------------- |
| // |
| // exportSafeTable() 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::exportSafeTable(void *where) { |
| RBBIStateTable *table = (RBBIStateTable *)where; |
| uint32_t state; |
| int col; |
| |
| if (U_FAILURE(*fStatus) || fSafeTable == nullptr) { |
| return; |
| } |
| |
| int32_t catCount = fRB->fSetBuilder->getNumCharCategories(); |
| if (catCount > 0x7fff || |
| fSafeTable->size() > 0x7fff) { |
| *fStatus = U_BRK_INTERNAL_ERROR; |
| return; |
| } |
| |
| table->fNumStates = fSafeTable->size(); |
| table->fFlags = 0; |
| if (use8BitsForSafeTable()) { |
| table->fRowLen = offsetof(RBBIStateTableRow8, fNextState) + sizeof(uint8_t) * catCount; |
| table->fFlags |= RBBI_8BITS_ROWS; |
| } else { |
| table->fRowLen = offsetof(RBBIStateTableRow16, fNextState) + sizeof(int16_t) * catCount; |
| } |
| |
| for (state=0; state<table->fNumStates; state++) { |
| UnicodeString *rowString = (UnicodeString *)fSafeTable->elementAt(state); |
| RBBIStateTableRow *row = (RBBIStateTableRow *)(table->fTableData + state*table->fRowLen); |
| if (use8BitsForSafeTable()) { |
| row->r8.fAccepting = 0; |
| row->r8.fLookAhead = 0; |
| row->r8.fTagsIdx = 0; |
| for (col=0; col<catCount; col++) { |
| U_ASSERT(rowString->charAt(col) <= kMaxStateFor8BitsTable); |
| row->r8.fNextState[col] = static_cast<uint8_t>(rowString->charAt(col)); |
| } |
| } else { |
| row->r16.fAccepting = 0; |
| row->r16.fLookAhead = 0; |
| row->r16.fTagsIdx = 0; |
| for (col=0; col<catCount; col++) { |
| row->r16.fNextState[col] = rowString->charAt(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++) { |
| const RBBINode *v = static_cast<const RBBINode *>(s->elementAt(i)); |
| RBBIDebugPrintf("%5d", v==NULL? -1 : v->fSerialNum); |
| } |
| 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(" %3d", 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(" %3d", sd->fDtran->elementAti(c)); |
| } |
| RBBIDebugPrintf("\n"); |
| } |
| RBBIDebugPrintf("\n\n"); |
| } |
| #endif |
| |
| |
| //----------------------------------------------------------------------------- |
| // |
| // printSafeTable Debug Function. Dump the fully constructed safe table. |
| // |
| //----------------------------------------------------------------------------- |
| #ifdef RBBI_DEBUG |
| void RBBITableBuilder::printReverseTable() { |
| int c; // input "character" |
| int n; // state number |
| |
| RBBIDebugPrintf(" Safe Reverse Table \n"); |
| if (fSafeTable == nullptr) { |
| RBBIDebugPrintf(" --- nullptr ---\n"); |
| return; |
| } |
| 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<fSafeTable->size(); n++) { |
| UnicodeString *rowString = (UnicodeString *)fSafeTable->elementAt(n); |
| RBBIDebugPrintf(" %3d | " , n); |
| RBBIDebugPrintf("%3d %3d %5d ", 0, 0, 0); // Accepting, LookAhead, Tags |
| for (c=0; c<fRB->fSetBuilder->getNumCharCategories(); c++) { |
| RBBIDebugPrintf(" %2d", rowString->charAt(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 UVector32(lastInputSymbol+1, *fStatus); |
| if (U_FAILURE(*fStatus)) { |
| return; |
| } |
| if (fDtran == NULL) { |
| *fStatus = U_MEMORY_ALLOCATION_ERROR; |
| return; |
| } |
| fDtran->setSize(lastInputSymbol+1); // 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 */ |
