The Tor Browser: intl/icu/source/common/rbbitblb.cpp@6474c204b198 (annotated)

intl/icu/source/common/rbbitblb.cpp@6474c204b198 (annotated)

intl/icu/source/common/rbbitblb.cpp

Wed, 31 Dec 2014 06:09:35 +0100

author: Michael Schloh von Bennewitz <michael@schloh.com>
date: Wed, 31 Dec 2014 06:09:35 +0100
changeset 0: 6474c204b198
permissions: -rw-r--r--

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

 /*
 **********************************************************************
 *   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 "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 */

The Tor Browser / annotate

intl/icu/source/common/rbbitblb.cpp@6474c204b198 (annotated)

intl/icu/source/common/rbbitblb.cpp