diff options
Diffstat (limited to 'deps/node/deps/icu-small/source/common/rbbisetb.cpp')
-rw-r--r-- | deps/node/deps/icu-small/source/common/rbbisetb.cpp | 684 |
1 files changed, 0 insertions, 684 deletions
diff --git a/deps/node/deps/icu-small/source/common/rbbisetb.cpp b/deps/node/deps/icu-small/source/common/rbbisetb.cpp deleted file mode 100644 index e6b98cf3..00000000 --- a/deps/node/deps/icu-small/source/common/rbbisetb.cpp +++ /dev/null @@ -1,684 +0,0 @@ -// © 2016 and later: Unicode, Inc. and others. -// License & terms of use: http://www.unicode.org/copyright.html -// -// rbbisetb.cpp -// -/* -*************************************************************************** -* Copyright (C) 2002-2008 International Business Machines Corporation * -* and others. All rights reserved. * -*************************************************************************** -*/ -// -// RBBISetBuilder Handles processing of Unicode Sets from RBBI rules -// (part of the rule building process.) -// -// Starting with the rules parse tree from the scanner, -// -// - Enumerate the set of UnicodeSets that are referenced -// by the RBBI rules. -// - compute a set of non-overlapping character ranges -// with all characters within a range belonging to the same -// set of input uniocde sets. -// - Derive a set of non-overlapping UnicodeSet (like things) -// that will correspond to columns in the state table for -// the RBBI execution engine. All characters within one -// of these sets belong to the same set of the original -// UnicodeSets from the user's rules. -// - construct the trie table that maps input characters -// to the index of the matching non-overlapping set of set from -// the previous step. -// - -#include "unicode/utypes.h" - -#if !UCONFIG_NO_BREAK_ITERATION - -#include "unicode/uniset.h" -#include "utrie2.h" -#include "uvector.h" -#include "uassert.h" -#include "cmemory.h" -#include "cstring.h" - -#include "rbbisetb.h" -#include "rbbinode.h" - -U_NAMESPACE_BEGIN - -//------------------------------------------------------------------------ -// -// Constructor -// -//------------------------------------------------------------------------ -RBBISetBuilder::RBBISetBuilder(RBBIRuleBuilder *rb) -{ - fRB = rb; - fStatus = rb->fStatus; - fRangeList = 0; - fTrie = 0; - fTrieSize = 0; - fGroupCount = 0; - fSawBOF = FALSE; -} - - -//------------------------------------------------------------------------ -// -// Destructor -// -//------------------------------------------------------------------------ -RBBISetBuilder::~RBBISetBuilder() -{ - RangeDescriptor *nextRangeDesc; - - // Walk through & delete the linked list of RangeDescriptors - for (nextRangeDesc = fRangeList; nextRangeDesc!=NULL;) { - RangeDescriptor *r = nextRangeDesc; - nextRangeDesc = r->fNext; - delete r; - } - - utrie2_close(fTrie); -} - - - - -//------------------------------------------------------------------------ -// -// build Build the list of non-overlapping character ranges -// from the Unicode Sets. -// -//------------------------------------------------------------------------ -void RBBISetBuilder::buildRanges() { - RBBINode *usetNode; - RangeDescriptor *rlRange; - - if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "usets")) {printSets();} - - // - // Initialize the process by creating a single range encompassing all characters - // that is in no sets. - // - fRangeList = new RangeDescriptor(*fStatus); // will check for status here - if (fRangeList == NULL) { - *fStatus = U_MEMORY_ALLOCATION_ERROR; - return; - } - fRangeList->fStartChar = 0; - fRangeList->fEndChar = 0x10ffff; - - if (U_FAILURE(*fStatus)) { - return; - } - - // - // Find the set of non-overlapping ranges of characters - // - int ni; - for (ni=0; ; ni++) { // Loop over each of the UnicodeSets encountered in the input rules - usetNode = (RBBINode *)this->fRB->fUSetNodes->elementAt(ni); - if (usetNode==NULL) { - break; - } - - UnicodeSet *inputSet = usetNode->fInputSet; - int32_t inputSetRangeCount = inputSet->getRangeCount(); - int inputSetRangeIndex = 0; - rlRange = fRangeList; - - for (;;) { - if (inputSetRangeIndex >= inputSetRangeCount) { - break; - } - UChar32 inputSetRangeBegin = inputSet->getRangeStart(inputSetRangeIndex); - UChar32 inputSetRangeEnd = inputSet->getRangeEnd(inputSetRangeIndex); - - // skip over ranges from the range list that are completely - // below the current range from the input unicode set. - while (rlRange->fEndChar < inputSetRangeBegin) { - rlRange = rlRange->fNext; - } - - // If the start of the range from the range list is before with - // the start of the range from the unicode set, split the range list range - // in two, with one part being before (wholly outside of) the unicode set - // and the other containing the rest. - // Then continue the loop; the post-split current range will then be skipped - // over - if (rlRange->fStartChar < inputSetRangeBegin) { - rlRange->split(inputSetRangeBegin, *fStatus); - if (U_FAILURE(*fStatus)) { - return; - } - continue; - } - - // Same thing at the end of the ranges... - // If the end of the range from the range list doesn't coincide with - // the end of the range from the unicode set, split the range list - // range in two. The first part of the split range will be - // wholly inside the Unicode set. - if (rlRange->fEndChar > inputSetRangeEnd) { - rlRange->split(inputSetRangeEnd+1, *fStatus); - if (U_FAILURE(*fStatus)) { - return; - } - } - - // The current rlRange is now entirely within the UnicodeSet range. - // Add this unicode set to the list of sets for this rlRange - if (rlRange->fIncludesSets->indexOf(usetNode) == -1) { - rlRange->fIncludesSets->addElement(usetNode, *fStatus); - if (U_FAILURE(*fStatus)) { - return; - } - } - - // Advance over ranges that we are finished with. - if (inputSetRangeEnd == rlRange->fEndChar) { - inputSetRangeIndex++; - } - rlRange = rlRange->fNext; - } - } - - if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "range")) { printRanges();} - - // - // Group the above ranges, with each group consisting of one or more - // ranges that are in exactly the same set of original UnicodeSets. - // The groups are numbered, and these group numbers are the set of - // input symbols recognized by the run-time state machine. - // - // Numbering: # 0 (state table column 0) is unused. - // # 1 is reserved - table column 1 is for end-of-input - // # 2 is reserved - table column 2 is for beginning-in-input - // # 3 is the first range list. - // - RangeDescriptor *rlSearchRange; - for (rlRange = fRangeList; rlRange!=0; rlRange=rlRange->fNext) { - for (rlSearchRange=fRangeList; rlSearchRange != rlRange; rlSearchRange=rlSearchRange->fNext) { - if (rlRange->fIncludesSets->equals(*rlSearchRange->fIncludesSets)) { - rlRange->fNum = rlSearchRange->fNum; - break; - } - } - if (rlRange->fNum == 0) { - fGroupCount ++; - rlRange->fNum = fGroupCount+2; - rlRange->setDictionaryFlag(); - addValToSets(rlRange->fIncludesSets, fGroupCount+2); - } - } - - // Handle input sets that contain the special string {eof}. - // Column 1 of the state table is reserved for EOF on input. - // Column 2 is reserved for before-the-start-input. - // (This column can be optimized away later if there are no rule - // references to {bof}.) - // Add this column value (1 or 2) to the equivalent expression - // subtree for each UnicodeSet that contains the string {eof} - // Because {bof} and {eof} are not a characters in the normal sense, - // they doesn't affect the computation of ranges or TRIE. - static const UChar eofUString[] = {0x65, 0x6f, 0x66, 0}; - static const UChar bofUString[] = {0x62, 0x6f, 0x66, 0}; - - UnicodeString eofString(eofUString); - UnicodeString bofString(bofUString); - for (ni=0; ; ni++) { // Loop over each of the UnicodeSets encountered in the input rules - usetNode = (RBBINode *)this->fRB->fUSetNodes->elementAt(ni); - if (usetNode==NULL) { - break; - } - UnicodeSet *inputSet = usetNode->fInputSet; - if (inputSet->contains(eofString)) { - addValToSet(usetNode, 1); - } - if (inputSet->contains(bofString)) { - addValToSet(usetNode, 2); - fSawBOF = TRUE; - } - } - - - if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "rgroup")) {printRangeGroups();} - if (fRB->fDebugEnv && uprv_strstr(fRB->fDebugEnv, "esets")) {printSets();} -} - - -// -// Build the Trie table for mapping UChar32 values to the corresponding -// range group number. -// -void RBBISetBuilder::buildTrie() { - RangeDescriptor *rlRange; - - fTrie = utrie2_open(0, // Initial value for all code points. - 0, // Error value for out-of-range input. - fStatus); - - for (rlRange = fRangeList; rlRange!=0 && U_SUCCESS(*fStatus); rlRange=rlRange->fNext) { - utrie2_setRange32(fTrie, - rlRange->fStartChar, // Range start - rlRange->fEndChar, // Range end (inclusive) - rlRange->fNum, // value for range - TRUE, // Overwrite previously written values - fStatus); - } -} - - -void RBBISetBuilder::mergeCategories(IntPair categories) { - U_ASSERT(categories.first >= 1); - U_ASSERT(categories.second > categories.first); - for (RangeDescriptor *rd = fRangeList; rd != nullptr; rd = rd->fNext) { - int32_t rangeNum = rd->fNum & ~DICT_BIT; - int32_t rangeDict = rd->fNum & DICT_BIT; - if (rangeNum == categories.second) { - rd->fNum = categories.first | rangeDict; - } else if (rangeNum > categories.second) { - rd->fNum--; - } - } - --fGroupCount; -} - - -//----------------------------------------------------------------------------------- -// -// getTrieSize() Return the size that will be required to serialize the Trie. -// -//----------------------------------------------------------------------------------- -int32_t RBBISetBuilder::getTrieSize() { - if (U_FAILURE(*fStatus)) { - return 0; - } - utrie2_freeze(fTrie, UTRIE2_16_VALUE_BITS, fStatus); - fTrieSize = utrie2_serialize(fTrie, - NULL, // Buffer - 0, // Capacity - fStatus); - if (*fStatus == U_BUFFER_OVERFLOW_ERROR) { - *fStatus = U_ZERO_ERROR; - } - // RBBIDebugPrintf("Trie table size is %d\n", trieSize); - return fTrieSize; -} - - -//----------------------------------------------------------------------------------- -// -// serializeTrie() Put the serialized trie at the specified address. -// Trust the caller to have given us enough memory. -// getTrieSize() MUST be called first. -// -//----------------------------------------------------------------------------------- -void RBBISetBuilder::serializeTrie(uint8_t *where) { - utrie2_serialize(fTrie, - where, // Buffer - fTrieSize, // Capacity - fStatus); -} - -//------------------------------------------------------------------------ -// -// addValToSets Add a runtime-mapped input value to each uset from a -// list of uset nodes. (val corresponds to a state table column.) -// For each of the original Unicode sets - which correspond -// directly to uset nodes - a logically equivalent expression -// is constructed in terms of the remapped runtime input -// symbol set. This function adds one runtime input symbol to -// a list of sets. -// -// The "logically equivalent expression" is the tree for an -// or-ing together of all of the symbols that go into the set. -// -//------------------------------------------------------------------------ -void RBBISetBuilder::addValToSets(UVector *sets, uint32_t val) { - int32_t ix; - - for (ix=0; ix<sets->size(); ix++) { - RBBINode *usetNode = (RBBINode *)sets->elementAt(ix); - addValToSet(usetNode, val); - } -} - -void RBBISetBuilder::addValToSet(RBBINode *usetNode, uint32_t val) { - RBBINode *leafNode = new RBBINode(RBBINode::leafChar); - if (leafNode == NULL) { - *fStatus = U_MEMORY_ALLOCATION_ERROR; - return; - } - leafNode->fVal = (unsigned short)val; - if (usetNode->fLeftChild == NULL) { - usetNode->fLeftChild = leafNode; - leafNode->fParent = usetNode; - } else { - // There are already input symbols present for this set. - // Set up an OR node, with the previous stuff as the left child - // and the new value as the right child. - RBBINode *orNode = new RBBINode(RBBINode::opOr); - if (orNode == NULL) { - *fStatus = U_MEMORY_ALLOCATION_ERROR; - return; - } - orNode->fLeftChild = usetNode->fLeftChild; - orNode->fRightChild = leafNode; - orNode->fLeftChild->fParent = orNode; - orNode->fRightChild->fParent = orNode; - usetNode->fLeftChild = orNode; - orNode->fParent = usetNode; - } -} - - -//------------------------------------------------------------------------ -// -// getNumCharCategories -// -//------------------------------------------------------------------------ -int32_t RBBISetBuilder::getNumCharCategories() const { - return fGroupCount + 3; -} - - -//------------------------------------------------------------------------ -// -// sawBOF -// -//------------------------------------------------------------------------ -UBool RBBISetBuilder::sawBOF() const { - return fSawBOF; -} - - -//------------------------------------------------------------------------ -// -// getFirstChar Given a runtime RBBI character category, find -// the first UChar32 that is in the set of chars -// in the category. -//------------------------------------------------------------------------ -UChar32 RBBISetBuilder::getFirstChar(int32_t category) const { - RangeDescriptor *rlRange; - UChar32 retVal = (UChar32)-1; - for (rlRange = fRangeList; rlRange!=0; rlRange=rlRange->fNext) { - if (rlRange->fNum == category) { - retVal = rlRange->fStartChar; - break; - } - } - return retVal; -} - - - -//------------------------------------------------------------------------ -// -// printRanges A debugging function. -// dump out all of the range definitions. -// -//------------------------------------------------------------------------ -#ifdef RBBI_DEBUG -void RBBISetBuilder::printRanges() { - RangeDescriptor *rlRange; - int i; - - RBBIDebugPrintf("\n\n Nonoverlapping Ranges ...\n"); - for (rlRange = fRangeList; rlRange!=0; rlRange=rlRange->fNext) { - RBBIDebugPrintf("%2i %4x-%4x ", rlRange->fNum, rlRange->fStartChar, rlRange->fEndChar); - - for (i=0; i<rlRange->fIncludesSets->size(); i++) { - RBBINode *usetNode = (RBBINode *)rlRange->fIncludesSets->elementAt(i); - UnicodeString setName = UNICODE_STRING("anon", 4); - RBBINode *setRef = usetNode->fParent; - if (setRef != NULL) { - RBBINode *varRef = setRef->fParent; - if (varRef != NULL && varRef->fType == RBBINode::varRef) { - setName = varRef->fText; - } - } - RBBI_DEBUG_printUnicodeString(setName); RBBIDebugPrintf(" "); - } - RBBIDebugPrintf("\n"); - } -} -#endif - - -//------------------------------------------------------------------------ -// -// printRangeGroups A debugging function. -// dump out all of the range groups. -// -//------------------------------------------------------------------------ -#ifdef RBBI_DEBUG -void RBBISetBuilder::printRangeGroups() { - RangeDescriptor *rlRange; - RangeDescriptor *tRange; - int i; - int lastPrintedGroupNum = 0; - - RBBIDebugPrintf("\nRanges grouped by Unicode Set Membership...\n"); - for (rlRange = fRangeList; rlRange!=0; rlRange=rlRange->fNext) { - int groupNum = rlRange->fNum & 0xbfff; - if (groupNum > lastPrintedGroupNum) { - lastPrintedGroupNum = groupNum; - RBBIDebugPrintf("%2i ", groupNum); - - if (rlRange->fNum & DICT_BIT) { RBBIDebugPrintf(" <DICT> ");} - - for (i=0; i<rlRange->fIncludesSets->size(); i++) { - RBBINode *usetNode = (RBBINode *)rlRange->fIncludesSets->elementAt(i); - UnicodeString setName = UNICODE_STRING("anon", 4); - RBBINode *setRef = usetNode->fParent; - if (setRef != NULL) { - RBBINode *varRef = setRef->fParent; - if (varRef != NULL && varRef->fType == RBBINode::varRef) { - setName = varRef->fText; - } - } - RBBI_DEBUG_printUnicodeString(setName); RBBIDebugPrintf(" "); - } - - i = 0; - for (tRange = rlRange; tRange != 0; tRange = tRange->fNext) { - if (tRange->fNum == rlRange->fNum) { - if (i++ % 5 == 0) { - RBBIDebugPrintf("\n "); - } - RBBIDebugPrintf(" %05x-%05x", tRange->fStartChar, tRange->fEndChar); - } - } - RBBIDebugPrintf("\n"); - } - } - RBBIDebugPrintf("\n"); -} -#endif - - -//------------------------------------------------------------------------ -// -// printSets A debugging function. -// dump out all of the set definitions. -// -//------------------------------------------------------------------------ -#ifdef RBBI_DEBUG -void RBBISetBuilder::printSets() { - int i; - - RBBIDebugPrintf("\n\nUnicode Sets List\n------------------\n"); - for (i=0; ; i++) { - RBBINode *usetNode; - RBBINode *setRef; - RBBINode *varRef; - UnicodeString setName; - - usetNode = (RBBINode *)fRB->fUSetNodes->elementAt(i); - if (usetNode == NULL) { - break; - } - - RBBIDebugPrintf("%3d ", i); - setName = UNICODE_STRING("anonymous", 9); - setRef = usetNode->fParent; - if (setRef != NULL) { - varRef = setRef->fParent; - if (varRef != NULL && varRef->fType == RBBINode::varRef) { - setName = varRef->fText; - } - } - RBBI_DEBUG_printUnicodeString(setName); - RBBIDebugPrintf(" "); - RBBI_DEBUG_printUnicodeString(usetNode->fText); - RBBIDebugPrintf("\n"); - if (usetNode->fLeftChild != NULL) { - RBBINode::printTree(usetNode->fLeftChild, TRUE); - } - } - RBBIDebugPrintf("\n"); -} -#endif - - - -//------------------------------------------------------------------------------------- -// -// RangeDescriptor copy constructor -// -//------------------------------------------------------------------------------------- - -RangeDescriptor::RangeDescriptor(const RangeDescriptor &other, UErrorCode &status) { - int i; - - this->fStartChar = other.fStartChar; - this->fEndChar = other.fEndChar; - this->fNum = other.fNum; - this->fNext = NULL; - UErrorCode oldstatus = status; - this->fIncludesSets = new UVector(status); - if (U_FAILURE(oldstatus)) { - status = oldstatus; - } - if (U_FAILURE(status)) { - return; - } - /* test for NULL */ - if (this->fIncludesSets == 0) { - status = U_MEMORY_ALLOCATION_ERROR; - return; - } - - for (i=0; i<other.fIncludesSets->size(); i++) { - this->fIncludesSets->addElement(other.fIncludesSets->elementAt(i), status); - } -} - - -//------------------------------------------------------------------------------------- -// -// RangeDesriptor default constructor -// -//------------------------------------------------------------------------------------- -RangeDescriptor::RangeDescriptor(UErrorCode &status) { - this->fStartChar = 0; - this->fEndChar = 0; - this->fNum = 0; - this->fNext = NULL; - UErrorCode oldstatus = status; - this->fIncludesSets = new UVector(status); - if (U_FAILURE(oldstatus)) { - status = oldstatus; - } - if (U_FAILURE(status)) { - return; - } - /* test for NULL */ - if(this->fIncludesSets == 0) { - status = U_MEMORY_ALLOCATION_ERROR; - return; - } - -} - - -//------------------------------------------------------------------------------------- -// -// RangeDesriptor Destructor -// -//------------------------------------------------------------------------------------- -RangeDescriptor::~RangeDescriptor() { - delete fIncludesSets; - fIncludesSets = NULL; -} - -//------------------------------------------------------------------------------------- -// -// RangeDesriptor::split() -// -//------------------------------------------------------------------------------------- -void RangeDescriptor::split(UChar32 where, UErrorCode &status) { - U_ASSERT(where>fStartChar && where<=fEndChar); - RangeDescriptor *nr = new RangeDescriptor(*this, status); - if(nr == 0) { - status = U_MEMORY_ALLOCATION_ERROR; - return; - } - if (U_FAILURE(status)) { - delete nr; - return; - } - // RangeDescriptor copy constructor copies all fields. - // Only need to update those that are different after the split. - nr->fStartChar = where; - this->fEndChar = where-1; - nr->fNext = this->fNext; - this->fNext = nr; -} - - -//------------------------------------------------------------------------------------- -// -// RangeDescriptor::setDictionaryFlag -// -// Character Category Numbers that include characters from -// the original Unicode Set named "dictionary" have bit 14 -// set to 1. The RBBI runtime engine uses this to trigger -// use of the word dictionary. -// -// This function looks through the Unicode Sets that it -// (the range) includes, and sets the bit in fNum when -// "dictionary" is among them. -// -// TODO: a faster way would be to find the set node for -// "dictionary" just once, rather than looking it -// up by name every time. -// -//------------------------------------------------------------------------------------- -void RangeDescriptor::setDictionaryFlag() { - int i; - - static const char16_t *dictionary = u"dictionary"; - for (i=0; i<fIncludesSets->size(); i++) { - RBBINode *usetNode = (RBBINode *)fIncludesSets->elementAt(i); - RBBINode *setRef = usetNode->fParent; - if (setRef != nullptr) { - RBBINode *varRef = setRef->fParent; - if (varRef && varRef->fType == RBBINode::varRef) { - const UnicodeString *setName = &varRef->fText; - if (setName->compare(dictionary, -1) == 0) { - fNum |= RBBISetBuilder::DICT_BIT; - break; - } - } - } - } -} - - - -U_NAMESPACE_END - -#endif /* #if !UCONFIG_NO_BREAK_ITERATION */ |