Adding upstream version 115.8.0esr.upstream/115.8.0esr

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 1810 insertions, 0 deletions

diff --git a/intl/icu/source/common/rbbitblb.cpp b/intl/icu/source/common/rbbitblb.cpp
new file mode 100644
index 0000000000..0c2bcff4e5
--- /dev/null
+++ b/intl/icu/source/common/rbbitblb.cpp
@@ -0,0 +1,1810 @@
+// © 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==nullptr) {
+        return;
+    }
+
+    //
+    // Walk through the tree, replacing any references to $variables with a copy of the
+    //   parse tree for the substitution 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 == nullptr || bofLeaf == nullptr) {
+            *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 == nullptr) {
+        *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 == nullptr) {
+        *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 algorithm 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 == nullptr) {
+        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 == nullptr) {
+        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 == nullptr) {
+        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 == nullptr ||
+        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 == nullptr || U_FAILURE(*fStatus)) {
+        return;
+    }
+    U_ASSERT(!dest->hasDeleter());
+    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 nullptr to avoid uninitialized warning
+    RBBIStateDescriptor *initialState = nullptr;
+    //
+    // Add a dummy state 0 - the stop state.  Not from Aho.
+    int      lastInputSymbol = fRB->fSetBuilder->getNumCharCategories() - 1;
+    failState = new RBBIStateDescriptor(lastInputSymbol, fStatus);
+    if (failState == nullptr) {
+        *fStatus = U_MEMORY_ALLOCATION_ERROR;
+        goto ExitBuildSTdeleteall;
+    }
+    failState->fPositions = new UVector(*fStatus);
+    if (failState->fPositions == nullptr) {
+        *fStatus = U_MEMORY_ALLOCATION_ERROR;
+    }
+    if (failState->fPositions == nullptr || 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 == nullptr) {
+        *fStatus = U_MEMORY_ALLOCATION_ERROR;
+    }
+    if (U_FAILURE(*fStatus)) {
+        goto ExitBuildSTdeleteall;
+    }
+    initialState->fPositions = new UVector(*fStatus);
+    if (initialState->fPositions == nullptr) {
+        *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 = nullptr;
+        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 == nullptr) {
+            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 = nullptr;
+            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 == nullptr) {
+                        U = new UVector(*fStatus);
+                        if (U == nullptr) {
+                        	*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 != nullptr) {
+                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 == nullptr) {
+                    	*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 occurred.
+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 == nullptr) {
+            // 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 == nullptr) {
+        *vector = new UVector(*fStatus);
+    }
+    if (*vector == nullptr || 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) {
+    U_ASSERT(!dest->hasDeleter());
+    U_ASSERT(!source->hasDeleter());
+    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) == nullptr) {
+            return;
+        }
+    }
+    destPtr = destArray.getAlias();
+    destLim = destPtr + destOriginalSize;  // destArray.getArrayLimit()?
+
+    if (sourceSize > sourceArray.getCapacity()) {
+        if (sourceArray.resize(sourceSize) == nullptr) {
+            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);
+    if (U_FAILURE(*fStatus)) {
+        return;
+    }
+
+    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==nullptr) {
+        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 == nullptr) {
+        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 == nullptr) {
+        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);
+            RBBIStateTableRow8 *r8 = (RBBIStateTableRow8*)row;
+            r8->fAccepting = sd->fAccepting;
+            r8->fLookAhead = sd->fLookAhead;
+            r8->fTagsIdx   = sd->fTagsIdx;
+            for (col=0; col<catCount; col++) {
+                U_ASSERT (sd->fDtran->elementAti(col) <= kMaxStateFor8BitsTable);
+                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. Identify 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 character 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 state.
+    // 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);
+    LocalPointer<UVector> lpSafeTable(
+        new UVector(uprv_deleteUObject, uhash_compareUnicodeString, numCharClasses + 2, status), status);
+    if (U_FAILURE(status)) {
+        return;
+    }
+    fSafeTable = lpSafeTable.orphan();
+    for (int32_t row=0; row<numCharClasses + 2; ++row) {
+        LocalPointer<UnicodeString> lpString(new UnicodeString(numCharClasses, 0, numCharClasses+4), status);
+        fSafeTable->adoptElement(lpString.orphan(), status);
+    }
+    if (U_FAILURE(status)) {
+        return;
+    }
+
+    // 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()) {
+            RBBIStateTableRow8 *r8 = (RBBIStateTableRow8*)row;
+            r8->fAccepting = 0;
+            r8->fLookAhead = 0;
+            r8->fTagsIdx    = 0;
+            for (col=0; col<catCount; col++) {
+                U_ASSERT(rowString->charAt(col) <= kMaxStateFor8BitsTable);
+                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==nullptr? -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   = nullptr;
+    fPositions = nullptr;
+    fDtran     = nullptr;
+
+    fDtran     = new UVector32(lastInputSymbol+1, *fStatus);
+    if (U_FAILURE(*fStatus)) {
+        return;
+    }
+    if (fDtran == nullptr) {
+        *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 = nullptr;
+    fDtran     = nullptr;
+    fTagVals   = nullptr;
+}
+
+U_NAMESPACE_END
+
+#endif /* #if !UCONFIG_NO_BREAK_ITERATION */